diff -r ba5faf85dec6 -r bb18daa62d5f tests/test_hash_map.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/test_hash_map.c Sat Dec 30 18:48:25 2023 +0100 @@ -0,0 +1,669 @@ +/* + * 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/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->item_size == 1); + CX_TEST_ASSERT(map->size == 0); + CX_TEST_ASSERT(map->allocator == allocator); + CX_TEST_ASSERT(!map->store_pointer); + CX_TEST_ASSERT(map->cmpfunc == NULL); + CX_TEST_ASSERT(map->simple_destructor == NULL); + CX_TEST_ASSERT(map->advanced_destructor == NULL); + CX_TEST_ASSERT(map->destructor_data == NULL); + cxMapStorePointers(map); + CX_TEST_ASSERT(map->store_pointer); + CX_TEST_ASSERT(map->item_size == sizeof(void *)); + cxMapStoreObjects(map); + CX_TEST_ASSERT(!map->store_pointer); + + cxMapDestroy(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->size == 0); + CX_TEST_ASSERT(map->allocator == allocator); + CX_TEST_ASSERT(map->store_pointer); + CX_TEST_ASSERT(map->item_size == sizeof(void *)); + + cxMapDestroy(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->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")); + + cxMapDestroy(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); + + cxMapDestroy(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->size == 3); + + cxMapClear(map); + + CX_TEST_ASSERT(map->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); + + cxMapDestroy(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 + cxMapRemove(map, "s2"); + CX_TEST_ASSERT(map->size == 3); + + // iterate + bool s3found = false, s4found = false, s5found = false; + CxIterator 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); + + cxMapDestroy(map); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +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"); + + CxMutIterator iter = cxMapMutIterator(map); + cx_foreach(CxMapEntry*, entry, iter) { + if (((char const *)entry->key->data)[4] % 2 == 1) cxIteratorFlagRemoval(iter); + } + CX_TEST_ASSERT(map->size == 3); + CX_TEST_ASSERT(iter.index == map->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); + + cxMapDestroy(map); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +static void test_simple_destructor(void *data) { + strcpy(data, "OK"); +} + +static void test_advanced_destructor( + __attribute__((__unused__)) void *unused, + void *data +) { + strcpy(data, "OK"); +} + +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"; + + cxMapPut(map, k1, v1); + cxMapPut(map, k2, v2); + cxMapPut(map, k3, v3); + cxMapPut(map, k4, v4); + + cxMapRemove(map, k2); + char *r = cxMapRemoveAndGet(map, k3); + cxMapDetach(map, k1); + + 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")); + CX_TEST_ASSERT(r == v3); + + cxMapClear(map); + + 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, "OK")); + CX_TEST_ASSERT(0 == strcmp(v5, "val 5")); + + cxMapPut(map, k1, (void *) v1); + cxMapPut(map, k3, (void *) v3); + cxMapPut(map, k5, (void *) v5); + + { + CxMutIterator iter = cxMapMutIteratorKeys(map); + cx_foreach(CxHashKey*, key, iter) { + if (((char*)key->data)[4] == '1') cxIteratorFlagRemoval(iter); + } + } + { + CxMutIterator iter = cxMapMutIteratorValues(map); + cx_foreach(char*, v, iter) { + if (v[4] == '5') cxIteratorFlagRemoval(iter); + } + } + + CX_TEST_ASSERT(0 == strcmp(v1, "OK")); + CX_TEST_ASSERT(0 == strcmp(v2, "OK")); + CX_TEST_ASSERT(0 == strcmp(v3, "val 3")); + CX_TEST_ASSERT(0 == strcmp(v4, "OK")); + CX_TEST_ASSERT(0 == strcmp(v5, "OK")); + + v1[0] = v2[0] = v4[0] = v5[0] = 'c'; + + cxMapDestroy(map); + + CX_TEST_ASSERT(0 == strcmp(v1, "cK")); + CX_TEST_ASSERT(0 == strcmp(v2, "cK")); + CX_TEST_ASSERT(0 == strcmp(v3, "OK")); + CX_TEST_ASSERT(0 == strcmp(v4, "cK")); + CX_TEST_ASSERT(0 == strcmp(v5, "cK")); +} + +CX_TEST(test_hash_map_simple_destructor) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *allocator = &talloc.base; + CX_TEST_DO { + CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); + map->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) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + CxAllocator *allocator = &talloc.base; + CX_TEST_DO { + CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0); + map->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_empty_map_size) { + CX_TEST_DO { + CX_TEST_ASSERT(cxEmptyMap->size == 0); + } +} + +CX_TEST(test_empty_map_iterator) { + CxMap *map = cxEmptyMap; + + CxIterator it1 = cxMapIterator(map); + CxIterator it2 = cxMapIteratorValues(map); + CxIterator it3 = cxMapIteratorKeys(map); + CxMutIterator it4 = cxMapMutIterator(map); + CxMutIterator it5 = cxMapMutIteratorValues(map); + CxMutIterator it6 = cxMapMutIteratorKeys(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); + cxMapDestroy(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, sizeof(cxstring), 0); + cxMapPut(map, "test", "test"); + cxMapPut(map, cx_mutstr("foo"), "bar"); + cxMapPut(map, cx_str("hallo"), "welt"); + + CX_TEST_ASSERT(map->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")); + + // note: we don't have a destructor here, so remove and detach are the same + cxMapRemove(map, cx_str("test")); + char const *hallo = "hallo"; + cxMapDetach(map, hallo); + cxMapPut(map, cx_hash_key_str("key"), "value"); + + CX_TEST_ASSERT(map->size == 2); + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key"), "value")); + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar")); + + void *r; + r = cxMapRemoveAndGet(map, "key"); + r = cxMapRemoveAndGet(map, cx_str("foo")); + if (r != NULL) map->size = 47; + + CX_TEST_ASSERT(map->size == 0); + + cxMapDestroy(map); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); + } + cx_testing_allocator_destroy(&talloc); +} + +struct test_map_kv { + char const *key; + char const *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 size_t const 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 size_t const test_map_reference_len = + sizeof(test_map_reference) / sizeof(struct test_map_kv); + +static void test_map_reference_put(char const *key, char const* 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 char const *test_map_reference_get(char const *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 char const *test_map_reference_remove(char const *key) { + for (size_t i = 0 ; i < test_map_reference_len ; i++) { + if (0 == strcmp(key, test_map_reference[i].key)) { + char const *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->size == test_map_reference_size()); + + // verify key iterator + { + // collect the keys from the map iterator + CxIterator keyiter = cxMapIteratorKeys(map); + CxHashKey *keys = calloc(map->size, sizeof(CxHashKey)); + cx_foreach(CxHashKey*, elem, keyiter) { + keys[keyiter.index] = *elem; + } + CX_TEST_ASSERT(keyiter.index == map->size); + // verify that all keys are mapped to values in reference map + for (size_t i = 0 ; i < map->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 + CxIterator valiter = cxMapIteratorValues(map); + char const** values = calloc(map->size, sizeof(char const*)); + cx_foreach(char const*, elem, valiter) { + values[valiter.index] = elem; + } + CX_TEST_ASSERT(valiter.index == map->size); + // verify that all values are present in the reference map + for (size_t i = 0 ; i < map->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 + { + CxIterator pairiter = cxMapIterator(map); + struct test_map_kv *pairs = calloc(map->size, sizeof(struct test_map_kv)); + cx_foreach(CxMapEntry*, entry, pairiter) { + CxHashKey const *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->size); + // verify that all pairs are present in the reference map + for (size_t i = 0 ; i < map->size ; i++) { + CX_TEST_ASSERT(test_map_reference_get(pairs[i].key) == pairs[i].value); + // this was strdup'ed + free((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) + char const *found = test_map_reference_remove(kv.key); + void *removed = cxMapRemoveAndGet(map, key); + CX_TEST_ASSERT(found == removed); + } + // 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 + cxMapDestroy(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_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_remove_via_iterator); + 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_hash_map_generics); + + return suite; +}