Freeciv-3.3: /fast/freeciv/nightly/main/utility/genhash.c Source File

Freeciv-3.3

Loading...
Searching...
No Matches
genhash.c
Go to the documentation of this file.
1/***********************************************************************
2 Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; either version 2, or (at your option)
6 any later version.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12***********************************************************************/
13
14/****************************************************************************
15 A general-purpose generic hash table implementation.
16
17 Based on implementation previous included in registry.c, but separated
18 out so that can be used more generally. Maybe we should just use glib?
19
20 Original author: David Pfitzner dwp@mso.anu.edu.au
21
22 A hash table maps keys to user data values, using a user-supplied hash
23 function to do this efficiently. Here both keys and values are general
24 data represented by (void*) pointers. Memory management of both keys
25 and data is the responsibility of the caller: that is, the caller must
26 ensure that the memory (especially for keys) remains valid (allocated)
27 for as long as required (typically, the life of the genhash table).
28 (Otherwise, to allocate keys internally would either have to restrict
29 key type (e.g., strings), or have user-supplied function to duplicate
30 a key type. See further comments below.)
31
32 User-supplied functions required are:
33 key_val_func: map key to bucket number given number of buckets; should
34 map keys fairly evenly to range 0 to (num_buckets - 1)
35 inclusive.
36
37 key_comp_func: compare keys for equality, necessary for lookups for keys
38 which map to the same genhash value. Keys which compare
39 equal should map to the same hash value. Returns 0 for
40 equality, so can use qsort-type comparison function (but
41 the hash table does not make use of the ordering
42 information if the return value is non-zero).
43
44 Some constructors also accept following functions to be registered:
45 key_copy_func: This is called when assigning a new value to a bucket.
46 key_free_func: This is called when genhash no longer needs key construct.
47 Note that one key construct gets freed even when it is
48 replaced with another that is considered identical by
49 key_comp_func().
50 data_copy_func: same as 'key_copy_func', but for data.
51 data_free_func: same as 'key_free_func', but for data.
52
53 Implementation uses open hashing. Collision resolution is done by
54 separate chaining with linked lists. Resize hash table when deemed
55 necessary by making and populating a new table.
56****************************************************************************/
57
58#ifdef HAVE_CONFIG_H
59#include <fc_config.h>
60#endif
61
62#include <string.h>
63
64/* utility */
65#include "log.h"
66#include "mem.h"
67#include "shared.h" /* ARRAY_SIZE */
68#include "support.h"
69
70#include "genhash.h"
71
72#define FULL_RATIO 0.75 /* consider expanding when above this */
73#define MIN_RATIO 0.24 /* shrink when below this */
74
75 struct genhash_entry {
76 void *key;
77 void *data;
78 genhash_val_t hash_val;
79 struct genhash_entry *next;
80};
81
82/* Contents of the opaque type: */
83 struct genhash {
84 struct genhash_entry **buckets;
85 genhash_val_fn_t key_val_func;
86 genhash_comp_fn_t key_comp_func;
87 genhash_copy_fn_t key_copy_func;
88 genhash_free_fn_t key_free_func;
89 genhash_copy_fn_t data_copy_func;
90 genhash_free_fn_t data_free_func;
91 size_t num_buckets;
92 size_t num_entries;
93 bool no_shrink; /* Do not auto-shrink when set. */
94};
95
96 struct genhash_iter {
97 struct iterator vtable;
98 struct genhash_entry *const *bucket, *const *end;
99 const struct genhash_entry *iterator;
100};
101
102#define GENHASH_ITER(p) ((struct genhash_iter *) (p))
103
104
105/************************************************************************/
109 genhash_val_t genhash_str_val_func(const char *vkey)
110{
111 unsigned long result = 0;
112
113 for (; *vkey != '\0'; vkey++) {
114 result *= 5;
115 result += *vkey;
116 }
117 result &= 0xFFFFFFFF; /* To make results independent of sizeof(long) */
118 return result;
119}
120
121/************************************************************************/
124 bool genhash_str_comp_func(const char *vkey1, const char *vkey2)
125{
126 return 0 == strcmp(vkey1, vkey2);
127}
128
129/************************************************************************/
132 char *genhash_str_copy_func(const char *vkey)
133{
134 return fc_strdup(NULL != vkey ? vkey : "");
135}
136
137/************************************************************************/
140 void genhash_str_free_func(char *vkey)
141{
142#ifdef FREECIV_DEBUG
143 fc_assert_ret(NULL != vkey);
144#endif
145 free(vkey);
146}
147
148/************************************************************************/
161#define MIN_BUCKETS 29 /* Historical purposes. */
162 static size_t genhash_calc_num_buckets(size_t num_entries)
163{
164 /* A bunch of prime numbers close to successive elements of the sequence
165 * A_n = 3 * 2 ^ n; to be used for table sizes. */
166 static const size_t sizes[] = {
167 MIN_BUCKETS, 53, 97, 193,
168 389, 769, 1543, 3079, 6151,
169 12289, 24593, 49157, 98317, 196613,
170 393241, 786433, 1572869, 3145739, 6291469,
171 12582917, 25165843, 50331653, 100663319, 201326611,
172 402653189, 805306457, 1610612741, 3221225473ul, 4294967291ul
173 };
174 const size_t *pframe = sizes, *pmid;
175 int fsize = ARRAY_SIZE(sizes) - 1, lpart;
176
177 num_entries <<= 1; /* breathing room */
178
179 while (fsize > 0) {
180 lpart = fsize >> 1;
181 pmid = pframe + lpart;
182 if (*pmid < num_entries) {
183 pframe = pmid + 1;
184 fsize = fsize - lpart - 1;
185 } else {
186 fsize = lpart;
187 }
188 }
189 return *pframe;
190}
191
192/************************************************************************/
201static struct genhash *
202genhash_new_nbuckets(genhash_val_fn_t key_val_func,
203 genhash_comp_fn_t key_comp_func,
204 genhash_copy_fn_t key_copy_func,
205 genhash_free_fn_t key_free_func,
206 genhash_copy_fn_t data_copy_func,
207 genhash_free_fn_t data_free_func,
208 size_t num_buckets)
209{
210 struct genhash *pgenhash = fc_malloc(sizeof(*pgenhash));
211
212 log_debug("New genhash table with %lu buckets",
213 (long unsigned) num_buckets);
214
215 pgenhash->buckets = fc_calloc(num_buckets, sizeof(*pgenhash->buckets));
216 pgenhash->key_val_func = key_val_func;
217 pgenhash->key_comp_func = key_comp_func;
218 pgenhash->key_copy_func = key_copy_func;
219 pgenhash->key_free_func = key_free_func;
220 pgenhash->data_copy_func = data_copy_func;
221 pgenhash->data_free_func = data_free_func;
222 pgenhash->num_buckets = num_buckets;
223 pgenhash->num_entries = 0;
224 pgenhash->no_shrink = FALSE;
225
226 return pgenhash;
227}
228
229/************************************************************************/
235struct genhash *
236genhash_new_nentries_full(genhash_val_fn_t key_val_func,
237 genhash_comp_fn_t key_comp_func,
238 genhash_copy_fn_t key_copy_func,
239 genhash_free_fn_t key_free_func,
240 genhash_copy_fn_t data_copy_func,
241 genhash_free_fn_t data_free_func,
242 size_t nentries)
243{
244 return genhash_new_nbuckets(key_val_func, key_comp_func,
245 key_copy_func, key_free_func,
246 data_copy_func, data_free_func,
247 genhash_calc_num_buckets(nentries));
248}
249
250/************************************************************************/
253 struct genhash *genhash_new_nentries(genhash_val_fn_t key_val_func,
254 genhash_comp_fn_t key_comp_func,
255 size_t nentries)
256{
257 return genhash_new_nbuckets(key_val_func, key_comp_func,
258 NULL, NULL, NULL, NULL,
259 genhash_calc_num_buckets(nentries));
260}
261
262/************************************************************************/
268 struct genhash *genhash_new_full(genhash_val_fn_t key_val_func,
269 genhash_comp_fn_t key_comp_func,
270 genhash_copy_fn_t key_copy_func,
271 genhash_free_fn_t key_free_func,
272 genhash_copy_fn_t data_copy_func,
273 genhash_free_fn_t data_free_func)
274{
275 return genhash_new_nbuckets(key_val_func, key_comp_func,
276 key_copy_func, key_free_func,
277 data_copy_func, data_free_func, MIN_BUCKETS);
278}
279
280/************************************************************************/
283 struct genhash *genhash_new(genhash_val_fn_t key_val_func,
284 genhash_comp_fn_t key_comp_func)
285{
286 return genhash_new_nbuckets(key_val_func, key_comp_func,
287 NULL, NULL, NULL, NULL, MIN_BUCKETS);
288}
289
290/************************************************************************/
293 void genhash_destroy(struct genhash *pgenhash)
294{
295 fc_assert_ret(NULL != pgenhash);
296 pgenhash->no_shrink = TRUE;
297 genhash_clear(pgenhash);
298 free(pgenhash->buckets);
299 free(pgenhash);
300}
301
302/************************************************************************/
305 static void genhash_resize_table(struct genhash *pgenhash,
306 size_t new_nbuckets)
307{
308 struct genhash_entry **new_buckets, **bucket, **end, **slot;
309 struct genhash_entry *iter, *next;
310
311 fc_assert(new_nbuckets >= pgenhash->num_entries);
312
313 new_buckets = fc_calloc(new_nbuckets, sizeof(*pgenhash->buckets));
314
315 bucket = pgenhash->buckets;
316 end = bucket + pgenhash->num_buckets;
317 for (; bucket < end; bucket++) {
318 for (iter = *bucket; NULL != iter; iter = next) {
319 slot = new_buckets + (iter->hash_val % new_nbuckets);
320 next = iter->next;
321 iter->next = *slot;
322 *slot = iter;
323 }
324 }
325
326 free(pgenhash->buckets);
327 pgenhash->buckets = new_buckets;
328 pgenhash->num_buckets = new_nbuckets;
329}
330
331/************************************************************************/
338#define genhash_maybe_expand(htab) genhash_maybe_resize((htab), TRUE)
339#define genhash_maybe_shrink(htab) genhash_maybe_resize((htab), FALSE)
340 static bool genhash_maybe_resize(struct genhash *pgenhash, bool expandingp)
341{
342 size_t limit, new_nbuckets;
343
344 if (!expandingp && pgenhash->no_shrink) {
345 return FALSE;
346 }
347 if (expandingp) {
348 limit = FULL_RATIO * pgenhash->num_buckets;
349 if (pgenhash->num_entries < limit) {
350 return FALSE;
351 }
352 } else {
353 if (pgenhash->num_buckets <= MIN_BUCKETS) {
354 return FALSE;
355 }
356 limit = MIN_RATIO * pgenhash->num_buckets;
357 if (pgenhash->num_entries > limit) {
358 return FALSE;
359 }
360 }
361
362 new_nbuckets = genhash_calc_num_buckets(pgenhash->num_entries);
363
364 log_debug("%s genhash (entries = %lu, buckets = %lu, new = %lu, "
365 "%s limit = %lu)",
366 (new_nbuckets < pgenhash->num_buckets ? "Shrinking"
367 : (new_nbuckets > pgenhash->num_buckets
368 ? "Expanding" : "Rehashing")),
369 (long unsigned) pgenhash->num_entries,
370 (long unsigned) pgenhash->num_buckets,
371 (long unsigned) new_nbuckets,
372 expandingp ? "up": "down", (long unsigned) limit);
373 genhash_resize_table(pgenhash, new_nbuckets);
374 return TRUE;
375}
376
377
378/************************************************************************/
381 static inline genhash_val_t genhash_val_calc(const struct genhash *pgenhash,
382 const void *key)
383{
384 if (NULL != pgenhash->key_val_func) {
385 return pgenhash->key_val_func(key);
386 } else {
387 return ((intptr_t) key);
388 }
389}
390
391/************************************************************************/
395static inline struct genhash_entry **
396genhash_slot_lookup(const struct genhash *pgenhash,
397 const void *key,
398 genhash_val_t hash_val)
399{
400 struct genhash_entry **slot;
401 genhash_comp_fn_t key_comp_func = pgenhash->key_comp_func;
402
403 slot = pgenhash->buckets + (hash_val % pgenhash->num_buckets);
404 if (NULL != key_comp_func) {
405 for (; NULL != *slot; slot = &(*slot)->next) {
406 if (hash_val == (*slot)->hash_val
407 && key_comp_func((*slot)->key, key)) {
408 return slot;
409 }
410 }
411 } else {
412 for (; NULL != *slot; slot = &(*slot)->next) {
413 if (key == (*slot)->key) {
414 return slot;
415 }
416 }
417 }
418 return slot;
419}
420
421/************************************************************************/
424 static inline void genhash_default_get(void **pkey, void **data)
425{
426 if (NULL != pkey) {
427 *pkey = NULL;
428 }
429 if (NULL != data) {
430 *data = NULL;
431 }
432}
433
434/************************************************************************/
437 static inline void genhash_slot_get(struct genhash_entry *const *slot,
438 void **pkey, void **data)
439{
440 const struct genhash_entry *entry = *slot;
441
442 if (NULL != pkey) {
443 *pkey = entry->key;
444 }
445 if (NULL != data) {
446 *data = entry->data;
447 }
448}
449
450/************************************************************************/
453 static inline void genhash_slot_create(struct genhash *pgenhash,
454 struct genhash_entry **slot,
455 const void *key, const void *data,
456 genhash_val_t hash_val)
457{
458 struct genhash_entry *entry = fc_malloc(sizeof(*entry));
459
460 entry->key = (NULL != pgenhash->key_copy_func
461 ? pgenhash->key_copy_func(key) : (void *) key);
462 entry->data = (NULL != pgenhash->data_copy_func
463 ? pgenhash->data_copy_func(data) : (void *) data);
464 entry->hash_val = hash_val;
465 entry->next = *slot;
466 *slot = entry;
467}
468
469/************************************************************************/
472 static inline void genhash_slot_free(struct genhash *pgenhash,
473 struct genhash_entry **slot)
474{
475 struct genhash_entry *entry = *slot;
476
477 if (NULL != pgenhash->key_free_func) {
478 pgenhash->key_free_func(entry->key);
479 }
480 if (NULL != pgenhash->data_free_func) {
481 pgenhash->data_free_func(entry->data);
482 }
483 *slot = entry->next;
484 free(entry);
485}
486
487/************************************************************************/
490 static inline void genhash_slot_set(struct genhash *pgenhash,
491 struct genhash_entry **slot,
492 const void *key, const void *data)
493{
494 struct genhash_entry *entry = *slot;
495
496 if (NULL != pgenhash->key_free_func) {
497 pgenhash->key_free_func(entry->key);
498 }
499 if (NULL != pgenhash->data_free_func) {
500 pgenhash->data_free_func(entry->data);
501 }
502 entry->key = (NULL != pgenhash->key_copy_func
503 ? pgenhash->key_copy_func(key) : (void *) key);
504 entry->data = (NULL != pgenhash->data_copy_func
505 ? pgenhash->data_copy_func(data) : (void *) data);
506}
507
508/************************************************************************/
512 bool genhash_set_no_shrink(struct genhash *pgenhash, bool no_shrink)
513{
514 bool old;
515
516 fc_assert_ret_val(NULL != pgenhash, FALSE);
517 old = pgenhash->no_shrink;
518 pgenhash->no_shrink = no_shrink;
519 return old;
520}
521
522/************************************************************************/
525 size_t genhash_size(const struct genhash *pgenhash)
526{
527 fc_assert_ret_val(NULL != pgenhash, 0);
528 return pgenhash->num_entries;
529}
530
531/************************************************************************/
534 size_t genhash_capacity(const struct genhash *pgenhash)
535{
536 fc_assert_ret_val(NULL != pgenhash, 0);
537 return pgenhash->num_buckets;
538}
539
540/************************************************************************/
543 struct genhash *genhash_copy(const struct genhash *pgenhash)
544{
545 struct genhash *new_genhash;
546 struct genhash_entry *const *src_bucket, *const *end;
547 const struct genhash_entry *src_iter;
548 struct genhash_entry **dest_slot, **dest_bucket;
549
550 fc_assert_ret_val(NULL != pgenhash, NULL);
551
552 new_genhash = fc_malloc(sizeof(*new_genhash));
553
554 /* Copy fields. */
555 *new_genhash = *pgenhash;
556
557 /* But make fresh buckets. */
558 new_genhash->buckets = fc_calloc(new_genhash->num_buckets,
559 sizeof(*new_genhash->buckets));
560
561 /* Let's re-insert all data */
562 src_bucket = pgenhash->buckets;
563 end = src_bucket + pgenhash->num_buckets;
564 dest_bucket = new_genhash->buckets;
565
566 for (; src_bucket < end; src_bucket++, dest_bucket++) {
567 dest_slot = dest_bucket;
568 for (src_iter = *src_bucket; NULL != src_iter;
569 src_iter = src_iter->next) {
570 genhash_slot_create(new_genhash, dest_slot, src_iter->key,
571 src_iter->data, src_iter->hash_val);
572 dest_slot = &(*dest_slot)->next;
573 }
574 }
575
576 return new_genhash;
577}
578
579/************************************************************************/
582 void genhash_clear(struct genhash *pgenhash)
583{
584 struct genhash_entry **bucket, **end;
585
586 fc_assert_ret(NULL != pgenhash);
587
588 bucket = pgenhash->buckets;
589 end = bucket + pgenhash->num_buckets;
590 for (; bucket < end; bucket++) {
591 while (NULL != *bucket) {
592 genhash_slot_free(pgenhash, bucket);
593 }
594 }
595
596 pgenhash->num_entries = 0;
597 genhash_maybe_shrink(pgenhash);
598}
599
600/************************************************************************/
604 bool genhash_insert(struct genhash *pgenhash, const void *key,
605 const void *data)
606{
607 struct genhash_entry **slot;
608 genhash_val_t hash_val;
609
610 fc_assert_ret_val(NULL != pgenhash, FALSE);
611
612 hash_val = genhash_val_calc(pgenhash, key);
613 slot = genhash_slot_lookup(pgenhash, key, hash_val);
614 if (NULL != *slot) {
615 return FALSE;
616 } else {
617 if (genhash_maybe_expand(pgenhash)) {
618 /* Recalculate slot. */
619 slot = pgenhash->buckets + (hash_val % pgenhash->num_buckets);
620 }
621 genhash_slot_create(pgenhash, slot, key, data, hash_val);
622 pgenhash->num_entries++;
623 return TRUE;
624 }
625}
626
627/************************************************************************/
632 bool genhash_replace(struct genhash *pgenhash, const void *key,
633 const void *data)
634{
635 return genhash_replace_full(pgenhash, key, data, NULL, NULL);
636}
637
638/************************************************************************/
647 bool genhash_replace_full(struct genhash *pgenhash, const void *key,
648 const void *data, void **old_pkey,
649 void **old_pdata)
650{
651 struct genhash_entry **slot;
652 genhash_val_t hash_val;
653
654 fc_assert_action(NULL != pgenhash,
655 genhash_default_get(old_pkey, old_pdata); return FALSE);
656
657 hash_val = genhash_val_calc(pgenhash, key);
658 slot = genhash_slot_lookup(pgenhash, key, hash_val);
659 if (NULL != *slot) {
660 /* Replace. */
661 genhash_slot_get(slot, old_pkey, old_pdata);
662 genhash_slot_set(pgenhash, slot, key, data);
663 return TRUE;
664 } else {
665 /* Insert. */
666 if (genhash_maybe_expand(pgenhash)) {
667 /* Recalculate slot. */
668 slot = pgenhash->buckets + (hash_val % pgenhash->num_buckets);
669 }
670 genhash_default_get(old_pkey, old_pdata);
671 genhash_slot_create(pgenhash, slot, key, data, hash_val);
672 pgenhash->num_entries++;
673 return FALSE;
674 }
675}
676
677/************************************************************************/
681 bool genhash_lookup(const struct genhash *pgenhash, const void *key,
682 void **pdata)
683{
684 struct genhash_entry **slot;
685
686 fc_assert_action(NULL != pgenhash,
687 genhash_default_get(NULL, pdata); return FALSE);
688
689 slot = genhash_slot_lookup(pgenhash, key, genhash_val_calc(pgenhash, key));
690 if (NULL != *slot) {
691 genhash_slot_get(slot, NULL, pdata);
692 return TRUE;
693 } else {
694 genhash_default_get(NULL, pdata);
695 return FALSE;
696 }
697}
698
699/************************************************************************/
702 bool genhash_remove(struct genhash *pgenhash, const void *key)
703{
704 return genhash_remove_full(pgenhash, key, NULL, NULL);
705}
706
707/************************************************************************/
714 bool genhash_remove_full(struct genhash *pgenhash, const void *key,
715 void **deleted_pkey, void **deleted_pdata)
716{
717 struct genhash_entry **slot;
718
719 fc_assert_action(NULL != pgenhash,
720 genhash_default_get(deleted_pkey, deleted_pdata);
721 return FALSE);
722
723 slot = genhash_slot_lookup(pgenhash, key, genhash_val_calc(pgenhash, key));
724 if (NULL != *slot) {
725 genhash_slot_get(slot, deleted_pkey, deleted_pdata);
726 genhash_slot_free(pgenhash, slot);
727 genhash_maybe_shrink(pgenhash);
728 fc_assert(0 < pgenhash->num_entries);
729 pgenhash->num_entries--;
730 return TRUE;
731 } else {
732 genhash_default_get(deleted_pkey, deleted_pdata);
733 return FALSE;
734 }
735}
736
737
738/************************************************************************/
741 bool genhashes_are_equal(const struct genhash *pgenhash1,
742 const struct genhash *pgenhash2)
743{
744 return genhashes_are_equal_full(pgenhash1, pgenhash2, NULL);
745}
746
747/************************************************************************/
750 bool genhashes_are_equal_full(const struct genhash *pgenhash1,
751 const struct genhash *pgenhash2,
752 genhash_comp_fn_t data_comp_func)
753{
754 struct genhash_entry *const *bucket1, *const *max1, *const *slot2;
755 const struct genhash_entry *iter1;
756
757 /* Check pointers. */
758 if (pgenhash1 == pgenhash2) {
759 return TRUE;
760 } else if (NULL == pgenhash1 || NULL == pgenhash2) {
761 return FALSE;
762 }
763
764 /* General check. */
765 if (pgenhash1->num_entries != pgenhash2->num_entries
766 /* If the key functions is not the same, we cannot know if the
767 * keys are equals. */
768 || pgenhash1->key_val_func != pgenhash2->key_val_func
769 || pgenhash1->key_comp_func != pgenhash2->key_comp_func) {
770 return FALSE;
771 }
772
773 /* Compare buckets. */
774 bucket1 = pgenhash1->buckets;
775 max1 = bucket1 + pgenhash1->num_buckets;
776 for (; bucket1 < max1; bucket1++) {
777 for (iter1 = *bucket1; NULL != iter1; iter1 = iter1->next) {
778 slot2 = genhash_slot_lookup(pgenhash2, iter1->key, iter1->hash_val);
779 if (NULL == *slot2
780 || (iter1->data != (*slot2)->data
781 && (NULL == data_comp_func
782 || !data_comp_func(iter1->data, (*slot2)->data)))) {
783 return FALSE;
784 }
785 }
786 }
787
788 return TRUE;
789}
790
791
792/************************************************************************/
795 size_t genhash_iter_sizeof(void)
796{
797 return sizeof(struct genhash_iter);
798}
799
800/************************************************************************/
803 void *genhash_iter_key(const struct iterator *genhash_iter)
804{
805 struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
806 return (void *) iter->iterator->key;
807}
808
809/************************************************************************/
812 void *genhash_iter_value(const struct iterator *genhash_iter)
813{
814 struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
815 return (void *) iter->iterator->data;
816}
817
818/************************************************************************/
821 static void genhash_iter_next(struct iterator *genhash_iter)
822{
823 struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
824
825 iter->iterator = iter->iterator->next;
826 if (NULL != iter->iterator) {
827 return;
828 }
829
830 for (iter->bucket++; iter->bucket < iter->end; iter->bucket++) {
831 if (NULL != *iter->bucket) {
832 iter->iterator = *iter->bucket;
833 return;
834 }
835 }
836}
837
838/************************************************************************/
843 static void *genhash_iter_get(const struct iterator *genhash_iter)
844{
845 return (void *) genhash_iter;
846}
847
848/************************************************************************/
851 static bool genhash_iter_valid(const struct iterator *genhash_iter)
852{
853 struct genhash_iter *iter = GENHASH_ITER(genhash_iter);
854 return iter->bucket < iter->end;
855}
856
857/************************************************************************/
860static inline struct iterator *
861genhash_iter_init_common(struct genhash_iter *iter,
862 const struct genhash *pgenhash,
863 void * (*get) (const struct iterator *))
864{
865 if (NULL == pgenhash) {
866 return invalid_iter_init(ITERATOR(iter));
867 }
868
869 iter->vtable.next = genhash_iter_next;
870 iter->vtable.get = get;
871 iter->vtable.valid = genhash_iter_valid;
872 iter->bucket = pgenhash->buckets;
873 iter->end = pgenhash->buckets + pgenhash->num_buckets;
874
875 /* Seek to the first used bucket. */
876 for (; iter->bucket < iter->end; iter->bucket++) {
877 if (NULL != *iter->bucket) {
878 iter->iterator = *iter->bucket;
879 break;
880 }
881 }
882
883 return ITERATOR(iter);
884}
885
886/************************************************************************/
891 struct iterator *genhash_iter_init(struct genhash_iter *iter,
892 const struct genhash *pgenhash)
893{
894 return genhash_iter_init_common(iter, pgenhash, genhash_iter_get);
895}
896
897/************************************************************************/
900 struct iterator *genhash_key_iter_init(struct genhash_iter *iter,
901 const struct genhash *pgenhash)
902{
903 return genhash_iter_init_common(iter, pgenhash, genhash_iter_key);
904}
905
906/************************************************************************/
909 struct iterator *genhash_value_iter_init(struct genhash_iter *iter,
910 const struct genhash *pgenhash)
911{
912 return genhash_iter_init_common(iter, pgenhash, genhash_iter_value);
913}
incite_cost
char * incite_cost
Definition comments.c:74
genhash_iter_init_common
static struct iterator * genhash_iter_init_common(struct genhash_iter *iter, const struct genhash *pgenhash, void *(*get)(const struct iterator *))
Definition genhash.c:861
genhash_maybe_expand
#define genhash_maybe_expand(htab)
Definition genhash.c:338
genhash_iter_init
struct iterator * genhash_iter_init(struct genhash_iter *iter, const struct genhash *pgenhash)
Definition genhash.c:891
genhash_new_full
struct genhash * genhash_new_full(genhash_val_fn_t key_val_func, genhash_comp_fn_t key_comp_func, genhash_copy_fn_t key_copy_func, genhash_free_fn_t key_free_func, genhash_copy_fn_t data_copy_func, genhash_free_fn_t data_free_func)
Definition genhash.c:268
genhash_iter_next
static void genhash_iter_next(struct iterator *genhash_iter)
Definition genhash.c:821
genhash_insert
bool genhash_insert(struct genhash *pgenhash, const void *key, const void *data)
Definition genhash.c:604
genhash_iter_get
static void * genhash_iter_get(const struct iterator *genhash_iter)
Definition genhash.c:843
genhash_str_comp_func
bool genhash_str_comp_func(const char *vkey1, const char *vkey2)
Definition genhash.c:124
genhashes_are_equal
bool genhashes_are_equal(const struct genhash *pgenhash1, const struct genhash *pgenhash2)
Definition genhash.c:741
genhash_maybe_shrink
#define genhash_maybe_shrink(htab)
Definition genhash.c:339
genhash_slot_free
static void genhash_slot_free(struct genhash *pgenhash, struct genhash_entry **slot)
Definition genhash.c:472
genhash_calc_num_buckets
static size_t genhash_calc_num_buckets(size_t num_entries)
Definition genhash.c:162
genhash_maybe_resize
static bool genhash_maybe_resize(struct genhash *pgenhash, bool expandingp)
Definition genhash.c:340
genhash_set_no_shrink
bool genhash_set_no_shrink(struct genhash *pgenhash, bool no_shrink)
Definition genhash.c:512
genhash_slot_lookup
static struct genhash_entry ** genhash_slot_lookup(const struct genhash *pgenhash, const void *key, genhash_val_t hash_val)
Definition genhash.c:396
genhash_size
size_t genhash_size(const struct genhash *pgenhash)
Definition genhash.c:525
genhash_iter_valid
static bool genhash_iter_valid(const struct iterator *genhash_iter)
Definition genhash.c:851
genhash_destroy
void genhash_destroy(struct genhash *pgenhash)
Definition genhash.c:293
genhash_slot_get
static void genhash_slot_get(struct genhash_entry *const *slot, void **pkey, void **data)
Definition genhash.c:437
genhash_new_nbuckets
static struct genhash * genhash_new_nbuckets(genhash_val_fn_t key_val_func, genhash_comp_fn_t key_comp_func, genhash_copy_fn_t key_copy_func, genhash_free_fn_t key_free_func, genhash_copy_fn_t data_copy_func, genhash_free_fn_t data_free_func, size_t num_buckets)
Definition genhash.c:202
genhash_capacity
size_t genhash_capacity(const struct genhash *pgenhash)
Definition genhash.c:534
genhash_clear
void genhash_clear(struct genhash *pgenhash)
Definition genhash.c:582
genhash_value_iter_init
struct iterator * genhash_value_iter_init(struct genhash_iter *iter, const struct genhash *pgenhash)
Definition genhash.c:909
genhash_iter_sizeof
size_t genhash_iter_sizeof(void)
Definition genhash.c:795
MIN_RATIO
#define MIN_RATIO
Definition genhash.c:73
genhash_default_get
static void genhash_default_get(void **pkey, void **data)
Definition genhash.c:424
genhash_lookup
bool genhash_lookup(const struct genhash *pgenhash, const void *key, void **pdata)
Definition genhash.c:681
genhashes_are_equal_full
bool genhashes_are_equal_full(const struct genhash *pgenhash1, const struct genhash *pgenhash2, genhash_comp_fn_t data_comp_func)
Definition genhash.c:750
genhash_val_calc
static genhash_val_t genhash_val_calc(const struct genhash *pgenhash, const void *key)
Definition genhash.c:381
FULL_RATIO
#define FULL_RATIO
Definition genhash.c:72
genhash_slot_create
static void genhash_slot_create(struct genhash *pgenhash, struct genhash_entry **slot, const void *key, const void *data, genhash_val_t hash_val)
Definition genhash.c:453
genhash_remove
bool genhash_remove(struct genhash *pgenhash, const void *key)
Definition genhash.c:702
MIN_BUCKETS
#define MIN_BUCKETS
Definition genhash.c:161
genhash_slot_set
static void genhash_slot_set(struct genhash *pgenhash, struct genhash_entry **slot, const void *key, const void *data)
Definition genhash.c:490
genhash_replace_full
bool genhash_replace_full(struct genhash *pgenhash, const void *key, const void *data, void **old_pkey, void **old_pdata)
Definition genhash.c:647
genhash_new
struct genhash * genhash_new(genhash_val_fn_t key_val_func, genhash_comp_fn_t key_comp_func)
Definition genhash.c:283
genhash_key_iter_init
struct iterator * genhash_key_iter_init(struct genhash_iter *iter, const struct genhash *pgenhash)
Definition genhash.c:900
genhash_new_nentries
struct genhash * genhash_new_nentries(genhash_val_fn_t key_val_func, genhash_comp_fn_t key_comp_func, size_t nentries)
Definition genhash.c:253
genhash_iter_key
void * genhash_iter_key(const struct iterator *genhash_iter)
Definition genhash.c:803
genhash_resize_table
static void genhash_resize_table(struct genhash *pgenhash, size_t new_nbuckets)
Definition genhash.c:305
genhash_str_free_func
void genhash_str_free_func(char *vkey)
Definition genhash.c:140
genhash_str_copy_func
char * genhash_str_copy_func(const char *vkey)
Definition genhash.c:132
genhash_replace
bool genhash_replace(struct genhash *pgenhash, const void *key, const void *data)
Definition genhash.c:632
genhash_copy
struct genhash * genhash_copy(const struct genhash *pgenhash)
Definition genhash.c:543
genhash_str_val_func
genhash_val_t genhash_str_val_func(const char *vkey)
Definition genhash.c:109
genhash_new_nentries_full
struct genhash * genhash_new_nentries_full(genhash_val_fn_t key_val_func, genhash_comp_fn_t key_comp_func, genhash_copy_fn_t key_copy_func, genhash_free_fn_t key_free_func, genhash_copy_fn_t data_copy_func, genhash_free_fn_t data_free_func, size_t nentries)
Definition genhash.c:236
GENHASH_ITER
#define GENHASH_ITER(p)
Definition genhash.c:102
genhash_remove_full
bool genhash_remove_full(struct genhash *pgenhash, const void *key, void **deleted_pkey, void **deleted_pdata)
Definition genhash.c:714
genhash_iter_value
void * genhash_iter_value(const struct iterator *genhash_iter)
Definition genhash.c:812
genhash.h
genhash_val_fn_t
genhash_val_t(* genhash_val_fn_t)(const void *)
Definition genhash.h:35
genhash_comp_fn_t
bool(* genhash_comp_fn_t)(const void *, const void *)
Definition genhash.h:36
genhash_free_fn_t
void(* genhash_free_fn_t)(void *)
Definition genhash.h:38
genhash_copy_fn_t
void *(* genhash_copy_fn_t)(const void *)
Definition genhash.h:37
genhash_val_t
unsigned int genhash_val_t
Definition genhash.h:32
invalid_iter_init
struct iterator * invalid_iter_init(struct iterator *it)
Definition iterator.c:51
ITERATOR
#define ITERATOR(p)
Definition iterator.h:37
log.h
fc_assert_ret
#define fc_assert_ret(condition)
Definition log.h:191
fc_assert
#define fc_assert(condition)
Definition log.h:176
fc_assert_ret_val
#define fc_assert_ret_val(condition, val)
Definition log.h:194
fc_assert_action
#define fc_assert_action(condition, action)
Definition log.h:187
log_debug
#define log_debug(message,...)
Definition log.h:115
mem.h
fc_calloc
#define fc_calloc(n, esz)
Definition mem.h:38
fc_strdup
#define fc_strdup(str)
Definition mem.h:43
fc_malloc
#define fc_malloc(sz)
Definition mem.h:34
shared.h
ARRAY_SIZE
#define ARRAY_SIZE(x)
Definition shared.h:85
entry
Definition registry_ini.c:193
genhash_entry
Definition genhash.c:75
genhash_entry::hash_val
genhash_val_t hash_val
Definition genhash.c:78
genhash_entry::next
struct genhash_entry * next
Definition genhash.c:79
genhash_entry::key
void * key
Definition genhash.c:76
genhash_entry::data
void * data
Definition genhash.c:77
genhash_iter
Definition genhash.c:96
genhash_iter::iterator
const struct genhash_entry * iterator
Definition genhash.c:99
genhash_iter::end
struct genhash_entry *const *const * end
Definition genhash.c:98
genhash_iter::bucket
struct genhash_entry *const * bucket
Definition genhash.c:98
genhash_iter::vtable
struct iterator vtable
Definition genhash.c:97
genhash
Definition genhash.c:83
genhash::buckets
struct genhash_entry ** buckets
Definition genhash.c:84
genhash::key_comp_func
genhash_comp_fn_t key_comp_func
Definition genhash.c:86
genhash::key_val_func
genhash_val_fn_t key_val_func
Definition genhash.c:85
genhash::key_free_func
genhash_free_fn_t key_free_func
Definition genhash.c:88
genhash::no_shrink
bool no_shrink
Definition genhash.c:93
genhash::data_copy_func
genhash_copy_fn_t data_copy_func
Definition genhash.c:89
genhash::num_buckets
size_t num_buckets
Definition genhash.c:91
genhash::num_entries
size_t num_entries
Definition genhash.c:92
genhash::data_free_func
genhash_free_fn_t data_free_func
Definition genhash.c:90
genhash::key_copy_func
genhash_copy_fn_t key_copy_func
Definition genhash.c:87
iterator
Definition iterator.h:31
iterator::get
void *(* get)(const struct iterator *it)
Definition iterator.h:33
support.h
TRUE
#define TRUE
Definition support.h:46
FALSE
#define FALSE
Definition support.h:47