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