diff -r 2e6e9d9f2159 -r c9d008861178 tests/test_map.cpp --- /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 +#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(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 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(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(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 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(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(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