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 */
28
29 #include "cx/hash_map.h"
30 #include "cx/utils.h"
31 #include "cx/string.h"
32 #include "util_allocator.h"
33 #include "test_map_generics.h"
34
35 #include <gtest/gtest.h>
36 #include <unordered_map>
37 #include <unordered_set>
38
39 struct map_operation {
40 enum {
41 put, rm
42 } op;
43 char const *key;
44 char const *value;
45 };
46
47 auto generate_map_operations() -> std::vector<map_operation> {
48 return {
49 {map_operation::put, "key 1", "test"},
50 {map_operation::put, "key 2", "blub"},
51 {map_operation::put, "key 3", "hallo"},
52 {map_operation::put, "key 2", "foobar"},
53 {map_operation::put, "key 4", "value 4"},
54 {map_operation::put, "key 5", "value 5"},
55 {map_operation::put, "key 6", "value 6"},
56 {map_operation::rm, "key 4", nullptr},
57 {map_operation::put, "key 7", "value 7"},
58 {map_operation::put, "key 8", "value 8"},
59 {map_operation::rm, "does not exist", nullptr},
60 {map_operation::put, "key 9", "value 9"},
61 {map_operation::put, "key 6", "other value"},
62 {map_operation::put, "key 7", "something else"},
63 {map_operation::rm, "key 8", nullptr},
64 {map_operation::rm, "key 2", nullptr},
65 {map_operation::put, "key 8", "new value"},
66 };
67 }
68
69 static void verify_map_contents(
70 CxMap *map,
71 std::unordered_map<std::string, std::string> const &refmap
72 ) {
73 // verify key iterator
74 {
75 auto keyiter = cxMapIteratorKeys(map);
76 std::unordered_set<std::string> keys;
77 cx_foreach(CxHashKey*, elem, keyiter) {
78 keys.insert(std::string(reinterpret_cast<char const *>(elem->data), elem->len));
79 }
80 EXPECT_EQ(keyiter.index, map->size);
81 ASSERT_EQ(keys.size(), map->size);
82 for (auto &&k: keys) {
83 EXPECT_NE(refmap.find(k), refmap.end());
84 }
85 }
86
87 // verify value iterator
88 {
89 auto valiter = cxMapIteratorValues(map);
90 std::unordered_set<std::string> values; // we use that the values in our test data are unique strings
91 cx_foreach(char const*, elem, valiter) {
92 values.insert(std::string(elem));
93 }
94 EXPECT_EQ(valiter.index, map->size);
95 ASSERT_EQ(values.size(), map->size);
96 for (auto &&v: values) {
97 EXPECT_NE(std::find_if(refmap.begin(), refmap.end(),
98 [v](auto const &e) { return e.second == v; }), refmap.end());
99 }
100 }
101
102 // verify pair iterator
103 {
104 auto pairiter = cxMapIterator(map);
105 std::unordered_map<std::string, std::string> pairs;
106 cx_foreach(CxMapEntry*, entry, pairiter) {
107 pairs[std::string(reinterpret_cast<char const *>(entry->key->data), entry->key->len)] = std::string(
108 (char *) entry->value);
109 }
110 EXPECT_EQ(pairiter.index, map->size);
111 ASSERT_EQ(pairs.size(), refmap.size());
112 for (auto &&p: pairs) {
113 ASSERT_EQ(p.second, refmap.at(p.first));
114 }
115 }
116 }
117
118 TEST(CxHashMap, Create) {
119 CxTestingAllocator allocator;
120 auto map = cxHashMapCreate(&allocator, 1, 0);
121 auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);
122 EXPECT_GT(hmap->bucket_count, 0);
123 cx_for_n(i, hmap->bucket_count) {
124 EXPECT_EQ(hmap->buckets[i], nullptr);
125 }
126 EXPECT_EQ(map->item_size, 1);
127 EXPECT_EQ(map->size, 0);
128 EXPECT_EQ(map->allocator, &allocator);
129 EXPECT_FALSE(map->store_pointer);
130 EXPECT_EQ(map->cmpfunc, nullptr);
131 EXPECT_EQ(map->simple_destructor, nullptr);
132 EXPECT_EQ(map->advanced_destructor, nullptr);
133 EXPECT_EQ(map->destructor_data, nullptr);
134 cxMapStorePointers(map);
135 EXPECT_TRUE(map->store_pointer);
136 EXPECT_EQ(map->item_size, sizeof(void *));
137 cxMapStoreObjects(map);
138 EXPECT_FALSE(map->store_pointer);
139
140 cxMapDestroy(map);
141 EXPECT_TRUE(allocator.verify());
142 }
143
144 TEST(CxHashMap, CreateForStoringPointers) {
145 CxTestingAllocator allocator;
146 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);
147 auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);
148 EXPECT_GT(hmap->bucket_count, 0);
149 cx_for_n(i, hmap->bucket_count) {
150 EXPECT_EQ(hmap->buckets[i], nullptr);
151 }
152 EXPECT_EQ(map->size, 0);
153 EXPECT_EQ(map->allocator, &allocator);
154 EXPECT_TRUE(map->store_pointer);
155 EXPECT_EQ(map->item_size, sizeof(void *));
156
157 cxMapDestroy(map);
158 EXPECT_TRUE(allocator.verify());
159 }
160
161 TEST(CxHashMap, BasicOperations) {
162 // create the map
163 CxTestingAllocator allocator;
164 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 8);
165
166 // create a reference map
167 std::unordered_map<std::string, std::string> refmap;
168
169 // generate operations
170 auto ops = generate_map_operations();
171
172 // verify iterators for empty map
173 verify_map_contents(map, refmap);
174
175 // execute operations and verify results
176 for (auto &&op: ops) {
177 CxHashKey key = cx_hash_key_str(op.key);
178 key.hash = 0; // force the hash map to compute the hash
179 if (op.op == map_operation::put) {
180 // execute a put operation and verify that the exact value can be read back
181 refmap[std::string(op.key)] = std::string(op.value);
182 int result = cxMapPut(map, key, (void *) op.value);
183 EXPECT_EQ(result, 0);
184 auto added = cxMapGet(map, key);
185 EXPECT_EQ(memcmp(op.value, added, strlen(op.value)), 0);
186 } else {
187 // execute a remove and verify that the removed element was returned (or nullptr)
188 auto found = refmap.find(op.key);
189 auto removed = cxMapRemoveAndGet(map, key);
190 if (found == refmap.end()) {
191 EXPECT_EQ(removed, nullptr);
192 } else {
193 EXPECT_EQ(std::string((char *) removed), found->second);
194 refmap.erase(found);
195 }
196 }
197 // compare the current map state with the reference map
198 verify_map_contents(map, refmap);
199 }
200
201 // destroy the map and verify the memory (de)allocations
202 cxMapDestroy(map);
203 EXPECT_TRUE(allocator.verify());
204 }
205
206 TEST(CxHashMap, RemoveViaIterator) {
207 CxTestingAllocator allocator;
208 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 4);
209
210 cxMapPut(map, "key 1", (void *) "val 1");
211 cxMapPut(map, "key 2", (void *) "val 2");
212 cxMapPut(map, "key 3", (void *) "val 3");
213 cxMapPut(map, "key 4", (void *) "val 4");
214 cxMapPut(map, "key 5", (void *) "val 5");
215 cxMapPut(map, "key 6", (void *) "val 6");
216
217 auto iter = cxMapMutIterator(map);
218 cx_foreach(CxMapEntry*, entry, iter) {
219 if (reinterpret_cast<char const *>(entry->key->data)[4] % 2 == 1) cxIteratorFlagRemoval(iter);
220 }
221 EXPECT_EQ(map->size, 3);
222 EXPECT_EQ(iter.index, map->size);
223
224 EXPECT_EQ(cxMapGet(map, "key 1"), nullptr);
225 EXPECT_NE(cxMapGet(map, "key 2"), nullptr);
226 EXPECT_EQ(cxMapGet(map, "key 3"), nullptr);
227 EXPECT_NE(cxMapGet(map, "key 4"), nullptr);
228 EXPECT_EQ(cxMapGet(map, "key 5"), nullptr);
229 EXPECT_NE(cxMapGet(map, "key 6"), nullptr);
230
231 cxMapDestroy(map);
232 EXPECT_TRUE(allocator.verify());
233 }
234
235 TEST(CxHashMap, RehashNotRequired) {
236 CxTestingAllocator allocator;
237 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 8);
238
239 cxMapPut(map, "key 1", (void *) "val 1");
240 cxMapPut(map, "key 2", (void *) "val 2");
241 cxMapPut(map, "key 3", (void *) "val 3");
242 cxMapPut(map, "key 4", (void *) "val 4");
243 cxMapPut(map, "key 5", (void *) "val 5");
244 cxMapPut(map, "key 6", (void *) "val 6");
245
246 // 6/8 does not exceed 0.75, therefore the function should not rehash
247 int result = cxMapRehash(map);
248 EXPECT_EQ(result, 0);
249 EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 8);
250
251 cxMapDestroy(map);
252 EXPECT_TRUE(allocator.verify());
253 }
254
255 TEST(CxHashMap, Rehash) {
256 CxTestingAllocator allocator;
257 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 7);
258
259 cxMapPut(map, "key 1", (void *) "val 1");
260 cxMapPut(map, "key 2", (void *) "val 2");
261 cxMapPut(map, "key 3", (void *) "val 3");
262 cxMapPut(map, "foo 4", (void *) "val 4");
263 cxMapPut(map, "key 5", (void *) "val 5");
264 cxMapPut(map, "key 6", (void *) "val 6");
265 cxMapPut(map, "bar 7", (void *) "val 7");
266 cxMapPut(map, "key 8", (void *) "val 8");
267 cxMapPut(map, "key 9", (void *) "val 9");
268 cxMapPut(map, "key 10", (void *) "val 10");
269
270 int result = cxMapRehash(map);
271 EXPECT_EQ(result, 0);
272 EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 25);
273 EXPECT_EQ(map->size, 10);
274
275 EXPECT_STREQ((char *) cxMapGet(map, "key 1"), "val 1");
276 EXPECT_STREQ((char *) cxMapGet(map, "key 2"), "val 2");
277 EXPECT_STREQ((char *) cxMapGet(map, "key 3"), "val 3");
278 EXPECT_STREQ((char *) cxMapGet(map, "foo 4"), "val 4");
279 EXPECT_STREQ((char *) cxMapGet(map, "key 5"), "val 5");
280 EXPECT_STREQ((char *) cxMapGet(map, "key 6"), "val 6");
281 EXPECT_STREQ((char *) cxMapGet(map, "bar 7"), "val 7");
282 EXPECT_STREQ((char *) cxMapGet(map, "key 8"), "val 8");
283 EXPECT_STREQ((char *) cxMapGet(map, "key 9"), "val 9");
284 EXPECT_STREQ((char *) cxMapGet(map, "key 10"), "val 10");
285
286 cxMapDestroy(map);
287 EXPECT_TRUE(allocator.verify());
288 }
289
290 TEST(CxHashMap, Clear) {
291 CxTestingAllocator allocator;
292 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);
293
294 cxMapPut(map, "key 1", (void *) "val 1");
295 cxMapPut(map, "key 2", (void *) "val 2");
296 cxMapPut(map, "key 3", (void *) "val 3");
297
298 EXPECT_EQ(map->size, 3);
299
300 cxMapClear(map);
301
302 EXPECT_EQ(map->size, 0);
303 EXPECT_EQ(cxMapGet(map, "key 1"), nullptr);
304 EXPECT_EQ(cxMapGet(map, "key 2"), nullptr);
305 EXPECT_EQ(cxMapGet(map, "key 3"), nullptr);
306
307 cxMapDestroy(map);
308 EXPECT_TRUE(allocator.verify());
309 }
310
311 TEST(CxHashMap, StoreUcxStrings) {
312 // create the map
313 CxTestingAllocator allocator;
314 auto map = cxHashMapCreate(&allocator, sizeof(cxstring), 8);
315
316 // define some strings
317 auto s1 = CX_STR("this");
318 auto s2 = CX_STR("is");
319 auto s3 = CX_STR("a");
320 auto s4 = CX_STR("test");
321 auto s5 = CX_STR("setup");
322
323 // put them into the map
324 cxMapPut(map, "s1", &s1);
325 cxMapPut(map, "s2", &s2);
326 cxMapPut(map, "s3", &s3);
327 cxMapPut(map, "s4", &s4);
328
329 // overwrite a value
330 cxMapPut(map, "s1", &s5);
331
332 // look up a string
333 auto s3p = reinterpret_cast<cxstring *>(cxMapGet(map, "s3"));
334 EXPECT_EQ(s3p->length, s3.length);
335 EXPECT_EQ(s3p->ptr, s3.ptr);
336 EXPECT_NE(s3p, &s3);
337
338 // remove a string
339 cxMapRemove(map, "s2");
340
341 // iterate
342 auto ref = std::vector{s5.ptr, s3.ptr, s4.ptr};
343 auto iter = cxMapIteratorValues(map);
344 cx_foreach(cxstring*, s, iter) {
345 auto found = std::find(ref.begin(), ref.end(), s->ptr);
346 ASSERT_NE(found, ref.end());
347 ref.erase(found);
348 }
349 EXPECT_EQ(ref.size(), 0);
350
351 cxMapDestroy(map);
352 EXPECT_TRUE(allocator.verify());
353 }
354
355 static void test_simple_destructor(void *data) {
356 strcpy((char *) data, "OK");
357 }
358
359 static void test_advanced_destructor(
360 [[maybe_unused]] void *unused,
361 void *data
362 ) {
363 strcpy((char *) data, "OK");
364 }
365
366 static void verify_any_destructor(CxMap *map) {
367 auto k1 = cx_hash_key_str("key 1");
368 auto k2 = cx_hash_key_str("key 2");
369 auto k3 = cx_hash_key_str("key 3");
370 auto k4 = cx_hash_key_str("key 4");
371 auto k5 = cx_hash_key_str("key 5");
372
373 char v1[] = "val 1";
374 char v2[] = "val 2";
375 char v3[] = "val 3";
376 char v4[] = "val 4";
377 char v5[] = "val 5";
378
379 cxMapPut(map, k1, (void *) v1);
380 cxMapPut(map, k2, (void *) v2);
381 cxMapPut(map, k3, (void *) v3);
382 cxMapPut(map, k4, (void *) v4);
383
384 cxMapRemove(map, k2);
385 auto r = cxMapRemoveAndGet(map, k3);
386 cxMapDetach(map, k1);
387
388 EXPECT_STREQ(v1, "val 1");
389 EXPECT_STREQ(v2, "OK");
390 EXPECT_STREQ(v3, "val 3");
391 EXPECT_STREQ(v4, "val 4");
392 EXPECT_STREQ(v5, "val 5");
393 EXPECT_EQ(r, v3);
394
395 cxMapClear(map);
396
397 EXPECT_STREQ(v1, "val 1");
398 EXPECT_STREQ(v2, "OK");
399 EXPECT_STREQ(v3, "val 3");
400 EXPECT_STREQ(v4, "OK");
401 EXPECT_STREQ(v5, "val 5");
402
403 cxMapPut(map, k1, (void *) v1);
404 cxMapPut(map, k3, (void *) v3);
405 cxMapPut(map, k5, (void *) v5);
406
407 {
408 auto iter = cxMapMutIteratorKeys(map);
409 cx_foreach(CxHashKey*, key, iter) {
410 if (reinterpret_cast<char const *>(key->data)[4] == '1') cxIteratorFlagRemoval(iter);
411 }
412 }
413 {
414 auto iter = cxMapMutIteratorValues(map);
415 cx_foreach(char*, v, iter) {
416 if (v[4] == '5') cxIteratorFlagRemoval(iter);
417 }
418 }
419
420 EXPECT_STREQ(v1, "OK");
421 EXPECT_STREQ(v2, "OK");
422 EXPECT_STREQ(v3, "val 3");
423 EXPECT_STREQ(v4, "OK");
424 EXPECT_STREQ(v5, "OK");
425
426 v1[0] = v2[0] = v4[0] = v5[0] = 'c';
427
428 cxMapDestroy(map);
429
430 EXPECT_STREQ(v1, "cK");
431 EXPECT_STREQ(v2, "cK");
432 EXPECT_STREQ(v3, "OK");
433 EXPECT_STREQ(v4, "cK");
434 EXPECT_STREQ(v5, "cK");
435 }
436
437 TEST(CxHashMap, SimpleDestructor) {
438 CxTestingAllocator allocator;
439 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);
440 map->simple_destructor = test_simple_destructor;
441 verify_any_destructor(map);
442 EXPECT_TRUE(allocator.verify());
443 }
444
445 TEST(CxHashMap, AdvancedDestructor) {
446 CxTestingAllocator allocator;
447 auto map = cxHashMapCreate(&allocator, CX_STORE_POINTERS, 0);
448 map->advanced_destructor = test_advanced_destructor;
449 verify_any_destructor(map);
450 EXPECT_TRUE(allocator.verify());
451 }
452
453 TEST(CxHashMap, Generics) {
454 CxTestingAllocator allocator;
455 auto map = test_map_generics_step_1(&allocator);
456
457 EXPECT_EQ(map->size, 3);
458 EXPECT_STREQ((char *) cxMapGet(map, "test"), "test");
459 EXPECT_STREQ((char *) cxMapGet(map, "foo"), "bar");
460 EXPECT_STREQ((char *) cxMapGet(map, "hallo"), "welt");
461
462 test_map_generics_step_2(map);
463
464 EXPECT_EQ(map->size, 2);
465 EXPECT_STREQ((char *) cxMapGet(map, "key"), "value");
466 EXPECT_STREQ((char *) cxMapGet(map, "foo"), "bar");
467
468 test_map_generics_step_3(map);
469
470 EXPECT_EQ(map->size, 0);
471
472 cxMapDestroy(map);
473 EXPECT_TRUE(allocator.verify());
474 }
475
476 TEST(EmptyMap, Size) {
477 auto map = cxEmptyMap;
478
479 EXPECT_EQ(map->size, 0);
480 }
481
482 TEST(EmptyMap, Iterator) {
483 auto map = cxEmptyMap;
484
485 auto it1 = cxMapIterator(map);
486 auto it2 = cxMapIteratorValues(map);
487 auto it3 = cxMapIteratorKeys(map);
488 auto it4 = cxMapMutIterator(map);
489 auto it5 = cxMapMutIteratorValues(map);
490 auto it6 = cxMapMutIteratorKeys(map);
491
492 EXPECT_FALSE(cxIteratorValid(it1));
493 EXPECT_FALSE(cxIteratorValid(it2));
494 EXPECT_FALSE(cxIteratorValid(it3));
495 EXPECT_FALSE(cxIteratorValid(it4));
496 EXPECT_FALSE(cxIteratorValid(it5));
497 EXPECT_FALSE(cxIteratorValid(it6));
498
499 int c = 0;
500 cx_foreach(void*, data, it1) c++;
501 cx_foreach(void*, data, it2) c++;
502 cx_foreach(void*, data, it3) c++;
503 cx_foreach(void*, data, it4) c++;
504 cx_foreach(void*, data, it5) c++;
505 cx_foreach(void*, data, it6) c++;
506 EXPECT_EQ(c, 0);
507 }
508
509 TEST(EmptyMap, NoOps) {
510 auto map = cxEmptyMap;
511
512 ASSERT_NO_FATAL_FAILURE(cxMapClear(map));
513 ASSERT_NO_FATAL_FAILURE(cxMapDestroy(map));
514 }
515
516 TEST(EmptyMap, Get) {
517 auto map = cxEmptyMap;
518
519 CxHashKey key = cx_hash_key_str("test");
520 EXPECT_EQ(cxMapGet(map, key), nullptr);
521 }
522