1*afc2ba1dSToomas Soome #include "ficl.h"
2*afc2ba1dSToomas Soome
3*afc2ba1dSToomas Soome #define FICL_ASSERT_PHASH(hash, expression) FICL_ASSERT(NULL, expression)
4*afc2ba1dSToomas Soome
5*afc2ba1dSToomas Soome /*
6*afc2ba1dSToomas Soome * h a s h F o r g e t
7*afc2ba1dSToomas Soome * Unlink all words in the hash that have addresses greater than or
8*afc2ba1dSToomas Soome * equal to the address supplied. Implementation factor for FORGET
9*afc2ba1dSToomas Soome * and MARKER.
10*afc2ba1dSToomas Soome */
11*afc2ba1dSToomas Soome void
ficlHashForget(ficlHash * hash,void * where)12*afc2ba1dSToomas Soome ficlHashForget(ficlHash *hash, void *where)
13*afc2ba1dSToomas Soome {
14*afc2ba1dSToomas Soome ficlWord *pWord;
15*afc2ba1dSToomas Soome unsigned i;
16*afc2ba1dSToomas Soome
17*afc2ba1dSToomas Soome FICL_ASSERT_PHASH(hash, hash);
18*afc2ba1dSToomas Soome FICL_ASSERT_PHASH(hash, where);
19*afc2ba1dSToomas Soome
20*afc2ba1dSToomas Soome for (i = 0; i < hash->size; i++) {
21*afc2ba1dSToomas Soome pWord = hash->table[i];
22*afc2ba1dSToomas Soome
23*afc2ba1dSToomas Soome while ((void *)pWord >= where) {
24*afc2ba1dSToomas Soome pWord = pWord->link;
25*afc2ba1dSToomas Soome }
26*afc2ba1dSToomas Soome
27*afc2ba1dSToomas Soome hash->table[i] = pWord;
28*afc2ba1dSToomas Soome }
29*afc2ba1dSToomas Soome }
30*afc2ba1dSToomas Soome
31*afc2ba1dSToomas Soome /*
32*afc2ba1dSToomas Soome * h a s h H a s h C o d e
33*afc2ba1dSToomas Soome *
34*afc2ba1dSToomas Soome * Generate a 16 bit hashcode from a character string using a rolling
35*afc2ba1dSToomas Soome * shift and add stolen from PJ Weinberger of Bell Labs fame. Case folds
36*afc2ba1dSToomas Soome * the name before hashing it...
37*afc2ba1dSToomas Soome * N O T E : If string has zero length, returns zero.
38*afc2ba1dSToomas Soome */
39*afc2ba1dSToomas Soome ficlUnsigned16
ficlHashCode(ficlString s)40*afc2ba1dSToomas Soome ficlHashCode(ficlString s)
41*afc2ba1dSToomas Soome {
42*afc2ba1dSToomas Soome /* hashPJW */
43*afc2ba1dSToomas Soome ficlUnsigned8 *trace;
44*afc2ba1dSToomas Soome ficlUnsigned16 code = (ficlUnsigned16)s.length;
45*afc2ba1dSToomas Soome ficlUnsigned16 shift = 0;
46*afc2ba1dSToomas Soome
47*afc2ba1dSToomas Soome if (s.length == 0)
48*afc2ba1dSToomas Soome return (0);
49*afc2ba1dSToomas Soome
50*afc2ba1dSToomas Soome /* changed to run without errors under Purify -- lch */
51*afc2ba1dSToomas Soome for (trace = (ficlUnsigned8 *)s.text;
52*afc2ba1dSToomas Soome s.length && *trace; trace++, s.length--) {
53*afc2ba1dSToomas Soome code = (ficlUnsigned16)((code << 4) + tolower(*trace));
54*afc2ba1dSToomas Soome shift = (ficlUnsigned16)(code & 0xf000);
55*afc2ba1dSToomas Soome if (shift) {
56*afc2ba1dSToomas Soome code ^= (ficlUnsigned16)(shift >> 8);
57*afc2ba1dSToomas Soome code ^= (ficlUnsigned16)shift;
58*afc2ba1dSToomas Soome }
59*afc2ba1dSToomas Soome }
60*afc2ba1dSToomas Soome
61*afc2ba1dSToomas Soome return ((ficlUnsigned16)code);
62*afc2ba1dSToomas Soome }
63*afc2ba1dSToomas Soome
64*afc2ba1dSToomas Soome /*
65*afc2ba1dSToomas Soome * h a s h I n s e r t W o r d
66*afc2ba1dSToomas Soome * Put a word into the hash table using the word's hashcode as
67*afc2ba1dSToomas Soome * an index (modulo the table size).
68*afc2ba1dSToomas Soome */
69*afc2ba1dSToomas Soome void
ficlHashInsertWord(ficlHash * hash,ficlWord * word)70*afc2ba1dSToomas Soome ficlHashInsertWord(ficlHash *hash, ficlWord *word)
71*afc2ba1dSToomas Soome {
72*afc2ba1dSToomas Soome ficlWord **pList;
73*afc2ba1dSToomas Soome
74*afc2ba1dSToomas Soome FICL_ASSERT_PHASH(hash, hash);
75*afc2ba1dSToomas Soome FICL_ASSERT_PHASH(hash, word);
76*afc2ba1dSToomas Soome
77*afc2ba1dSToomas Soome if (hash->size == 1) {
78*afc2ba1dSToomas Soome pList = hash->table;
79*afc2ba1dSToomas Soome } else {
80*afc2ba1dSToomas Soome pList = hash->table + (word->hash % hash->size);
81*afc2ba1dSToomas Soome }
82*afc2ba1dSToomas Soome
83*afc2ba1dSToomas Soome word->link = *pList;
84*afc2ba1dSToomas Soome *pList = word;
85*afc2ba1dSToomas Soome }
86*afc2ba1dSToomas Soome
87*afc2ba1dSToomas Soome /*
88*afc2ba1dSToomas Soome * h a s h L o o k u p
89*afc2ba1dSToomas Soome * Find a name in the hash table given the hashcode and text of the name.
90*afc2ba1dSToomas Soome * Returns the address of the corresponding ficlWord if found,
91*afc2ba1dSToomas Soome * otherwise NULL.
92*afc2ba1dSToomas Soome * Note: outer loop on link field supports inheritance in wordlists.
93*afc2ba1dSToomas Soome * It's not part of ANS Forth - Ficl only. hashReset creates wordlists
94*afc2ba1dSToomas Soome * with NULL link fields.
95*afc2ba1dSToomas Soome */
96*afc2ba1dSToomas Soome ficlWord *
ficlHashLookup(ficlHash * hash,ficlString name,ficlUnsigned16 hashCode)97*afc2ba1dSToomas Soome ficlHashLookup(ficlHash *hash, ficlString name, ficlUnsigned16 hashCode)
98*afc2ba1dSToomas Soome {
99*afc2ba1dSToomas Soome ficlUnsigned nCmp = name.length;
100*afc2ba1dSToomas Soome ficlWord *word;
101*afc2ba1dSToomas Soome ficlUnsigned16 hashIdx;
102*afc2ba1dSToomas Soome
103*afc2ba1dSToomas Soome if (nCmp > FICL_NAME_LENGTH)
104*afc2ba1dSToomas Soome nCmp = FICL_NAME_LENGTH;
105*afc2ba1dSToomas Soome
106*afc2ba1dSToomas Soome for (; hash != NULL; hash = hash->link) {
107*afc2ba1dSToomas Soome if (hash->size > 1)
108*afc2ba1dSToomas Soome hashIdx = (ficlUnsigned16)(hashCode % hash->size);
109*afc2ba1dSToomas Soome else /* avoid the modulo op for single threaded lists */
110*afc2ba1dSToomas Soome hashIdx = 0;
111*afc2ba1dSToomas Soome
112*afc2ba1dSToomas Soome for (word = hash->table[hashIdx]; word; word = word->link) {
113*afc2ba1dSToomas Soome if ((word->length == name.length) &&
114*afc2ba1dSToomas Soome (!ficlStrincmp(name.text, word->name, nCmp)))
115*afc2ba1dSToomas Soome return (word);
116*afc2ba1dSToomas Soome #if FICL_ROBUST
117*afc2ba1dSToomas Soome FICL_ASSERT_PHASH(hash, word != word->link);
118*afc2ba1dSToomas Soome #endif
119*afc2ba1dSToomas Soome }
120*afc2ba1dSToomas Soome }
121*afc2ba1dSToomas Soome
122*afc2ba1dSToomas Soome return (NULL);
123*afc2ba1dSToomas Soome }
124*afc2ba1dSToomas Soome
125*afc2ba1dSToomas Soome /*
126*afc2ba1dSToomas Soome * h a s h R e s e t
127*afc2ba1dSToomas Soome * Initialize a ficlHash to empty state.
128*afc2ba1dSToomas Soome */
129*afc2ba1dSToomas Soome void
ficlHashReset(ficlHash * hash)130*afc2ba1dSToomas Soome ficlHashReset(ficlHash *hash)
131*afc2ba1dSToomas Soome {
132*afc2ba1dSToomas Soome unsigned i;
133*afc2ba1dSToomas Soome
134*afc2ba1dSToomas Soome FICL_ASSERT_PHASH(hash, hash);
135*afc2ba1dSToomas Soome
136*afc2ba1dSToomas Soome for (i = 0; i < hash->size; i++) {
137*afc2ba1dSToomas Soome hash->table[i] = NULL;
138*afc2ba1dSToomas Soome }
139*afc2ba1dSToomas Soome
140*afc2ba1dSToomas Soome hash->link = NULL;
141*afc2ba1dSToomas Soome hash->name = NULL;
142*afc2ba1dSToomas Soome }
143