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