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