diff -r d79fbd028e26 -r 3d19cae7e924 test/test_map.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 +#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(CxDataPtr*, elem, keyiter) { + // we use that our test keys contain NULL-terminated strings + keys.insert(std::string(reinterpret_cast(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 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 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(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) { + CxDataPtr key = {reinterpret_cast(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()); +}