9 static int isprime(int number);
10 static int nextprime(int number);
12 static void hashexpand(hashtable *table);
14 static unsigned chrhash(void *s, int M);
15 static int chrcomp(void *s1, void *s2);
16 static void * chrdupe(void *key);
18 static unsigned inthash(void *s, int M);
19 static int intcomp(void *s1, void *s2);
20 static void * intdupe(void *i);
24 hashcreate(hashtable *table, keytype typ, int size)
26 table->size=nextprime(size);
30 table->hashfunc=chrhash;
31 table->compfunc=chrcomp;
32 table->dupefunc=chrdupe;
35 table->hashfunc=inthash;
36 table->compfunc=intcomp;
37 table->dupefunc=intdupe;
40 assert((table->table=(calloc(table->size, sizeof(bucket *)))) != NULL);
44 hashinsert(hashtable *table, void *key, void *val)
46 unsigned h=table->hashfunc(key, table->size);
49 assert((p=(bucket *)malloc(sizeof(bucket))) != NULL);
50 assert((p->key=table->dupefunc(key)) != NULL);
53 for (; (table->table)[h] != NULL; h=(h+1)%table->size)
58 if (table->numkeys++ > table->size/2)
63 hashfind(hashtable *table, void *key)
65 register unsigned h=table->hashfunc(key, table->size);
67 for (; (table->table)[h] != NULL; h=(h+1)%table->size)
68 if (table->compfunc((table->table)[h]->key, key) == 0)
69 return (table->table)[h]->val;
75 hashdelete(hashtable *table, void *key)
77 register unsigned h=table->hashfunc(key, table->size);
79 for (; (table->table)[h] != NULL; h=(h+1)%table->size) {
80 if (table->compfunc((table->table)[h]->key, key) == 0) {
81 free((table->table)[h]->key);
82 free((table->table)[h]->val);
83 (table->table)[h]->key=(table->table)[h]->val=NULL;
84 free((table->table)[h]);
85 (table->table)[h]=NULL;
91 hashforeach(hashtable *table, void (*func)(void *, void *))
95 for (l=0; l<table->size; l++)
96 if ((table->table)[l] != NULL)
97 func((table->table)[l]->key, (table->table)[l]->val);
101 hashempty(hashtable *table)
105 for (l=0; l<table->size; l++) {
106 if ((table->table)[l] != NULL) {
107 free((table->table)[l]->key);
108 free((table->table)[l]->val);
109 free((table->table)[l]);
110 (table->table)[l]=NULL;
118 hashexpand(hashtable *table)
124 size=nextprime(table->size*2);
126 assert((t=(calloc(size, sizeof(bucket *)))) != NULL);
128 for (l=0; l<table->size; l++) {
129 if ((table->table)[l] != NULL) {
130 h=table->hashfunc((table->table)[l]->key, size);
132 for (; t[h] != NULL; h=(h+1)%size)
135 t[h]=(table->table)[l];
146 nextprime(int number)
148 for (;!isprime(number);number++)
169 chrhash(void *p, int M)
171 register unsigned hashval;
174 for (hashval=0; *s!='\0'; s++)
175 hashval=*s+31*hashval;
181 chrcomp(void *s1, void *s2)
183 return strcmp((char *)s1, (char *)s2);
189 return (void *)strdup((char *)key);
193 inthash(void *i, int M)
199 intcomp(void *i1, void *i2)
201 return *(int *)i1-*(int *)i2;
210 assert((p=(int *)malloc(sizeof(int))) != NULL);