X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?a=blobdiff_plain;f=src%2Fshared%2Fhashmap.c;h=0ee2f3bd317ce50abfe7729a919cb9ed8a4b6a36;hb=d896ac2d2fbce41a0b11a0618a685adeaf18b8fe;hp=73937ac217358ee42e01edbeb27d43456dd5688d;hpb=99e651c2dc93fcc0ce762e7dab2dd3e9a70d76a1;p=elogind.git diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c index 73937ac21..0ee2f3bd3 100644 --- a/src/shared/hashmap.c +++ b/src/shared/hashmap.c @@ -30,6 +30,7 @@ #include "siphash24.h" #include "strv.h" #include "mempool.h" +#include "random-util.h" #ifdef ENABLE_DEBUG_HASHMAP #include "list.h" @@ -131,10 +132,10 @@ struct swap_entries { /* Distance from Initial Bucket */ typedef uint8_t dib_raw_t; -#define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */ -#define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */ -#define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */ -#define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */ +#define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */ +#define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */ +#define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */ +#define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */ #define DIB_FREE UINT_MAX @@ -732,29 +733,33 @@ static unsigned hashmap_iterate_entry(HashmapBase *h, Iterator *i) { : hashmap_iterate_in_internal_order(h, i); } -void *internal_hashmap_iterate(HashmapBase *h, Iterator *i, const void **key) { +bool internal_hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key) { struct hashmap_base_entry *e; void *data; unsigned idx; idx = hashmap_iterate_entry(h, i); if (idx == IDX_NIL) { + if (value) + *value = NULL; if (key) *key = NULL; - return NULL; + return false; } e = bucket_at(h, idx); data = entry_value(h, e); + if (value) + *value = data; if (key) *key = e->key; - return data; + return true; } -void *set_iterate(Set *s, Iterator *i) { - return internal_hashmap_iterate(HASHMAP_BASE(s), i, NULL); +bool set_iterate(Set *s, Iterator *i, void **value) { + return internal_hashmap_iterate(HASHMAP_BASE(s), i, value, NULL); } #define HASHMAP_FOREACH_IDX(idx, h, i) \ @@ -772,7 +777,7 @@ static void reset_direct_storage(HashmapBase *h) { memset(p, DIB_RAW_INIT, sizeof(dib_raw_t) * hi->n_direct_buckets); } -static struct HashmapBase *hashmap_base_new(const struct hash_ops *hash_ops, enum HashmapType type HASHMAP_DEBUG_PARAMS) { +static struct HashmapBase *hashmap_base_new(const struct hash_ops *hash_ops, enum HashmapType type HASHMAP_DEBUG_PARAMS) { HashmapBase *h; const struct hashmap_type_info *hi = &hashmap_type_info[type]; bool use_pool; @@ -811,19 +816,19 @@ static struct HashmapBase *hashmap_base_new(const struct hash_ops *hash_ops, enu } Hashmap *internal_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) { - return (Hashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS); + return (Hashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS); } OrderedHashmap *internal_ordered_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) { - return (OrderedHashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS); + return (OrderedHashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS); } Set *internal_set_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) { - return (Set*) hashmap_base_new(hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS); + return (Set*) hashmap_base_new(hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS); } static int hashmap_base_ensure_allocated(HashmapBase **h, const struct hash_ops *hash_ops, - enum HashmapType type HASHMAP_DEBUG_PARAMS) { + enum HashmapType type HASHMAP_DEBUG_PARAMS) { HashmapBase *q; assert(h); @@ -831,7 +836,7 @@ static int hashmap_base_ensure_allocated(HashmapBase **h, const struct hash_ops if (*h) return 0; - q = hashmap_base_new(hash_ops, type HASHMAP_DEBUG_PASS_ARGS); + q = hashmap_base_new(hash_ops, type HASHMAP_DEBUG_PASS_ARGS); if (!q) return -ENOMEM; @@ -840,15 +845,15 @@ static int hashmap_base_ensure_allocated(HashmapBase **h, const struct hash_ops } int internal_hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) { - return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS); + return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS); } int internal_ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) { - return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS); + return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS); } int internal_set_ensure_allocated(Set **s, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) { - return hashmap_base_ensure_allocated((HashmapBase**)s, hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS); + return hashmap_base_ensure_allocated((HashmapBase**)s, hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS); } static void hashmap_free_no_clear(HashmapBase *h) { @@ -994,7 +999,6 @@ static bool hashmap_put_robin_hood(HashmapBase *h, unsigned idx, if (dib < distance) { /* Found a wealthier entry. Go Robin Hood! */ - bucket_set_dib(h, idx, distance); /* swap the entries */