| \ Hashed dictionaries 15jul94py |
\ Hashed dictionaries 15jul94py |
| |
|
| $80 Value Hashlen |
\ Copyright (C) 1995,1998,2000 Free Software Foundation, Inc. |
| |
|
| |
\ 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 |
| |
\ as published by the Free Software Foundation; either version 2 |
| |
\ 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 |
| |
\ along with this program; if not, write to the Free Software |
| |
\ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. |
| |
|
| |
[IFUNDEF] allocate |
| |
: reserve-mem here swap allot ; |
| |
\ move to a kernel/memory.fs |
| |
[ELSE] |
| |
: reserve-mem allocate throw ; |
| |
[THEN] |
| |
|
| |
[IFUNDEF] hashbits |
| |
11 Value hashbits |
| |
[THEN] |
| |
1 hashbits lshift Value Hashlen |
| |
|
| |
\ compute hash key 15jul94py |
| |
|
| |
[IFUNDEF] hash |
| |
: hash ( addr len -- key ) |
| |
hashbits (hashkey1) ; |
| |
[THEN] |
| |
|
| Variable insRule insRule on |
Variable insRule insRule on |
| |
Variable revealed |
| |
|
| \ Memory handling 15jul94py |
\ Memory handling 10oct94py |
| |
|
| Variable HashPointer |
Variable HashPointer |
| |
Variable HashIndex |
| |
0 Value HashTable |
| |
|
| : hash-alloc ( addr -- addr ) dup @ 0= IF |
\ forward declarations |
| Hashlen cells allocate throw over ! |
0 Value hashsearch-map |
| dup @ Hashlen cells erase THEN ; |
Defer hash-alloc ( addr -- addr ) |
| |
|
| \ DelFix and NewFix is from bigFORTH 15jul94py |
\ DelFix and NewFix are from bigFORTH 15jul94py |
| |
|
| : DelFix ( addr root -- ) dup @ 2 pick ! ! ; |
: DelFix ( addr root -- ) dup @ 2 pick ! ! ; |
| : NewFix ( root len # -- addr ) |
: NewFix ( root len # -- addr ) |
| BEGIN 2 pick @ ?dup 0= WHILE 2dup * allocate throw |
BEGIN 2 pick @ ?dup 0= WHILE 2dup * reserve-mem |
| over 0 ?DO dup 4 pick DelFix 2 pick + LOOP drop |
over 0 ?DO dup 4 pick DelFix 2 pick + LOOP drop |
| REPEAT >r drop r@ @ rot ! r@ swap erase r> ; |
REPEAT >r drop r@ @ rot ! r@ swap erase r> ; |
| |
|
| \ compute hash key 15jul94py |
: 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# ) |
| |
cells HashTable + ; |
| |
|
| : hash ( addr len -- key ) (hashkey) |
: hash-find ( addr len wordlist -- nfa / false ) |
| \ tuck bounds ?DO I c@ toupper + LOOP |
>r 2dup r> bucket @ (hashlfind) ; |
| Hashlen 1- and ; |
|
| |
|
| : hash-find ( addr len wordlist -- nfa / false ) $C + @ >r |
|
| 2dup hash cells r> + @ (hashfind) ; |
|
| \ BEGIN dup WHILE |
|
| \ 2@ >r >r dup r@ cell+ c@ $1F and = |
|
| \ IF 2dup r@ cell+ char+ capscomp 0= |
|
| \ IF 2drop r> rdrop EXIT THEN THEN |
|
| \ rdrop r> |
|
| \ REPEAT nip nip ; |
|
| |
|
| \ hash vocabularies 16jul94py |
\ hash vocabularies 16jul94py |
| |
|
| : lastlink! ( addr link -- ) |
: lastlink! ( addr link -- ) |
| BEGIN dup @ dup WHILE nip REPEAT drop ! ; |
BEGIN dup @ dup WHILE nip REPEAT drop ! ; |
| |
|
| : (reveal ( addr voc -- ) $C + dup @ 0< IF 2drop EXIT THEN |
: (reveal ( nfa wid -- ) |
| hash-alloc @ over cell+ count $1F and Hash cells + >r |
over name>string rot bucket >r |
| HashPointer 8 $400 NewFix |
HashPointer 2 Cells $400 NewFix |
| tuck cell+ ! r> insRule @ |
tuck cell+ ! r> insRule @ |
| IF dup @ 2 pick ! ! ELSE lastlink! THEN ; |
IF |
| |
dup @ 2 pick ! ! |
| : hash-reveal ( -- ) (reveal) last? IF |
ELSE |
| current @ (reveal THEN ; |
lastlink! |
| |
THEN |
| Create hashsearch ' hash-find A, ' hash-reveal A, ' drop A, |
revealed on ; |
| |
|
| : (initvoc ( addr -- ) cell+ dup @ 0< IF drop EXIT THEN |
: hash-reveal ( nfa wid -- ) |
| insRule @ >r insRule off hash-alloc |
2dup (reveal) (reveal ; |
| 3 cells - hashsearch over cell+ ! dup |
|
| |
: inithash ( wid -- ) |
| |
wordlist-extend |
| |
insRule @ >r insRule off hash-alloc 3 cells - |
| |
dup wordlist-id |
| BEGIN @ dup WHILE 2dup swap (reveal REPEAT |
BEGIN @ dup WHILE 2dup swap (reveal REPEAT |
| 2drop r> insRule ! ; |
2drop r> insRule ! ; |
| |
|
| ' (initvoc IS 'initvoc |
: addall ( -- ) |
| |
voclink |
| : addall ( -- ) voclink |
BEGIN @ dup WHILE |
| BEGIN @ dup @ WHILE dup (initvoc REPEAT drop ; |
dup 0 wordlist-link - |
| |
dup wordlist-map @ reveal-method @ ['] hash-reveal = |
| |
IF inithash ELSE drop THEN |
| |
REPEAT drop ; |
| |
|
| |
: clearhash ( -- ) |
| |
HashTable Hashlen cells bounds |
| |
DO I @ |
| |
BEGIN dup WHILE |
| |
dup @ swap HashPointer DelFix |
| |
REPEAT |
| |
I ! |
| |
cell +LOOP |
| |
HashIndex off |
| |
voclink |
| |
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 ; |
| |
|
| |
: rehashall ( wid -- ) |
| |
drop revealed @ |
| |
IF clearhash addall revealed off |
| |
THEN ; |
| |
|
| |
: (rehash) ( wid -- ) |
| |
dup wordlist-extend @ 0= |
| |
IF inithash |
| |
ELSE rehashall THEN ; |
| |
|
| |
\ >rom ?! |
| |
align here ' hash-find A, ' hash-reveal A, ' (rehash) A, ' (rehash) A, |
| |
to hashsearch-map |
| |
|
| |
\ hash allocate and vocabulary initialization 10oct94py |
| |
|
| |
:noname ( addr -- addr ) |
| |
HashTable 0= |
| |
IF Hashlen cells reserve-mem TO HashTable |
| |
HashTable Hashlen cells erase THEN |
| |
HashIndex @ over ! 1 HashIndex +! |
| |
HashIndex @ Hashlen >= |
| |
[ [IFUNDEF] allocate ] |
| |
ABORT" no more space in hashtable" |
| |
[ [ELSE] ] |
| |
IF HashTable >r clearhash |
| |
1 hashbits 1+ dup to hashbits lshift to hashlen |
| |
r> free >r 0 to HashTable |
| |
addall r> throw |
| |
THEN |
| |
[ [THEN] ] ; is hash-alloc |
| |
|
| \ Hash-Find 01jan93py |
\ Hash-Find 01jan93py |
| |
has? cross 0= |
| |
[IF] |
| |
: make-hash |
| |
hashsearch-map forth-wordlist wordlist-map ! |
| |
addall ; |
| |
make-hash \ Baumsuche ist installiert. |
| |
[ELSE] |
| |
hashsearch-map forth-wordlist wordlist-map ! |
| |
[THEN] |
| |
|
| |
\ for ec version display that vocabulary goes hashed |
| |
|
| |
: hash-cold ( -- ) |
| |
[ has? ec [IF] ] ." Hashing..." [ [THEN] ] |
| |
HashPointer off 0 TO HashTable HashIndex off |
| |
addall |
| |
\ voclink |
| |
\ BEGIN @ dup WHILE |
| |
\ dup 0 wordlist-link - initvoc |
| |
\ REPEAT drop |
| |
[ has? ec [IF] ] ." Done" cr [ [THEN] ] ; |
| |
|
| addall \ Baum aufbauen |
' hash-cold INIT8 chained |
| \ Baumsuche ist installiert. |
|
| |
|
| : .words ( -- ) |
: .words ( -- ) |
| base @ >r hex context @ 3 cells + HashLen 0 |
base @ >r hex HashTable Hashlen 0 |
| DO cr i 2 .r ." : " dup @ i cells + |
DO cr i 2 .r ." : " dup i cells + |
| BEGIN @ dup WHILE |
BEGIN @ dup WHILE |
| dup cell+ @ .name REPEAT drop |
dup cell+ @ name>string type space REPEAT drop |
| LOOP drop r> base ! ; |
LOOP drop r> base ! ; |
| |
|
| |
\ \ this stuff is for evaluating the hash function |
| |
\ : square dup * ; |
| |
|
| |
\ : countwl ( -- sum sumsq ) |
| |
\ \ gives the number of words in the current wordlist |
| |
\ \ and the sum of squares for the sublist lengths |
| |
\ 0 0 |
| |
\ hashtable Hashlen cells bounds DO |
| |
\ 0 i BEGIN |
| |
\ @ dup WHILE |
| |
\ swap 1+ swap |
| |
\ REPEAT |
| |
\ drop |
| |
\ swap over square + |
| |
\ >r + r> |
| |
\ 1 cells |
| |
\ +LOOP ; |
| |
|
| |
\ : chisq ( -- n ) |
| |
\ \ n should have about the same size as Hashlen |
| |
\ countwl Hashlen 2 pick */ swap - ; |
