1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <assert.h>
4 #include <string.h>
5 #include <math.h>
6 #include <time.h>
7 #include "hash.h"
8
9 static int isprime(int number);
10 static int nextprime(int number);
11
12 static void hashexpand(hashtable *table);
13
14 static unsigned chrhash(void *s, int M);
15 static int chrcomp(void *s1, void *s2);
16 static void * chrdupe(void *key);
17
18 static unsigned inthash(void *s, int M);
19 static int intcomp(void *s1, void *s2);
20 static void * intdupe(void *i);
21
22
23 void
hashcreate(hashtable * table,keytype typ,int size)24 hashcreate(hashtable *table, keytype typ, int size)
25 {
26 table->size=nextprime(size);
27 table->numkeys=0;
28
29 if (typ == CHAR) {
30 table->hashfunc=chrhash;
31 table->compfunc=chrcomp;
32 table->dupefunc=chrdupe;
33 }
34 else { /* INT */
35 table->hashfunc=inthash;
36 table->compfunc=intcomp;
37 table->dupefunc=intdupe;
38 }
39
40 assert((table->table=(calloc(table->size, sizeof(bucket *)))) != NULL);
41 }
42
43 void
hashinsert(hashtable * table,void * key,void * val)44 hashinsert(hashtable *table, void *key, void *val)
45 {
46 unsigned h=table->hashfunc(key, table->size);
47 bucket *p;
48
49 assert((p=(bucket *)malloc(sizeof(bucket))) != NULL);
50 assert((p->key=table->dupefunc(key)) != NULL);
51 p->val=val;
52
53 for (; (table->table)[h] != NULL; h=(h+1)%table->size)
54 ;
55
56 (table->table)[h]=p;
57
58 if (table->numkeys++ > table->size/2)
59 hashexpand(table);
60 }
61
62 void *
hashfind(hashtable * table,void * key)63 hashfind(hashtable *table, void *key)
64 {
65 register unsigned h=table->hashfunc(key, table->size);
66
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;
70
71 return NULL;
72 }
73
74 void
hashdelete(hashtable * table,void * key)75 hashdelete(hashtable *table, void *key)
76 {
77 register unsigned h=table->hashfunc(key, table->size);
78
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;
86 }
87 }
88 }
89
90 void
hashforeach(hashtable * table,void (* func)(void *,void *))91 hashforeach(hashtable *table, void (*func)(void *, void *))
92 {
93 int l;
94
95 for (l=0; l<table->size; l++)
96 if ((table->table)[l] != NULL)
97 func((table->table)[l]->key, (table->table)[l]->val);
98 }
99
100 void
hashempty(hashtable * table)101 hashempty(hashtable *table)
102 {
103 int l;
104
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;
111 }
112 }
113
114 table->numkeys=0;
115 }
116
117 static void
hashexpand(hashtable * table)118 hashexpand(hashtable *table)
119 {
120 int size, l;
121 bucket **t;
122 unsigned h;
123
124 size=nextprime(table->size*2);
125
126 assert((t=(calloc(size, sizeof(bucket *)))) != NULL);
127
128 for (l=0; l<table->size; l++) {
129 if ((table->table)[l] != NULL) {
130 h=table->hashfunc((table->table)[l]->key, size);
131
132 for (; t[h] != NULL; h=(h+1)%size)
133 ;
134
135 t[h]=(table->table)[l];
136 }
137 }
138
139 free(table->table);
140
141 table->size=size;
142 table->table=t;
143 }
144
145 static int
nextprime(int number)146 nextprime(int number)
147 {
148 for (;!isprime(number);number++)
149 ;
150
151 return number;
152 }
153
154 static int
isprime(int number)155 isprime(int number)
156 {
157 int sqr, l;
158
159 sqr=sqrt(number);
160
161 for (l=2;l<=sqr;l++)
162 if (number%l == 0)
163 return 0;
164
165 return 1;
166 }
167
168 static unsigned
chrhash(void * p,int M)169 chrhash(void *p, int M)
170 {
171 register unsigned hashval;
172 register char *s=p;
173
174 for (hashval=0; *s!='\0'; s++)
175 hashval=*s+31*hashval;
176
177 return hashval%M;
178 }
179
180 static int
chrcomp(void * s1,void * s2)181 chrcomp(void *s1, void *s2)
182 {
183 return strcmp((char *)s1, (char *)s2);
184 }
185
186 static void *
chrdupe(void * key)187 chrdupe(void *key)
188 {
189 return (void *)strdup((char *)key);
190 }
191
192 static unsigned
inthash(void * i,int M)193 inthash(void *i, int M)
194 {
195 return *(int *)i%M;
196 }
197
198 static int
intcomp(void * i1,void * i2)199 intcomp(void *i1, void *i2)
200 {
201 return *(int *)i1-*(int *)i2;
202 }
203
204 static void *
intdupe(void * i)205 intdupe(void *i)
206 {
207 int *p;
208
209
210 assert((p=(int *)malloc(sizeof(int))) != NULL);
211
212 *p=*(int *)i;
213
214 return p;
215 }
216
217
218
219
220
221
222
223