1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2023 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/test.h"
30 #include "util_allocator.h"
31 #include "cx/array_list.h"
32 #include "cx/list.h"
33
34 #include "cx/hash_map.h"
35
36 CX_TEST(test_hash_map_create) {
37 CxTestingAllocator talloc;
38 cx_testing_allocator_init(&talloc);
39 CxAllocator *allocator = &talloc.base;
40 CX_TEST_DO {
41 CxMap *map = cxHashMapCreate(allocator, 1, 0);
42 struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
43 CX_TEST_ASSERT(hmap->bucket_count > 0);
44 for(size_t i = 0 ; i < hmap->bucket_count ; i++) {
45 CX_TEST_ASSERT(hmap->buckets[i] == NULL);
46 }
47 CX_TEST_ASSERT(map->collection.elem_size == 1);
48 CX_TEST_ASSERT(map->collection.size == 0);
49 CX_TEST_ASSERT(map->collection.allocator == allocator);
50 CX_TEST_ASSERT(!map->collection.store_pointer);
51 CX_TEST_ASSERT(map->collection.cmpfunc == NULL);
52 CX_TEST_ASSERT(map->collection.simple_destructor == NULL);
53 CX_TEST_ASSERT(map->collection.advanced_destructor == NULL);
54 CX_TEST_ASSERT(map->collection.destructor_data == NULL);
55
56 cxMapFree(map);
57 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
58 }
59 cx_testing_allocator_destroy(&talloc);
60 }
61
62 CX_TEST(test_hash_map_create_store_pointers) {
63 CxTestingAllocator talloc;
64 cx_testing_allocator_init(&talloc);
65 CxAllocator *allocator = &talloc.base;
66 CX_TEST_DO {
67 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
68 struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
69 CX_TEST_ASSERT(hmap->bucket_count > 0);
70 for (size_t i = 0; i < hmap->bucket_count; i++) {
71 CX_TEST_ASSERT(hmap->buckets[i] == NULL);
72 }
73 CX_TEST_ASSERT(map->collection.size == 0);
74 CX_TEST_ASSERT(map->collection.allocator == allocator);
75 CX_TEST_ASSERT(map->collection.store_pointer);
76 CX_TEST_ASSERT(map->collection.elem_size == sizeof(void *));
77
78 cxMapFree(map);
79 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
80 }
81 cx_testing_allocator_destroy(&talloc);
82 }
83
84 CX_TEST(test_hash_map_emplace) {
85 CxTestingAllocator talloc;
86 cx_testing_allocator_init(&talloc);
87 CxAllocator *allocator = &talloc.base;
88 CX_TEST_DO {
89 CxMap *map = cxHashMapCreate(allocator, 20, 4);
90
91 char *v = cxMapEmplace(map, "key 1");
92 CX_TEST_ASSERT(v != NULL);
93 strcpy(v, "val 1");
94
95 char *tv = cxMapGet(map, "key 1");
96 CX_TEST_ASSERT(tv != NULL);
97 CX_TEST_ASSERT(0 == strcmp(tv, "val 1"));
98
99 v = cxMapEmplace(map, "key 1");
100 CX_TEST_ASSERT(v != NULL);
101 CX_TEST_ASSERT(0 != strcmp(v, "val 1"));
102
103 tv = cxMapGet(map, "key 1");
104 CX_TEST_ASSERT(tv != NULL);
105 CX_TEST_ASSERT(0 != strcmp(tv, "val 1"));
106
107 cxMapFree(map);
108 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
109 }
110 cx_testing_allocator_destroy(&talloc);
111 }
112
113 CX_TEST(test_hash_map_emplace_pointers) {
114 CxTestingAllocator talloc;
115 cx_testing_allocator_init(&talloc);
116 CxAllocator *allocator = &talloc.base;
117 CX_TEST_DO {
118 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 4);
119 cxSetAdvancedDestructor(map, cxFree, allocator);
120
121 char *val1 = cxMalloc(allocator, 8);
122 strcpy(val1, "val 1");
123 char *val2 = cxMalloc(allocator, 8);
124 strcpy(val2, "val 2");
125
126 char **v1 = cxMapEmplace(map, "key 1");
127 CX_TEST_ASSERT(v1 != NULL);
128 *v1 = val1;
129
130 char *tv = cxMapGet(map, "key 1");
131 CX_TEST_ASSERT(tv != NULL);
132 CX_TEST_ASSERT(0 == strcmp(tv, "val 1"));
133
134 // this will call the destructor of former v1
135 char **v2 = cxMapEmplace(map, "key 1");
136 CX_TEST_ASSERT(v2 != NULL);
137 *v2 = val2;
138 tv = cxMapGet(map, "key 1");
139 CX_TEST_ASSERT(tv != NULL);
140 CX_TEST_ASSERT(0 == strcmp(tv, "val 2"));
141
142 cxMapFree(map);
143 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
144 }
145 cx_testing_allocator_destroy(&talloc);
146 }
147
148 CX_TEST(test_hash_map_rehash) {
149 CxTestingAllocator talloc;
150 cx_testing_allocator_init(&talloc);
151 CxAllocator *allocator = &talloc.base;
152 CX_TEST_DO {
153 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 7);
154
155 cxMapPut(map, "key 1", (void *) "val 1");
156 cxMapPut(map, "key 2", (void *) "val 2");
157 cxMapPut(map, "key 3", (void *) "val 3");
158 cxMapPut(map, "foo 4", (void *) "val 4");
159 cxMapPut(map, "key 5", (void *) "val 5");
160 cxMapPut(map, "key 6", (void *) "val 6");
161 cxMapPut(map, "bar 7", (void *) "val 7");
162 cxMapPut(map, "key 8", (void *) "val 8");
163 cxMapPut(map, "key 9", (void *) "val 9");
164 cxMapPut(map, "key 10", (void *) "val 10");
165
166 CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 7);
167 int result = cxMapRehash(map);
168 CX_TEST_ASSERT(result == 0);
169 CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 25);
170 CX_TEST_ASSERT(map->collection.size == 10);
171
172 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 1"), "val 1"));
173 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 2"), "val 2"));
174 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 3"), "val 3"));
175 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo 4"), "val 4"));
176 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 5"), "val 5"));
177 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 6"), "val 6"));
178 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "bar 7"), "val 7"));
179 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 8"), "val 8"));
180 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 9"), "val 9"));
181 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 10"), "val 10"));
182
183 cxMapFree(map);
184 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
185 }
186 cx_testing_allocator_destroy(&talloc);
187 }
188
189 CX_TEST(test_hash_map_rehash_not_required) {
190 CxTestingAllocator talloc;
191 cx_testing_allocator_init(&talloc);
192 CxAllocator *allocator = &talloc.base;
193 CX_TEST_DO {
194 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 8);
195
196 cxMapPut(map, "key 1", (void *) "val 1");
197 cxMapPut(map, "key 2", (void *) "val 2");
198 cxMapPut(map, "key 3", (void *) "val 3");
199 cxMapPut(map, "key 4", (void *) "val 4");
200 cxMapPut(map, "key 5", (void *) "val 5");
201 cxMapPut(map, "key 6", (void *) "val 6");
202
203 // 6/8 does not exceed 0.75, therefore the function should not rehash
204 int result = cxMapRehash(map);
205 CX_TEST_ASSERT(result == 0);
206 CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 8);
207
208 cxMapFree(map);
209 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
210 }
211 cx_testing_allocator_destroy(&talloc);
212 }
213
214 CX_TEST(test_hash_map_clear) {
215 CxTestingAllocator talloc;
216 cx_testing_allocator_init(&talloc);
217 CxAllocator *allocator = &talloc.base;
218 CX_TEST_DO {
219 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
220
221 cxMapPut(map, "key 1", (void *) "val 1");
222 cxMapPut(map, "key 2", (void *) "val 2");
223 cxMapPut(map, "key 3", (void *) "val 3");
224
225 CX_TEST_ASSERT(map->collection.size == 3);
226
227 cxMapClear(map);
228
229 CX_TEST_ASSERT(map->collection.size == 0);
230 CX_TEST_ASSERT(cxMapGet(map, "key 1") == NULL);
231 CX_TEST_ASSERT(cxMapGet(map, "key 2") == NULL);
232 CX_TEST_ASSERT(cxMapGet(map, "key 3") == NULL);
233
234 cxMapFree(map);
235 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
236 }
237 cx_testing_allocator_destroy(&talloc);
238 }
239
240 CX_TEST(test_hash_map_store_ucx_strings) {
241 CxTestingAllocator talloc;
242 cx_testing_allocator_init(&talloc);
243 CxAllocator *allocator = &talloc.base;
244 CX_TEST_DO {
245 // create the map
246 CxMap *map = cxHashMapCreate(allocator, sizeof(cxstring), 8);
247
248 // define some strings
249 cxstring s1 = cx_str("this");
250 cxstring s2 = cx_str("is");
251 cxstring s3 = cx_str("a");
252 cxstring s4 = cx_str("test");
253 cxstring s5 = cx_str("setup");
254
255 // put them into the map
256 cxMapPut(map, "s1", &s1);
257 cxMapPut(map, "s2", &s2);
258 cxMapPut(map, "s3", &s3);
259 cxMapPut(map, "s4", &s4);
260
261 // overwrite a value
262 cxMapPut(map, "s1", &s5);
263
264 // look up a string
265 cxstring * s3p = cxMapGet(map, "s3");
266 CX_TEST_ASSERT(s3p->length == s3.length);
267 CX_TEST_ASSERT(s3p->ptr == s3.ptr);
268 CX_TEST_ASSERT(s3p != &s3);
269
270 // remove a string
271 cxstring ret = {0};
272 CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, "s2", &ret));
273 CX_TEST_ASSERT(map->collection.size == 3);
274 CX_TEST_ASSERT(0 == cx_strcmp(ret, cx_str("is")));
275
276 // iterate
277 bool s3found = false, s4found = false, s5found = false;
278 CxMapIterator iter = cxMapIteratorValues(map);
279 cx_foreach(cxstring*, s, iter) {
280 s3found |= s3.ptr == s->ptr;
281 s4found |= s4.ptr == s->ptr;
282 s5found |= s5.ptr == s->ptr;
283 }
284 CX_TEST_ASSERT(s3found && s4found && s5found);
285
286 cxMapFree(map);
287 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
288 }
289 cx_testing_allocator_destroy(&talloc);
290 }
291
292 CX_TEST(test_hash_map_integer_keys) {
293 CxMap *map = cxHashMapCreate(NULL, sizeof(cxstring), 0);
294 CX_TEST_DO {
295 cxstring s1 = cx_str("hello");
296 cxstring s2 = cx_str("world");
297
298 cxMapPut(map, UINT32_C(70875), &s1);
299 cxMapPut(map, UINT64_C(5785133750), &s2);
300
301 CX_TEST_ASSERT(cx_strcmp_p(&s1, cxMapGet(map, UINT32_C(70875))) == 0);
302 CX_TEST_ASSERT(cx_strcmp_p(&s2, cxMapGet(map, UINT64_C(5785133750))) == 0);
303 }
304 cxMapFree(map);
305 }
306
307 CX_TEST(test_hash_map_remove_via_iterator) {
308 CxTestingAllocator talloc;
309 cx_testing_allocator_init(&talloc);
310 CxAllocator *allocator = &talloc.base;
311 CX_TEST_DO {
312 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 3);
313
314 cxMapPut(map, "key 1", (void *) "val 1");
315 cxMapPut(map, "key 2", (void *) "val 2");
316 cxMapPut(map, "key 3", (void *) "val 3");
317 cxMapPut(map, "key 4", (void *) "val 4");
318 cxMapPut(map, "key 5", (void *) "val 5");
319 cxMapPut(map, "key 6", (void *) "val 6");
320 cxMapPut(map, "key 7", (void *) "val 7");
321 cxMapPut(map, "key 8", (void *) "val 8");
322 cxMapPut(map, "key 9", (void *) "val 9");
323
324 CxMapIterator iter = cxMapIterator(map);
325 cx_foreach(CxMapEntry*, entry, iter) {
326 if (((const char *)entry->key->data)[4] % 2 == 1) cxIteratorFlagRemoval(iter);
327 }
328 CX_TEST_ASSERT(cxMapSize(map) == 4);
329 CX_TEST_ASSERT(iter.elem_count == 4);
330 CX_TEST_ASSERT(iter.index == map->collection.size);
331
332 CX_TEST_ASSERT(cxMapGet(map, "key 1") == NULL);
333 CX_TEST_ASSERT(cxMapGet(map, "key 2") != NULL);
334 CX_TEST_ASSERT(cxMapGet(map, "key 3") == NULL);
335 CX_TEST_ASSERT(cxMapGet(map, "key 4") != NULL);
336 CX_TEST_ASSERT(cxMapGet(map, "key 5") == NULL);
337 CX_TEST_ASSERT(cxMapGet(map, "key 6") != NULL);
338 CX_TEST_ASSERT(cxMapGet(map, "key 7") == NULL);
339 CX_TEST_ASSERT(cxMapGet(map, "key 8") != NULL);
340 CX_TEST_ASSERT(cxMapGet(map, "key 9") == NULL);
341
342 cxMapFree(map);
343 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
344 }
345 cx_testing_allocator_destroy(&talloc);
346 }
347
348 struct test_destr_struct {
349 char *str;
350 };
351
352 static void test_simple_destructor(void *d) {
353 struct test_destr_struct *data = d;
354 strcpy(data->str, "OK");
355 }
356
357 static void test_advanced_destructor(
358 cx_attr_unused void *unused,
359 void *d
360 ) {
361 test_simple_destructor(d);
362 }
363
364 static CX_TEST_SUBROUTINE(verify_any_destructor, CxMap *map) {
365 CxHashKey k1 = cx_hash_key_str("key 1");
366 CxHashKey k2 = cx_hash_key_str("key 2");
367 CxHashKey k3 = cx_hash_key_str("key 3");
368 CxHashKey k4 = cx_hash_key_str("key 4");
369 CxHashKey k5 = cx_hash_key_str("key 5");
370
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";
376 char v6[] = "val 6";
377 char v7[] = "val 7";
378
379 struct test_destr_struct d1 = {v1};
380 struct test_destr_struct d2 = {v2};
381 struct test_destr_struct d3 = {v3};
382 struct test_destr_struct d4 = {v4};
383 struct test_destr_struct d5 = {v5};
384 struct test_destr_struct d6 = {v6};
385 struct test_destr_struct d7 = {v7};
386
387 void *v1data = &d1;
388 void *v2data = &d2;
389 void *v3data = &d3;
390 void *v4data = &d4;
391 void *v5data = &d5;
392 void *v6data = &d6;
393 void *v7data = &d7;
394
395 cxMapPut(map, k1, v1data);
396 cxMapPut(map, k2, v2data);
397 cxMapPut(map, k3, v3data);
398 cxMapPut(map, k4, v4data);
399
400 CX_TEST_ASSERT(0 == cxMapRemove(map, k2));
401 if (map->collection.store_pointer) {
402 struct test_destr_struct *r;
403 CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, k3, &r));
404 CX_TEST_ASSERT(r == &d3);
405 } else {
406 struct test_destr_struct r;
407 CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, k3, &r));
408 CX_TEST_ASSERT(r.str == v3);
409 }
410
411 CX_TEST_ASSERT(0 == strcmp(v1, "val 1"));
412 CX_TEST_ASSERT(0 == strcmp(v2, "OK"));
413 CX_TEST_ASSERT(0 == strcmp(v3, "val 3"));
414 CX_TEST_ASSERT(0 == strcmp(v4, "val 4"));
415 CX_TEST_ASSERT(0 == strcmp(v5, "val 5"));
416
417 // put k5, overwrite k1, put new k3
418 cxMapPut(map, k5, v5data);
419 cxMapPut(map, k1, v6data);
420 cxMapPut(map, k3, v7data);
421
422 // destructor the value behind k1 was called, but for k3 not
423 CX_TEST_ASSERT(0 == strcmp(v1, "OK"));
424 CX_TEST_ASSERT(0 == strcmp(v3, "val 3"));
425
426 // now remove k1 via key iterator and k5 (val 5) via value iterator
427 v1[0] = 'y'; // mark v1 and check that destr is not called for previous val
428 {
429 CxMapIterator iter = cxMapIteratorKeys(map);
430 CX_TEST_ASSERT(iter.elem_count == 4);
431 CX_TEST_ASSERT(cxMapSize(map) == 4);
432 cx_foreach(CxHashKey*, key, iter) {
433 if (((char*)key->data)[4] == '1') cxIteratorFlagRemoval(iter);
434 }
435 CX_TEST_ASSERT(iter.elem_count == 3);
436 CX_TEST_ASSERT(cxMapSize(map) == 3);
437 }
438 {
439 CxMapIterator iter = cxMapIteratorValues(map);
440 cx_foreach(struct test_destr_struct*, v, iter) {
441 if (v->str[4] == '5') cxIteratorFlagRemoval(iter);
442 }
443 CX_TEST_ASSERT(iter.elem_count == 2);
444 CX_TEST_ASSERT(cxMapSize(map) == 2);
445 }
446
447 CX_TEST_ASSERT(0 == strcmp(v1, "yK"));
448 CX_TEST_ASSERT(0 == strcmp(v2, "OK"));
449 CX_TEST_ASSERT(0 == strcmp(v3, "val 3"));
450 CX_TEST_ASSERT(0 == strcmp(v4, "val 4"));
451 CX_TEST_ASSERT(0 == strcmp(v5, "OK"));
452 CX_TEST_ASSERT(0 == strcmp(v6, "OK"));
453 CX_TEST_ASSERT(0 == strcmp(v7, "val 7"));
454
455 // mark the already destroyed items
456 // and check that they are not destroyed again
457 v1[0] = v2[0] = v4[0] = v5[0] = 'c';
458
459 cxMapFree(map);
460
461 CX_TEST_ASSERT(0 == strcmp(v1, "cK"));
462 CX_TEST_ASSERT(0 == strcmp(v2, "cK"));
463 CX_TEST_ASSERT(0 == strcmp(v3, "val 3"));
464 CX_TEST_ASSERT(0 == strcmp(v4, "OK"));
465 CX_TEST_ASSERT(0 == strcmp(v5, "cK"));
466 CX_TEST_ASSERT(0 == strcmp(v6, "OK"));
467 CX_TEST_ASSERT(0 == strcmp(v7, "OK"));
468 }
469
470 CX_TEST(test_hash_map_simple_destructor_objects) {
471 CxTestingAllocator talloc;
472 cx_testing_allocator_init(&talloc);
473 CxAllocator *allocator = &talloc.base;
474 CX_TEST_DO {
475 CxMap *map = cxHashMapCreate(allocator,
476 sizeof(struct test_destr_struct), 0);
477 map->collection.simple_destructor = test_simple_destructor;
478 CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map);
479 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
480 }
481 cx_testing_allocator_destroy(&talloc);
482 }
483
484 CX_TEST(test_hash_map_advanced_destructor_objects) {
485 CxTestingAllocator talloc;
486 cx_testing_allocator_init(&talloc);
487 CxAllocator *allocator = &talloc.base;
488 CX_TEST_DO {
489 CxMap *map = cxHashMapCreate(allocator,
490 sizeof(struct test_destr_struct), 0);
491 map->collection.advanced_destructor = test_advanced_destructor;
492 CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map);
493 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
494 }
495 cx_testing_allocator_destroy(&talloc);
496 }
497
498 CX_TEST(test_hash_map_simple_destructor_pointers) {
499 CxTestingAllocator talloc;
500 cx_testing_allocator_init(&talloc);
501 CxAllocator *allocator = &talloc.base;
502 CX_TEST_DO {
503 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
504 map->collection.simple_destructor = test_simple_destructor;
505 CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map);
506 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
507 }
508 cx_testing_allocator_destroy(&talloc);
509 }
510
511 CX_TEST(test_hash_map_advanced_destructor_pointers) {
512 CxTestingAllocator talloc;
513 cx_testing_allocator_init(&talloc);
514 CxAllocator *allocator = &talloc.base;
515 CX_TEST_DO {
516 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
517 map->collection.advanced_destructor = test_advanced_destructor;
518 CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map);
519 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
520 }
521 cx_testing_allocator_destroy(&talloc);
522 }
523
524 static bool test_hash_map_clone_func_max_enabled = false;
525 static unsigned test_hash_map_clone_func_max_clones;
526 static void *test_hash_map_clone_func(void *dst, const void *src,
527 const CxAllocator *al, void *data) {
528 if (test_hash_map_clone_func_max_enabled) {
529 if (test_hash_map_clone_func_max_clones == 0) return NULL;
530 test_hash_map_clone_func_max_clones--;
531 }
532 if (dst == NULL) {
533 dst = cxMalloc(al, sizeof(int));
534 }
535 *((int*)dst) = *((int*)src) + *((int*)data);
536 return dst;
537 }
538
539 CX_TEST(test_hash_map_clone) {
540 CxMap *dst = cxHashMapCreate(NULL, sizeof(int), 0);
541 CxMap *src = cxHashMapCreate(NULL, sizeof(int), 0);
542 const char *exist_keys[] = {"k1", "k2", "k3"};
543 int exists[] = {1, 3, 4};
544 const char *source_keys[] = {"k4", "k2", "k5"};
545 int source[] = {7, 9, 15};
546 for (unsigned int i = 0 ; i < 3 ; i++) {
547 cxMapPut(dst, exist_keys[i], &exists[i]);
548 cxMapPut(src, source_keys[i], &source[i]);
549 }
550 CX_TEST_DO {
551 int c = 4;
552 CX_TEST_ASSERT(0 == cxMapClone(dst, src, test_hash_map_clone_func, NULL, &c));
553 CX_TEST_ASSERT(cxMapSize(dst) == 5);
554 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 1);
555 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 13);
556 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 4);
557 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 11);
558 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k5")) == 19);
559 CX_TEST_ASSERT(cxMapSize(src) == 3);
560 CX_TEST_ASSERT(*((int*)cxMapGet(src, "k4")) == 7);
561 CX_TEST_ASSERT(*((int*)cxMapGet(src, "k2")) == 9);
562 CX_TEST_ASSERT(*((int*)cxMapGet(src, "k5")) == 15);
563 }
564 cxMapFree(dst);
565 cxMapFree(src);
566 }
567
568 CX_TEST(test_hash_map_clone_alloc_fail) {
569 CxMap *dst = cxHashMapCreate(NULL, sizeof(int), 0);
570 CxMap *src = cxHashMapCreate(NULL, sizeof(int), 0);
571 const char *exist_keys[] = {"k1", "k2", "k3"};
572 int exists[] = {1, 3, 4};
573 const char *source_keys[] = {"k4", "k2", "k5"};
574 int source[] = {7, 9, 15};
575 for (unsigned int i = 0 ; i < 3 ; i++) {
576 cxMapPut(dst, exist_keys[i], &exists[i]);
577 cxMapPut(src, source_keys[i], &source[i]);
578 }
579 CX_TEST_DO {
580 int c = 4;
581 test_hash_map_clone_func_max_enabled = true;
582 test_hash_map_clone_func_max_clones = 2;
583 CX_TEST_ASSERT(0 != cxMapClone(dst, src, test_hash_map_clone_func, NULL, &c));
584 test_hash_map_clone_func_max_enabled = false;
585 CX_TEST_ASSERT(cxMapSize(dst) == 4);
586 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 1);
587 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 13);
588 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 4);
589 // the concrete element which is affected might change when the hash function changes
590 CX_TEST_ASSERT(cxMapGet(dst, "k4") == NULL);
591 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k5")) == 19);
592 CX_TEST_ASSERT(cxMapSize(src) == 3);
593 CX_TEST_ASSERT(*((int*)cxMapGet(src, "k4")) == 7);
594 CX_TEST_ASSERT(*((int*)cxMapGet(src, "k2")) == 9);
595 CX_TEST_ASSERT(*((int*)cxMapGet(src, "k5")) == 15);
596 }
597 cxMapFree(dst);
598 cxMapFree(src);
599 }
600
601 CX_TEST(test_hash_map_clone_ptr) {
602 CxTestingAllocator talloc;
603 cx_testing_allocator_init(&talloc);
604 CxAllocator *allocator = &talloc.base;
605 CxMap *dst = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
606 cxSetAdvancedDestructor(dst, cxFree, allocator);
607 CxMap *src = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
608 const char *exist_keys[] = {"k1", "k2", "k3"};
609 int exists[] = {1, 3, 4};
610 const char *source_keys[] = {"k4", "k2", "k5"};
611 int source[] = {7, 9, 15};
612 for (unsigned int i = 0 ; i < 3 ; i++) {
613 int *y = cxMalloc(allocator, sizeof(int));
614 *y = exists[i];
615 cxMapPut(dst, exist_keys[i], y);
616 cxMapPut(src, source_keys[i], &source[i]);
617 }
618 CX_TEST_DO {
619 int c = 4;
620 CX_TEST_ASSERT(0 == cxMapClone(dst, src, test_hash_map_clone_func, allocator, &c));
621 CX_TEST_ASSERT(cxMapSize(dst) == 5);
622 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 1);
623 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 13);
624 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 4);
625 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 11);
626 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k5")) == 19);
627 CX_TEST_ASSERT(cxMapSize(src) == 3);
628 CX_TEST_ASSERT(*((int*)cxMapGet(src, "k4")) == 7);
629 CX_TEST_ASSERT(*((int*)cxMapGet(src, "k2")) == 9);
630 CX_TEST_ASSERT(*((int*)cxMapGet(src, "k5")) == 15);
631
632 cxMapClear(dst);
633 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
634 }
635 cxMapFree(dst);
636 cxMapFree(src);
637 cx_testing_allocator_destroy(&talloc);
638 }
639
640 CX_TEST(test_hash_map_difference) {
641 CxMap *dst = cxHashMapCreate(NULL, sizeof(int), 0);
642
643 CxMap *s1 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
644 CxMap *s2 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
645 const char *s1_keys[] = {"k1", "k2", "k3"};
646 int s1_values[] = {1, 3, 4};
647 const char *s2_keys[] = {"k4", "k2", "k5"};
648 int s2_values[] = {7, 9, 15};
649 for (unsigned int i = 0 ; i < 3 ; i++) {
650 cxMapPut(s1, s1_keys[i], &s1_values[i]);
651 cxMapPut(s2, s2_keys[i], &s2_values[i]);
652 }
653 CX_TEST_DO {
654 int c = 4;
655 CX_TEST_ASSERT(0 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, NULL, &c));
656 CX_TEST_ASSERT(cxMapSize(dst) == 2);
657 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5);
658 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL);
659 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8);
660 }
661 cxMapFree(dst);
662 cxMapFree(s1);
663 cxMapFree(s2);
664 }
665
666 CX_TEST(test_hash_map_difference_alloc_fail) {
667 CxMap *dst = cxHashMapCreate(NULL, sizeof(int), 0);
668
669 CxMap *s1 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
670 CxMap *s2 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
671 const char *s1_keys[] = {"k1", "k2", "k3"};
672 int s1_values[] = {1, 3, 4};
673 const char *s2_keys[] = {"k4", "k2", "k5"};
674 int s2_values[] = {7, 9, 15};
675 for (unsigned int i = 0 ; i < 3 ; i++) {
676 cxMapPut(s1, s1_keys[i], &s1_values[i]);
677 cxMapPut(s2, s2_keys[i], &s2_values[i]);
678 }
679 CX_TEST_DO {
680 int c = 4;
681 test_hash_map_clone_func_max_enabled = true;
682 test_hash_map_clone_func_max_clones = 1;
683 CX_TEST_ASSERT(1 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, NULL, &c));
684 test_hash_map_clone_func_max_enabled = false;
685 CX_TEST_ASSERT(cxMapSize(dst) == 1);
686 // the concrete element which is affected might change when the hash function changes
687 CX_TEST_ASSERT(cxMapGet(dst, "k1") == NULL);
688 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL);
689 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8);
690 }
691 cxMapFree(dst);
692 cxMapFree(s1);
693 cxMapFree(s2);
694 }
695
696 CX_TEST(test_hash_map_list_difference) {
697 CxMap *dst = cxHashMapCreate(NULL, sizeof(int), 0);
698 CxMap *src = cxHashMapCreate(NULL, sizeof(int), 0);
699 CxList *keys = cxArrayListCreate(NULL, sizeof(CxHashKey), 4);
700 cxSetCompareFunc(keys, cx_hash_key_cmp);
701
702 const char *src_keys[] = {"k1", "k2", "k3"};
703 int src_values[] = {1, 3, 4};
704 for (unsigned int i = 0 ; i < 3 ; i++) {
705 cxMapPut(src, src_keys[i], &src_values[i]);
706 }
707 const char *k[] = {"k4", "k2", "k5"};
708 for (unsigned int i = 0 ; i < 3 ; i++) {
709 CxHashKey key = CX_HASH_KEY(k[i]);
710 cxListAdd(keys, &key);
711 }
712 CX_TEST_DO {
713 int c = 4;
714 CX_TEST_ASSERT(0 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c));
715 CX_TEST_ASSERT(cxMapSize(dst) == 2);
716 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5);
717 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL);
718 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8);
719 }
720 cxMapFree(dst);
721 cxMapFree(src);
722 cxListFree(keys);
723 }
724
725 CX_TEST(test_hash_map_list_difference_alloc_fail) {
726 CxMap *dst = cxHashMapCreate(NULL, sizeof(int), 0);
727 CxMap *src = cxHashMapCreate(NULL, sizeof(int), 0);
728 CxList *keys = cxArrayListCreate(NULL, sizeof(CxHashKey), 4);
729 cxSetCompareFunc(keys, cx_hash_key_cmp);
730
731 const char *src_keys[] = {"k1", "k2", "k3"};
732 int src_values[] = {1, 3, 4};
733 for (unsigned int i = 0 ; i < 3 ; i++) {
734 cxMapPut(src, src_keys[i], &src_values[i]);
735 }
736 const char *k[] = {"k4", "k2", "k5"};
737 for (unsigned int i = 0 ; i < 3 ; i++) {
738 CxHashKey key = CX_HASH_KEY(k[i]);
739 cxListAdd(keys, &key);
740 }
741 CX_TEST_DO {
742 int c = 4;
743 test_hash_map_clone_func_max_enabled = true;
744 test_hash_map_clone_func_max_clones = 1;
745 CX_TEST_ASSERT(1 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c));
746 test_hash_map_clone_func_max_enabled = false;
747 CX_TEST_ASSERT(cxMapSize(dst) == 1);
748 // the concrete element which is affected might change when the hash function changes
749 CX_TEST_ASSERT(cxMapGet(dst, "k1") == NULL);
750 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL);
751 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8);
752 }
753 cxMapFree(dst);
754 cxMapFree(src);
755 cxListFree(keys);
756 }
757
758 CX_TEST(test_hash_map_difference_non_empty_target) {
759 CxMap *dst = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
760 cxSetAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator);
761
762 CxMap *s1 = cxHashMapCreate(NULL, sizeof(int), 0);
763 CxMap *s2 = cxHashMapCreate(NULL, sizeof(int), 0);
764 const char *s1_keys[] = {"k1", "k2", "k3"};
765 int s1_values[] = {1, 3, 4};
766 const char *s2_keys[] = {"k4", "k2", "k5"};
767 int s2_values[] = {7, 9, 15};
768 for (unsigned int i = 0 ; i < 3 ; i++) {
769 cxMapPut(s1, s1_keys[i], &s1_values[i]);
770 cxMapPut(s2, s2_keys[i], &s2_values[i]);
771 }
772
773 // add k5 to dst which is not in src, and also not in the difference
774 int *k5 = cxMallocDefault(sizeof(int));
775 *k5 = 1337;
776 cxMapPut(dst, "k5",k5);
777
778 CX_TEST_DO {
779 int c = 4;
780 CX_TEST_ASSERT(0 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, NULL, &c));
781 CX_TEST_ASSERT(cxMapSize(dst) == 3);
782 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5);
783 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL);
784 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8);
785 CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k5") == 1337);
786 }
787 cxMapFree(dst);
788 cxMapFree(s1);
789 cxMapFree(s2);
790 }
791
792 CX_TEST(test_hash_map_list_difference_non_empty_target) {
793 CxMap *dst = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
794 cxSetAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator);
795 CxMap *src = cxHashMapCreate(NULL, sizeof(int), 0);
796 CxList *keys = cxArrayListCreate(NULL, sizeof(CxHashKey), 4);
797 cxSetCompareFunc(keys, cx_hash_key_cmp);
798
799 const char *src_keys[] = {"k1", "k2", "k3"};
800 int src_values[] = {1, 3, 4};
801 for (unsigned int i = 0 ; i < 3 ; i++) {
802 cxMapPut(src, src_keys[i], &src_values[i]);
803 }
804 const char *k[] = {"k4", "k2", "k5"};
805 for (unsigned int i = 0 ; i < 3 ; i++) {
806 CxHashKey key = CX_HASH_KEY(k[i]);
807 cxListAdd(keys, &key);
808 }
809
810 // add k5 to dst which is not in src, and also not in the difference
811 int *k5 = cxMallocDefault(sizeof(int));
812 *k5 = 1337;
813 cxMapPut(dst, "k5",k5);
814
815 CX_TEST_DO {
816 int c = 4;
817 CX_TEST_ASSERT(0 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c));
818 CX_TEST_ASSERT(cxMapSize(dst) == 3);
819 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5);
820 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL);
821 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8);
822 CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k5") == 1337);
823 }
824 cxMapFree(dst);
825 cxMapFree(src);
826 cxListFree(keys);
827 }
828
829 CX_TEST(test_hash_map_difference_ptr) {
830 CxTestingAllocator talloc;
831 cx_testing_allocator_init(&talloc);
832 CxAllocator *allocator = &talloc.base;
833 CxMap *dst = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
834 cxSetAdvancedDestructor(dst, cxFree, allocator);
835
836 CxMap *s1 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
837 CxMap *s2 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
838 const char *s1_keys[] = {"k1", "k2", "k3"};
839 int s1_values[] = {1, 3, 4};
840 const char *s2_keys[] = {"k4", "k2", "k5"};
841 int s2_values[] = {7, 9, 15};
842 for (unsigned int i = 0 ; i < 3 ; i++) {
843 cxMapPut(s1, s1_keys[i], &s1_values[i]);
844 cxMapPut(s2, s2_keys[i], &s2_values[i]);
845 }
846 CX_TEST_DO {
847 int c = 4;
848 CX_TEST_ASSERT(0 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, allocator, &c));
849 CX_TEST_ASSERT(cxMapSize(dst) == 2);
850 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5);
851 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL);
852 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8);
853
854 cxMapClear(dst);
855 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
856 }
857 cxMapFree(dst);
858 cxMapFree(s1);
859 cxMapFree(s2);
860 cx_testing_allocator_destroy(&talloc);
861 }
862
863 CX_TEST(test_hash_map_intersection) {
864 CxMap *dst = cxHashMapCreate(NULL, sizeof(int), 0);
865
866 CxMap *s1 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
867 CxMap *s2 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
868 const char *s1_keys[] = {"k1", "k2", "k3", "k4"};
869 int s1_values[] = {1, 3, 4, 6};
870 const char *s2_keys[] = {"k4", "k5", "k2", "k6"};
871 int s2_values[] = {5, 9, 15, 23};
872 for (unsigned int i = 0 ; i < 4 ; i++) {
873 cxMapPut(s1, s1_keys[i], &s1_values[i]);
874 cxMapPut(s2, s2_keys[i], &s2_values[i]);
875 }
876 CX_TEST_DO {
877 int c = 4;
878 CX_TEST_ASSERT(0 == cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, NULL, &c));
879 CX_TEST_ASSERT(cxMapSize(dst) == 2);
880 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7);
881 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10);
882 }
883 cxMapFree(dst);
884 cxMapFree(s1);
885 cxMapFree(s2);
886 }
887
888 CX_TEST(test_hash_map_intersection_alloc_fail) {
889 CxMap *dst = cxHashMapCreate(NULL, sizeof(int), 0);
890
891 CxMap *s1 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
892 CxMap *s2 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
893 const char *s1_keys[] = {"k1", "k2", "k3", "k4"};
894 int s1_values[] = {1, 3, 4, 6};
895 const char *s2_keys[] = {"k4", "k5", "k2", "k6"};
896 int s2_values[] = {5, 9, 15, 23};
897 for (unsigned int i = 0 ; i < 4 ; i++) {
898 cxMapPut(s1, s1_keys[i], &s1_values[i]);
899 cxMapPut(s2, s2_keys[i], &s2_values[i]);
900 }
901 CX_TEST_DO {
902 int c = 4;
903 test_hash_map_clone_func_max_enabled = true;
904 test_hash_map_clone_func_max_clones = 1;
905 CX_TEST_ASSERT(0 != cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, NULL, &c));
906 test_hash_map_clone_func_max_enabled = false;
907 CX_TEST_ASSERT(cxMapSize(dst) == 1);
908 // the concrete element which is affected might change when the hash function changes
909 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7);
910 CX_TEST_ASSERT(cxMapGet(dst, "k4") == NULL);
911 }
912 cxMapFree(dst);
913 cxMapFree(s1);
914 cxMapFree(s2);
915 }
916
917 CX_TEST(test_hash_map_list_intersection) {
918 CxMap *dst = cxHashMapCreate(NULL, sizeof(int), 0);
919 CxMap *src = cxHashMapCreate(NULL, sizeof(int), 0);
920 CxList *keys = cxArrayListCreate(NULL, sizeof(CxHashKey), 4);
921 cxSetCompareFunc(keys, cx_hash_key_cmp);
922
923 const char *src_keys[] = {"k1", "k2", "k3", "k4"};
924 int src_values[] = {1, 3, 4, 6};
925 for (unsigned int i = 0 ; i < 4 ; i++) {
926 cxMapPut(src, src_keys[i], &src_values[i]);
927 }
928 const char *k[] = {"k4", "k5", "k2", "k6"};
929 for (unsigned int i = 0 ; i < 4 ; i++) {
930 CxHashKey key = CX_HASH_KEY(k[i]);
931 cxListAdd(keys, &key);
932 }
933 CX_TEST_DO {
934 int c = 4;
935 CX_TEST_ASSERT(0 == cxMapListIntersection(dst, src, keys, test_hash_map_clone_func, NULL, &c));
936 CX_TEST_ASSERT(cxMapSize(dst) == 2);
937 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7);
938 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10);
939 }
940 cxMapFree(dst);
941 cxMapFree(src);
942 cxListFree(keys);
943 }
944
945 CX_TEST(test_hash_map_list_intersection_alloc_fail) {
946 CxMap *dst = cxHashMapCreate(NULL, sizeof(int), 0);
947 CxMap *src = cxHashMapCreate(NULL, sizeof(int), 0);
948 CxList *keys = cxArrayListCreate(NULL, sizeof(CxHashKey), 4);
949 cxSetCompareFunc(keys, cx_hash_key_cmp);
950
951 const char *src_keys[] = {"k1", "k2", "k3", "k4"};
952 int src_values[] = {1, 3, 4, 6};
953 for (unsigned int i = 0 ; i < 4 ; i++) {
954 cxMapPut(src, src_keys[i], &src_values[i]);
955 }
956 const char *k[] = {"k4", "k5", "k2", "k6"};
957 for (unsigned int i = 0 ; i < 4 ; i++) {
958 CxHashKey key = CX_HASH_KEY(k[i]);
959 cxListAdd(keys, &key);
960 }
961 CX_TEST_DO {
962 int c = 4;
963 test_hash_map_clone_func_max_enabled = true;
964 test_hash_map_clone_func_max_clones = 1;
965 CX_TEST_ASSERT(0 != cxMapListIntersection(dst, src, keys, test_hash_map_clone_func, NULL, &c));
966 test_hash_map_clone_func_max_enabled = false;
967 CX_TEST_ASSERT(cxMapSize(dst) == 1);
968 // the concrete element which is affected might change when the hash function changes
969 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7);
970 CX_TEST_ASSERT(cxMapGet(dst, "k4") == NULL);
971 }
972 cxMapFree(dst);
973 cxMapFree(src);
974 cxListFree(keys);
975 }
976
977 CX_TEST(test_hash_map_intersection_non_empty_target) {
978 CxMap *dst = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
979 cxSetAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator);
980
981 CxMap *s1 = cxHashMapCreate(NULL, sizeof(int), 0);
982 CxMap *s2 = cxHashMapCreate(NULL, sizeof(int), 0);
983 const char *s1_keys[] = {"k1", "k2", "k3", "k4"};
984 int s1_values[] = {1, 3, 4, 6};
985 const char *s2_keys[] = {"k4", "k5", "k2", "k6"};
986 int s2_values[] = {5, 9, 15, 23};
987 for (unsigned int i = 0 ; i < 4 ; i++) {
988 cxMapPut(s1, s1_keys[i], &s1_values[i]);
989 cxMapPut(s2, s2_keys[i], &s2_values[i]);
990 }
991
992 // add k7 to dst which is not in src, and also not in the difference
993 int *k7 = cxMallocDefault(sizeof(int));
994 *k7 = 1337;
995 cxMapPut(dst, "k7", k7);
996
997 CX_TEST_DO {
998 int c = 4;
999 CX_TEST_ASSERT(0 == cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, NULL, &c));
1000 CX_TEST_ASSERT(cxMapSize(dst) == 3);
1001 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7);
1002 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10);
1003 CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k7") == 1337);
1004 }
1005 cxMapFree(dst);
1006 cxMapFree(s1);
1007 cxMapFree(s2);
1008 }
1009
1010 CX_TEST(test_hash_map_list_intersection_non_empty_target) {
1011 CxMap *dst = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
1012 cxSetAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator);
1013 CxMap *src = cxHashMapCreate(NULL, sizeof(int), 0);
1014 CxList *keys = cxArrayListCreate(NULL, sizeof(CxHashKey), 4);
1015 cxSetCompareFunc(keys, cx_hash_key_cmp);
1016
1017 const char *src_keys[] = {"k1", "k2", "k3", "k4"};
1018 int src_values[] = {1, 3, 4, 6};
1019 for (unsigned int i = 0 ; i < 4 ; i++) {
1020 cxMapPut(src, src_keys[i], &src_values[i]);
1021 }
1022 const char *k[] = {"k4", "k5", "k2", "k6"};
1023 for (unsigned int i = 0 ; i < 4 ; i++) {
1024 CxHashKey key = CX_HASH_KEY(k[i]);
1025 cxListAdd(keys, &key);
1026 }
1027
1028 // add k7 to dst which is not in src, and also not in the difference
1029 int *k7 = cxMallocDefault(sizeof(int));
1030 *k7 = 1337;
1031 cxMapPut(dst, "k7", k7);
1032
1033 CX_TEST_DO {
1034 int c = 4;
1035 CX_TEST_ASSERT(0 == cxMapListIntersection(dst, src, keys, test_hash_map_clone_func, NULL, &c));
1036 CX_TEST_ASSERT(cxMapSize(dst) == 3);
1037 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7);
1038 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10);
1039 CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k7") == 1337);
1040 }
1041
1042 cxMapFree(dst);
1043 cxMapFree(src);
1044 cxListFree(keys);
1045 }
1046
1047 CX_TEST(test_hash_map_intersection_ptr) {
1048 CxTestingAllocator talloc;
1049 cx_testing_allocator_init(&talloc);
1050 CxAllocator *allocator = &talloc.base;
1051 CxMap *dst = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
1052 cxSetAdvancedDestructor(dst, cxFree, allocator);
1053
1054 CxMap *s1 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
1055 CxMap *s2 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
1056 const char *s1_keys[] = {"k1", "k2", "k3", "k4"};
1057 int s1_values[] = {1, 3, 4, 6};
1058 const char *s2_keys[] = {"k4", "k5", "k2", "k6"};
1059 int s2_values[] = {5, 9, 15, 23};
1060 for (unsigned int i = 0 ; i < 4 ; i++) {
1061 cxMapPut(s1, s1_keys[i], &s1_values[i]);
1062 cxMapPut(s2, s2_keys[i], &s2_values[i]);
1063 }
1064 CX_TEST_DO {
1065 int c = 4;
1066 CX_TEST_ASSERT(0 == cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, allocator, &c));
1067 CX_TEST_ASSERT(cxMapSize(dst) == 2);
1068 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7);
1069 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10);
1070 CX_TEST_ASSERT(cx_testing_allocator_used(&talloc));
1071 }
1072 cxMapFree(dst);
1073 cxMapFree(s1);
1074 cxMapFree(s2);
1075 cx_testing_allocator_destroy(&talloc);
1076 }
1077
1078 CX_TEST(test_hash_map_union) {
1079 CxMap *s1 = cxHashMapCreate(NULL, sizeof(int), 0);
1080 CxMap *s2 = cxHashMapCreate(NULL, sizeof(int), 0);
1081 const char *s1_keys[] = {"k1", "k2", "k3", "k4"};
1082 int s1_values[] = {1, 3, 4, 6};
1083 const char *s2_keys[] = {"k4", "k5", "k2", "k6"};
1084 int s2_values[] = {5, 9, 15, 23};
1085 for (unsigned int i = 0 ; i < 4 ; i++) {
1086 cxMapPut(s1, s1_keys[i], &s1_values[i]);
1087 cxMapPut(s2, s2_keys[i], &s2_values[i]);
1088 }
1089 CX_TEST_DO {
1090 int c = 4;
1091 CX_TEST_ASSERT(0 == cxMapUnion(s1, s2, test_hash_map_clone_func, NULL, &c));
1092 CX_TEST_ASSERT(cxMapSize(s1) == 6);
1093 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k1")) == 1);
1094 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k2")) == 3);
1095 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k3")) == 4);
1096 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k4")) == 6);
1097 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k5")) == 13);
1098 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k6")) == 27);
1099 }
1100 cxMapFree(s1);
1101 cxMapFree(s2);
1102 }
1103
1104 CX_TEST(test_hash_map_union_ptr) {
1105 CxTestingAllocator talloc;
1106 cx_testing_allocator_init(&talloc);
1107 CxAllocator *allocator = &talloc.base;
1108 CxMap *dst = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
1109 cxSetAdvancedDestructor(dst, cxFree, allocator);
1110
1111 CxMap *s1 = cxHashMapCreate(NULL, sizeof(int), 0);
1112 CxMap *s2 = cxHashMapCreate(NULL, sizeof(int), 0);
1113 const char *s1_keys[] = {"k1", "k2", "k3", "k4"};
1114 int s1_values[] = {1, 3, 4, 6};
1115 const char *s2_keys[] = {"k4", "k5", "k2", "k6"};
1116 int s2_values[] = {5, 9, 15, 23};
1117 for (unsigned int i = 0 ; i < 4 ; i++) {
1118 cxMapPut(s1, s1_keys[i], &s1_values[i]);
1119 cxMapPut(s2, s2_keys[i], &s2_values[i]);
1120 }
1121 CX_TEST_DO {
1122 int c = 4;
1123 CX_TEST_ASSERT(0 == cxMapClone(dst, s1, test_hash_map_clone_func, allocator, &c));
1124 CX_TEST_ASSERT(0 == cxMapUnion(dst, s2, test_hash_map_clone_func, allocator, &c));
1125 CX_TEST_ASSERT(cxMapSize(dst) == 6);
1126 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5);
1127 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7);
1128 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8);
1129 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10);
1130 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k5")) == 13);
1131 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k6")) == 27);
1132 CX_TEST_ASSERT(cx_testing_allocator_used(&talloc));
1133 }
1134 cxMapFree(dst);
1135 cxMapFree(s1);
1136 cxMapFree(s2);
1137 cx_testing_allocator_destroy(&talloc);
1138 }
1139
1140 CX_TEST(test_hash_map_union_alloc_fail) {
1141 CxMap *s1 = cxHashMapCreate(NULL, sizeof(int), 0);
1142 CxMap *s2 = cxHashMapCreate(NULL, sizeof(int), 0);
1143 const char *s1_keys[] = {"k1", "k2", "k3", "k4"};
1144 int s1_values[] = {1, 3, 4, 6};
1145 const char *s2_keys[] = {"k4", "k5", "k2", "k6"};
1146 int s2_values[] = {5, 9, 15, 23};
1147 for (unsigned int i = 0 ; i < 4 ; i++) {
1148 cxMapPut(s1, s1_keys[i], &s1_values[i]);
1149 cxMapPut(s2, s2_keys[i], &s2_values[i]);
1150 }
1151 CX_TEST_DO {
1152 int c = 4;
1153 test_hash_map_clone_func_max_enabled = true;
1154 test_hash_map_clone_func_max_clones = 1;
1155 CX_TEST_ASSERT(0 != cxMapUnion(s1, s2, test_hash_map_clone_func, NULL, &c));
1156 test_hash_map_clone_func_max_enabled = false;
1157 CX_TEST_ASSERT(cxMapSize(s1) == 5);
1158 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k1")) == 1);
1159 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k2")) == 3);
1160 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k3")) == 4);
1161 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k4")) == 6);
1162 // the concrete element which is affected might change when the hash function changes
1163 CX_TEST_ASSERT(cxMapGet(s1, "k5") == NULL);
1164 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k6")) == 27);
1165 }
1166 cxMapFree(s1);
1167 cxMapFree(s2);
1168 }
1169
1170 CX_TEST(test_hash_map_simple_clones) {
1171 int v = 47; // the value does not matter in this test
1172 CxMap *a = cxHashMapCreate(NULL, sizeof(int), 0);
1173 cxMapPut(a, "k1", &v);
1174 cxMapPut(a, "k2", &v);
1175 cxMapPut(a, "k3", &v);
1176 cxMapPut(a, "k4", &v);
1177
1178 CxMap *b = cxHashMapCreate(NULL, sizeof(int), 0);
1179 cxMapPut(b, "k0", &v);
1180 cxMapPut(b, "k2", &v);
1181 cxMapPut(b, "k5", &v);
1182
1183 CxMap *c = cxHashMapCreate(NULL, sizeof(int), 0);
1184 cxMapPut(c, "k3", &v);
1185 cxMapPut(c, "k4", &v);
1186 cxMapPut(c, "k5", &v);
1187
1188
1189 CxHashKey k;
1190 CxList *kl1 = cxArrayListCreate(NULL, sizeof(CxHashKey), 4);
1191 cxSetCompareFunc(kl1, cx_hash_key_cmp);
1192 k = CX_HASH_KEY("k0");
1193 cxListAdd(kl1, &k);
1194 k = CX_HASH_KEY("k2");
1195 cxListAdd(kl1, &k);
1196 k = CX_HASH_KEY("k5");
1197 cxListAdd(kl1, &k);
1198
1199 CxList *kl2 = cxArrayListCreate(NULL, sizeof(CxHashKey), 4);
1200 cxSetCompareFunc(kl2, cx_hash_key_cmp);
1201 k = CX_HASH_KEY("k3");
1202 cxListAdd(kl2, &k);
1203 k = CX_HASH_KEY("k4");
1204 cxListAdd(kl2, &k);
1205 k = CX_HASH_KEY("k5");
1206 cxListAdd(kl2, &k);
1207
1208 CxMap *d1 = cxHashMapCreate(NULL, sizeof(int), 0);
1209 CxMap *d2 = cxHashMapCreate(NULL, sizeof(int), 0);
1210
1211 CX_TEST_DO {
1212 CX_TEST_ASSERT(0 == cxMapCloneShallow(d1, a));
1213 CX_TEST_ASSERT(!cxMapContains(d1, "k0"));
1214 CX_TEST_ASSERT(cxMapContains(d1, "k1"));
1215 CX_TEST_ASSERT(cxMapContains(d1, "k2"));
1216 CX_TEST_ASSERT(cxMapContains(d1, "k3"));
1217 CX_TEST_ASSERT(cxMapContains(d1, "k4"));
1218 CX_TEST_ASSERT(!cxMapContains(d1, "k5"));
1219
1220 CX_TEST_ASSERT(0 == cxMapListDifferenceShallow(d2, d1, kl1));
1221 CX_TEST_ASSERT(!cxMapContains(d2, "k0"));
1222 CX_TEST_ASSERT(cxMapContains(d2, "k1"));
1223 CX_TEST_ASSERT(!cxMapContains(d2, "k2"));
1224 CX_TEST_ASSERT(cxMapContains(d2, "k3"));
1225 CX_TEST_ASSERT(cxMapContains(d2, "k4"));
1226 CX_TEST_ASSERT(!cxMapContains(d2, "k5"));
1227
1228 cxMapClear(d1);
1229 CX_TEST_ASSERT(0 == cxMapListIntersectionShallow(d1, d2, kl2));
1230 CX_TEST_ASSERT(!cxMapContains(d1, "k0"));
1231 CX_TEST_ASSERT(!cxMapContains(d1, "k1"));
1232 CX_TEST_ASSERT(!cxMapContains(d1, "k2"));
1233 CX_TEST_ASSERT(cxMapContains(d1, "k3"));
1234 CX_TEST_ASSERT(cxMapContains(d1, "k4"));
1235
1236 CX_TEST_ASSERT(0 == cxMapUnionShallow(d1, b));
1237 CX_TEST_ASSERT(cxMapContains(d1, "k0"));
1238 CX_TEST_ASSERT(!cxMapContains(d1, "k1"));
1239 CX_TEST_ASSERT(cxMapContains(d1, "k2"));
1240 CX_TEST_ASSERT(cxMapContains(d1, "k3"));
1241 CX_TEST_ASSERT(cxMapContains(d1, "k4"));
1242 CX_TEST_ASSERT(cxMapContains(d1, "k5"));
1243
1244 cxMapClear(d2);
1245 CX_TEST_ASSERT(0 == cxMapDifferenceShallow(d2, d1, a));
1246 CX_TEST_ASSERT(cxMapContains(d2, "k0"));
1247 CX_TEST_ASSERT(!cxMapContains(d2, "k1"));
1248 CX_TEST_ASSERT(!cxMapContains(d2, "k2"));
1249 CX_TEST_ASSERT(!cxMapContains(d2, "k3"));
1250 CX_TEST_ASSERT(!cxMapContains(d2, "k4"));
1251 CX_TEST_ASSERT(cxMapContains(d2, "k5"));
1252
1253 cxMapClear(d1);
1254 CX_TEST_ASSERT(0 == cxMapIntersectionShallow(d1, d2, c));
1255 CX_TEST_ASSERT(!cxMapContains(d1, "k0"));
1256 CX_TEST_ASSERT(!cxMapContains(d1, "k1"));
1257 CX_TEST_ASSERT(!cxMapContains(d1, "k2"));
1258 CX_TEST_ASSERT(!cxMapContains(d1, "k3"));
1259 CX_TEST_ASSERT(!cxMapContains(d1, "k4"));
1260 CX_TEST_ASSERT(cxMapContains(d1, "k5"));
1261 }
1262
1263 cxMapFree(a);
1264 cxMapFree(b);
1265 cxMapFree(c);
1266 cxListFree(kl1);
1267 cxListFree(kl2);
1268 cxMapFree(d1);
1269 cxMapFree(d2);
1270 }
1271
1272 CX_TEST(test_hash_map_compare) {
1273 CxMap *map1 = cxHashMapCreate(NULL, sizeof(int), 0);
1274 CxMap *map2 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
1275 // TODO: fix specification of compare function once #622 is realized
1276 map1->collection.cmpfunc = cx_cmp_int;
1277 map2->collection.cmpfunc = cx_cmp_int;
1278
1279 // some ints we can point to in the pointer map
1280 int z13 = 13;
1281 int z15 = 15;
1282 int z42 = 42;
1283 int z1337 = 1337;
1284 int z4711 = 4711;
1285
1286 CX_TEST_DO {
1287 // empty maps are equal
1288 CX_TEST_ASSERT(cxMapCompare(map1, map2) == 0);
1289 CX_TEST_ASSERT(cxMapCompare(map2, map1) == 0);
1290
1291 // left has fewer keys than right
1292 cxMapPut(map1, "first key", &z13);
1293 cxMapPut(map1, "second key", &z15);
1294 cxMapPut(map2, "first key", &z13);
1295 cxMapPut(map2, "second key", &z15);
1296 cxMapPut(map2, "third key", &z42);
1297 CX_TEST_ASSERT(cxMapCompare(map1, map2) < 0);
1298 CX_TEST_ASSERT(cxMapCompare(map2, map1) > 0);
1299
1300 // both are equal
1301 cxMapPut(map1, "third key", &z42);
1302 CX_TEST_ASSERT(cxMapCompare(map1, map2) == 0);
1303 CX_TEST_ASSERT(cxMapCompare(map2, map1) == 0);
1304
1305 // left has more keys than right
1306 cxMapPut(map1, "fourth key", &z1337);
1307 CX_TEST_ASSERT(cxMapCompare(map1, map2) > 0);
1308 CX_TEST_ASSERT(cxMapCompare(map2, map1) < 0);
1309
1310 // key sets differ
1311 cxMapPut(map2, "wrong key", &z1337);
1312 CX_TEST_ASSERT(cxMapCompare(map1, map2) != 0);
1313 CX_TEST_ASSERT(cxMapCompare(map2, map1) != 0);
1314
1315 // values differ
1316 cxMapRemove(map2, "wrong key");
1317 cxMapPut(map2, "fourth key", &z4711);
1318 CX_TEST_ASSERT(cxMapCompare(map1, map2) != 0);
1319 CX_TEST_ASSERT(cxMapCompare(map2, map1) != 0);
1320
1321 // equal again (by overwriting value in map 1)
1322 cxMapPut(map1, "fourth key", &z4711);
1323 CX_TEST_ASSERT(cxMapCompare(map1, map2) == 0);
1324 CX_TEST_ASSERT(cxMapCompare(map2, map1) == 0);
1325 }
1326 cxMapFree(map1);
1327 cxMapFree(map2);
1328 }
1329
1330 CX_TEST(test_empty_map_size) {
1331 CX_TEST_DO {
1332 CX_TEST_ASSERT(cxEmptyMap->collection.size == 0);
1333 CX_TEST_ASSERT(cxMapSize(cxEmptyMap) == 0);
1334 }
1335 }
1336
1337 CX_TEST(test_empty_map_iterator) {
1338 CxMap *map = cxEmptyMap;
1339
1340 CxMapIterator it1 = cxMapIterator(map);
1341 CxMapIterator it2 = cxMapIteratorValues(map);
1342 CxMapIterator it3 = cxMapIteratorKeys(map);
1343 CxMapIterator it4 = cxMapIterator(map);
1344 CxMapIterator it5 = cxMapIteratorValues(map);
1345 CxMapIterator it6 = cxMapIteratorKeys(map);
1346
1347 CX_TEST_DO {
1348 CX_TEST_ASSERT(!cxIteratorValid(it1));
1349 CX_TEST_ASSERT(!cxIteratorValid(it2));
1350 CX_TEST_ASSERT(!cxIteratorValid(it3));
1351 CX_TEST_ASSERT(!cxIteratorValid(it4));
1352 CX_TEST_ASSERT(!cxIteratorValid(it5));
1353 CX_TEST_ASSERT(!cxIteratorValid(it6));
1354
1355 int c = 0;
1356 cx_foreach(void*, data, it1) c++;
1357 cx_foreach(void*, data, it2) c++;
1358 cx_foreach(void*, data, it3) c++;
1359 cx_foreach(void*, data, it4) c++;
1360 cx_foreach(void*, data, it5) c++;
1361 cx_foreach(void*, data, it6) c++;
1362 CX_TEST_ASSERT(c == 0);
1363 }
1364 }
1365
1366 CX_TEST(test_null_map_iterator) {
1367 CxMap *map = NULL;
1368
1369 CxMapIterator it1 = cxMapIterator(map);
1370 CxMapIterator it2 = cxMapIteratorValues(map);
1371 CxMapIterator it3 = cxMapIteratorKeys(map);
1372 CxMapIterator it4 = cxMapIterator(map);
1373 CxMapIterator it5 = cxMapIteratorValues(map);
1374 CxMapIterator it6 = cxMapIteratorKeys(map);
1375
1376 CX_TEST_DO {
1377 CX_TEST_ASSERT(!cxIteratorValid(it1));
1378 CX_TEST_ASSERT(!cxIteratorValid(it2));
1379 CX_TEST_ASSERT(!cxIteratorValid(it3));
1380 CX_TEST_ASSERT(!cxIteratorValid(it4));
1381 CX_TEST_ASSERT(!cxIteratorValid(it5));
1382 CX_TEST_ASSERT(!cxIteratorValid(it6));
1383
1384 int c = 0;
1385 cx_foreach(void*, data, it1) c++;
1386 cx_foreach(void*, data, it2) c++;
1387 cx_foreach(void*, data, it3) c++;
1388 cx_foreach(void*, data, it4) c++;
1389 cx_foreach(void*, data, it5) c++;
1390 cx_foreach(void*, data, it6) c++;
1391 CX_TEST_ASSERT(c == 0);
1392 }
1393 }
1394
1395 CX_TEST(test_empty_map_no_ops) {
1396 CX_TEST_DO {
1397 // assertion not possible
1398 // test that no segfault happens and valgrind is happy
1399 cxMapClear(cxEmptyMap);
1400 cxMapFree(cxEmptyMap);
1401 CX_TEST_ASSERT(true);
1402 }
1403 }
1404
1405 CX_TEST(test_empty_map_get) {
1406 CX_TEST_DO {
1407 CxHashKey key = cx_hash_key_str("test");
1408 CX_TEST_ASSERT(cxMapGet(cxEmptyMap, key) == NULL);
1409 }
1410 }
1411
1412 CX_TEST(test_hash_map_generics) {
1413 CxTestingAllocator talloc;
1414 cx_testing_allocator_init(&talloc);
1415 CxAllocator *allocator = &talloc.base;
1416 CX_TEST_DO {
1417 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
1418 cxMapPut(map, "test", "test");
1419 cxMapPut(map, cx_mutstr("foo"), "bar");
1420 cxMapPut(map, cx_str("hallo"), "welt");
1421
1422 CX_TEST_ASSERT(map->collection.size == 3);
1423 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "test"), "test"));
1424 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar"));
1425 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "hallo"), "welt"));
1426
1427 CX_TEST_ASSERT(0 == cxMapRemove(map, cx_str("test")));
1428 const char *hallo = "hallo";
1429 CX_TEST_ASSERT(0 == cxMapRemove(map, hallo));
1430 cxMapPut(map, cx_hash_key_str("key"), "value");
1431
1432 CX_TEST_ASSERT(map->collection.size == 2);
1433 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key"), "value"));
1434 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar"));
1435
1436 const char *r1, *r2;
1437 CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, "key", &r1));
1438 CX_TEST_ASSERT(0 == strcmp(r1, "value"));
1439 CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, cx_str("foo"), &r2));
1440 CX_TEST_ASSERT(0 == strcmp(r2, "bar"));
1441 r2 = "nope";
1442 CX_TEST_ASSERT(0 != cxMapRemoveAndGet(map, cx_hash_key("notfound",9), &r2));
1443 CX_TEST_ASSERT(0 == strcmp(r2, "nope"));
1444
1445 CX_TEST_ASSERT(map->collection.size == 0);
1446
1447 cxMapFree(map);
1448 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1449 }
1450 cx_testing_allocator_destroy(&talloc);
1451 }
1452
1453 struct test_map_kv {
1454 const char *key;
1455 const char *value;
1456 };
1457
1458 static struct test_map_kv const test_map_operations[] = {
1459 {"key 1", "test"},
1460 {"key 2", "blub"},
1461 {"key 3", "hallo"},
1462 {"key 2", "foobar"},
1463 {"key 4", "value 4"},
1464 {"key 5", "value 5"},
1465 {"key 6", "value 6"},
1466 {"key 4", NULL},
1467 {"key 7", "value 7"},
1468 {"key 8", "value 8"},
1469 {"does not exist", NULL},
1470 {"key 9", "value 9"},
1471 {"key 6", "other value"},
1472 {"key 7", "something else"},
1473 {"key 8", NULL},
1474 {"key 2", NULL},
1475 {"key 8", "new value"},
1476 };
1477 static const size_t test_map_operations_len =
1478 sizeof(test_map_operations) / sizeof(struct test_map_kv);
1479 static struct test_map_kv test_map_reference[] = {
1480 {"key 1", NULL},
1481 {"key 2", NULL},
1482 {"key 3", NULL},
1483 {"key 4", NULL},
1484 {"key 5", NULL},
1485 {"key 6", NULL},
1486 {"key 7", NULL},
1487 {"key 8", NULL},
1488 {"key 9", NULL},
1489 };
1490 static const size_t test_map_reference_len =
1491 sizeof(test_map_reference) / sizeof(struct test_map_kv);
1492
1493 static void test_map_reference_put(const char *key, const char *value) {
1494 for (size_t i = 0 ; i < test_map_reference_len ; i++) {
1495 if (0 == strcmp(key, test_map_reference[i].key)) {
1496 test_map_reference[i].value = value;
1497 return;
1498 }
1499 }
1500 }
1501
1502 static const char *test_map_reference_get(const char *key) {
1503 for (size_t i = 0 ; i < test_map_reference_len ; i++) {
1504 if (0 == strcmp(key, test_map_reference[i].key)) {
1505 return test_map_reference[i].value;
1506 }
1507 }
1508 return NULL;
1509 }
1510
1511 static const char *test_map_reference_remove(const char *key) {
1512 for (size_t i = 0 ; i < test_map_reference_len ; i++) {
1513 if (0 == strcmp(key, test_map_reference[i].key)) {
1514 const char *ret = test_map_reference[i].value;
1515 test_map_reference[i].value = NULL;
1516 return ret;
1517 }
1518 }
1519 return NULL;
1520 }
1521
1522 static size_t test_map_reference_size(void) {
1523 size_t size = 0;
1524 for (size_t i = 0; i < test_map_reference_len; i++) {
1525 if (test_map_reference[i].value != NULL) {
1526 size++;
1527 }
1528 }
1529 return size;
1530 }
1531
1532 static CX_TEST_SUBROUTINE(verify_map_contents, CxMap *map) {
1533 // verify that the reference map has same size (i.e. no other keys are mapped)
1534 CX_TEST_ASSERT(map->collection.size == test_map_reference_size());
1535
1536 // verify key iterator
1537 {
1538 // collect the keys from the map iterator
1539 CxMapIterator keyiter = cxMapIteratorKeys(map);
1540 CX_TEST_ASSERT(keyiter.elem_size == sizeof(CxHashKey));
1541 CX_TEST_ASSERT(keyiter.elem_count == map->collection.size);
1542 CxHashKey *keys = calloc(map->collection.size, sizeof(CxHashKey));
1543 cx_foreach(CxHashKey*, elem, keyiter) {
1544 keys[keyiter.index] = *elem;
1545 }
1546 CX_TEST_ASSERT(keyiter.index == map->collection.size);
1547 // verify that all keys are mapped to values in reference map
1548 for (size_t i = 0 ; i < map->collection.size ; i++) {
1549 cxmutstr ksz = cx_strdup(cx_strn(keys[i].data, keys[i].len));
1550 CX_TEST_ASSERT(test_map_reference_get(ksz.ptr) != NULL);
1551 cx_strfree(&ksz);
1552 }
1553 free(keys);
1554 }
1555
1556 // verify value iterator
1557 {
1558 // by using that the values in our test data are unique strings
1559 // we can re-use a similar approach as above
1560 CxMapIterator valiter = cxMapIteratorValues(map);
1561 CX_TEST_ASSERT(valiter.elem_size == map->collection.elem_size);
1562 CX_TEST_ASSERT(valiter.elem_count == map->collection.size);
1563 const char ** values = calloc(map->collection.size, sizeof(const char *));
1564 cx_foreach(const char *, elem, valiter) {
1565 values[valiter.index] = elem;
1566 }
1567 CX_TEST_ASSERT(valiter.index == map->collection.size);
1568 // verify that all values are present in the reference map
1569 for (size_t i = 0 ; i < map->collection.size ; i++) {
1570 bool found = false;
1571 for (size_t j = 0; j < test_map_reference_len ; j++) {
1572 if (test_map_reference[j].value == values[i]) {
1573 found = true;
1574 break;
1575 }
1576 }
1577 CX_TEST_ASSERTM(found, "A value was not found in the reference map");
1578 }
1579 free(values);
1580 }
1581
1582 // verify pair iterator
1583 {
1584 CxMapIterator pairiter = cxMapIterator(map);
1585 CX_TEST_ASSERT(pairiter.elem_size == sizeof(CxMapEntry));
1586 CX_TEST_ASSERT(pairiter.elem_count == map->collection.size);
1587 struct test_map_kv *pairs = calloc(map->collection.size, sizeof(struct test_map_kv));
1588 cx_foreach(CxMapEntry*, entry, pairiter) {
1589 const CxHashKey *key = entry->key;
1590 pairs[pairiter.index].key = cx_strdup(cx_strn(key->data, key->len)).ptr;
1591 pairs[pairiter.index].value = entry->value;
1592 }
1593 CX_TEST_ASSERT(pairiter.index == map->collection.size);
1594 // verify that all pairs are present in the reference map
1595 for (size_t i = 0 ; i < map->collection.size ; i++) {
1596 CX_TEST_ASSERT(test_map_reference_get(pairs[i].key) == pairs[i].value);
1597 // this was cx_strdup'ed
1598 cxFreeDefault((void*)pairs[i].key);
1599 }
1600 free(pairs);
1601 }
1602 }
1603
1604 CX_TEST(test_hash_map_basic_operations) {
1605 CxTestingAllocator talloc;
1606 cx_testing_allocator_init(&talloc);
1607 CxAllocator *allocator = &talloc.base;
1608 CX_TEST_DO {
1609 // create the map
1610 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 8);
1611
1612 // clear the reference map
1613 for (size_t i = 0 ; i < test_map_reference_len ; i++) {
1614 test_map_reference[i].value = NULL;
1615 }
1616
1617 // verify iterators for empty map
1618 CX_TEST_CALL_SUBROUTINE(verify_map_contents, map);
1619
1620 // execute operations and verify results
1621 for (size_t i = 0 ; i < test_map_operations_len ; i++) {
1622 struct test_map_kv kv = test_map_operations[i];
1623 CxHashKey key = cx_hash_key_str(kv.key);
1624 key.hash = 0; // force the hash map to compute the hash
1625 if (kv.value != NULL) {
1626 // execute a put operation and verify that the exact value can be read back
1627 test_map_reference_put(kv.key, kv.value);
1628 int result = cxMapPut(map, key, (void *) kv.value);
1629 CX_TEST_ASSERT(result == 0);
1630 void *added = cxMapGet(map, key);
1631 CX_TEST_ASSERT(0 == memcmp(kv.value, added, strlen(kv.value)));
1632 } else {
1633 // execute a remove and verify that the removed element was returned (or NULL)
1634 const char *found = test_map_reference_remove(kv.key);
1635 void *removed = (void*) 0x1337;
1636 int result = cxMapRemoveAndGet(map, key, &removed);
1637 if (found == NULL) {
1638 CX_TEST_ASSERT(0 != result);
1639 CX_TEST_ASSERT(removed == (void*) 0x1337);
1640 } else {
1641 CX_TEST_ASSERT(0 == result);
1642 CX_TEST_ASSERT(removed == found);
1643 }
1644
1645 }
1646 // compare the current map state with the reference map
1647 CX_TEST_CALL_SUBROUTINE(verify_map_contents, map);
1648 }
1649
1650 // destroy the map and verify the memory (de)allocations
1651 cxMapFree(map);
1652 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1653 }
1654 cx_testing_allocator_destroy(&talloc);
1655 }
1656
1657 CxTestSuite *cx_test_suite_hash_map(void) {
1658 CxTestSuite *suite = cx_test_suite_new("map");
1659
1660 cx_test_register(suite, test_hash_map_create);
1661 cx_test_register(suite, test_hash_map_create_store_pointers);
1662 cx_test_register(suite, test_hash_map_basic_operations);
1663 cx_test_register(suite, test_hash_map_emplace);
1664 cx_test_register(suite, test_hash_map_emplace_pointers);
1665 cx_test_register(suite, test_hash_map_rehash);
1666 cx_test_register(suite, test_hash_map_rehash_not_required);
1667 cx_test_register(suite, test_hash_map_clear);
1668 cx_test_register(suite, test_hash_map_store_ucx_strings);
1669 cx_test_register(suite, test_hash_map_integer_keys);
1670 cx_test_register(suite, test_hash_map_remove_via_iterator);
1671 cx_test_register(suite, test_hash_map_simple_destructor_objects);
1672 cx_test_register(suite, test_hash_map_advanced_destructor_objects);
1673 cx_test_register(suite, test_hash_map_simple_destructor_pointers);
1674 cx_test_register(suite, test_hash_map_advanced_destructor_pointers);
1675 cx_test_register(suite, test_hash_map_clone);
1676 cx_test_register(suite, test_hash_map_clone_alloc_fail);
1677 cx_test_register(suite, test_hash_map_clone_ptr);
1678 cx_test_register(suite, test_hash_map_difference);
1679 cx_test_register(suite, test_hash_map_difference_ptr);
1680 cx_test_register(suite, test_hash_map_list_difference);
1681 cx_test_register(suite, test_hash_map_difference_alloc_fail);
1682 cx_test_register(suite, test_hash_map_list_difference_alloc_fail);
1683 cx_test_register(suite, test_hash_map_difference_non_empty_target);
1684 cx_test_register(suite, test_hash_map_list_difference_non_empty_target);
1685 cx_test_register(suite, test_hash_map_intersection);
1686 cx_test_register(suite, test_hash_map_intersection_ptr);
1687 cx_test_register(suite, test_hash_map_list_intersection);
1688 cx_test_register(suite, test_hash_map_intersection_alloc_fail);
1689 cx_test_register(suite, test_hash_map_list_intersection_alloc_fail);
1690 cx_test_register(suite, test_hash_map_intersection_non_empty_target);
1691 cx_test_register(suite, test_hash_map_list_intersection_non_empty_target);
1692 cx_test_register(suite, test_hash_map_union);
1693 cx_test_register(suite, test_hash_map_union_ptr);
1694 cx_test_register(suite, test_hash_map_union_alloc_fail);
1695 cx_test_register(suite, test_hash_map_simple_clones);
1696 cx_test_register(suite, test_hash_map_compare);
1697 cx_test_register(suite, test_empty_map_no_ops);
1698 cx_test_register(suite, test_empty_map_size);
1699 cx_test_register(suite, test_empty_map_get);
1700 cx_test_register(suite, test_empty_map_iterator);
1701 cx_test_register(suite, test_null_map_iterator);
1702 cx_test_register(suite, test_hash_map_generics);
1703
1704 return suite;
1705 }
1706