Bug Summary

File:bld/../dhash/dhash.c
Location:line 892, column 10
Description:Although the value stored to 'error' is used in the enclosing expression, the value is never actually read from 'error'

Annotated Source Code

1/*
2 Authors:
3 John Dennis <jdennis.redhat.com>
4 Esmond Pitt <ejp@ausmelb.oz.AU>
5
6 This implementation was based on a 3/7/1989 public domain submission
7 to comp.sources.misc by Esmond Pitt <ejp@ausmelb.oz.AU>.
8
9 Copyright (C) 2009 Red Hat
10
11 This program is free software; you can redistribute it and/or modify
12 it under the terms of the GNU Lesser General Public License as published by
13 the Free Software Foundation; either version 3 of the License, or
14 (at your option) any later version.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU Lesser General Public License for more details.
20
21 You should have received a copy of the GNU Lesser General Public License
22 along with this program. If not, see <http://www.gnu.org/licenses/>.
23*/
24
25/*****************************************************************************/
26/******************************** Documentation ******************************/
27/*****************************************************************************/
28
29/*
30 * See documentation in corresponding header file dhash.h.
31 *
32 * Compilation controls:
33 * DEBUG controls some informative traces, mainly for debugging.
34 * HASH_STATISTICS causes hash_accesses and hash_collisions to be maintained;
35 * when combined with DEBUG, these are displayed by hash_destroy().
36 *
37 */
38
39/*****************************************************************************/
40/******************************* Include Files *******************************/
41/*****************************************************************************/
42
43#include "config.h"
44#include <stdio.h>
45#include <string.h>
46#include <stdlib.h>
47#include <errno(*__errno_location ()).h>
48#include "dhash.h"
49
50/*****************************************************************************/
51/****************************** Internal Defines *****************************/
52/*****************************************************************************/
53
54#define PRIME_137 37
55#define PRIME_21048583 1048583
56
57#ifndef MIN
58 #define MIN(a,b)(((a) < (b)) ? (a) : (b)) (((a) < (b)) ? (a) : (b))
59#endif
60
61#ifndef MAX
62 #define MAX(a,b)(((a) > (b)) ? (a) : (b)) (((a) > (b)) ? (a) : (b))
63#endif
64
65#define halloc(table, size)table->halloc(size, table->halloc_pvt) table->halloc(size, table->halloc_pvt)size->halloc(table->halloc_pvt, size->halloc_pvt)
66#define hfree(table, ptr)table->hfree(ptr, table->halloc_pvt) table->hfree(ptr, table->halloc_pvt)ptr->hfree(table->halloc_pvt, ptr->halloc_pvt)
67#define hdelete_callback(table, type, entry)do { if (table->delete_callback) { table->delete_callback
(entry, type, table->delete_pvt); } } while(0)
do { \
68 if (table->delete_callback) { \
69 table->delete_callback(entry, type, table->delete_pvt); \
70 } \
71} while(0)
72
73/*****************************************************************************/
74/************************** Internal Type Definitions ************************/
75/*****************************************************************************/
76
77typedef struct element_t {
78 hash_entry_t entry;
79 struct element_t *next;
80} element_t, *segment_t;
81
82
83struct hash_table_str {
84 unsigned long p; /* Next bucket to be split */
85 unsigned long maxp; /* upper bound on p during expansion */
86 unsigned long entry_count; /* current # entries */
87 unsigned long bucket_count; /* current # buckets */
88 unsigned long segment_count; /* current # segments */
89 unsigned long min_load_factor;
90 unsigned long max_load_factor;
91 unsigned long directory_size;
92 unsigned int directory_size_shift;
93 unsigned long segment_size;
94 unsigned int segment_size_shift;
95 hash_delete_callback *delete_callback;
96 void *delete_pvt;
97 hash_alloc_func *halloc;
98 hash_free_func *hfree;
99 void *halloc_pvt;
100 segment_t **directory;
101#ifdef HASH_STATISTICS
102 hash_statistics_t statistics;
103#endif
104
105};
106
107typedef unsigned long address_t;
108
109typedef struct hash_keys_callback_data_t {
110 unsigned long index;
111 hash_key_t *keys;
112} hash_keys_callback_data_t;
113
114typedef struct hash_values_callback_data_t {
115 unsigned long index;
116 hash_value_t *values;
117} hash_values_callback_data_t;
118
119struct _hash_iter_context_t {
120 struct hash_iter_context_t iter;
121 hash_table_t *table;
122 unsigned long i, j;
123 segment_t *s;
124 element_t *p;
125};
126
127/*****************************************************************************/
128/********************** External Function Declarations *********************/
129/*****************************************************************************/
130
131/*****************************************************************************/
132/********************** Internal Function Declarations *********************/
133/*****************************************************************************/
134
135static address_t convert_key(hash_key_t *key);
136static address_t hash(hash_table_t *table, hash_key_t *key);
137static bool_Bool key_equal(hash_key_t *a, hash_key_t *b);
138static int contract_table(hash_table_t *table);
139static int expand_table(hash_table_t *table);
140static hash_entry_t *hash_iter_next(struct hash_iter_context_t *iter);
141
142/*****************************************************************************/
143/************************* External Global Variables ***********************/
144/*****************************************************************************/
145
146/*****************************************************************************/
147/************************* Internal Global Variables ***********************/
148/*****************************************************************************/
149
150#if DEBUG
151int debug_level = 1;
152#endif
153
154/*****************************************************************************/
155/*************************** Internal Functions ****************************/
156/*****************************************************************************/
157
158static void *sys_malloc_wrapper(size_t size, void *pvt)
159{
160 return malloc(size);
161}
162
163static void sys_free_wrapper(void *ptr, void *pvt)
164{
165 return free(ptr);
166}
167
168static address_t convert_key(hash_key_t *key)
169{
170 address_t h;
171 unsigned char *k;
172
173 switch(key->type) {
174 case HASH_KEY_ULONG:
175 h = key->ul;
176 break;
177 case HASH_KEY_STRING:
178 /* Convert string to integer */
179 for (h = 0, k = (unsigned char *) key->str; *k; k++)
180 h = h * PRIME_137 ^ (*k - ' ');
181 break;
182 default:
183 h = key->ul;
184 break;
185 }
186 return h;
187}
188
189static address_t hash(hash_table_t *table, hash_key_t *key)
190{
191 address_t h, address;
192
193 h = convert_key(key);
194 h %= PRIME_21048583;
195 address = h & (table->maxp-1); /* h % maxp */
196 if (address < table->p)
197 address = h & ((table->maxp << 1)-1); /* h % (2*table->maxp) */
198
199 return address;
200}
201
202static bool_Bool is_valid_key_type(hash_key_enum key_type)
203{
204 switch(key_type) {
205 case HASH_KEY_ULONG:
206 case HASH_KEY_STRING:
207 return true1;
208 default:
209 return false0;
210 }
211}
212
213static bool_Bool is_valid_value_type(hash_value_enum value_type)
214{
215 switch(value_type) {
216 case HASH_VALUE_UNDEF:
217 case HASH_VALUE_PTR:
218 case HASH_VALUE_INT:
219 case HASH_VALUE_UINT:
220 case HASH_VALUE_LONG:
221 case HASH_VALUE_ULONG:
222 case HASH_VALUE_FLOAT:
223 case HASH_VALUE_DOUBLE:
224 return true1;
225 default:
226 return false0;
227 }
228}
229
230static bool_Bool key_equal(hash_key_t *a, hash_key_t *b)
231{
232 if (a->type != b->type) return false0;
233
234 switch(a->type) {
235 case HASH_KEY_ULONG:
236 return (a->ul == b->ul);
237 case HASH_KEY_STRING:
238 return (strcmp(a->str, b->str) == 0);
239 }
240 return false0;
241}
242
243
244static int expand_table(hash_table_t *table)
245{
246 address_t new_address;
247 unsigned long old_segment_index, new_segment_index;
248 unsigned long old_segment_dir, new_segment_dir;
249 segment_t *old_segment, *new_segment;
250 element_t *current, **previous, **last_of_new;
251
252 if (table->bucket_count < (table->directory_size << table->segment_size_shift)) {
253#ifdef DEBUG
254 if (debug_level >= 2)
255 fprintf(stderrstderr, "expand_table on entry: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n",
256 table->bucket_count, table->segment_count, table->p, table->maxp);
257#endif
258#ifdef HASH_STATISTICS
259 table->statistics.table_expansions++;
260#endif
261
262 /*
263 * Locate the bucket to be split
264 */
265 old_segment_dir = table->p >> table->segment_size_shift;
266 old_segment = table->directory[old_segment_dir];
267 old_segment_index = table->p & (table->segment_size-1); /* p % segment_size */
268 /*
269 * Expand address space; if necessary create a new segment
270 */
271 new_address = table->maxp + table->p;
272 new_segment_dir = new_address >> table->segment_size_shift;
273 new_segment_index = new_address & (table->segment_size-1); /* new_address % segment_size */
274 if (new_segment_index == 0) {
275 table->directory[new_segment_dir] = (segment_t *)halloc(table, table->segment_size * sizeof(segment_t))table->halloc(table->segment_size * sizeof(segment_t), table
->halloc_pvt)
;
276 if (table->directory[new_segment_dir] == NULL((void*)0)) {
277 return HASH_ERROR_NO_MEMORY(-2000 + 3);
278 }
279 memset(table->directory[new_segment_dir], 0, table->segment_size * sizeof(segment_t));
280 table->segment_count++;
281 }
282 new_segment = table->directory[new_segment_dir];
283 /*
284 * Adjust state variables
285 */
286 table->p++;
287 if (table->p == table->maxp) {
288 table->maxp <<= 1; /* table->maxp *= 2 */
289 table->p = 0;
290 }
291 table->bucket_count++;
292 /*
293 * Relocate records to the new bucket
294 */
295 previous = &old_segment[old_segment_index];
296 current = *previous;
297 last_of_new = &new_segment[new_segment_index];
298 *last_of_new = NULL((void*)0);
299 while (current != NULL((void*)0)) {
300 if (hash(table, &current->entry.key) == new_address) {
301 /*
302 * Attach it to the end of the new chain
303 */
304 *last_of_new = current;
305 /*
306 * Remove it from old chain
307 */
308 *previous = current->next;
309 last_of_new = &current->next;
310 current = current->next;
311 *last_of_new = NULL((void*)0);
312 } else {
313 /*
314 * leave it on the old chain
315 */
316 previous = &current->next;
317 current = current->next;
318 }
319 }
320#ifdef DEBUG
321 if (debug_level >= 2)
322 fprintf(stderrstderr, "expand_table on exit: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n",
323 table->bucket_count, table->segment_count, table->p, table->maxp);
324#endif
325 }
326 return HASH_SUCCESS0;
327}
328
329static int contract_table(hash_table_t *table)
330{
331 address_t new_address, old_address;
332 unsigned long old_segment_index, new_segment_index;
333 unsigned long old_segment_dir, new_segment_dir;
334 segment_t *old_segment, *new_segment;
335 element_t *current;
336
337 if ((table->bucket_count > table->segment_size) && (table->segment_count > 1)) {
338#ifdef DEBUG
339 if (debug_level >= 2)
340 fprintf(stderrstderr, "contract_table on entry: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n",
341 table->bucket_count, table->segment_count, table->p, table->maxp);
342#endif
343
344#ifdef HASH_STATISTICS
345 table->statistics.table_contractions++;
346#endif
347 /*
348 * Locate the bucket to be merged with the last bucket
349 */
350 old_address = table->bucket_count - 1;
351 old_segment_dir = old_address >> table->segment_size_shift;
352 old_segment = table->directory[old_segment_dir];
353 old_segment_index = old_address & (table->segment_size-1); /* old_address % segment_size */
354
355 /*
356 * Adjust state variables
357 */
358 if (table->p > 0) {
359 table->p--;
360 } else {
361 table->maxp >>= 1;
362 table->p = table->maxp - 1;
363 }
364 table->bucket_count--;
365
366 /*
367 * Find the last bucket to merge back
368 */
369 if((current = old_segment[old_segment_index]) != NULL((void*)0)) {
370 new_address = hash(table, &old_segment[old_segment_index]->entry.key);
371 new_segment_dir = new_address >> table->segment_size_shift;
372 new_segment_index = new_address & (table->segment_size-1); /* new_address % segment_size */
373 new_segment = table->directory[new_segment_dir];
374
375 /*
376 * Relocate records to the new bucket by splicing the two chains
377 * together by inserting the old chain at the head of the new chain.
378 * First find the end of the old chain, then set its next pointer to
379 * point to the head of the new chain, set the head of the new chain to
380 * point to the old chain, then finally set the head of the old chain to
381 * NULL.
382 */
383
384 while (current->next != NULL((void*)0)) {
385 current = current->next;
386 }
387
388 current->next = new_segment[new_segment_index];
389 new_segment[new_segment_index] = old_segment[old_segment_index];
390 old_segment[old_segment_index] = NULL((void*)0);
391 }
392 /*
393 * If we have removed the last of the chains in this segment then free the
394 * segment since its no longer in use.
395 */
396 if (old_segment_index == 0) {
397 table->segment_count--;
398 hfree(table, table->directory[old_segment_dir])table->hfree(table->directory[old_segment_dir], table->
halloc_pvt)
;
399 }
400
401#ifdef DEBUG
402 if (debug_level >= 2)
403 fprintf(stderrstderr, "contract_table on exit: bucket_count=%lu, segment_count=%lu p=%lu maxp=%lu\n",
404 table->bucket_count, table->segment_count, table->p, table->maxp);
405#endif
406
407 }
408 return HASH_SUCCESS0;
409}
410
411static int lookup(hash_table_t *table, hash_key_t *key, element_t **element_arg, segment_t **chain_arg)
412{
413 address_t h;
414 segment_t *current_segment;
415 unsigned long segment_index, segment_dir;
416 segment_t *chain, element;
417
418 *element_arg = NULL((void*)0);
419 *chain_arg = NULL((void*)0);
420
421 if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5);
422
423#ifdef HASH_STATISTICS
424 table->statistics.hash_accesses++;
425#endif
426 h = hash(table, key);
427 segment_dir = h >> table->segment_size_shift;
428 segment_index = h & (table->segment_size-1); /* h % segment_size */
429 /*
430 * valid segment ensured by hash()
431 */
432 current_segment = table->directory[segment_dir];
433
434#ifdef DEBUG
435 if (debug_level >= 3)
436 fprintf(stderrstderr, "lookup: h=%lu, segment_dir=%lu, segment_index=%lu current_segment=%p\n",
437 h, segment_dir, segment_index, current_segment);
438#endif
439
440 if (current_segment == NULL((void*)0)) return EFAULT14;
441 chain = &current_segment[segment_index];
442 element = *chain;
443 /*
444 * Follow collision chain
445 */
446 while (element != NULL((void*)0) && !key_equal(&element->entry.key, key)) {
447 chain = &element->next;
448 element = *chain;
449#ifdef HASH_STATISTICS
450 table->statistics.hash_collisions++;
451#endif
452 }
453 *element_arg = element;
454 *chain_arg = chain;
455
456 return HASH_SUCCESS0;
457}
458
459static bool_Bool hash_keys_callback(hash_entry_t *item, void *user_data)
460{
461 hash_keys_callback_data_t *data = (hash_keys_callback_data_t *)user_data;
462
463 data->keys[data->index++] = item->key;
464 return true1;
465}
466
467static bool_Bool hash_values_callback(hash_entry_t *item, void *user_data)
468{
469 hash_values_callback_data_t *data = (hash_values_callback_data_t *)user_data;
470
471 data->values[data->index++] = item->value;
472 return true1;
473}
474
475/*****************************************************************************/
476/**************************** Exported Functions ***************************/
477/*****************************************************************************/
478
479const char* hash_error_string(int error)
480{
481 switch(error) {
482 case HASH_SUCCESS0: return "Success";
483 case HASH_ERROR_BAD_KEY_TYPE(-2000 + 1): return "Bad key type";
484 case HASH_ERROR_BAD_VALUE_TYPE(-2000 + 2): return "Bad value type";
485 case HASH_ERROR_NO_MEMORY(-2000 + 3): return "No memory";
486 case HASH_ERROR_KEY_NOT_FOUND(-2000 + 4): return "Key not found";
487 case HASH_ERROR_BAD_TABLE(-2000 + 5): return "Bad table";
488 }
489 return NULL((void*)0);
490}
491
492
493int hash_create(unsigned long count, hash_table_t **tbl,
494 hash_delete_callback *delete_callback,
495 void *delete_private_data)
496{
497 return hash_create_ex(count, tbl, 0, 0, 0, 0,
498 NULL((void*)0), NULL((void*)0), NULL((void*)0),
499 delete_callback,
500 delete_private_data);
501}
502
503int hash_create_ex(unsigned long count, hash_table_t **tbl,
504 unsigned int directory_bits,
505 unsigned int segment_bits,
506 unsigned long min_load_factor,
507 unsigned long max_load_factor,
508 hash_alloc_func *alloc_func,
509 hash_free_func *free_func,
510 void *alloc_private_data,
511 hash_delete_callback *delete_callback,
512 void *delete_private_data) {
513 unsigned long i;
514 unsigned int n_addr_bits, requested_bits;
515 unsigned int requested_directory_bits;
516 unsigned int requested_segment_bits;
517 address_t addr;
518 hash_table_t *table = NULL((void*)0);
519
520 /* Initialize to NULL in case of an early return due to an error */
521 *tbl = NULL((void*)0);
522
523 if (alloc_func == NULL((void*)0)) alloc_func = sys_malloc_wrapper;
524 if (free_func == NULL((void*)0)) free_func = sys_free_wrapper;
525
526 /* Compute directory and segment parameters */
527
528 /* compute power of 2 >= count; it's the number of requested buckets */
529 if (count > 1) {
530 for (requested_bits = 0; (1 << requested_bits) < count; requested_bits++);
531 } else {
532 requested_bits = 1;
533 }
534
535 /*
536 * If caller didn't specify directory & segment allocation then
537 * compute it from the requested count.
538 */
539 if (directory_bits == 0 || segment_bits == 0) {
540 /* Equally divide buckets between the directory and segments */
541 requested_directory_bits = MAX(requested_bits >> 1, 1)(((requested_bits >> 1) > (1)) ? (requested_bits >>
1) : (1))
;
542 requested_segment_bits = MAX(requested_bits - requested_directory_bits, 1)(((requested_bits - requested_directory_bits) > (1)) ? (requested_bits
- requested_directory_bits) : (1))
;
543
544 /* If the requested count wasn't specified pick a default */
545 if (count == 0) {
546 directory_bits = MAX(requested_directory_bits, HASH_DEFAULT_DIRECTORY_BITS)(((requested_directory_bits) > (5)) ? (requested_directory_bits
) : (5))
;
547 segment_bits = MAX(requested_segment_bits, HASH_DEFAULT_SEGMENT_BITS)(((requested_segment_bits) > (5)) ? (requested_segment_bits
) : (5))
;
548 } else {
549 directory_bits = requested_directory_bits;
550 segment_bits = requested_segment_bits;
551 }
552 }
553
554 for (addr = ~0, n_addr_bits = 0; addr; addr >>= 1, n_addr_bits++);
555
556 if (directory_bits + segment_bits > n_addr_bits) return EINVAL22;
557
558 table = (hash_table_t *)alloc_func(sizeof(hash_table_t),
559 alloc_private_data);
560 if (table == NULL((void*)0)) {
561 return HASH_ERROR_NO_MEMORY(-2000 + 3);
562 }
563 memset(table, 0, sizeof(hash_table_t));
564 table->halloc = alloc_func;
565 table->hfree = free_func;
566 table->halloc_pvt = alloc_private_data;
567
568 table->directory_size_shift = directory_bits;
569 table->directory_size = directory_bits ? 1 << directory_bits : 0;
570
571 table->segment_size_shift = segment_bits;
572 table->segment_size = segment_bits ? 1 << segment_bits : 0;
573
574 /* Allocate directory */
575 table->directory = (segment_t **)halloc(table, table->directory_size * sizeof(segment_t *))table->halloc(table->directory_size * sizeof(segment_t *
), table->halloc_pvt)
;
576 if (table->directory == NULL((void*)0)) {
577 hash_destroy(table);
578 return HASH_ERROR_NO_MEMORY(-2000 + 3);
579 }
580 memset(table->directory, 0, table->directory_size * sizeof(segment_t *));
581
582 /*
583 * If one wanted to pre-allocate all the buckets necessary to meet the needs
584 * of the requested count it would be done like this:
585 *
586 * table->segment_count = MIN((count + table->segment_size-1) / table->segment_size,
587 * table->directory_size);
588 *
589 * But with dynamic hash tables there is little point to this, the whole idea is to
590 * allow the table to grow/shrink dynamically, therefore we start with just one
591 * segment of buckets, the minimum necessary.
592 */
593 table->segment_count = 1;
594 table->p = 0;
595 table->entry_count = 0;
596 table->delete_callback = delete_callback;
597 table->delete_pvt = delete_private_data;
598
599 /*
600 * Allocate initial segments of buckets
601 */
602 for (i = 0; i < table->segment_count; i++) {
603 table->directory[i] = (segment_t *)halloc(table, table->segment_size * sizeof(segment_t))table->halloc(table->segment_size * sizeof(segment_t), table
->halloc_pvt)
;
604 if (table->directory[i] == NULL((void*)0)) {
605 hash_destroy(table);
606 return HASH_ERROR_NO_MEMORY(-2000 + 3);
607 }
608 memset(table->directory[i], 0, table->segment_size * sizeof(segment_t));
609 }
610 table->bucket_count = table->segment_count << table->segment_size_shift;
611 table->maxp = table->bucket_count;
612 table->min_load_factor = min_load_factor == 0 ? HASH_DEFAULT_MIN_LOAD_FACTOR1 : min_load_factor;
613 table->max_load_factor = max_load_factor == 0 ? HASH_DEFAULT_MAX_LOAD_FACTOR5 : max_load_factor;
614
615#if DEBUG
616 if (debug_level >= 1) {
617 fprintf(stderrstderr, "hash_create_ex: count=%lu available buckets=%lu bucket_count=%lu maxp=%lu\n",
618 count, table->directory_size*table->segment_size, table->bucket_count, table->maxp);
619 fprintf(stderrstderr, " directory_bits=%u segment_bits=%u requested_bits=%u\n",
620 directory_bits, segment_bits, requested_bits);
621 fprintf(stderrstderr, " directory_size=%lu segment_size=%lu segment_count=%lu\n",
622 table->directory_size, table->segment_size, table->segment_count);
623 fprintf(stderrstderr, " min_load_factor=%lu max_load_factor=%lu\n",
624 table->min_load_factor, table->max_load_factor);
625 }
626#endif
627#ifdef HASH_STATISTICS
628 memset(&table->statistics, 0, sizeof(table->statistics));
629#endif
630
631 *tbl = table;
632 return HASH_SUCCESS0;
633}
634
635#ifdef HASH_STATISTICS
636int hash_get_statistics(hash_table_t *table, hash_statistics_t *statistics)
637{
638 if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5);
639 if (!statistics) return EINVAL22;
640
641 *statistics = table->statistics;
642
643 return HASH_SUCCESS0;
644}
645#endif
646
647int hash_destroy(hash_table_t *table)
648{
649 unsigned long i, j;
650 segment_t *s;
651 element_t *p, *q;
652
653 if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5);
654
655 if (table != NULL((void*)0)) {
656 if (table->directory) {
657 for (i = 0; i < table->segment_count; i++) {
658 /* test probably unnecessary */
659 if ((s = table->directory[i]) != NULL((void*)0)) {
660 for (j = 0; j < table->segment_size; j++) {
661 p = s[j];
662 while (p != NULL((void*)0)) {
663 q = p->next;
664 hdelete_callback(table, HASH_TABLE_DESTROY, &p->entry)do { if (table->delete_callback) { table->delete_callback
(&p->entry, HASH_TABLE_DESTROY, table->delete_pvt);
} } while(0)
;
665 if (p->entry.key.type == HASH_KEY_STRING) {
666 hfree(table, (char *)p->entry.key.str)table->hfree((char *)p->entry.key.str, table->halloc_pvt
)
;
667 }
668 hfree(table, (char *)p)table->hfree((char *)p, table->halloc_pvt);
669 p = q;
670 }
671 }
672 hfree(table, s)table->hfree(s, table->halloc_pvt);
673 }
674 }
675 hfree(table, table->directory)table->hfree(table->directory, table->halloc_pvt);
676 }
677 hfree(table, table)table->hfree(table, table->halloc_pvt);
678 table = NULL((void*)0);
679 }
680 return HASH_SUCCESS0;
681}
682
683int hash_iterate(hash_table_t *table, hash_iterate_callback callback, void *user_data)
684{
685 unsigned long i, j;
686 segment_t *s;
687 element_t *p;
688
689 if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5);
690
691 if (table != NULL((void*)0)) {
692 for (i = 0; i < table->segment_count; i++) {
693 /* test probably unnecessary */
694 if ((s = table->directory[i]) != NULL((void*)0)) {
695 for (j = 0; j < table->segment_size; j++) {
696 p = s[j];
697 while (p != NULL((void*)0)) {
698 if(!(*callback)(&p->entry, user_data)) return HASH_SUCCESS0;
699 p = p->next;
700 }
701 }
702 }
703 }
704 }
705 return HASH_SUCCESS0;
706}
707
708static hash_entry_t *hash_iter_next(struct hash_iter_context_t *iter_arg)
709{
710 struct _hash_iter_context_t *iter = (struct _hash_iter_context_t *) iter_arg;
711 hash_entry_t *entry;
712
713 if (iter->table == NULL((void*)0)) return NULL((void*)0);
714 goto state_3a;
715
716 state_1:
717 iter->i++;
718 if(iter->i >= iter->table->segment_count) return NULL((void*)0);
719 /* test probably unnecessary */
720 iter->s = iter->table->directory[iter->i];
721 if (iter->s == NULL((void*)0)) goto state_1;
722 iter->j = 0;
723 state_2:
724 if (iter->j >= iter->table->segment_size) goto state_1;
725 iter->p = iter->s[iter->j];
726 state_3a:
727 if (iter->p == NULL((void*)0)) goto state_3b;
728 entry = &iter->p->entry;
729 iter->p = iter->p->next;
730 return entry;
731 state_3b:
732 iter->j++;
733 goto state_2;
734
735 /* Should never reach here */
736 fprintf(stderrstderr, "ERROR hash_iter_next reached invalid state\n");
737 return NULL((void*)0);
738}
739
740struct hash_iter_context_t *new_hash_iter_context(hash_table_t *table)
741{
742 struct _hash_iter_context_t *iter;
743
744 if (!table) return NULL((void*)0);;
745
746 iter = halloc(table, sizeof(struct _hash_iter_context_t))table->halloc(sizeof(struct _hash_iter_context_t), table->
halloc_pvt)
;
747 if (iter == NULL((void*)0)) {
748 return NULL((void*)0);
749 }
750
751
752 iter->iter.next = (hash_iter_next_t) hash_iter_next;
753
754 iter->table = table;
755 iter->i = 0;
756 iter->j = 0;
757 iter->s = table->directory[iter->i];
758 iter->p = iter->s[iter->j];
759
760 return (struct hash_iter_context_t *)iter;
761}
762
763unsigned long hash_count(hash_table_t *table)
764{
765 return table->entry_count;
766}
767
768
769int hash_keys(hash_table_t *table, unsigned long *count_arg, hash_key_t **keys_arg)
770{
771 unsigned long count = table->entry_count;
772 hash_key_t *keys;
773 hash_keys_callback_data_t data;
774
775 if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5);
776
777 if (count == 0) {
778 *count_arg = 0;
779 *keys_arg = NULL((void*)0);
780 return HASH_SUCCESS0;
781 }
782
783 keys = halloc(table, sizeof(hash_key_t) * count)table->halloc(sizeof(hash_key_t) * count, table->halloc_pvt
)
;
784 if (keys == NULL((void*)0)) {
785 *count_arg = -1;
786 *keys_arg = NULL((void*)0);
787 return HASH_ERROR_NO_MEMORY(-2000 + 3);
788 }
789
790 data.index = 0;
791 data.keys = keys;
792
793 hash_iterate(table, hash_keys_callback, &data);
794
795 *count_arg = count;
796 *keys_arg = keys;
797 return HASH_SUCCESS0;
798}
799
800int hash_values(hash_table_t *table, unsigned long *count_arg, hash_value_t **values_arg)
801{
802 unsigned long count = table->entry_count;
803 hash_value_t *values;
804 hash_values_callback_data_t data;
805
806 if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5);
807
808 if (count == 0) {
809 *count_arg = 0;
810 *values_arg = NULL((void*)0);
811 return HASH_SUCCESS0;
812 }
813
814 values = halloc(table, sizeof(hash_value_t) * count)table->halloc(sizeof(hash_value_t) * count, table->halloc_pvt
)
;
815 if (values == NULL((void*)0)) {
816 *count_arg = -1;
817 *values_arg = NULL((void*)0);
818 return HASH_ERROR_NO_MEMORY(-2000 + 3);
819 }
820
821 data.index = 0;
822 data.values = values;
823
824 hash_iterate(table, hash_values_callback, &data);
825
826 *count_arg = count;
827 *values_arg = values;
828 return HASH_SUCCESS0;
829}
830
831typedef struct hash_entries_callback_data_t {
832 unsigned long index;
833 hash_entry_t *entries;
834} hash_entries_callback_data_t;
835
836static bool_Bool hash_entries_callback(hash_entry_t *item, void *user_data)
837{
838 hash_entries_callback_data_t *data = (hash_entries_callback_data_t *)user_data;
839
840 data->entries[data->index++] = *item;
841 return true1;
842}
843
844int hash_entries(hash_table_t *table, unsigned long *count_arg, hash_entry_t **entries_arg)
845{
846 unsigned long count = table->entry_count;
847 hash_entry_t *entries;
848 hash_entries_callback_data_t data;
849
850 if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5);
851
852 if (count == 0) {
853 *count_arg = 0;
854 *entries_arg = NULL((void*)0);
855 return HASH_SUCCESS0;
856 }
857
858 entries = halloc(table, sizeof(hash_entry_t) * count)table->halloc(sizeof(hash_entry_t) * count, table->halloc_pvt
)
;
859 if (entries == NULL((void*)0)) {
860 *count_arg = -1;
861 *entries_arg = NULL((void*)0);
862 return HASH_ERROR_NO_MEMORY(-2000 + 3);
863 }
864
865 data.index = 0;
866 data.entries = entries;
867
868 hash_iterate(table, hash_entries_callback, &data);
869
870 *count_arg = count;
871 *entries_arg = entries;
872 return HASH_SUCCESS0;
873}
874
875bool_Bool hash_has_key(hash_table_t *table, hash_key_t *key)
876{
877 hash_value_t value;
878
879 if (hash_lookup(table, key, &value) == HASH_SUCCESS0)
880 return true1;
881 else
882 return false0;
883}
884
885
886int hash_get_default(hash_table_t *table, hash_key_t *key, hash_value_t *value, hash_value_t *default_value)
887{
888 int error;
889
890 if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5);
891
892 if ((error = hash_lookup(table, key, value)) != HASH_SUCCESS0) {
Although the value stored to 'error' is used in the enclosing expression, the value is never actually read from 'error'
893 if ((error = hash_enter(table, key, default_value)) != HASH_SUCCESS0) {
894 return error;
895 }
896 *value = *default_value;
897 return HASH_SUCCESS0;
898 }
899
900 return HASH_SUCCESS0;
901}
902
903int hash_enter(hash_table_t *table, hash_key_t *key, hash_value_t *value)
904{
905 int error;
906 segment_t element, *chain;
907 size_t len;
908
909 if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5);
910
911 if (!is_valid_key_type(key->type))
912 return HASH_ERROR_BAD_KEY_TYPE(-2000 + 1);
913
914 if (!is_valid_value_type(value->type))
915 return HASH_ERROR_BAD_VALUE_TYPE(-2000 + 2);
916
917 lookup(table, key, &element, &chain);
918
919 if (element == NULL((void*)0)) { /* not found */
920 element = (element_t *)halloc(table, sizeof(element_t))table->halloc(sizeof(element_t), table->halloc_pvt);
921 if (element == NULL((void*)0)) {
922 /* Allocation failed, return NULL */
923 return HASH_ERROR_NO_MEMORY(-2000 + 3);
924 }
925 memset(element, 0, sizeof(element_t));
926 /*
927 * Initialize new element
928 */
929 switch(element->entry.key.type = key->type) {
930 case HASH_KEY_ULONG:
931 element->entry.key.ul = key->ul;
932 break;
933 case HASH_KEY_STRING:
934 len = strlen(key->str)+1;
935 element->entry.key.str = halloc(table, len)table->halloc(len, table->halloc_pvt);
936 if (element->entry.key.str == NULL((void*)0)) {
937 hfree(table, element)table->hfree(element, table->halloc_pvt);
938 return HASH_ERROR_NO_MEMORY(-2000 + 3);
939 }
940 memcpy((void *)element->entry.key.str, key->str, len);
941 break;
942 }
943
944 *chain = element; /* link into chain */
945 element->next = NULL((void*)0);
946
947 /*
948 * Table over-full?
949 */
950 if (++table->entry_count / table->bucket_count > table->max_load_factor) {
951 if ((error = expand_table(table)) != HASH_SUCCESS0) { /* doesn't affect element */
952 return error;
953 }
954 }
955
956 } else {
957 hdelete_callback(table, HASH_ENTRY_DESTROY, &element->entry)do { if (table->delete_callback) { table->delete_callback
(&element->entry, HASH_ENTRY_DESTROY, table->delete_pvt
); } } while(0)
;
958 }
959
960 switch(element->entry.value.type = value->type) {
961 case HASH_VALUE_UNDEF:
962 element->entry.value.ul = 0;
963 break;
964 case HASH_VALUE_PTR:
965 element->entry.value.ptr = value->ptr;
966 break;
967 case HASH_VALUE_INT:
968 element->entry.value.i = value->i;
969 break;
970 case HASH_VALUE_UINT:
971 element->entry.value.ui = value->ui;
972 break;
973 case HASH_VALUE_LONG:
974 element->entry.value.l = value->l;
975 break;
976 case HASH_VALUE_ULONG:
977 element->entry.value.ul = value->ul;
978 break;
979 case HASH_VALUE_FLOAT:
980 element->entry.value.f = value->f;
981 break;
982 case HASH_VALUE_DOUBLE:
983 element->entry.value.d = value->d;
984 break;
985 }
986
987 return HASH_SUCCESS0;
988}
989
990int hash_lookup(hash_table_t *table, hash_key_t *key, hash_value_t *value)
991{
992 segment_t element, *chain;
993
994 if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5);
995
996 if (!is_valid_key_type(key->type))
997 return HASH_ERROR_BAD_KEY_TYPE(-2000 + 1);
998
999 lookup(table, key, &element, &chain);
1000
1001 if (element) {
1002 *value = element->entry.value;
1003 return HASH_SUCCESS0;
1004 } else {
1005 return HASH_ERROR_KEY_NOT_FOUND(-2000 + 4);
1006 }
1007}
1008
1009int hash_delete(hash_table_t *table, hash_key_t *key)
1010{
1011 int error;
1012 segment_t element, *chain;
1013
1014 if (!table) return HASH_ERROR_BAD_TABLE(-2000 + 5);
1015
1016 if (!is_valid_key_type(key->type))
1017 return HASH_ERROR_BAD_KEY_TYPE(-2000 + 1);
1018
1019 lookup(table, key, &element, &chain);
1020
1021 if (element) {
1022 hdelete_callback(table, HASH_ENTRY_DESTROY, &element->entry)do { if (table->delete_callback) { table->delete_callback
(&element->entry, HASH_ENTRY_DESTROY, table->delete_pvt
); } } while(0)
;
1023 *chain = element->next; /* remove from chain */
1024 /*
1025 * Table too sparse?
1026 */
1027 if (--table->entry_count / table->bucket_count < table->min_load_factor) {
1028 if ((error = contract_table(table)) != HASH_SUCCESS0) { /* doesn't affect element */
1029 return error;
1030 }
1031 }
1032 if (element->entry.key.type == HASH_KEY_STRING) {
1033 hfree(table, (char *)element->entry.key.str)table->hfree((char *)element->entry.key.str, table->
halloc_pvt)
;
1034 }
1035 hfree(table, element)table->hfree(element, table->halloc_pvt);
1036 return HASH_SUCCESS0;
1037 } else {
1038 return HASH_ERROR_KEY_NOT_FOUND(-2000 + 4);
1039 }
1040}
1041
1042