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/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 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_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;
        test_hash_map_clone_func_max_clones = 100; // no limit
        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_clones = 2;
        CX_TEST_ASSERT(0 != cxMapClone(dst, src, test_hash_map_clone_func, NULL, &c));
        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;
        test_hash_map_clone_func_max_clones = 100; // no limit
        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;
        test_hash_map_clone_func_max_clones = 100; // no limit
        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_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;
        test_hash_map_clone_func_max_clones = 100; // no limit
        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_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;
        test_hash_map_clone_func_max_clones = 100; // no limit
        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_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_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;
}