1 /*
2 * Generic hash table routines.
3 * (c) Thomas Pornin 1998, 1999, 2000
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 4. The name of the authors may not be used to endorse or promote
14 * products derived from this software without specific prior written
15 * permission.
16 *
17 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
23 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
24 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
25 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
26 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
27 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 */
30
31 #include <string.h>
32 #include "hash.h"
33 #include "mem.h"
34 #include "tune.h"
35
36 /*
37 * hash_string() is a sample hash function for strings
38 */
hash_string(char * s)39 int hash_string(char *s)
40 {
41 #ifdef FAST_HASH
42 unsigned h = 0, g;
43
44 while (*s) {
45 h = (h << 4) + *(unsigned char *)(s ++);
46 if ((g = h & 0xF000U) != 0) h ^= (g >> 12);
47 h &= ~g;
48 }
49 return (h ^ (h >> 9)) & 127U;
50 #else
51 unsigned char h = 0;
52
53 for (; *s; s ++) h ^= (unsigned char)(*s);
54 return ((int)h);
55 #endif
56 }
57
58 /*
59 * struct hash_item is the basic data type to internally handle hash tables
60 */
61 struct hash_item {
62 void *data;
63 struct hash_item *next;
64 };
65
66 /*
67 * This function adds an entry to the struct hash_item list
68 */
add_entry(struct hash_item * blist,void * data)69 static struct hash_item *add_entry(struct hash_item *blist, void *data)
70 {
71 struct hash_item *t = getmem(sizeof(struct hash_item));
72
73 t->data = data;
74 t->next = blist;
75 return t;
76 }
77
78 /*
79 * This function finds a struct hash_item in a list, using the
80 * comparison function provided as cmpdata (*cmpdata() returns
81 * non-zero if the two parameters are to be considered identical).
82 *
83 * It returns 0 if the item is not found.
84 */
get_entry(struct hash_item * blist,void * data,int (* cmpdata)(void *,void *))85 static struct hash_item *get_entry(struct hash_item *blist, void *data,
86 int (*cmpdata)(void *, void *))
87 {
88 while (blist) {
89 if ((*cmpdata)(data, blist->data)) return blist;
90 blist = blist->next;
91 }
92 return 0;
93 }
94
95 /*
96 * This function acts like get_entry but deletes the found item, using
97 * the provided function deldata(); it returns 0 if the given data was
98 * not found.
99 */
del_entry(struct hash_item * blist,void * data,int (* cmpdata)(void *,void *),void (* deldata)(void *))100 static struct hash_item *del_entry(struct hash_item *blist, void *data,
101 int (*cmpdata)(void *, void *), void (*deldata)(void *))
102 {
103 struct hash_item *prev = 0, *save = blist;
104
105 while (blist) {
106 if ((*cmpdata)(data, blist->data)) {
107 if (deldata) (*deldata)(blist->data);
108 if (prev) prev->next = blist->next;
109 if (save == blist) save = blist->next;
110 freemem(blist);
111 return save;
112 }
113 prev = blist;
114 blist = blist->next;
115 }
116 return 0;
117 }
118
119 /*
120 * This function creates a new hashtable, with the hashing and comparison
121 * functions given as parameters
122 */
newHT(int n,int (* cmpdata)(void *,void *),int (* hash)(void *),void (* deldata)(void *))123 struct HT *newHT(int n, int (*cmpdata)(void *, void *), int (*hash)(void *),
124 void (*deldata)(void *))
125 {
126 struct HT *t = getmem(sizeof(struct HT));
127 int i;
128
129 t->lists = getmem(n * sizeof(struct hash_item *));
130 for (i = 0; i < n; i ++) t->lists[i] = 0;
131 t->nb_lists = n;
132 t->cmpdata = cmpdata;
133 t->hash = hash;
134 t->deldata = deldata;
135 return t;
136 }
137
138 /*
139 * This function adds a new entry in the hashtable ht; it returns 0
140 * on success, or a pointer to the already present item otherwise.
141 */
putHT(struct HT * ht,void * data)142 void *putHT(struct HT *ht, void *data)
143 {
144 int h;
145 struct hash_item *d;
146
147 h = ((*(ht->hash))(data));
148 #ifndef FAST_HASH
149 h %= ht->nb_lists;
150 #endif
151 if ((d = get_entry(ht->lists[h], data, ht->cmpdata)))
152 return d->data;
153 ht->lists[h] = add_entry(ht->lists[h], data);
154 return 0;
155 }
156
157 /*
158 * This function adds a new entry in the hashtable ht, even if an equal
159 * entry is already there. Exercise caution !
160 * The new entry will "hide" the old one, which means that the new will be
161 * found upon lookup/delete, not the old one.
162 */
forceputHT(struct HT * ht,void * data)163 void *forceputHT(struct HT *ht, void *data)
164 {
165 int h;
166
167 h = ((*(ht->hash))(data));
168 #ifndef FAST_HASH
169 h %= ht->nb_lists;
170 #endif
171 ht->lists[h] = add_entry(ht->lists[h], data);
172 return 0;
173 }
174
175 /*
176 * This function finds the entry corresponding to *data in the
177 * hashtable ht (using the comparison function given as argument
178 * to newHT)
179 */
getHT(struct HT * ht,void * data)180 void *getHT(struct HT *ht, void *data)
181 {
182 int h;
183 struct hash_item *t;
184
185 h = ((*(ht->hash))(data));
186 #ifndef FAST_HASH
187 h %= ht->nb_lists;
188 #endif
189 if ((t = get_entry(ht->lists[h], data, ht->cmpdata)) == 0)
190 return 0;
191 return (t->data);
192 }
193
194 /*
195 * This function finds and delete the entry corresponding to *data
196 * in the hashtable ht (using the comparison function given as
197 * argument to newHT).
198 */
199
delHT(struct HT * ht,void * data)200 int delHT(struct HT *ht, void *data)
201 {
202 int h;
203
204 h = ((*(ht->hash))(data));
205 #ifndef FAST_HASH
206 h %= ht->nb_lists;
207 #endif
208 ht->lists[h] = del_entry(ht->lists[h], data, ht->cmpdata, ht->deldata);
209 return 1;
210 }
211
212 /*
213 * This function completely eradicates from memory a given hash table,
214 * releasing all objects
215 */
killHT(struct HT * ht)216 void killHT(struct HT *ht)
217 {
218 int i;
219 struct hash_item *t, *n;
220 void (*dd)(void *) = ht->deldata;
221
222 for (i = 0; i < ht->nb_lists; i ++) for (t = ht->lists[i]; t;) {
223 n = t->next;
224 if (dd) (*dd)(t->data);
225 freemem(t);
226 t = n;
227 }
228 freemem(ht->lists);
229 freemem(ht);
230 }
231
232 /*
233 * This function stores a backup of the hash table, for context stacking.
234 */
saveHT(struct HT * ht,void ** buffer)235 void saveHT(struct HT *ht, void **buffer)
236 {
237 struct hash_item **b = (struct hash_item **)buffer;
238
239 mmv(b, ht->lists, ht->nb_lists * sizeof(struct hash_item *));
240 }
241
242 /*
243 * This function restores the saved state of the hash table.
244 * Do NOT use if some of the entries that were present before the backup
245 * have been removed (even temporarily).
246 */
restoreHT(struct HT * ht,void ** buffer)247 void restoreHT(struct HT *ht, void **buffer)
248 {
249 struct hash_item **b = (struct hash_item **)buffer;
250 int i;
251
252 for (i = 0; i < ht->nb_lists; i ++) {
253 struct hash_item *t = ht->lists[i], *n;
254
255 while (t != b[i]) {
256 n = t->next;
257 (*(ht->deldata))(t->data);
258 freemem(t);
259 t = n;
260 }
261 ht->lists[i] = b[i];
262 }
263 }
264
265 /*
266 * This function is evil. It inserts a new item in a saved hash table,
267 * tweaking the save buffer and the hash table in order to keep things
268 * stable. There are no checks.
269 */
tweakHT(struct HT * ht,void ** buffer,void * data)270 void tweakHT(struct HT *ht, void **buffer, void *data)
271 {
272 int h;
273 struct hash_item *d, *e;
274
275 h = ((*(ht->hash))(data));
276 #ifndef FAST_HASH
277 h %= ht->nb_lists;
278 #endif
279 for (d = ht->lists[h]; d != buffer[h]; d = d->next);
280 d = add_entry(buffer[h], data);
281 if (buffer[h] == ht->lists[h]) {
282 buffer[h] = ht->lists[h] = d;
283 return;
284 }
285 for (e = ht->lists[h]; e->next != buffer[h]; e = e->next);
286 e->next = d;
287 buffer[h] = d;
288 }
289
290 /*
291 * This function scans the whole table and calls the given function on
292 * each entry.
293 */
scanHT(struct HT * ht,void (* action)(void *))294 void scanHT(struct HT *ht, void (*action)(void *))
295 {
296 int i;
297
298 for (i = 0; i < ht->nb_lists; i ++) {
299 struct hash_item *t = ht->lists[i];
300
301 while (t) {
302 (*action)(t->data);
303 t = t->next;
304 }
305 }
306 }
307
308 /*
309 * The two following fonctions are generic for storing structures
310 * uniquely identified by their name, which must be the first
311 * field of the structure.
312 */
hash_struct(void * m)313 int hash_struct(void *m)
314 {
315 char *n = *(char **)m;
316
317 #ifdef FAST_HASH
318 return hash_string(n);
319 #else
320 return hash_string(n) & 127;
321 #endif
322 }
323
cmp_struct(void * m1,void * m2)324 int cmp_struct(void *m1, void *m2)
325 {
326 char *n1 = *(char **)m1, *n2 = *(char **)m2;
327
328 return !strcmp(n1, n2);
329 }
330