tests/test_map.cpp@612ed521b1c5
tests/test_map.cpp
Tue, 18 Apr 2023 19:15:50 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Tue, 18 Apr 2023 19:15:50 +0200
- changeset 687
- 612ed521b1c5
- parent 686
- 64919f63f059
- child 690
- 2c2304622981
- permissions
- -rw-r--r--
tweak rehash test to achieve missing coverage
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 "cx/string.h"
32 #include "util_allocator.h"
34 #include <gtest/gtest.h>
35 #include <unordered_map>
36 #include <unordered_set>
38 struct map_operation {
39 enum {
40 put, rm
41 } op;
42 char const *key;
43 char const *value;
44 };
46 auto generate_map_operations() -> std::vector<map_operation> {
47 return {
48 {map_operation::put, "key 1", "test"},
49 {map_operation::put, "key 2", "blub"},
50 {map_operation::put, "key 3", "hallo"},
51 {map_operation::put, "key 2", "foobar"},
52 {map_operation::put, "key 4", "value 4"},
53 {map_operation::put, "key 5", "value 5"},
54 {map_operation::put, "key 6", "value 6"},
55 {map_operation::rm, "key 4", nullptr},
56 {map_operation::put, "key 7", "value 7"},
57 {map_operation::put, "key 8", "value 8"},
58 {map_operation::rm, "does not exist", nullptr},
59 {map_operation::put, "key 9", "value 9"},
60 {map_operation::put, "key 6", "other value"},
61 {map_operation::put, "key 7", "something else"},
62 {map_operation::rm, "key 8", nullptr},
63 {map_operation::rm, "key 2", nullptr},
64 {map_operation::put, "key 8", "new value"},
65 };
66 }
68 static void verify_map_contents(
69 CxMap *map,
70 std::unordered_map<std::string, std::string> const &refmap
71 ) {
72 // verify key iterator
73 {
74 auto keyiter = cxMapIteratorKeys(map);
75 std::unordered_set<std::string> keys;
76 cx_foreach(CxHashKey*, elem, keyiter) {
77 keys.insert(std::string(elem->data.cstr, elem->len));
78 }
79 EXPECT_EQ(keyiter.index, map->size);
80 ASSERT_EQ(keys.size(), map->size);
81 for (auto &&k: keys) {
82 EXPECT_NE(refmap.find(k), refmap.end());
83 }
84 }
86 // verify value iterator
87 {
88 auto valiter = cxMapIteratorValues(map);
89 std::unordered_set<std::string> values; // we use that the values in our test data are unique strings
90 cx_foreach(char const*, elem, valiter) {
91 values.insert(std::string(elem));
92 }
93 EXPECT_EQ(valiter.index, map->size);
94 ASSERT_EQ(values.size(), map->size);
95 for (auto &&v: values) {
96 EXPECT_NE(std::find_if(refmap.begin(), refmap.end(),
97 [v](auto const &e) { return e.second == v; }), refmap.end());
98 }
99 }
101 // verify pair iterator
102 {
103 auto pairiter = cxMapIterator(map);
104 std::unordered_map<std::string, std::string> pairs;
105 cx_foreach(CxMapEntry*, entry, pairiter) {
106 pairs[std::string(entry->key->data.cstr, entry->key->len)] = std::string((char *) entry->value);
107 }
108 EXPECT_EQ(pairiter.index, map->size);
109 ASSERT_EQ(pairs.size(), refmap.size());
110 for (auto &&p: pairs) {
111 ASSERT_EQ(p.second, refmap.at(p.first));
112 }
113 }
114 }
116 TEST(CxHashMap, Create) {
117 CxTestingAllocator allocator;
118 auto map = cxHashMapCreate(&allocator, 1, 0);
119 auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);
120 EXPECT_GT(hmap->bucket_count, 0);
121 cx_for_n(i, hmap->bucket_count) {
122 EXPECT_EQ(hmap->buckets[i], nullptr);
123 }
124 EXPECT_EQ(map->item_size, 1);
125 EXPECT_EQ(map->size, 0);
126 EXPECT_EQ(map->allocator, &allocator);
127 EXPECT_FALSE(map->store_pointer);
128 EXPECT_EQ(map->cmpfunc, nullptr);
129 EXPECT_EQ(map->simple_destructor, nullptr);
130 EXPECT_EQ(map->advanced_destructor, nullptr);
131 EXPECT_EQ(map->destructor_data, nullptr);
132 cxMapStorePointers(map);
133 EXPECT_TRUE(map->store_pointer);
134 EXPECT_EQ(map->item_size, sizeof(void *));
135 cxMapStoreObjects(map);
136 EXPECT_FALSE(map->store_pointer);
138 cxMapDestroy(map);
139 EXPECT_TRUE(allocator.verify());
140 }
142 TEST(CxHashMap, CreateForStoringPointers) {
143 CxTestingAllocator allocator;
144 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);
145 auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);
146 EXPECT_GT(hmap->bucket_count, 0);
147 cx_for_n(i, hmap->bucket_count) {
148 EXPECT_EQ(hmap->buckets[i], nullptr);
149 }
150 EXPECT_EQ(map->size, 0);
151 EXPECT_EQ(map->allocator, &allocator);
152 EXPECT_TRUE(map->store_pointer);
153 EXPECT_EQ(map->item_size, sizeof(void *));
155 cxMapDestroy(map);
156 EXPECT_TRUE(allocator.verify());
157 }
159 TEST(CxHashMap, BasicOperations) {
160 // create the map
161 CxTestingAllocator allocator;
162 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 8);
164 // create a reference map
165 std::unordered_map<std::string, std::string> refmap;
167 // generate operations
168 auto ops = generate_map_operations();
170 // verify iterators for empty map
171 verify_map_contents(map, refmap);
173 // execute operations and verify results
174 for (auto &&op: ops) {
175 CxHashKey key = cx_hash_key_str(op.key);
176 key.hash = 0; // force the hash map to compute the hash
177 if (op.op == map_operation::put) {
178 // execute a put operation and verify that the exact value can be read back
179 refmap[std::string(op.key)] = std::string(op.value);
180 int result = cxMapPut(map, key, (void *) op.value);
181 EXPECT_EQ(result, 0);
182 auto added = cxMapGet(map, key);
183 EXPECT_EQ(memcmp(op.value, added, strlen(op.value)), 0);
184 } else {
185 // execute a remove and verify that the removed element was returned (or nullptr)
186 auto found = refmap.find(op.key);
187 auto removed = cxMapRemoveAndGet(map, key);
188 if (found == refmap.end()) {
189 EXPECT_EQ(removed, nullptr);
190 } else {
191 EXPECT_EQ(std::string((char *) removed), found->second);
192 refmap.erase(found);
193 }
194 }
195 // compare the current map state with the reference map
196 verify_map_contents(map, refmap);
197 }
199 // destroy the map and verify the memory (de)allocations
200 cxMapDestroy(map);
201 EXPECT_TRUE(allocator.verify());
202 }
204 TEST(CxHashMap, RemoveViaIterator) {
205 CxTestingAllocator allocator;
206 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 4);
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 auto iter = cxMapMutIterator(map);
216 cx_foreach(CxMapEntry*, entry, iter) {
217 if (entry->key->data.cstr[4] % 2 == 1) cxIteratorFlagRemoval(iter);
218 }
219 EXPECT_EQ(map->size, 3);
220 EXPECT_EQ(iter.index, map->size);
222 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);
223 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);
224 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);
225 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 4")), nullptr);
226 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 5")), nullptr);
227 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 6")), nullptr);
229 cxMapDestroy(map);
230 EXPECT_TRUE(allocator.verify());
231 }
233 TEST(CxHashMap, RehashNotRequired) {
234 CxTestingAllocator allocator;
235 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 8);
237 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
238 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
239 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
240 cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
241 cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
242 cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
244 // 6/8 does not exceed 0.75, therefore the function should not rehash
245 int result = cxMapRehash(map);
246 EXPECT_EQ(result, 0);
247 EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 8);
249 cxMapDestroy(map);
250 EXPECT_TRUE(allocator.verify());
251 }
253 TEST(CxHashMap, Rehash) {
254 CxTestingAllocator allocator;
255 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 7);
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");
260 cxMapPut(map, cx_hash_key_str("foo 4"), (void *) "val 4");
261 cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
262 cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
263 cxMapPut(map, cx_hash_key_str("bar 7"), (void *) "val 7");
264 cxMapPut(map, cx_hash_key_str("key 8"), (void *) "val 8");
265 cxMapPut(map, cx_hash_key_str("key 9"), (void *) "val 9");
266 cxMapPut(map, cx_hash_key_str("key 10"), (void *) "val 10");
268 int result = cxMapRehash(map);
269 EXPECT_EQ(result, 0);
270 EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 25);
271 EXPECT_EQ(map->size, 10);
273 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 1")), "val 1"), 0);
274 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 2")), "val 2"), 0);
275 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 3")), "val 3"), 0);
276 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("foo 4")), "val 4"), 0);
277 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 5")), "val 5"), 0);
278 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 6")), "val 6"), 0);
279 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("bar 7")), "val 7"), 0);
280 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 8")), "val 8"), 0);
281 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 9")), "val 9"), 0);
282 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 10")), "val 10"), 0);
284 cxMapDestroy(map);
285 EXPECT_TRUE(allocator.verify());
286 }
288 TEST(CxHashMap, Clear) {
289 CxTestingAllocator allocator;
290 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);
292 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
293 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
294 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
296 EXPECT_EQ(map->size, 3);
298 cxMapClear(map);
300 EXPECT_EQ(map->size, 0);
301 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);
302 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);
303 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);
305 cxMapDestroy(map);
306 EXPECT_TRUE(allocator.verify());
307 }
309 TEST(CxHashMap, StoreUcxStrings) {
310 // create the map
311 CxTestingAllocator allocator;
312 auto map = cxHashMapCreate(&allocator, sizeof(cxstring), 8);
314 // define some strings
315 auto s1 = CX_STR("this");
316 auto s2 = CX_STR("is");
317 auto s3 = CX_STR("a");
318 auto s4 = CX_STR("test");
319 auto s5 = CX_STR("setup");
321 // put them into the map
322 cxMapPut(map, cx_hash_key_str("s1"), &s1);
323 cxMapPut(map, cx_hash_key_str("s2"), &s2);
324 cxMapPut(map, cx_hash_key_str("s3"), &s3);
325 cxMapPut(map, cx_hash_key_str("s4"), &s4);
327 // overwrite a value
328 cxMapPut(map, cx_hash_key_str("s1"), &s5);
330 // look up a string
331 auto s3p = reinterpret_cast<cxstring *>(cxMapGet(map, cx_hash_key_str("s3")));
332 EXPECT_EQ(s3p->length, s3.length);
333 EXPECT_EQ(s3p->ptr, s3.ptr);
334 EXPECT_NE(s3p, &s3);
336 // remove a string
337 cxMapRemove(map, cx_hash_key_str("s2"));
339 // iterate
340 auto ref = std::vector{s5.ptr, s3.ptr, s4.ptr};
341 auto iter = cxMapIteratorValues(map);
342 cx_foreach(cxstring*, s, iter) {
343 auto found = std::find(ref.begin(), ref.end(), s->ptr);
344 ASSERT_NE(found, ref.end());
345 ref.erase(found);
346 }
347 EXPECT_EQ(ref.size(), 0);
349 cxMapDestroy(map);
350 EXPECT_TRUE(allocator.verify());
351 }
353 static void test_simple_destructor(void *data) {
354 strcpy((char *) data, "OK");
355 }
357 static void test_advanced_destructor(
358 [[maybe_unused]] void *unused,
359 void *data
360 ) {
361 strcpy((char *) data, "OK");
362 }
364 static void verify_any_destructor(CxMap *map) {
365 auto k1 = cx_hash_key_str("key 1");
366 auto k2 = cx_hash_key_str("key 2");
367 auto k3 = cx_hash_key_str("key 3");
368 auto k4 = cx_hash_key_str("key 4");
369 auto k5 = cx_hash_key_str("key 5");
371 char v1[] = "val 1";
372 char v2[] = "val 2";
373 char v3[] = "val 3";
374 char v4[] = "val 4";
375 char v5[] = "val 5";
377 cxMapPut(map, k1, (void *) v1);
378 cxMapPut(map, k2, (void *) v2);
379 cxMapPut(map, k3, (void *) v3);
380 cxMapPut(map, k4, (void *) v4);
382 cxMapRemove(map, k2);
383 auto r = cxMapRemoveAndGet(map, k3);
384 cxMapDetach(map, k1);
386 EXPECT_STREQ(v1, "val 1");
387 EXPECT_STREQ(v2, "OK");
388 EXPECT_STREQ(v3, "val 3");
389 EXPECT_STREQ(v4, "val 4");
390 EXPECT_STREQ(v5, "val 5");
391 EXPECT_EQ(r, v3);
393 cxMapClear(map);
395 EXPECT_STREQ(v1, "val 1");
396 EXPECT_STREQ(v2, "OK");
397 EXPECT_STREQ(v3, "val 3");
398 EXPECT_STREQ(v4, "OK");
399 EXPECT_STREQ(v5, "val 5");
401 cxMapPut(map, k1, (void *) v1);
402 cxMapPut(map, k3, (void *) v3);
403 cxMapPut(map, k5, (void *) v5);
405 {
406 auto iter = cxMapMutIteratorKeys(map);
407 cx_foreach(CxHashKey*, key, iter) {
408 if (key->data.cstr[4] == '1') cxIteratorFlagRemoval(iter);
409 }
410 }
411 {
412 auto iter = cxMapMutIteratorValues(map);
413 cx_foreach(char*, v, iter) {
414 if (v[4] == '5') cxIteratorFlagRemoval(iter);
415 }
416 }
418 EXPECT_STREQ(v1, "OK");
419 EXPECT_STREQ(v2, "OK");
420 EXPECT_STREQ(v3, "val 3");
421 EXPECT_STREQ(v4, "OK");
422 EXPECT_STREQ(v5, "OK");
424 v1[0] = v2[0] = v4[0] = v5[0] = 'c';
426 cxMapDestroy(map);
428 EXPECT_STREQ(v1, "cK");
429 EXPECT_STREQ(v2, "cK");
430 EXPECT_STREQ(v3, "OK");
431 EXPECT_STREQ(v4, "cK");
432 EXPECT_STREQ(v5, "cK");
433 }
435 TEST(CxHashMap, SimpleDestructor) {
436 CxTestingAllocator allocator;
437 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);
438 map->simple_destructor = test_simple_destructor;
439 verify_any_destructor(map);
440 EXPECT_TRUE(allocator.verify());
441 }
443 TEST(CxHashMap, AdvancedDestructor) {
444 CxTestingAllocator allocator;
445 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);
446 map->advanced_destructor = test_advanced_destructor;
447 verify_any_destructor(map);
448 EXPECT_TRUE(allocator.verify());
449 }
