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
120 : new_size(size)
121 : int size;
122 2 : {
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 2 : for (i = 0, newsize = MINSIZE;
134 6 : i < (int )(sizeof(primes)/sizeof(primes[0]));
135 2 : i++, newsize <<= 1)
136 : {
137 4 : if (newsize > size) return primes[i];
138 : }
139 : /* Ran out of polynomials */
140 0 : 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
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*
158 : st_init_table_with_size(type, size)
159 : struct st_hash_type *type;
160 : int size;
161 2 : {
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 2 : size = new_size(size); /* round up to prime number */
172 :
173 2 : tbl = alloc(st_table);
174 2 : tbl->type = type;
175 2 : tbl->num_entries = 0;
176 2 : tbl->num_bins = size;
177 2 : tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
178 :
179 2 : return tbl;
180 : }
181 :
182 : st_table*
183 : st_init_table(type)
184 : struct st_hash_type *type;
185 0 : {
186 0 : return st_init_table_with_size(type, 0);
187 : }
188 :
189 : st_table*
190 : st_init_numtable(void)
191 0 : {
192 0 : return st_init_table(&type_numhash);
193 : }
194 :
195 : st_table*
196 : st_init_numtable_with_size(size)
197 : int size;
198 0 : {
199 0 : return st_init_table_with_size(&type_numhash, size);
200 : }
201 :
202 : st_table*
203 : st_init_strtable(void)
204 0 : {
205 0 : return st_init_table(&type_strhash);
206 : }
207 :
208 : st_table*
209 : st_init_strtable_with_size(size)
210 : int size;
211 0 : {
212 0 : return st_init_table_with_size(&type_strhash, size);
213 : }
214 :
215 : void
216 : st_free_table(table)
217 : st_table *table;
218 0 : {
219 : register st_table_entry *ptr, *next;
220 : int i;
221 :
222 0 : for(i = 0; i < table->num_bins; i++) {
223 0 : ptr = table->bins[i];
224 0 : while (ptr != 0) {
225 0 : next = ptr->next;
226 0 : free(ptr);
227 0 : ptr = next;
228 : }
229 : }
230 0 : free(table->bins);
231 0 : free(table);
232 0 : }
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
256 : st_lookup(table, key, value)
257 : st_table *table;
258 : register st_data_t key;
259 : st_data_t *value;
260 4 : {
261 : unsigned int hash_val, bin_pos;
262 : register st_table_entry *ptr;
263 :
264 4 : hash_val = do_hash(key, table);
265 4 : FIND_ENTRY(table, ptr, hash_val, bin_pos);
266 :
267 4 : if (ptr == 0) {
268 4 : return 0;
269 : }
270 : else {
271 0 : if (value != 0) *value = ptr->record;
272 0 : 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
295 : st_insert(table, key, value)
296 : register st_table *table;
297 : register st_data_t key;
298 : st_data_t value;
299 0 : {
300 : unsigned int hash_val, bin_pos;
301 : register st_table_entry *ptr;
302 :
303 0 : hash_val = do_hash(key, table);
304 0 : FIND_ENTRY(table, ptr, hash_val, bin_pos);
305 :
306 0 : if (ptr == 0) {
307 0 : ADD_DIRECT(table, key, value, hash_val, bin_pos);
308 0 : return 0;
309 : }
310 : else {
311 0 : ptr->record = value;
312 0 : return 1;
313 : }
314 : }
315 :
316 : void
317 : st_add_direct(table, key, value)
318 : st_table *table;
319 : st_data_t key;
320 : st_data_t value;
321 6 : {
322 : unsigned int hash_val, bin_pos;
323 :
324 6 : hash_val = do_hash(key, table);
325 6 : bin_pos = hash_val % table->num_bins;
326 6 : ADD_DIRECT(table, key, value, hash_val, bin_pos);
327 6 : }
328 :
329 : static void
330 : rehash(table)
331 : register st_table *table;
332 0 : {
333 : register st_table_entry *ptr, *next, **new_bins;
334 0 : int i, old_num_bins = table->num_bins, new_num_bins;
335 : unsigned int hash_val;
336 :
337 0 : new_num_bins = new_size(old_num_bins+1);
338 0 : new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
339 :
340 0 : for(i = 0; i < old_num_bins; i++) {
341 0 : ptr = table->bins[i];
342 0 : while (ptr != 0) {
343 0 : next = ptr->next;
344 0 : hash_val = ptr->hash % new_num_bins;
345 0 : ptr->next = new_bins[hash_val];
346 0 : new_bins[hash_val] = ptr;
347 0 : ptr = next;
348 : }
349 : }
350 0 : free(table->bins);
351 0 : table->num_bins = new_num_bins;
352 0 : table->bins = new_bins;
353 0 : }
354 :
355 : st_table*
356 : st_copy(old_table)
357 : st_table *old_table;
358 0 : {
359 : st_table *new_table;
360 : st_table_entry *ptr, *entry;
361 0 : int i, num_bins = old_table->num_bins;
362 :
363 0 : new_table = alloc(st_table);
364 0 : if (new_table == 0) {
365 0 : return 0;
366 : }
367 :
368 0 : *new_table = *old_table;
369 0 : new_table->bins = (st_table_entry**)
370 : Calloc((unsigned)num_bins, sizeof(st_table_entry*));
371 :
372 0 : if (new_table->bins == 0) {
373 0 : free(new_table);
374 0 : return 0;
375 : }
376 :
377 0 : for(i = 0; i < num_bins; i++) {
378 0 : new_table->bins[i] = 0;
379 0 : ptr = old_table->bins[i];
380 0 : while (ptr != 0) {
381 0 : entry = alloc(st_table_entry);
382 0 : if (entry == 0) {
383 0 : free(new_table->bins);
384 0 : free(new_table);
385 0 : return 0;
386 : }
387 0 : *entry = *ptr;
388 0 : entry->next = new_table->bins[i];
389 0 : new_table->bins[i] = entry;
390 0 : ptr = ptr->next;
391 : }
392 : }
393 0 : return new_table;
394 : }
395 :
396 : int
397 : st_delete(table, key, value)
398 : register st_table *table;
399 : register st_data_t *key;
400 : st_data_t *value;
401 0 : {
402 : unsigned int hash_val;
403 : st_table_entry *tmp;
404 : register st_table_entry *ptr;
405 :
406 0 : hash_val = do_hash_bin(*key, table);
407 0 : ptr = table->bins[hash_val];
408 :
409 0 : if (ptr == 0) {
410 0 : if (value != 0) *value = 0;
411 0 : return 0;
412 : }
413 :
414 0 : if (EQUAL(table, *key, ptr->key)) {
415 0 : table->bins[hash_val] = ptr->next;
416 0 : table->num_entries--;
417 0 : if (value != 0) *value = ptr->record;
418 0 : *key = ptr->key;
419 0 : free(ptr);
420 0 : return 1;
421 : }
422 :
423 0 : for(; ptr->next != 0; ptr = ptr->next) {
424 0 : if (EQUAL(table, ptr->next->key, *key)) {
425 0 : tmp = ptr->next;
426 0 : ptr->next = ptr->next->next;
427 0 : table->num_entries--;
428 0 : if (value != 0) *value = tmp->record;
429 0 : *key = tmp->key;
430 0 : free(tmp);
431 0 : return 1;
432 : }
433 : }
434 :
435 0 : return 0;
436 : }
437 :
438 : int
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 0 : {
445 : unsigned int hash_val;
446 : register st_table_entry *ptr;
447 :
448 0 : hash_val = do_hash_bin(*key, table);
449 0 : ptr = table->bins[hash_val];
450 :
451 0 : if (ptr == 0) {
452 0 : if (value != 0) *value = 0;
453 0 : return 0;
454 : }
455 :
456 0 : for(; ptr != 0; ptr = ptr->next) {
457 0 : if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
458 0 : table->num_entries--;
459 0 : *key = ptr->key;
460 0 : if (value != 0) *value = ptr->record;
461 0 : ptr->key = ptr->record = never;
462 0 : return 1;
463 : }
464 : }
465 :
466 0 : return 0;
467 : }
468 :
469 : static int
470 : delete_never(key, value, never)
471 : st_data_t key, value, never;
472 0 : {
473 0 : if (value == never) return ST_DELETE;
474 0 : return ST_CONTINUE;
475 : }
476 :
477 : void
478 : st_cleanup_safe(table, never)
479 : st_table *table;
480 : st_data_t never;
481 0 : {
482 0 : int num_entries = table->num_entries;
483 :
484 0 : st_foreach(table, delete_never, never);
485 0 : table->num_entries = num_entries;
486 0 : }
487 :
488 : int
489 : st_foreach(table, func, arg)
490 : st_table *table;
491 : int (*func)();
492 : st_data_t arg;
493 2 : {
494 : st_table_entry *ptr, *last, *tmp;
495 : enum st_retval retval;
496 : int i;
497 :
498 40 : for(i = 0; i < table->num_bins; i++) {
499 38 : last = 0;
500 82 : for(ptr = table->bins[i]; ptr != 0;) {
501 6 : retval = (*func)(ptr->key, ptr->record, arg);
502 6 : switch (retval) {
503 : case ST_CHECK: /* check if hash is modified during iteration */
504 0 : tmp = 0;
505 0 : if (i < table->num_bins) {
506 0 : for (tmp = table->bins[i]; tmp; tmp=tmp->next) {
507 0 : if (tmp == ptr) break;
508 : }
509 : }
510 0 : if (!tmp) {
511 : /* call func with error notice */
512 0 : return 1;
513 : }
514 : /* fall through */
515 : case ST_CONTINUE:
516 0 : last = ptr;
517 0 : ptr = ptr->next;
518 0 : break;
519 : case ST_STOP:
520 0 : return 0;
521 : case ST_DELETE:
522 6 : tmp = ptr;
523 6 : if (last == 0) {
524 6 : table->bins[i] = ptr->next;
525 : }
526 : else {
527 0 : last->next = ptr->next;
528 : }
529 6 : ptr = ptr->next;
530 6 : free(tmp);
531 6 : table->num_entries--;
532 : }
533 : }
534 : }
535 2 : return 0;
536 : }
537 :
538 : static int
539 : strhash(string)
540 : register const char *string;
541 0 : {
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 0 : register int val = 0;
568 :
569 0 : while ((c = *string++) != '\0') {
570 0 : val = val*997 + c;
571 : }
572 :
573 0 : return val + (val>>5);
574 : #endif
575 : }
576 :
577 : static int
578 : numcmp(x, y)
579 : long x, y;
580 0 : {
581 0 : return x != y;
582 : }
583 :
584 : static int
585 : numhash(n)
586 : long n;
587 0 : {
588 0 : return n;
589 : }
|
