diff -r ba5faf85dec6 -r bb18daa62d5f tests/test_map.cpp --- 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 -#include -#include - -struct map_operation { - enum { - put, rm - } op; - char const *key; - char const *value; -}; - -auto generate_map_operations() -> std::vector { - 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 const &refmap -) { - // verify key iterator - { - auto keyiter = cxMapIteratorKeys(map); - std::unordered_set keys; - cx_foreach(CxHashKey*, elem, keyiter) { - keys.insert(std::string(reinterpret_cast(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 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 pairs; - cx_foreach(CxMapEntry*, entry, pairiter) { - pairs[std::string(reinterpret_cast(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(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(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 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(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(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(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(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(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); -}