Line data Source code
1 : /*
2 : * Mixed hash table / binary tree code.
3 : * (c) Thomas Pornin 2002
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 <stddef.h>
32 : #include <string.h>
33 : #include <limits.h>
34 : #include "nhash.h"
35 : #include "mem.h"
36 :
37 : /*
38 : * Hash a string into an `unsigned' value. This function is derived
39 : * from the hash function used in the ELF binary object file format
40 : * hash tables. The result size is a 32-bit number if the `unsigned'
41 : * type is big enough to hold 32-bit arbitrary numbers, a 16-bit number
42 : * otherwise.
43 : */
44 0 : static unsigned hash_string(char *name)
45 : {
46 0 : unsigned h = 0;
47 :
48 0 : for (h = 0; *name; name ++) {
49 : unsigned g;
50 :
51 0 : h = (h << 4) + *(unsigned char *)name;
52 : #if UINT_MAX >= 0xffffffffU
53 0 : g = h & 0xF0000000U;
54 0 : h ^= (g >> 24);
55 : #else
56 : g = h & 0xF000U;
57 : h ^= (g >> 12);
58 : #endif
59 0 : h &= ~g;
60 : }
61 0 : return h;
62 : }
63 :
64 : /*
65 : * Each item in the table is a structure beginning with a `hash_item_header'
66 : * structure. Those headers define binary trees such that all left-descendants
67 : * (respectively right-descendants) of a given tree node have an associated
68 : * hash value strictly smaller (respectively greater) than the hash value
69 : * associated with this node.
70 : *
71 : * The `ident' field points to an array of char. The `sizeof(unsigned)'
72 : * first `char' contain a copy of an `unsigned' value which is the hashed
73 : * string, except the least significant bit. When this bit is set to 0,
74 : * the node contains the unique item using that hash value. If the bit
75 : * is set to 1, then there are several items with that hash value.
76 : *
77 : * When several items share the same hash value, they are linked together
78 : * in a linked list by their `left' field. The node contains no data;
79 : * it is a "fake item".
80 : *
81 : * The `char' following the hash value encode the item name for true items.
82 : * For fake items, they contain the pointer to the first true item of the
83 : * corresponding link list (suitably aligned).
84 : *
85 : * There are HTT_NUM_TREES trees; the items are sorted among trees by the
86 : * lest significant bits of their hash value.
87 : */
88 :
89 0 : static void internal_init(HTT *htt, void (*deldata)(void *), int reduced)
90 : {
91 0 : htt->deldata = deldata;
92 0 : if (reduced) {
93 0 : HTT2 *htt2 = (HTT2 *)htt;
94 :
95 0 : htt2->tree[0] = htt2->tree[1] = NULL;
96 : } else {
97 : unsigned u;
98 :
99 0 : for (u = 0; u < HTT_NUM_TREES; u ++) htt->tree[u] = NULL;
100 : }
101 0 : }
102 :
103 : /* see nhash.h */
104 0 : void HTT_init(HTT *htt, void (*deldata)(void *))
105 : {
106 0 : internal_init(htt, deldata, 0);
107 0 : }
108 :
109 : /* see nhash.h */
110 0 : void HTT2_init(HTT2 *htt, void (*deldata)(void *))
111 : {
112 0 : internal_init((HTT *)htt, deldata, 1);
113 0 : }
114 :
115 : #define PTR_SHIFT (sizeof(hash_item_header *) * \
116 : ((sizeof(unsigned) + sizeof(hash_item_header *) - 1) / \
117 : sizeof(hash_item_header *)))
118 :
119 : #define TREE(u) (*(reduced ? ((HTT2 *)htt)->tree + ((u) & 1) \
120 : : htt->tree + ((u) & (HTT_NUM_TREES - 1))))
121 :
122 : /*
123 : * Find a node for the given hash value. If `father' is not NULL, fill
124 : * `*father' with a pointer to the node's father.
125 : * If the return value is NULL, then no existing node was found; if `*father'
126 : * is also NULL, the tree is empty. If the return value is not NULL but
127 : * `*father' is NULL, then the found node is the tree root.
128 : *
129 : * If `father' is not NULL, then `*leftson' is filled with 1 if the node
130 : * was looked for as the father left son, 0 otherwise.
131 : */
132 0 : static hash_item_header *find_node(HTT *htt, unsigned u,
133 : hash_item_header **father, int *leftson, int reduced)
134 : {
135 0 : hash_item_header *node = TREE(u);
136 0 : hash_item_header *nodef = NULL;
137 : int ls;
138 :
139 0 : u &= ~1U;
140 0 : while (node != NULL) {
141 0 : unsigned v = *(unsigned *)(node->ident);
142 0 : unsigned w = v & ~1U;
143 :
144 0 : if (u == w) break;
145 0 : nodef = node;
146 0 : if (u < w) {
147 0 : node = node->left;
148 0 : ls = 1;
149 : } else {
150 0 : node = node->right;
151 0 : ls = 0;
152 : }
153 : }
154 0 : if (father != NULL) {
155 0 : *father = nodef;
156 0 : *leftson = ls;
157 : }
158 0 : return node;
159 : }
160 :
161 0 : static void *internal_get(HTT *htt, char *name, int reduced)
162 : {
163 0 : unsigned u = hash_string(name), v;
164 0 : hash_item_header *node = find_node(htt, u, NULL, NULL, reduced);
165 :
166 0 : if (node == NULL) return NULL;
167 0 : v = *(unsigned *)(node->ident);
168 0 : if ((v & 1U) == 0) {
169 0 : return (strcmp(HASH_ITEM_NAME(node), name) == 0) ? node : NULL;
170 : }
171 0 : node = *(hash_item_header **)(node->ident + PTR_SHIFT);
172 0 : while (node != NULL) {
173 0 : if (strcmp(HASH_ITEM_NAME(node), name) == 0) return node;
174 0 : node = node->left;
175 : }
176 0 : return NULL;
177 : }
178 :
179 : /* see nhash.h */
180 0 : void *HTT_get(HTT *htt, char *name)
181 : {
182 0 : return internal_get(htt, name, 0);
183 : }
184 :
185 : /* see nhash.h */
186 0 : void *HTT2_get(HTT2 *htt, char *name)
187 : {
188 0 : return internal_get((HTT *)htt, name, 1);
189 : }
190 :
191 : /*
192 : * Make an item identifier from its name and its hash value.
193 : */
194 0 : static char *make_ident(char *name, unsigned u)
195 : {
196 0 : size_t n = strlen(name) + 1;
197 0 : char *ident = getmem(n + sizeof(unsigned));
198 :
199 0 : *(unsigned *)ident = u & ~1U;
200 0 : memcpy(ident + sizeof(unsigned), name, n);
201 0 : return ident;
202 : }
203 :
204 : /*
205 : * Make an identifier for a fake item, pointing to a true item.
206 : */
207 0 : static char *make_fake_ident(unsigned u, hash_item_header *next)
208 : {
209 0 : char *ident = getmem(PTR_SHIFT + sizeof(hash_item_header *));
210 :
211 0 : *(unsigned *)ident = u | 1U;
212 0 : *(hash_item_header **)(ident + PTR_SHIFT) = next;
213 0 : return ident;
214 : }
215 :
216 : /*
217 : * Adding an item is straightforward:
218 : * 1. look for its emplacement
219 : * 2. if no node is found, use the item as a new node and link it to the tree
220 : * 3. if a node is found:
221 : * 3.1. if the node is real, check for name inequality, then create a
222 : * fake node and assemble the two-element linked list
223 : * 3.2. if the node is fake, look for the name in the list; if not found,
224 : * add the node at the list end
225 : */
226 0 : static void *internal_put(HTT *htt, void *item, char *name, int reduced)
227 : {
228 0 : unsigned u = hash_string(name), v;
229 : int ls;
230 : hash_item_header *father;
231 0 : hash_item_header *node = find_node(htt, u, &father, &ls, reduced);
232 0 : hash_item_header *itemg = item, *pnode;
233 :
234 0 : if (node == NULL) {
235 0 : itemg->left = itemg->right = NULL;
236 0 : itemg->ident = make_ident(name, u);
237 0 : if (father == NULL) {
238 0 : TREE(u) = itemg;
239 0 : } else if (ls) {
240 0 : father->left = itemg;
241 : } else {
242 0 : father->right = itemg;
243 : }
244 0 : return NULL;
245 : }
246 0 : v = *(unsigned *)(node->ident);
247 0 : if ((v & 1U) == 0) {
248 0 : if (strcmp(HASH_ITEM_NAME(node), name) == 0)
249 0 : return node;
250 0 : pnode = getmem(sizeof *pnode);
251 0 : pnode->left = node->left;
252 0 : pnode->right = node->right;
253 0 : pnode->ident = make_fake_ident(u, node);
254 0 : node->left = itemg;
255 0 : node->right = NULL;
256 0 : itemg->left = itemg->right = NULL;
257 0 : itemg->ident = make_ident(name, u);
258 0 : if (father == NULL) {
259 0 : TREE(u) = pnode;
260 0 : } else if (ls) {
261 0 : father->left = pnode;
262 : } else {
263 0 : father->right = pnode;
264 : }
265 0 : return NULL;
266 : }
267 0 : node = *(hash_item_header **)(node->ident + PTR_SHIFT);
268 0 : while (node != NULL) {
269 0 : if (strcmp(HASH_ITEM_NAME(node), name) == 0) return node;
270 0 : pnode = node;
271 0 : node = node->left;
272 : }
273 0 : itemg->left = itemg->right = NULL;
274 0 : itemg->ident = make_ident(name, u);
275 0 : pnode->left = itemg;
276 0 : return NULL;
277 : }
278 :
279 : /* see nhash.h */
280 0 : void *HTT_put(HTT *htt, void *item, char *name)
281 : {
282 0 : return internal_put(htt, item, name, 0);
283 : }
284 :
285 : /* see nhash.h */
286 0 : void *HTT2_put(HTT2 *htt, void *item, char *name)
287 : {
288 0 : return internal_put((HTT *)htt, item, name, 1);
289 : }
290 :
291 : /*
292 : * A fake node subnode list has shrunk to one item only; make the
293 : * node real again.
294 : * fnode the fake node
295 : * node the last remaining node
296 : * father the fake node father (NULL if the fake node is root)
297 : * leftson 1 if the fake node is a left son, 0 otehrwise
298 : * u the hash value for this node
299 : */
300 0 : static void shrink_node(HTT *htt, hash_item_header *fnode,
301 : hash_item_header *node, hash_item_header *father, int leftson,
302 : unsigned u, int reduced)
303 : {
304 0 : node->left = fnode->left;
305 0 : node->right = fnode->right;
306 0 : if (father == NULL) {
307 0 : TREE(u) = node;
308 0 : } else if (leftson) {
309 0 : father->left = node;
310 : } else {
311 0 : father->right = node;
312 : }
313 0 : freemem(fnode->ident);
314 0 : freemem(fnode);
315 0 : }
316 :
317 : /*
318 : * Deletion algorithm:
319 : * 1. look for the node; if not found, exit
320 : * 2. if the node is real:
321 : * 2.1. check for equality; exit otherwise
322 : * 2.2. delete the node
323 : * 2.3. promote the leftest of right descendants or rightest of left
324 : * descendants
325 : * 3. if the node is fake:
326 : * 3.1. check the list items for equality; exit otherwise
327 : * 3.2. delete the correct item
328 : * 3.3. if there remains only one item, supress the fake node
329 : */
330 0 : static int internal_del(HTT *htt, char *name, int reduced)
331 : {
332 0 : unsigned u = hash_string(name), v;
333 : int ls;
334 : hash_item_header *father;
335 0 : hash_item_header *node = find_node(htt, u, &father, &ls, reduced);
336 : hash_item_header *pnode, *fnode, *znode;
337 : char *tmp;
338 :
339 0 : if (node == NULL) return 0;
340 0 : v = *(unsigned *)(node->ident);
341 0 : if ((v & 1U) != 0) {
342 0 : fnode = node;
343 0 : node = znode = *(hash_item_header **)(node->ident + PTR_SHIFT);
344 0 : pnode = NULL;
345 0 : while (node != NULL) {
346 0 : if (strcmp(HASH_ITEM_NAME(node), name) == 0) break;
347 0 : pnode = node;
348 0 : node = node->left;
349 : }
350 0 : if (node == NULL) return 0;
351 0 : if (pnode == NULL) {
352 : /*
353 : * We supress the first item in the list.
354 : */
355 0 : *(hash_item_header **)(fnode->ident + PTR_SHIFT) =
356 0 : node->left;
357 0 : if (node->left->left == NULL) {
358 0 : shrink_node(htt, fnode, node->left,
359 : father, ls, u, reduced);
360 : }
361 : } else {
362 0 : pnode->left = node->left;
363 0 : if (pnode->left == NULL && znode == pnode) {
364 0 : shrink_node(htt, fnode, pnode,
365 : father, ls, u, reduced);
366 : }
367 : }
368 : } else {
369 0 : if (strcmp(HASH_ITEM_NAME(node), name) != 0) return 0;
370 0 : if (node->left != NULL) {
371 0 : for (znode = node, pnode = node->left; pnode->right;
372 0 : znode = pnode, pnode = pnode->right);
373 0 : if (znode != node) {
374 0 : znode->right = pnode->left;
375 0 : pnode->left = node->left;
376 : }
377 0 : pnode->right = node->right;
378 0 : } else if (node->right != NULL) {
379 0 : for (znode = node, pnode = node->right; pnode->left;
380 0 : znode = pnode, pnode = pnode->left);
381 0 : if (znode != node) {
382 0 : znode->left = pnode->right;
383 0 : pnode->right = node->right;
384 : }
385 0 : pnode->left = node->left;
386 0 : } else pnode = NULL;
387 0 : if (father == NULL) {
388 0 : TREE(u) = pnode;
389 0 : } else if (ls) {
390 0 : father->left = pnode;
391 : } else {
392 0 : father->right = pnode;
393 : }
394 : }
395 0 : tmp = node->ident;
396 0 : htt->deldata(node);
397 0 : freemem(tmp);
398 0 : return 1;
399 : }
400 :
401 : /* see nhash.h */
402 0 : int HTT_del(HTT *htt, char *name)
403 : {
404 0 : return internal_del(htt, name, 0);
405 : }
406 :
407 : /* see nhash.h */
408 0 : int HTT2_del(HTT2 *htt, char *name)
409 : {
410 0 : return internal_del((HTT *)htt, name, 1);
411 : }
412 :
413 : /*
414 : * Apply `action()' on all nodes of the tree whose root is given as
415 : * parameter `node'. If `wipe' is non-zero, the nodes are removed
416 : * from memory.
417 : */
418 0 : static void scan_node(hash_item_header *node, void (*action)(void *), int wipe)
419 : {
420 : unsigned v;
421 :
422 0 : if (node == NULL) return;
423 0 : scan_node(node->left, action, wipe);
424 0 : scan_node(node->right, action, wipe);
425 0 : v = *(unsigned *)(node->ident);
426 0 : if ((v & 1U) != 0) {
427 : hash_item_header *pnode, *nnode;
428 :
429 0 : for (pnode = *(hash_item_header **)(node->ident + PTR_SHIFT);
430 0 : pnode != NULL; pnode = nnode) {
431 0 : char *tmp = pnode->ident;
432 :
433 0 : nnode = pnode->left;
434 0 : action(pnode);
435 0 : if (wipe) freemem(tmp);
436 : }
437 0 : if (wipe) {
438 0 : freemem(node->ident);
439 0 : freemem(node);
440 : }
441 : } else {
442 0 : char *tmp = node->ident;
443 :
444 0 : action(node);
445 0 : if (wipe) freemem(tmp);
446 : }
447 : }
448 :
449 : /* see nhash.h */
450 0 : void HTT_scan(HTT *htt, void (*action)(void *))
451 : {
452 : unsigned u;
453 :
454 0 : for (u = 0; u < HTT_NUM_TREES; u ++) {
455 0 : scan_node(htt->tree[u], action, 0);
456 : }
457 0 : }
458 :
459 : /* see nhash.h */
460 0 : void HTT2_scan(HTT2 *htt, void (*action)(void *))
461 : {
462 0 : scan_node(htt->tree[0], action, 0);
463 0 : scan_node(htt->tree[1], action, 0);
464 0 : }
465 :
466 : /* see nhash.h */
467 0 : void HTT_kill(HTT *htt)
468 : {
469 : unsigned u;
470 :
471 0 : for (u = 0; u < HTT_NUM_TREES; u ++) {
472 0 : scan_node(htt->tree[u], htt->deldata, 1);
473 : }
474 0 : }
475 :
476 : /* see nhash.h */
477 0 : void HTT2_kill(HTT2 *htt)
478 : {
479 0 : scan_node(htt->tree[0], htt->deldata, 1);
480 0 : scan_node(htt->tree[1], htt->deldata, 1);
481 0 : }
|
