72#define FULL_RATIO 0.75
102#define GENHASH_ITER(p) ((struct genhash_iter *) (p))
111 unsigned long result = 0;
117 result &= 0xFFFFFFFF;
161#define MIN_BUCKETS 29
166 static const size_t sizes[] = {
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
182 if (*
pmid < num_entries) {
212 log_debug(
"New genhash table with %lu buckets",
316 end = bucket +
pgenhash->num_buckets;
317 for (; bucket < end; bucket++) {
338#define genhash_maybe_expand(htab) genhash_maybe_resize((htab), TRUE)
339#define genhash_maybe_shrink(htab) genhash_maybe_resize((htab), FALSE)
364 log_debug(
"%s genhash (entries = %lu, buckets = %lu, new = %lu, "
368 ?
"Expanding" :
"Rehashing")),
370 (
long unsigned)
pgenhash->num_buckets,
404 if (
NULL != key_comp_func) {
405 for (;
NULL != *slot; slot = &(*slot)->
next) {
407 && key_comp_func((*slot)->key,
key)) {
412 for (;
NULL != *slot; slot = &(*slot)->
next) {
413 if (
key == (*slot)->key) {
455 const void *
key,
const void *
data,
492 const void *
key,
const void *
data)
589 end = bucket +
pgenhash->num_buckets;
590 for (; bucket < end; bucket++) {
591 while (
NULL != *bucket) {
780 || (
iter1->data != (*slot2)->data
806 return (
void *)
iter->iterator->key;
815 return (
void *)
iter->iterator->data;
825 iter->iterator =
iter->iterator->next;
static struct iterator * genhash_iter_init_common(struct genhash_iter *iter, const struct genhash *pgenhash, void *(*get)(const struct iterator *))
#define genhash_maybe_expand(htab)
struct iterator * genhash_iter_init(struct genhash_iter *iter, const struct genhash *pgenhash)
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)
static void genhash_iter_next(struct iterator *genhash_iter)
bool genhash_insert(struct genhash *pgenhash, const void *key, const void *data)
static void * genhash_iter_get(const struct iterator *genhash_iter)
bool genhash_str_comp_func(const char *vkey1, const char *vkey2)
bool genhashes_are_equal(const struct genhash *pgenhash1, const struct genhash *pgenhash2)
#define genhash_maybe_shrink(htab)
static void genhash_slot_free(struct genhash *pgenhash, struct genhash_entry **slot)
static size_t genhash_calc_num_buckets(size_t num_entries)
static bool genhash_maybe_resize(struct genhash *pgenhash, bool expandingp)
bool genhash_set_no_shrink(struct genhash *pgenhash, bool no_shrink)
static struct genhash_entry ** genhash_slot_lookup(const struct genhash *pgenhash, const void *key, genhash_val_t hash_val)
size_t genhash_size(const struct genhash *pgenhash)
static bool genhash_iter_valid(const struct iterator *genhash_iter)
void genhash_destroy(struct genhash *pgenhash)
static void genhash_slot_get(struct genhash_entry *const *slot, void **pkey, void **data)
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)
size_t genhash_capacity(const struct genhash *pgenhash)
void genhash_clear(struct genhash *pgenhash)
struct iterator * genhash_value_iter_init(struct genhash_iter *iter, const struct genhash *pgenhash)
size_t genhash_iter_sizeof(void)
static void genhash_default_get(void **pkey, void **data)
bool genhash_lookup(const struct genhash *pgenhash, const void *key, void **pdata)
bool genhashes_are_equal_full(const struct genhash *pgenhash1, const struct genhash *pgenhash2, genhash_comp_fn_t data_comp_func)
static genhash_val_t genhash_val_calc(const struct genhash *pgenhash, const void *key)
static void genhash_slot_create(struct genhash *pgenhash, struct genhash_entry **slot, const void *key, const void *data, genhash_val_t hash_val)
bool genhash_remove(struct genhash *pgenhash, const void *key)
static void genhash_slot_set(struct genhash *pgenhash, struct genhash_entry **slot, const void *key, const void *data)
bool genhash_replace_full(struct genhash *pgenhash, const void *key, const void *data, void **old_pkey, void **old_pdata)
struct genhash * genhash_new(genhash_val_fn_t key_val_func, genhash_comp_fn_t key_comp_func)
struct iterator * genhash_key_iter_init(struct genhash_iter *iter, const struct genhash *pgenhash)
struct genhash * genhash_new_nentries(genhash_val_fn_t key_val_func, genhash_comp_fn_t key_comp_func, size_t nentries)
void * genhash_iter_key(const struct iterator *genhash_iter)
static void genhash_resize_table(struct genhash *pgenhash, size_t new_nbuckets)
void genhash_str_free_func(char *vkey)
char * genhash_str_copy_func(const char *vkey)
bool genhash_replace(struct genhash *pgenhash, const void *key, const void *data)
struct genhash * genhash_copy(const struct genhash *pgenhash)
genhash_val_t genhash_str_val_func(const char *vkey)
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)
bool genhash_remove_full(struct genhash *pgenhash, const void *key, void **deleted_pkey, void **deleted_pdata)
void * genhash_iter_value(const struct iterator *genhash_iter)
genhash_val_t(* genhash_val_fn_t)(const void *)
bool(* genhash_comp_fn_t)(const void *, const void *)
void(* genhash_free_fn_t)(void *)
void *(* genhash_copy_fn_t)(const void *)
unsigned int genhash_val_t
struct iterator * invalid_iter_init(struct iterator *it)
#define fc_assert_ret(condition)
#define fc_assert(condition)
#define fc_assert_ret_val(condition, val)
#define fc_assert_action(condition, action)
#define log_debug(message,...)
#define fc_calloc(n, esz)
struct genhash_entry * next
const struct genhash_entry * iterator
struct genhash_entry *const *const * end
struct genhash_entry *const * bucket
struct genhash_entry ** buckets
genhash_comp_fn_t key_comp_func
genhash_val_fn_t key_val_func
genhash_free_fn_t key_free_func
genhash_copy_fn_t data_copy_func
genhash_free_fn_t data_free_func
genhash_copy_fn_t key_copy_func
void *(* get)(const struct iterator *it)