xref: /illumos-gate/usr/src/common/ficl/hash.c (revision afc2ba1d)
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 }