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(void)133 stat_col(void)
134 {
135 FILE *f = fopen("/tmp/col", "w");
136 if (f == 0) return ;
137
138 (void) fprintf(f, "collision: %d\n", collision);
139 (void) fclose(f);
140 }
141 #endif
142
143 st_table*
st_init_table_with_size(type,size)144 st_init_table_with_size(type, size)
145 struct st_hash_type *type;
146 int size;
147 {
148 st_table *tbl;
149
150 #ifdef HASH_LOG
151 if (init_st == 0) {
152 init_st = 1;
153 atexit(stat_col);
154 }
155 #endif
156
157 size = new_size(size); /* round up to prime number */
158
159 tbl = alloc(st_table);
160 if (tbl == 0) return 0;
161
162 tbl->type = type;
163 tbl->num_entries = 0;
164 tbl->num_bins = size;
165 tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
166 if (tbl->bins == 0) {
167 free(tbl);
168 return 0;
169 }
170
171 return tbl;
172 }
173
174 st_table*
st_init_table(type)175 st_init_table(type)
176 struct st_hash_type *type;
177 {
178 return st_init_table_with_size(type, 0);
179 }
180
181 st_table*
st_init_numtable(void)182 st_init_numtable(void)
183 {
184 return st_init_table(&type_numhash);
185 }
186
187 st_table*
st_init_numtable_with_size(size)188 st_init_numtable_with_size(size)
189 int size;
190 {
191 return st_init_table_with_size(&type_numhash, size);
192 }
193
194 st_table*
st_init_strtable(void)195 st_init_strtable(void)
196 {
197 return st_init_table(&type_strhash);
198 }
199
200 st_table*
st_init_strtable_with_size(size)201 st_init_strtable_with_size(size)
202 int size;
203 {
204 return st_init_table_with_size(&type_strhash, size);
205 }
206
207 void
st_free_table(table)208 st_free_table(table)
209 st_table *table;
210 {
211 register st_table_entry *ptr, *next;
212 int i;
213
214 for(i = 0; i < table->num_bins; i++) {
215 ptr = table->bins[i];
216 while (ptr != 0) {
217 next = ptr->next;
218 free(ptr);
219 ptr = next;
220 }
221 }
222 free(table->bins);
223 free(table);
224 }
225
226 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
227 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
228
229 #ifdef HASH_LOG
230 #define COLLISION collision++
231 #else
232 #define COLLISION
233 #endif
234
235 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
236 bin_pos = hash_val%(table)->num_bins;\
237 ptr = (table)->bins[bin_pos];\
238 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
239 COLLISION;\
240 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
241 ptr = ptr->next;\
242 }\
243 ptr = ptr->next;\
244 }\
245 } while (0)
246
247 int
st_lookup(table,key,value)248 st_lookup(table, key, value)
249 st_table *table;
250 register st_data_t key;
251 st_data_t *value;
252 {
253 unsigned int hash_val, bin_pos;
254 register st_table_entry *ptr;
255
256 hash_val = do_hash(key, table);
257 FIND_ENTRY(table, ptr, hash_val, bin_pos);
258
259 if (ptr == 0) {
260 return 0;
261 }
262 else {
263 if (value != 0) *value = ptr->record;
264 return 1;
265 }
266 }
267
268 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
269 do {\
270 st_table_entry *entry;\
271 if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
272 rehash(table);\
273 bin_pos = hash_val % table->num_bins;\
274 }\
275 \
276 entry = alloc(st_table_entry);\
277 \
278 entry->hash = hash_val;\
279 entry->key = key;\
280 entry->record = value;\
281 entry->next = table->bins[bin_pos];\
282 table->bins[bin_pos] = entry;\
283 table->num_entries++;\
284 } while (0)
285
286 int
st_insert(table,key,value)287 st_insert(table, key, value)
288 register st_table *table;
289 register st_data_t key;
290 st_data_t value;
291 {
292 unsigned int hash_val, bin_pos;
293 register st_table_entry *ptr;
294
295 hash_val = do_hash(key, table);
296 FIND_ENTRY(table, ptr, hash_val, bin_pos);
297
298 if (ptr == 0) {
299 ADD_DIRECT(table, key, value, hash_val, bin_pos);
300 return 0;
301 }
302 else {
303 ptr->record = value;
304 return 1;
305 }
306 }
307
308 void
st_add_direct(table,key,value)309 st_add_direct(table, key, value)
310 st_table *table;
311 st_data_t key;
312 st_data_t value;
313 {
314 unsigned int hash_val, bin_pos;
315
316 hash_val = do_hash(key, table);
317 bin_pos = hash_val % table->num_bins;
318 ADD_DIRECT(table, key, value, hash_val, bin_pos);
319 }
320
321 static void
rehash(table)322 rehash(table)
323 register st_table *table;
324 {
325 register st_table_entry *ptr, *next, **new_bins;
326 int i, old_num_bins = table->num_bins, new_num_bins;
327 unsigned int hash_val;
328
329 new_num_bins = new_size(old_num_bins+1);
330 new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
331 if (new_bins == 0) {
332 return ;
333 }
334
335 for(i = 0; i < old_num_bins; i++) {
336 ptr = table->bins[i];
337 while (ptr != 0) {
338 next = ptr->next;
339 hash_val = ptr->hash % new_num_bins;
340 ptr->next = new_bins[hash_val];
341 new_bins[hash_val] = ptr;
342 ptr = next;
343 }
344 }
345 free(table->bins);
346 table->num_bins = new_num_bins;
347 table->bins = new_bins;
348 }
349
350 st_table*
st_copy(old_table)351 st_copy(old_table)
352 st_table *old_table;
353 {
354 st_table *new_table;
355 st_table_entry *ptr, *entry;
356 int i, num_bins = old_table->num_bins;
357
358 new_table = alloc(st_table);
359 if (new_table == 0) {
360 return 0;
361 }
362
363 *new_table = *old_table;
364 new_table->bins = (st_table_entry**)
365 Calloc((unsigned)num_bins, sizeof(st_table_entry*));
366
367 if (new_table->bins == 0) {
368 free(new_table);
369 return 0;
370 }
371
372 for(i = 0; i < num_bins; i++) {
373 new_table->bins[i] = 0;
374 ptr = old_table->bins[i];
375 while (ptr != 0) {
376 entry = alloc(st_table_entry);
377 if (entry == 0) {
378 free(new_table->bins);
379 free(new_table);
380 return 0;
381 }
382 *entry = *ptr;
383 entry->next = new_table->bins[i];
384 new_table->bins[i] = entry;
385 ptr = ptr->next;
386 }
387 }
388 return new_table;
389 }
390
391 int
st_delete(table,key,value)392 st_delete(table, key, value)
393 register st_table *table;
394 register st_data_t *key;
395 st_data_t *value;
396 {
397 unsigned int hash_val;
398 st_table_entry *tmp;
399 register st_table_entry *ptr;
400
401 hash_val = do_hash_bin(*key, table);
402 ptr = table->bins[hash_val];
403
404 if (ptr == 0) {
405 if (value != 0) *value = 0;
406 return 0;
407 }
408
409 if (EQUAL(table, *key, ptr->key)) {
410 table->bins[hash_val] = ptr->next;
411 table->num_entries--;
412 if (value != 0) *value = ptr->record;
413 *key = ptr->key;
414 free(ptr);
415 return 1;
416 }
417
418 for(; ptr->next != 0; ptr = ptr->next) {
419 if (EQUAL(table, ptr->next->key, *key)) {
420 tmp = ptr->next;
421 ptr->next = ptr->next->next;
422 table->num_entries--;
423 if (value != 0) *value = tmp->record;
424 *key = tmp->key;
425 free(tmp);
426 return 1;
427 }
428 }
429
430 return 0;
431 }
432
433 int
st_delete_safe(table,key,value,never)434 st_delete_safe(table, key, value, never)
435 register st_table *table;
436 register st_data_t *key;
437 st_data_t *value;
438 st_data_t never;
439 {
440 unsigned int hash_val;
441 register st_table_entry *ptr;
442
443 hash_val = do_hash_bin(*key, table);
444 ptr = table->bins[hash_val];
445
446 if (ptr == 0) {
447 if (value != 0) *value = 0;
448 return 0;
449 }
450
451 for(; ptr != 0; ptr = ptr->next) {
452 if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
453 table->num_entries--;
454 *key = ptr->key;
455 if (value != 0) *value = ptr->record;
456 ptr->key = ptr->record = never;
457 return 1;
458 }
459 }
460
461 return 0;
462 }
463
464 static int
465 #if defined(__GNUC__)
delete_never(st_data_t key,st_data_t value,st_data_t never)466 delete_never(st_data_t key __attribute__ ((unused)), st_data_t value,
467 st_data_t never)
468 #else
469 delete_never(key, value, never)
470 st_data_t key, value, never;
471 #endif
472 {
473 if (value == never) return ST_DELETE;
474 return ST_CONTINUE;
475 }
476
477 void
st_cleanup_safe(table,never)478 st_cleanup_safe(table, never)
479 st_table *table;
480 st_data_t never;
481 {
482 int num_entries = table->num_entries;
483
484 st_foreach(table, delete_never, never);
485 table->num_entries = num_entries;
486 }
487
488 int
st_foreach(table,func,arg)489 st_foreach(table, func, arg)
490 st_table *table;
491 int (*func)();
492 st_data_t arg;
493 {
494 st_table_entry *ptr, *last, *tmp;
495 enum st_retval retval;
496 int i;
497
498 for(i = 0; i < table->num_bins; i++) {
499 last = 0;
500 for(ptr = table->bins[i]; ptr != 0;) {
501 retval = (*func)(ptr->key, ptr->record, arg);
502 switch (retval) {
503 case ST_CHECK: /* check if hash is modified during iteration */
504 tmp = 0;
505 if (i < table->num_bins) {
506 for (tmp = table->bins[i]; tmp; tmp=tmp->next) {
507 if (tmp == ptr) break;
508 }
509 }
510 if (!tmp) {
511 /* call func with error notice */
512 return 1;
513 }
514 /* fall through */
515 case ST_CONTINUE:
516 last = ptr;
517 ptr = ptr->next;
518 break;
519 case ST_STOP:
520 return 0;
521 case ST_DELETE:
522 tmp = ptr;
523 if (last == 0) {
524 table->bins[i] = ptr->next;
525 }
526 else {
527 last->next = ptr->next;
528 }
529 ptr = ptr->next;
530 free(tmp);
531 table->num_entries--;
532 }
533 }
534 }
535 return 0;
536 }
537
538 static int
strhash(string)539 strhash(string)
540 register const char *string;
541 {
542 register int c;
543
544 #ifdef HASH_ELFHASH
545 register unsigned int h = 0, g;
546
547 while ((c = *string++) != '\0') {
548 h = ( h << 4 ) + c;
549 if ( g = h & 0xF0000000 )
550 h ^= g >> 24;
551 h &= ~g;
552 }
553 return h;
554 #elif HASH_PERL
555 register int val = 0;
556
557 while ((c = *string++) != '\0') {
558 val += c;
559 val += (val << 10);
560 val ^= (val >> 6);
561 }
562 val += (val << 3);
563 val ^= (val >> 11);
564
565 return val + (val << 15);
566 #else
567 register int val = 0;
568
569 while ((c = *string++) != '\0') {
570 val = val*997 + c;
571 }
572
573 return val + (val>>5);
574 #endif
575 }
576
577 static int
numcmp(x,y)578 numcmp(x, y)
579 long x, y;
580 {
581 return x != y;
582 }
583
584 static int
numhash(n)585 numhash(n)
586 long n;
587 {
588 return n;
589 }
590
