1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tests/test_map.cpp Tue Feb 07 21:55:37 2023 +0100
1.3 @@ -0,0 +1,272 @@
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
