1.1 --- a/test/test_map.cpp Tue Feb 07 21:53:06 2023 +0100 1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 1.3 @@ -1,272 +0,0 @@ 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(CxHashKey*, elem, keyiter) { 1.79 - keys.insert(std::string(elem->data.cstr, elem->len)); 1.80 - } 1.81 - EXPECT_EQ(keyiter.index, map->size); 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 - EXPECT_EQ(valiter.index, map->size); 1.96 - ASSERT_EQ(values.size(), map->size); 1.97 - for (auto &&v: values) { 1.98 - EXPECT_NE(std::find_if(refmap.begin(), refmap.end(), 1.99 - [v](auto const &e) { return e.second == v; }), refmap.end()); 1.100 - } 1.101 - } 1.102 - 1.103 - // verify pair iterator 1.104 - { 1.105 - auto pairiter = cxMapIterator(map); 1.106 - std::unordered_map<std::string, std::string> pairs; 1.107 - cx_foreach(CxMapEntry*, entry, pairiter) { 1.108 - pairs[std::string(entry->key->data.cstr, entry->key->len)] = std::string((char *) entry->value); 1.109 - } 1.110 - EXPECT_EQ(pairiter.index, map->size); 1.111 - ASSERT_EQ(pairs.size(), refmap.size()); 1.112 - for (auto &&p: pairs) { 1.113 - ASSERT_EQ(p.second, refmap.at(p.first)); 1.114 - } 1.115 - } 1.116 -} 1.117 - 1.118 -TEST(CxHashMap, Create) { 1.119 - CxTestingAllocator allocator; 1.120 - auto map = cxHashMapCreate(&allocator, 0); 1.121 - auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map); 1.122 - EXPECT_GT(hmap->bucket_count, 0); 1.123 - cx_for_n(i, hmap->bucket_count) { 1.124 - EXPECT_EQ(hmap->buckets[i], nullptr); 1.125 - } 1.126 - EXPECT_EQ(map->size, 0); 1.127 - EXPECT_EQ(map->allocator, &allocator); 1.128 - 1.129 - cxMapDestroy(map); 1.130 - EXPECT_TRUE(allocator.verify()); 1.131 -} 1.132 - 1.133 -TEST(CxHashMap, BasicOperations) { 1.134 - // create the map 1.135 - CxTestingAllocator allocator; 1.136 - auto map = cxHashMapCreate(&allocator, 8); 1.137 - 1.138 - // create a reference map 1.139 - std::unordered_map<std::string, std::string> refmap; 1.140 - 1.141 - // generate operations 1.142 - auto ops = generate_map_operations(); 1.143 - 1.144 - // verify iterators for empty map 1.145 - verify_map_contents(map, refmap); 1.146 - 1.147 - // execute operations and verify results 1.148 - for (auto &&op: ops) { 1.149 - CxHashKey key = cx_hash_key_str(op.key); 1.150 - key.hash = 0; // force the hash map to compute the hash 1.151 - if (op.op == map_operation::put) { 1.152 - // execute a put operation and verify that the exact value can be read back 1.153 - refmap[std::string(op.key)] = std::string(op.value); 1.154 - int result = cxMapPut(map, key, (void *) op.value); 1.155 - EXPECT_EQ(result, 0); 1.156 - auto added = cxMapGet(map, key); 1.157 - EXPECT_EQ(memcmp(op.value, added, strlen(op.value)), 0); 1.158 - } else { 1.159 - // execute a remove and verify that the removed element was returned (or nullptr) 1.160 - auto found = refmap.find(op.key); 1.161 - auto removed = cxMapRemove(map, key); 1.162 - if (found == refmap.end()) { 1.163 - EXPECT_EQ(removed, nullptr); 1.164 - } else { 1.165 - EXPECT_EQ(std::string((char *) removed), found->second); 1.166 - refmap.erase(found); 1.167 - } 1.168 - } 1.169 - // compare the current map state with the reference map 1.170 - verify_map_contents(map, refmap); 1.171 - } 1.172 - 1.173 - // destroy the map and verify the memory (de)allocations 1.174 - cxMapDestroy(map); 1.175 - EXPECT_TRUE(allocator.verify()); 1.176 -} 1.177 - 1.178 -TEST(CxHashMap, RemoveViaIterator) { 1.179 - CxTestingAllocator allocator; 1.180 - auto map = cxHashMapCreate(&allocator, 4); 1.181 - 1.182 - cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1"); 1.183 - cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2"); 1.184 - cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3"); 1.185 - cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4"); 1.186 - cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5"); 1.187 - cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6"); 1.188 - 1.189 - auto iter = cxMapMutIterator(map); 1.190 - cx_foreach(CxMapEntry*, entry, iter) { 1.191 - if (entry->key->data.cstr[4] % 2 == 1) cxIteratorFlagRemoval(iter); 1.192 - } 1.193 - EXPECT_EQ(map->size, 3); 1.194 - EXPECT_EQ(iter.index, map->size); 1.195 - 1.196 - EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr); 1.197 - EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 2")), nullptr); 1.198 - EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr); 1.199 - EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 4")), nullptr); 1.200 - EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 5")), nullptr); 1.201 - EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 6")), nullptr); 1.202 - 1.203 - cxMapDestroy(map); 1.204 - EXPECT_TRUE(allocator.verify()); 1.205 -} 1.206 - 1.207 -TEST(CxHashMap, RehashNotRequired) { 1.208 - CxTestingAllocator allocator; 1.209 - auto map = cxHashMapCreate(&allocator, 8); 1.210 - 1.211 - cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1"); 1.212 - cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2"); 1.213 - cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3"); 1.214 - cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4"); 1.215 - cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5"); 1.216 - cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6"); 1.217 - 1.218 - // 6/8 does not exceed 0.75, therefore the function should not rehash 1.219 - int result = cxMapRehash(map); 1.220 - EXPECT_EQ(result, 0); 1.221 - EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 8); 1.222 - 1.223 - cxMapDestroy(map); 1.224 - EXPECT_TRUE(allocator.verify()); 1.225 -} 1.226 - 1.227 -TEST(CxHashMap, Rehash) { 1.228 - CxTestingAllocator allocator; 1.229 - auto map = cxHashMapCreate(&allocator, 8); 1.230 - 1.231 - cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1"); 1.232 - cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2"); 1.233 - cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3"); 1.234 - cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4"); 1.235 - cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5"); 1.236 - cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6"); 1.237 - cxMapPut(map, cx_hash_key_str("key 7"), (void *) "val 7"); 1.238 - 1.239 - int result = cxMapRehash(map); 1.240 - EXPECT_EQ(result, 0); 1.241 - EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 17); 1.242 - EXPECT_EQ(map->size, 7); 1.243 - 1.244 - EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 1")), "val 1"), 0); 1.245 - EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 2")), "val 2"), 0); 1.246 - EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 3")), "val 3"), 0); 1.247 - EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 4")), "val 4"), 0); 1.248 - EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 5")), "val 5"), 0); 1.249 - EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 6")), "val 6"), 0); 1.250 - EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 7")), "val 7"), 0); 1.251 - 1.252 - cxMapDestroy(map); 1.253 - EXPECT_TRUE(allocator.verify()); 1.254 -} 1.255 - 1.256 -TEST(CxHashMap, Clear) { 1.257 - CxTestingAllocator allocator; 1.258 - auto map = cxHashMapCreate(&allocator, 0); 1.259 - 1.260 - cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1"); 1.261 - cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2"); 1.262 - cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3"); 1.263 - 1.264 - EXPECT_EQ(map->size, 3); 1.265 - 1.266 - cxMapClear(map); 1.267 - 1.268 - EXPECT_EQ(map->size, 0); 1.269 - EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr); 1.270 - EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 2")), nullptr); 1.271 - EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr); 1.272 - 1.273 - cxMapDestroy(map); 1.274 - EXPECT_TRUE(allocator.verify()); 1.275 -} 1.276 \ No newline at end of file