X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=elogind.git;a=blobdiff_plain;f=src%2Fshared%2Fhashmap.c;h=0ee2f3bd317ce50abfe7729a919cb9ed8a4b6a36;hp=2bc3b38739a093e6515b4cdfcec62a02cff7cade;hb=545407b3b250edd0a05e314a0b5cf73cdb5a74fa;hpb=89439d4fc0d29f04ac68432fd06ab84bc4e36e20

diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c
index 2bc3b3873..0ee2f3bd3 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,14 +132,14 @@ 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
 
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
 struct hashmap_debug_info {
         LIST_FIELDS(struct hashmap_debug_info, debug_list);
         unsigned max_entries;  /* high watermark of n_entries */
@@ -158,9 +160,9 @@ static LIST_HEAD(struct hashmap_debug_info, hashmap_debug_list);
 
 #define HASHMAP_DEBUG_FIELDS struct hashmap_debug_info debug;
 
-#else /* !ENABLE_HASHMAP_DEBUG */
+#else /* !ENABLE_DEBUG_HASHMAP */
 #define HASHMAP_DEBUG_FIELDS
-#endif /* ENABLE_HASHMAP_DEBUG */
+#endif /* ENABLE_DEBUG_HASHMAP */
 
 enum HashmapType {
         HASHMAP_TYPE_PLAIN,
@@ -482,7 +484,7 @@ static unsigned skip_free_buckets(HashmapBase *h, unsigned idx) {
 }
 
 static void bucket_mark_free(HashmapBase *h, unsigned idx) {
-        memset(bucket_at(h, idx), 0, hashmap_type_info[h->type].entry_size);
+        memzero(bucket_at(h, idx), hashmap_type_info[h->type].entry_size);
         bucket_set_dib(h, idx, DIB_FREE);
 }
 
@@ -552,7 +554,7 @@ static void base_remove_entry(HashmapBase *h, unsigned idx) {
         dibs = dib_raw_ptr(h);
         assert(dibs[idx] != DIB_RAW_FREE);
 
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
         h->debug.rem_count++;
         h->debug.last_rem_idx = idx;
 #endif
@@ -631,7 +633,7 @@ static unsigned hashmap_iterate_in_insertion_order(OrderedHashmap *h, Iterator *
                 assert(e->p.b.key == i->next_key);
         }
 
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
         i->prev_idx = idx;
 #endif
 
@@ -688,7 +690,7 @@ static unsigned hashmap_iterate_in_internal_order(HashmapBase *h, Iterator *i) {
         }
 
         idx = i->idx;
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
         i->prev_idx = idx;
 #endif
 
@@ -711,7 +713,7 @@ static unsigned hashmap_iterate_entry(HashmapBase *h, Iterator *i) {
                 return IDX_NIL;
         }
 
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
         if (i->idx == IDX_FIRST) {
                 i->put_count = h->debug.put_count;
                 i->rem_count = h->debug.rem_count;
@@ -731,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) \
@@ -771,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;
@@ -799,7 +805,7 @@ static struct HashmapBase *hashmap_base_new(const struct hash_ops *hash_ops, enu
                 shared_hash_key_initialized= true;
         }
 
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
         LIST_PREPEND(debug_list, hashmap_debug_list, &h->debug);
         h->debug.func = func;
         h->debug.file = file;
@@ -810,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);
@@ -830,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;
 
@@ -839,22 +845,22 @@ 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) {
         assert(!h->has_indirect);
         assert(!h->n_direct_entries);
 
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
         LIST_REMOVE(debug_list, hashmap_debug_list, &h->debug);
 #endif
 
@@ -864,38 +870,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) {
@@ -961,7 +970,7 @@ static bool hashmap_put_robin_hood(HashmapBase *h, unsigned idx,
         dib_raw_t raw_dib, *dibs;
         unsigned dib, distance;
 
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
         h->debug.put_count++;
 #endif
 
@@ -990,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 */
@@ -1055,7 +1063,7 @@ static int hashmap_base_put_boldly(HashmapBase *h, unsigned idx,
         assert_se(hashmap_put_robin_hood(h, idx, swap) == false);
 
         n_entries_inc(h);
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
         h->debug.max_entries = MAX(h->debug.max_entries, n_entries(h));
 #endif
 
@@ -1066,7 +1074,7 @@ static int hashmap_base_put_boldly(HashmapBase *h, unsigned idx,
 
 /*
  * Returns 0 if resize is not needed.
- *         1 if succesfully resized.
+ *         1 if successfully resized.
  *         -ENOMEM on allocation failure.
  */
 static int resize_buckets(HashmapBase *h, unsigned entries_add) {
@@ -1154,7 +1162,7 @@ static int resize_buckets(HashmapBase *h, unsigned entries_add) {
         }
 
         /* Zero the area of newly added entries (including the old DIB area) */
-        memset(bucket_at(h, old_n_buckets), 0,
+        memzero(bucket_at(h, old_n_buckets),
                (n_buckets(h) - old_n_buckets) * hi->entry_size);
 
         /* The upper half of the new DIB array needs initialization */
@@ -1182,7 +1190,7 @@ static int resize_buckets(HashmapBase *h, unsigned entries_add) {
                 new_dibs[idx] = DIB_RAW_FREE;
                 bucket_move_entry(h, &swap, idx, IDX_PUT);
                 /* bucket_move_entry does not clear the source */
-                memset(bucket_at(h, idx), 0, hi->entry_size);
+                memzero(bucket_at(h, idx), hi->entry_size);
 
                 do {
                         /*
@@ -1283,7 +1291,7 @@ int hashmap_replace(Hashmap *h, const void *key, void *value) {
         idx = bucket_scan(h, hash, key);
         if (idx != IDX_NIL) {
                 e = plain_bucket_at(h, idx);
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
                 /* Although the key is equal, the key pointer may have changed,
                  * and this would break our assumption for iterating. So count
                  * this operation as incompatible with iteration. */
@@ -1810,7 +1818,7 @@ int set_consume(Set *s, void *value) {
         int r;
 
         r = set_put(s, value);
-        if (r < 0)
+        if (r <= 0)
                 free(value);
 
         return r;