1 /*
2 Copyright (c) 1991-1999 Thomas T. Wetmore IV
3
4 Permission is hereby granted, free of charge, to any person
5 obtaining a copy of this software and associated documentation
6 files (the "Software"), to deal in the Software without
7 restriction, including without limitation the rights to use, copy,
8 modify, merge, publish, distribute, sublicense, and/or sell copies
9 of the Software, and to permit persons to whom the Software is
10 furnished to do so, subject to the following conditions:
11
12 The above copyright notice and this permission notice shall be
13 included in all copies or substantial portions of the Software.
14
15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 SOFTWARE.
23 */
24
25 /*
26 hashtab contains a simple hash table implementation
27 keys are strings (hash table copies & manages memory itself for keys
28 values (void * pointers, they are client's responsibility to free)
29 */
30
31 #include "llstdlib.h"
32 #include "hashtab.h"
33
34 /*********************************************
35 * local enums & defines
36 *********************************************/
37
38 #define MAXHASH_DEF 512
39
40 /*********************************************
41 * local types
42 *********************************************/
43
44 /* entry in hash table */
45 struct tag_hashent {
46 CNSTRING magic;
47 CNSTRING ekey;
48 HVALUE val;
49 struct tag_hashent *enext;
50 };
51 typedef struct tag_hashent *HASHENT;
52
53 /* hash table */
54 struct tag_hashtab {
55 CNSTRING magic;
56 HASHENT *entries;
57 INT count; /* #entries */
58 INT maxhash;
59 };
60 /* typedef struct tag_hashtab *HASHTAB */ /* in hashtab.h */
61
62 /* hash table iterator */
63 struct tag_hashtab_iter {
64 CNSTRING magic;
65 HASHTAB hashtab;
66 INT index;
67 HASHENT enext;
68 };
69
70 /*********************************************
71 * local function prototypes
72 *********************************************/
73
74 static HASHENT create_entry(CNSTRING key, HVALUE val);
75 static HASHENT fndentry(HASHTAB tab, CNSTRING key);
76 static INT hash(HASHTAB tab, CNSTRING key);
77
78 /*********************************************
79 * local variables
80 *********************************************/
81
82 /* fixed magic strings to verify object identity */
83 static CNSTRING hashtab_magic = "HASHTAB_MAGIC";
84 static CNSTRING hashent_magic = "HASHENT_MAGIC";
85 static CNSTRING hashtab_iter_magic = "HASHTAB_ITER_MAGIC";
86
87 /*********************************************
88 * local & exported function definitions
89 * body of module
90 *********************************************/
91
92 /*================================
93 * create_hashtab -- Create & return new hash table
94 *==============================*/
95 HASHTAB
create_hashtab(void)96 create_hashtab (void)
97 {
98 HASHTAB tab = (HASHTAB)stdalloc(sizeof(*tab));
99 tab->magic = hashtab_magic;
100 tab->maxhash = MAXHASH_DEF;
101 tab->entries = (HASHENT *)stdalloc(tab->maxhash * sizeof(HASHENT));
102 return tab;
103 }
104 /*================================
105 * destroy_hashtab -- Destroy hash table
106 *==============================*/
107 void
destroy_hashtab(HASHTAB tab,DELFUNC func)108 destroy_hashtab (HASHTAB tab, DELFUNC func)
109 {
110 INT i=0;
111 if (!tab) return;
112 ASSERT(tab->magic == hashtab_magic);
113 for (i=0; i<tab->maxhash; ++i) {
114 HASHENT entry = tab->entries[i];
115 HASHENT next=0;
116 while (entry) {
117 ASSERT(entry->magic == hashent_magic);
118 next = entry->enext;
119 if (func)
120 (*func)(entry->val);
121 entry->val = 0;
122 strfree((STRING *)&entry->ekey);
123 stdfree(entry);
124 entry = next;
125 }
126 }
127 stdfree(tab->entries);
128 tab->entries = 0;
129 stdfree(tab);
130 }
131 /*======================
132 * get_hashtab_count -- Return number of elements currently contained
133 *====================*/
134 INT
get_hashtab_count(HASHTAB tab)135 get_hashtab_count (HASHTAB tab)
136 {
137 ASSERT(tab);
138 ASSERT(tab->magic == hashtab_magic);
139
140 return tab->count;
141 }
142 /*======================
143 * insert_hashtab -- Add new value to hash table
144 * return previous value for this key, if any
145 *====================*/
146 HVALUE
insert_hashtab(HASHTAB tab,CNSTRING key,HVALUE val)147 insert_hashtab (HASHTAB tab, CNSTRING key, HVALUE val)
148 {
149 HASHENT entry=0;
150 INT hval=0;
151
152 ASSERT(tab);
153 ASSERT(tab->magic == hashtab_magic);
154
155 /* find appropriate has chain */
156 hval = hash(tab, key);
157 if (!tab->entries[hval]) {
158 /* table lacks entry for this key, create it */
159 entry = create_entry(key, val);
160 tab->entries[hval] = entry;
161 ++tab->count;
162 return 0; /* no old value */
163 }
164 entry = tab->entries[hval];
165 while (TRUE) {
166 ASSERT(entry->magic == hashent_magic);
167 if (eqstr(key, entry->ekey)) {
168 /* table already has entry for this key, replace it */
169 HVALUE old = entry->val;
170 entry->val = val;
171 return old;
172 }
173 if (!entry->enext) {
174 /* table lacks entry for this key, create it */
175 HASHENT newent = create_entry(key, val);
176 entry->enext = newent;
177 ++tab->count;
178 return 0; /* no old value */
179 }
180 entry = entry->enext;
181 }
182 }
183 /*======================
184 * remove_hashtab -- Remove element from table
185 * return old value if found
186 *====================*/
187 HVALUE
remove_hashtab(HASHTAB tab,CNSTRING key)188 remove_hashtab (HASHTAB tab, CNSTRING key)
189 {
190 HVALUE val=0;
191 INT hval=0;
192 HASHENT preve=0, thise=0;
193
194 ASSERT(tab);
195 ASSERT(tab->magic == hashtab_magic);
196
197 hval = hash(tab, key);
198 thise = tab->entries[hval];
199 while (thise && nestr(key, thise->ekey)) {
200 ASSERT(thise->magic == hashent_magic);
201 preve = thise;
202 thise = thise->enext;
203 }
204 if (!thise) return 0;
205 if (preve)
206 preve->enext = thise->enext;
207 else
208 tab->entries[hval] = thise->enext;
209
210 val = thise->val;
211 strfree((STRING *)&thise->ekey);
212 thise->val = 0;
213 stdfree(thise);
214 --tab->count;
215 return val;
216 }
217 /*======================
218 * find_hashtab -- Find and return value
219 * set optional present arg to indicate whether value was found
220 *====================*/
221 HVALUE
find_hashtab(HASHTAB tab,CNSTRING key,BOOLEAN * present)222 find_hashtab (HASHTAB tab, CNSTRING key, BOOLEAN * present)
223 {
224 HASHENT entry=0;
225
226 ASSERT(tab);
227 ASSERT(tab->magic == hashtab_magic);
228
229 entry = fndentry(tab, key);
230 if (present) *present = !!entry;
231 if (!entry) return 0;
232
233 ASSERT(entry->magic == hashent_magic);
234 return entry->val;
235 }
236 /*======================
237 * in_hashtab -- Find and return value
238 *====================*/
239 BOOLEAN
in_hashtab(HASHTAB tab,CNSTRING key)240 in_hashtab (HASHTAB tab, CNSTRING key)
241 {
242 HASHENT entry=0;
243
244 ASSERT(tab);
245 ASSERT(tab->magic == hashtab_magic);
246
247 entry = fndentry(tab, key);
248 return (entry != 0);
249 }
250 /*================================
251 * fndentry -- Find entry in table
252 *==============================*/
253 static HASHENT
fndentry(HASHTAB tab,CNSTRING key)254 fndentry (HASHTAB tab, CNSTRING key)
255 {
256 HASHENT entry=0;
257 if (!tab || !key) return NULL;
258 entry = tab->entries[hash(tab, key)];
259 while (entry) {
260 if (eqstr(key, entry->ekey)) return entry;
261 entry = entry->enext;
262 }
263 return NULL;
264 }
265 /*======================
266 * hash -- Hash function
267 *====================*/
268 static INT
hash(HASHTAB tab,CNSTRING key)269 hash (HASHTAB tab, CNSTRING key)
270 {
271 const unsigned char *ckey = (const unsigned char *)key;
272 INT hval = 0;
273 while (*ckey)
274 hval += *ckey++;
275 hval %= tab->maxhash;
276 ASSERT(hval>=0);
277 ASSERT(hval < tab->maxhash);
278 return hval;
279 }
280 /*================================
281 * create_entry -- Create and return new hash entry
282 *==============================*/
283 static HASHENT
create_entry(CNSTRING key,HVALUE val)284 create_entry (CNSTRING key, HVALUE val)
285 {
286 HASHENT entry = (HASHENT)stdalloc(sizeof(*entry));
287 entry->magic = hashent_magic;
288 entry->ekey = strsave(key);
289 entry->val = val;
290 return entry;
291 }
292 /*================================
293 * begin_hashtab -- Create new iterator for hash table
294 *==============================*/
295 HASHTAB_ITER
begin_hashtab(HASHTAB tab)296 begin_hashtab (HASHTAB tab)
297 {
298 HASHTAB_ITER tabit=0;
299 ASSERT(tab);
300 ASSERT(tab->magic == hashtab_magic);
301
302 tabit = (HASHTAB_ITER)stdalloc(sizeof(*tabit));
303 tabit->magic = hashtab_iter_magic;
304 tabit->hashtab = tab;
305 /* table iterator starts at index=0, enext=0 */
306 /* stdalloc gave us all zero memory */
307 return tabit;
308 }
309 /*================================
310 * next_hashtab -- Advance hash table iterator
311 * If not finished, set pointers and return TRUE
312 * If no more entries, return FALSE
313 *==============================*/
314 BOOLEAN
next_hashtab(HASHTAB_ITER tabit,CNSTRING * pkey,HVALUE * pval)315 next_hashtab (HASHTAB_ITER tabit, CNSTRING *pkey, HVALUE *pval)
316 {
317 HASHTAB tab=0;
318 ASSERT(tabit);
319 ASSERT(tabit->magic == hashtab_iter_magic);
320
321 if (!tabit->hashtab) return FALSE;
322 tab = tabit->hashtab;
323
324 if (tabit->index == -1 || tab->count == 0)
325 return FALSE;
326
327 /* continue current hash chain */
328 if (tabit->enext) {
329 tabit->enext = tabit->enext->enext;
330 if (tabit->enext)
331 goto returnit;
332 ++tabit->index;
333 }
334 /* find next populated hash chain */
335 for ( ; tabit->index < tab->maxhash; ++tabit->index) {
336 tabit->enext = tab->entries[tabit->index];
337 if (tabit->enext)
338 goto returnit;
339 }
340 /* finished (ran out of hash chains) */
341 tabit->index = -1;
342 tabit->enext = 0;
343 return FALSE;
344
345 /* found entry */
346 returnit:
347 *pkey = tabit->enext->ekey;
348 *pval = tabit->enext->val;
349 return TRUE;
350
351 }
352 /*================================
353 * end_hashtab -- Release/destroy hash table iterator
354 *==============================*/
355 void
end_hashtab(HASHTAB_ITER * ptabit)356 end_hashtab (HASHTAB_ITER * ptabit)
357 {
358 HASHTAB_ITER tabit = *ptabit;
359 ASSERT(tabit);
360 ASSERT(tabit->magic == hashtab_iter_magic);
361
362 memset(tabit, 0, sizeof(*tabit));
363 stdfree(tabit);
364 *ptabit = 0;
365 }
366