From cb1a40859029f33184355475e51fec95afb79a73 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Yaroslav=20de=20la=20Pe=C3=B1a=20Smirnov?= Date: Sat, 22 Jul 2023 03:03:09 +0300 Subject: init Just some C wares; hmap, list, optional, unit tests. --- hmap/hmap-test.c | 291 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 291 insertions(+) create mode 100644 hmap/hmap-test.c (limited to 'hmap/hmap-test.c') diff --git a/hmap/hmap-test.c b/hmap/hmap-test.c new file mode 100644 index 0000000..bf3ebe2 --- /dev/null +++ b/hmap/hmap-test.c @@ -0,0 +1,291 @@ +#include "hash.h" +#include "hmap.h" +#include "../utest/utest.h" + +#include + +struct hmap_test_s { + const char *key; + uint64_t data; + struct hmap_entry entry; +}; + +#define entry_to_test_s(ent) hmap_item(ent, struct hmap_test_s, entry) + +bool hmap_test_cmp(const struct hmap_entry *ent, const struct hmap_entry *key) +{ + struct hmap_test_s *a = entry_to_test_s(ent); + struct hmap_test_s *b = entry_to_test_s(key); + + return !strcmp(a->key, b->key); +} + +void hmap_test_hash(struct hmap_entry *ent) +{ + struct hmap_test_s *e = entry_to_test_s(ent); + ent->hash = fnv1a_str_hash(e->key); +} + +struct hmap *map; + +/* clang-format off */ +struct hmap_test_s inputs[] = { + { .key = "alpha", .data = 10, }, + { .key = "bravo", .data = 24, }, + { .key = "charlie", .data = 30, }, + { .key = "delta", .data = 42, }, + { .key = "echo", .data = 50, }, + { .key = "foxtrot", .data = 69, }, + { .key = "golf", .data = 70, }, + { .key = "hotel", .data = 80, }, + { .key = "india", .data = 99, }, +}; + +struct hmap_test_s inputs2[] = { + { .key = "aa" }, + { .key = "ab" }, + { .key = "ac" }, + { .key = "ad" }, + { .key = "ae" }, + { .key = "af" }, + { .key = "ag" }, + { .key = "ah" }, + { .key = "ai" }, + { .key = "aj" }, + { .key = "ak" }, + { .key = "al" }, + { .key = "am" }, + { .key = "an" }, + { .key = "ao" }, + { .key = "ap" }, + { .key = "aq" }, + { .key = "ar" }, + { .key = "as" }, + { .key = "at" }, + { .key = "au" }, + { .key = "av" }, + { .key = "aw" }, + { .key = "ax" }, + { .key = "ay" }, + { .key = "az" }, + { .key = "ba" }, + { .key = "bb" }, + { .key = "bc" }, + { .key = "bd" }, + { .key = "be" }, + { .key = "bf" }, + { .key = "bg" }, + { .key = "bh" }, + { .key = "bi" }, + { .key = "bj" }, + { .key = "bk" }, + { .key = "bl" }, + { .key = "bm" }, + { .key = "bn" }, + { .key = "bo" }, + { .key = "bp" }, + { .key = "bq" }, + { .key = "br" }, + { .key = "bs" }, + { .key = "bt" }, + { .key = "bu" }, + { .key = "bv" }, + { .key = "bw" }, + { .key = "bx" }, + { .key = "by" }, +}; +/* clang-format on */ + +struct hmap_test_s duplicate = { .key = "foxtrot", .data = 420 }; + +#ifndef HMAP_DEBUG + +TEST_BEGIN(test_hmap_add) +{ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + size_t cnt = hmap_entry_cnt(map); + expect(cnt == ARRAY_SIZE(inputs), + "number of entries in hashmap (%lu) != number of entries added " + "(%lu)", + cnt, ARRAY_SIZE(inputs)); + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_get) +{ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + struct hmap_test_s key = { .key = inputs[i].key }; + struct hmap_test_s *expect = inputs + i; + struct hmap_entry *ent = hmap_get(map, &key.entry); + + assertneq(ent, NULL); + + struct hmap_test_s *got = entry_to_test_s(ent); + asserteq(expect, got); + } + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_get_next_dup) +{ + hmap_add(map, &duplicate.entry); + struct hmap_test_s key = { .key = duplicate.key }; + struct hmap_entry *ent = hmap_get(map, &key.entry); + + assertneq(ent, NULL); + + struct hmap_test_s *got = entry_to_test_s(ent); + + struct hmap_entry *next = hmap_get_next_dup(map, ent); + + assertneq(next, NULL); + + struct hmap_test_s *got_dup = entry_to_test_s(next); + if (got->data != duplicate.data) { + asserteq(got_dup->data, duplicate.data); + } else { + assertneq(got_dup->data, duplicate.data); + } + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_remove) +{ + struct hmap_entry *removed; + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + struct hmap_test_s key = { .key = inputs[i].key }; + removed = hmap_remove(map, &key.entry); + + assertneq(removed, NULL); + } + + expect(hmap_entry_cnt(map) == 1, "expected only duplicate entry left"); + removed = hmap_remove(map, &duplicate.entry); + asserteq(removed, &duplicate.entry); + + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_realloc) +{ + /* This test case assumes default hmap settings */ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + expect(hmap_cur_cap(map) <= 64, "hashmap shouldn't grow so fast"); + + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_add(map, &inputs2[i].entry); + } + asserteq(hmap_entry_cnt(map), ARRAY_SIZE(inputs) + ARRAY_SIZE(inputs2)); + expect(hmap_cur_cap(map) > 64, "expected hashmap to grow"); + + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_remove(map, &inputs2[i].entry); + } + expect(hmap_cur_cap(map) <= 64, "expected hashmap to shrink"); + + TEST_OUT + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_remove(map, &inputs[i].entry); + } +} +TEST_END + +TEST_BEGIN(test_hmap_iter) +{ + struct hmap_iter iter; + struct hmap_entry *ent, *prev = NULL; + size_t cnt = 0; + + hmap_iter_init(&iter, map); + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + + hmap_iter_foreach(&iter, ent) { + cnt++; + expect(ent != prev, "hmap_iter shouldn't return same entry on next"); + } + asserteq(cnt, ARRAY_SIZE(inputs)); + + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_iter_remove) +{ + struct hmap_iter iter; + struct hmap_entry *ent; + + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_add(map, &inputs2[i].entry); + } + + hmap_dynamic_set(map, false); + expect(!hmap_dynamic_get(map), "expected dynamic setting to be off"); + + hmap_iter_init(&iter, map); + hmap_iter_foreach(&iter, ent) { + expect(hmap_remove(map, ent), "expected entry to be removed"); + } + asserteq(hmap_entry_cnt(map), 0); + + hmap_dynamic_set(map, true); + expect(hmap_dynamic_get(map), "expected dynamic setting to be on"); + + TEST_OUT +} +TEST_END + +#else + +TEST_BEGIN(test_hmap_collisions) +{ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_add(map, &inputs2[i].entry); + } + asserteq(hmap_entry_cnt(map), ARRAY_SIZE(inputs) + ARRAY_SIZE(inputs2)); + TEST_OUT +} +TEST_END + +#endif /* HMAP_DEBUG */ + +void hmap_test_init(void) +{ +#ifdef HMAP_DEBUG +#ifndef HMAP_DEBUG_CAP +#define HMAP_DEBUG_CAP 128 +#endif /* HMAP_DEBUG_CAP */ + map = hmap_new_with(hmap_test_cmp, hmap_test_hash, HMAP_DEBUG_CAP, false); +#else + map = hmap_new(hmap_test_cmp, hmap_test_hash); +#endif /* HMAP_DEBUG */ +} + +void hmap_test_destroy(void) +{ + hmap_free(map); +} + +#ifdef HMAP_DEBUG + +RUN_TEST_SUITE(hmap_test_init, hmap_test_destroy, test_hmap_collisions); + +#else + +RUN_TEST_SUITE(hmap_test_init, hmap_test_destroy, test_hmap_add, test_hmap_get, + test_hmap_get_next_dup, test_hmap_remove, test_hmap_realloc, + test_hmap_iter, test_hmap_iter_remove) + +#endif /* HMAP_DEBUG */ -- cgit v1.2.3