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 "config.h"
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
9
10 #ifdef _WIN32
11 #include <malloc.h>
12 #endif
13
14 #ifdef NOT_RUBY
15 #include "regint.h"
16 #else
17 #ifdef RUBY_PLATFORM
18 #define xmalloc ruby_xmalloc
19 #define xcalloc ruby_xcalloc
20 #define xrealloc ruby_xrealloc
21 #define xfree ruby_xfree
22
23 void *xmalloc(long);
24 void *xcalloc(long, long);
25 void *xrealloc(void *, long);
26 void xfree(void *);
27 #endif
28 #endif
29
30 #include "st.h"
31
32 typedef struct st_table_entry st_table_entry;
33
34 struct st_table_entry {
35 unsigned int hash;
36 st_data_t key;
37 st_data_t record;
38 st_table_entry *next;
39 };
40
41 #define ST_DEFAULT_MAX_DENSITY 5
42 #define ST_DEFAULT_INIT_TABLE_SIZE 11
43
44 /*
45 * DEFAULT_MAX_DENSITY is the default for the largest we allow the
46 * average number of items per bin before increasing the number of
47 * bins
48 *
49 * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
50 * allocated initially
51 *
52 */
53
54 static int numcmp(long, long);
55 static int numhash(long);
56 static struct st_hash_type type_numhash = {
57 numcmp,
58 numhash,
59 };
60
61 /* extern int strcmp(const char *, const char *); */
62 static int strhash(const char *);
63 static struct st_hash_type type_strhash = {
64 strcmp,
65 strhash,
66 };
67
68 static void rehash(st_table *);
69
70 #define alloc(type) (type*)xmalloc((unsigned)sizeof(type))
71 #define Calloc(n,s) (char*)xcalloc((n),(s))
72
73 #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
74
75 #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))
76 #define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins)
77
78 /*
79 * MINSIZE is the minimum size of a dictionary.
80 */
81
82 #define MINSIZE 8
83
84 /*
85 Table of prime numbers 2^n+a, 2<=n<=30.
86 */
87 static const long primes[] = {
88 8 + 3,
89 16 + 3,
90 32 + 5,
91 64 + 3,
92 128 + 3,
93 256 + 27,
94 512 + 9,
95 1024 + 9,
96 2048 + 5,
97 4096 + 3,
98 8192 + 27,
99 16384 + 43,
100 32768 + 3,
101 65536 + 45,
102 131072 + 29,
103 262144 + 3,
104 524288 + 21,
105 1048576 + 7,
106 2097152 + 17,
107 4194304 + 15,
108 8388608 + 9,
109 16777216 + 43,
110 33554432 + 35,
111 67108864 + 15,
112 134217728 + 29,
113 268435456 + 3,
114 536870912 + 11,
115 1073741824 + 85,
116 0
117 };
118
119 static int
new_size(size)120 new_size(size)
121 int size;
122 {
123 int i;
124
125 #if 0
126 for (i=3; i<31; i++) {
127 if ((1<<i) > size) return 1<<i;
128 }
129 return -1;
130 #else
131 int newsize;
132
133 for (i = 0, newsize = MINSIZE;
134 i < (int )(sizeof(primes)/sizeof(primes[0]));
135 i++, newsize <<= 1)
136 {
137 if (newsize > size) return primes[i];
138 }
139 /* Ran out of polynomials */
140 return -1; /* should raise exception */
141 #endif
142 }
143
144 #ifdef HASH_LOG
145 static int collision = 0;
146 static int init_st = 0;
147
148 static void
stat_col()149 stat_col()
150 {
151 FILE *f = fopen("/tmp/col", "w");
152 fprintf(f, "collision: %d\n", collision);
153 fclose(f);
154 }
155 #endif
156
157 st_table*
st_init_table_with_size(type,size)158 st_init_table_with_size(type, size)
159 struct st_hash_type *type;
160 int size;
161 {
162 st_table *tbl;
163
164 #ifdef HASH_LOG
165 if (init_st == 0) {
166 init_st = 1;
167 atexit(stat_col);
168 }
169 #endif
170
171 size = new_size(size); /* round up to prime number */
172
173 tbl = alloc(st_table);
174 tbl->type = type;
175 tbl->num_entries = 0;
176 tbl->num_bins = size;
177 tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
178
179 return tbl;
180 }
181
182 st_table*
st_init_table(type)183 st_init_table(type)
184 struct st_hash_type *type;
185 {
186 return st_init_table_with_size(type, 0);
187 }
188
189 st_table*
st_init_numtable(void)190 st_init_numtable(void)
191 {
192 return st_init_table(&type_numhash);
193 }
194
195 st_table*
st_init_numtable_with_size(size)196 st_init_numtable_with_size(size)
197 int size;
198 {
199 return st_init_table_with_size(&type_numhash, size);
200 }
201
202 st_table*
st_init_strtable(void)203 st_init_strtable(void)
204 {
205 return st_init_table(&type_strhash);
206 }
207
208 st_table*
st_init_strtable_with_size(size)209 st_init_strtable_with_size(size)
210 int size;
211 {
212 return st_init_table_with_size(&type_strhash, size);
213 }
214
215 void
st_free_table(table)216 st_free_table(table)
217 st_table *table;
218 {
219 register st_table_entry *ptr, *next;
220 int i;
221
222 for(i = 0; i < table->num_bins; i++) {
223 ptr = table->bins[i];
224 while (ptr != 0) {
225 next = ptr->next;
226 free(ptr);
227 ptr = next;
228 }
229 }
230 free(table->bins);
231 free(table);
232 }
233
234 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
235 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
236
237 #ifdef HASH_LOG
238 #define COLLISION collision++
239 #else
240 #define COLLISION
241 #endif
242
243 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
244 bin_pos = hash_val%(table)->num_bins;\
245 ptr = (table)->bins[bin_pos];\
246 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
247 COLLISION;\
248 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
249 ptr = ptr->next;\
250 }\
251 ptr = ptr->next;\
252 }\
253 } while (0)
254
255 int
st_lookup(table,key,value)256 st_lookup(table, key, value)
257 st_table *table;
258 register st_data_t key;
259 st_data_t *value;
260 {
261 unsigned int hash_val, bin_pos;
262 register st_table_entry *ptr;
263
264 hash_val = do_hash(key, table);
265 FIND_ENTRY(table, ptr, hash_val, bin_pos);
266
267 if (ptr == 0) {
268 return 0;
269 }
270 else {
271 if (value != 0) *value = ptr->record;
272 return 1;
273 }
274 }
275
276 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
277 do {\
278 st_table_entry *entry;\
279 if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
280 rehash(table);\
281 bin_pos = hash_val % table->num_bins;\
282 }\
283 \
284 entry = alloc(st_table_entry);\
285 \
286 entry->hash = hash_val;\
287 entry->key = key;\
288 entry->record = value;\
289 entry->next = table->bins[bin_pos];\
290 table->bins[bin_pos] = entry;\
291 table->num_entries++;\
292 } while (0)
293
294 int
st_insert(table,key,value)295 st_insert(table, key, value)
296 register st_table *table;
297 register st_data_t key;
298 st_data_t value;
299 {
300 unsigned int hash_val, bin_pos;
301 register st_table_entry *ptr;
302
303 hash_val = do_hash(key, table);
304 FIND_ENTRY(table, ptr, hash_val, bin_pos);
305
306 if (ptr == 0) {
307 ADD_DIRECT(table, key, value, hash_val, bin_pos);
308 return 0;
309 }
310 else {
311 ptr->record = value;
312 return 1;
313 }
314 }
315
316 void
st_add_direct(table,key,value)317 st_add_direct(table, key, value)
318 st_table *table;
319 st_data_t key;
320 st_data_t value;
321 {
322 unsigned int hash_val, bin_pos;
323
324 hash_val = do_hash(key, table);
325 bin_pos = hash_val % table->num_bins;
326 ADD_DIRECT(table, key, value, hash_val, bin_pos);
327 }
328
329 static void
rehash(table)330 rehash(table)
331 register st_table *table;
332 {
333 register st_table_entry *ptr, *next, **new_bins;
334 int i, old_num_bins = table->num_bins, new_num_bins;
335 unsigned int hash_val;
336
337 new_num_bins = new_size(old_num_bins+1);
338 new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
339
340 for(i = 0; i < old_num_bins; i++) {
341 ptr = table->bins[i];
342 while (ptr != 0) {
343 next = ptr->next;
344 hash_val = ptr->hash % new_num_bins;
345 ptr->next = new_bins[hash_val];
346 new_bins[hash_val] = ptr;
347 ptr = next;
348 }
349 }
350 free(table->bins);
351 table->num_bins = new_num_bins;
352 table->bins = new_bins;
353 }
354
355 st_table*
st_copy(old_table)356 st_copy(old_table)
357 st_table *old_table;
358 {
359 st_table *new_table;
360 st_table_entry *ptr, *entry;
361 int i, num_bins = old_table->num_bins;
362
363 new_table = alloc(st_table);
364 if (new_table == 0) {
365 return 0;
366 }
367
368 *new_table = *old_table;
369 new_table->bins = (st_table_entry**)
370 Calloc((unsigned)num_bins, sizeof(st_table_entry*));
371
372 if (new_table->bins == 0) {
373 free(new_table);
374 return 0;
375 }
376
377 for(i = 0; i < num_bins; i++) {
378 new_table->bins[i] = 0;
379 ptr = old_table->bins[i];
380 while (ptr != 0) {
381 entry = alloc(st_table_entry);
382 if (entry == 0) {
383 free(new_table->bins);
384 free(new_table);
385 return 0;
386 }
387 *entry = *ptr;
388 entry->next = new_table->bins[i];
389 new_table->bins[i] = entry;
390 ptr = ptr->next;
391 }
392 }
393 return new_table;
394 }
395
396 int
st_delete(table,key,value)397 st_delete(table, key, value)
398 register st_table *table;
399 register st_data_t *key;
400 st_data_t *value;
401 {
402 unsigned int hash_val;
403 st_table_entry *tmp;
404 register st_table_entry *ptr;
405
406 hash_val = do_hash_bin(*key, table);
407 ptr = table->bins[hash_val];
408
409 if (ptr == 0) {
410 if (value != 0) *value = 0;
411 return 0;
412 }
413
414 if (EQUAL(table, *key, ptr->key)) {
415 table->bins[hash_val] = ptr->next;
416 table->num_entries--;
417 if (value != 0) *value = ptr->record;
418 *key = ptr->key;
419 free(ptr);
420 return 1;
421 }
422
423 for(; ptr->next != 0; ptr = ptr->next) {
424 if (EQUAL(table, ptr->next->key, *key)) {
425 tmp = ptr->next;
426 ptr->next = ptr->next->next;
427 table->num_entries--;
428 if (value != 0) *value = tmp->record;
429 *key = tmp->key;
430 free(tmp);
431 return 1;
432 }
433 }
434
435 return 0;
436 }
437
438 int
st_delete_safe(table,key,value,never)439 st_delete_safe(table, key, value, never)
440 register st_table *table;
441 register st_data_t *key;
442 st_data_t *value;
443 st_data_t never;
444 {
445 unsigned int hash_val;
446 register st_table_entry *ptr;
447
448 hash_val = do_hash_bin(*key, table);
449 ptr = table->bins[hash_val];
450
451 if (ptr == 0) {
452 if (value != 0) *value = 0;
453 return 0;
454 }
455
456 for(; ptr != 0; ptr = ptr->next) {
457 if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
458 table->num_entries--;
459 *key = ptr->key;
460 if (value != 0) *value = ptr->record;
461 ptr->key = ptr->record = never;
462 return 1;
463 }
464 }
465
466 return 0;
467 }
468
469 static int
delete_never(key,value,never)470 delete_never(key, value, never)
471 st_data_t key, value, never;
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
