test/test_map.cpp@ac5e7f789048
test/test_map.cpp
Sat, 26 Nov 2022 16:58:41 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Sat, 26 Nov 2022 16:58:41 +0100
- changeset 630
- ac5e7f789048
- parent 604
- 056e5f592d84
- permissions
- -rw-r--r--
separate iterators and mutating iterators
Trade tons of code duplication for const-correctness.
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
29 #include "cx/hash_map.h"
30 #include "cx/utils.h"
31 #include "util_allocator.h"
33 #include <gtest/gtest.h>
34 #include <unordered_map>
35 #include <unordered_set>
37 struct map_operation {
38 enum {
39 put, rm
40 } op;
41 char const *key;
42 char const *value;
43 };
45 auto generate_map_operations() -> std::vector<map_operation> {
46 return {
47 {map_operation::put, "key 1", "test"},
48 {map_operation::put, "key 2", "blub"},
49 {map_operation::put, "key 3", "hallo"},
50 {map_operation::put, "key 2", "foobar"},
51 {map_operation::put, "key 4", "value 4"},
52 {map_operation::put, "key 5", "value 5"},
53 {map_operation::put, "key 6", "value 6"},
54 {map_operation::rm, "key 4", nullptr},
55 {map_operation::put, "key 7", "value 7"},
56 {map_operation::put, "key 8", "value 8"},
57 {map_operation::rm, "does not exist", nullptr},
58 {map_operation::put, "key 9", "value 9"},
59 {map_operation::put, "key 6", "other value"},
60 {map_operation::put, "key 7", "something else"},
61 {map_operation::rm, "key 8", nullptr},
62 {map_operation::rm, "key 2", nullptr},
63 {map_operation::put, "key 8", "new value"},
64 };
65 }
67 static void verify_map_contents(
68 CxMap *map,
69 std::unordered_map<std::string, std::string> const &refmap
70 ) {
71 // verify key iterator
72 {
73 auto keyiter = cxMapIteratorKeys(map);
74 std::unordered_set<std::string> keys;
75 cx_foreach(CxHashKey*, elem, keyiter) {
76 keys.insert(std::string(elem->data.cstr, elem->len));
77 }
78 EXPECT_EQ(keyiter.index, map->size);
79 ASSERT_EQ(keys.size(), map->size);
80 for (auto &&k: keys) {
81 EXPECT_NE(refmap.find(k), refmap.end());
82 }
83 }
85 // verify value iterator
86 {
87 auto valiter = cxMapIteratorValues(map);
88 std::unordered_set<std::string> values; // we use that the values in our test data are unique strings
89 cx_foreach(char const*, elem, valiter) {
90 values.insert(std::string(elem));
91 }
92 EXPECT_EQ(valiter.index, map->size);
93 ASSERT_EQ(values.size(), map->size);
94 for (auto &&v: values) {
95 EXPECT_NE(std::find_if(refmap.begin(), refmap.end(),
96 [v](auto const &e) { return e.second == v; }), refmap.end());
97 }
98 }
100 // verify pair iterator
101 {
102 auto pairiter = cxMapIterator(map);
103 std::unordered_map<std::string, std::string> pairs;
104 cx_foreach(CxMapEntry*, entry, pairiter) {
105 pairs[std::string(entry->key->data.cstr, entry->key->len)] = std::string((char *) entry->value);
106 }
107 EXPECT_EQ(pairiter.index, map->size);
108 ASSERT_EQ(pairs.size(), refmap.size());
109 for (auto &&p: pairs) {
110 ASSERT_EQ(p.second, refmap.at(p.first));
111 }
112 }
113 }
115 TEST(CxHashMap, Create) {
116 CxTestingAllocator allocator;
117 auto map = cxHashMapCreate(&allocator, 0);
118 auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);
119 EXPECT_GT(hmap->bucket_count, 0);
120 cx_for_n(i, hmap->bucket_count) {
121 EXPECT_EQ(hmap->buckets[i], nullptr);
122 }
123 EXPECT_EQ(map->size, 0);
124 EXPECT_EQ(map->allocator, &allocator);
126 cxMapDestroy(map);
127 EXPECT_TRUE(allocator.verify());
128 }
130 TEST(CxHashMap, BasicOperations) {
131 // create the map
132 CxTestingAllocator allocator;
133 auto map = cxHashMapCreate(&allocator, 8);
135 // create a reference map
136 std::unordered_map<std::string, std::string> refmap;
138 // generate operations
139 auto ops = generate_map_operations();
141 // verify iterators for empty map
142 verify_map_contents(map, refmap);
144 // execute operations and verify results
145 for (auto &&op: ops) {
146 CxHashKey key = cx_hash_key_str(op.key);
147 key.hash = 0; // force the hash map to compute the hash
148 if (op.op == map_operation::put) {
149 // execute a put operation and verify that the exact value can be read back
150 refmap[std::string(op.key)] = std::string(op.value);
151 int result = cxMapPut(map, key, (void *) op.value);
152 EXPECT_EQ(result, 0);
153 auto added = cxMapGet(map, key);
154 EXPECT_EQ(memcmp(op.value, added, strlen(op.value)), 0);
155 } else {
156 // execute a remove and verify that the removed element was returned (or nullptr)
157 auto found = refmap.find(op.key);
158 auto removed = cxMapRemove(map, key);
159 if (found == refmap.end()) {
160 EXPECT_EQ(removed, nullptr);
161 } else {
162 EXPECT_EQ(std::string((char *) removed), found->second);
163 refmap.erase(found);
164 }
165 }
166 // compare the current map state with the reference map
167 verify_map_contents(map, refmap);
168 }
170 // destroy the map and verify the memory (de)allocations
171 cxMapDestroy(map);
172 EXPECT_TRUE(allocator.verify());
173 }
175 TEST(CxHashMap, RemoveViaIterator) {
176 CxTestingAllocator allocator;
177 auto map = cxHashMapCreate(&allocator, 4);
179 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
180 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
181 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
182 cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
183 cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
184 cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
186 auto iter = cxMapMutIterator(map);
187 cx_foreach(CxMapEntry*, entry, iter) {
188 if (entry->key->data.cstr[4] % 2 == 1) cxIteratorFlagRemoval(iter);
189 }
190 EXPECT_EQ(map->size, 3);
191 EXPECT_EQ(iter.index, map->size);
193 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);
194 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);
195 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);
196 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 4")), nullptr);
197 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 5")), nullptr);
198 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 6")), nullptr);
200 cxMapDestroy(map);
201 EXPECT_TRUE(allocator.verify());
202 }
204 TEST(CxHashMap, RehashNotRequired) {
205 CxTestingAllocator allocator;
206 auto map = cxHashMapCreate(&allocator, 8);
208 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
209 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
210 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
211 cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
212 cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
213 cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
215 // 6/8 does not exceed 0.75, therefore the function should not rehash
216 int result = cxMapRehash(map);
217 EXPECT_EQ(result, 0);
218 EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 8);
220 cxMapDestroy(map);
221 EXPECT_TRUE(allocator.verify());
222 }
224 TEST(CxHashMap, Rehash) {
225 CxTestingAllocator allocator;
226 auto map = cxHashMapCreate(&allocator, 8);
228 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
229 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
230 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
231 cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
232 cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
233 cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
234 cxMapPut(map, cx_hash_key_str("key 7"), (void *) "val 7");
236 int result = cxMapRehash(map);
237 EXPECT_EQ(result, 0);
238 EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 17);
239 EXPECT_EQ(map->size, 7);
241 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 1")), "val 1"), 0);
242 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 2")), "val 2"), 0);
243 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 3")), "val 3"), 0);
244 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 4")), "val 4"), 0);
245 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 5")), "val 5"), 0);
246 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 6")), "val 6"), 0);
247 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 7")), "val 7"), 0);
249 cxMapDestroy(map);
250 EXPECT_TRUE(allocator.verify());
251 }
253 TEST(CxHashMap, Clear) {
254 CxTestingAllocator allocator;
255 auto map = cxHashMapCreate(&allocator, 0);
257 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
258 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
259 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
261 EXPECT_EQ(map->size, 3);
263 cxMapClear(map);
265 EXPECT_EQ(map->size, 0);
266 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);
267 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);
268 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);
270 cxMapDestroy(map);
271 EXPECT_TRUE(allocator.verify());
272 }
