From 45fa9e29f8c9759c8f2f4238fed956f695c73dc3 Mon Sep 17 00:00:00 2001 From: Lennart Poettering Date: Tue, 1 Oct 2013 00:13:18 +0200 Subject: hashmap: size hashmap bucket array dynamically Instead of fixing the hashmap bucket array to 127 entries dynamically size it, starting with a smaller one of 31. As soon as a fill level of 75% is reached, quadruple the size, and so on. This should siginficantly optimize the lookup time in large tables (from O(n) back to O(1)), and save memory on smaller tables (which most are). --- src/shared/hashmap.h | 1 + 1 file changed, 1 insertion(+) (limited to 'src/shared/hashmap.h') diff --git a/src/shared/hashmap.h b/src/shared/hashmap.h index 15b7e27585..3d4f6721bc 100644 --- a/src/shared/hashmap.h +++ b/src/shared/hashmap.h @@ -76,6 +76,7 @@ int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key); unsigned hashmap_size(Hashmap *h) _pure_; bool hashmap_isempty(Hashmap *h) _pure_; +unsigned hashmap_buckets(Hashmap *h) _pure_; void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key); void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key); -- cgit v1.2.3-54-g00ecf