1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/test/test_map.cpp Fri May 27 12:59:32 2022 +0200 1.3 @@ -0,0 +1,170 @@ 1.4 +/* 1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 1.6 + * 1.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. 1.8 + * 1.9 + * Redistribution and use in source and binary forms, with or without 1.10 + * modification, are permitted provided that the following conditions are met: 1.11 + * 1.12 + * 1. Redistributions of source code must retain the above copyright 1.13 + * notice, this list of conditions and the following disclaimer. 1.14 + * 1.15 + * 2. Redistributions in binary form must reproduce the above copyright 1.16 + * notice, this list of conditions and the following disclaimer in the 1.17 + * documentation and/or other materials provided with the distribution. 1.18 + * 1.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 1.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 1.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 1.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 1.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 1.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 1.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 1.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 1.29 + * POSSIBILITY OF SUCH DAMAGE. 1.30 + */ 1.31 + 1.32 +#include "cx/hash_map.h" 1.33 +#include "cx/utils.h" 1.34 +#include "util_allocator.h" 1.35 + 1.36 +#include <gtest/gtest.h> 1.37 +#include <unordered_map> 1.38 +#include <unordered_set> 1.39 + 1.40 +struct map_operation { 1.41 + enum { 1.42 + put, rm 1.43 + } op; 1.44 + char const *key; 1.45 + char const *value; 1.46 +}; 1.47 + 1.48 +auto generate_map_operations() -> std::vector<map_operation> { 1.49 + return { 1.50 + {map_operation::put, "key 1", "test"}, 1.51 + {map_operation::put, "key 2", "blub"}, 1.52 + {map_operation::put, "key 3", "hallo"}, 1.53 + {map_operation::put, "key 2", "foobar"}, 1.54 + {map_operation::put, "key 4", "value 4"}, 1.55 + {map_operation::put, "key 5", "value 5"}, 1.56 + {map_operation::put, "key 6", "value 6"}, 1.57 + {map_operation::rm, "key 4", nullptr}, 1.58 + {map_operation::put, "key 7", "value 7"}, 1.59 + {map_operation::put, "key 8", "value 8"}, 1.60 + {map_operation::rm, "does not exist", nullptr}, 1.61 + {map_operation::put, "key 9", "value 9"}, 1.62 + {map_operation::put, "key 6", "other value"}, 1.63 + {map_operation::put, "key 7", "something else"}, 1.64 + {map_operation::rm, "key 8", nullptr}, 1.65 + {map_operation::rm, "key 2", nullptr}, 1.66 + {map_operation::put, "key 8", "new value"}, 1.67 + }; 1.68 +} 1.69 + 1.70 +static void verify_map_contents( 1.71 + CxMap *map, 1.72 + std::unordered_map<std::string, std::string> const &refmap 1.73 +) { 1.74 + // verify key iterator 1.75 + { 1.76 + auto keyiter = cxMapIteratorKeys(map); 1.77 + std::unordered_set<std::string> keys; 1.78 + cx_foreach(CxDataPtr*, elem, keyiter) { 1.79 + // we use that our test keys contain NULL-terminated strings 1.80 + keys.insert(std::string(reinterpret_cast<const char *>(elem->data))); 1.81 + } 1.82 + ASSERT_EQ(keys.size(), map->size); 1.83 + for (auto &&k: keys) { 1.84 + EXPECT_NE(refmap.find(k), refmap.end()); 1.85 + } 1.86 + } 1.87 + 1.88 + // verify value iterator 1.89 + { 1.90 + auto valiter = cxMapIteratorValues(map); 1.91 + std::unordered_set<std::string> values; // we use that the values in our test data are unique strings 1.92 + cx_foreach(char const*, elem, valiter) { 1.93 + values.insert(std::string(elem)); 1.94 + } 1.95 + ASSERT_EQ(values.size(), map->size); 1.96 + for (auto &&v: values) { 1.97 + EXPECT_NE(std::find_if(refmap.begin(), refmap.end(), 1.98 + [v](auto const &e) { return e.second == v; }), refmap.end()); 1.99 + } 1.100 + } 1.101 + 1.102 + // verify pair iterator 1.103 + { 1.104 + auto pairiter = cxMapIterator(map); 1.105 + std::unordered_map<std::string, std::string> pairs; 1.106 + cx_foreach(CxMapEntry*, entry, pairiter) { 1.107 + pairs[std::string((char const *) entry->key->data)] = std::string((char *) entry->value); 1.108 + } 1.109 + ASSERT_EQ(pairs.size(), refmap.size()); 1.110 + for (auto &&p: pairs) { 1.111 + ASSERT_EQ(p.second, refmap.at(p.first)); 1.112 + } 1.113 + } 1.114 +} 1.115 + 1.116 +TEST(CxHashMap, Create) { 1.117 + CxTestingAllocator allocator; 1.118 + auto map = cxHashMapCreate(&allocator, 0); 1.119 + auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map); 1.120 + EXPECT_GT(hmap->bucket_count, 0); 1.121 + cx_for_n(i, hmap->bucket_count) { 1.122 + EXPECT_EQ(hmap->buckets[i], nullptr); 1.123 + } 1.124 + EXPECT_EQ(map->size, 0); 1.125 + EXPECT_EQ(map->allocator, &allocator); 1.126 + 1.127 + cxMapDestroy(map); 1.128 + EXPECT_TRUE(allocator.verify()); 1.129 +} 1.130 + 1.131 +TEST(CxHashMap, BasicOperations) { 1.132 + // create the map 1.133 + CxTestingAllocator allocator; 1.134 + auto map = cxHashMapCreate(&allocator, 8); 1.135 + 1.136 + // create a reference map 1.137 + std::unordered_map<std::string, std::string> refmap; 1.138 + 1.139 + // generate operations 1.140 + auto ops = generate_map_operations(); 1.141 + 1.142 + // verify iterators for empty map 1.143 + verify_map_contents(map, refmap); 1.144 + 1.145 + // execute operations and verify results 1.146 + for (auto &&op: ops) { 1.147 + CxDataPtr key = {reinterpret_cast<const unsigned char *>(op.key), 1 + strlen(op.key)}; 1.148 + if (op.op == map_operation::put) { 1.149 + // execute a put operation and verify that the exact value can be read back 1.150 + refmap[std::string(op.key)] = std::string(op.value); 1.151 + int result = cxMapPut(map, key, (void *) op.value); 1.152 + EXPECT_EQ(result, 0); 1.153 + auto added = cxMapGet(map, key); 1.154 + EXPECT_EQ(memcmp(op.value, added, strlen(op.value)), 0); 1.155 + } else { 1.156 + // execute a remove and verify that the removed element was returned (or nullptr) 1.157 + auto found = refmap.find(op.key); 1.158 + auto removed = cxMapRemove(map, key); 1.159 + if (found == refmap.end()) { 1.160 + EXPECT_EQ(removed, nullptr); 1.161 + } else { 1.162 + EXPECT_EQ(std::string((char *) removed), found->second); 1.163 + refmap.erase(found); 1.164 + } 1.165 + } 1.166 + // compare the current map state with the reference map 1.167 + verify_map_contents(map, refmap); 1.168 + } 1.169 + 1.170 + // destroy the map and verify the memory (de)allocations 1.171 + cxMapDestroy(map); 1.172 + EXPECT_TRUE(allocator.verify()); 1.173 +}