1 /****************************************************************************
2 Copyright (C) 1987-2015 by Jeffery P. Hansen
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
17 ****************************************************************************/
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include "hash.h"
22
23 /*****************************************************************************
24 *
25 * Object memory functions possibly used here.
26 *
27 *****************************************************************************/
28 void *ob_malloc(int,char*);
29 void *ob_calloc(int,int,char*);
30 void ob_free(void*);
31 char *ob_strdup(const char*);
32 void ob_touch(void*);
33
34 typedef void *malloc_f(int,char*);
35 typedef void *calloc_f(int,int,char*);
36 typedef void free_f(void*);
37 typedef char *strdup_f(const char*);
38 typedef void touch_f(void*);
39
40 typedef struct hash_vtable_str {
41 malloc_f *hv_malloc;
42 calloc_f *hv_calloc;
43 free_f *hv_free;
44 strdup_f *hv_strdup;
45 touch_f *hv_touch;
46 } HashVTable;
47
48 /*
49 * Standard function replacements for object memory handling.
50 */
h_malloc(int size,char * name)51 static void *h_malloc(int size,char *name) { return malloc(size); }
h_calloc(int n,int size,char * name)52 static void *h_calloc(int n,int size,char *name) { return calloc(n,size);}
nop_touch(void * p)53 static void nop_touch(void *p) {}
54
55 #define HT_MALLOC(H,size,name) (*((HashVTable*)H->vtable)->hv_malloc)(size,name)
56 #define HT_CALLOC(H,n,size,name) (*((HashVTable*)H->vtable)->hv_calloc)(n,size,name)
57 #define HT_FREE(H,p) (*((HashVTable*)H->vtable)->hv_free)(p)
58 #define HT_STRDUP(H,s) (*((HashVTable*)H->vtable)->hv_strdup)(s)
59 #define HT_TOUCH(H,p) (*((HashVTable*)H->vtable)->hv_touch)(p)
60
61 static HashVTable obj_mmgr = {
62 ob_malloc, ob_calloc, ob_free, ob_strdup, ob_touch
63 };
64
65 static HashVTable normal_mmgr = {
66 h_malloc, h_calloc, free, strdup, nop_touch
67 };
68
69 /*
70 Round N up to a power of 2.
71 */
roundup(unsigned N)72 static unsigned roundup(unsigned N)
73 {
74 unsigned P = N & (N ^ -N);
75
76 if (P) {
77 do {
78 N = P;
79 P = N & (N ^ -N);
80 } while (P);
81 N <<= 1;
82 }
83 return N;
84 }
85
inthash(uintptr_t key)86 static uintptr_t inthash(uintptr_t key)
87 {
88 key += 123456;
89 key += (key << 12);
90 key ^= (key >> 22);
91 key += (key << 4);
92 key ^= (key >> 9);
93 key += (key << 10);
94 key ^= (key >> 2);
95 key += (key << 7);
96 key ^= (key >> 12);
97
98 return key;
99 }
100
computestrhash(const char * s)101 uintptr_t computestrhash(const char *s)
102 {
103 uintptr_t N = 0;
104 uintptr_t H = 0;
105 int i;
106
107 for (i = 0;*s;s++, i++) {
108 N <<= 8;
109 N |= (unsigned char) *s;
110 if ((i & 3) == 3)
111 H = inthash(H + N);
112 }
113 H = inthash(H + N);
114 return H;
115 }
116
new_SHashElem(Hash * H,const char * key,uintptr_t hcode,void * val)117 static HashElem *new_SHashElem(Hash *H,const char *key,uintptr_t hcode, void *val)
118 {
119 HashElem *E = (HashElem*) HT_MALLOC(H,sizeof(HashElem),"HashElem");
120
121 E->key.s = HT_STRDUP(H,key);
122 E->hashcode = hcode;
123 E->value = val;
124 E->next = 0;
125
126 return E;
127 }
128
new_NHashElem(Hash * H,intptr_t key,unsigned hcode,void * val)129 static HashElem *new_NHashElem(Hash *H,intptr_t key,unsigned hcode,void *val)
130 {
131 HashElem *E = (HashElem*) HT_MALLOC(H,sizeof(HashElem),"HashElem");
132
133 E->key.d = key;
134 E->hashcode = hcode;
135 E->value = val;
136 E->next = 0;
137
138 return E;
139 }
140
SHashElem_uninit(HashElem * E,Hash * H)141 void SHashElem_uninit(HashElem *E,Hash *H)
142 {
143 HT_FREE(H,E->key.s);
144 }
145
new_Hash(int use_ob)146 Hash *new_Hash(int use_ob)
147 {
148 Hash *H;
149
150 if (use_ob) {
151 H = (Hash*) ob_malloc(sizeof(Hash),"Hash");
152 Hash_init(H,use_ob);
153 } else {
154 H = (Hash*) malloc(sizeof(Hash));
155 Hash_init(H,use_ob);
156 }
157
158 return H;
159 }
160
delete_Hash(Hash * H,HashElemDelFunc * hdel)161 void delete_Hash(Hash *H,HashElemDelFunc *hdel)
162 {
163 Hash_uninit(H,hdel);
164 HT_FREE(H,H);
165 }
166
Hash_init(Hash * H,int use_ob)167 void Hash_init(Hash *H,int use_ob)
168 {
169 if (use_ob) ob_touch(H);
170 if (use_ob)
171 H->vtable = &obj_mmgr;
172 else
173 H->vtable = &normal_mmgr;
174
175 H->size = roundup(INITIAL_HASHSIZE);
176 H->mask = H->size-1;
177 H->num = 0;
178 H->loop_ok = 0;
179 H->elems = (HashElem**) HT_CALLOC(H,H->size,sizeof(HashElem*),"HashElem[]");
180 if (use_ob) ob_touch(H->elems);
181 }
182
Hash_uninit(Hash * H,HashElemDelFunc * hdel)183 void Hash_uninit(Hash *H,HashElemDelFunc *hdel)
184 {
185 int i;
186
187 HT_TOUCH(H,H);
188 HT_TOUCH(H,H->elems);
189
190 for (i = 0;i < H->size;i++) {
191 HashElem *E,*N;
192 for (E = H->elems[i];E;E = N) {
193 N = E->next;
194 if (hdel)
195 (*hdel)(E,H);
196 HT_FREE(H,E);
197 }
198 }
199 HT_FREE(H,H->elems);
200 }
201
Hash_first(Hash * H)202 HashElem *Hash_first(Hash *H)
203 {
204 int i;
205
206 H->loop_ok = 1; /* This debugging flag does not need an ob_touch */
207 for (i = 0;i < H->size;i++)
208 if (H->elems[i])
209 return H->elems[i];
210 return 0;
211 }
212
Hash_next(Hash * H,HashElem * E)213 HashElem *Hash_next(Hash *H,HashElem *E)
214 {
215 int A;
216
217 if (!H->loop_ok) {
218 printf("echo Illegal sequential hash table access.\n");
219 fflush(stdout);
220 }
221
222 if (E->next) return E->next;
223
224 for (A = (E->hashcode & H->mask) + 1;A < H->size;A++)
225 if (H->elems[A])
226 return H->elems[A];
227
228 return 0;
229 }
230
231 /*
232 Double the size of a hash table
233 */
Hash_grow(Hash * H)234 void Hash_grow(Hash *H)
235 {
236 Hash_resize(H,(H->size << 1));
237 }
238
239 /*
240 * Request a specific size for a hash table (rounded up to power of two)
241 */
Hash_resize(Hash * H,int reqSize)242 void Hash_resize(Hash *H,int reqSize)
243 {
244 int S = H->size;
245 HashElem **nea;
246 int i;
247
248 reqSize = roundup(reqSize);
249
250 HT_TOUCH(H,H);
251 HT_TOUCH(H,H->elems);
252
253 H->size = reqSize;
254 H->mask = H->size - 1;
255 nea = (HashElem**) HT_CALLOC(H,H->size,sizeof(HashElem*),"HashElem[]");
256
257 for (i = 0;i < S;i++) {
258 HashElem *E;
259 while ((E = H->elems[i])) {
260 unsigned A = E->hashcode & H->mask;
261 H->elems[i] = E->next;
262 HT_TOUCH(H,E);
263 E->next = nea[A];
264 nea[A] = E;
265 }
266 }
267 HT_FREE(H,H->elems);
268 H->elems = nea;
269 }
270
Hash_removeElem(Hash * H,int A,HashElem * E)271 void Hash_removeElem(Hash *H,int A,HashElem *E)
272 {
273 HashElem *P;
274
275 HT_TOUCH(H,H);
276
277 H->num--;
278
279 H->loop_ok = 0;
280
281 if (H->elems[A] == E) {
282 HT_TOUCH(H,H->elems);
283 H->elems[A] = E->next;
284 return;
285 }
286
287 for (P = H->elems[A];P->next != E;P = P->next);
288
289 HT_TOUCH(H,P);
290 P->next = E->next;
291 }
292
SHash_find(Hash * H,const char * key)293 void *SHash_find(Hash *H,const char *key)
294 {
295 uintptr_t HC = computestrhash(key);
296 uintptr_t A = HC & H->mask;
297 HashElem *E;
298
299 for (E = H->elems[A];E;E = E->next)
300 if (E->hashcode == HC && strcmp(E->key.s,key) == 0)
301 return E->value;
302 return 0;
303 }
304
SHash_insert(Hash * H,const char * key,void * val)305 int SHash_insert(Hash *H,const char *key,void* val)
306 {
307 uintptr_t HC = computestrhash(key);
308 uintptr_t A = HC & H->mask;
309 HashElem *E;
310
311 HT_TOUCH(H,H);
312
313 H->loop_ok = 0;
314 for (E = H->elems[A];E;E = E->next)
315 if (E->hashcode == HC && strcmp(E->key.s,key) == 0)
316 return -1;
317
318 HT_TOUCH(H,H->elems);
319 E = new_SHashElem(H,key,HC,val);
320 E->next = H->elems[A];
321 H->elems[A] = E;
322 H->num++;
323 if (H->size*HASH_MAXLOAD < H->num)
324 Hash_grow(H);
325
326 return 0;
327 }
328
SHash_replace(Hash * H,const char * key,void * val)329 int SHash_replace(Hash *H,const char *key,void* val)
330 {
331 uintptr_t HC = computestrhash(key);
332 uintptr_t A = HC & H->mask;
333 HashElem *E;
334
335 HT_TOUCH(H,H);
336 HT_TOUCH(H,H->elems);
337
338 H->loop_ok = 0;
339 for (E = H->elems[A];E;E = E->next)
340 if (E->hashcode == HC && strcmp(E->key.s,key) == 0) {
341 HT_TOUCH(H,E);
342 E->value = val;
343 return 1;
344 }
345
346 E = new_SHashElem(H,key,HC,val);
347 E->next = H->elems[A];
348 H->elems[A] = E;
349 H->num++;
350 if (H->size*HASH_MAXLOAD < H->num)
351 Hash_grow(H);
352
353 return 0;
354 }
355
SHash_remove(Hash * H,const char * key)356 int SHash_remove(Hash *H,const char *key)
357 {
358 uintptr_t HC = computestrhash(key);
359 uintptr_t A = HC & H->mask;
360 HashElem *E;
361
362 HT_TOUCH(H,H);
363
364 H->loop_ok = 0;
365 for (E = H->elems[A];E;E = E->next)
366 if (E->hashcode == HC && strcmp(E->key.s,key) == 0) {
367 Hash_removeElem(H,A,E);
368 HT_FREE(H,E->key.s);
369 HT_FREE(H,E);
370 return 0;
371 }
372
373 return -1;
374 }
375
Hash_flush(Hash * H,HashElemDelFunc * hdel)376 void Hash_flush(Hash *H,HashElemDelFunc *hdel)
377 {
378 int i;
379
380 HT_TOUCH(H,H);
381 HT_TOUCH(H,H->elems);
382
383 H->loop_ok = 0;
384
385 for (i = 0;i < H->size;i++) {
386 HashElem *E = H->elems[i];
387 HashElem *N;
388 for (;E;E = N) {
389 N = E->next;
390 if (hdel) (*hdel)(E,H);
391 HT_FREE(H,E);
392 }
393 H->elems[i] = 0;
394 }
395 H->num = 0;
396 }
397
NHash_find(Hash * H,intptr_t key)398 void *NHash_find(Hash *H,intptr_t key)
399 {
400 uintptr_t HC = inthash(key);
401 uintptr_t A = HC & H->mask;
402 HashElem *E;
403
404 for (E = H->elems[A];E;E = E->next)
405 if (E->key.d == key)
406 return E->value;
407 return 0;
408 }
409
NHash_insert(Hash * H,intptr_t key,void * val)410 int NHash_insert(Hash *H,intptr_t key,void* val)
411 {
412 uintptr_t HC = inthash(key);
413 uintptr_t A = HC & H->mask;
414 HashElem *E;
415
416 HT_TOUCH(H,H);
417 HT_TOUCH(H,H->elems);
418
419 H->loop_ok = 0;
420
421 for (E = H->elems[A];E;E = E->next)
422 if (E->key.d == key)
423 return -1;
424
425 E = new_NHashElem(H,key,HC,val);
426 E->next = H->elems[A];
427 H->elems[A] = E;
428 H->num++;
429 if (H->size*HASH_MAXLOAD < H->num)
430 Hash_grow(H);
431
432 return 0;
433 }
434
NHash_replace(Hash * H,intptr_t key,void * val)435 int NHash_replace(Hash *H,intptr_t key,void* val)
436 {
437 uintptr_t HC = inthash(key);
438 uintptr_t A = HC & H->mask;
439 HashElem *E;
440
441 HT_TOUCH(H,H);
442 HT_TOUCH(H,H->elems);
443
444 H->loop_ok = 0;
445
446 for (E = H->elems[A];E;E = E->next)
447 if (E->key.d == key) {
448 E->value = val;
449 return 0;
450 }
451
452 E = new_NHashElem(H,key,HC,val);
453 E->next = H->elems[A];
454 H->elems[A] = E;
455 H->num++;
456 if (H->size*HASH_MAXLOAD < H->num)
457 Hash_grow(H);
458
459 return 0;
460 }
461
NHash_remove(Hash * H,intptr_t key)462 int NHash_remove(Hash * H,intptr_t key)
463 {
464 uintptr_t HC = inthash(key);
465 uintptr_t A = HC & H->mask;
466 HashElem *E;
467
468 HT_TOUCH(H,H);
469 H->loop_ok = 0;
470
471 for (E = H->elems[A];E;E = E->next)
472 if (E->key.d == key) {
473 Hash_removeElem(H,A,E);
474 HT_FREE(H,E);
475 return 0;
476 }
477
478 return -1;
479 }
480