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