File: | workdir/unxlngi6.pro/CustomTarget/ucpp/source/nhash.c |
Location: | line 156, column 3 |
Description: | Assigned value is garbage or undefined |
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 | static unsigned hash_string(char *name) | |||
45 | { | |||
46 | unsigned h = 0; | |||
47 | ||||
48 | for (h = 0; *name; name ++) { | |||
49 | unsigned g; | |||
50 | ||||
51 | h = (h << 4) + *(unsigned char *)name; | |||
52 | #if UINT_MAX(2147483647 *2U +1U) >= 0xffffffffU | |||
53 | g = h & 0xF0000000U; | |||
54 | h ^= (g >> 24); | |||
55 | #else | |||
56 | g = h & 0xF000U; | |||
57 | h ^= (g >> 12); | |||
58 | #endif | |||
59 | h &= ~g; | |||
60 | } | |||
61 | 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 | static void internal_init(HTT *htt, void (*deldata)(void *), int reduced) | |||
90 | { | |||
91 | htt->deldata = deldata; | |||
92 | if (reduced) { | |||
93 | HTT2 *htt2 = (HTT2 *)htt; | |||
94 | ||||
95 | htt2->tree[0] = htt2->tree[1] = NULL((void*)0); | |||
96 | } else { | |||
97 | unsigned u; | |||
98 | ||||
99 | for (u = 0; u < HTT_NUM_TREES128; u ++) htt->tree[u] = NULL((void*)0); | |||
100 | } | |||
101 | } | |||
102 | ||||
103 | /* see nhash.h */ | |||
104 | void HTT_init(HTT *htt, void (*deldata)(void *)) | |||
105 | { | |||
106 | internal_init(htt, deldata, 0); | |||
107 | } | |||
108 | ||||
109 | /* see nhash.h */ | |||
110 | void HTT2_init(HTT2 *htt, void (*deldata)(void *)) | |||
111 | { | |||
112 | internal_init((HTT *)htt, deldata, 1); | |||
113 | } | |||
114 | ||||
115 | #define PTR_SHIFT(sizeof(hash_item_header *) * ((sizeof(unsigned) + sizeof(hash_item_header *) - 1) / sizeof(hash_item_header *))) (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) : htt-> tree + ((u) & (128 - 1)))) (*(reduced ? ((HTT2 *)htt)->tree + ((u) & 1) \ | |||
120 | : htt->tree + ((u) & (HTT_NUM_TREES128 - 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 | static hash_item_header *find_node(HTT *htt, unsigned u, | |||
133 | hash_item_header **father, int *leftson, int reduced) | |||
134 | { | |||
135 | hash_item_header *node = TREE(u)(*(reduced ? ((HTT2 *)htt)->tree + ((u) & 1) : htt-> tree + ((u) & (128 - 1)))); | |||
136 | hash_item_header *nodef = NULL((void*)0); | |||
137 | int ls; | |||
138 | ||||
139 | u &= ~1U; | |||
140 | while (node != NULL((void*)0)) { | |||
141 | unsigned v = *(unsigned *)(node->ident); | |||
142 | unsigned w = v & ~1U; | |||
143 | ||||
144 | if (u == w) break; | |||
145 | nodef = node; | |||
146 | if (u < w) { | |||
147 | node = node->left; | |||
148 | ls = 1; | |||
149 | } else { | |||
150 | node = node->right; | |||
151 | ls = 0; | |||
152 | } | |||
153 | } | |||
154 | if (father != NULL((void*)0)) { | |||
155 | *father = nodef; | |||
156 | *leftson = ls; | |||
| ||||
157 | } | |||
158 | return node; | |||
159 | } | |||
160 | ||||
161 | static void *internal_get(HTT *htt, char *name, int reduced) | |||
162 | { | |||
163 | unsigned u = hash_string(name), v; | |||
164 | hash_item_header *node = find_node(htt, u, NULL((void*)0), NULL((void*)0), reduced); | |||
165 | ||||
166 | if (node == NULL((void*)0)) return NULL((void*)0); | |||
167 | v = *(unsigned *)(node->ident); | |||
168 | if ((v & 1U) == 0) { | |||
169 | return (strcmp(HASH_ITEM_NAME(node)(((hash_item_header *)(node))->ident + sizeof(unsigned)), name) == 0) ? node : NULL((void*)0); | |||
170 | } | |||
171 | node = *(hash_item_header **)(node->ident + PTR_SHIFT(sizeof(hash_item_header *) * ((sizeof(unsigned) + sizeof(hash_item_header *) - 1) / sizeof(hash_item_header *)))); | |||
172 | while (node != NULL((void*)0)) { | |||
173 | if (strcmp(HASH_ITEM_NAME(node)(((hash_item_header *)(node))->ident + sizeof(unsigned)), name) == 0) return node; | |||
174 | node = node->left; | |||
175 | } | |||
176 | return NULL((void*)0); | |||
177 | } | |||
178 | ||||
179 | /* see nhash.h */ | |||
180 | void *HTT_get(HTT *htt, char *name) | |||
181 | { | |||
182 | return internal_get(htt, name, 0); | |||
183 | } | |||
184 | ||||
185 | /* see nhash.h */ | |||
186 | void *HTT2_get(HTT2 *htt, char *name) | |||
187 | { | |||
188 | return internal_get((HTT *)htt, name, 1); | |||
189 | } | |||
190 | ||||
191 | /* | |||
192 | * Make an item identifier from its name and its hash value. | |||
193 | */ | |||
194 | static char *make_ident(char *name, unsigned u) | |||
195 | { | |||
196 | size_t n = strlen(name) + 1; | |||
197 | char *ident = getmemmalloc(n + sizeof(unsigned)); | |||
198 | ||||
199 | *(unsigned *)ident = u & ~1U; | |||
200 | memcpy(ident + sizeof(unsigned), name, n); | |||
201 | return ident; | |||
202 | } | |||
203 | ||||
204 | /* | |||
205 | * Make an identifier for a fake item, pointing to a true item. | |||
206 | */ | |||
207 | static char *make_fake_ident(unsigned u, hash_item_header *next) | |||
208 | { | |||
209 | char *ident = getmemmalloc(PTR_SHIFT(sizeof(hash_item_header *) * ((sizeof(unsigned) + sizeof(hash_item_header *) - 1) / sizeof(hash_item_header *))) + sizeof(hash_item_header *)); | |||
210 | ||||
211 | *(unsigned *)ident = u | 1U; | |||
212 | *(hash_item_header **)(ident + PTR_SHIFT(sizeof(hash_item_header *) * ((sizeof(unsigned) + sizeof(hash_item_header *) - 1) / sizeof(hash_item_header *)))) = next; | |||
213 | 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 | static void *internal_put(HTT *htt, void *item, char *name, int reduced) | |||
227 | { | |||
228 | unsigned u = hash_string(name), v; | |||
229 | int ls; | |||
230 | hash_item_header *father; | |||
231 | hash_item_header *node = find_node(htt, u, &father, &ls, reduced); | |||
232 | hash_item_header *itemg = item, *pnode; | |||
233 | ||||
234 | if (node == NULL((void*)0)) { | |||
235 | itemg->left = itemg->right = NULL((void*)0); | |||
236 | itemg->ident = make_ident(name, u); | |||
237 | if (father == NULL((void*)0)) { | |||
238 | TREE(u)(*(reduced ? ((HTT2 *)htt)->tree + ((u) & 1) : htt-> tree + ((u) & (128 - 1)))) = itemg; | |||
239 | } else if (ls) { | |||
240 | father->left = itemg; | |||
241 | } else { | |||
242 | father->right = itemg; | |||
243 | } | |||
244 | return NULL((void*)0); | |||
245 | } | |||
246 | v = *(unsigned *)(node->ident); | |||
247 | if ((v & 1U) == 0) { | |||
248 | if (strcmp(HASH_ITEM_NAME(node)(((hash_item_header *)(node))->ident + sizeof(unsigned)), name) == 0) | |||
249 | return node; | |||
250 | pnode = getmemmalloc(sizeof *pnode); | |||
251 | pnode->left = node->left; | |||
252 | pnode->right = node->right; | |||
253 | pnode->ident = make_fake_ident(u, node); | |||
254 | node->left = itemg; | |||
255 | node->right = NULL((void*)0); | |||
256 | itemg->left = itemg->right = NULL((void*)0); | |||
257 | itemg->ident = make_ident(name, u); | |||
258 | if (father == NULL((void*)0)) { | |||
259 | TREE(u)(*(reduced ? ((HTT2 *)htt)->tree + ((u) & 1) : htt-> tree + ((u) & (128 - 1)))) = pnode; | |||
260 | } else if (ls) { | |||
261 | father->left = pnode; | |||
262 | } else { | |||
263 | father->right = pnode; | |||
264 | } | |||
265 | return NULL((void*)0); | |||
266 | } | |||
267 | node = *(hash_item_header **)(node->ident + PTR_SHIFT(sizeof(hash_item_header *) * ((sizeof(unsigned) + sizeof(hash_item_header *) - 1) / sizeof(hash_item_header *)))); | |||
268 | while (node != NULL((void*)0)) { | |||
269 | if (strcmp(HASH_ITEM_NAME(node)(((hash_item_header *)(node))->ident + sizeof(unsigned)), name) == 0) return node; | |||
270 | pnode = node; | |||
271 | node = node->left; | |||
272 | } | |||
273 | itemg->left = itemg->right = NULL((void*)0); | |||
274 | itemg->ident = make_ident(name, u); | |||
275 | pnode->left = itemg; | |||
276 | return NULL((void*)0); | |||
277 | } | |||
278 | ||||
279 | /* see nhash.h */ | |||
280 | void *HTT_put(HTT *htt, void *item, char *name) | |||
281 | { | |||
282 | return internal_put(htt, item, name, 0); | |||
283 | } | |||
284 | ||||
285 | /* see nhash.h */ | |||
286 | void *HTT2_put(HTT2 *htt, void *item, char *name) | |||
287 | { | |||
288 | 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 | 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 | node->left = fnode->left; | |||
305 | node->right = fnode->right; | |||
306 | if (father == NULL((void*)0)) { | |||
307 | TREE(u)(*(reduced ? ((HTT2 *)htt)->tree + ((u) & 1) : htt-> tree + ((u) & (128 - 1)))) = node; | |||
308 | } else if (leftson) { | |||
309 | father->left = node; | |||
310 | } else { | |||
311 | father->right = node; | |||
312 | } | |||
313 | freememfree(fnode->ident); | |||
314 | freememfree(fnode); | |||
315 | } | |||
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 | static int internal_del(HTT *htt, char *name, int reduced) | |||
331 | { | |||
332 | unsigned u = hash_string(name), v; | |||
333 | int ls; | |||
334 | hash_item_header *father; | |||
335 | hash_item_header *node = find_node(htt, u, &father, &ls, reduced); | |||
336 | hash_item_header *pnode, *fnode, *znode; | |||
337 | char *tmp; | |||
338 | ||||
339 | if (node == NULL((void*)0)) return 0; | |||
340 | v = *(unsigned *)(node->ident); | |||
341 | if ((v & 1U) != 0) { | |||
342 | fnode = node; | |||
343 | node = znode = *(hash_item_header **)(node->ident + PTR_SHIFT(sizeof(hash_item_header *) * ((sizeof(unsigned) + sizeof(hash_item_header *) - 1) / sizeof(hash_item_header *)))); | |||
344 | pnode = NULL((void*)0); | |||
345 | while (node != NULL((void*)0)) { | |||
346 | if (strcmp(HASH_ITEM_NAME(node)(((hash_item_header *)(node))->ident + sizeof(unsigned)), name) == 0) break; | |||
347 | pnode = node; | |||
348 | node = node->left; | |||
349 | } | |||
350 | if (node == NULL((void*)0)) return 0; | |||
351 | if (pnode == NULL((void*)0)) { | |||
352 | /* | |||
353 | * We supress the first item in the list. | |||
354 | */ | |||
355 | *(hash_item_header **)(fnode->ident + PTR_SHIFT(sizeof(hash_item_header *) * ((sizeof(unsigned) + sizeof(hash_item_header *) - 1) / sizeof(hash_item_header *)))) = | |||
356 | node->left; | |||
357 | if (node->left->left == NULL((void*)0)) { | |||
358 | shrink_node(htt, fnode, node->left, | |||
359 | father, ls, u, reduced); | |||
360 | } | |||
361 | } else { | |||
362 | pnode->left = node->left; | |||
363 | if (pnode->left == NULL((void*)0) && znode == pnode) { | |||
364 | shrink_node(htt, fnode, pnode, | |||
365 | father, ls, u, reduced); | |||
366 | } | |||
367 | } | |||
368 | } else { | |||
369 | if (strcmp(HASH_ITEM_NAME(node)(((hash_item_header *)(node))->ident + sizeof(unsigned)), name) != 0) return 0; | |||
370 | if (node->left != NULL((void*)0)) { | |||
371 | for (znode = node, pnode = node->left; pnode->right; | |||
372 | znode = pnode, pnode = pnode->right); | |||
373 | if (znode != node) { | |||
374 | znode->right = pnode->left; | |||
375 | pnode->left = node->left; | |||
376 | } | |||
377 | pnode->right = node->right; | |||
378 | } else if (node->right != NULL((void*)0)) { | |||
379 | for (znode = node, pnode = node->right; pnode->left; | |||
380 | znode = pnode, pnode = pnode->left); | |||
381 | if (znode != node) { | |||
382 | znode->left = pnode->right; | |||
383 | pnode->right = node->right; | |||
384 | } | |||
385 | pnode->left = node->left; | |||
386 | } else pnode = NULL((void*)0); | |||
387 | if (father == NULL((void*)0)) { | |||
388 | TREE(u)(*(reduced ? ((HTT2 *)htt)->tree + ((u) & 1) : htt-> tree + ((u) & (128 - 1)))) = pnode; | |||
389 | } else if (ls) { | |||
390 | father->left = pnode; | |||
391 | } else { | |||
392 | father->right = pnode; | |||
393 | } | |||
394 | } | |||
395 | tmp = node->ident; | |||
396 | htt->deldata(node); | |||
397 | freememfree(tmp); | |||
398 | return 1; | |||
399 | } | |||
400 | ||||
401 | /* see nhash.h */ | |||
402 | int HTT_del(HTT *htt, char *name) | |||
403 | { | |||
404 | return internal_del(htt, name, 0); | |||
405 | } | |||
406 | ||||
407 | /* see nhash.h */ | |||
408 | int HTT2_del(HTT2 *htt, char *name) | |||
409 | { | |||
410 | 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 | static void scan_node(hash_item_header *node, void (*action)(void *), int wipe) | |||
419 | { | |||
420 | unsigned v; | |||
421 | ||||
422 | if (node == NULL((void*)0)) return; | |||
423 | scan_node(node->left, action, wipe); | |||
424 | scan_node(node->right, action, wipe); | |||
425 | v = *(unsigned *)(node->ident); | |||
426 | if ((v & 1U) != 0) { | |||
427 | hash_item_header *pnode, *nnode; | |||
428 | ||||
429 | for (pnode = *(hash_item_header **)(node->ident + PTR_SHIFT(sizeof(hash_item_header *) * ((sizeof(unsigned) + sizeof(hash_item_header *) - 1) / sizeof(hash_item_header *)))); | |||
430 | pnode != NULL((void*)0); pnode = nnode) { | |||
431 | char *tmp = pnode->ident; | |||
432 | ||||
433 | nnode = pnode->left; | |||
434 | action(pnode); | |||
435 | if (wipe) freememfree(tmp); | |||
436 | } | |||
437 | if (wipe) { | |||
438 | freememfree(node->ident); | |||
439 | freememfree(node); | |||
440 | } | |||
441 | } else { | |||
442 | char *tmp = node->ident; | |||
443 | ||||
444 | action(node); | |||
445 | if (wipe) freememfree(tmp); | |||
446 | } | |||
447 | } | |||
448 | ||||
449 | /* see nhash.h */ | |||
450 | void HTT_scan(HTT *htt, void (*action)(void *)) | |||
451 | { | |||
452 | unsigned u; | |||
453 | ||||
454 | for (u = 0; u < HTT_NUM_TREES128; u ++) { | |||
455 | scan_node(htt->tree[u], action, 0); | |||
456 | } | |||
457 | } | |||
458 | ||||
459 | /* see nhash.h */ | |||
460 | void HTT2_scan(HTT2 *htt, void (*action)(void *)) | |||
461 | { | |||
462 | scan_node(htt->tree[0], action, 0); | |||
463 | scan_node(htt->tree[1], action, 0); | |||
464 | } | |||
465 | ||||
466 | /* see nhash.h */ | |||
467 | void HTT_kill(HTT *htt) | |||
468 | { | |||
469 | unsigned u; | |||
470 | ||||
471 | for (u = 0; u < HTT_NUM_TREES128; u ++) { | |||
472 | scan_node(htt->tree[u], htt->deldata, 1); | |||
473 | } | |||
474 | } | |||
475 | ||||
476 | /* see nhash.h */ | |||
477 | void HTT2_kill(HTT2 *htt) | |||
478 | { | |||
479 | scan_node(htt->tree[0], htt->deldata, 1); | |||
480 | scan_node(htt->tree[1], htt->deldata, 1); | |||
481 | } |