Bug Summary

File:workdir/unxlngi6.pro/CustomTarget/ucpp/source/nhash.c
Location:line 156, column 3
Description:Assigned value is garbage or undefined

Annotated 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 */
44static unsigned hash_string(char *name)
45{
46 unsigned h = 0;
47
48 for (h = 0; *name; name ++) {
3
←
Loop condition is false. Execution continues on line 61
→
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
89static 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 */
104void HTT_init(HTT *htt, void (*deldata)(void *))
105{
106 internal_init(htt, deldata, 0);
107}
108
109/* see nhash.h */
110void 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 */
132static 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))));
6
←
Within the expansion of the macro 'TREE':
→
136 hash_item_header *nodef = NULL((void*)0);
137 int ls;
138
139 u &= ~1U;
140 while (node != NULL((void*)0)) {
7
←
Assuming 'node' is equal to null
→
8
←
Loop condition is false. Execution continues on line 154
→
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)) {
9
←
Taking true branch
→
155 *father = nodef;
156 *leftson = ls;
10
←
Assigned value is garbage or undefined
157 }
158 return node;
159}
160
161static 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 */
180void *HTT_get(HTT *htt, char *name)
181{
182 return internal_get(htt, name, 0);
183}
184
185/* see nhash.h */
186void *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 */
194static 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 */
207static 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 */
226static 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 */
280void *HTT_put(HTT *htt, void *item, char *name)
281{
282 return internal_put(htt, item, name, 0);
283}
284
285/* see nhash.h */
286void *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 */
300static 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 */
330static int internal_del(HTT *htt, char *name, int reduced)
331{
332 unsigned u = hash_string(name), v;
2
←
Calling 'hash_string'
→
4
←
Returning from 'hash_string'
→
333 int ls;
334 hash_item_header *father;
335 hash_item_header *node = find_node(htt, u, &father, &ls, reduced);
5
←
Calling 'find_node'
→
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 */
402int HTT_del(HTT *htt, char *name)
403{
404 return internal_del(htt, name, 0);
405}
406
407/* see nhash.h */
408int HTT2_del(HTT2 *htt, char *name)
409{
410 return internal_del((HTT *)htt, name, 1);
1
Calling 'internal_del'
→
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 */
418static 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 */
450void 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 */
460void 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 */
467void 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 */
477void HTT2_kill(HTT2 *htt)
478{
479 scan_node(htt->tree[0], htt->deldata, 1);
480 scan_node(htt->tree[1], htt->deldata, 1);
481}