![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to st.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / mbstring / oniguruma|
Return to st.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / mbstring / oniguruma |
1.1 misho 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: {
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
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: {
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*
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*
190: st_init_numtable(void)
191: {
192: return st_init_table(&type_numhash);
193: }
194:
195: st_table*
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*
203: st_init_strtable(void)
204: {
205: return st_init_table(&type_strhash);
206: }
207:
208: st_table*
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
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
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
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
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
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*
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
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
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
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
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
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
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
578: numcmp(x, y)
579: long x, y;
580: {
581: return x != y;
582: }
583:
584: static int
585: numhash(n)
586: long n;
587: {
588: return n;
589: }