tests/test_hash_map.c@dfc0ddd9571e
tests/test_hash_map.c
Sun, 23 Nov 2025 13:15:19 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Sun, 23 Nov 2025 13:15:19 +0100
- changeset 1508
- dfc0ddd9571e
- parent 1483
- 97a6cf1520ba
- permissions
- -rw-r--r--
optimize sorted insertion by using the infimum instead of the supremum
The reason is that the supremum returns the equal element with the smallest index, and we want the largest.
Therefore, we use the infimum, which already gives us the largest index when there are equal elements, and increase the index by one. The infimum is also guaranteed to exist in that case.
/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. * * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #include "cx/test.h" #include "util_allocator.h" #include "cx/array_list.h" #include "cx/list.h" #include "cx/hash_map.h" CX_TEST(test_hash_map_create) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, 1, 0); struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map; CX_TEST_ASSERT(hmap->bucket_count > 0); for(size_t i = 0 ; i < hmap->bucket_count ; i++) { CX_TEST_ASSERT(hmap->buckets[i] == NULL); } CX_TEST_ASSERT(map->collection.elem_size == 1); CX_TEST_ASSERT(map->collection.size == 0); CX_TEST_ASSERT(map->collection.allocator == allocator); CX_TEST_ASSERT(!map->collection.store_pointer); CX_TEST_ASSERT(map->collection.cmpfunc == NULL); CX_TEST_ASSERT(map->collection.simple_destructor == NULL); CX_TEST_ASSERT(map->collection.advanced_destructor == NULL); CX_TEST_ASSERT(map->collection.destructor_data == NULL); cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_create_store_pointers) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map; CX_TEST_ASSERT(hmap->bucket_count > 0); for (size_t i = 0; i < hmap->bucket_count; i++) { CX_TEST_ASSERT(hmap->buckets[i] == NULL); } CX_TEST_ASSERT(map->collection.size == 0); CX_TEST_ASSERT(map->collection.allocator == allocator); CX_TEST_ASSERT(map->collection.store_pointer); CX_TEST_ASSERT(map->collection.elem_size == sizeof(void *)); cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_emplace) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, 20, 4); char *v = cxMapEmplace(map, "key 1"); CX_TEST_ASSERT(v != NULL); strcpy(v, "val 1"); char *tv = cxMapGet(map, "key 1"); CX_TEST_ASSERT(tv != NULL); CX_TEST_ASSERT(0 == strcmp(tv, "val 1")); v = cxMapEmplace(map, "key 1"); CX_TEST_ASSERT(v != NULL); CX_TEST_ASSERT(0 != strcmp(v, "val 1")); tv = cxMapGet(map, "key 1"); CX_TEST_ASSERT(tv != NULL); CX_TEST_ASSERT(0 != strcmp(tv, "val 1")); cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_emplace_pointers) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 4); cxDefineAdvancedDestructor(map, cxFree, allocator); char *val1 = cxMalloc(allocator, 8); strcpy(val1, "val 1"); char *val2 = cxMalloc(allocator, 8); strcpy(val2, "val 2"); char **v1 = cxMapEmplace(map, "key 1"); CX_TEST_ASSERT(v1 != NULL); *v1 = val1; char *tv = cxMapGet(map, "key 1"); CX_TEST_ASSERT(tv != NULL); CX_TEST_ASSERT(0 == strcmp(tv, "val 1")); // this will call the destructor of former v1 char **v2 = cxMapEmplace(map, "key 1"); CX_TEST_ASSERT(v2 != NULL); *v2 = val2; tv = cxMapGet(map, "key 1"); CX_TEST_ASSERT(tv != NULL); CX_TEST_ASSERT(0 == strcmp(tv, "val 2")); cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_rehash) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 7); cxMapPut(map, "key 1", (void *) "val 1"); cxMapPut(map, "key 2", (void *) "val 2"); cxMapPut(map, "key 3", (void *) "val 3"); cxMapPut(map, "foo 4", (void *) "val 4"); cxMapPut(map, "key 5", (void *) "val 5"); cxMapPut(map, "key 6", (void *) "val 6"); cxMapPut(map, "bar 7", (void *) "val 7"); cxMapPut(map, "key 8", (void *) "val 8"); cxMapPut(map, "key 9", (void *) "val 9"); cxMapPut(map, "key 10", (void *) "val 10"); CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 7); int result = cxMapRehash(map); CX_TEST_ASSERT(result == 0); CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 25); CX_TEST_ASSERT(map->collection.size == 10); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 1"), "val 1")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 2"), "val 2")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 3"), "val 3")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo 4"), "val 4")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 5"), "val 5")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 6"), "val 6")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "bar 7"), "val 7")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 8"), "val 8")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 9"), "val 9")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 10"), "val 10")); cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_rehash_not_required) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 8); cxMapPut(map, "key 1", (void *) "val 1"); cxMapPut(map, "key 2", (void *) "val 2"); cxMapPut(map, "key 3", (void *) "val 3"); cxMapPut(map, "key 4", (void *) "val 4"); cxMapPut(map, "key 5", (void *) "val 5"); cxMapPut(map, "key 6", (void *) "val 6"); // 6/8 does not exceed 0.75, therefore the function should not rehash int result = cxMapRehash(map); CX_TEST_ASSERT(result == 0); CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 8); cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_clear) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); cxMapPut(map, "key 1", (void *) "val 1"); cxMapPut(map, "key 2", (void *) "val 2"); cxMapPut(map, "key 3", (void *) "val 3"); CX_TEST_ASSERT(map->collection.size == 3); cxMapClear(map); CX_TEST_ASSERT(map->collection.size == 0); CX_TEST_ASSERT(cxMapGet(map, "key 1") == NULL); CX_TEST_ASSERT(cxMapGet(map, "key 2") == NULL); CX_TEST_ASSERT(cxMapGet(map, "key 3") == NULL); cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_store_ucx_strings) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { // create the map CxMap *map = cxHashMapCreate(allocator, sizeof(cxstring), 8); // define some strings cxstring s1 = CX_STR("this"); cxstring s2 = CX_STR("is"); cxstring s3 = CX_STR("a"); cxstring s4 = CX_STR("test"); cxstring s5 = CX_STR("setup"); // put them into the map cxMapPut(map, "s1", &s1); cxMapPut(map, "s2", &s2); cxMapPut(map, "s3", &s3); cxMapPut(map, "s4", &s4); // overwrite a value cxMapPut(map, "s1", &s5); // look up a string cxstring * s3p = cxMapGet(map, "s3"); CX_TEST_ASSERT(s3p->length == s3.length); CX_TEST_ASSERT(s3p->ptr == s3.ptr); CX_TEST_ASSERT(s3p != &s3); // remove a string cxstring ret = {0}; CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, "s2", &ret)); CX_TEST_ASSERT(map->collection.size == 3); CX_TEST_ASSERT(0 == cx_strcmp(ret, cx_str("is"))); // iterate bool s3found = false, s4found = false, s5found = false; CxMapIterator iter = cxMapIteratorValues(map); cx_foreach(cxstring*, s, iter) { s3found |= s3.ptr == s->ptr; s4found |= s4.ptr == s->ptr; s5found |= s5.ptr == s->ptr; } CX_TEST_ASSERT(s3found && s4found && s5found); cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_integer_keys) { CxMap *map = cxHashMapCreateSimple(sizeof(cxstring)); CX_TEST_DO { cxstring s1 = CX_STR("hello"); cxstring s2 = CX_STR("world"); cxMapPut(map, UINT32_C(70875), &s1); cxMapPut(map, UINT64_C(5785133750), &s2); CX_TEST_ASSERT(cx_strcmp_p(&s1, cxMapGet(map, UINT32_C(70875))) == 0); CX_TEST_ASSERT(cx_strcmp_p(&s2, cxMapGet(map, UINT64_C(5785133750))) == 0); } cxMapFree(map); } CX_TEST(test_hash_map_remove_via_iterator) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 4); cxMapPut(map, "key 1", (void *) "val 1"); cxMapPut(map, "key 2", (void *) "val 2"); cxMapPut(map, "key 3", (void *) "val 3"); cxMapPut(map, "key 4", (void *) "val 4"); cxMapPut(map, "key 5", (void *) "val 5"); cxMapPut(map, "key 6", (void *) "val 6"); CxMapIterator iter = cxMapIterator(map); cx_foreach(CxMapEntry*, entry, iter) { if (((const char *)entry->key->data)[4] % 2 == 1) cxIteratorFlagRemoval(iter); } CX_TEST_ASSERT(cxMapSize(map) == 3); CX_TEST_ASSERT(iter.elem_count == 3); CX_TEST_ASSERT(iter.index == map->collection.size); CX_TEST_ASSERT(cxMapGet(map, "key 1") == NULL); CX_TEST_ASSERT(cxMapGet(map, "key 2") != NULL); CX_TEST_ASSERT(cxMapGet(map, "key 3") == NULL); CX_TEST_ASSERT(cxMapGet(map, "key 4") != NULL); CX_TEST_ASSERT(cxMapGet(map, "key 5") == NULL); CX_TEST_ASSERT(cxMapGet(map, "key 6") != NULL); cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } struct test_destr_struct { char *str; }; static void test_simple_destructor(void *d) { struct test_destr_struct *data = d; strcpy(data->str, "OK"); } static void test_advanced_destructor( cx_attr_unused void *unused, void *d ) { test_simple_destructor(d); } static CX_TEST_SUBROUTINE(verify_any_destructor, CxMap *map) { CxHashKey k1 = cx_hash_key_str("key 1"); CxHashKey k2 = cx_hash_key_str("key 2"); CxHashKey k3 = cx_hash_key_str("key 3"); CxHashKey k4 = cx_hash_key_str("key 4"); CxHashKey k5 = cx_hash_key_str("key 5"); char v1[] = "val 1"; char v2[] = "val 2"; char v3[] = "val 3"; char v4[] = "val 4"; char v5[] = "val 5"; char v6[] = "val 6"; char v7[] = "val 7"; struct test_destr_struct d1 = {v1}; struct test_destr_struct d2 = {v2}; struct test_destr_struct d3 = {v3}; struct test_destr_struct d4 = {v4}; struct test_destr_struct d5 = {v5}; struct test_destr_struct d6 = {v6}; struct test_destr_struct d7 = {v7}; void *v1data = &d1; void *v2data = &d2; void *v3data = &d3; void *v4data = &d4; void *v5data = &d5; void *v6data = &d6; void *v7data = &d7; cxMapPut(map, k1, v1data); cxMapPut(map, k2, v2data); cxMapPut(map, k3, v3data); cxMapPut(map, k4, v4data); CX_TEST_ASSERT(0 == cxMapRemove(map, k2)); if (map->collection.store_pointer) { struct test_destr_struct *r; CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, k3, &r)); CX_TEST_ASSERT(r == &d3); } else { struct test_destr_struct r; CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, k3, &r)); CX_TEST_ASSERT(r.str == v3); } CX_TEST_ASSERT(0 == strcmp(v1, "val 1")); CX_TEST_ASSERT(0 == strcmp(v2, "OK")); CX_TEST_ASSERT(0 == strcmp(v3, "val 3")); CX_TEST_ASSERT(0 == strcmp(v4, "val 4")); CX_TEST_ASSERT(0 == strcmp(v5, "val 5")); // put k5, overwrite k1, put new k3 cxMapPut(map, k5, v5data); cxMapPut(map, k1, v6data); cxMapPut(map, k3, v7data); // destructor the value behind k1 was called, but for k3 not CX_TEST_ASSERT(0 == strcmp(v1, "OK")); CX_TEST_ASSERT(0 == strcmp(v3, "val 3")); // now remove k1 via key iterator and k5 (val 5) via value iterator v1[0] = 'y'; // mark v1 and check that destr is not called for previous val { CxMapIterator iter = cxMapIteratorKeys(map); CX_TEST_ASSERT(iter.elem_count == 4); CX_TEST_ASSERT(cxMapSize(map) == 4); cx_foreach(CxHashKey*, key, iter) { if (((char*)key->data)[4] == '1') cxIteratorFlagRemoval(iter); } CX_TEST_ASSERT(iter.elem_count == 3); CX_TEST_ASSERT(cxMapSize(map) == 3); } { CxMapIterator iter = cxMapIteratorValues(map); cx_foreach(struct test_destr_struct*, v, iter) { if (v->str[4] == '5') cxIteratorFlagRemoval(iter); } CX_TEST_ASSERT(iter.elem_count == 2); CX_TEST_ASSERT(cxMapSize(map) == 2); } CX_TEST_ASSERT(0 == strcmp(v1, "yK")); CX_TEST_ASSERT(0 == strcmp(v2, "OK")); CX_TEST_ASSERT(0 == strcmp(v3, "val 3")); CX_TEST_ASSERT(0 == strcmp(v4, "val 4")); CX_TEST_ASSERT(0 == strcmp(v5, "OK")); CX_TEST_ASSERT(0 == strcmp(v6, "OK")); CX_TEST_ASSERT(0 == strcmp(v7, "val 7")); // mark the already destroyed items // and check that they are not destroyed again v1[0] = v2[0] = v4[0] = v5[0] = 'c'; cxMapFree(map); CX_TEST_ASSERT(0 == strcmp(v1, "cK")); CX_TEST_ASSERT(0 == strcmp(v2, "cK")); CX_TEST_ASSERT(0 == strcmp(v3, "val 3")); CX_TEST_ASSERT(0 == strcmp(v4, "OK")); CX_TEST_ASSERT(0 == strcmp(v5, "cK")); CX_TEST_ASSERT(0 == strcmp(v6, "OK")); CX_TEST_ASSERT(0 == strcmp(v7, "OK")); } CX_TEST(test_hash_map_simple_destructor_objects) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, sizeof(struct test_destr_struct), 0); map->collection.simple_destructor = test_simple_destructor; CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_advanced_destructor_objects) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, sizeof(struct test_destr_struct), 0); map->collection.advanced_destructor = test_advanced_destructor; CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_simple_destructor_pointers) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); map->collection.simple_destructor = test_simple_destructor; CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_advanced_destructor_pointers) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); map->collection.advanced_destructor = test_advanced_destructor; CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } static bool test_hash_map_clone_func_max_enabled = false; static unsigned test_hash_map_clone_func_max_clones; static void *test_hash_map_clone_func(void *dst, const void *src, const CxAllocator *al, void *data) { if (test_hash_map_clone_func_max_enabled) { if (test_hash_map_clone_func_max_clones == 0) return NULL; test_hash_map_clone_func_max_clones--; } if (dst == NULL) { dst = cxMalloc(al, sizeof(int)); } *((int*)dst) = *((int*)src) + *((int*)data); return dst; } CX_TEST(test_hash_map_clone) { CxMap *dst = cxHashMapCreateSimple(sizeof(int)); CxMap *src = cxHashMapCreateSimple(sizeof(int)); const char *exist_keys[] = {"k1", "k2", "k3"}; int exists[] = {1, 3, 4}; const char *source_keys[] = {"k4", "k2", "k5"}; int source[] = {7, 9, 15}; for (unsigned int i = 0 ; i < 3 ; i++) { cxMapPut(dst, exist_keys[i], &exists[i]); cxMapPut(src, source_keys[i], &source[i]); } CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapClone(dst, src, test_hash_map_clone_func, NULL, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 5); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 1); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 13); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 4); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 11); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k5")) == 19); CX_TEST_ASSERT(cxMapSize(src) == 3); CX_TEST_ASSERT(*((int*)cxMapGet(src, "k4")) == 7); CX_TEST_ASSERT(*((int*)cxMapGet(src, "k2")) == 9); CX_TEST_ASSERT(*((int*)cxMapGet(src, "k5")) == 15); } cxMapFree(dst); cxMapFree(src); } CX_TEST(test_hash_map_clone_alloc_fail) { CxMap *dst = cxHashMapCreateSimple(sizeof(int)); CxMap *src = cxHashMapCreateSimple(sizeof(int)); const char *exist_keys[] = {"k1", "k2", "k3"}; int exists[] = {1, 3, 4}; const char *source_keys[] = {"k4", "k2", "k5"}; int source[] = {7, 9, 15}; for (unsigned int i = 0 ; i < 3 ; i++) { cxMapPut(dst, exist_keys[i], &exists[i]); cxMapPut(src, source_keys[i], &source[i]); } CX_TEST_DO { int c = 4; test_hash_map_clone_func_max_enabled = true; test_hash_map_clone_func_max_clones = 2; CX_TEST_ASSERT(0 != cxMapClone(dst, src, test_hash_map_clone_func, NULL, &c)); test_hash_map_clone_func_max_enabled = false; CX_TEST_ASSERT(cxMapSize(dst) == 4); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 1); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 13); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 4); // the concrete element which is affected might change when the hash function changes CX_TEST_ASSERT(cxMapGet(dst, "k4") == NULL); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k5")) == 19); CX_TEST_ASSERT(cxMapSize(src) == 3); CX_TEST_ASSERT(*((int*)cxMapGet(src, "k4")) == 7); CX_TEST_ASSERT(*((int*)cxMapGet(src, "k2")) == 9); CX_TEST_ASSERT(*((int*)cxMapGet(src, "k5")) == 15); } cxMapFree(dst); cxMapFree(src); } CX_TEST(test_hash_map_clone_ptr) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); cxDefineAdvancedDestructor(dst, cxFree, allocator); CxMap *src = cxHashMapCreateSimple(CX_STORE_POINTERS); const char *exist_keys[] = {"k1", "k2", "k3"}; int exists[] = {1, 3, 4}; const char *source_keys[] = {"k4", "k2", "k5"}; int source[] = {7, 9, 15}; for (unsigned int i = 0 ; i < 3 ; i++) { int *y = cxMalloc(allocator, sizeof(int)); *y = exists[i]; cxMapPut(dst, exist_keys[i], y); cxMapPut(src, source_keys[i], &source[i]); } CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapClone(dst, src, test_hash_map_clone_func, allocator, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 5); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 1); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 13); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 4); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 11); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k5")) == 19); CX_TEST_ASSERT(cxMapSize(src) == 3); CX_TEST_ASSERT(*((int*)cxMapGet(src, "k4")) == 7); CX_TEST_ASSERT(*((int*)cxMapGet(src, "k2")) == 9); CX_TEST_ASSERT(*((int*)cxMapGet(src, "k5")) == 15); cxMapClear(dst); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cxMapFree(dst); cxMapFree(src); cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_difference) { CxMap *dst = cxHashMapCreateSimple(sizeof(int)); CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); const char *s1_keys[] = {"k1", "k2", "k3"}; int s1_values[] = {1, 3, 4}; const char *s2_keys[] = {"k4", "k2", "k5"}; int s2_values[] = {7, 9, 15}; for (unsigned int i = 0 ; i < 3 ; i++) { cxMapPut(s1, s1_keys[i], &s1_values[i]); cxMapPut(s2, s2_keys[i], &s2_values[i]); } CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, NULL, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 2); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5); CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); } cxMapFree(dst); cxMapFree(s1); cxMapFree(s2); } CX_TEST(test_hash_map_difference_alloc_fail) { CxMap *dst = cxHashMapCreateSimple(sizeof(int)); CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); const char *s1_keys[] = {"k1", "k2", "k3"}; int s1_values[] = {1, 3, 4}; const char *s2_keys[] = {"k4", "k2", "k5"}; int s2_values[] = {7, 9, 15}; for (unsigned int i = 0 ; i < 3 ; i++) { cxMapPut(s1, s1_keys[i], &s1_values[i]); cxMapPut(s2, s2_keys[i], &s2_values[i]); } CX_TEST_DO { int c = 4; test_hash_map_clone_func_max_enabled = true; test_hash_map_clone_func_max_clones = 1; CX_TEST_ASSERT(1 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, NULL, &c)); test_hash_map_clone_func_max_enabled = false; CX_TEST_ASSERT(cxMapSize(dst) == 1); // the concrete element which is affected might change when the hash function changes CX_TEST_ASSERT(cxMapGet(dst, "k1") == NULL); CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); } cxMapFree(dst); cxMapFree(s1); cxMapFree(s2); } CX_TEST(test_hash_map_list_difference) { CxMap *dst = cxHashMapCreateSimple(sizeof(int)); CxMap *src = cxHashMapCreateSimple(sizeof(int)); CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); const char *src_keys[] = {"k1", "k2", "k3"}; int src_values[] = {1, 3, 4}; for (unsigned int i = 0 ; i < 3 ; i++) { cxMapPut(src, src_keys[i], &src_values[i]); } const char *k[] = {"k4", "k2", "k5"}; for (unsigned int i = 0 ; i < 3 ; i++) { CxHashKey key = CX_HASH_KEY(k[i]); cxListAdd(keys, &key); } CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 2); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5); CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); } cxMapFree(dst); cxMapFree(src); cxListFree(keys); } CX_TEST(test_hash_map_list_difference_alloc_fail) { CxMap *dst = cxHashMapCreateSimple(sizeof(int)); CxMap *src = cxHashMapCreateSimple(sizeof(int)); CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); const char *src_keys[] = {"k1", "k2", "k3"}; int src_values[] = {1, 3, 4}; for (unsigned int i = 0 ; i < 3 ; i++) { cxMapPut(src, src_keys[i], &src_values[i]); } const char *k[] = {"k4", "k2", "k5"}; for (unsigned int i = 0 ; i < 3 ; i++) { CxHashKey key = CX_HASH_KEY(k[i]); cxListAdd(keys, &key); } CX_TEST_DO { int c = 4; test_hash_map_clone_func_max_enabled = true; test_hash_map_clone_func_max_clones = 1; CX_TEST_ASSERT(1 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c)); test_hash_map_clone_func_max_enabled = false; CX_TEST_ASSERT(cxMapSize(dst) == 1); // the concrete element which is affected might change when the hash function changes CX_TEST_ASSERT(cxMapGet(dst, "k1") == NULL); CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); } cxMapFree(dst); cxMapFree(src); cxListFree(keys); } CX_TEST(test_hash_map_difference_non_empty_target) { CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); cxDefineAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator); CxMap *s1 = cxHashMapCreateSimple(sizeof(int)); CxMap *s2 = cxHashMapCreateSimple(sizeof(int)); const char *s1_keys[] = {"k1", "k2", "k3"}; int s1_values[] = {1, 3, 4}; const char *s2_keys[] = {"k4", "k2", "k5"}; int s2_values[] = {7, 9, 15}; for (unsigned int i = 0 ; i < 3 ; i++) { cxMapPut(s1, s1_keys[i], &s1_values[i]); cxMapPut(s2, s2_keys[i], &s2_values[i]); } // add k5 to dst which is not in src, and also not in the difference int *k5 = cxMallocDefault(sizeof(int)); *k5 = 1337; cxMapPut(dst, "k5",k5); CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, NULL, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 3); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5); CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k5") == 1337); } cxMapFree(dst); cxMapFree(s1); cxMapFree(s2); } CX_TEST(test_hash_map_list_difference_non_empty_target) { CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); cxDefineAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator); CxMap *src = cxHashMapCreateSimple(sizeof(int)); CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); const char *src_keys[] = {"k1", "k2", "k3"}; int src_values[] = {1, 3, 4}; for (unsigned int i = 0 ; i < 3 ; i++) { cxMapPut(src, src_keys[i], &src_values[i]); } const char *k[] = {"k4", "k2", "k5"}; for (unsigned int i = 0 ; i < 3 ; i++) { CxHashKey key = CX_HASH_KEY(k[i]); cxListAdd(keys, &key); } // add k5 to dst which is not in src, and also not in the difference int *k5 = cxMallocDefault(sizeof(int)); *k5 = 1337; cxMapPut(dst, "k5",k5); CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 3); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5); CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k5") == 1337); } cxMapFree(dst); cxMapFree(src); cxListFree(keys); } CX_TEST(test_hash_map_difference_ptr) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); cxDefineAdvancedDestructor(dst, cxFree, allocator); CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); const char *s1_keys[] = {"k1", "k2", "k3"}; int s1_values[] = {1, 3, 4}; const char *s2_keys[] = {"k4", "k2", "k5"}; int s2_values[] = {7, 9, 15}; for (unsigned int i = 0 ; i < 3 ; i++) { cxMapPut(s1, s1_keys[i], &s1_values[i]); cxMapPut(s2, s2_keys[i], &s2_values[i]); } CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, allocator, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 2); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5); CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); cxMapClear(dst); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cxMapFree(dst); cxMapFree(s1); cxMapFree(s2); cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_intersection) { CxMap *dst = cxHashMapCreateSimple(sizeof(int)); CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; int s1_values[] = {1, 3, 4, 6}; const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; int s2_values[] = {5, 9, 15, 23}; for (unsigned int i = 0 ; i < 4 ; i++) { cxMapPut(s1, s1_keys[i], &s1_values[i]); cxMapPut(s2, s2_keys[i], &s2_values[i]); } CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, NULL, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 2); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); } cxMapFree(dst); cxMapFree(s1); cxMapFree(s2); } CX_TEST(test_hash_map_intersection_alloc_fail) { CxMap *dst = cxHashMapCreateSimple(sizeof(int)); CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; int s1_values[] = {1, 3, 4, 6}; const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; int s2_values[] = {5, 9, 15, 23}; for (unsigned int i = 0 ; i < 4 ; i++) { cxMapPut(s1, s1_keys[i], &s1_values[i]); cxMapPut(s2, s2_keys[i], &s2_values[i]); } CX_TEST_DO { int c = 4; test_hash_map_clone_func_max_enabled = true; test_hash_map_clone_func_max_clones = 1; CX_TEST_ASSERT(0 != cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, NULL, &c)); test_hash_map_clone_func_max_enabled = false; CX_TEST_ASSERT(cxMapSize(dst) == 1); // the concrete element which is affected might change when the hash function changes CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); CX_TEST_ASSERT(cxMapGet(dst, "k4") == NULL); } cxMapFree(dst); cxMapFree(s1); cxMapFree(s2); } CX_TEST(test_hash_map_list_intersection) { CxMap *dst = cxHashMapCreateSimple(sizeof(int)); CxMap *src = cxHashMapCreateSimple(sizeof(int)); CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); const char *src_keys[] = {"k1", "k2", "k3", "k4"}; int src_values[] = {1, 3, 4, 6}; for (unsigned int i = 0 ; i < 4 ; i++) { cxMapPut(src, src_keys[i], &src_values[i]); } const char *k[] = {"k4", "k5", "k2", "k6"}; for (unsigned int i = 0 ; i < 4 ; i++) { CxHashKey key = CX_HASH_KEY(k[i]); cxListAdd(keys, &key); } CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapListIntersection(dst, src, keys, test_hash_map_clone_func, NULL, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 2); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); } cxMapFree(dst); cxMapFree(src); cxListFree(keys); } CX_TEST(test_hash_map_list_intersection_alloc_fail) { CxMap *dst = cxHashMapCreateSimple(sizeof(int)); CxMap *src = cxHashMapCreateSimple(sizeof(int)); CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); const char *src_keys[] = {"k1", "k2", "k3", "k4"}; int src_values[] = {1, 3, 4, 6}; for (unsigned int i = 0 ; i < 4 ; i++) { cxMapPut(src, src_keys[i], &src_values[i]); } const char *k[] = {"k4", "k5", "k2", "k6"}; for (unsigned int i = 0 ; i < 4 ; i++) { CxHashKey key = CX_HASH_KEY(k[i]); cxListAdd(keys, &key); } CX_TEST_DO { int c = 4; test_hash_map_clone_func_max_enabled = true; test_hash_map_clone_func_max_clones = 1; CX_TEST_ASSERT(0 != cxMapListIntersection(dst, src, keys, test_hash_map_clone_func, NULL, &c)); test_hash_map_clone_func_max_enabled = false; CX_TEST_ASSERT(cxMapSize(dst) == 1); // the concrete element which is affected might change when the hash function changes CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); CX_TEST_ASSERT(cxMapGet(dst, "k4") == NULL); } cxMapFree(dst); cxMapFree(src); cxListFree(keys); } CX_TEST(test_hash_map_intersection_non_empty_target) { CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); cxDefineAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator); CxMap *s1 = cxHashMapCreateSimple(sizeof(int)); CxMap *s2 = cxHashMapCreateSimple(sizeof(int)); const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; int s1_values[] = {1, 3, 4, 6}; const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; int s2_values[] = {5, 9, 15, 23}; for (unsigned int i = 0 ; i < 4 ; i++) { cxMapPut(s1, s1_keys[i], &s1_values[i]); cxMapPut(s2, s2_keys[i], &s2_values[i]); } // add k7 to dst which is not in src, and also not in the difference int *k7 = cxMallocDefault(sizeof(int)); *k7 = 1337; cxMapPut(dst, "k7", k7); CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, NULL, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 3); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k7") == 1337); } cxMapFree(dst); cxMapFree(s1); cxMapFree(s2); } CX_TEST(test_hash_map_list_intersection_non_empty_target) { CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); cxDefineAdvancedDestructor(dst, cxFree, (void*) cxDefaultAllocator); CxMap *src = cxHashMapCreateSimple(sizeof(int)); CxList *keys = cxArrayListCreate(NULL, cx_hash_key_cmp, sizeof(CxHashKey), 4); const char *src_keys[] = {"k1", "k2", "k3", "k4"}; int src_values[] = {1, 3, 4, 6}; for (unsigned int i = 0 ; i < 4 ; i++) { cxMapPut(src, src_keys[i], &src_values[i]); } const char *k[] = {"k4", "k5", "k2", "k6"}; for (unsigned int i = 0 ; i < 4 ; i++) { CxHashKey key = CX_HASH_KEY(k[i]); cxListAdd(keys, &key); } // add k7 to dst which is not in src, and also not in the difference int *k7 = cxMallocDefault(sizeof(int)); *k7 = 1337; cxMapPut(dst, "k7", k7); CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapListIntersection(dst, src, keys, test_hash_map_clone_func, NULL, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 3); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k7") == 1337); } cxMapFree(dst); cxMapFree(src); cxListFree(keys); } CX_TEST(test_hash_map_intersection_ptr) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); cxDefineAdvancedDestructor(dst, cxFree, allocator); CxMap *s1 = cxHashMapCreateSimple(CX_STORE_POINTERS); CxMap *s2 = cxHashMapCreateSimple(CX_STORE_POINTERS); const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; int s1_values[] = {1, 3, 4, 6}; const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; int s2_values[] = {5, 9, 15, 23}; for (unsigned int i = 0 ; i < 4 ; i++) { cxMapPut(s1, s1_keys[i], &s1_values[i]); cxMapPut(s2, s2_keys[i], &s2_values[i]); } CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapIntersection(dst, s1, s2, test_hash_map_clone_func, allocator, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 2); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); CX_TEST_ASSERT(cx_testing_allocator_used(&talloc)); } cxMapFree(dst); cxMapFree(s1); cxMapFree(s2); cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_union) { CxMap *s1 = cxHashMapCreateSimple(sizeof(int)); CxMap *s2 = cxHashMapCreateSimple(sizeof(int)); const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; int s1_values[] = {1, 3, 4, 6}; const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; int s2_values[] = {5, 9, 15, 23}; for (unsigned int i = 0 ; i < 4 ; i++) { cxMapPut(s1, s1_keys[i], &s1_values[i]); cxMapPut(s2, s2_keys[i], &s2_values[i]); } CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapUnion(s1, s2, test_hash_map_clone_func, NULL, &c)); CX_TEST_ASSERT(cxMapSize(s1) == 6); CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k1")) == 1); CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k2")) == 3); CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k3")) == 4); CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k4")) == 6); CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k5")) == 13); CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k6")) == 27); } cxMapFree(s1); cxMapFree(s2); } CX_TEST(test_hash_map_union_ptr) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CxMap *dst = cxHashMapCreateSimple(CX_STORE_POINTERS); cxDefineAdvancedDestructor(dst, cxFree, allocator); CxMap *s1 = cxHashMapCreateSimple(sizeof(int)); CxMap *s2 = cxHashMapCreateSimple(sizeof(int)); const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; int s1_values[] = {1, 3, 4, 6}; const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; int s2_values[] = {5, 9, 15, 23}; for (unsigned int i = 0 ; i < 4 ; i++) { cxMapPut(s1, s1_keys[i], &s1_values[i]); cxMapPut(s2, s2_keys[i], &s2_values[i]); } CX_TEST_DO { int c = 4; CX_TEST_ASSERT(0 == cxMapClone(dst, s1, test_hash_map_clone_func, allocator, &c)); CX_TEST_ASSERT(0 == cxMapUnion(dst, s2, test_hash_map_clone_func, allocator, &c)); CX_TEST_ASSERT(cxMapSize(dst) == 6); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 7); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k4")) == 10); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k5")) == 13); CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k6")) == 27); CX_TEST_ASSERT(cx_testing_allocator_used(&talloc)); } cxMapFree(dst); cxMapFree(s1); cxMapFree(s2); cx_testing_allocator_destroy(&talloc); } CX_TEST(test_hash_map_union_alloc_fail) { CxMap *s1 = cxHashMapCreateSimple(sizeof(int)); CxMap *s2 = cxHashMapCreateSimple(sizeof(int)); const char *s1_keys[] = {"k1", "k2", "k3", "k4"}; int s1_values[] = {1, 3, 4, 6}; const char *s2_keys[] = {"k4", "k5", "k2", "k6"}; int s2_values[] = {5, 9, 15, 23}; for (unsigned int i = 0 ; i < 4 ; i++) { cxMapPut(s1, s1_keys[i], &s1_values[i]); cxMapPut(s2, s2_keys[i], &s2_values[i]); } CX_TEST_DO { int c = 4; test_hash_map_clone_func_max_enabled = true; test_hash_map_clone_func_max_clones = 1; CX_TEST_ASSERT(0 != cxMapUnion(s1, s2, test_hash_map_clone_func, NULL, &c)); test_hash_map_clone_func_max_enabled = false; CX_TEST_ASSERT(cxMapSize(s1) == 5); CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k1")) == 1); CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k2")) == 3); CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k3")) == 4); CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k4")) == 6); // the concrete element which is affected might change when the hash function changes CX_TEST_ASSERT(cxMapGet(s1, "k5") == NULL); CX_TEST_ASSERT(*((int*)cxMapGet(s1, "k6")) == 27); } cxMapFree(s1); cxMapFree(s2); } CX_TEST(test_hash_map_simple_clones) { int v = 47; // the value does not matter in this test CxMap *a = cxHashMapCreateSimple(sizeof(int)); cxMapPut(a, "k1", &v); cxMapPut(a, "k2", &v); cxMapPut(a, "k3", &v); cxMapPut(a, "k4", &v); CxMap *b = cxHashMapCreateSimple(sizeof(int)); cxMapPut(b, "k0", &v); cxMapPut(b, "k2", &v); cxMapPut(b, "k5", &v); CxMap *c = cxHashMapCreateSimple(sizeof(int)); cxMapPut(c, "k3", &v); cxMapPut(c, "k4", &v); cxMapPut(c, "k5", &v); CxHashKey k; CxList *kl1 = cxArrayListCreateSimple(sizeof(CxHashKey), 4); cxCollectionCompareFunc(kl1, cx_hash_key_cmp); k = CX_HASH_KEY("k0"); cxListAdd(kl1, &k); k = CX_HASH_KEY("k2"); cxListAdd(kl1, &k); k = CX_HASH_KEY("k5"); cxListAdd(kl1, &k); CxList *kl2 = cxArrayListCreateSimple(sizeof(CxHashKey), 4); cxCollectionCompareFunc(kl2, cx_hash_key_cmp); k = CX_HASH_KEY("k3"); cxListAdd(kl2, &k); k = CX_HASH_KEY("k4"); cxListAdd(kl2, &k); k = CX_HASH_KEY("k5"); cxListAdd(kl2, &k); CxMap *d1 = cxHashMapCreateSimple(sizeof(int)); CxMap *d2 = cxHashMapCreateSimple(sizeof(int)); CX_TEST_DO { CX_TEST_ASSERT(0 == cxMapCloneSimple(d1, a)); CX_TEST_ASSERT(!cxMapContains(d1, "k0")); CX_TEST_ASSERT(cxMapContains(d1, "k1")); CX_TEST_ASSERT(cxMapContains(d1, "k2")); CX_TEST_ASSERT(cxMapContains(d1, "k3")); CX_TEST_ASSERT(cxMapContains(d1, "k4")); CX_TEST_ASSERT(!cxMapContains(d1, "k5")); CX_TEST_ASSERT(0 == cxMapListDifferenceSimple(d2, d1, kl1)); CX_TEST_ASSERT(!cxMapContains(d2, "k0")); CX_TEST_ASSERT(cxMapContains(d2, "k1")); CX_TEST_ASSERT(!cxMapContains(d2, "k2")); CX_TEST_ASSERT(cxMapContains(d2, "k3")); CX_TEST_ASSERT(cxMapContains(d2, "k4")); CX_TEST_ASSERT(!cxMapContains(d2, "k5")); cxMapClear(d1); CX_TEST_ASSERT(0 == cxMapListIntersectionSimple(d1, d2, kl2)); CX_TEST_ASSERT(!cxMapContains(d1, "k0")); CX_TEST_ASSERT(!cxMapContains(d1, "k1")); CX_TEST_ASSERT(!cxMapContains(d1, "k2")); CX_TEST_ASSERT(cxMapContains(d1, "k3")); CX_TEST_ASSERT(cxMapContains(d1, "k4")); CX_TEST_ASSERT(0 == cxMapUnionSimple(d1, b)); CX_TEST_ASSERT(cxMapContains(d1, "k0")); CX_TEST_ASSERT(!cxMapContains(d1, "k1")); CX_TEST_ASSERT(cxMapContains(d1, "k2")); CX_TEST_ASSERT(cxMapContains(d1, "k3")); CX_TEST_ASSERT(cxMapContains(d1, "k4")); CX_TEST_ASSERT(cxMapContains(d1, "k5")); cxMapClear(d2); CX_TEST_ASSERT(0 == cxMapDifferenceSimple(d2, d1, a)); CX_TEST_ASSERT(cxMapContains(d2, "k0")); CX_TEST_ASSERT(!cxMapContains(d2, "k1")); CX_TEST_ASSERT(!cxMapContains(d2, "k2")); CX_TEST_ASSERT(!cxMapContains(d2, "k3")); CX_TEST_ASSERT(!cxMapContains(d2, "k4")); CX_TEST_ASSERT(cxMapContains(d2, "k5")); cxMapClear(d1); CX_TEST_ASSERT(0 == cxMapIntersectionSimple(d1, d2, c)); CX_TEST_ASSERT(!cxMapContains(d1, "k0")); CX_TEST_ASSERT(!cxMapContains(d1, "k1")); CX_TEST_ASSERT(!cxMapContains(d1, "k2")); CX_TEST_ASSERT(!cxMapContains(d1, "k3")); CX_TEST_ASSERT(!cxMapContains(d1, "k4")); CX_TEST_ASSERT(cxMapContains(d1, "k5")); } cxMapFree(a); cxMapFree(b); cxMapFree(c); cxListFree(kl1); cxListFree(kl2); cxMapFree(d1); cxMapFree(d2); } CX_TEST(test_empty_map_size) { CX_TEST_DO { CX_TEST_ASSERT(cxEmptyMap->collection.size == 0); CX_TEST_ASSERT(cxMapSize(cxEmptyMap) == 0); } } CX_TEST(test_empty_map_iterator) { CxMap *map = cxEmptyMap; CxMapIterator it1 = cxMapIterator(map); CxMapIterator it2 = cxMapIteratorValues(map); CxMapIterator it3 = cxMapIteratorKeys(map); CxMapIterator it4 = cxMapIterator(map); CxMapIterator it5 = cxMapIteratorValues(map); CxMapIterator it6 = cxMapIteratorKeys(map); CX_TEST_DO { CX_TEST_ASSERT(!cxIteratorValid(it1)); CX_TEST_ASSERT(!cxIteratorValid(it2)); CX_TEST_ASSERT(!cxIteratorValid(it3)); CX_TEST_ASSERT(!cxIteratorValid(it4)); CX_TEST_ASSERT(!cxIteratorValid(it5)); CX_TEST_ASSERT(!cxIteratorValid(it6)); int c = 0; cx_foreach(void*, data, it1) c++; cx_foreach(void*, data, it2) c++; cx_foreach(void*, data, it3) c++; cx_foreach(void*, data, it4) c++; cx_foreach(void*, data, it5) c++; cx_foreach(void*, data, it6) c++; CX_TEST_ASSERT(c == 0); } } CX_TEST(test_null_map_iterator) { CxMap *map = NULL; CxMapIterator it1 = cxMapIterator(map); CxMapIterator it2 = cxMapIteratorValues(map); CxMapIterator it3 = cxMapIteratorKeys(map); CxMapIterator it4 = cxMapIterator(map); CxMapIterator it5 = cxMapIteratorValues(map); CxMapIterator it6 = cxMapIteratorKeys(map); CX_TEST_DO { CX_TEST_ASSERT(!cxIteratorValid(it1)); CX_TEST_ASSERT(!cxIteratorValid(it2)); CX_TEST_ASSERT(!cxIteratorValid(it3)); CX_TEST_ASSERT(!cxIteratorValid(it4)); CX_TEST_ASSERT(!cxIteratorValid(it5)); CX_TEST_ASSERT(!cxIteratorValid(it6)); int c = 0; cx_foreach(void*, data, it1) c++; cx_foreach(void*, data, it2) c++; cx_foreach(void*, data, it3) c++; cx_foreach(void*, data, it4) c++; cx_foreach(void*, data, it5) c++; cx_foreach(void*, data, it6) c++; CX_TEST_ASSERT(c == 0); } } CX_TEST(test_empty_map_no_ops) { CX_TEST_DO { // assertion not possible // test that no segfault happens and valgrind is happy cxMapClear(cxEmptyMap); cxMapFree(cxEmptyMap); CX_TEST_ASSERT(true); } } CX_TEST(test_empty_map_get) { CX_TEST_DO { CxHashKey key = cx_hash_key_str("test"); CX_TEST_ASSERT(cxMapGet(cxEmptyMap, key) == NULL); } } CX_TEST(test_hash_map_generics) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); cxMapPut(map, "test", "test"); cxMapPut(map, cx_mutstr("foo"), "bar"); cxMapPut(map, cx_str("hallo"), "welt"); CX_TEST_ASSERT(map->collection.size == 3); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "test"), "test")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "hallo"), "welt")); CX_TEST_ASSERT(0 == cxMapRemove(map, cx_str("test"))); const char *hallo = "hallo"; CX_TEST_ASSERT(0 == cxMapRemove(map, hallo)); cxMapPut(map, cx_hash_key_str("key"), "value"); CX_TEST_ASSERT(map->collection.size == 2); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key"), "value")); CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar")); const char *r1, *r2; CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, "key", &r1)); CX_TEST_ASSERT(0 == strcmp(r1, "value")); CX_TEST_ASSERT(0 == cxMapRemoveAndGet(map, cx_str("foo"), &r2)); CX_TEST_ASSERT(0 == strcmp(r2, "bar")); r2 = "nope"; CX_TEST_ASSERT(0 != cxMapRemoveAndGet(map, cx_hash_key("notfound",9), &r2)); CX_TEST_ASSERT(0 == strcmp(r2, "nope")); CX_TEST_ASSERT(map->collection.size == 0); cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } struct test_map_kv { const char *key; const char *value; }; static struct test_map_kv const test_map_operations[] = { {"key 1", "test"}, {"key 2", "blub"}, {"key 3", "hallo"}, {"key 2", "foobar"}, {"key 4", "value 4"}, {"key 5", "value 5"}, {"key 6", "value 6"}, {"key 4", NULL}, {"key 7", "value 7"}, {"key 8", "value 8"}, {"does not exist", NULL}, {"key 9", "value 9"}, {"key 6", "other value"}, {"key 7", "something else"}, {"key 8", NULL}, {"key 2", NULL}, {"key 8", "new value"}, }; static const size_t test_map_operations_len = sizeof(test_map_operations) / sizeof(struct test_map_kv); static struct test_map_kv test_map_reference[] = { {"key 1", NULL}, {"key 2", NULL}, {"key 3", NULL}, {"key 4", NULL}, {"key 5", NULL}, {"key 6", NULL}, {"key 7", NULL}, {"key 8", NULL}, {"key 9", NULL}, }; static const size_t test_map_reference_len = sizeof(test_map_reference) / sizeof(struct test_map_kv); static void test_map_reference_put(const char *key, const char *value) { for (size_t i = 0 ; i < test_map_reference_len ; i++) { if (0 == strcmp(key, test_map_reference[i].key)) { test_map_reference[i].value = value; return; } } } static const char *test_map_reference_get(const char *key) { for (size_t i = 0 ; i < test_map_reference_len ; i++) { if (0 == strcmp(key, test_map_reference[i].key)) { return test_map_reference[i].value; } } return NULL; } static const char *test_map_reference_remove(const char *key) { for (size_t i = 0 ; i < test_map_reference_len ; i++) { if (0 == strcmp(key, test_map_reference[i].key)) { const char *ret = test_map_reference[i].value; test_map_reference[i].value = NULL; return ret; } } return NULL; } static size_t test_map_reference_size(void) { size_t size = 0; for (size_t i = 0; i < test_map_reference_len; i++) { if (test_map_reference[i].value != NULL) { size++; } } return size; } static CX_TEST_SUBROUTINE(verify_map_contents, CxMap *map) { // verify that the reference map has same size (i.e. no other keys are mapped) CX_TEST_ASSERT(map->collection.size == test_map_reference_size()); // verify key iterator { // collect the keys from the map iterator CxMapIterator keyiter = cxMapIteratorKeys(map); CX_TEST_ASSERT(keyiter.elem_size == sizeof(CxHashKey)); CX_TEST_ASSERT(keyiter.elem_count == map->collection.size); CxHashKey *keys = calloc(map->collection.size, sizeof(CxHashKey)); cx_foreach(CxHashKey*, elem, keyiter) { keys[keyiter.index] = *elem; } CX_TEST_ASSERT(keyiter.index == map->collection.size); // verify that all keys are mapped to values in reference map for (size_t i = 0 ; i < map->collection.size ; i++) { cxmutstr ksz = cx_strdup(cx_strn(keys[i].data, keys[i].len)); CX_TEST_ASSERT(test_map_reference_get(ksz.ptr) != NULL); cx_strfree(&ksz); } free(keys); } // verify value iterator { // by using that the values in our test data are unique strings // we can re-use a similar approach as above CxMapIterator valiter = cxMapIteratorValues(map); CX_TEST_ASSERT(valiter.elem_size == map->collection.elem_size); CX_TEST_ASSERT(valiter.elem_count == map->collection.size); const char ** values = calloc(map->collection.size, sizeof(const char *)); cx_foreach(const char *, elem, valiter) { values[valiter.index] = elem; } CX_TEST_ASSERT(valiter.index == map->collection.size); // verify that all values are present in the reference map for (size_t i = 0 ; i < map->collection.size ; i++) { bool found = false; for (size_t j = 0; j < test_map_reference_len ; j++) { if (test_map_reference[j].value == values[i]) { found = true; break; } } CX_TEST_ASSERTM(found, "A value was not found in the reference map"); } free(values); } // verify pair iterator { CxMapIterator pairiter = cxMapIterator(map); CX_TEST_ASSERT(pairiter.elem_size == sizeof(CxMapEntry)); CX_TEST_ASSERT(pairiter.elem_count == map->collection.size); struct test_map_kv *pairs = calloc(map->collection.size, sizeof(struct test_map_kv)); cx_foreach(CxMapEntry*, entry, pairiter) { const CxHashKey *key = entry->key; pairs[pairiter.index].key = cx_strdup(cx_strn(key->data, key->len)).ptr; pairs[pairiter.index].value = entry->value; } CX_TEST_ASSERT(pairiter.index == map->collection.size); // verify that all pairs are present in the reference map for (size_t i = 0 ; i < map->collection.size ; i++) { CX_TEST_ASSERT(test_map_reference_get(pairs[i].key) == pairs[i].value); // this was cx_strdup'ed cxFreeDefault((void*)pairs[i].key); } free(pairs); } } CX_TEST(test_hash_map_basic_operations) { CxTestingAllocator talloc; cx_testing_allocator_init(&talloc); CxAllocator *allocator = &talloc.base; CX_TEST_DO { // create the map CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 8); // clear the reference map for (size_t i = 0 ; i < test_map_reference_len ; i++) { test_map_reference[i].value = NULL; } // verify iterators for empty map CX_TEST_CALL_SUBROUTINE(verify_map_contents, map); // execute operations and verify results for (size_t i = 0 ; i < test_map_operations_len ; i++) { struct test_map_kv kv = test_map_operations[i]; CxHashKey key = cx_hash_key_str(kv.key); key.hash = 0; // force the hash map to compute the hash if (kv.value != NULL) { // execute a put operation and verify that the exact value can be read back test_map_reference_put(kv.key, kv.value); int result = cxMapPut(map, key, (void *) kv.value); CX_TEST_ASSERT(result == 0); void *added = cxMapGet(map, key); CX_TEST_ASSERT(0 == memcmp(kv.value, added, strlen(kv.value))); } else { // execute a remove and verify that the removed element was returned (or NULL) const char *found = test_map_reference_remove(kv.key); void *removed = (void*) 0x1337; int result = cxMapRemoveAndGet(map, key, &removed); if (found == NULL) { CX_TEST_ASSERT(0 != result); CX_TEST_ASSERT(removed == (void*) 0x1337); } else { CX_TEST_ASSERT(0 == result); CX_TEST_ASSERT(removed == found); } } // compare the current map state with the reference map CX_TEST_CALL_SUBROUTINE(verify_map_contents, map); } // destroy the map and verify the memory (de)allocations cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); } cx_testing_allocator_destroy(&talloc); } CxTestSuite *cx_test_suite_hash_map(void) { CxTestSuite *suite = cx_test_suite_new("map"); cx_test_register(suite, test_hash_map_create); cx_test_register(suite, test_hash_map_create_store_pointers); cx_test_register(suite, test_hash_map_basic_operations); cx_test_register(suite, test_hash_map_emplace); cx_test_register(suite, test_hash_map_emplace_pointers); cx_test_register(suite, test_hash_map_rehash); cx_test_register(suite, test_hash_map_rehash_not_required); cx_test_register(suite, test_hash_map_clear); cx_test_register(suite, test_hash_map_store_ucx_strings); cx_test_register(suite, test_hash_map_integer_keys); cx_test_register(suite, test_hash_map_remove_via_iterator); cx_test_register(suite, test_hash_map_simple_destructor_objects); cx_test_register(suite, test_hash_map_advanced_destructor_objects); cx_test_register(suite, test_hash_map_simple_destructor_pointers); cx_test_register(suite, test_hash_map_advanced_destructor_pointers); cx_test_register(suite, test_hash_map_clone); cx_test_register(suite, test_hash_map_clone_alloc_fail); cx_test_register(suite, test_hash_map_clone_ptr); cx_test_register(suite, test_hash_map_difference); cx_test_register(suite, test_hash_map_difference_ptr); cx_test_register(suite, test_hash_map_list_difference); cx_test_register(suite, test_hash_map_difference_alloc_fail); cx_test_register(suite, test_hash_map_list_difference_alloc_fail); cx_test_register(suite, test_hash_map_difference_non_empty_target); cx_test_register(suite, test_hash_map_list_difference_non_empty_target); cx_test_register(suite, test_hash_map_intersection); cx_test_register(suite, test_hash_map_intersection_ptr); cx_test_register(suite, test_hash_map_list_intersection); cx_test_register(suite, test_hash_map_intersection_alloc_fail); cx_test_register(suite, test_hash_map_list_intersection_alloc_fail); cx_test_register(suite, test_hash_map_intersection_non_empty_target); cx_test_register(suite, test_hash_map_list_intersection_non_empty_target); cx_test_register(suite, test_hash_map_union); cx_test_register(suite, test_hash_map_union_ptr); cx_test_register(suite, test_hash_map_union_alloc_fail); cx_test_register(suite, test_hash_map_simple_clones); cx_test_register(suite, test_empty_map_no_ops); cx_test_register(suite, test_empty_map_size); cx_test_register(suite, test_empty_map_get); cx_test_register(suite, test_empty_map_iterator); cx_test_register(suite, test_null_map_iterator); cx_test_register(suite, test_hash_map_generics); return suite; }
