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