UNIXworkcode

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 cxDefineAdvancedDestructor(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 = cxHashMapCreateSimple(sizeof(cxstring)); 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 = cxHashMapCreateSimple(sizeof(int)); 541 CxMap *src = cxHashMapCreateSimple(sizeof(int)); 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 = cxHashMapCreateSimple(sizeof(int)); 570 CxMap *src = cxHashMapCreateSimple(sizeof(int)); 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 = cxHashMapCreateSimple(CX_STORE_POINTERS); 606 cxDefineAdvancedDestructor(dst, cxFree, allocator); 607 CxMap *src = cxHashMapCreateSimple(CX_STORE_POINTERS); 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 = cxHashMapCreateSimple(sizeof(int)); 642 643 CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); 644 CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); 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 = cxHashMapCreateSimple(sizeof(int)); 668 669 CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); 670 CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); 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 = cxHashMapCreateSimple(sizeof(int)); 698 CxMap *src = cxHashMapCreateSimple(sizeof(int)); 699 CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); 700 701 const char *src_keys[] = {"k1", "k2", "k3"}; 702 int src_values[] = {1, 3, 4}; 703 for (unsigned int i = 0 ; i < 3 ; i++) { 704 cxMapPut(src, src_keys[i], &src_values[i]); 705 } 706 const char *k[] = {"k4", "k2", "k5"}; 707 for (unsigned int i = 0 ; i < 3 ; i++) { 708 CxHashKey key = CX_HASH_KEY(k[i]); 709 cxListAdd(keys, &key); 710 } 711 CX_TEST_DO { 712 int c = 4; 713 CX_TEST_ASSERT(0 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c)); 714 CX_TEST_ASSERT(cxMapSize(dst) == 2); 715 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5); 716 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); 717 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); 718 } 719 cxMapFree(dst); 720 cxMapFree(src); 721 cxListFree(keys); 722 } 723 724 CX_TEST(test_hash_map_list_difference_alloc_fail) { 725 CxMap *dst = cxHashMapCreateSimple(sizeof(int)); 726 CxMap *src = cxHashMapCreateSimple(sizeof(int)); 727 CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); 728 729 const char *src_keys[] = {"k1", "k2", "k3"}; 730 int src_values[] = {1, 3, 4}; 731 for (unsigned int i = 0 ; i < 3 ; i++) { 732 cxMapPut(src, src_keys[i], &src_values[i]); 733 } 734 const char *k[] = {"k4", "k2", "k5"}; 735 for (unsigned int i = 0 ; i < 3 ; i++) { 736 CxHashKey key = CX_HASH_KEY(k[i]); 737 cxListAdd(keys, &key); 738 } 739 CX_TEST_DO { 740 int c = 4; 741 test_hash_map_clone_func_max_enabled = true; 742 test_hash_map_clone_func_max_clones = 1; 743 CX_TEST_ASSERT(1 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c)); 744 test_hash_map_clone_func_max_enabled = false; 745 CX_TEST_ASSERT(cxMapSize(dst) == 1); 746 // the concrete element which is affected might change when the hash function changes 747 CX_TEST_ASSERT(cxMapGet(dst, "k1") == NULL); 748 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); 749 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); 750 } 751 cxMapFree(dst); 752 cxMapFree(src); 753 cxListFree(keys); 754 } 755 756 CX_TEST(test_hash_map_difference_non_empty_target) { 757 CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); 758 cxDefineAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator); 759 760 CxMap *s1 = cxHashMapCreateSimple(sizeof(int)); 761 CxMap *s2 = cxHashMapCreateSimple(sizeof(int)); 762 const char *s1_keys[] = {"k1", "k2", "k3"}; 763 int s1_values[] = {1, 3, 4}; 764 const char *s2_keys[] = {"k4", "k2", "k5"}; 765 int s2_values[] = {7, 9, 15}; 766 for (unsigned int i = 0 ; i < 3 ; i++) { 767 cxMapPut(s1, s1_keys[i], &s1_values[i]); 768 cxMapPut(s2, s2_keys[i], &s2_values[i]); 769 } 770 771 // add k5 to dst which is not in src, and also not in the difference 772 int *k5 = cxMallocDefault(sizeof(int)); 773 *k5 = 1337; 774 cxMapPut(dst, "k5",k5); 775 776 CX_TEST_DO { 777 int c = 4; 778 CX_TEST_ASSERT(0 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, NULL, &c)); 779 CX_TEST_ASSERT(cxMapSize(dst) == 3); 780 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5); 781 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); 782 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); 783 CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k5") == 1337); 784 } 785 cxMapFree(dst); 786 cxMapFree(s1); 787 cxMapFree(s2); 788 } 789 790 CX_TEST(test_hash_map_list_difference_non_empty_target) { 791 CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); 792 cxDefineAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator); 793 CxMap *src = cxHashMapCreateSimple(sizeof(int)); 794 CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); 795 796 const char *src_keys[] = {"k1", "k2", "k3"}; 797 int src_values[] = {1, 3, 4}; 798 for (unsigned int i = 0 ; i < 3 ; i++) { 799 cxMapPut(src, src_keys[i], &src_values[i]); 800 } 801 const char *k[] = {"k4", "k2", "k5"}; 802 for (unsigned int i = 0 ; i < 3 ; i++) { 803 CxHashKey key = CX_HASH_KEY(k[i]); 804 cxListAdd(keys, &key); 805 } 806 807 // add k5 to dst which is not in src, and also not in the difference 808 int *k5 = cxMallocDefault(sizeof(int)); 809 *k5 = 1337; 810 cxMapPut(dst, "k5",k5); 811 812 CX_TEST_DO { 813 int c = 4; 814 CX_TEST_ASSERT(0 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c)); 815 CX_TEST_ASSERT(cxMapSize(dst) == 3); 816 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5); 817 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); 818 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); 819 CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k5") == 1337); 820 } 821 cxMapFree(dst); 822 cxMapFree(src); 823 cxListFree(keys); 824 } 825 826 CX_TEST(test_hash_map_difference_ptr) { 827 CxTestingAllocator talloc; 828 cx_testing_allocator_init(&talloc); 829 CxAllocator *allocator = &talloc.base; 830 CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); 831 cxDefineAdvancedDestructor(dst, cxFree, allocator); 832 833 CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); 834 CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); 835 const char *s1_keys[] = {"k1", "k2", "k3"}; 836 int s1_values[] = {1, 3, 4}; 837 const char *s2_keys[] = {"k4", "k2", "k5"}; 838 int s2_values[] = {7, 9, 15}; 839 for (unsigned int i = 0 ; i < 3 ; i++) { 840 cxMapPut(s1, s1_keys[i], &s1_values[i]); 841 cxMapPut(s2, s2_keys[i], &s2_values[i]); 842 } 843 CX_TEST_DO { 844 int c = 4; 845 CX_TEST_ASSERT(0 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, allocator, &c)); 846 CX_TEST_ASSERT(cxMapSize(dst) == 2); 847 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5); 848 CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); 849 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); 850 851 cxMapClear(dst); 852 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 853 } 854 cxMapFree(dst); 855 cxMapFree(s1); 856 cxMapFree(s2); 857 cx_testing_allocator_destroy(&talloc); 858 } 859 860 CX_TEST(test_hash_map_intersection) { 861 CxMap *dst = cxHashMapCreateSimple(sizeof(int)); 862 863 CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); 864 CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); 865 const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; 866 int s1_values[] = {1, 3, 4, 6}; 867 const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; 868 int s2_values[] = {5, 9, 15, 23}; 869 for (unsigned int i = 0 ; i < 4 ; i++) { 870 cxMapPut(s1, s1_keys[i], &s1_values[i]); 871 cxMapPut(s2, s2_keys[i], &s2_values[i]); 872 } 873 CX_TEST_DO { 874 int c = 4; 875 CX_TEST_ASSERT(0 == cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, NULL, &c)); 876 CX_TEST_ASSERT(cxMapSize(dst) == 2); 877 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); 878 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); 879 } 880 cxMapFree(dst); 881 cxMapFree(s1); 882 cxMapFree(s2); 883 } 884 885 CX_TEST(test_hash_map_intersection_alloc_fail) { 886 CxMap *dst = cxHashMapCreateSimple(sizeof(int)); 887 888 CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); 889 CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); 890 const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; 891 int s1_values[] = {1, 3, 4, 6}; 892 const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; 893 int s2_values[] = {5, 9, 15, 23}; 894 for (unsigned int i = 0 ; i < 4 ; i++) { 895 cxMapPut(s1, s1_keys[i], &s1_values[i]); 896 cxMapPut(s2, s2_keys[i], &s2_values[i]); 897 } 898 CX_TEST_DO { 899 int c = 4; 900 test_hash_map_clone_func_max_enabled = true; 901 test_hash_map_clone_func_max_clones = 1; 902 CX_TEST_ASSERT(0 != cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, NULL, &c)); 903 test_hash_map_clone_func_max_enabled = false; 904 CX_TEST_ASSERT(cxMapSize(dst) == 1); 905 // the concrete element which is affected might change when the hash function changes 906 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); 907 CX_TEST_ASSERT(cxMapGet(dst, "k4") == NULL); 908 } 909 cxMapFree(dst); 910 cxMapFree(s1); 911 cxMapFree(s2); 912 } 913 914 CX_TEST(test_hash_map_list_intersection) { 915 CxMap *dst = cxHashMapCreateSimple(sizeof(int)); 916 CxMap *src = cxHashMapCreateSimple(sizeof(int)); 917 CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); 918 919 const char *src_keys[] = {"k1", "k2", "k3", "k4"}; 920 int src_values[] = {1, 3, 4, 6}; 921 for (unsigned int i = 0 ; i < 4 ; i++) { 922 cxMapPut(src, src_keys[i], &src_values[i]); 923 } 924 const char *k[] = {"k4", "k5", "k2", "k6"}; 925 for (unsigned int i = 0 ; i < 4 ; i++) { 926 CxHashKey key = CX_HASH_KEY(k[i]); 927 cxListAdd(keys, &key); 928 } 929 CX_TEST_DO { 930 int c = 4; 931 CX_TEST_ASSERT(0 == cxMapListIntersection(dst, src, keys, test_hash_map_clone_func, NULL, &c)); 932 CX_TEST_ASSERT(cxMapSize(dst) == 2); 933 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); 934 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); 935 } 936 cxMapFree(dst); 937 cxMapFree(src); 938 cxListFree(keys); 939 } 940 941 CX_TEST(test_hash_map_list_intersection_alloc_fail) { 942 CxMap *dst = cxHashMapCreateSimple(sizeof(int)); 943 CxMap *src = cxHashMapCreateSimple(sizeof(int)); 944 CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); 945 946 const char *src_keys[] = {"k1", "k2", "k3", "k4"}; 947 int src_values[] = {1, 3, 4, 6}; 948 for (unsigned int i = 0 ; i < 4 ; i++) { 949 cxMapPut(src, src_keys[i], &src_values[i]); 950 } 951 const char *k[] = {"k4", "k5", "k2", "k6"}; 952 for (unsigned int i = 0 ; i < 4 ; i++) { 953 CxHashKey key = CX_HASH_KEY(k[i]); 954 cxListAdd(keys, &key); 955 } 956 CX_TEST_DO { 957 int c = 4; 958 test_hash_map_clone_func_max_enabled = true; 959 test_hash_map_clone_func_max_clones = 1; 960 CX_TEST_ASSERT(0 != cxMapListIntersection(dst, src, keys, test_hash_map_clone_func, NULL, &c)); 961 test_hash_map_clone_func_max_enabled = false; 962 CX_TEST_ASSERT(cxMapSize(dst) == 1); 963 // the concrete element which is affected might change when the hash function changes 964 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); 965 CX_TEST_ASSERT(cxMapGet(dst, "k4") == NULL); 966 } 967 cxMapFree(dst); 968 cxMapFree(src); 969 cxListFree(keys); 970 } 971 972 CX_TEST(test_hash_map_intersection_non_empty_target) { 973 CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); 974 cxDefineAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator); 975 976 CxMap *s1 = cxHashMapCreateSimple(sizeof(int)); 977 CxMap *s2 = cxHashMapCreateSimple(sizeof(int)); 978 const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; 979 int s1_values[] = {1, 3, 4, 6}; 980 const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; 981 int s2_values[] = {5, 9, 15, 23}; 982 for (unsigned int i = 0 ; i < 4 ; i++) { 983 cxMapPut(s1, s1_keys[i], &s1_values[i]); 984 cxMapPut(s2, s2_keys[i], &s2_values[i]); 985 } 986 987 // add k7 to dst which is not in src, and also not in the difference 988 int *k7 = cxMallocDefault(sizeof(int)); 989 *k7 = 1337; 990 cxMapPut(dst, "k7", k7); 991 992 CX_TEST_DO { 993 int c = 4; 994 CX_TEST_ASSERT(0 == cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, NULL, &c)); 995 CX_TEST_ASSERT(cxMapSize(dst) == 3); 996 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); 997 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); 998 CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k7") == 1337); 999 } 1000 cxMapFree(dst); 1001 cxMapFree(s1); 1002 cxMapFree(s2); 1003 } 1004 1005 CX_TEST(test_hash_map_list_intersection_non_empty_target) { 1006 CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); 1007 cxDefineAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator); 1008 CxMap *src = cxHashMapCreateSimple(sizeof(int)); 1009 CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); 1010 1011 const char *src_keys[] = {"k1", "k2", "k3", "k4"}; 1012 int src_values[] = {1, 3, 4, 6}; 1013 for (unsigned int i = 0 ; i < 4 ; i++) { 1014 cxMapPut(src, src_keys[i], &src_values[i]); 1015 } 1016 const char *k[] = {"k4", "k5", "k2", "k6"}; 1017 for (unsigned int i = 0 ; i < 4 ; i++) { 1018 CxHashKey key = CX_HASH_KEY(k[i]); 1019 cxListAdd(keys, &key); 1020 } 1021 1022 // add k7 to dst which is not in src, and also not in the difference 1023 int *k7 = cxMallocDefault(sizeof(int)); 1024 *k7 = 1337; 1025 cxMapPut(dst, "k7", k7); 1026 1027 CX_TEST_DO { 1028 int c = 4; 1029 CX_TEST_ASSERT(0 == cxMapListIntersection(dst, src, keys, test_hash_map_clone_func, NULL, &c)); 1030 CX_TEST_ASSERT(cxMapSize(dst) == 3); 1031 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); 1032 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); 1033 CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k7") == 1337); 1034 } 1035 1036 cxMapFree(dst); 1037 cxMapFree(src); 1038 cxListFree(keys); 1039 } 1040 1041 CX_TEST(test_hash_map_intersection_ptr) { 1042 CxTestingAllocator talloc; 1043 cx_testing_allocator_init(&talloc); 1044 CxAllocator *allocator = &talloc.base; 1045 CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); 1046 cxDefineAdvancedDestructor(dst, cxFree, allocator); 1047 1048 CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); 1049 CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); 1050 const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; 1051 int s1_values[] = {1, 3, 4, 6}; 1052 const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; 1053 int s2_values[] = {5, 9, 15, 23}; 1054 for (unsigned int i = 0 ; i < 4 ; i++) { 1055 cxMapPut(s1, s1_keys[i], &s1_values[i]); 1056 cxMapPut(s2, s2_keys[i], &s2_values[i]); 1057 } 1058 CX_TEST_DO { 1059 int c = 4; 1060 CX_TEST_ASSERT(0 == cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, allocator, &c)); 1061 CX_TEST_ASSERT(cxMapSize(dst) == 2); 1062 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); 1063 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); 1064 CX_TEST_ASSERT(cx_testing_allocator_used(&talloc)); 1065 } 1066 cxMapFree(dst); 1067 cxMapFree(s1); 1068 cxMapFree(s2); 1069 cx_testing_allocator_destroy(&talloc); 1070 } 1071 1072 CX_TEST(test_hash_map_union) { 1073 CxMap *s1 = cxHashMapCreateSimple(sizeof(int)); 1074 CxMap *s2 = cxHashMapCreateSimple(sizeof(int)); 1075 const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; 1076 int s1_values[] = {1, 3, 4, 6}; 1077 const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; 1078 int s2_values[] = {5, 9, 15, 23}; 1079 for (unsigned int i = 0 ; i < 4 ; i++) { 1080 cxMapPut(s1, s1_keys[i], &s1_values[i]); 1081 cxMapPut(s2, s2_keys[i], &s2_values[i]); 1082 } 1083 CX_TEST_DO { 1084 int c = 4; 1085 CX_TEST_ASSERT(0 == cxMapUnion(s1, s2, test_hash_map_clone_func, NULL, &c)); 1086 CX_TEST_ASSERT(cxMapSize(s1) == 6); 1087 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k1")) == 1); 1088 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k2")) == 3); 1089 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k3")) == 4); 1090 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k4")) == 6); 1091 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k5")) == 13); 1092 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k6")) == 27); 1093 } 1094 cxMapFree(s1); 1095 cxMapFree(s2); 1096 } 1097 1098 CX_TEST(test_hash_map_union_ptr) { 1099 CxTestingAllocator talloc; 1100 cx_testing_allocator_init(&talloc); 1101 CxAllocator *allocator = &talloc.base; 1102 CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); 1103 cxDefineAdvancedDestructor(dst, cxFree, allocator); 1104 1105 CxMap *s1 = cxHashMapCreateSimple(sizeof(int)); 1106 CxMap *s2 = cxHashMapCreateSimple(sizeof(int)); 1107 const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; 1108 int s1_values[] = {1, 3, 4, 6}; 1109 const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; 1110 int s2_values[] = {5, 9, 15, 23}; 1111 for (unsigned int i = 0 ; i < 4 ; i++) { 1112 cxMapPut(s1, s1_keys[i], &s1_values[i]); 1113 cxMapPut(s2, s2_keys[i], &s2_values[i]); 1114 } 1115 CX_TEST_DO { 1116 int c = 4; 1117 CX_TEST_ASSERT(0 == cxMapClone(dst, s1, test_hash_map_clone_func, allocator, &c)); 1118 CX_TEST_ASSERT(0 == cxMapUnion(dst, s2, test_hash_map_clone_func, allocator, &c)); 1119 CX_TEST_ASSERT(cxMapSize(dst) == 6); 1120 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5); 1121 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); 1122 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); 1123 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); 1124 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k5")) == 13); 1125 CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k6")) == 27); 1126 CX_TEST_ASSERT(cx_testing_allocator_used(&talloc)); 1127 } 1128 cxMapFree(dst); 1129 cxMapFree(s1); 1130 cxMapFree(s2); 1131 cx_testing_allocator_destroy(&talloc); 1132 } 1133 1134 CX_TEST(test_hash_map_union_alloc_fail) { 1135 CxMap *s1 = cxHashMapCreateSimple(sizeof(int)); 1136 CxMap *s2 = cxHashMapCreateSimple(sizeof(int)); 1137 const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; 1138 int s1_values[] = {1, 3, 4, 6}; 1139 const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; 1140 int s2_values[] = {5, 9, 15, 23}; 1141 for (unsigned int i = 0 ; i < 4 ; i++) { 1142 cxMapPut(s1, s1_keys[i], &s1_values[i]); 1143 cxMapPut(s2, s2_keys[i], &s2_values[i]); 1144 } 1145 CX_TEST_DO { 1146 int c = 4; 1147 test_hash_map_clone_func_max_enabled = true; 1148 test_hash_map_clone_func_max_clones = 1; 1149 CX_TEST_ASSERT(0 != cxMapUnion(s1, s2, test_hash_map_clone_func, NULL, &c)); 1150 test_hash_map_clone_func_max_enabled = false; 1151 CX_TEST_ASSERT(cxMapSize(s1) == 5); 1152 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k1")) == 1); 1153 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k2")) == 3); 1154 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k3")) == 4); 1155 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k4")) == 6); 1156 // the concrete element which is affected might change when the hash function changes 1157 CX_TEST_ASSERT(cxMapGet(s1, "k5") == NULL); 1158 CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k6")) == 27); 1159 } 1160 cxMapFree(s1); 1161 cxMapFree(s2); 1162 } 1163 1164 CX_TEST(test_hash_map_simple_clones) { 1165 int v = 47; // the value does not matter in this test 1166 CxMap *a = cxHashMapCreateSimple(sizeof(int)); 1167 cxMapPut(a, "k1", &v); 1168 cxMapPut(a, "k2", &v); 1169 cxMapPut(a, "k3", &v); 1170 cxMapPut(a, "k4", &v); 1171 1172 CxMap *b = cxHashMapCreateSimple(sizeof(int)); 1173 cxMapPut(b, "k0", &v); 1174 cxMapPut(b, "k2", &v); 1175 cxMapPut(b, "k5", &v); 1176 1177 CxMap *c = cxHashMapCreateSimple(sizeof(int)); 1178 cxMapPut(c, "k3", &v); 1179 cxMapPut(c, "k4", &v); 1180 cxMapPut(c, "k5", &v); 1181 1182 1183 CxHashKey k; 1184 CxList *kl1 = cxArrayListCreateSimple(sizeof(CxHashKey), 4); 1185 cxCollectionCompareFunc(kl1, cx_hash_key_cmp); 1186 k = CX_HASH_KEY("k0"); 1187 cxListAdd(kl1, &k); 1188 k = CX_HASH_KEY("k2"); 1189 cxListAdd(kl1, &k); 1190 k = CX_HASH_KEY("k5"); 1191 cxListAdd(kl1, &k); 1192 1193 CxList *kl2 = cxArrayListCreateSimple(sizeof(CxHashKey), 4); 1194 cxCollectionCompareFunc(kl2, cx_hash_key_cmp); 1195 k = CX_HASH_KEY("k3"); 1196 cxListAdd(kl2, &k); 1197 k = CX_HASH_KEY("k4"); 1198 cxListAdd(kl2, &k); 1199 k = CX_HASH_KEY("k5"); 1200 cxListAdd(kl2, &k); 1201 1202 CxMap *d1 = cxHashMapCreateSimple(sizeof(int)); 1203 CxMap *d2 = cxHashMapCreateSimple(sizeof(int)); 1204 1205 CX_TEST_DO { 1206 CX_TEST_ASSERT(0 == cxMapCloneSimple(d1, a)); 1207 CX_TEST_ASSERT(!cxMapContains(d1, "k0")); 1208 CX_TEST_ASSERT(cxMapContains(d1, "k1")); 1209 CX_TEST_ASSERT(cxMapContains(d1, "k2")); 1210 CX_TEST_ASSERT(cxMapContains(d1, "k3")); 1211 CX_TEST_ASSERT(cxMapContains(d1, "k4")); 1212 CX_TEST_ASSERT(!cxMapContains(d1, "k5")); 1213 1214 CX_TEST_ASSERT(0 == cxMapListDifferenceSimple(d2, d1, kl1)); 1215 CX_TEST_ASSERT(!cxMapContains(d2, "k0")); 1216 CX_TEST_ASSERT(cxMapContains(d2, "k1")); 1217 CX_TEST_ASSERT(!cxMapContains(d2, "k2")); 1218 CX_TEST_ASSERT(cxMapContains(d2, "k3")); 1219 CX_TEST_ASSERT(cxMapContains(d2, "k4")); 1220 CX_TEST_ASSERT(!cxMapContains(d2, "k5")); 1221 1222 cxMapClear(d1); 1223 CX_TEST_ASSERT(0 == cxMapListIntersectionSimple(d1, d2, kl2)); 1224 CX_TEST_ASSERT(!cxMapContains(d1, "k0")); 1225 CX_TEST_ASSERT(!cxMapContains(d1, "k1")); 1226 CX_TEST_ASSERT(!cxMapContains(d1, "k2")); 1227 CX_TEST_ASSERT(cxMapContains(d1, "k3")); 1228 CX_TEST_ASSERT(cxMapContains(d1, "k4")); 1229 1230 CX_TEST_ASSERT(0 == cxMapUnionSimple(d1, b)); 1231 CX_TEST_ASSERT(cxMapContains(d1, "k0")); 1232 CX_TEST_ASSERT(!cxMapContains(d1, "k1")); 1233 CX_TEST_ASSERT(cxMapContains(d1, "k2")); 1234 CX_TEST_ASSERT(cxMapContains(d1, "k3")); 1235 CX_TEST_ASSERT(cxMapContains(d1, "k4")); 1236 CX_TEST_ASSERT(cxMapContains(d1, "k5")); 1237 1238 cxMapClear(d2); 1239 CX_TEST_ASSERT(0 == cxMapDifferenceSimple(d2, d1, a)); 1240 CX_TEST_ASSERT(cxMapContains(d2, "k0")); 1241 CX_TEST_ASSERT(!cxMapContains(d2, "k1")); 1242 CX_TEST_ASSERT(!cxMapContains(d2, "k2")); 1243 CX_TEST_ASSERT(!cxMapContains(d2, "k3")); 1244 CX_TEST_ASSERT(!cxMapContains(d2, "k4")); 1245 CX_TEST_ASSERT(cxMapContains(d2, "k5")); 1246 1247 cxMapClear(d1); 1248 CX_TEST_ASSERT(0 == cxMapIntersectionSimple(d1, d2, c)); 1249 CX_TEST_ASSERT(!cxMapContains(d1, "k0")); 1250 CX_TEST_ASSERT(!cxMapContains(d1, "k1")); 1251 CX_TEST_ASSERT(!cxMapContains(d1, "k2")); 1252 CX_TEST_ASSERT(!cxMapContains(d1, "k3")); 1253 CX_TEST_ASSERT(!cxMapContains(d1, "k4")); 1254 CX_TEST_ASSERT(cxMapContains(d1, "k5")); 1255 } 1256 1257 cxMapFree(a); 1258 cxMapFree(b); 1259 cxMapFree(c); 1260 cxListFree(kl1); 1261 cxListFree(kl2); 1262 cxMapFree(d1); 1263 cxMapFree(d2); 1264 } 1265 1266 CX_TEST(test_empty_map_size) { 1267 CX_TEST_DO { 1268 CX_TEST_ASSERT(cxEmptyMap->collection.size == 0); 1269 CX_TEST_ASSERT(cxMapSize(cxEmptyMap) == 0); 1270 } 1271 } 1272 1273 CX_TEST(test_empty_map_iterator) { 1274 CxMap *map = cxEmptyMap; 1275 1276 CxMapIterator it1 = cxMapIterator(map); 1277 CxMapIterator it2 = cxMapIteratorValues(map); 1278 CxMapIterator it3 = cxMapIteratorKeys(map); 1279 CxMapIterator it4 = cxMapIterator(map); 1280 CxMapIterator it5 = cxMapIteratorValues(map); 1281 CxMapIterator it6 = cxMapIteratorKeys(map); 1282 1283 CX_TEST_DO { 1284 CX_TEST_ASSERT(!cxIteratorValid(it1)); 1285 CX_TEST_ASSERT(!cxIteratorValid(it2)); 1286 CX_TEST_ASSERT(!cxIteratorValid(it3)); 1287 CX_TEST_ASSERT(!cxIteratorValid(it4)); 1288 CX_TEST_ASSERT(!cxIteratorValid(it5)); 1289 CX_TEST_ASSERT(!cxIteratorValid(it6)); 1290 1291 int c = 0; 1292 cx_foreach(void*, data, it1) c++; 1293 cx_foreach(void*, data, it2) c++; 1294 cx_foreach(void*, data, it3) c++; 1295 cx_foreach(void*, data, it4) c++; 1296 cx_foreach(void*, data, it5) c++; 1297 cx_foreach(void*, data, it6) c++; 1298 CX_TEST_ASSERT(c == 0); 1299 } 1300 } 1301 1302 CX_TEST(test_null_map_iterator) { 1303 CxMap *map = NULL; 1304 1305 CxMapIterator it1 = cxMapIterator(map); 1306 CxMapIterator it2 = cxMapIteratorValues(map); 1307 CxMapIterator it3 = cxMapIteratorKeys(map); 1308 CxMapIterator it4 = cxMapIterator(map); 1309 CxMapIterator it5 = cxMapIteratorValues(map); 1310 CxMapIterator it6 = cxMapIteratorKeys(map); 1311 1312 CX_TEST_DO { 1313 CX_TEST_ASSERT(!cxIteratorValid(it1)); 1314 CX_TEST_ASSERT(!cxIteratorValid(it2)); 1315 CX_TEST_ASSERT(!cxIteratorValid(it3)); 1316 CX_TEST_ASSERT(!cxIteratorValid(it4)); 1317 CX_TEST_ASSERT(!cxIteratorValid(it5)); 1318 CX_TEST_ASSERT(!cxIteratorValid(it6)); 1319 1320 int c = 0; 1321 cx_foreach(void*, data, it1) c++; 1322 cx_foreach(void*, data, it2) c++; 1323 cx_foreach(void*, data, it3) c++; 1324 cx_foreach(void*, data, it4) c++; 1325 cx_foreach(void*, data, it5) c++; 1326 cx_foreach(void*, data, it6) c++; 1327 CX_TEST_ASSERT(c == 0); 1328 } 1329 } 1330 1331 CX_TEST(test_empty_map_no_ops) { 1332 CX_TEST_DO { 1333 // assertion not possible 1334 // test that no segfault happens and valgrind is happy 1335 cxMapClear(cxEmptyMap); 1336 cxMapFree(cxEmptyMap); 1337 CX_TEST_ASSERT(true); 1338 } 1339 } 1340 1341 CX_TEST(test_empty_map_get) { 1342 CX_TEST_DO { 1343 CxHashKey key = cx_hash_key_str("test"); 1344 CX_TEST_ASSERT(cxMapGet(cxEmptyMap, key) == NULL); 1345 } 1346 } 1347 1348 CX_TEST(test_hash_map_generics) { 1349 CxTestingAllocator talloc; 1350 cx_testing_allocator_init(&talloc); 1351 CxAllocator *allocator = &talloc.base; 1352 CX_TEST_DO { 1353 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); 1354 cxMapPut(map, "test", "test"); 1355 cxMapPut(map, cx_mutstr("foo"), "bar"); 1356 cxMapPut(map, cx_str("hallo"), "welt"); 1357 1358 CX_TEST_ASSERT(map->collection.size == 3); 1359 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "test"), "test")); 1360 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar")); 1361 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "hallo"), "welt")); 1362 1363 CX_TEST_ASSERT(0 == cxMapRemove(map, cx_str("test"))); 1364 const char *hallo = "hallo"; 1365 CX_TEST_ASSERT(0 == cxMapRemove(map, hallo)); 1366 cxMapPut(map, cx_hash_key_str("key"), "value"); 1367 1368 CX_TEST_ASSERT(map->collection.size == 2); 1369 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key"), "value")); 1370 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar")); 1371 1372 const char *r1, *r2; 1373 CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, "key", &r1)); 1374 CX_TEST_ASSERT(0 == strcmp(r1, "value")); 1375 CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, cx_str("foo"), &r2)); 1376 CX_TEST_ASSERT(0 == strcmp(r2, "bar")); 1377 r2 = "nope"; 1378 CX_TEST_ASSERT(0 != cxMapRemoveAndGet(map, cx_hash_key("notfound",9), &r2)); 1379 CX_TEST_ASSERT(0 == strcmp(r2, "nope")); 1380 1381 CX_TEST_ASSERT(map->collection.size == 0); 1382 1383 cxMapFree(map); 1384 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1385 } 1386 cx_testing_allocator_destroy(&talloc); 1387 } 1388 1389 struct test_map_kv { 1390 const char *key; 1391 const char *value; 1392 }; 1393 1394 static struct test_map_kv const test_map_operations[] = { 1395 {"key 1", "test"}, 1396 {"key 2", "blub"}, 1397 {"key 3", "hallo"}, 1398 {"key 2", "foobar"}, 1399 {"key 4", "value 4"}, 1400 {"key 5", "value 5"}, 1401 {"key 6", "value 6"}, 1402 {"key 4", NULL}, 1403 {"key 7", "value 7"}, 1404 {"key 8", "value 8"}, 1405 {"does not exist", NULL}, 1406 {"key 9", "value 9"}, 1407 {"key 6", "other value"}, 1408 {"key 7", "something else"}, 1409 {"key 8", NULL}, 1410 {"key 2", NULL}, 1411 {"key 8", "new value"}, 1412 }; 1413 static const size_t test_map_operations_len = 1414 sizeof(test_map_operations) / sizeof(struct test_map_kv); 1415 static struct test_map_kv test_map_reference[] = { 1416 {"key 1", NULL}, 1417 {"key 2", NULL}, 1418 {"key 3", NULL}, 1419 {"key 4", NULL}, 1420 {"key 5", NULL}, 1421 {"key 6", NULL}, 1422 {"key 7", NULL}, 1423 {"key 8", NULL}, 1424 {"key 9", NULL}, 1425 }; 1426 static const size_t test_map_reference_len = 1427 sizeof(test_map_reference) / sizeof(struct test_map_kv); 1428 1429 static void test_map_reference_put(const char *key, const char *value) { 1430 for (size_t i = 0 ; i < test_map_reference_len ; i++) { 1431 if (0 == strcmp(key, test_map_reference[i].key)) { 1432 test_map_reference[i].value = value; 1433 return; 1434 } 1435 } 1436 } 1437 1438 static const char *test_map_reference_get(const char *key) { 1439 for (size_t i = 0 ; i < test_map_reference_len ; i++) { 1440 if (0 == strcmp(key, test_map_reference[i].key)) { 1441 return test_map_reference[i].value; 1442 } 1443 } 1444 return NULL; 1445 } 1446 1447 static const char *test_map_reference_remove(const char *key) { 1448 for (size_t i = 0 ; i < test_map_reference_len ; i++) { 1449 if (0 == strcmp(key, test_map_reference[i].key)) { 1450 const char *ret = test_map_reference[i].value; 1451 test_map_reference[i].value = NULL; 1452 return ret; 1453 } 1454 } 1455 return NULL; 1456 } 1457 1458 static size_t test_map_reference_size(void) { 1459 size_t size = 0; 1460 for (size_t i = 0; i < test_map_reference_len; i++) { 1461 if (test_map_reference[i].value != NULL) { 1462 size++; 1463 } 1464 } 1465 return size; 1466 } 1467 1468 static CX_TEST_SUBROUTINE(verify_map_contents, CxMap *map) { 1469 // verify that the reference map has same size (i.e. no other keys are mapped) 1470 CX_TEST_ASSERT(map->collection.size == test_map_reference_size()); 1471 1472 // verify key iterator 1473 { 1474 // collect the keys from the map iterator 1475 CxMapIterator keyiter = cxMapIteratorKeys(map); 1476 CX_TEST_ASSERT(keyiter.elem_size == sizeof(CxHashKey)); 1477 CX_TEST_ASSERT(keyiter.elem_count == map->collection.size); 1478 CxHashKey *keys = calloc(map->collection.size, sizeof(CxHashKey)); 1479 cx_foreach(CxHashKey*, elem, keyiter) { 1480 keys[keyiter.index] = *elem; 1481 } 1482 CX_TEST_ASSERT(keyiter.index == map->collection.size); 1483 // verify that all keys are mapped to values in reference map 1484 for (size_t i = 0 ; i < map->collection.size ; i++) { 1485 cxmutstr ksz = cx_strdup(cx_strn(keys[i].data, keys[i].len)); 1486 CX_TEST_ASSERT(test_map_reference_get(ksz.ptr) != NULL); 1487 cx_strfree(&ksz); 1488 } 1489 free(keys); 1490 } 1491 1492 // verify value iterator 1493 { 1494 // by using that the values in our test data are unique strings 1495 // we can re-use a similar approach as above 1496 CxMapIterator valiter = cxMapIteratorValues(map); 1497 CX_TEST_ASSERT(valiter.elem_size == map->collection.elem_size); 1498 CX_TEST_ASSERT(valiter.elem_count == map->collection.size); 1499 const char ** values = calloc(map->collection.size, sizeof(const char *)); 1500 cx_foreach(const char *, elem, valiter) { 1501 values[valiter.index] = elem; 1502 } 1503 CX_TEST_ASSERT(valiter.index == map->collection.size); 1504 // verify that all values are present in the reference map 1505 for (size_t i = 0 ; i < map->collection.size ; i++) { 1506 bool found = false; 1507 for (size_t j = 0; j < test_map_reference_len ; j++) { 1508 if (test_map_reference[j].value == values[i]) { 1509 found = true; 1510 break; 1511 } 1512 } 1513 CX_TEST_ASSERTM(found, "A value was not found in the reference map"); 1514 } 1515 free(values); 1516 } 1517 1518 // verify pair iterator 1519 { 1520 CxMapIterator pairiter = cxMapIterator(map); 1521 CX_TEST_ASSERT(pairiter.elem_size == sizeof(CxMapEntry)); 1522 CX_TEST_ASSERT(pairiter.elem_count == map->collection.size); 1523 struct test_map_kv *pairs = calloc(map->collection.size, sizeof(struct test_map_kv)); 1524 cx_foreach(CxMapEntry*, entry, pairiter) { 1525 const CxHashKey *key = entry->key; 1526 pairs[pairiter.index].key = cx_strdup(cx_strn(key->data, key->len)).ptr; 1527 pairs[pairiter.index].value = entry->value; 1528 } 1529 CX_TEST_ASSERT(pairiter.index == map->collection.size); 1530 // verify that all pairs are present in the reference map 1531 for (size_t i = 0 ; i < map->collection.size ; i++) { 1532 CX_TEST_ASSERT(test_map_reference_get(pairs[i].key) == pairs[i].value); 1533 // this was cx_strdup'ed 1534 cxFreeDefault((void*)pairs[i].key); 1535 } 1536 free(pairs); 1537 } 1538 } 1539 1540 CX_TEST(test_hash_map_basic_operations) { 1541 CxTestingAllocator talloc; 1542 cx_testing_allocator_init(&talloc); 1543 CxAllocator *allocator = &talloc.base; 1544 CX_TEST_DO { 1545 // create the map 1546 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 8); 1547 1548 // clear the reference map 1549 for (size_t i = 0 ; i < test_map_reference_len ; i++) { 1550 test_map_reference[i].value = NULL; 1551 } 1552 1553 // verify iterators for empty map 1554 CX_TEST_CALL_SUBROUTINE(verify_map_contents, map); 1555 1556 // execute operations and verify results 1557 for (size_t i = 0 ; i < test_map_operations_len ; i++) { 1558 struct test_map_kv kv = test_map_operations[i]; 1559 CxHashKey key = cx_hash_key_str(kv.key); 1560 key.hash = 0; // force the hash map to compute the hash 1561 if (kv.value != NULL) { 1562 // execute a put operation and verify that the exact value can be read back 1563 test_map_reference_put(kv.key, kv.value); 1564 int result = cxMapPut(map, key, (void *) kv.value); 1565 CX_TEST_ASSERT(result == 0); 1566 void *added = cxMapGet(map, key); 1567 CX_TEST_ASSERT(0 == memcmp(kv.value, added, strlen(kv.value))); 1568 } else { 1569 // execute a remove and verify that the removed element was returned (or NULL) 1570 const char *found = test_map_reference_remove(kv.key); 1571 void *removed = (void*) 0x1337; 1572 int result = cxMapRemoveAndGet(map, key, &removed); 1573 if (found == NULL) { 1574 CX_TEST_ASSERT(0 != result); 1575 CX_TEST_ASSERT(removed == (void*) 0x1337); 1576 } else { 1577 CX_TEST_ASSERT(0 == result); 1578 CX_TEST_ASSERT(removed == found); 1579 } 1580 1581 } 1582 // compare the current map state with the reference map 1583 CX_TEST_CALL_SUBROUTINE(verify_map_contents, map); 1584 } 1585 1586 // destroy the map and verify the memory (de)allocations 1587 cxMapFree(map); 1588 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1589 } 1590 cx_testing_allocator_destroy(&talloc); 1591 } 1592 1593 CxTestSuite *cx_test_suite_hash_map(void) { 1594 CxTestSuite *suite = cx_test_suite_new("map"); 1595 1596 cx_test_register(suite, test_hash_map_create); 1597 cx_test_register(suite, test_hash_map_create_store_pointers); 1598 cx_test_register(suite, test_hash_map_basic_operations); 1599 cx_test_register(suite, test_hash_map_emplace); 1600 cx_test_register(suite, test_hash_map_emplace_pointers); 1601 cx_test_register(suite, test_hash_map_rehash); 1602 cx_test_register(suite, test_hash_map_rehash_not_required); 1603 cx_test_register(suite, test_hash_map_clear); 1604 cx_test_register(suite, test_hash_map_store_ucx_strings); 1605 cx_test_register(suite, test_hash_map_integer_keys); 1606 cx_test_register(suite, test_hash_map_remove_via_iterator); 1607 cx_test_register(suite, test_hash_map_simple_destructor_objects); 1608 cx_test_register(suite, test_hash_map_advanced_destructor_objects); 1609 cx_test_register(suite, test_hash_map_simple_destructor_pointers); 1610 cx_test_register(suite, test_hash_map_advanced_destructor_pointers); 1611 cx_test_register(suite, test_hash_map_clone); 1612 cx_test_register(suite, test_hash_map_clone_alloc_fail); 1613 cx_test_register(suite, test_hash_map_clone_ptr); 1614 cx_test_register(suite, test_hash_map_difference); 1615 cx_test_register(suite, test_hash_map_difference_ptr); 1616 cx_test_register(suite, test_hash_map_list_difference); 1617 cx_test_register(suite, test_hash_map_difference_alloc_fail); 1618 cx_test_register(suite, test_hash_map_list_difference_alloc_fail); 1619 cx_test_register(suite, test_hash_map_difference_non_empty_target); 1620 cx_test_register(suite, test_hash_map_list_difference_non_empty_target); 1621 cx_test_register(suite, test_hash_map_intersection); 1622 cx_test_register(suite, test_hash_map_intersection_ptr); 1623 cx_test_register(suite, test_hash_map_list_intersection); 1624 cx_test_register(suite, test_hash_map_intersection_alloc_fail); 1625 cx_test_register(suite, test_hash_map_list_intersection_alloc_fail); 1626 cx_test_register(suite, test_hash_map_intersection_non_empty_target); 1627 cx_test_register(suite, test_hash_map_list_intersection_non_empty_target); 1628 cx_test_register(suite, test_hash_map_union); 1629 cx_test_register(suite, test_hash_map_union_ptr); 1630 cx_test_register(suite, test_hash_map_union_alloc_fail); 1631 cx_test_register(suite, test_hash_map_simple_clones); 1632 cx_test_register(suite, test_empty_map_no_ops); 1633 cx_test_register(suite, test_empty_map_size); 1634 cx_test_register(suite, test_empty_map_get); 1635 cx_test_register(suite, test_empty_map_iterator); 1636 cx_test_register(suite, test_null_map_iterator); 1637 cx_test_register(suite, test_hash_map_generics); 1638 1639 return suite; 1640 } 1641