Line data Source code
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 : */
39 0 : 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 0 : unsigned char h = 0;
52 :
53 0 : for (; *s; s ++) h ^= (unsigned char)(*s);
54 0 : 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 : */
69 0 : static struct hash_item *add_entry(struct hash_item *blist, void *data)
70 : {
71 0 : struct hash_item *t = getmem(sizeof(struct hash_item));
72 :
73 0 : t->data = data;
74 0 : t->next = blist;
75 0 : 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 : */
85 0 : static struct hash_item *get_entry(struct hash_item *blist, void *data,
86 : int (*cmpdata)(void *, void *))
87 : {
88 0 : while (blist) {
89 0 : if ((*cmpdata)(data, blist->data)) return blist;
90 0 : blist = blist->next;
91 : }
92 0 : 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 : */
100 0 : static struct hash_item *del_entry(struct hash_item *blist, void *data,
101 : int (*cmpdata)(void *, void *), void (*deldata)(void *))
102 : {
103 0 : struct hash_item *prev = 0, *save = blist;
104 :
105 0 : while (blist) {
106 0 : if ((*cmpdata)(data, blist->data)) {
107 0 : if (deldata) (*deldata)(blist->data);
108 0 : if (prev) prev->next = blist->next;
109 0 : if (save == blist) save = blist->next;
110 0 : freemem(blist);
111 0 : return save;
112 : }
113 0 : prev = blist;
114 0 : blist = blist->next;
115 : }
116 0 : return 0;
117 : }
118 :
119 : /*
120 : * This function creates a new hashtable, with the hashing and comparison
121 : * functions given as parameters
122 : */
123 0 : struct HT *newHT(int n, int (*cmpdata)(void *, void *), int (*hash)(void *),
124 : void (*deldata)(void *))
125 : {
126 0 : struct HT *t = getmem(sizeof(struct HT));
127 : int i;
128 :
129 0 : t->lists = getmem(n * sizeof(struct hash_item *));
130 0 : for (i = 0; i < n; i ++) t->lists[i] = 0;
131 0 : t->nb_lists = n;
132 0 : t->cmpdata = cmpdata;
133 0 : t->hash = hash;
134 0 : t->deldata = deldata;
135 0 : 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 : */
142 0 : void *putHT(struct HT *ht, void *data)
143 : {
144 : int h;
145 : struct hash_item *d;
146 :
147 0 : h = ((*(ht->hash))(data));
148 : #ifndef FAST_HASH
149 0 : h %= ht->nb_lists;
150 : #endif
151 0 : if ((d = get_entry(ht->lists[h], data, ht->cmpdata)))
152 0 : return d->data;
153 0 : ht->lists[h] = add_entry(ht->lists[h], data);
154 0 : 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 : */
163 0 : void *forceputHT(struct HT *ht, void *data)
164 : {
165 : int h;
166 :
167 0 : h = ((*(ht->hash))(data));
168 : #ifndef FAST_HASH
169 0 : h %= ht->nb_lists;
170 : #endif
171 0 : ht->lists[h] = add_entry(ht->lists[h], data);
172 0 : 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 : */
180 0 : void *getHT(struct HT *ht, void *data)
181 : {
182 : int h;
183 : struct hash_item *t;
184 :
185 0 : h = ((*(ht->hash))(data));
186 : #ifndef FAST_HASH
187 0 : h %= ht->nb_lists;
188 : #endif
189 0 : if ((t = get_entry(ht->lists[h], data, ht->cmpdata)) == 0)
190 0 : return 0;
191 0 : 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 :
200 0 : int delHT(struct HT *ht, void *data)
201 : {
202 : int h;
203 :
204 0 : h = ((*(ht->hash))(data));
205 : #ifndef FAST_HASH
206 0 : h %= ht->nb_lists;
207 : #endif
208 0 : ht->lists[h] = del_entry(ht->lists[h], data, ht->cmpdata, ht->deldata);
209 0 : return 1;
210 : }
211 :
212 : /*
213 : * This function completely eradicates from memory a given hash table,
214 : * releasing all objects
215 : */
216 0 : void killHT(struct HT *ht)
217 : {
218 : int i;
219 : struct hash_item *t, *n;
220 0 : void (*dd)(void *) = ht->deldata;
221 :
222 0 : for (i = 0; i < ht->nb_lists; i ++) for (t = ht->lists[i]; t;) {
223 0 : n = t->next;
224 0 : if (dd) (*dd)(t->data);
225 0 : freemem(t);
226 0 : t = n;
227 : }
228 0 : freemem(ht->lists);
229 0 : freemem(ht);
230 0 : }
231 :
232 : /*
233 : * This function stores a backup of the hash table, for context stacking.
234 : */
235 0 : void saveHT(struct HT *ht, void **buffer)
236 : {
237 0 : struct hash_item **b = (struct hash_item **)buffer;
238 :
239 0 : mmv(b, ht->lists, ht->nb_lists * sizeof(struct hash_item *));
240 0 : }
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 : */
247 0 : void restoreHT(struct HT *ht, void **buffer)
248 : {
249 0 : struct hash_item **b = (struct hash_item **)buffer;
250 : int i;
251 :
252 0 : for (i = 0; i < ht->nb_lists; i ++) {
253 0 : struct hash_item *t = ht->lists[i], *n;
254 :
255 0 : while (t != b[i]) {
256 0 : n = t->next;
257 0 : (*(ht->deldata))(t->data);
258 0 : freemem(t);
259 0 : t = n;
260 : }
261 0 : ht->lists[i] = b[i];
262 : }
263 0 : }
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 : */
270 0 : void tweakHT(struct HT *ht, void **buffer, void *data)
271 : {
272 : int h;
273 : struct hash_item *d, *e;
274 :
275 0 : h = ((*(ht->hash))(data));
276 : #ifndef FAST_HASH
277 0 : h %= ht->nb_lists;
278 : #endif
279 0 : for (d = ht->lists[h]; d != buffer[h]; d = d->next);
280 0 : d = add_entry(buffer[h], data);
281 0 : if (buffer[h] == ht->lists[h]) {
282 0 : buffer[h] = ht->lists[h] = d;
283 0 : return;
284 : }
285 0 : for (e = ht->lists[h]; e->next != buffer[h]; e = e->next);
286 0 : e->next = d;
287 0 : buffer[h] = d;
288 : }
289 :
290 : /*
291 : * This function scans the whole table and calls the given function on
292 : * each entry.
293 : */
294 0 : void scanHT(struct HT *ht, void (*action)(void *))
295 : {
296 : int i;
297 :
298 0 : for (i = 0; i < ht->nb_lists; i ++) {
299 0 : struct hash_item *t = ht->lists[i];
300 :
301 0 : while (t) {
302 0 : (*action)(t->data);
303 0 : t = t->next;
304 : }
305 : }
306 0 : }
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 : */
313 0 : int hash_struct(void *m)
314 : {
315 0 : char *n = *(char **)m;
316 :
317 : #ifdef FAST_HASH
318 : return hash_string(n);
319 : #else
320 0 : return hash_string(n) & 127;
321 : #endif
322 : }
323 :
324 0 : int cmp_struct(void *m1, void *m2)
325 : {
326 0 : char *n1 = *(char **)m1, *n2 = *(char **)m2;
327 :
328 0 : return !strcmp(n1, n2);
329 : }
|
