[systemd-devel] [PATCH 14/26] hashmap: introduce hashmap_reserve()

[Michal Schmidt]

With the current hashmap implementation that uses chaining, placing a
reservation can serve two purposes:
 - To optimize putting of entries if the number of entries to put is
   known. The reservation allocates buckets, so later resizing can be
   avoided.
 - To avoid having very long bucket chains after using
   hashmap_move(_one).

In an alternative hashmap implementation it will serve an additional
purpose:
 - To guarantee a subsequent hashmap_move(_one) will not fail with
   -ENOMEM (this never happens in the current implementation).
---
 src/shared/hashmap.c | 32 ++++++++++++++++++++++++++------
 src/shared/hashmap.h |  4 ++++
 src/shared/set.c     |  4 ++++
 src/shared/set.h     |  1 +
 4 files changed, 35 insertions(+), 6 deletions(-)

diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c
index 2a152ab..a11ef45 100644
--- a/src/shared/hashmap.c
+++ b/src/shared/hashmap.c
@@ -369,18 +369,26 @@ static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *ke
         return NULL;
 }
 
-static int resize_buckets(Hashmap *h) {
+static int resize_buckets(Hashmap *h, unsigned entries_add) {
         struct hashmap_entry **n, *i;
-        unsigned m;
+        unsigned m, new_n_entries, new_n_buckets;
         uint8_t nkey[HASH_KEY_SIZE];
 
         assert(h);
 
-        if (_likely_(h->n_entries*4 < h->n_buckets*3))
+        new_n_entries = h->n_entries + entries_add;
+
+        /* overflow? */
+        if (_unlikely_(new_n_entries < entries_add || new_n_entries > UINT_MAX / 4))
+                return -ENOMEM;
+
+        new_n_buckets = new_n_entries * 4 / 3;
+
+        if (_likely_(new_n_buckets <= h->n_buckets))
                 return 0;
 
-        /* Increase by four */
-        m = (h->n_entries+1)*4-1;
+        /* Increase by four at least */
+        m = MAX((h->n_entries+1)*4-1, new_n_buckets);
 
         /* If we hit OOM we simply risk packed hashmaps... */
         n = new0(struct hashmap_entry*, m);
@@ -432,7 +440,7 @@ static int __hashmap_put(Hashmap *h, const void *key, void *value, unsigned hash
 
         struct hashmap_entry *e;
 
-        if (resize_buckets(h) > 0)
+        if (resize_buckets(h, 1) > 0)
                 hash = bucket_hash(h, key);
 
         if (h->from_pool)
@@ -795,6 +803,18 @@ int hashmap_merge(Hashmap *h, Hashmap *other) {
         return 0;
 }
 
+int hashmap_reserve(Hashmap *h, unsigned entries_add) {
+        int r;
+
+        assert(h);
+
+        r = resize_buckets(h, entries_add);
+        if (r < 0)
+                return r;
+
+        return 0;
+}
+
 void hashmap_move(Hashmap *h, Hashmap *other) {
         struct hashmap_entry *e, *n;
 
diff --git a/src/shared/hashmap.h b/src/shared/hashmap.h
index 2a4277d..9a16eaf 100644
--- a/src/shared/hashmap.h
+++ b/src/shared/hashmap.h
@@ -156,6 +156,10 @@ int hashmap_merge(Hashmap *h, Hashmap *other);
 static inline int linked_hashmap_merge(LinkedHashmap *h, LinkedHashmap *other) {
         return hashmap_merge((Hashmap*) h, (Hashmap*) other);
 }
+int hashmap_reserve(Hashmap *h, unsigned entries_add);
+static inline int linked_hashmap_reserve(LinkedHashmap *h, unsigned entries_add) {
+        return hashmap_reserve((Hashmap*) h, entries_add);
+}
 void hashmap_move(Hashmap *h, Hashmap *other);
 static inline void linked_hashmap_move(LinkedHashmap *h, LinkedHashmap *other) {
         hashmap_move((Hashmap*) h, (Hashmap*) other);
diff --git a/src/shared/set.c b/src/shared/set.c
index ed16067..1a3465c 100644
--- a/src/shared/set.c
+++ b/src/shared/set.c
@@ -137,6 +137,10 @@ int set_merge(Set *s, Set *other) {
         return hashmap_merge(MAKE_HASHMAP(s), MAKE_HASHMAP(other));
 }
 
+int set_reserve(Set *s, unsigned entries_add) {
+        return hashmap_reserve(MAKE_HASHMAP(s), entries_add);
+}
+
 void set_move(Set *s, Set *other) {
         return hashmap_move(MAKE_HASHMAP(s), MAKE_HASHMAP(other));
 }
diff --git a/src/shared/set.h b/src/shared/set.h
index 840ee0a..8fe071a 100644
--- a/src/shared/set.h
+++ b/src/shared/set.h
@@ -50,6 +50,7 @@ void *set_remove(Set *s, void *value);
 int set_remove_and_put(Set *s, void *old_value, void *new_value);
 
 int set_merge(Set *s, Set *other);
+int set_reserve(Set *s, unsigned entries_add);
 void set_move(Set *s, Set *other);
 int set_move_one(Set *s, Set *other, void *value);
 
-- 
2.1.0