diff options
Diffstat (limited to 'src/shared/hashmap.c')
| -rw-r--r-- | src/shared/hashmap.c | 68 |
1 files changed, 36 insertions, 32 deletions
diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c index e63ba4bb5a..20d599d04b 100644 --- a/src/shared/hashmap.c +++ b/src/shared/hashmap.c @@ -20,9 +20,7 @@ along with systemd; If not, see <http://www.gnu.org/licenses/>. ***/ -#include <assert.h> #include <stdlib.h> -#include <string.h> #include <errno.h> #include "util.h" @@ -31,8 +29,12 @@ #include "macro.h" #include "siphash24.h" #include "strv.h" -#include "list.h" #include "mempool.h" +#include "random-util.h" + +#ifdef ENABLE_DEBUG_HASHMAP +#include "list.h" +#endif /* * Implementation of hashmaps. @@ -130,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 @@ -771,7 +773,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; @@ -810,19 +812,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); @@ -830,7 +832,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; @@ -839,15 +841,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) { @@ -864,38 +866,41 @@ static void hashmap_free_no_clear(HashmapBase *h) { free(h); } -void internal_hashmap_free(HashmapBase *h) { +HashmapBase *internal_hashmap_free(HashmapBase *h) { /* Free the hashmap, but nothing in it */ - if (!h) - return; + if (h) { + internal_hashmap_clear(h); + hashmap_free_no_clear(h); + } - internal_hashmap_clear(h); - hashmap_free_no_clear(h); + return NULL; } -void internal_hashmap_free_free(HashmapBase *h) { +HashmapBase *internal_hashmap_free_free(HashmapBase *h) { /* Free the hashmap and all data objects in it, but not the * keys */ - if (!h) - return; + if (h) { + internal_hashmap_clear_free(h); + hashmap_free_no_clear(h); + } - internal_hashmap_clear_free(h); - hashmap_free_no_clear(h); + return NULL; } -void hashmap_free_free_free(Hashmap *h) { +Hashmap *hashmap_free_free_free(Hashmap *h) { /* Free the hashmap and all data and key objects in it */ - if (!h) - return; + if (h) { + hashmap_clear_free_free(h); + hashmap_free_no_clear(HASHMAP_BASE(h)); + } - hashmap_clear_free_free(h); - hashmap_free_no_clear(HASHMAP_BASE(h)); + return NULL; } void internal_hashmap_clear(HashmapBase *h) { @@ -990,7 +995,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 */ |