Mercurial > hg > ucx / file comparison

comparison: tests/test_hash_map.c

tests/test_hash_map.c

changeset 785
bb18daa62d5f
child 850
b2bc48c2b251
equal deleted inserted replaced
784:ba5faf85dec6 785:bb18daa62d5f
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2023 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include "cx/test.h"
30 #include "util_allocator.h"
31
32 #include "cx/hash_map.h"
33
34 CX_TEST(test_hash_map_create) {
35 CxTestingAllocator talloc;
36 cx_testing_allocator_init(&talloc);
37 CxAllocator *allocator = &talloc.base;
38 CX_TEST_DO {
39 CxMap *map = cxHashMapCreate(allocator, 1, 0);
40 struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
41 CX_TEST_ASSERT(hmap->bucket_count > 0);
42 for(size_t i = 0 ; i < hmap->bucket_count ; i++) {
43 CX_TEST_ASSERT(hmap->buckets[i] == NULL);
44 }
45 CX_TEST_ASSERT(map->item_size == 1);
46 CX_TEST_ASSERT(map->size == 0);
47 CX_TEST_ASSERT(map->allocator == allocator);
48 CX_TEST_ASSERT(!map->store_pointer);
49 CX_TEST_ASSERT(map->cmpfunc == NULL);
50 CX_TEST_ASSERT(map->simple_destructor == NULL);
51 CX_TEST_ASSERT(map->advanced_destructor == NULL);
52 CX_TEST_ASSERT(map->destructor_data == NULL);
53 cxMapStorePointers(map);
54 CX_TEST_ASSERT(map->store_pointer);
55 CX_TEST_ASSERT(map->item_size == sizeof(void *));
56 cxMapStoreObjects(map);
57 CX_TEST_ASSERT(!map->store_pointer);
58
59 cxMapDestroy(map);
60 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
61 }
62 cx_testing_allocator_destroy(&talloc);
63 }
64
65 CX_TEST(test_hash_map_create_store_pointers) {
66 CxTestingAllocator talloc;
67 cx_testing_allocator_init(&talloc);
68 CxAllocator *allocator = &talloc.base;
69 CX_TEST_DO {
70 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
71 struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
72 CX_TEST_ASSERT(hmap->bucket_count > 0);
73 for (size_t i = 0; i < hmap->bucket_count; i++) {
74 CX_TEST_ASSERT(hmap->buckets[i] == NULL);
75 }
76 CX_TEST_ASSERT(map->size == 0);
77 CX_TEST_ASSERT(map->allocator == allocator);
78 CX_TEST_ASSERT(map->store_pointer);
79 CX_TEST_ASSERT(map->item_size == sizeof(void *));
80
81 cxMapDestroy(map);
82 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
83 }
84 cx_testing_allocator_destroy(&talloc);
85 }
86
87 CX_TEST(test_hash_map_rehash) {
88 CxTestingAllocator talloc;
89 cx_testing_allocator_init(&talloc);
90 CxAllocator *allocator = &talloc.base;
91 CX_TEST_DO {
92 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 7);
93
94 cxMapPut(map, "key 1", (void *) "val 1");
95 cxMapPut(map, "key 2", (void *) "val 2");
96 cxMapPut(map, "key 3", (void *) "val 3");
97 cxMapPut(map, "foo 4", (void *) "val 4");
98 cxMapPut(map, "key 5", (void *) "val 5");
99 cxMapPut(map, "key 6", (void *) "val 6");
100 cxMapPut(map, "bar 7", (void *) "val 7");
101 cxMapPut(map, "key 8", (void *) "val 8");
102 cxMapPut(map, "key 9", (void *) "val 9");
103 cxMapPut(map, "key 10", (void *) "val 10");
104
105 CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 7);
106 int result = cxMapRehash(map);
107 CX_TEST_ASSERT(result == 0);
108 CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 25);
109 CX_TEST_ASSERT(map->size == 10);
110
111 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 1"), "val 1"));
112 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 2"), "val 2"));
113 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 3"), "val 3"));
114 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo 4"), "val 4"));
115 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 5"), "val 5"));
116 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 6"), "val 6"));
117 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "bar 7"), "val 7"));
118 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 8"), "val 8"));
119 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 9"), "val 9"));
120 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key 10"), "val 10"));
121
122 cxMapDestroy(map);
123 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
124 }
125 cx_testing_allocator_destroy(&talloc);
126 }
127
128 CX_TEST(test_hash_map_rehash_not_required) {
129 CxTestingAllocator talloc;
130 cx_testing_allocator_init(&talloc);
131 CxAllocator *allocator = &talloc.base;
132 CX_TEST_DO {
133 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 8);
134
135 cxMapPut(map, "key 1", (void *) "val 1");
136 cxMapPut(map, "key 2", (void *) "val 2");
137 cxMapPut(map, "key 3", (void *) "val 3");
138 cxMapPut(map, "key 4", (void *) "val 4");
139 cxMapPut(map, "key 5", (void *) "val 5");
140 cxMapPut(map, "key 6", (void *) "val 6");
141
142 // 6/8 does not exceed 0.75, therefore the function should not rehash
143 int result = cxMapRehash(map);
144 CX_TEST_ASSERT(result == 0);
145 CX_TEST_ASSERT(((struct cx_hash_map_s *)map)->bucket_count == 8);
146
147 cxMapDestroy(map);
148 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
149 }
150 cx_testing_allocator_destroy(&talloc);
151 }
152
153 CX_TEST(test_hash_map_clear) {
154 CxTestingAllocator talloc;
155 cx_testing_allocator_init(&talloc);
156 CxAllocator *allocator = &talloc.base;
157 CX_TEST_DO {
158 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
159
160 cxMapPut(map, "key 1", (void *) "val 1");
161 cxMapPut(map, "key 2", (void *) "val 2");
162 cxMapPut(map, "key 3", (void *) "val 3");
163
164 CX_TEST_ASSERT(map->size == 3);
165
166 cxMapClear(map);
167
168 CX_TEST_ASSERT(map->size == 0);
169 CX_TEST_ASSERT(cxMapGet(map, "key 1") == NULL);
170 CX_TEST_ASSERT(cxMapGet(map, "key 2") == NULL);
171 CX_TEST_ASSERT(cxMapGet(map, "key 3") == NULL);
172
173 cxMapDestroy(map);
174 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
175 }
176 cx_testing_allocator_destroy(&talloc);
177 }
178
179 CX_TEST(test_hash_map_store_ucx_strings) {
180 CxTestingAllocator talloc;
181 cx_testing_allocator_init(&talloc);
182 CxAllocator *allocator = &talloc.base;
183 CX_TEST_DO {
184 // create the map
185 CxMap *map = cxHashMapCreate(allocator, sizeof(cxstring), 8);
186
187 // define some strings
188 cxstring s1 = CX_STR("this");
189 cxstring s2 = CX_STR("is");
190 cxstring s3 = CX_STR("a");
191 cxstring s4 = CX_STR("test");
192 cxstring s5 = CX_STR("setup");
193
194 // put them into the map
195 cxMapPut(map, "s1", &s1);
196 cxMapPut(map, "s2", &s2);
197 cxMapPut(map, "s3", &s3);
198 cxMapPut(map, "s4", &s4);
199
200 // overwrite a value
201 cxMapPut(map, "s1", &s5);
202
203 // look up a string
204 cxstring * s3p = cxMapGet(map, "s3");
205 CX_TEST_ASSERT(s3p->length == s3.length);
206 CX_TEST_ASSERT(s3p->ptr == s3.ptr);
207 CX_TEST_ASSERT(s3p != &s3);
208
209 // remove a string
210 cxMapRemove(map, "s2");
211 CX_TEST_ASSERT(map->size == 3);
212
213 // iterate
214 bool s3found = false, s4found = false, s5found = false;
215 CxIterator iter = cxMapIteratorValues(map);
216 cx_foreach(cxstring*, s, iter) {
217 s3found |= s3.ptr == s->ptr;
218 s4found |= s4.ptr == s->ptr;
219 s5found |= s5.ptr == s->ptr;
220 }
221 CX_TEST_ASSERT(s3found && s4found && s5found);
222
223 cxMapDestroy(map);
224 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
225 }
226 cx_testing_allocator_destroy(&talloc);
227 }
228
229 CX_TEST(test_hash_map_remove_via_iterator) {
230 CxTestingAllocator talloc;
231 cx_testing_allocator_init(&talloc);
232 CxAllocator *allocator = &talloc.base;
233 CX_TEST_DO {
234 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 4);
235
236 cxMapPut(map, "key 1", (void *) "val 1");
237 cxMapPut(map, "key 2", (void *) "val 2");
238 cxMapPut(map, "key 3", (void *) "val 3");
239 cxMapPut(map, "key 4", (void *) "val 4");
240 cxMapPut(map, "key 5", (void *) "val 5");
241 cxMapPut(map, "key 6", (void *) "val 6");
242
243 CxMutIterator iter = cxMapMutIterator(map);
244 cx_foreach(CxMapEntry*, entry, iter) {
245 if (((char const *)entry->key->data)[4] % 2 == 1) cxIteratorFlagRemoval(iter);
246 }
247 CX_TEST_ASSERT(map->size == 3);
248 CX_TEST_ASSERT(iter.index == map->size);
249
250 CX_TEST_ASSERT(cxMapGet(map, "key 1") == NULL);
251 CX_TEST_ASSERT(cxMapGet(map, "key 2") != NULL);
252 CX_TEST_ASSERT(cxMapGet(map, "key 3") == NULL);
253 CX_TEST_ASSERT(cxMapGet(map, "key 4") != NULL);
254 CX_TEST_ASSERT(cxMapGet(map, "key 5") == NULL);
255 CX_TEST_ASSERT(cxMapGet(map, "key 6") != NULL);
256
257 cxMapDestroy(map);
258 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
259 }
260 cx_testing_allocator_destroy(&talloc);
261 }
262
263 static void test_simple_destructor(void *data) {
264 strcpy(data, "OK");
265 }
266
267 static void test_advanced_destructor(
268 __attribute__((__unused__)) void *unused,
269 void *data
270 ) {
271 strcpy(data, "OK");
272 }
273
274 static CX_TEST_SUBROUTINE(verify_any_destructor, CxMap *map) {
275 CxHashKey k1 = cx_hash_key_str("key 1");
276 CxHashKey k2 = cx_hash_key_str("key 2");
277 CxHashKey k3 = cx_hash_key_str("key 3");
278 CxHashKey k4 = cx_hash_key_str("key 4");
279 CxHashKey k5 = cx_hash_key_str("key 5");
280
281 char v1[] = "val 1";
282 char v2[] = "val 2";
283 char v3[] = "val 3";
284 char v4[] = "val 4";
285 char v5[] = "val 5";
286
287 cxMapPut(map, k1, v1);
288 cxMapPut(map, k2, v2);
289 cxMapPut(map, k3, v3);
290 cxMapPut(map, k4, v4);
291
292 cxMapRemove(map, k2);
293 char *r = cxMapRemoveAndGet(map, k3);
294 cxMapDetach(map, k1);
295
296 CX_TEST_ASSERT(0 == strcmp(v1, "val 1"));
297 CX_TEST_ASSERT(0 == strcmp(v2, "OK"));
298 CX_TEST_ASSERT(0 == strcmp(v3, "val 3"));
299 CX_TEST_ASSERT(0 == strcmp(v4, "val 4"));
300 CX_TEST_ASSERT(0 == strcmp(v5, "val 5"));
301 CX_TEST_ASSERT(r == v3);
302
303 cxMapClear(map);
304
305 CX_TEST_ASSERT(0 == strcmp(v1, "val 1"));
306 CX_TEST_ASSERT(0 == strcmp(v2, "OK"));
307 CX_TEST_ASSERT(0 == strcmp(v3, "val 3"));
308 CX_TEST_ASSERT(0 == strcmp(v4, "OK"));
309 CX_TEST_ASSERT(0 == strcmp(v5, "val 5"));
310
311 cxMapPut(map, k1, (void *) v1);
312 cxMapPut(map, k3, (void *) v3);
313 cxMapPut(map, k5, (void *) v5);
314
315 {
316 CxMutIterator iter = cxMapMutIteratorKeys(map);
317 cx_foreach(CxHashKey*, key, iter) {
318 if (((char*)key->data)[4] == '1') cxIteratorFlagRemoval(iter);
319 }
320 }
321 {
322 CxMutIterator iter = cxMapMutIteratorValues(map);
323 cx_foreach(char*, v, iter) {
324 if (v[4] == '5') cxIteratorFlagRemoval(iter);
325 }
326 }
327
328 CX_TEST_ASSERT(0 == strcmp(v1, "OK"));
329 CX_TEST_ASSERT(0 == strcmp(v2, "OK"));
330 CX_TEST_ASSERT(0 == strcmp(v3, "val 3"));
331 CX_TEST_ASSERT(0 == strcmp(v4, "OK"));
332 CX_TEST_ASSERT(0 == strcmp(v5, "OK"));
333
334 v1[0] = v2[0] = v4[0] = v5[0] = 'c';
335
336 cxMapDestroy(map);
337
338 CX_TEST_ASSERT(0 == strcmp(v1, "cK"));
339 CX_TEST_ASSERT(0 == strcmp(v2, "cK"));
340 CX_TEST_ASSERT(0 == strcmp(v3, "OK"));
341 CX_TEST_ASSERT(0 == strcmp(v4, "cK"));
342 CX_TEST_ASSERT(0 == strcmp(v5, "cK"));
343 }
344
345 CX_TEST(test_hash_map_simple_destructor) {
346 CxTestingAllocator talloc;
347 cx_testing_allocator_init(&talloc);
348 CxAllocator *allocator = &talloc.base;
349 CX_TEST_DO {
350 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
351 map->simple_destructor = test_simple_destructor;
352 CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map);
353 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
354 }
355 cx_testing_allocator_destroy(&talloc);
356 }
357
358 CX_TEST(test_hash_map_advanced_destructor) {
359 CxTestingAllocator talloc;
360 cx_testing_allocator_init(&talloc);
361 CxAllocator *allocator = &talloc.base;
362 CX_TEST_DO {
363 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
364 map->advanced_destructor = test_advanced_destructor;
365 CX_TEST_CALL_SUBROUTINE(verify_any_destructor, map);
366 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
367 }
368 cx_testing_allocator_destroy(&talloc);
369 }
370
371 CX_TEST(test_empty_map_size) {
372 CX_TEST_DO {
373 CX_TEST_ASSERT(cxEmptyMap->size == 0);
374 }
375 }
376
377 CX_TEST(test_empty_map_iterator) {
378 CxMap *map = cxEmptyMap;
379
380 CxIterator it1 = cxMapIterator(map);
381 CxIterator it2 = cxMapIteratorValues(map);
382 CxIterator it3 = cxMapIteratorKeys(map);
383 CxMutIterator it4 = cxMapMutIterator(map);
384 CxMutIterator it5 = cxMapMutIteratorValues(map);
385 CxMutIterator it6 = cxMapMutIteratorKeys(map);
386
387 CX_TEST_DO {
388 CX_TEST_ASSERT(!cxIteratorValid(it1));
389 CX_TEST_ASSERT(!cxIteratorValid(it2));
390 CX_TEST_ASSERT(!cxIteratorValid(it3));
391 CX_TEST_ASSERT(!cxIteratorValid(it4));
392 CX_TEST_ASSERT(!cxIteratorValid(it5));
393 CX_TEST_ASSERT(!cxIteratorValid(it6));
394
395 int c = 0;
396 cx_foreach(void*, data, it1) c++;
397 cx_foreach(void*, data, it2) c++;
398 cx_foreach(void*, data, it3) c++;
399 cx_foreach(void*, data, it4) c++;
400 cx_foreach(void*, data, it5) c++;
401 cx_foreach(void*, data, it6) c++;
402 CX_TEST_ASSERT(c == 0);
403 }
404 }
405
406 CX_TEST(test_empty_map_no_ops) {
407 CX_TEST_DO {
408 // assertion not possible
409 // test that no segfault happens and valgrind is happy
410 cxMapClear(cxEmptyMap);
411 cxMapDestroy(cxEmptyMap);
412 CX_TEST_ASSERT(true);
413 }
414 }
415
416 CX_TEST(test_empty_map_get) {
417 CX_TEST_DO {
418 CxHashKey key = cx_hash_key_str("test");
419 CX_TEST_ASSERT(cxMapGet(cxEmptyMap, key) == NULL);
420 }
421 }
422
423 CX_TEST(test_hash_map_generics) {
424 CxTestingAllocator talloc;
425 cx_testing_allocator_init(&talloc);
426 CxAllocator *allocator = &talloc.base;
427 CX_TEST_DO {
428 CxMap *map = cxHashMapCreate(allocator, sizeof(cxstring), 0);
429 cxMapPut(map, "test", "test");
430 cxMapPut(map, cx_mutstr("foo"), "bar");
431 cxMapPut(map, cx_str("hallo"), "welt");
432
433 CX_TEST_ASSERT(map->size == 3);
434 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "test"), "test"));
435 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar"));
436 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "hallo"), "welt"));
437
438 // note: we don't have a destructor here, so remove and detach are the same
439 cxMapRemove(map, cx_str("test"));
440 char const *hallo = "hallo";
441 cxMapDetach(map, hallo);
442 cxMapPut(map, cx_hash_key_str("key"), "value");
443
444 CX_TEST_ASSERT(map->size == 2);
445 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "key"), "value"));
446 CX_TEST_ASSERT(0 == strcmp(cxMapGet(map, "foo"), "bar"));
447
448 void *r;
449 r = cxMapRemoveAndGet(map, "key");
450 r = cxMapRemoveAndGet(map, cx_str("foo"));
451 if (r != NULL) map->size = 47;
452
453 CX_TEST_ASSERT(map->size == 0);
454
455 cxMapDestroy(map);
456 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
457 }
458 cx_testing_allocator_destroy(&talloc);
459 }
460
461 struct test_map_kv {
462 char const *key;
463 char const *value;
464 };
465
466 static struct test_map_kv const test_map_operations[] = {
467 {"key 1", "test"},
468 {"key 2", "blub"},
469 {"key 3", "hallo"},
470 {"key 2", "foobar"},
471 {"key 4", "value 4"},
472 {"key 5", "value 5"},
473 {"key 6", "value 6"},
474 {"key 4", NULL},
475 {"key 7", "value 7"},
476 {"key 8", "value 8"},
477 {"does not exist", NULL},
478 {"key 9", "value 9"},
479 {"key 6", "other value"},
480 {"key 7", "something else"},
481 {"key 8", NULL},
482 {"key 2", NULL},
483 {"key 8", "new value"},
484 };
485 static size_t const test_map_operations_len =
486 sizeof(test_map_operations) / sizeof(struct test_map_kv);
487 static struct test_map_kv test_map_reference[] = {
488 {"key 1", NULL},
489 {"key 2", NULL},
490 {"key 3", NULL},
491 {"key 4", NULL},
492 {"key 5", NULL},
493 {"key 6", NULL},
494 {"key 7", NULL},
495 {"key 8", NULL},
496 {"key 9", NULL},
497 };
498 static size_t const test_map_reference_len =
499 sizeof(test_map_reference) / sizeof(struct test_map_kv);
500
501 static void test_map_reference_put(char const *key, char const* value) {
502 for (size_t i = 0 ; i < test_map_reference_len ; i++) {
503 if (0 == strcmp(key, test_map_reference[i].key)) {
504 test_map_reference[i].value = value;
505 return;
506 }
507 }
508 }
509
510 static char const *test_map_reference_get(char const *key) {
511 for (size_t i = 0 ; i < test_map_reference_len ; i++) {
512 if (0 == strcmp(key, test_map_reference[i].key)) {
513 return test_map_reference[i].value;
514 }
515 }
516 return NULL;
517 }
518
519 static char const *test_map_reference_remove(char const *key) {
520 for (size_t i = 0 ; i < test_map_reference_len ; i++) {
521 if (0 == strcmp(key, test_map_reference[i].key)) {
522 char const *ret = test_map_reference[i].value;
523 test_map_reference[i].value = NULL;
524 return ret;
525 }
526 }
527 return NULL;
528 }
529
530 static size_t test_map_reference_size(void) {
531 size_t size = 0;
532 for (size_t i = 0; i < test_map_reference_len; i++) {
533 if (test_map_reference[i].value != NULL) {
534 size++;
535 }
536 }
537 return size;
538 }
539
540 static CX_TEST_SUBROUTINE(verify_map_contents, CxMap *map) {
541 // verify that the reference map has same size (i.e. no other keys are mapped)
542 CX_TEST_ASSERT(map->size == test_map_reference_size());
543
544 // verify key iterator
545 {
546 // collect the keys from the map iterator
547 CxIterator keyiter = cxMapIteratorKeys(map);
548 CxHashKey *keys = calloc(map->size, sizeof(CxHashKey));
549 cx_foreach(CxHashKey*, elem, keyiter) {
550 keys[keyiter.index] = *elem;
551 }
552 CX_TEST_ASSERT(keyiter.index == map->size);
553 // verify that all keys are mapped to values in reference map
554 for (size_t i = 0 ; i < map->size ; i++) {
555 cxmutstr ksz = cx_strdup(cx_strn(keys[i].data, keys[i].len));
556 CX_TEST_ASSERT(test_map_reference_get(ksz.ptr) != NULL);
557 cx_strfree(&ksz);
558 }
559 free(keys);
560 }
561
562 // verify value iterator
563 {
564 // by using that the values in our test data are unique strings
565 // we can re-use a similar approach as above
566 CxIterator valiter = cxMapIteratorValues(map);
567 char const** values = calloc(map->size, sizeof(char const*));
568 cx_foreach(char const*, elem, valiter) {
569 values[valiter.index] = elem;
570 }
571 CX_TEST_ASSERT(valiter.index == map->size);
572 // verify that all values are present in the reference map
573 for (size_t i = 0 ; i < map->size ; i++) {
574 bool found = false;
575 for (size_t j = 0; j < test_map_reference_len ; j++) {
576 if (test_map_reference[j].value == values[i]) {
577 found = true;
578 break;
579 }
580 }
581 CX_TEST_ASSERTM(found, "A value was not found in the reference map");
582 }
583 free(values);
584 }
585
586 // verify pair iterator
587 {
588 CxIterator pairiter = cxMapIterator(map);
589 struct test_map_kv *pairs = calloc(map->size, sizeof(struct test_map_kv));
590 cx_foreach(CxMapEntry*, entry, pairiter) {
591 CxHashKey const *key = entry->key;
592 pairs[pairiter.index].key = cx_strdup(cx_strn(key->data, key->len)).ptr;
593 pairs[pairiter.index].value = entry->value;
594 }
595 CX_TEST_ASSERT(pairiter.index == map->size);
596 // verify that all pairs are present in the reference map
597 for (size_t i = 0 ; i < map->size ; i++) {
598 CX_TEST_ASSERT(test_map_reference_get(pairs[i].key) == pairs[i].value);
599 // this was strdup'ed
600 free((void*)pairs[i].key);
601 }
602 free(pairs);
603 }
604 }
605
606 CX_TEST(test_hash_map_basic_operations) {
607 CxTestingAllocator talloc;
608 cx_testing_allocator_init(&talloc);
609 CxAllocator *allocator = &talloc.base;
610 CX_TEST_DO {
611 // create the map
612 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 8);
613
614 // clear the reference map
615 for (size_t i = 0 ; i < test_map_reference_len ; i++) {
616 test_map_reference[i].value = NULL;
617 }
618
619 // verify iterators for empty map
620 CX_TEST_CALL_SUBROUTINE(verify_map_contents, map);
621
622 // execute operations and verify results
623 for (size_t i = 0 ; i < test_map_operations_len ; i++) {
624 struct test_map_kv kv = test_map_operations[i];
625 CxHashKey key = cx_hash_key_str(kv.key);
626 key.hash = 0; // force the hash map to compute the hash
627 if (kv.value != NULL) {
628 // execute a put operation and verify that the exact value can be read back
629 test_map_reference_put(kv.key, kv.value);
630 int result = cxMapPut(map, key, (void *) kv.value);
631 CX_TEST_ASSERT(result == 0);
632 void *added = cxMapGet(map, key);
633 CX_TEST_ASSERT(0 == memcmp(kv.value, added, strlen(kv.value)));
634 } else {
635 // execute a remove and verify that the removed element was returned (or NULL)
636 char const *found = test_map_reference_remove(kv.key);
637 void *removed = cxMapRemoveAndGet(map, key);
638 CX_TEST_ASSERT(found == removed);
639 }
640 // compare the current map state with the reference map
641 CX_TEST_CALL_SUBROUTINE(verify_map_contents, map);
642 }
643
644 // destroy the map and verify the memory (de)allocations
645 cxMapDestroy(map);
646 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
647 }
648 cx_testing_allocator_destroy(&talloc);
649 }
650
651 CxTestSuite *cx_test_suite_hash_map(void) {
652 CxTestSuite *suite = cx_test_suite_new("map");
653
654 cx_test_register(suite, test_hash_map_create);
655 cx_test_register(suite, test_hash_map_create_store_pointers);
656 cx_test_register(suite, test_hash_map_basic_operations);
657 cx_test_register(suite, test_hash_map_rehash);
658 cx_test_register(suite, test_hash_map_rehash_not_required);
659 cx_test_register(suite, test_hash_map_clear);
660 cx_test_register(suite, test_hash_map_store_ucx_strings);
661 cx_test_register(suite, test_hash_map_remove_via_iterator);
662 cx_test_register(suite, test_empty_map_no_ops);
663 cx_test_register(suite, test_empty_map_size);
664 cx_test_register(suite, test_empty_map_get);
665 cx_test_register(suite, test_empty_map_iterator);
666 cx_test_register(suite, test_hash_map_generics);
667
668 return suite;
669 }

Mercurial Repository: ucx

mercurial