Branch data 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 : : }
|
