summaryrefslogtreecommitdiff
path: root/src/test/test-hashmap.c
diff options
context:
space:
mode:
authorLennart Poettering <lennart@poettering.net>2013-10-01 00:13:18 +0200
committerLennart Poettering <lennart@poettering.net>2013-10-01 00:17:21 +0200
commit45fa9e29f8c9759c8f2f4238fed956f695c73dc3 (patch)
tree456b6168141128bd35319af35ac9e437851680b1 /src/test/test-hashmap.c
parentbcd8e6d1bd3f434af894faeb400fee0e99445a7f (diff)
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).
Diffstat (limited to 'src/test/test-hashmap.c')
-rw-r--r--src/test/test-hashmap.c28
1 files changed, 26 insertions, 2 deletions
diff --git a/src/test/test-hashmap.c b/src/test/test-hashmap.c
index 2c27d08670..56a9b58c24 100644
--- a/src/test/test-hashmap.c
+++ b/src/test/test-hashmap.c
@@ -467,6 +467,30 @@ static void test_hashmap_get(void) {
hashmap_free_free(m);
}
+static void test_hashmap_many(void) {
+ Hashmap *h;
+ unsigned i;
+
+#define N_ENTRIES 100000
+
+ assert_se(h = hashmap_new(NULL, NULL));
+
+ for (i = 1; i < N_ENTRIES*3; i+=3) {
+ assert_se(hashmap_put(h, UINT_TO_PTR(i), UINT_TO_PTR(i)) >= 0);
+ assert_se(PTR_TO_UINT(hashmap_get(h, UINT_TO_PTR(i))) == i);
+ }
+
+ for (i = 1; i < N_ENTRIES*3; i++)
+ assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1));
+
+ log_info("%u <= %u * 0.75 = %g", hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.75);
+
+ assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.75);
+ assert_se(hashmap_size(h) == N_ENTRIES);
+
+ hashmap_free(h);
+}
+
static void test_uint64_compare_func(void) {
const uint64_t a = 0x100, b = 0x101;
@@ -486,8 +510,7 @@ static void test_string_compare_func(void) {
assert_se(string_compare_func("fred", "fred") == 0);
}
-int main(int argc, const char *argv[])
-{
+int main(int argc, const char *argv[]) {
test_hashmap_copy();
test_hashmap_get_strv();
test_hashmap_move_one();
@@ -504,6 +527,7 @@ int main(int argc, const char *argv[])
test_hashmap_isempty();
test_hashmap_get();
test_hashmap_size();
+ test_hashmap_many();
test_uint64_compare_func();
test_trivial_compare_func();
test_string_compare_func();