universe@785: /* universe@785: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. universe@785: * universe@785: * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved. universe@785: * universe@785: * Redistribution and use in source and binary forms, with or without universe@785: * modification, are permitted provided that the following conditions are met: universe@785: * universe@785: * 1. Redistributions of source code must retain the above copyright universe@785: * notice, this list of conditions and the following disclaimer. universe@785: * universe@785: * 2. Redistributions in binary form must reproduce the above copyright universe@785: * notice, this list of conditions and the following disclaimer in the universe@785: * documentation and/or other materials provided with the distribution. universe@785: * universe@785: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" universe@785: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE universe@785: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE universe@785: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE universe@785: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR universe@785: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF universe@785: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS universe@785: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN universe@785: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) universe@785: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE universe@785: * POSSIBILITY OF SUCH DAMAGE. universe@785: */ universe@785: universe@785: #include "cx/test.h" universe@785: #include "util_allocator.h" universe@785: universe@785: #include "cx/hash_map.h" universe@785: universe@785: CX_TEST(test_hash_map_create) { universe@785: CxTestingAllocator talloc; universe@785: cx_testing_allocator_init(&talloc); universe@785: CxAllocator *allocator = &talloc.base; universe@785: CX_TEST_DO { universe@785: CxMap *map = cxHashMapCreate(allocator, 1, 0); universe@785: struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map; universe@785: CX_TEST_ASSERT(hmap->bucket_count > 0); universe@785: for(size_t i = 0 ; i < hmap->bucket_count ; i++) { universe@785: CX_TEST_ASSERT(hmap->buckets[i] == NULL); universe@785: } universe@785: CX_TEST_ASSERT(map->item_size == 1); universe@785: CX_TEST_ASSERT(map->size == 0); universe@785: CX_TEST_ASSERT(map->allocator == allocator); universe@785: CX_TEST_ASSERT(!map->store_pointer); universe@785: CX_TEST_ASSERT(map->cmpfunc == NULL); universe@785: CX_TEST_ASSERT(map->simple_destructor == NULL); universe@785: CX_TEST_ASSERT(map->advanced_destructor == NULL); universe@785: CX_TEST_ASSERT(map->destructor_data == NULL); universe@785: cxMapStorePointers(map); universe@785: CX_TEST_ASSERT(map->store_pointer); universe@785: CX_TEST_ASSERT(map->item_size == sizeof(void *)); universe@785: cxMapStoreObjects(map); universe@785: CX_TEST_ASSERT(!map->store_pointer); universe@785: universe@785: cxMapDestroy(map); universe@785: CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); universe@785: } universe@785: cx_testing_allocator_destroy(&talloc); universe@785: } universe@785: universe@785: CX_TEST(test_hash_map_create_store_pointers) { universe@785: CxTestingAllocator talloc; universe@785: cx_testing_allocator_init(&talloc); universe@785: CxAllocator *allocator = &talloc.base; universe@785: CX_TEST_DO { universe@785: CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); universe@785: struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map; universe@785: CX_TEST_ASSERT(hmap->bucket_count > 0); universe@785: for (size_t i = 0; i < hmap->bucket_count; i++) { universe@785: CX_TEST_ASSERT(hmap->buckets[i] == NULL); universe@785: } universe@785: CX_TEST_ASSERT(map->size == 0); universe@785: CX_TEST_ASSERT(map->allocator == allocator); universe@785: CX_TEST_ASSERT(map->store_pointer); universe@785: CX_TEST_ASSERT(map->item_size == sizeof(void *)); universe@785: universe@785: cxMapDestroy(map); universe@785: CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); universe@785: } universe@785: cx_testing_allocator_destroy(&talloc); universe@785: } universe@785: universe@785: CX_TEST(test_hash_map_rehash) { universe@785: CxTestingAllocator talloc; universe@785: cx_testing_allocator_init(&talloc); universe@785: CxAllocator *allocator = &talloc.base; universe@785: CX_TEST_DO { universe@785: CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 7); universe@785: universe@785: cxMapPut(map, "key 1", (void *) "val 1"); universe@785: cxMapPut(map, "key 2", (void *) "val 2"); universe@785: cxMapPut(map, "key 3", (void *) "val 3"); universe@785: cxMapPut(map, "foo 4", (void *) "val 4"); universe@785: cxMapPut(map, "key 5", (void *) "val 5"); universe@785: cxMapPut(map, "key 6", (void *) "val 6"); universe@785: cxMapPut(map, "bar 7", (void *) "val 7"); universe@785: cxMapPut(map, "key 8", (void *) "val 8"); universe@785: cxMapPut(map, "key 9", (void *) "val 9"); universe@785: cxMapPut(map, "key 10", (void *) "val 10"); universe@785: universe@785: CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 7); universe@785: int result = cxMapRehash(map); universe@785: CX_TEST_ASSERT(result == 0); universe@785: CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 25); universe@785: CX_TEST_ASSERT(map->size == 10); universe@785: universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 1"), "val 1")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 2"), "val 2")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 3"), "val 3")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo 4"), "val 4")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 5"), "val 5")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 6"), "val 6")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "bar 7"), "val 7")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 8"), "val 8")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 9"), "val 9")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 10"), "val 10")); universe@785: universe@785: cxMapDestroy(map); universe@785: CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); universe@785: } universe@785: cx_testing_allocator_destroy(&talloc); universe@785: } universe@785: universe@785: CX_TEST(test_hash_map_rehash_not_required) { universe@785: CxTestingAllocator talloc; universe@785: cx_testing_allocator_init(&talloc); universe@785: CxAllocator *allocator = &talloc.base; universe@785: CX_TEST_DO { universe@785: CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 8); universe@785: universe@785: cxMapPut(map, "key 1", (void *) "val 1"); universe@785: cxMapPut(map, "key 2", (void *) "val 2"); universe@785: cxMapPut(map, "key 3", (void *) "val 3"); universe@785: cxMapPut(map, "key 4", (void *) "val 4"); universe@785: cxMapPut(map, "key 5", (void *) "val 5"); universe@785: cxMapPut(map, "key 6", (void *) "val 6"); universe@785: universe@785: // 6/8 does not exceed 0.75, therefore the function should not rehash universe@785: int result = cxMapRehash(map); universe@785: CX_TEST_ASSERT(result == 0); universe@785: CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 8); universe@785: universe@785: cxMapDestroy(map); universe@785: CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); universe@785: } universe@785: cx_testing_allocator_destroy(&talloc); universe@785: } universe@785: universe@785: CX_TEST(test_hash_map_clear) { universe@785: CxTestingAllocator talloc; universe@785: cx_testing_allocator_init(&talloc); universe@785: CxAllocator *allocator = &talloc.base; universe@785: CX_TEST_DO { universe@785: CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); universe@785: universe@785: cxMapPut(map, "key 1", (void *) "val 1"); universe@785: cxMapPut(map, "key 2", (void *) "val 2"); universe@785: cxMapPut(map, "key 3", (void *) "val 3"); universe@785: universe@785: CX_TEST_ASSERT(map->size == 3); universe@785: universe@785: cxMapClear(map); universe@785: universe@785: CX_TEST_ASSERT(map->size == 0); universe@785: CX_TEST_ASSERT(cxMapGet(map, "key 1") == NULL); universe@785: CX_TEST_ASSERT(cxMapGet(map, "key 2") == NULL); universe@785: CX_TEST_ASSERT(cxMapGet(map, "key 3") == NULL); universe@785: universe@785: cxMapDestroy(map); universe@785: CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); universe@785: } universe@785: cx_testing_allocator_destroy(&talloc); universe@785: } universe@785: universe@785: CX_TEST(test_hash_map_store_ucx_strings) { universe@785: CxTestingAllocator talloc; universe@785: cx_testing_allocator_init(&talloc); universe@785: CxAllocator *allocator = &talloc.base; universe@785: CX_TEST_DO { universe@785: // create the map universe@785: CxMap *map = cxHashMapCreate(allocator, sizeof(cxstring), 8); universe@785: universe@785: // define some strings universe@785: cxstring s1 = CX_STR("this"); universe@785: cxstring s2 = CX_STR("is"); universe@785: cxstring s3 = CX_STR("a"); universe@785: cxstring s4 = CX_STR("test"); universe@785: cxstring s5 = CX_STR("setup"); universe@785: universe@785: // put them into the map universe@785: cxMapPut(map, "s1", &s1); universe@785: cxMapPut(map, "s2", &s2); universe@785: cxMapPut(map, "s3", &s3); universe@785: cxMapPut(map, "s4", &s4); universe@785: universe@785: // overwrite a value universe@785: cxMapPut(map, "s1", &s5); universe@785: universe@785: // look up a string universe@785: cxstring * s3p = cxMapGet(map, "s3"); universe@785: CX_TEST_ASSERT(s3p->length == s3.length); universe@785: CX_TEST_ASSERT(s3p->ptr == s3.ptr); universe@785: CX_TEST_ASSERT(s3p != &s3); universe@785: universe@785: // remove a string universe@785: cxMapRemove(map, "s2"); universe@785: CX_TEST_ASSERT(map->size == 3); universe@785: universe@785: // iterate universe@785: bool s3found = false, s4found = false, s5found = false; universe@785: CxIterator iter = cxMapIteratorValues(map); universe@785: cx_foreach(cxstring*, s, iter) { universe@785: s3found |= s3.ptr == s->ptr; universe@785: s4found |= s4.ptr == s->ptr; universe@785: s5found |= s5.ptr == s->ptr; universe@785: } universe@785: CX_TEST_ASSERT(s3found && s4found && s5found); universe@785: universe@785: cxMapDestroy(map); universe@785: CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); universe@785: } universe@785: cx_testing_allocator_destroy(&talloc); universe@785: } universe@785: universe@785: CX_TEST(test_hash_map_remove_via_iterator) { universe@785: CxTestingAllocator talloc; universe@785: cx_testing_allocator_init(&talloc); universe@785: CxAllocator *allocator = &talloc.base; universe@785: CX_TEST_DO { universe@785: CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 4); universe@785: universe@785: cxMapPut(map, "key 1", (void *) "val 1"); universe@785: cxMapPut(map, "key 2", (void *) "val 2"); universe@785: cxMapPut(map, "key 3", (void *) "val 3"); universe@785: cxMapPut(map, "key 4", (void *) "val 4"); universe@785: cxMapPut(map, "key 5", (void *) "val 5"); universe@785: cxMapPut(map, "key 6", (void *) "val 6"); universe@785: universe@785: CxMutIterator iter = cxMapMutIterator(map); universe@785: cx_foreach(CxMapEntry*, entry, iter) { universe@785: if (((char const *)entry->key->data)[4] % 2 == 1) cxIteratorFlagRemoval(iter); universe@785: } universe@785: CX_TEST_ASSERT(map->size == 3); universe@785: CX_TEST_ASSERT(iter.index == map->size); universe@785: universe@785: CX_TEST_ASSERT(cxMapGet(map, "key 1") == NULL); universe@785: CX_TEST_ASSERT(cxMapGet(map, "key 2") != NULL); universe@785: CX_TEST_ASSERT(cxMapGet(map, "key 3") == NULL); universe@785: CX_TEST_ASSERT(cxMapGet(map, "key 4") != NULL); universe@785: CX_TEST_ASSERT(cxMapGet(map, "key 5") == NULL); universe@785: CX_TEST_ASSERT(cxMapGet(map, "key 6") != NULL); universe@785: universe@785: cxMapDestroy(map); universe@785: CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); universe@785: } universe@785: cx_testing_allocator_destroy(&talloc); universe@785: } universe@785: universe@785: static void test_simple_destructor(void *data) { universe@785: strcpy(data, "OK"); universe@785: } universe@785: universe@785: static void test_advanced_destructor( universe@785: __attribute__((__unused__)) void *unused, universe@785: void *data universe@785: ) { universe@785: strcpy(data, "OK"); universe@785: } universe@785: universe@785: static CX_TEST_SUBROUTINE(verify_any_destructor, CxMap *map) { universe@785: CxHashKey k1 = cx_hash_key_str("key 1"); universe@785: CxHashKey k2 = cx_hash_key_str("key 2"); universe@785: CxHashKey k3 = cx_hash_key_str("key 3"); universe@785: CxHashKey k4 = cx_hash_key_str("key 4"); universe@785: CxHashKey k5 = cx_hash_key_str("key 5"); universe@785: universe@785: char v1[] = "val 1"; universe@785: char v2[] = "val 2"; universe@785: char v3[] = "val 3"; universe@785: char v4[] = "val 4"; universe@785: char v5[] = "val 5"; universe@785: universe@785: cxMapPut(map, k1, v1); universe@785: cxMapPut(map, k2, v2); universe@785: cxMapPut(map, k3, v3); universe@785: cxMapPut(map, k4, v4); universe@785: universe@785: cxMapRemove(map, k2); universe@785: char *r = cxMapRemoveAndGet(map, k3); universe@785: cxMapDetach(map, k1); universe@785: universe@785: CX_TEST_ASSERT(0 == strcmp(v1, "val 1")); universe@785: CX_TEST_ASSERT(0 == strcmp(v2, "OK")); universe@785: CX_TEST_ASSERT(0 == strcmp(v3, "val 3")); universe@785: CX_TEST_ASSERT(0 == strcmp(v4, "val 4")); universe@785: CX_TEST_ASSERT(0 == strcmp(v5, "val 5")); universe@785: CX_TEST_ASSERT(r == v3); universe@785: universe@785: cxMapClear(map); universe@785: universe@785: CX_TEST_ASSERT(0 == strcmp(v1, "val 1")); universe@785: CX_TEST_ASSERT(0 == strcmp(v2, "OK")); universe@785: CX_TEST_ASSERT(0 == strcmp(v3, "val 3")); universe@785: CX_TEST_ASSERT(0 == strcmp(v4, "OK")); universe@785: CX_TEST_ASSERT(0 == strcmp(v5, "val 5")); universe@785: universe@785: cxMapPut(map, k1, (void *) v1); universe@785: cxMapPut(map, k3, (void *) v3); universe@785: cxMapPut(map, k5, (void *) v5); universe@785: universe@785: { universe@785: CxMutIterator iter = cxMapMutIteratorKeys(map); universe@785: cx_foreach(CxHashKey*, key, iter) { universe@785: if (((char*)key->data)[4] == '1') cxIteratorFlagRemoval(iter); universe@785: } universe@785: } universe@785: { universe@785: CxMutIterator iter = cxMapMutIteratorValues(map); universe@785: cx_foreach(char*, v, iter) { universe@785: if (v[4] == '5') cxIteratorFlagRemoval(iter); universe@785: } universe@785: } universe@785: universe@785: CX_TEST_ASSERT(0 == strcmp(v1, "OK")); universe@785: CX_TEST_ASSERT(0 == strcmp(v2, "OK")); universe@785: CX_TEST_ASSERT(0 == strcmp(v3, "val 3")); universe@785: CX_TEST_ASSERT(0 == strcmp(v4, "OK")); universe@785: CX_TEST_ASSERT(0 == strcmp(v5, "OK")); universe@785: universe@785: v1[0] = v2[0] = v4[0] = v5[0] = 'c'; universe@785: universe@785: cxMapDestroy(map); universe@785: universe@785: CX_TEST_ASSERT(0 == strcmp(v1, "cK")); universe@785: CX_TEST_ASSERT(0 == strcmp(v2, "cK")); universe@785: CX_TEST_ASSERT(0 == strcmp(v3, "OK")); universe@785: CX_TEST_ASSERT(0 == strcmp(v4, "cK")); universe@785: CX_TEST_ASSERT(0 == strcmp(v5, "cK")); universe@785: } universe@785: universe@785: CX_TEST(test_hash_map_simple_destructor) { universe@785: CxTestingAllocator talloc; universe@785: cx_testing_allocator_init(&talloc); universe@785: CxAllocator *allocator = &talloc.base; universe@785: CX_TEST_DO { universe@785: CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); universe@785: map->simple_destructor = test_simple_destructor; universe@785: CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map); universe@785: CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); universe@785: } universe@785: cx_testing_allocator_destroy(&talloc); universe@785: } universe@785: universe@785: CX_TEST(test_hash_map_advanced_destructor) { universe@785: CxTestingAllocator talloc; universe@785: cx_testing_allocator_init(&talloc); universe@785: CxAllocator *allocator = &talloc.base; universe@785: CX_TEST_DO { universe@785: CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); universe@785: map->advanced_destructor = test_advanced_destructor; universe@785: CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map); universe@785: CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); universe@785: } universe@785: cx_testing_allocator_destroy(&talloc); universe@785: } universe@785: universe@785: CX_TEST(test_empty_map_size) { universe@785: CX_TEST_DO { universe@785: CX_TEST_ASSERT(cxEmptyMap->size == 0); universe@785: } universe@785: } universe@785: universe@785: CX_TEST(test_empty_map_iterator) { universe@785: CxMap *map = cxEmptyMap; universe@785: universe@785: CxIterator it1 = cxMapIterator(map); universe@785: CxIterator it2 = cxMapIteratorValues(map); universe@785: CxIterator it3 = cxMapIteratorKeys(map); universe@785: CxMutIterator it4 = cxMapMutIterator(map); universe@785: CxMutIterator it5 = cxMapMutIteratorValues(map); universe@785: CxMutIterator it6 = cxMapMutIteratorKeys(map); universe@785: universe@785: CX_TEST_DO { universe@785: CX_TEST_ASSERT(!cxIteratorValid(it1)); universe@785: CX_TEST_ASSERT(!cxIteratorValid(it2)); universe@785: CX_TEST_ASSERT(!cxIteratorValid(it3)); universe@785: CX_TEST_ASSERT(!cxIteratorValid(it4)); universe@785: CX_TEST_ASSERT(!cxIteratorValid(it5)); universe@785: CX_TEST_ASSERT(!cxIteratorValid(it6)); universe@785: universe@785: int c = 0; universe@785: cx_foreach(void*, data, it1) c++; universe@785: cx_foreach(void*, data, it2) c++; universe@785: cx_foreach(void*, data, it3) c++; universe@785: cx_foreach(void*, data, it4) c++; universe@785: cx_foreach(void*, data, it5) c++; universe@785: cx_foreach(void*, data, it6) c++; universe@785: CX_TEST_ASSERT(c == 0); universe@785: } universe@785: } universe@785: universe@785: CX_TEST(test_empty_map_no_ops) { universe@785: CX_TEST_DO { universe@785: // assertion not possible universe@785: // test that no segfault happens and valgrind is happy universe@785: cxMapClear(cxEmptyMap); universe@785: cxMapDestroy(cxEmptyMap); universe@785: CX_TEST_ASSERT(true); universe@785: } universe@785: } universe@785: universe@785: CX_TEST(test_empty_map_get) { universe@785: CX_TEST_DO { universe@785: CxHashKey key = cx_hash_key_str("test"); universe@785: CX_TEST_ASSERT(cxMapGet(cxEmptyMap, key) == NULL); universe@785: } universe@785: } universe@785: universe@785: CX_TEST(test_hash_map_generics) { universe@785: CxTestingAllocator talloc; universe@785: cx_testing_allocator_init(&talloc); universe@785: CxAllocator *allocator = &talloc.base; universe@785: CX_TEST_DO { universe@785: CxMap *map = cxHashMapCreate(allocator, sizeof(cxstring), 0); universe@785: cxMapPut(map, "test", "test"); universe@785: cxMapPut(map, cx_mutstr("foo"), "bar"); universe@785: cxMapPut(map, cx_str("hallo"), "welt"); universe@785: universe@785: CX_TEST_ASSERT(map->size == 3); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "test"), "test")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "hallo"), "welt")); universe@785: universe@785: // note: we don't have a destructor here, so remove and detach are the same universe@785: cxMapRemove(map, cx_str("test")); universe@785: char const *hallo = "hallo"; universe@785: cxMapDetach(map, hallo); universe@785: cxMapPut(map, cx_hash_key_str("key"), "value"); universe@785: universe@785: CX_TEST_ASSERT(map->size == 2); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key"), "value")); universe@785: CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar")); universe@785: universe@785: void *r; universe@785: r = cxMapRemoveAndGet(map, "key"); universe@785: r = cxMapRemoveAndGet(map, cx_str("foo")); universe@785: if (r != NULL) map->size = 47; universe@785: universe@785: CX_TEST_ASSERT(map->size == 0); universe@785: universe@785: cxMapDestroy(map); universe@785: CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); universe@785: } universe@785: cx_testing_allocator_destroy(&talloc); universe@785: } universe@785: universe@785: struct test_map_kv { universe@785: char const *key; universe@785: char const *value; universe@785: }; universe@785: universe@785: static struct test_map_kv const test_map_operations[] = { universe@785: {"key 1", "test"}, universe@785: {"key 2", "blub"}, universe@785: {"key 3", "hallo"}, universe@785: {"key 2", "foobar"}, universe@785: {"key 4", "value 4"}, universe@785: {"key 5", "value 5"}, universe@785: {"key 6", "value 6"}, universe@785: {"key 4", NULL}, universe@785: {"key 7", "value 7"}, universe@785: {"key 8", "value 8"}, universe@785: {"does not exist", NULL}, universe@785: {"key 9", "value 9"}, universe@785: {"key 6", "other value"}, universe@785: {"key 7", "something else"}, universe@785: {"key 8", NULL}, universe@785: {"key 2", NULL}, universe@785: {"key 8", "new value"}, universe@785: }; universe@785: static size_t const test_map_operations_len = universe@785: sizeof(test_map_operations) / sizeof(struct test_map_kv); universe@785: static struct test_map_kv test_map_reference[] = { universe@785: {"key 1", NULL}, universe@785: {"key 2", NULL}, universe@785: {"key 3", NULL}, universe@785: {"key 4", NULL}, universe@785: {"key 5", NULL}, universe@785: {"key 6", NULL}, universe@785: {"key 7", NULL}, universe@785: {"key 8", NULL}, universe@785: {"key 9", NULL}, universe@785: }; universe@785: static size_t const test_map_reference_len = universe@785: sizeof(test_map_reference) / sizeof(struct test_map_kv); universe@785: universe@785: static void test_map_reference_put(char const *key, char const* value) { universe@785: for (size_t i = 0 ; i < test_map_reference_len ; i++) { universe@785: if (0 == strcmp(key, test_map_reference[i].key)) { universe@785: test_map_reference[i].value = value; universe@785: return; universe@785: } universe@785: } universe@785: } universe@785: universe@785: static char const *test_map_reference_get(char const *key) { universe@785: for (size_t i = 0 ; i < test_map_reference_len ; i++) { universe@785: if (0 == strcmp(key, test_map_reference[i].key)) { universe@785: return test_map_reference[i].value; universe@785: } universe@785: } universe@785: return NULL; universe@785: } universe@785: universe@785: static char const *test_map_reference_remove(char const *key) { universe@785: for (size_t i = 0 ; i < test_map_reference_len ; i++) { universe@785: if (0 == strcmp(key, test_map_reference[i].key)) { universe@785: char const *ret = test_map_reference[i].value; universe@785: test_map_reference[i].value = NULL; universe@785: return ret; universe@785: } universe@785: } universe@785: return NULL; universe@785: } universe@785: universe@785: static size_t test_map_reference_size(void) { universe@785: size_t size = 0; universe@785: for (size_t i = 0; i < test_map_reference_len; i++) { universe@785: if (test_map_reference[i].value != NULL) { universe@785: size++; universe@785: } universe@785: } universe@785: return size; universe@785: } universe@785: universe@785: static CX_TEST_SUBROUTINE(verify_map_contents, CxMap *map) { universe@785: // verify that the reference map has same size (i.e. no other keys are mapped) universe@785: CX_TEST_ASSERT(map->size == test_map_reference_size()); universe@785: universe@785: // verify key iterator universe@785: { universe@785: // collect the keys from the map iterator universe@785: CxIterator keyiter = cxMapIteratorKeys(map); universe@785: CxHashKey *keys = calloc(map->size, sizeof(CxHashKey)); universe@785: cx_foreach(CxHashKey*, elem, keyiter) { universe@785: keys[keyiter.index] = *elem; universe@785: } universe@785: CX_TEST_ASSERT(keyiter.index == map->size); universe@785: // verify that all keys are mapped to values in reference map universe@785: for (size_t i = 0 ; i < map->size ; i++) { universe@785: cxmutstr ksz = cx_strdup(cx_strn(keys[i].data, keys[i].len)); universe@785: CX_TEST_ASSERT(test_map_reference_get(ksz.ptr) != NULL); universe@785: cx_strfree(&ksz); universe@785: } universe@785: free(keys); universe@785: } universe@785: universe@785: // verify value iterator universe@785: { universe@785: // by using that the values in our test data are unique strings universe@785: // we can re-use a similar approach as above universe@785: CxIterator valiter = cxMapIteratorValues(map); universe@785: char const** values = calloc(map->size, sizeof(char const*)); universe@785: cx_foreach(char const*, elem, valiter) { universe@785: values[valiter.index] = elem; universe@785: } universe@785: CX_TEST_ASSERT(valiter.index == map->size); universe@785: // verify that all values are present in the reference map universe@785: for (size_t i = 0 ; i < map->size ; i++) { universe@785: bool found = false; universe@785: for (size_t j = 0; j < test_map_reference_len ; j++) { universe@785: if (test_map_reference[j].value == values[i]) { universe@785: found = true; universe@785: break; universe@785: } universe@785: } universe@785: CX_TEST_ASSERTM(found, "A value was not found in the reference map"); universe@785: } universe@785: free(values); universe@785: } universe@785: universe@785: // verify pair iterator universe@785: { universe@785: CxIterator pairiter = cxMapIterator(map); universe@785: struct test_map_kv *pairs = calloc(map->size, sizeof(struct test_map_kv)); universe@785: cx_foreach(CxMapEntry*, entry, pairiter) { universe@785: CxHashKey const *key = entry->key; universe@785: pairs[pairiter.index].key = cx_strdup(cx_strn(key->data, key->len)).ptr; universe@785: pairs[pairiter.index].value = entry->value; universe@785: } universe@785: CX_TEST_ASSERT(pairiter.index == map->size); universe@785: // verify that all pairs are present in the reference map universe@785: for (size_t i = 0 ; i < map->size ; i++) { universe@785: CX_TEST_ASSERT(test_map_reference_get(pairs[i].key) == pairs[i].value); universe@785: // this was strdup'ed universe@785: free((void*)pairs[i].key); universe@785: } universe@785: free(pairs); universe@785: } universe@785: } universe@785: universe@785: CX_TEST(test_hash_map_basic_operations) { universe@785: CxTestingAllocator talloc; universe@785: cx_testing_allocator_init(&talloc); universe@785: CxAllocator *allocator = &talloc.base; universe@785: CX_TEST_DO { universe@785: // create the map universe@785: CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 8); universe@785: universe@785: // clear the reference map universe@785: for (size_t i = 0 ; i < test_map_reference_len ; i++) { universe@785: test_map_reference[i].value = NULL; universe@785: } universe@785: universe@785: // verify iterators for empty map universe@785: CX_TEST_CALL_SUBROUTINE(verify_map_contents, map); universe@785: universe@785: // execute operations and verify results universe@785: for (size_t i = 0 ; i < test_map_operations_len ; i++) { universe@785: struct test_map_kv kv = test_map_operations[i]; universe@785: CxHashKey key = cx_hash_key_str(kv.key); universe@785: key.hash = 0; // force the hash map to compute the hash universe@785: if (kv.value != NULL) { universe@785: // execute a put operation and verify that the exact value can be read back universe@785: test_map_reference_put(kv.key, kv.value); universe@785: int result = cxMapPut(map, key, (void *) kv.value); universe@785: CX_TEST_ASSERT(result == 0); universe@785: void *added = cxMapGet(map, key); universe@785: CX_TEST_ASSERT(0 == memcmp(kv.value, added, strlen(kv.value))); universe@785: } else { universe@785: // execute a remove and verify that the removed element was returned (or NULL) universe@785: char const *found = test_map_reference_remove(kv.key); universe@785: void *removed = cxMapRemoveAndGet(map, key); universe@785: CX_TEST_ASSERT(found == removed); universe@785: } universe@785: // compare the current map state with the reference map universe@785: CX_TEST_CALL_SUBROUTINE(verify_map_contents, map); universe@785: } universe@785: universe@785: // destroy the map and verify the memory (de)allocations universe@785: cxMapDestroy(map); universe@785: CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); universe@785: } universe@785: cx_testing_allocator_destroy(&talloc); universe@785: } universe@785: universe@785: CxTestSuite *cx_test_suite_hash_map(void) { universe@785: CxTestSuite *suite = cx_test_suite_new("map"); universe@785: universe@785: cx_test_register(suite, test_hash_map_create); universe@785: cx_test_register(suite, test_hash_map_create_store_pointers); universe@785: cx_test_register(suite, test_hash_map_basic_operations); universe@785: cx_test_register(suite, test_hash_map_rehash); universe@785: cx_test_register(suite, test_hash_map_rehash_not_required); universe@785: cx_test_register(suite, test_hash_map_clear); universe@785: cx_test_register(suite, test_hash_map_store_ucx_strings); universe@785: cx_test_register(suite, test_hash_map_remove_via_iterator); universe@785: cx_test_register(suite, test_empty_map_no_ops); universe@785: cx_test_register(suite, test_empty_map_size); universe@785: cx_test_register(suite, test_empty_map_get); universe@785: cx_test_register(suite, test_empty_map_iterator); universe@785: cx_test_register(suite, test_hash_map_generics); universe@785: universe@785: return suite; universe@785: }