--- a/tests/test_map.cpp Sat Dec 30 15:21:16 2023 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,521 +0,0 @@
-/*
- * 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 "cx/string.h"
-#include "util_allocator.h"
-#include "test_map_generics.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(reinterpret_cast<char const *>(elem->data), 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(reinterpret_cast<char const *>(entry->key->data), 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, 1, 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->item_size, 1);
- EXPECT_EQ(map->size, 0);
- EXPECT_EQ(map->allocator, &allocator);
- EXPECT_FALSE(map->store_pointer);
- EXPECT_EQ(map->cmpfunc, nullptr);
- EXPECT_EQ(map->simple_destructor, nullptr);
- EXPECT_EQ(map->advanced_destructor, nullptr);
- EXPECT_EQ(map->destructor_data, nullptr);
- cxMapStorePointers(map);
- EXPECT_TRUE(map->store_pointer);
- EXPECT_EQ(map->item_size, sizeof(void *));
- cxMapStoreObjects(map);
- EXPECT_FALSE(map->store_pointer);
-
- cxMapDestroy(map);
- EXPECT_TRUE(allocator.verify());
-}
-
-TEST(CxHashMap, CreateForStoringPointers) {
- CxTestingAllocator allocator;
- auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 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);
- EXPECT_TRUE(map->store_pointer);
- EXPECT_EQ(map->item_size, sizeof(void *));
-
- cxMapDestroy(map);
- EXPECT_TRUE(allocator.verify());
-}
-
-TEST(CxHashMap, BasicOperations) {
- // create the map
- CxTestingAllocator allocator;
- auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 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 = cxMapRemoveAndGet(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, CX_STORE_POINTERS, 4);
-
- cxMapPut(map, "key 1", (void *) "val 1");
- cxMapPut(map, "key 2", (void *) "val 2");
- cxMapPut(map, "key 3", (void *) "val 3");
- cxMapPut(map, "key 4", (void *) "val 4");
- cxMapPut(map, "key 5", (void *) "val 5");
- cxMapPut(map, "key 6", (void *) "val 6");
-
- auto iter = cxMapMutIterator(map);
- cx_foreach(CxMapEntry*, entry, iter) {
- if (reinterpret_cast<char const *>(entry->key->data)[4] % 2 == 1) cxIteratorFlagRemoval(iter);
- }
- EXPECT_EQ(map->size, 3);
- EXPECT_EQ(iter.index, map->size);
-
- EXPECT_EQ(cxMapGet(map, "key 1"), nullptr);
- EXPECT_NE(cxMapGet(map, "key 2"), nullptr);
- EXPECT_EQ(cxMapGet(map, "key 3"), nullptr);
- EXPECT_NE(cxMapGet(map, "key 4"), nullptr);
- EXPECT_EQ(cxMapGet(map, "key 5"), nullptr);
- EXPECT_NE(cxMapGet(map, "key 6"), nullptr);
-
- cxMapDestroy(map);
- EXPECT_TRUE(allocator.verify());
-}
-
-TEST(CxHashMap, RehashNotRequired) {
- CxTestingAllocator allocator;
- auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 8);
-
- cxMapPut(map, "key 1", (void *) "val 1");
- cxMapPut(map, "key 2", (void *) "val 2");
- cxMapPut(map, "key 3", (void *) "val 3");
- cxMapPut(map, "key 4", (void *) "val 4");
- cxMapPut(map, "key 5", (void *) "val 5");
- cxMapPut(map, "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, CX_STORE_POINTERS, 7);
-
- cxMapPut(map, "key 1", (void *) "val 1");
- cxMapPut(map, "key 2", (void *) "val 2");
- cxMapPut(map, "key 3", (void *) "val 3");
- cxMapPut(map, "foo 4", (void *) "val 4");
- cxMapPut(map, "key 5", (void *) "val 5");
- cxMapPut(map, "key 6", (void *) "val 6");
- cxMapPut(map, "bar 7", (void *) "val 7");
- cxMapPut(map, "key 8", (void *) "val 8");
- cxMapPut(map, "key 9", (void *) "val 9");
- cxMapPut(map, "key 10", (void *) "val 10");
-
- int result = cxMapRehash(map);
- EXPECT_EQ(result, 0);
- EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 25);
- EXPECT_EQ(map->size, 10);
-
- EXPECT_STREQ((char *) cxMapGet(map, "key 1"), "val 1");
- EXPECT_STREQ((char *) cxMapGet(map, "key 2"), "val 2");
- EXPECT_STREQ((char *) cxMapGet(map, "key 3"), "val 3");
- EXPECT_STREQ((char *) cxMapGet(map, "foo 4"), "val 4");
- EXPECT_STREQ((char *) cxMapGet(map, "key 5"), "val 5");
- EXPECT_STREQ((char *) cxMapGet(map, "key 6"), "val 6");
- EXPECT_STREQ((char *) cxMapGet(map, "bar 7"), "val 7");
- EXPECT_STREQ((char *) cxMapGet(map, "key 8"), "val 8");
- EXPECT_STREQ((char *) cxMapGet(map, "key 9"), "val 9");
- EXPECT_STREQ((char *) cxMapGet(map, "key 10"), "val 10");
-
- cxMapDestroy(map);
- EXPECT_TRUE(allocator.verify());
-}
-
-TEST(CxHashMap, Clear) {
- CxTestingAllocator allocator;
- auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);
-
- cxMapPut(map, "key 1", (void *) "val 1");
- cxMapPut(map, "key 2", (void *) "val 2");
- cxMapPut(map, "key 3", (void *) "val 3");
-
- EXPECT_EQ(map->size, 3);
-
- cxMapClear(map);
-
- EXPECT_EQ(map->size, 0);
- EXPECT_EQ(cxMapGet(map, "key 1"), nullptr);
- EXPECT_EQ(cxMapGet(map, "key 2"), nullptr);
- EXPECT_EQ(cxMapGet(map, "key 3"), nullptr);
-
- cxMapDestroy(map);
- EXPECT_TRUE(allocator.verify());
-}
-
-TEST(CxHashMap, StoreUcxStrings) {
- // create the map
- CxTestingAllocator allocator;
- auto map = cxHashMapCreate(&allocator, sizeof(cxstring), 8);
-
- // define some strings
- auto s1 = CX_STR("this");
- auto s2 = CX_STR("is");
- auto s3 = CX_STR("a");
- auto s4 = CX_STR("test");
- auto s5 = CX_STR("setup");
-
- // put them into the map
- cxMapPut(map, "s1", &s1);
- cxMapPut(map, "s2", &s2);
- cxMapPut(map, "s3", &s3);
- cxMapPut(map, "s4", &s4);
-
- // overwrite a value
- cxMapPut(map, "s1", &s5);
-
- // look up a string
- auto s3p = reinterpret_cast<cxstring *>(cxMapGet(map, "s3"));
- EXPECT_EQ(s3p->length, s3.length);
- EXPECT_EQ(s3p->ptr, s3.ptr);
- EXPECT_NE(s3p, &s3);
-
- // remove a string
- cxMapRemove(map, "s2");
-
- // iterate
- auto ref = std::vector{s5.ptr, s3.ptr, s4.ptr};
- auto iter = cxMapIteratorValues(map);
- cx_foreach(cxstring*, s, iter) {
- auto found = std::find(ref.begin(), ref.end(), s->ptr);
- ASSERT_NE(found, ref.end());
- ref.erase(found);
- }
- EXPECT_EQ(ref.size(), 0);
-
- cxMapDestroy(map);
- EXPECT_TRUE(allocator.verify());
-}
-
-static void test_simple_destructor(void *data) {
- strcpy((char *) data, "OK");
-}
-
-static void test_advanced_destructor(
- [[maybe_unused]] void *unused,
- void *data
-) {
- strcpy((char *) data, "OK");
-}
-
-static void verify_any_destructor(CxMap *map) {
- auto k1 = cx_hash_key_str("key 1");
- auto k2 = cx_hash_key_str("key 2");
- auto k3 = cx_hash_key_str("key 3");
- auto k4 = cx_hash_key_str("key 4");
- auto k5 = cx_hash_key_str("key 5");
-
- char v1[] = "val 1";
- char v2[] = "val 2";
- char v3[] = "val 3";
- char v4[] = "val 4";
- char v5[] = "val 5";
-
- cxMapPut(map, k1, (void *) v1);
- cxMapPut(map, k2, (void *) v2);
- cxMapPut(map, k3, (void *) v3);
- cxMapPut(map, k4, (void *) v4);
-
- cxMapRemove(map, k2);
- auto r = cxMapRemoveAndGet(map, k3);
- cxMapDetach(map, k1);
-
- EXPECT_STREQ(v1, "val 1");
- EXPECT_STREQ(v2, "OK");
- EXPECT_STREQ(v3, "val 3");
- EXPECT_STREQ(v4, "val 4");
- EXPECT_STREQ(v5, "val 5");
- EXPECT_EQ(r, v3);
-
- cxMapClear(map);
-
- EXPECT_STREQ(v1, "val 1");
- EXPECT_STREQ(v2, "OK");
- EXPECT_STREQ(v3, "val 3");
- EXPECT_STREQ(v4, "OK");
- EXPECT_STREQ(v5, "val 5");
-
- cxMapPut(map, k1, (void *) v1);
- cxMapPut(map, k3, (void *) v3);
- cxMapPut(map, k5, (void *) v5);
-
- {
- auto iter = cxMapMutIteratorKeys(map);
- cx_foreach(CxHashKey*, key, iter) {
- if (reinterpret_cast<char const *>(key->data)[4] == '1') cxIteratorFlagRemoval(iter);
- }
- }
- {
- auto iter = cxMapMutIteratorValues(map);
- cx_foreach(char*, v, iter) {
- if (v[4] == '5') cxIteratorFlagRemoval(iter);
- }
- }
-
- EXPECT_STREQ(v1, "OK");
- EXPECT_STREQ(v2, "OK");
- EXPECT_STREQ(v3, "val 3");
- EXPECT_STREQ(v4, "OK");
- EXPECT_STREQ(v5, "OK");
-
- v1[0] = v2[0] = v4[0] = v5[0] = 'c';
-
- cxMapDestroy(map);
-
- EXPECT_STREQ(v1, "cK");
- EXPECT_STREQ(v2, "cK");
- EXPECT_STREQ(v3, "OK");
- EXPECT_STREQ(v4, "cK");
- EXPECT_STREQ(v5, "cK");
-}
-
-TEST(CxHashMap, SimpleDestructor) {
- CxTestingAllocator allocator;
- auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);
- map->simple_destructor = test_simple_destructor;
- verify_any_destructor(map);
- EXPECT_TRUE(allocator.verify());
-}
-
-TEST(CxHashMap, AdvancedDestructor) {
- CxTestingAllocator allocator;
- auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);
- map->advanced_destructor = test_advanced_destructor;
- verify_any_destructor(map);
- EXPECT_TRUE(allocator.verify());
-}
-
-TEST(CxHashMap, Generics) {
- CxTestingAllocator allocator;
- auto map = test_map_generics_step_1(&allocator);
-
- EXPECT_EQ(map->size, 3);
- EXPECT_STREQ((char *) cxMapGet(map, "test"), "test");
- EXPECT_STREQ((char *) cxMapGet(map, "foo"), "bar");
- EXPECT_STREQ((char *) cxMapGet(map, "hallo"), "welt");
-
- test_map_generics_step_2(map);
-
- EXPECT_EQ(map->size, 2);
- EXPECT_STREQ((char *) cxMapGet(map, "key"), "value");
- EXPECT_STREQ((char *) cxMapGet(map, "foo"), "bar");
-
- test_map_generics_step_3(map);
-
- EXPECT_EQ(map->size, 0);
-
- cxMapDestroy(map);
- EXPECT_TRUE(allocator.verify());
-}
-
-TEST(EmptyMap, Size) {
- auto map = cxEmptyMap;
-
- EXPECT_EQ(map->size, 0);
-}
-
-TEST(EmptyMap, Iterator) {
- auto map = cxEmptyMap;
-
- auto it1 = cxMapIterator(map);
- auto it2 = cxMapIteratorValues(map);
- auto it3 = cxMapIteratorKeys(map);
- auto it4 = cxMapMutIterator(map);
- auto it5 = cxMapMutIteratorValues(map);
- auto it6 = cxMapMutIteratorKeys(map);
-
- EXPECT_FALSE(cxIteratorValid(it1));
- EXPECT_FALSE(cxIteratorValid(it2));
- EXPECT_FALSE(cxIteratorValid(it3));
- EXPECT_FALSE(cxIteratorValid(it4));
- EXPECT_FALSE(cxIteratorValid(it5));
- EXPECT_FALSE(cxIteratorValid(it6));
-
- int c = 0;
- cx_foreach(void*, data, it1) c++;
- cx_foreach(void*, data, it2) c++;
- cx_foreach(void*, data, it3) c++;
- cx_foreach(void*, data, it4) c++;
- cx_foreach(void*, data, it5) c++;
- cx_foreach(void*, data, it6) c++;
- EXPECT_EQ(c, 0);
-}
-
-TEST(EmptyMap, NoOps) {
- auto map = cxEmptyMap;
-
- ASSERT_NO_FATAL_FAILURE(cxMapClear(map));
- ASSERT_NO_FATAL_FAILURE(cxMapDestroy(map));
-}
-
-TEST(EmptyMap, Get) {
- auto map = cxEmptyMap;
-
- CxHashKey key = cx_hash_key_str("test");
- EXPECT_EQ(cxMapGet(map, key), nullptr);
-}