Mercurial > hg > ucx / changeset

--- a/test/CMakeLists.txt	Fri May 27 12:28:49 2022 +0200
+++ b/test/CMakeLists.txt	Fri May 27 12:59:32 2022 +0200
@@ -18,6 +18,7 @@
         test_buffer.cpp
         test_list.cpp
         test_tree.cpp
+        test_map.cpp
         selftest.cpp
         util_allocator.cpp
         )

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/test_map.cpp	Fri May 27 12:59:32 2022 +0200
@@ -0,0 +1,170 @@
+/*
+ * 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(CxDataPtr*, elem, keyiter) {
+            // we use that our test keys contain NULL-terminated strings
+            keys.insert(std::string(reinterpret_cast<const char *>(elem->data)));
+        }
+        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));
+        }
+        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((char const *) entry->key->data)] = std::string((char *) entry->value);
+        }
+        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) {
+        CxDataPtr key = {reinterpret_cast<const unsigned char *>(op.key), 1 + strlen(op.key)};
+        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());
+}