From: Michal Schmidt Date: Wed, 15 Oct 2014 09:06:08 +0000 (+0200) Subject: test: add and improve hashmap tests X-Git-Tag: v217~126 X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=elogind.git;a=commitdiff_plain;h=9ba81d5a61b7c992a1d2e5e02f334b8e2a0b0c22;ds=sidebyside test: add and improve hashmap tests Test more corner cases and error states in several tests. Add new tests for: hashmap_move hashmap_remove hashmap_remove2 hashmap_remove_value hashmap_remove_and_replace hashmap_get2 hashmap_first In test_hashmap_many additionally test with an intentionally bad hash function. --- diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c index 9080df5da..ef78ed6cc 100644 --- a/src/test/test-hashmap-plain.c +++ b/src/test/test-hashmap-plain.c @@ -154,8 +154,10 @@ static void test_hashmap_move_one(void) { hashmap_put(m, "key 3", val3); hashmap_put(m, "key 4", val4); - hashmap_move_one(n, m, "key 3"); - hashmap_move_one(n, m, "key 4"); + assert_se(hashmap_move_one(n, NULL, "key 3") == -ENOENT); + assert_se(hashmap_move_one(n, m, "key 5") == -ENOENT); + assert_se(hashmap_move_one(n, m, "key 3") == 0); + assert_se(hashmap_move_one(n, m, "key 4") == 0); r = hashmap_get(n, "key 3"); assert_se(r && streq(r, "val3")); @@ -164,6 +166,49 @@ static void test_hashmap_move_one(void) { r = hashmap_get(m, "key 3"); assert_se(!r); + assert_se(hashmap_move_one(n, m, "key 3") == -EEXIST); + + hashmap_free_free(m); + hashmap_free_free(n); +} + +static void test_hashmap_move(void) { + Hashmap *m, *n; + char *val1, *val2, *val3, *val4, *r; + + val1 = strdup("val1"); + assert_se(val1); + val2 = strdup("val2"); + assert_se(val2); + val3 = strdup("val3"); + assert_se(val3); + val4 = strdup("val4"); + assert_se(val4); + + m = hashmap_new(&string_hash_ops); + n = hashmap_new(&string_hash_ops); + + hashmap_put(n, "key 1", strdup(val1)); + hashmap_put(m, "key 1", val1); + hashmap_put(m, "key 2", val2); + hashmap_put(m, "key 3", val3); + hashmap_put(m, "key 4", val4); + + hashmap_move(n, NULL); + hashmap_move(n, m); + + assert_se(hashmap_size(m) == 1); + r = hashmap_get(m, "key 1"); + assert_se(r && streq(r, "val1")); + + r = hashmap_get(n, "key 1"); + assert_se(r && streq(r, "val1")); + r = hashmap_get(n, "key 2"); + assert_se(r && streq(r, "val2")); + r = hashmap_get(n, "key 3"); + assert_se(r && streq(r, "val3")); + r = hashmap_get(n, "key 4"); + assert_se(r && streq(r, "val4")); hashmap_free_free(m); hashmap_free_free(n); @@ -183,7 +228,11 @@ static void test_hashmap_update(void) { r = hashmap_get(m, "key 1"); assert_se(streq(r, "old_value")); - hashmap_update(m, "key 1", val2); + assert_se(hashmap_update(m, "key 2", val2) == -ENOENT); + r = hashmap_get(m, "key 1"); + assert_se(streq(r, "old_value")); + + assert_se(hashmap_update(m, "key 1", val2) == 0); r = hashmap_get(m, "key 1"); assert_se(streq(r, "new_value")); @@ -193,18 +242,107 @@ static void test_hashmap_update(void) { } static void test_hashmap_put(void) { - Hashmap *m; + Hashmap *m = NULL; int valid_hashmap_put; + void *val1 = (void*) "val 1"; - m = hashmap_new(&string_hash_ops); + hashmap_ensure_allocated(&m, &string_hash_ops); + assert_se(m); - valid_hashmap_put = hashmap_put(m, "key 1", (void*) (const char *) "val 1"); + valid_hashmap_put = hashmap_put(m, "key 1", val1); assert_se(valid_hashmap_put == 1); + assert_se(hashmap_put(m, "key 1", val1) == 0); + assert_se(hashmap_put(m, "key 1", (void *)"val 2") == -EEXIST); - assert_se(m); hashmap_free(m); } +static void test_hashmap_remove(void) { + _cleanup_hashmap_free_ Hashmap *m = NULL; + char *r; + + r = hashmap_remove(NULL, "key 1"); + assert_se(r == NULL); + + m = hashmap_new(&string_hash_ops); + assert_se(m); + + r = hashmap_remove(m, "no such key"); + assert_se(r == NULL); + + hashmap_put(m, "key 1", (void*) "val 1"); + hashmap_put(m, "key 2", (void*) "val 2"); + + r = hashmap_remove(m, "key 1"); + assert_se(streq(r, "val 1")); + + r = hashmap_get(m, "key 2"); + assert_se(streq(r, "val 2")); + assert_se(!hashmap_get(m, "key 1")); +} + +static void test_hashmap_remove2(void) { + _cleanup_hashmap_free_free_free_ Hashmap *m = NULL; + char key1[] = "key 1"; + char key2[] = "key 2"; + char val1[] = "val 1"; + char val2[] = "val 2"; + void *r, *r2; + + r = hashmap_remove2(NULL, "key 1", &r2); + assert_se(r == NULL); + + m = hashmap_new(&string_hash_ops); + assert_se(m); + + r = hashmap_remove2(m, "no such key", &r2); + assert_se(r == NULL); + + hashmap_put(m, strdup(key1), strdup(val1)); + hashmap_put(m, strdup(key2), strdup(val2)); + + r = hashmap_remove2(m, key1, &r2); + assert_se(streq(r, val1)); + assert_se(streq(r2, key1)); + free(r); + free(r2); + + r = hashmap_get(m, key2); + assert_se(streq(r, val2)); + assert_se(!hashmap_get(m, key1)); +} + +static void test_hashmap_remove_value(void) { + _cleanup_hashmap_free_ Hashmap *m = NULL; + char *r; + + r = hashmap_remove_value(NULL, "key 1", (void*) "val 1"); + assert_se(r == NULL); + + m = hashmap_new(&string_hash_ops); + assert_se(m); + + r = hashmap_remove_value(m, "key 1", (void*) "val 1"); + assert_se(r == NULL); + + hashmap_put(m, "key 1", (void*) "val 1"); + hashmap_put(m, "key 2", (void*) "val 2"); + + r = hashmap_remove_value(m, "key 1", (void*) "val 1"); + assert_se(streq(r, "val 1")); + + r = hashmap_get(m, "key 2"); + assert_se(streq(r, "val 2")); + assert_se(!hashmap_get(m, "key 1")); + + r = hashmap_remove_value(m, "key 2", (void*) "val 1"); + assert_se(r == NULL); + + r = hashmap_get(m, "key 2"); + assert_se(streq(r, "val 2")); + assert_se(!hashmap_get(m, "key 1")); +} + static void test_hashmap_remove_and_put(void) { _cleanup_hashmap_free_ Hashmap *m = NULL; int valid; @@ -213,11 +351,15 @@ static void test_hashmap_remove_and_put(void) { m = hashmap_new(&string_hash_ops); assert_se(m); - valid = hashmap_remove_and_put(m, "unvalid key", "new key", NULL); - assert_se(valid < 0); + valid = hashmap_remove_and_put(m, "invalid key", "new key", NULL); + assert_se(valid == -ENOENT); valid = hashmap_put(m, "key 1", (void*) (const char *) "val 1"); assert_se(valid == 1); + + valid = hashmap_remove_and_put(NULL, "key 1", "key 2", (void*) (const char *) "val 2"); + assert_se(valid == -ENOENT); + valid = hashmap_remove_and_put(m, "key 1", "key 2", (void*) (const char *) "val 2"); assert_se(valid == 0); @@ -228,7 +370,43 @@ static void test_hashmap_remove_and_put(void) { valid = hashmap_put(m, "key 3", (void*) (const char *) "val 3"); assert_se(valid == 1); valid = hashmap_remove_and_put(m, "key 3", "key 2", (void*) (const char *) "val 2"); - assert_se(valid < 0); + assert_se(valid == -EEXIST); +} + +static void test_hashmap_remove_and_replace(void) { + _cleanup_hashmap_free_ Hashmap *m = NULL; + int valid; + void *key1 = UINT_TO_PTR(1); + void *key2 = UINT_TO_PTR(2); + void *key3 = UINT_TO_PTR(3); + void *r; + + m = hashmap_new(&trivial_hash_ops); + assert_se(m); + + valid = hashmap_remove_and_replace(m, key1, key2, NULL); + assert_se(valid == -ENOENT); + + valid = hashmap_put(m, key1, key1); + assert_se(valid == 1); + + valid = hashmap_remove_and_replace(NULL, key1, key2, key2); + assert_se(valid == -ENOENT); + + valid = hashmap_remove_and_replace(m, key1, key2, key2); + assert_se(valid == 0); + + r = hashmap_get(m, key2); + assert_se(r == key2); + assert_se(!hashmap_get(m, key1)); + + valid = hashmap_put(m, key3, key3); + assert_se(valid == 1); + valid = hashmap_remove_and_replace(m, key3, key2, key2); + assert_se(valid == 0); + r = hashmap_get(m, key2); + assert_se(r == key2); + assert_se(!hashmap_get(m, key3)); } static void test_hashmap_ensure_allocated(void) { @@ -283,6 +461,7 @@ static void test_hashmap_foreach(void) { Iterator i; bool value_found[] = { false, false, false, false }; char *val1, *val2, *val3, *val4, *s; + unsigned count; val1 = strdup("my val1"); assert_se(val1); @@ -293,8 +472,20 @@ static void test_hashmap_foreach(void) { val4 = strdup("my val4"); assert_se(val4); + m = NULL; + + count = 0; + HASHMAP_FOREACH(s, m, i) + count++; + assert_se(count == 0); + m = hashmap_new(&string_hash_ops); + count = 0; + HASHMAP_FOREACH(s, m, i) + count++; + assert_se(count == 0); + hashmap_put(m, "Key 1", val1); hashmap_put(m, "Key 2", val2); hashmap_put(m, "Key 3", val3); @@ -363,6 +554,9 @@ static void test_hashmap_contains(void) { assert_se(!hashmap_contains(m, "Key 1")); hashmap_put(m, "Key 1", val1); assert_se(hashmap_contains(m, "Key 1")); + assert_se(!hashmap_contains(m, "Key 2")); + + assert_se(!hashmap_contains(NULL, "Key 1")); assert_se(m); hashmap_free_free(m); @@ -398,6 +592,9 @@ static void test_hashmap_size(void) { val4 = strdup("my val"); assert_se(val4); + assert_se(hashmap_size(NULL) == 0); + assert_se(hashmap_buckets(NULL) == 0); + m = hashmap_new(&string_hash_ops); hashmap_put(m, "Key 1", val1); @@ -407,6 +604,7 @@ static void test_hashmap_size(void) { assert_se(m); assert_se(hashmap_size(m) == 4); + assert_se(hashmap_buckets(m) >= 4); hashmap_free_free(m); } @@ -418,6 +616,9 @@ static void test_hashmap_get(void) { val = strdup("my val"); assert_se(val); + r = hashmap_get(NULL, "Key 1"); + assert_se(r == NULL); + m = hashmap_new(&string_hash_ops); hashmap_put(m, "Key 1", val); @@ -425,32 +626,109 @@ static void test_hashmap_get(void) { r = hashmap_get(m, "Key 1"); assert_se(streq(r, val)); + r = hashmap_get(m, "no such key"); + assert_se(r == NULL); + assert_se(m); hashmap_free_free(m); } +static void test_hashmap_get2(void) { + Hashmap *m; + char *r; + char *val; + char key_orig[] = "Key 1"; + void *key_copy; + + val = strdup("my val"); + assert_se(val); + + key_copy = strdup(key_orig); + assert_se(key_copy); + + r = hashmap_get2(NULL, key_orig, &key_copy); + assert_se(r == NULL); + + m = hashmap_new(&string_hash_ops); + + hashmap_put(m, key_copy, val); + key_copy = NULL; + + r = hashmap_get2(m, key_orig, &key_copy); + assert_se(streq(r, val)); + assert_se(key_orig != key_copy); + assert_se(streq(key_orig, key_orig)); + + r = hashmap_get2(m, "no such key", NULL); + assert_se(r == NULL); + + assert_se(m); + hashmap_free_free_free(m); +} + +static unsigned long crippled_hashmap_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) { + return trivial_hash_func(p, hash_key) & 0xff; +} + +static const struct hash_ops crippled_hashmap_ops = { + .hash = crippled_hashmap_func, + .compare = trivial_compare_func, +}; + static void test_hashmap_many(void) { Hashmap *h; - unsigned i; + unsigned i, j; + void *v, *k; + static const struct { + const struct hash_ops *ops; + unsigned n_entries; + } tests[] = { + { .ops = NULL, .n_entries = 1 << 20 }, + { .ops = &crippled_hashmap_ops, .n_entries = 1 << 11 }, + }; -#define N_ENTRIES 100000 - assert_se(h = hashmap_new(NULL)); + for (j = 0; j < ELEMENTSOF(tests); j++) { + assert_se(h = hashmap_new(tests[j].ops)); - 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 < tests[j].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 < tests[j].n_entries*3; i++) + assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1)); - 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); - 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) == tests[j].n_entries); - assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.75); - assert_se(hashmap_size(h) == N_ENTRIES); + while (!hashmap_isempty(h)) { + k = hashmap_first_key(h); + v = hashmap_remove(h, k); + assert_se(v == k); + } - hashmap_free(h); + hashmap_free(h); + } +} + +static void test_hashmap_first(void) { + _cleanup_hashmap_free_ Hashmap *m = NULL; + + m = hashmap_new(&string_hash_ops); + assert_se(m); + + assert_se(!hashmap_first(m)); + assert_se(hashmap_put(m, "key 1", (void*) "val 1") == 1); + assert_se(streq(hashmap_first(m), "val 1")); + assert_se(hashmap_put(m, "key 2", (void*) "val 2") == 1); +#ifdef ORDERED + assert_se(streq(hashmap_first(m), "val 1")); + assert_se(hashmap_remove(m, "key 1")); + assert_se(streq(hashmap_first(m), "val 2")); +#endif } static void test_hashmap_first_key(void) { @@ -521,10 +799,15 @@ void test_hashmap_funcs(void) { test_hashmap_copy(); test_hashmap_get_strv(); test_hashmap_move_one(); + test_hashmap_move(); test_hashmap_replace(); test_hashmap_update(); test_hashmap_put(); + test_hashmap_remove(); + test_hashmap_remove2(); + test_hashmap_remove_value(); test_hashmap_remove_and_put(); + test_hashmap_remove_and_replace(); test_hashmap_ensure_allocated(); test_hashmap_foreach(); test_hashmap_foreach_key(); @@ -532,8 +815,10 @@ void test_hashmap_funcs(void) { test_hashmap_merge(); test_hashmap_isempty(); test_hashmap_get(); + test_hashmap_get2(); test_hashmap_size(); test_hashmap_many(); + test_hashmap_first(); test_hashmap_first_key(); test_hashmap_steal_first_key(); test_hashmap_steal_first();