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