tests/test_hash_map.c

/*
 * 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;
}