1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tests/test_hash_map.c Sat Dec 30 18:48:25 2023 +0100
1.3 @@ -0,0 +1,669 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 + *
1.7 + * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved.
1.8 + *
1.9 + * Redistribution and use in source and binary forms, with or without
1.10 + * modification, are permitted provided that the following conditions are met:
1.11 + *
1.12 + * 1. Redistributions of source code must retain the above copyright
1.13 + * notice, this list of conditions and the following disclaimer.
1.14 + *
1.15 + * 2. Redistributions in binary form must reproduce the above copyright
1.16 + * notice, this list of conditions and the following disclaimer in the
1.17 + * documentation and/or other materials provided with the distribution.
1.18 + *
1.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.29 + * POSSIBILITY OF SUCH DAMAGE.
1.30 + */
1.31 +
1.32 +#include "cx/test.h"
1.33 +#include "util_allocator.h"
1.34 +
1.35 +#include "cx/hash_map.h"
1.36 +
1.37 +CX_TEST(test_hash_map_create) {
1.38 + CxTestingAllocator talloc;
1.39 + cx_testing_allocator_init(&talloc);
1.40 + CxAllocator *allocator = &talloc.base;
1.41 + CX_TEST_DO {
1.42 + CxMap *map = cxHashMapCreate(allocator, 1, 0);
1.43 + struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
1.44 + CX_TEST_ASSERT(hmap->bucket_count > 0);
1.45 + for(size_t i = 0 ; i < hmap->bucket_count ; i++) {
1.46 + CX_TEST_ASSERT(hmap->buckets[i] == NULL);
1.47 + }
1.48 + CX_TEST_ASSERT(map->item_size == 1);
1.49 + CX_TEST_ASSERT(map->size == 0);
1.50 + CX_TEST_ASSERT(map->allocator == allocator);
1.51 + CX_TEST_ASSERT(!map->store_pointer);
1.52 + CX_TEST_ASSERT(map->cmpfunc == NULL);
1.53 + CX_TEST_ASSERT(map->simple_destructor == NULL);
1.54 + CX_TEST_ASSERT(map->advanced_destructor == NULL);
1.55 + CX_TEST_ASSERT(map->destructor_data == NULL);
1.56 + cxMapStorePointers(map);
1.57 + CX_TEST_ASSERT(map->store_pointer);
1.58 + CX_TEST_ASSERT(map->item_size == sizeof(void *));
1.59 + cxMapStoreObjects(map);
1.60 + CX_TEST_ASSERT(!map->store_pointer);
1.61 +
1.62 + cxMapDestroy(map);
1.63 + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1.64 + }
1.65 + cx_testing_allocator_destroy(&talloc);
1.66 +}
1.67 +
1.68 +CX_TEST(test_hash_map_create_store_pointers) {
1.69 + CxTestingAllocator talloc;
1.70 + cx_testing_allocator_init(&talloc);
1.71 + CxAllocator *allocator = &talloc.base;
1.72 + CX_TEST_DO {
1.73 + CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
1.74 + struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
1.75 + CX_TEST_ASSERT(hmap->bucket_count > 0);
1.76 + for (size_t i = 0; i < hmap->bucket_count; i++) {
1.77 + CX_TEST_ASSERT(hmap->buckets[i] == NULL);
1.78 + }
1.79 + CX_TEST_ASSERT(map->size == 0);
1.80 + CX_TEST_ASSERT(map->allocator == allocator);
1.81 + CX_TEST_ASSERT(map->store_pointer);
1.82 + CX_TEST_ASSERT(map->item_size == sizeof(void *));
1.83 +
1.84 + cxMapDestroy(map);
1.85 + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1.86 + }
1.87 + cx_testing_allocator_destroy(&talloc);
1.88 +}
1.89 +
1.90 +CX_TEST(test_hash_map_rehash) {
1.91 + CxTestingAllocator talloc;
1.92 + cx_testing_allocator_init(&talloc);
1.93 + CxAllocator *allocator = &talloc.base;
1.94 + CX_TEST_DO {
1.95 + CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 7);
1.96 +
1.97 + cxMapPut(map, "key 1", (void *) "val 1");
1.98 + cxMapPut(map, "key 2", (void *) "val 2");
1.99 + cxMapPut(map, "key 3", (void *) "val 3");
1.100 + cxMapPut(map, "foo 4", (void *) "val 4");
1.101 + cxMapPut(map, "key 5", (void *) "val 5");
1.102 + cxMapPut(map, "key 6", (void *) "val 6");
1.103 + cxMapPut(map, "bar 7", (void *) "val 7");
1.104 + cxMapPut(map, "key 8", (void *) "val 8");
1.105 + cxMapPut(map, "key 9", (void *) "val 9");
1.106 + cxMapPut(map, "key 10", (void *) "val 10");
1.107 +
1.108 + CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 7);
1.109 + int result = cxMapRehash(map);
1.110 + CX_TEST_ASSERT(result == 0);
1.111 + CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 25);
1.112 + CX_TEST_ASSERT(map->size == 10);
1.113 +
1.114 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 1"), "val 1"));
1.115 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 2"), "val 2"));
1.116 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 3"), "val 3"));
1.117 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo 4"), "val 4"));
1.118 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 5"), "val 5"));
1.119 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 6"), "val 6"));
1.120 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "bar 7"), "val 7"));
1.121 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 8"), "val 8"));
1.122 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 9"), "val 9"));
1.123 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 10"), "val 10"));
1.124 +
1.125 + cxMapDestroy(map);
1.126 + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1.127 + }
1.128 + cx_testing_allocator_destroy(&talloc);
1.129 +}
1.130 +
1.131 +CX_TEST(test_hash_map_rehash_not_required) {
1.132 + CxTestingAllocator talloc;
1.133 + cx_testing_allocator_init(&talloc);
1.134 + CxAllocator *allocator = &talloc.base;
1.135 + CX_TEST_DO {
1.136 + CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 8);
1.137 +
1.138 + cxMapPut(map, "key 1", (void *) "val 1");
1.139 + cxMapPut(map, "key 2", (void *) "val 2");
1.140 + cxMapPut(map, "key 3", (void *) "val 3");
1.141 + cxMapPut(map, "key 4", (void *) "val 4");
1.142 + cxMapPut(map, "key 5", (void *) "val 5");
1.143 + cxMapPut(map, "key 6", (void *) "val 6");
1.144 +
1.145 + // 6/8 does not exceed 0.75, therefore the function should not rehash
1.146 + int result = cxMapRehash(map);
1.147 + CX_TEST_ASSERT(result == 0);
1.148 + CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 8);
1.149 +
1.150 + cxMapDestroy(map);
1.151 + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1.152 + }
1.153 + cx_testing_allocator_destroy(&talloc);
1.154 +}
1.155 +
1.156 +CX_TEST(test_hash_map_clear) {
1.157 + CxTestingAllocator talloc;
1.158 + cx_testing_allocator_init(&talloc);
1.159 + CxAllocator *allocator = &talloc.base;
1.160 + CX_TEST_DO {
1.161 + CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
1.162 +
1.163 + cxMapPut(map, "key 1", (void *) "val 1");
1.164 + cxMapPut(map, "key 2", (void *) "val 2");
1.165 + cxMapPut(map, "key 3", (void *) "val 3");
1.166 +
1.167 + CX_TEST_ASSERT(map->size == 3);
1.168 +
1.169 + cxMapClear(map);
1.170 +
1.171 + CX_TEST_ASSERT(map->size == 0);
1.172 + CX_TEST_ASSERT(cxMapGet(map, "key 1") == NULL);
1.173 + CX_TEST_ASSERT(cxMapGet(map, "key 2") == NULL);
1.174 + CX_TEST_ASSERT(cxMapGet(map, "key 3") == NULL);
1.175 +
1.176 + cxMapDestroy(map);
1.177 + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1.178 + }
1.179 + cx_testing_allocator_destroy(&talloc);
1.180 +}
1.181 +
1.182 +CX_TEST(test_hash_map_store_ucx_strings) {
1.183 + CxTestingAllocator talloc;
1.184 + cx_testing_allocator_init(&talloc);
1.185 + CxAllocator *allocator = &talloc.base;
1.186 + CX_TEST_DO {
1.187 + // create the map
1.188 + CxMap *map = cxHashMapCreate(allocator, sizeof(cxstring), 8);
1.189 +
1.190 + // define some strings
1.191 + cxstring s1 = CX_STR("this");
1.192 + cxstring s2 = CX_STR("is");
1.193 + cxstring s3 = CX_STR("a");
1.194 + cxstring s4 = CX_STR("test");
1.195 + cxstring s5 = CX_STR("setup");
1.196 +
1.197 + // put them into the map
1.198 + cxMapPut(map, "s1", &s1);
1.199 + cxMapPut(map, "s2", &s2);
1.200 + cxMapPut(map, "s3", &s3);
1.201 + cxMapPut(map, "s4", &s4);
1.202 +
1.203 + // overwrite a value
1.204 + cxMapPut(map, "s1", &s5);
1.205 +
1.206 + // look up a string
1.207 + cxstring * s3p = cxMapGet(map, "s3");
1.208 + CX_TEST_ASSERT(s3p->length == s3.length);
1.209 + CX_TEST_ASSERT(s3p->ptr == s3.ptr);
1.210 + CX_TEST_ASSERT(s3p != &s3);
1.211 +
1.212 + // remove a string
1.213 + cxMapRemove(map, "s2");
1.214 + CX_TEST_ASSERT(map->size == 3);
1.215 +
1.216 + // iterate
1.217 + bool s3found = false, s4found = false, s5found = false;
1.218 + CxIterator iter = cxMapIteratorValues(map);
1.219 + cx_foreach(cxstring*, s, iter) {
1.220 + s3found |= s3.ptr == s->ptr;
1.221 + s4found |= s4.ptr == s->ptr;
1.222 + s5found |= s5.ptr == s->ptr;
1.223 + }
1.224 + CX_TEST_ASSERT(s3found && s4found && s5found);
1.225 +
1.226 + cxMapDestroy(map);
1.227 + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1.228 + }
1.229 + cx_testing_allocator_destroy(&talloc);
1.230 +}
1.231 +
1.232 +CX_TEST(test_hash_map_remove_via_iterator) {
1.233 + CxTestingAllocator talloc;
1.234 + cx_testing_allocator_init(&talloc);
1.235 + CxAllocator *allocator = &talloc.base;
1.236 + CX_TEST_DO {
1.237 + CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 4);
1.238 +
1.239 + cxMapPut(map, "key 1", (void *) "val 1");
1.240 + cxMapPut(map, "key 2", (void *) "val 2");
1.241 + cxMapPut(map, "key 3", (void *) "val 3");
1.242 + cxMapPut(map, "key 4", (void *) "val 4");
1.243 + cxMapPut(map, "key 5", (void *) "val 5");
1.244 + cxMapPut(map, "key 6", (void *) "val 6");
1.245 +
1.246 + CxMutIterator iter = cxMapMutIterator(map);
1.247 + cx_foreach(CxMapEntry*, entry, iter) {
1.248 + if (((char const *)entry->key->data)[4] % 2 == 1) cxIteratorFlagRemoval(iter);
1.249 + }
1.250 + CX_TEST_ASSERT(map->size == 3);
1.251 + CX_TEST_ASSERT(iter.index == map->size);
1.252 +
1.253 + CX_TEST_ASSERT(cxMapGet(map, "key 1") == NULL);
1.254 + CX_TEST_ASSERT(cxMapGet(map, "key 2") != NULL);
1.255 + CX_TEST_ASSERT(cxMapGet(map, "key 3") == NULL);
1.256 + CX_TEST_ASSERT(cxMapGet(map, "key 4") != NULL);
1.257 + CX_TEST_ASSERT(cxMapGet(map, "key 5") == NULL);
1.258 + CX_TEST_ASSERT(cxMapGet(map, "key 6") != NULL);
1.259 +
1.260 + cxMapDestroy(map);
1.261 + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1.262 + }
1.263 + cx_testing_allocator_destroy(&talloc);
1.264 +}
1.265 +
1.266 +static void test_simple_destructor(void *data) {
1.267 + strcpy(data, "OK");
1.268 +}
1.269 +
1.270 +static void test_advanced_destructor(
1.271 + __attribute__((__unused__)) void *unused,
1.272 + void *data
1.273 +) {
1.274 + strcpy(data, "OK");
1.275 +}
1.276 +
1.277 +static CX_TEST_SUBROUTINE(verify_any_destructor, CxMap *map) {
1.278 + CxHashKey k1 = cx_hash_key_str("key 1");
1.279 + CxHashKey k2 = cx_hash_key_str("key 2");
1.280 + CxHashKey k3 = cx_hash_key_str("key 3");
1.281 + CxHashKey k4 = cx_hash_key_str("key 4");
1.282 + CxHashKey k5 = cx_hash_key_str("key 5");
1.283 +
1.284 + char v1[] = "val 1";
1.285 + char v2[] = "val 2";
1.286 + char v3[] = "val 3";
1.287 + char v4[] = "val 4";
1.288 + char v5[] = "val 5";
1.289 +
1.290 + cxMapPut(map, k1, v1);
1.291 + cxMapPut(map, k2, v2);
1.292 + cxMapPut(map, k3, v3);
1.293 + cxMapPut(map, k4, v4);
1.294 +
1.295 + cxMapRemove(map, k2);
1.296 + char *r = cxMapRemoveAndGet(map, k3);
1.297 + cxMapDetach(map, k1);
1.298 +
1.299 + CX_TEST_ASSERT(0 == strcmp(v1, "val 1"));
1.300 + CX_TEST_ASSERT(0 == strcmp(v2, "OK"));
1.301 + CX_TEST_ASSERT(0 == strcmp(v3, "val 3"));
1.302 + CX_TEST_ASSERT(0 == strcmp(v4, "val 4"));
1.303 + CX_TEST_ASSERT(0 == strcmp(v5, "val 5"));
1.304 + CX_TEST_ASSERT(r == v3);
1.305 +
1.306 + cxMapClear(map);
1.307 +
1.308 + CX_TEST_ASSERT(0 == strcmp(v1, "val 1"));
1.309 + CX_TEST_ASSERT(0 == strcmp(v2, "OK"));
1.310 + CX_TEST_ASSERT(0 == strcmp(v3, "val 3"));
1.311 + CX_TEST_ASSERT(0 == strcmp(v4, "OK"));
1.312 + CX_TEST_ASSERT(0 == strcmp(v5, "val 5"));
1.313 +
1.314 + cxMapPut(map, k1, (void *) v1);
1.315 + cxMapPut(map, k3, (void *) v3);
1.316 + cxMapPut(map, k5, (void *) v5);
1.317 +
1.318 + {
1.319 + CxMutIterator iter = cxMapMutIteratorKeys(map);
1.320 + cx_foreach(CxHashKey*, key, iter) {
1.321 + if (((char*)key->data)[4] == '1') cxIteratorFlagRemoval(iter);
1.322 + }
1.323 + }
1.324 + {
1.325 + CxMutIterator iter = cxMapMutIteratorValues(map);
1.326 + cx_foreach(char*, v, iter) {
1.327 + if (v[4] == '5') cxIteratorFlagRemoval(iter);
1.328 + }
1.329 + }
1.330 +
1.331 + CX_TEST_ASSERT(0 == strcmp(v1, "OK"));
1.332 + CX_TEST_ASSERT(0 == strcmp(v2, "OK"));
1.333 + CX_TEST_ASSERT(0 == strcmp(v3, "val 3"));
1.334 + CX_TEST_ASSERT(0 == strcmp(v4, "OK"));
1.335 + CX_TEST_ASSERT(0 == strcmp(v5, "OK"));
1.336 +
1.337 + v1[0] = v2[0] = v4[0] = v5[0] = 'c';
1.338 +
1.339 + cxMapDestroy(map);
1.340 +
1.341 + CX_TEST_ASSERT(0 == strcmp(v1, "cK"));
1.342 + CX_TEST_ASSERT(0 == strcmp(v2, "cK"));
1.343 + CX_TEST_ASSERT(0 == strcmp(v3, "OK"));
1.344 + CX_TEST_ASSERT(0 == strcmp(v4, "cK"));
1.345 + CX_TEST_ASSERT(0 == strcmp(v5, "cK"));
1.346 +}
1.347 +
1.348 +CX_TEST(test_hash_map_simple_destructor) {
1.349 + CxTestingAllocator talloc;
1.350 + cx_testing_allocator_init(&talloc);
1.351 + CxAllocator *allocator = &talloc.base;
1.352 + CX_TEST_DO {
1.353 + CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
1.354 + map->simple_destructor = test_simple_destructor;
1.355 + CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map);
1.356 + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1.357 + }
1.358 + cx_testing_allocator_destroy(&talloc);
1.359 +}
1.360 +
1.361 +CX_TEST(test_hash_map_advanced_destructor) {
1.362 + CxTestingAllocator talloc;
1.363 + cx_testing_allocator_init(&talloc);
1.364 + CxAllocator *allocator = &talloc.base;
1.365 + CX_TEST_DO {
1.366 + CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
1.367 + map->advanced_destructor = test_advanced_destructor;
1.368 + CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map);
1.369 + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1.370 + }
1.371 + cx_testing_allocator_destroy(&talloc);
1.372 +}
1.373 +
1.374 +CX_TEST(test_empty_map_size) {
1.375 + CX_TEST_DO {
1.376 + CX_TEST_ASSERT(cxEmptyMap->size == 0);
1.377 + }
1.378 +}
1.379 +
1.380 +CX_TEST(test_empty_map_iterator) {
1.381 + CxMap *map = cxEmptyMap;
1.382 +
1.383 + CxIterator it1 = cxMapIterator(map);
1.384 + CxIterator it2 = cxMapIteratorValues(map);
1.385 + CxIterator it3 = cxMapIteratorKeys(map);
1.386 + CxMutIterator it4 = cxMapMutIterator(map);
1.387 + CxMutIterator it5 = cxMapMutIteratorValues(map);
1.388 + CxMutIterator it6 = cxMapMutIteratorKeys(map);
1.389 +
1.390 + CX_TEST_DO {
1.391 + CX_TEST_ASSERT(!cxIteratorValid(it1));
1.392 + CX_TEST_ASSERT(!cxIteratorValid(it2));
1.393 + CX_TEST_ASSERT(!cxIteratorValid(it3));
1.394 + CX_TEST_ASSERT(!cxIteratorValid(it4));
1.395 + CX_TEST_ASSERT(!cxIteratorValid(it5));
1.396 + CX_TEST_ASSERT(!cxIteratorValid(it6));
1.397 +
1.398 + int c = 0;
1.399 + cx_foreach(void*, data, it1) c++;
1.400 + cx_foreach(void*, data, it2) c++;
1.401 + cx_foreach(void*, data, it3) c++;
1.402 + cx_foreach(void*, data, it4) c++;
1.403 + cx_foreach(void*, data, it5) c++;
1.404 + cx_foreach(void*, data, it6) c++;
1.405 + CX_TEST_ASSERT(c == 0);
1.406 + }
1.407 +}
1.408 +
1.409 +CX_TEST(test_empty_map_no_ops) {
1.410 + CX_TEST_DO {
1.411 + // assertion not possible
1.412 + // test that no segfault happens and valgrind is happy
1.413 + cxMapClear(cxEmptyMap);
1.414 + cxMapDestroy(cxEmptyMap);
1.415 + CX_TEST_ASSERT(true);
1.416 + }
1.417 +}
1.418 +
1.419 +CX_TEST(test_empty_map_get) {
1.420 + CX_TEST_DO {
1.421 + CxHashKey key = cx_hash_key_str("test");
1.422 + CX_TEST_ASSERT(cxMapGet(cxEmptyMap, key) == NULL);
1.423 + }
1.424 +}
1.425 +
1.426 +CX_TEST(test_hash_map_generics) {
1.427 + CxTestingAllocator talloc;
1.428 + cx_testing_allocator_init(&talloc);
1.429 + CxAllocator *allocator = &talloc.base;
1.430 + CX_TEST_DO {
1.431 + CxMap *map = cxHashMapCreate(allocator, sizeof(cxstring), 0);
1.432 + cxMapPut(map, "test", "test");
1.433 + cxMapPut(map, cx_mutstr("foo"), "bar");
1.434 + cxMapPut(map, cx_str("hallo"), "welt");
1.435 +
1.436 + CX_TEST_ASSERT(map->size == 3);
1.437 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "test"), "test"));
1.438 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar"));
1.439 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "hallo"), "welt"));
1.440 +
1.441 + // note: we don't have a destructor here, so remove and detach are the same
1.442 + cxMapRemove(map, cx_str("test"));
1.443 + char const *hallo = "hallo";
1.444 + cxMapDetach(map, hallo);
1.445 + cxMapPut(map, cx_hash_key_str("key"), "value");
1.446 +
1.447 + CX_TEST_ASSERT(map->size == 2);
1.448 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key"), "value"));
1.449 + CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar"));
1.450 +
1.451 + void *r;
1.452 + r = cxMapRemoveAndGet(map, "key");
1.453 + r = cxMapRemoveAndGet(map, cx_str("foo"));
1.454 + if (r != NULL) map->size = 47;
1.455 +
1.456 + CX_TEST_ASSERT(map->size == 0);
1.457 +
1.458 + cxMapDestroy(map);
1.459 + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1.460 + }
1.461 + cx_testing_allocator_destroy(&talloc);
1.462 +}
1.463 +
1.464 +struct test_map_kv {
1.465 + char const *key;
1.466 + char const *value;
1.467 +};
1.468 +
1.469 +static struct test_map_kv const test_map_operations[] = {
1.470 + {"key 1", "test"},
1.471 + {"key 2", "blub"},
1.472 + {"key 3", "hallo"},
1.473 + {"key 2", "foobar"},
1.474 + {"key 4", "value 4"},
1.475 + {"key 5", "value 5"},
1.476 + {"key 6", "value 6"},
1.477 + {"key 4", NULL},
1.478 + {"key 7", "value 7"},
1.479 + {"key 8", "value 8"},
1.480 + {"does not exist", NULL},
1.481 + {"key 9", "value 9"},
1.482 + {"key 6", "other value"},
1.483 + {"key 7", "something else"},
1.484 + {"key 8", NULL},
1.485 + {"key 2", NULL},
1.486 + {"key 8", "new value"},
1.487 +};
1.488 +static size_t const test_map_operations_len =
1.489 + sizeof(test_map_operations) / sizeof(struct test_map_kv);
1.490 +static struct test_map_kv test_map_reference[] = {
1.491 + {"key 1", NULL},
1.492 + {"key 2", NULL},
1.493 + {"key 3", NULL},
1.494 + {"key 4", NULL},
1.495 + {"key 5", NULL},
1.496 + {"key 6", NULL},
1.497 + {"key 7", NULL},
1.498 + {"key 8", NULL},
1.499 + {"key 9", NULL},
1.500 +};
1.501 +static size_t const test_map_reference_len =
1.502 + sizeof(test_map_reference) / sizeof(struct test_map_kv);
1.503 +
1.504 +static void test_map_reference_put(char const *key, char const* value) {
1.505 + for (size_t i = 0 ; i < test_map_reference_len ; i++) {
1.506 + if (0 == strcmp(key, test_map_reference[i].key)) {
1.507 + test_map_reference[i].value = value;
1.508 + return;
1.509 + }
1.510 + }
1.511 +}
1.512 +
1.513 +static char const *test_map_reference_get(char const *key) {
1.514 + for (size_t i = 0 ; i < test_map_reference_len ; i++) {
1.515 + if (0 == strcmp(key, test_map_reference[i].key)) {
1.516 + return test_map_reference[i].value;
1.517 + }
1.518 + }
1.519 + return NULL;
1.520 +}
1.521 +
1.522 +static char const *test_map_reference_remove(char const *key) {
1.523 + for (size_t i = 0 ; i < test_map_reference_len ; i++) {
1.524 + if (0 == strcmp(key, test_map_reference[i].key)) {
1.525 + char const *ret = test_map_reference[i].value;
1.526 + test_map_reference[i].value = NULL;
1.527 + return ret;
1.528 + }
1.529 + }
1.530 + return NULL;
1.531 +}
1.532 +
1.533 +static size_t test_map_reference_size(void) {
1.534 + size_t size = 0;
1.535 + for (size_t i = 0; i < test_map_reference_len; i++) {
1.536 + if (test_map_reference[i].value != NULL) {
1.537 + size++;
1.538 + }
1.539 + }
1.540 + return size;
1.541 +}
1.542 +
1.543 +static CX_TEST_SUBROUTINE(verify_map_contents, CxMap *map) {
1.544 + // verify that the reference map has same size (i.e. no other keys are mapped)
1.545 + CX_TEST_ASSERT(map->size == test_map_reference_size());
1.546 +
1.547 + // verify key iterator
1.548 + {
1.549 + // collect the keys from the map iterator
1.550 + CxIterator keyiter = cxMapIteratorKeys(map);
1.551 + CxHashKey *keys = calloc(map->size, sizeof(CxHashKey));
1.552 + cx_foreach(CxHashKey*, elem, keyiter) {
1.553 + keys[keyiter.index] = *elem;
1.554 + }
1.555 + CX_TEST_ASSERT(keyiter.index == map->size);
1.556 + // verify that all keys are mapped to values in reference map
1.557 + for (size_t i = 0 ; i < map->size ; i++) {
1.558 + cxmutstr ksz = cx_strdup(cx_strn(keys[i].data, keys[i].len));
1.559 + CX_TEST_ASSERT(test_map_reference_get(ksz.ptr) != NULL);
1.560 + cx_strfree(&ksz);
1.561 + }
1.562 + free(keys);
1.563 + }
1.564 +
1.565 + // verify value iterator
1.566 + {
1.567 + // by using that the values in our test data are unique strings
1.568 + // we can re-use a similar approach as above
1.569 + CxIterator valiter = cxMapIteratorValues(map);
1.570 + char const** values = calloc(map->size, sizeof(char const*));
1.571 + cx_foreach(char const*, elem, valiter) {
1.572 + values[valiter.index] = elem;
1.573 + }
1.574 + CX_TEST_ASSERT(valiter.index == map->size);
1.575 + // verify that all values are present in the reference map
1.576 + for (size_t i = 0 ; i < map->size ; i++) {
1.577 + bool found = false;
1.578 + for (size_t j = 0; j < test_map_reference_len ; j++) {
1.579 + if (test_map_reference[j].value == values[i]) {
1.580 + found = true;
1.581 + break;
1.582 + }
1.583 + }
1.584 + CX_TEST_ASSERTM(found, "A value was not found in the reference map");
1.585 + }
1.586 + free(values);
1.587 + }
1.588 +
1.589 + // verify pair iterator
1.590 + {
1.591 + CxIterator pairiter = cxMapIterator(map);
1.592 + struct test_map_kv *pairs = calloc(map->size, sizeof(struct test_map_kv));
1.593 + cx_foreach(CxMapEntry*, entry, pairiter) {
1.594 + CxHashKey const *key = entry->key;
1.595 + pairs[pairiter.index].key = cx_strdup(cx_strn(key->data, key->len)).ptr;
1.596 + pairs[pairiter.index].value = entry->value;
1.597 + }
1.598 + CX_TEST_ASSERT(pairiter.index == map->size);
1.599 + // verify that all pairs are present in the reference map
1.600 + for (size_t i = 0 ; i < map->size ; i++) {
1.601 + CX_TEST_ASSERT(test_map_reference_get(pairs[i].key) == pairs[i].value);
1.602 + // this was strdup'ed
1.603 + free((void*)pairs[i].key);
1.604 + }
1.605 + free(pairs);
1.606 + }
1.607 +}
1.608 +
1.609 +CX_TEST(test_hash_map_basic_operations) {
1.610 + CxTestingAllocator talloc;
1.611 + cx_testing_allocator_init(&talloc);
1.612 + CxAllocator *allocator = &talloc.base;
1.613 + CX_TEST_DO {
1.614 + // create the map
1.615 + CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 8);
1.616 +
1.617 + // clear the reference map
1.618 + for (size_t i = 0 ; i < test_map_reference_len ; i++) {
1.619 + test_map_reference[i].value = NULL;
1.620 + }
1.621 +
1.622 + // verify iterators for empty map
1.623 + CX_TEST_CALL_SUBROUTINE(verify_map_contents, map);
1.624 +
1.625 + // execute operations and verify results
1.626 + for (size_t i = 0 ; i < test_map_operations_len ; i++) {
1.627 + struct test_map_kv kv = test_map_operations[i];
1.628 + CxHashKey key = cx_hash_key_str(kv.key);
1.629 + key.hash = 0; // force the hash map to compute the hash
1.630 + if (kv.value != NULL) {
1.631 + // execute a put operation and verify that the exact value can be read back
1.632 + test_map_reference_put(kv.key, kv.value);
1.633 + int result = cxMapPut(map, key, (void *) kv.value);
1.634 + CX_TEST_ASSERT(result == 0);
1.635 + void *added = cxMapGet(map, key);
1.636 + CX_TEST_ASSERT(0 == memcmp(kv.value, added, strlen(kv.value)));
1.637 + } else {
1.638 + // execute a remove and verify that the removed element was returned (or NULL)
1.639 + char const *found = test_map_reference_remove(kv.key);
1.640 + void *removed = cxMapRemoveAndGet(map, key);
1.641 + CX_TEST_ASSERT(found == removed);
1.642 + }
1.643 + // compare the current map state with the reference map
1.644 + CX_TEST_CALL_SUBROUTINE(verify_map_contents, map);
1.645 + }
1.646 +
1.647 + // destroy the map and verify the memory (de)allocations
1.648 + cxMapDestroy(map);
1.649 + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1.650 + }
1.651 + cx_testing_allocator_destroy(&talloc);
1.652 +}
1.653 +
1.654 +CxTestSuite *cx_test_suite_hash_map(void) {
1.655 + CxTestSuite *suite = cx_test_suite_new("map");
1.656 +
1.657 + cx_test_register(suite, test_hash_map_create);
1.658 + cx_test_register(suite, test_hash_map_create_store_pointers);
1.659 + cx_test_register(suite, test_hash_map_basic_operations);
1.660 + cx_test_register(suite, test_hash_map_rehash);
1.661 + cx_test_register(suite, test_hash_map_rehash_not_required);
1.662 + cx_test_register(suite, test_hash_map_clear);
1.663 + cx_test_register(suite, test_hash_map_store_ucx_strings);
1.664 + cx_test_register(suite, test_hash_map_remove_via_iterator);
1.665 + cx_test_register(suite, test_empty_map_no_ops);
1.666 + cx_test_register(suite, test_empty_map_size);
1.667 + cx_test_register(suite, test_empty_map_get);
1.668 + cx_test_register(suite, test_empty_map_iterator);
1.669 + cx_test_register(suite, test_hash_map_generics);
1.670 +
1.671 + return suite;
1.672 +}
