--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test_map.cpp Wed Feb 08 20:26:26 2023 +0100
@@ -0,0 +1,272 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
+ *
+ * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "cx/hash_map.h"
+#include "cx/utils.h"
+#include "util_allocator.h"
+
+#include <gtest/gtest.h>
+#include <unordered_map>
+#include <unordered_set>
+
+struct map_operation {
+ enum {
+ put, rm
+ } op;
+ char const *key;
+ char const *value;
+};
+
+auto generate_map_operations() -> std::vector<map_operation> {
+ return {
+ {map_operation::put, "key 1", "test"},
+ {map_operation::put, "key 2", "blub"},
+ {map_operation::put, "key 3", "hallo"},
+ {map_operation::put, "key 2", "foobar"},
+ {map_operation::put, "key 4", "value 4"},
+ {map_operation::put, "key 5", "value 5"},
+ {map_operation::put, "key 6", "value 6"},
+ {map_operation::rm, "key 4", nullptr},
+ {map_operation::put, "key 7", "value 7"},
+ {map_operation::put, "key 8", "value 8"},
+ {map_operation::rm, "does not exist", nullptr},
+ {map_operation::put, "key 9", "value 9"},
+ {map_operation::put, "key 6", "other value"},
+ {map_operation::put, "key 7", "something else"},
+ {map_operation::rm, "key 8", nullptr},
+ {map_operation::rm, "key 2", nullptr},
+ {map_operation::put, "key 8", "new value"},
+ };
+}
+
+static void verify_map_contents(
+ CxMap *map,
+ std::unordered_map<std::string, std::string> const &refmap
+) {
+ // verify key iterator
+ {
+ auto keyiter = cxMapIteratorKeys(map);
+ std::unordered_set<std::string> keys;
+ cx_foreach(CxHashKey*, elem, keyiter) {
+ keys.insert(std::string(elem->data.cstr, elem->len));
+ }
+ EXPECT_EQ(keyiter.index, map->size);
+ ASSERT_EQ(keys.size(), map->size);
+ for (auto &&k: keys) {
+ EXPECT_NE(refmap.find(k), refmap.end());
+ }
+ }
+
+ // verify value iterator
+ {
+ auto valiter = cxMapIteratorValues(map);
+ std::unordered_set<std::string> values; // we use that the values in our test data are unique strings
+ cx_foreach(char const*, elem, valiter) {
+ values.insert(std::string(elem));
+ }
+ EXPECT_EQ(valiter.index, map->size);
+ ASSERT_EQ(values.size(), map->size);
+ for (auto &&v: values) {
+ EXPECT_NE(std::find_if(refmap.begin(), refmap.end(),
+ [v](auto const &e) { return e.second == v; }), refmap.end());
+ }
+ }
+
+ // verify pair iterator
+ {
+ auto pairiter = cxMapIterator(map);
+ std::unordered_map<std::string, std::string> pairs;
+ cx_foreach(CxMapEntry*, entry, pairiter) {
+ pairs[std::string(entry->key->data.cstr, entry->key->len)] = std::string((char *) entry->value);
+ }
+ EXPECT_EQ(pairiter.index, map->size);
+ ASSERT_EQ(pairs.size(), refmap.size());
+ for (auto &&p: pairs) {
+ ASSERT_EQ(p.second, refmap.at(p.first));
+ }
+ }
+}
+
+TEST(CxHashMap, Create) {
+ CxTestingAllocator allocator;
+ auto map = cxHashMapCreate(&allocator, 0);
+ auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);
+ EXPECT_GT(hmap->bucket_count, 0);
+ cx_for_n(i, hmap->bucket_count) {
+ EXPECT_EQ(hmap->buckets[i], nullptr);
+ }
+ EXPECT_EQ(map->size, 0);
+ EXPECT_EQ(map->allocator, &allocator);
+
+ cxMapDestroy(map);
+ EXPECT_TRUE(allocator.verify());
+}
+
+TEST(CxHashMap, BasicOperations) {
+ // create the map
+ CxTestingAllocator allocator;
+ auto map = cxHashMapCreate(&allocator, 8);
+
+ // create a reference map
+ std::unordered_map<std::string, std::string> refmap;
+
+ // generate operations
+ auto ops = generate_map_operations();
+
+ // verify iterators for empty map
+ verify_map_contents(map, refmap);
+
+ // execute operations and verify results
+ for (auto &&op: ops) {
+ CxHashKey key = cx_hash_key_str(op.key);
+ key.hash = 0; // force the hash map to compute the hash
+ if (op.op == map_operation::put) {
+ // execute a put operation and verify that the exact value can be read back
+ refmap[std::string(op.key)] = std::string(op.value);
+ int result = cxMapPut(map, key, (void *) op.value);
+ EXPECT_EQ(result, 0);
+ auto added = cxMapGet(map, key);
+ EXPECT_EQ(memcmp(op.value, added, strlen(op.value)), 0);
+ } else {
+ // execute a remove and verify that the removed element was returned (or nullptr)
+ auto found = refmap.find(op.key);
+ auto removed = cxMapRemove(map, key);
+ if (found == refmap.end()) {
+ EXPECT_EQ(removed, nullptr);
+ } else {
+ EXPECT_EQ(std::string((char *) removed), found->second);
+ refmap.erase(found);
+ }
+ }
+ // compare the current map state with the reference map
+ verify_map_contents(map, refmap);
+ }
+
+ // destroy the map and verify the memory (de)allocations
+ cxMapDestroy(map);
+ EXPECT_TRUE(allocator.verify());
+}
+
+TEST(CxHashMap, RemoveViaIterator) {
+ CxTestingAllocator allocator;
+ auto map = cxHashMapCreate(&allocator, 4);
+
+ cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
+ cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
+ cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
+ cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
+ cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
+ cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
+
+ auto iter = cxMapMutIterator(map);
+ cx_foreach(CxMapEntry*, entry, iter) {
+ if (entry->key->data.cstr[4] % 2 == 1) cxIteratorFlagRemoval(iter);
+ }
+ EXPECT_EQ(map->size, 3);
+ EXPECT_EQ(iter.index, map->size);
+
+ EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);
+ EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);
+ EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);
+ EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 4")), nullptr);
+ EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 5")), nullptr);
+ EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 6")), nullptr);
+
+ cxMapDestroy(map);
+ EXPECT_TRUE(allocator.verify());
+}
+
+TEST(CxHashMap, RehashNotRequired) {
+ CxTestingAllocator allocator;
+ auto map = cxHashMapCreate(&allocator, 8);
+
+ cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
+ cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
+ cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
+ cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
+ cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
+ cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
+
+ // 6/8 does not exceed 0.75, therefore the function should not rehash
+ int result = cxMapRehash(map);
+ EXPECT_EQ(result, 0);
+ EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 8);
+
+ cxMapDestroy(map);
+ EXPECT_TRUE(allocator.verify());
+}
+
+TEST(CxHashMap, Rehash) {
+ CxTestingAllocator allocator;
+ auto map = cxHashMapCreate(&allocator, 8);
+
+ cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
+ cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
+ cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
+ cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
+ cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
+ cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
+ cxMapPut(map, cx_hash_key_str("key 7"), (void *) "val 7");
+
+ int result = cxMapRehash(map);
+ EXPECT_EQ(result, 0);
+ EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 17);
+ EXPECT_EQ(map->size, 7);
+
+ EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 1")), "val 1"), 0);
+ EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 2")), "val 2"), 0);
+ EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 3")), "val 3"), 0);
+ EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 4")), "val 4"), 0);
+ EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 5")), "val 5"), 0);
+ EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 6")), "val 6"), 0);
+ EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 7")), "val 7"), 0);
+
+ cxMapDestroy(map);
+ EXPECT_TRUE(allocator.verify());
+}
+
+TEST(CxHashMap, Clear) {
+ CxTestingAllocator allocator;
+ auto map = cxHashMapCreate(&allocator, 0);
+
+ cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
+ cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
+ cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
+
+ EXPECT_EQ(map->size, 3);
+
+ cxMapClear(map);
+
+ EXPECT_EQ(map->size, 0);
+ EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);
+ EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);
+ EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);
+
+ cxMapDestroy(map);
+ EXPECT_TRUE(allocator.verify());
+}
\ No newline at end of file