1 /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */
2
3 /* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 #ifdef _WIN32
10 #include <malloc.h>
11 #endif
12
13 #include "regint.h"
14 #include "st.h"
15
16 typedef struct st_table_entry st_table_entry;
17
18 struct st_table_entry {
19 unsigned int hash;
20 st_data_t key;
21 st_data_t record;
22 st_table_entry *next;
23 };
24
25 #define ST_DEFAULT_MAX_DENSITY 5
26 #define ST_DEFAULT_INIT_TABLE_SIZE 11
27
28 /*
29 * DEFAULT_MAX_DENSITY is the default for the largest we allow the
30 * average number of items per bin before increasing the number of
31 * bins
32 *
33 * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
34 * allocated initially
35 *
36 */
37
38 static int numcmp(long, long);
39 static int numhash(long);
40 static struct st_hash_type type_numhash = {
41 numcmp,
42 numhash,
43 };
44
45 /* extern int strcmp(const char *, const char *); */
46 static int strhash(const char *);
47 static struct st_hash_type type_strhash = {
48 strcmp,
49 strhash,
50 };
51
52 static void rehash(st_table *);
53
54 #define alloc(type) (type*)xmalloc((unsigned)sizeof(type))
55 #define Calloc(n,s) (char*)xcalloc((n),(s))
56
57 #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
58
59 #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))
60 #define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins)
61
62 /*
63 * MINSIZE is the minimum size of a dictionary.
64 */
65
66 #define MINSIZE 8
67
68 /*
69 Table of prime numbers 2^n+a, 2<=n<=30.
70 */
71 static const long primes[] = {
72 8 + 3,
73 16 + 3,
74 32 + 5,
75 64 + 3,
76 128 + 3,
77 256 + 27,
78 512 + 9,
79 1024 + 9,
80 2048 + 5,
81 4096 + 3,
82 8192 + 27,
83 16384 + 43,
84 32768 + 3,
85 65536 + 45,
86 131072 + 29,
87 262144 + 3,
88 524288 + 21,
89 1048576 + 7,
90 2097152 + 17,
91 4194304 + 15,
92 8388608 + 9,
93 16777216 + 43,
94 33554432 + 35,
95 67108864 + 15,
96 134217728 + 29,
97 268435456 + 3,
98 536870912 + 11,
99 1073741824 + 85,
100 0
101 };
102
103 static int
new_size(size)104 new_size(size)
105 int size;
106 {
107 int i;
108
109 #if 0
110 for (i=3; i<31; i++) {
111 if ((1<<i) > size) return 1<<i;
112 }
113 return -1;
114 #else
115 int newsize;
116
117 for (i = 0, newsize = MINSIZE;
118 i < (int )(sizeof(primes)/sizeof(primes[0]));
119 i++, newsize <<= 1)
120 {
121 if (newsize > size) return primes[i];
122 }
123 /* Ran out of polynomials */
124 return -1; /* should raise exception */
125 #endif
126 }
127
128 #ifdef HASH_LOG
129 static int collision = 0;
130 static int init_st = 0;
131
132 static void
stat_col()133 stat_col()
134 {
135 FILE *f = fopen("/tmp/col", "w");
136 fprintf(f, "collision: %d\n", collision);
137 fclose(f);
138 }
139 #endif
140
141 st_table*
st_init_table_with_size(type,size)142 st_init_table_with_size(type, size)
143 struct st_hash_type *type;
144 int size;
145 {
146 st_table *tbl;
147
148 #ifdef HASH_LOG
149 if (init_st == 0) {
150 init_st = 1;
151 atexit(stat_col);
152 }
153 #endif
154
155 size = new_size(size); /* round up to prime number */
156
157 tbl = alloc(st_table);
158 tbl->type = type;
159 tbl->num_entries = 0;
160 tbl->num_bins = size;
161 tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
162
163 return tbl;
164 }
165
166 st_table*
st_init_table(type)167 st_init_table(type)
168 struct st_hash_type *type;
169 {
170 return st_init_table_with_size(type, 0);
171 }
172
173 st_table*
st_init_numtable(void)174 st_init_numtable(void)
175 {
176 return st_init_table(&type_numhash);
177 }
178
179 st_table*
st_init_numtable_with_size(size)180 st_init_numtable_with_size(size)
181 int size;
182 {
183 return st_init_table_with_size(&type_numhash, size);
184 }
185
186 st_table*
st_init_strtable(void)187 st_init_strtable(void)
188 {
189 return st_init_table(&type_strhash);
190 }
191
192 st_table*
st_init_strtable_with_size(size)193 st_init_strtable_with_size(size)
194 int size;
195 {
196 return st_init_table_with_size(&type_strhash, size);
197 }
198
199 void
st_free_table(table)200 st_free_table(table)
201 st_table *table;
202 {
203 register st_table_entry *ptr, *next;
204 int i;
205
206 for(i = 0; i < table->num_bins; i++) {
207 ptr = table->bins[i];
208 while (ptr != 0) {
209 next = ptr->next;
210 free(ptr);
211 ptr = next;
212 }
213 }
214 free(table->bins);
215 free(table);
216 }
217
218 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
219 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
220
221 #ifdef HASH_LOG
222 #define COLLISION collision++
223 #else
224 #define COLLISION
225 #endif
226
227 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
228 bin_pos = hash_val%(table)->num_bins;\
229 ptr = (table)->bins[bin_pos];\
230 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
231 COLLISION;\
232 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
233 ptr = ptr->next;\
234 }\
235 ptr = ptr->next;\
236 }\
237 } while (0)
238
239 int
st_lookup(table,key,value)240 st_lookup(table, key, value)
241 st_table *table;
242 register st_data_t key;
243 st_data_t *value;
244 {
245 unsigned int hash_val, bin_pos;
246 register st_table_entry *ptr;
247
248 hash_val = do_hash(key, table);
249 FIND_ENTRY(table, ptr, hash_val, bin_pos);
250
251 if (ptr == 0) {
252 return 0;
253 }
254 else {
255 if (value != 0) *value = ptr->record;
256 return 1;
257 }
258 }
259
260 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
261 do {\
262 st_table_entry *entry;\
263 if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
264 rehash(table);\
265 bin_pos = hash_val % table->num_bins;\
266 }\
267 \
268 entry = alloc(st_table_entry);\
269 \
270 entry->hash = hash_val;\
271 entry->key = key;\
272 entry->record = value;\
273 entry->next = table->bins[bin_pos];\
274 table->bins[bin_pos] = entry;\
275 table->num_entries++;\
276 } while (0)
277
278 int
st_insert(table,key,value)279 st_insert(table, key, value)
280 register st_table *table;
281 register st_data_t key;
282 st_data_t value;
283 {
284 unsigned int hash_val, bin_pos;
285 register st_table_entry *ptr;
286
287 hash_val = do_hash(key, table);
288 FIND_ENTRY(table, ptr, hash_val, bin_pos);
289
290 if (ptr == 0) {
291 ADD_DIRECT(table, key, value, hash_val, bin_pos);
292 return 0;
293 }
294 else {
295 ptr->record = value;
296 return 1;
297 }
298 }
299
300 void
st_add_direct(table,key,value)301 st_add_direct(table, key, value)
302 st_table *table;
303 st_data_t key;
304 st_data_t value;
305 {
306 unsigned int hash_val, bin_pos;
307
308 hash_val = do_hash(key, table);
309 bin_pos = hash_val % table->num_bins;
310 ADD_DIRECT(table, key, value, hash_val, bin_pos);
311 }
312
313 static void
rehash(table)314 rehash(table)
315 register st_table *table;
316 {
317 register st_table_entry *ptr, *next, **new_bins;
318 int i, old_num_bins = table->num_bins, new_num_bins;
319 unsigned int hash_val;
320
321 new_num_bins = new_size(old_num_bins+1);
322 new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
323
324 for(i = 0; i < old_num_bins; i++) {
325 ptr = table->bins[i];
326 while (ptr != 0) {
327 next = ptr->next;
328 hash_val = ptr->hash % new_num_bins;
329 ptr->next = new_bins[hash_val];
330 new_bins[hash_val] = ptr;
331 ptr = next;
332 }
333 }
334 free(table->bins);
335 table->num_bins = new_num_bins;
336 table->bins = new_bins;
337 }
338
339 st_table*
st_copy(old_table)340 st_copy(old_table)
341 st_table *old_table;
342 {
343 st_table *new_table;
344 st_table_entry *ptr, *entry;
345 int i, num_bins = old_table->num_bins;
346
347 new_table = alloc(st_table);
348 if (new_table == 0) {
349 return 0;
350 }
351
352 *new_table = *old_table;
353 new_table->bins = (st_table_entry**)
354 Calloc((unsigned)num_bins, sizeof(st_table_entry*));
355
356 if (new_table->bins == 0) {
357 free(new_table);
358 return 0;
359 }
360
361 for(i = 0; i < num_bins; i++) {
362 new_table->bins[i] = 0;
363 ptr = old_table->bins[i];
364 while (ptr != 0) {
365 entry = alloc(st_table_entry);
366 if (entry == 0) {
367 free(new_table->bins);
368 free(new_table);
369 return 0;
370 }
371 *entry = *ptr;
372 entry->next = new_table->bins[i];
373 new_table->bins[i] = entry;
374 ptr = ptr->next;
375 }
376 }
377 return new_table;
378 }
379
380 int
st_delete(table,key,value)381 st_delete(table, key, value)
382 register st_table *table;
383 register st_data_t *key;
384 st_data_t *value;
385 {
386 unsigned int hash_val;
387 st_table_entry *tmp;
388 register st_table_entry *ptr;
389
390 hash_val = do_hash_bin(*key, table);
391 ptr = table->bins[hash_val];
392
393 if (ptr == 0) {
394 if (value != 0) *value = 0;
395 return 0;
396 }
397
398 if (EQUAL(table, *key, ptr->key)) {
399 table->bins[hash_val] = ptr->next;
400 table->num_entries--;
401 if (value != 0) *value = ptr->record;
402 *key = ptr->key;
403 free(ptr);
404 return 1;
405 }
406
407 for(; ptr->next != 0; ptr = ptr->next) {
408 if (EQUAL(table, ptr->next->key, *key)) {
409 tmp = ptr->next;
410 ptr->next = ptr->next->next;
411 table->num_entries--;
412 if (value != 0) *value = tmp->record;
413 *key = tmp->key;
414 free(tmp);
415 return 1;
416 }
417 }
418
419 return 0;
420 }
421
422 int
st_delete_safe(table,key,value,never)423 st_delete_safe(table, key, value, never)
424 register st_table *table;
425 register st_data_t *key;
426 st_data_t *value;
427 st_data_t never;
428 {
429 unsigned int hash_val;
430 register st_table_entry *ptr;
431
432 hash_val = do_hash_bin(*key, table);
433 ptr = table->bins[hash_val];
434
435 if (ptr == 0) {
436 if (value != 0) *value = 0;
437 return 0;
438 }
439
440 for(; ptr != 0; ptr = ptr->next) {
441 if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
442 table->num_entries--;
443 *key = ptr->key;
444 if (value != 0) *value = ptr->record;
445 ptr->key = ptr->record = never;
446 return 1;
447 }
448 }
449
450 return 0;
451 }
452
453 static int
454 #if defined(__GNUC__)
delete_never(st_data_t key,st_data_t value,st_data_t never)455 delete_never(st_data_t key __attribute__ ((unused)), st_data_t value,
456 st_data_t never)
457 #else
458 delete_never(key, value, never)
459 st_data_t key, value, never;
460 #endif
461 {
462 if (value == never) return ST_DELETE;
463 return ST_CONTINUE;
464 }
465
466 void
st_cleanup_safe(table,never)467 st_cleanup_safe(table, never)
468 st_table *table;
469 st_data_t never;
470 {
471 int num_entries = table->num_entries;
472
473 st_foreach(table, delete_never, never);
474 table->num_entries = num_entries;
475 }
476
477 int
st_foreach(table,func,arg)478 st_foreach(table, func, arg)
479 st_table *table;
480 int (*func)();
481 st_data_t arg;
482 {
483 st_table_entry *ptr, *last, *tmp;
484 enum st_retval retval;
485 int i;
486
487 for(i = 0; i < table->num_bins; i++) {
488 last = 0;
489 for(ptr = table->bins[i]; ptr != 0;) {
490 retval = (*func)(ptr->key, ptr->record, arg);
491 switch (retval) {
492 case ST_CHECK: /* check if hash is modified during iteration */
493 tmp = 0;
494 if (i < table->num_bins) {
495 for (tmp = table->bins[i]; tmp; tmp=tmp->next) {
496 if (tmp == ptr) break;
497 }
498 }
499 if (!tmp) {
500 /* call func with error notice */
501 return 1;
502 }
503 /* fall through */
504 case ST_CONTINUE:
505 last = ptr;
506 ptr = ptr->next;
507 break;
508 case ST_STOP:
509 return 0;
510 case ST_DELETE:
511 tmp = ptr;
512 if (last == 0) {
513 table->bins[i] = ptr->next;
514 }
515 else {
516 last->next = ptr->next;
517 }
518 ptr = ptr->next;
519 free(tmp);
520 table->num_entries--;
521 }
522 }
523 }
524 return 0;
525 }
526
527 static int
strhash(string)528 strhash(string)
529 register const char *string;
530 {
531 register int c;
532
533 #ifdef HASH_ELFHASH
534 register unsigned int h = 0, g;
535
536 while ((c = *string++) != '\0') {
537 h = ( h << 4 ) + c;
538 if ( g = h & 0xF0000000 )
539 h ^= g >> 24;
540 h &= ~g;
541 }
542 return h;
543 #elif HASH_PERL
544 register int val = 0;
545
546 while ((c = *string++) != '\0') {
547 val += c;
548 val += (val << 10);
549 val ^= (val >> 6);
550 }
551 val += (val << 3);
552 val ^= (val >> 11);
553
554 return val + (val << 15);
555 #else
556 register int val = 0;
557
558 while ((c = *string++) != '\0') {
559 val = val*997 + c;
560 }
561
562 return val + (val>>5);
563 #endif
564 }
565
566 static int
numcmp(x,y)567 numcmp(x, y)
568 long x, y;
569 {
570 return x != y;
571 }
572
573 static int
numhash(n)574 numhash(n)
575 long n;
576 {
577 return n;
578 }
579
