hash.fs 6.57 KB
Newer Older
pazsan's avatar
pazsan committed
1 2
\ Hashed dictionaries                                  15jul94py

Anton Ertl's avatar
Anton Ertl committed
3
\ Copyright (C) 1995,1998,2000,2003,2006,2007,2009,2013,2017 Free Software Foundation, Inc.
anton's avatar
anton committed
4 5 6 7 8

\ This file is part of Gforth.

\ Gforth is free software; you can redistribute it and/or
\ modify it under the terms of the GNU General Public License
9
\ as published by the Free Software Foundation, either version 3
anton's avatar
anton committed
10 11 12 13 14 15 16 17
\ of the License, or (at your option) any later version.

\ This program is distributed in the hope that it will be useful,
\ but WITHOUT ANY WARRANTY; without even the implied warranty of
\ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
\ GNU General Public License for more details.

\ You should have received a copy of the GNU General Public License
18
\ along with this program. If not, see http://www.gnu.org/licenses/.
anton's avatar
anton committed
19

20 21 22 23
[IFUNDEF] erase
: erase ( addr len -- ) 0 fill ;
[THEN]

jwilke's avatar
jwilke committed
24
[IFUNDEF] allocate
jwilke's avatar
jwilke committed
25 26 27 28 29 30 31
: reserve-mem here swap allot ;
\ move to a kernel/memory.fs
[ELSE]
: reserve-mem allocate throw ;
[THEN]

[IFUNDEF] hashbits
jwilke's avatar
jwilke committed
32
11 Value hashbits
jwilke's avatar
jwilke committed
33
[THEN]
anton's avatar
anton committed
34
1 hashbits lshift Value Hashlen
pazsan's avatar
pazsan committed
35

jwilke's avatar
jwilke committed
36 37
\ compute hash key                                     15jul94py

38 39 40 41 42 43
has? ec [IF] [IFUNDEF] hash
: hash ( addr len -- key )
  over c@ swap 1- IF swap char+ c@ + ELSE nip THEN
  [ Hashlen 1- ] literal and ;
[THEN] [THEN]

jwilke's avatar
jwilke committed
44
[IFUNDEF] hash
45 46 47 48 49 50 51
    [IFDEF] (hashkey2)
	: hash ( addr len -- key )
	    hashbits (hashkey2) ;
    [ELSE]
	: hash ( addr len -- key )
	    hashbits (hashkey1) ;
    [THEN]
jwilke's avatar
jwilke committed
52 53
[THEN]

pazsan's avatar
pazsan committed
54
Variable insRule        insRule on
55
Variable revealed
pazsan's avatar
pazsan committed
56

57
\ Memory handling                                      10oct94py
pazsan's avatar
pazsan committed
58

59
AVariable HashPointer
60 61
Variable HashIndex     \ Number of wordlists
Variable HashPop       \ Number of words
62
0 AValue HashTable
pazsan's avatar
pazsan committed
63

jwilke's avatar
jwilke committed
64
\ forward declarations
65
0 AValue hashsearch-map
anton's avatar
anton committed
66
Defer hash-alloc ( addr -- addr )
jwilke's avatar
jwilke committed
67

68
\ DelFix and NewFix are from bigFORTH                  15jul94py
pazsan's avatar
pazsan committed
69 70 71

: DelFix ( addr root -- ) dup @ 2 pick ! ! ;
: NewFix  ( root len # -- addr )
jwilke's avatar
jwilke committed
72
  BEGIN  2 pick @ ?dup  0= WHILE  2dup * reserve-mem
pazsan's avatar
pazsan committed
73 74 75
         over 0 ?DO  dup 4 pick DelFix 2 pick +  LOOP  drop
  REPEAT  >r drop r@ @ rot ! r@ swap erase r> ;

76 77 78 79
: bucket ( addr len wordlist -- bucket-addr )
    \ @var{bucket-addr} is the address of a cell that points to the first
    \ element in the list of the bucket for the string @var{addr len}
    wordlist-extend @ -rot hash xor ( bucket# )
80
    cells HashTable + ;
anton's avatar
anton committed
81 82

: hash-find ( addr len wordlist -- nfa / false )
anton's avatar
anton committed
83
    >r 2dup r> bucket @ (hashlfind) ;
pazsan's avatar
pazsan committed
84 85 86 87 88 89

\ hash vocabularies                                    16jul94py

: lastlink! ( addr link -- )
  BEGIN  dup @ dup  WHILE  nip  REPEAT  drop ! ;

90
: (reveal ( nfa wid -- )
91 92 93 94 95 96 97 98
    over name>string rot bucket >r
    HashPointer 2 Cells $400 NewFix
    tuck cell+ ! r> insRule @
    IF
	dup @ 2 pick ! !
    ELSE
	lastlink!
    THEN
99
    revealed on 1 HashPop +! 0 hash-alloc drop ;
100

101 102
: hash-reveal ( nfa wid -- )
    2dup (reveal) (reveal ;
103 104
: table-reveal ( nfa wid -- )
    2dup (nocheck-reveal) (reveal ;
pazsan's avatar
pazsan committed
105

Bernd Paysan's avatar
Bernd Paysan committed
106 107
[IFUNDEF] >link ' noop Alias >link [THEN]

jwilke's avatar
jwilke committed
108 109
: inithash ( wid -- )
    wordlist-extend
110
    insRule @ >r  insRule off  1 hash-alloc over ! 3 cells -
111 112
    dup wordlist-id 0 >link -
    BEGIN  >link @ dup  WHILE  2dup swap (reveal  REPEAT
jwilke's avatar
jwilke committed
113 114
    2drop  r> insRule ! ;

115
: addall  ( -- )
116
    HashPop off voclink
jwilke's avatar
jwilke committed
117
    BEGIN  @ dup WHILE
118 119 120 121
	    dup 0 wordlist-link -
	    dup wordlist-map @ reveal-method @
	    dup ['] hash-reveal = swap ['] table-reveal = or
	    IF  inithash ELSE drop THEN
jwilke's avatar
jwilke committed
122
    REPEAT  drop ;
123 124

: clearhash  ( -- )
125
    HashTable Hashlen cells bounds
126
    DO  I @
127
	BEGIN  dup  WHILE
anton's avatar
anton committed
128 129 130 131 132
	    dup @ swap HashPointer DelFix
	REPEAT
	I !
	cell +LOOP
    HashIndex off 
jwilke's avatar
jwilke committed
133
    voclink
anton's avatar
anton committed
134 135 136 137 138 139 140 141 142 143 144 145
    BEGIN ( wordlist-link-addr )
	@ dup
    WHILE ( wordlist-link )
	dup 0 wordlist-link - ( wordlist-link wid ) 
	dup wordlist-map @ hashsearch-map = 
	IF ( wordlist-link wid )
	    0 swap wordlist-extend !
	ELSE
	    drop
	THEN
    REPEAT
    drop ;
jwilke's avatar
jwilke committed
146 147 148 149 150

: rehashall  ( wid -- ) 
  drop revealed @ 
  IF 	clearhash addall revealed off 
  THEN ;
151

jwilke's avatar
jwilke committed
152 153 154 155
: (rehash)   ( wid -- )
  dup wordlist-extend @ 0=
  IF   inithash
  ELSE rehashall THEN ;
156

157 158 159 160 161 162
: hashdouble ( -- )
    HashTable >r clearhash
    1 hashbits 1+ dup  to hashbits  lshift  to hashlen
    r> free >r  0 to HashTable
    addall r> throw ;

163 164 165
const Create (hashsearch-map)
' hash-find A, ' hash-reveal A, ' (rehash) A, ' (rehash) A,
(hashsearch-map) to hashsearch-map
166 167 168

\ hash allocate and vocabulary initialization          10oct94py

169
:noname ( n+ -- n )
jwilke's avatar
jwilke committed
170 171 172
  HashTable 0= 
  IF  Hashlen cells reserve-mem TO HashTable
      HashTable Hashlen cells erase THEN
173
  HashIndex @ swap HashIndex +!
174
  HashIndex @ Hashlen >=
jwilke's avatar
jwilke committed
175
  [ [IFUNDEF] allocate ]
jwilke's avatar
jwilke committed
176 177
  ABORT" no more space in hashtable"
  [ [ELSE] ]
178
  HashPop @ hashlen 2* >= or
179
  IF  hashdouble  THEN 
jwilke's avatar
jwilke committed
180
  [ [THEN] ] ; is hash-alloc
pazsan's avatar
pazsan committed
181 182

\ Hash-Find                                            01jan93py
jwilke's avatar
jwilke committed
183
has? cross 0= 
jwilke's avatar
jwilke committed
184
[IF]
185 186
: hash-wordlist ( wid -- )
  hashsearch-map swap wordlist-map ! ;
187
: make-hash
188 189 190
  forth-wordlist hash-wordlist
  environment-wordlist hash-wordlist
  ['] Root >body hash-wordlist
jwilke's avatar
jwilke committed
191 192 193
  addall ;
  make-hash \ Baumsuche ist installiert.
[ELSE]
194
  hashsearch-map forth-wordlist wordlist-map !
jwilke's avatar
jwilke committed
195
[THEN]
196

jwilke's avatar
jwilke committed
197
\ for ec version display that vocabulary goes hashed
pazsan's avatar
pazsan committed
198

jwilke's avatar
jwilke committed
199
: hash-cold  ( -- )
jwilke's avatar
jwilke committed
200
[ has? ec [IF] ] ." Hashing..." [ [THEN] ]
201
  HashPointer off  0 TO HashTable  HashIndex off
jwilke's avatar
jwilke committed
202 203 204 205 206
  addall
\  voclink
\  BEGIN  @ dup WHILE
\         dup 0 wordlist-link - initvoc
\  REPEAT  drop 
jwilke's avatar
jwilke committed
207
[ has? ec [IF] ] ." Done" cr [ [THEN] ] ;
jwilke's avatar
jwilke committed
208

209 210 211 212
:noname ( -- )
    defers 'cold
    hash-cold
; is 'cold
213 214 215 216
:noname
    defers 'image
    HashPointer off
; is 'image
217

pazsan's avatar
pazsan committed
218
: .words  ( -- )
219
  base @ >r hex HashTable  Hashlen 0
220
  DO  cr  i 2 .r ." : " dup i cells +
pazsan's avatar
pazsan committed
221
      BEGIN  @ dup  WHILE
pazsan's avatar
pazsan committed
222
             dup cell+ @ name>string type space  REPEAT  drop
pazsan's avatar
pazsan committed
223 224
  LOOP  drop r> base ! ;

anton's avatar
anton committed
225 226 227 228
\ \ this stuff is for evaluating the hash function
\ : square dup * ;

\ : countwl  ( -- sum sumsq )
229 230
\     \ gives the number of words in the current wordlist
\     \ and the sum of squares for the sublist lengths
anton's avatar
anton committed
231
\     0 0
232
\     hashtable Hashlen cells bounds DO
233 234 235 236 237 238 239 240 241
\        0 i BEGIN
\            @ dup WHILE
\            swap 1+ swap
\        REPEAT
\        drop
\        swap over square +
\        >r + r>
\        1 cells
\    +LOOP ;
anton's avatar
anton committed
242 243

\ : chisq ( -- n )
244 245
\     \ n should have about the same size as Hashlen
\     countwl Hashlen 2 pick */ swap - ;
246 247 248 249 250 251 252 253 254 255 256 257

\ Create hashhist here $100 cells dup allot erase

\ : .hashhist ( -- )  hashhist $100 cells erase
\     HashTable HashLen cells bounds
\     DO  0 I  BEGIN  @ dup  WHILE  swap 1+ swap  REPEAT  drop
\         1 swap cells hashhist + +!
\     cell +LOOP
\     0 0 $100 0 DO
\         hashhist I cells + @ dup IF
\     	cr I 0 .r ." : " dup .  THEN tuck I * + >r + r>
\     LOOP cr ." Total: " 0 .r ." /" . cr ;