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 _______________________________________________ systemd-devel mailing list systemd-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/systemd-devel