1 #include <test.h>
2
3 #include <array_map_priv.h>
4 #include <hash_map_priv.h>
5 #include <map.h>
6 #include <string_lib.h>
7
8 #include <alloc.h>
9
10 #define HASH_MAP_INIT_SIZE 128
11 #define HASH_MAP_MAX_LOAD_FACTOR 0.75
12 #define HASH_MAP_MIN_LOAD_FACTOR 0.35
13 #define MIN_HASHMAP_BUCKETS 1 << 5
14
ConstHash(ARG_UNUSED const void * key,ARG_UNUSED unsigned int seed)15 static unsigned int ConstHash(ARG_UNUSED const void *key,
16 ARG_UNUSED unsigned int seed)
17 {
18 return 0;
19 }
20
test_new_destroy(void)21 static void test_new_destroy(void)
22 {
23 Map *map = MapNew(NULL, NULL, NULL, NULL);
24 assert_int_equal(MapSize(map), 0);
25 MapDestroy(map);
26 }
27
test_new_hashmap_bad_size(void)28 static void test_new_hashmap_bad_size(void)
29 {
30 /* too small */
31 HashMap *hashmap = HashMapNew(StringHash_untyped, StringEqual_untyped,
32 free, free, MIN_HASHMAP_BUCKETS >> 1);
33 assert_int_equal(hashmap->size, MIN_HASHMAP_BUCKETS);
34 HashMapDestroy(hashmap);
35
36 /* not a pow2 */
37 hashmap = HashMapNew(StringHash_untyped, StringEqual_untyped,
38 free, free, 123);
39 assert_int_equal(hashmap->size, 128);
40 HashMapDestroy(hashmap);
41
42 /* TODO: test size too big? Would require a lot of memory to be available. */
43 }
44
test_insert(void)45 static void test_insert(void)
46 {
47 StringMap *map = StringMapNew();
48
49 assert_false(StringMapHasKey(map, "one"));
50 assert_false(StringMapInsert(map, xstrdup("one"), xstrdup("first")));
51 assert_true(StringMapHasKey(map, "one"));
52 assert_int_equal(StringMapSize(map), 1);
53 assert_true(StringMapInsert(map, xstrdup("one"), xstrdup("duplicate")));
54 assert_int_equal(StringMapSize(map), 1);
55
56 assert_false(StringMapHasKey(map, "two"));
57 assert_false(StringMapInsert(map, xstrdup("two"), xstrdup("second")));
58 assert_true(StringMapHasKey(map, "two"));
59 assert_int_equal(StringMapSize(map), 2);
60
61 assert_false(StringMapHasKey(map, "third"));
62 assert_false(StringMapInsert(map, xstrdup("third"), xstrdup("first")));
63 assert_true(StringMapHasKey(map, "third"));
64
65 assert_true(StringMapInsert(map, xstrdup("third"), xstrdup("stuff")));
66 assert_true(StringMapHasKey(map, "third"));
67 assert_int_equal(StringMapSize(map), 3);
68
69 StringMapDestroy(map);
70 }
71
CharTimes(char c,size_t times)72 static char *CharTimes(char c, size_t times)
73 {
74 char *res = xmalloc(times + 1);
75 memset(res, c, times);
76 res[times] = '\0';
77 return res;
78 }
79
80 static StringMap *jumbo_map;
81
test_insert_jumbo(void)82 static void test_insert_jumbo(void)
83 {
84 jumbo_map = StringMapNew();
85
86 for (int i = 0; i < 10000; i++)
87 {
88 /* char *s = CharTimes('a', i); */
89 char s[i+1];
90 memset(s, 'a', i);
91 s[i] = '\0';
92
93 assert_false(StringMapHasKey(jumbo_map, s));
94 assert_false(StringMapInsert(jumbo_map, xstrdup(s), xstrdup(s)));
95 assert_true(StringMapHasKey(jumbo_map, s));
96 /* free(s); */
97 }
98
99 StringMapPrintStats(jumbo_map, stdout);
100 }
101
test_remove(void)102 static void test_remove(void)
103 {
104 HashMap *hashmap = HashMapNew(ConstHash, StringEqual_untyped, free, free,
105 HASH_MAP_INIT_SIZE);
106
107 HashMapInsert(hashmap, xstrdup("a"), xstrdup("b"));
108
109 MapKeyValue *item = HashMapGet(hashmap, "a");
110 assert_string_equal(item->key, "a");
111 assert_string_equal(item->value, "b");
112
113 assert_true(HashMapRemove(hashmap, "a"));
114 assert_int_equal(HashMapGet(hashmap, "a"), NULL);
115
116 HashMapDestroy(hashmap);
117 }
118
test_add_n_as_to_map(HashMap * hashmap,unsigned int i)119 static void test_add_n_as_to_map(HashMap *hashmap, unsigned int i)
120 {
121 char s[i+1];
122 memset(s, 'a', i);
123 s[i] = '\0';
124
125 assert_true(HashMapGet(hashmap, s) == NULL);
126 assert_false(HashMapInsert(hashmap, xstrdup(s), xstrdup(s)));
127 assert_true(HashMapGet(hashmap, s) != NULL);
128 }
129
test_remove_n_as_from_map(HashMap * hashmap,unsigned int i)130 static void test_remove_n_as_from_map(HashMap *hashmap, unsigned int i)
131 {
132 char s[i+1];
133 memset(s, 'a', i);
134 s[i] = '\0';
135
136 assert_true(HashMapGet(hashmap, s) != NULL);
137 char * dup = xstrdup(s);
138 assert_true(HashMapRemove(hashmap, dup));
139 free(dup);
140 assert_true(HashMapGet(hashmap, s) == NULL);
141 }
142
assert_n_as_in_map(HashMap * hashmap,unsigned int i,bool in)143 static void assert_n_as_in_map(HashMap *hashmap, unsigned int i, bool in)
144 {
145 char s[i+1];
146 memset(s, 'a', i);
147 s[i] = '\0';
148
149 if (in)
150 {
151 assert_true(HashMapGet(hashmap, s) != NULL);
152 }
153 else
154 {
155 assert_true(HashMapGet(hashmap, s) == NULL);
156 }
157 }
158
test_grow(void)159 static void test_grow(void)
160 {
161 unsigned int i = 0;
162 HashMap *hashmap = HashMapNew(StringHash_untyped, StringEqual_untyped,
163 free, free, HASH_MAP_INIT_SIZE);
164
165 size_t orig_size = hashmap->size;
166 size_t orig_threshold = hashmap->max_threshold;
167
168 for (i = 1; i <= orig_threshold; i++)
169 {
170 test_add_n_as_to_map(hashmap, i);
171 assert_int_equal(hashmap->load, i);
172 }
173 // HashMapPrintStats(hashmap, stdout);
174 assert_int_equal(hashmap->size, orig_size);
175 assert_int_equal(hashmap->max_threshold, orig_threshold);
176
177 /* i == (orig_threshold + 1) now
178 * let's go over the threshold
179 */
180 test_add_n_as_to_map(hashmap, i);
181 assert_int_equal(hashmap->load, i);
182 assert_int_equal(hashmap->size, orig_size << 1);
183 assert_int_equal(hashmap->max_threshold,
184 (size_t) (hashmap->size * HASH_MAP_MAX_LOAD_FACTOR));
185
186 /* all the items so far should be in the map */
187 for (int j = 1; j <= i; j++)
188 {
189 assert_n_as_in_map(hashmap, j, true);
190 }
191
192
193 /* here we go again */
194 orig_size = hashmap->size;
195 orig_threshold = hashmap->max_threshold;
196 /* i * 'a' is in the map already, we need to bump it first */
197 for (++i; i <= orig_threshold; i++)
198 {
199 test_add_n_as_to_map(hashmap, i);
200 assert_int_equal(hashmap->load, i);
201 }
202 // HashMapPrintStats(hashmap, stdout);
203 assert_int_equal(hashmap->size, orig_size);
204 assert_int_equal(hashmap->max_threshold, orig_threshold);
205
206 /* i == (orig_threshold + 1) now
207 * let's go over the threshold
208 */
209 test_add_n_as_to_map(hashmap, i);
210 assert_int_equal(hashmap->load, i);
211 assert_int_equal(hashmap->size, orig_size << 1);
212 assert_int_equal(hashmap->max_threshold,
213 (size_t) (hashmap->size * HASH_MAP_MAX_LOAD_FACTOR));
214
215 /* all the items so far should be in the map */
216 for (int j = 1; j <= i; j++)
217 {
218 assert_n_as_in_map(hashmap, j, true);
219 }
220
221
222 /* and once more */
223 orig_size = hashmap->size;
224 orig_threshold = hashmap->max_threshold;
225 /* i * 'a' is in the map already, we need to bump it first */
226 for (++i; i <= orig_threshold; i++)
227 {
228 test_add_n_as_to_map(hashmap, i);
229 assert_int_equal(hashmap->load, i);
230 }
231 // HashMapPrintStats(hashmap, stdout);
232 assert_int_equal(hashmap->size, orig_size);
233 assert_int_equal(hashmap->max_threshold, orig_threshold);
234
235 /* i == (orig_threshold + 1) now
236 * let's go over the threshold
237 */
238 test_add_n_as_to_map(hashmap, i);
239 assert_int_equal(hashmap->load, i);
240 assert_int_equal(hashmap->size, orig_size << 1);
241 assert_int_equal(hashmap->max_threshold,
242 (size_t) (hashmap->size * HASH_MAP_MAX_LOAD_FACTOR));
243
244 /* all the items so far should be in the map */
245 for (int j = 1; j <= i; j++)
246 {
247 assert_n_as_in_map(hashmap, j, true);
248 }
249
250 HashMapDestroy(hashmap);
251 }
252
test_shrink(void)253 static void test_shrink(void)
254 {
255 unsigned int i = 0;
256 HashMap *hashmap = HashMapNew(StringHash_untyped, StringEqual_untyped,
257 free, free, HASH_MAP_INIT_SIZE);
258
259 size_t orig_size = hashmap->size;
260 size_t orig_threshold = hashmap->max_threshold;
261
262 /* let the map grow first (see test_grow above for some details */
263 for (i = 1; i <= orig_threshold; i++)
264 {
265 test_add_n_as_to_map(hashmap, i);
266 }
267 assert_int_equal(hashmap->size, orig_size);
268 assert_int_equal(hashmap->max_threshold, orig_threshold);
269 test_add_n_as_to_map(hashmap, i);
270 assert_int_equal(hashmap->load, i);
271 assert_int_equal(hashmap->size, orig_size << 1);
272 assert_int_equal(hashmap->max_threshold,
273 (size_t) (hashmap->size * HASH_MAP_MAX_LOAD_FACTOR));
274
275 /* all the items so far should be in the map */
276 for (int j = 1; j <= i; j++)
277 {
278 assert_n_as_in_map(hashmap, j, true);
279 }
280
281
282 /* now start removing things from the map */
283 size_t min_threshold = hashmap->min_threshold;
284 orig_size = hashmap->size;
285
286 /* 'i' is the length of the longest one already inserted */
287 for (; i > min_threshold; i--)
288 {
289 test_remove_n_as_from_map(hashmap, i);
290 assert_int_equal(hashmap->load, i - 1);
291 }
292 assert_int_equal(hashmap->load, hashmap->min_threshold);
293 assert_int_equal(hashmap->size, orig_size);
294 assert_int_equal(hashmap->min_threshold, min_threshold);
295
296 /* let's move over the threshold */
297 test_remove_n_as_from_map(hashmap, i);
298 assert_int_equal(hashmap->load, i - 1);
299 assert_int_equal(hashmap->size, orig_size >> 1);
300 assert_int_equal(hashmap->min_threshold,
301 (size_t) (hashmap->size * HASH_MAP_MIN_LOAD_FACTOR));
302
303 /* all the non-removed items should still be in the map */
304 for (int j = 1; j < i; j++)
305 {
306 assert_n_as_in_map(hashmap, j, true);
307 }
308
309 HashMapDestroy(hashmap);
310 }
311
test_no_shrink_below_init_size(void)312 static void test_no_shrink_below_init_size(void)
313 {
314 HashMap *hashmap = HashMapNew(StringHash_untyped, StringEqual_untyped,
315 free, free, HASH_MAP_INIT_SIZE);
316
317 assert_int_equal(hashmap->size, HASH_MAP_INIT_SIZE);
318 assert_int_equal(hashmap->init_size, HASH_MAP_INIT_SIZE);
319
320 /* add and remove 'aaaaa' to/from the HashMap
321 *
322 * The remove could trigger the shrink mechanism because there are obviously
323 * less than HASH_MAP_MIN_LOAD_FACTOR * HASH_MAP_INIT_SIZE items in the
324 * map. But the 'init_size' should block that from happening.
325 */
326 test_add_n_as_to_map(hashmap, 5);
327 test_remove_n_as_from_map(hashmap, 5);
328
329 assert_int_equal(hashmap->size, HASH_MAP_INIT_SIZE);
330
331 HashMapDestroy(hashmap);
332 }
333
test_get(void)334 static void test_get(void)
335 {
336 StringMap *map = StringMapNew();
337
338 assert_false(StringMapInsert(map, xstrdup("one"), xstrdup("first")));
339 assert_string_equal(StringMapGet(map, "one"), "first");
340 assert_int_equal(StringMapGet(map, "two"), NULL);
341
342 StringMapDestroy(map);
343 }
344
test_has_key(void)345 static void test_has_key(void)
346 {
347 StringMap *map = StringMapNew();
348
349 assert_false(StringMapInsert(map, xstrdup("one"), xstrdup("first")));
350 assert_true(StringMapHasKey(map, "one"));
351
352 StringMapDestroy(map);
353 }
354
test_clear(void)355 static void test_clear(void)
356 {
357 StringMap *map = StringMapNew();
358
359 assert_false(StringMapInsert(map, xstrdup("one"), xstrdup("first")));
360 assert_true(StringMapHasKey(map, "one"));
361
362 StringMapClear(map);
363 assert_false(StringMapHasKey(map, "one"));
364
365 StringMapDestroy(map);
366 }
367
test_clear_hashmap(void)368 static void test_clear_hashmap(void)
369 {
370 HashMap *map = HashMapNew(StringHash_untyped, StringEqual_untyped,
371 free, free, HASH_MAP_INIT_SIZE);
372
373 assert_false(HashMapInsert(map, xstrdup("one"), xstrdup("first")));
374 assert_false(HashMapInsert(map, xstrdup("two"), xstrdup("second")));
375
376 assert_true(HashMapGet(map, "one") != NULL);
377 assert_true(HashMapGet(map, "two") != NULL);
378 assert_int_equal(map->load, 2);
379
380 HashMapClear(map);
381 assert_true(HashMapGet(map, "one") == NULL);
382 assert_true(HashMapGet(map, "two") == NULL);
383 assert_int_equal(map->load, 0);
384
385
386 /* make sure that inserting items after clear doesn't trigger growth */
387 unsigned int i = 0;
388
389 /* first populate the hashmap just below the threshold */
390 size_t orig_size = map->size;
391 size_t orig_threshold = map->max_threshold;
392
393 for (i = 1; i <= orig_threshold; i++)
394 {
395 test_add_n_as_to_map(map, i);
396 assert_int_equal(map->load, i);
397 }
398 assert_int_equal(map->size, orig_size);
399 assert_int_equal(map->max_threshold, orig_threshold);
400
401 /* clear and repopulate again */
402 HashMapClear(map);
403 for (i = 1; i <= orig_threshold; i++)
404 {
405 test_add_n_as_to_map(map, i);
406 assert_int_equal(map->load, i);
407 }
408
409 /* the map was cleared before re-population, there's no reason for it to
410 * grow */
411 assert_int_equal(map->size, orig_size);
412 assert_int_equal(map->max_threshold, orig_threshold);
413
414 HashMapDestroy(map);
415 }
416
test_soft_destroy(void)417 static void test_soft_destroy(void)
418 {
419 StringMap *map = StringMapNew();
420
421 char *key = xstrdup("one");
422 char *value = xstrdup("first");
423
424 assert_false(StringMapInsert(map, key, value));
425 assert_true(StringMapHasKey(map, "one"));
426 assert_string_equal(StringMapGet(map, "one"),"first");
427
428 StringMapSoftDestroy(map);
429
430 assert_string_equal("first", value);
431 free(value);
432 }
433
test_iterate_jumbo(void)434 static void test_iterate_jumbo(void)
435 {
436 size_t size = StringMapSize(jumbo_map);
437
438 MapIterator it = MapIteratorInit(jumbo_map->impl);
439 MapKeyValue *item = NULL;
440 int count = 0;
441 int sum_len = 0;
442 while ((item = MapIteratorNext(&it)))
443 {
444 int key_len = strlen(item->key);
445 int value_len = strlen(item->value);
446 assert_int_equal(key_len, value_len);
447
448 sum_len += key_len;
449 count++;
450 }
451 assert_int_equal(count, 10000);
452 assert_int_equal(count, size);
453 assert_int_equal(sum_len, 10000*9999/2);
454 }
455
456 #ifndef _AIX
test_insert_jumbo_more(void)457 static void test_insert_jumbo_more(void)
458 {
459 for (int i = 1; i < 10000; i++)
460 {
461 /* char *s = CharTimes('x', i); */
462 char s[i+1];
463 memset(s, 'x', i);
464 s[i] = '\0';
465
466 assert_false(StringMapHasKey(jumbo_map, s));
467 assert_false(StringMapInsert(jumbo_map, xstrdup(s), xstrdup(s)));
468 assert_true(StringMapHasKey(jumbo_map, s));
469 /* free(s); */
470 }
471
472 for (int i = 1; i < 7500; i++)
473 {
474 /* char *s = CharTimes('y', i); */
475 char s[i+1];
476 memset(s, 'y', i);
477 s[i] = '\0';
478
479 assert_false(StringMapHasKey(jumbo_map, s));
480 assert_false(StringMapInsert(jumbo_map, xstrdup(s), xstrdup(s)));
481 assert_true(StringMapHasKey(jumbo_map, s));
482 /* free(s); */
483 }
484
485 StringMapPrintStats(jumbo_map, stdout);
486
487 /* TODO: maybe we need a GetStats() function so that we can actually verify
488 the stats here automatically? */
489
490 StringMapDestroy(jumbo_map);
491 };
492 #endif
493
test_hashmap_new_destroy(void)494 static void test_hashmap_new_destroy(void)
495 {
496 HashMap *hashmap = HashMapNew(NULL, NULL, NULL, NULL, HASH_MAP_INIT_SIZE);
497 HashMapDestroy(hashmap);
498 }
499
test_hashmap_degenerate_hash_fn(void)500 static void test_hashmap_degenerate_hash_fn(void)
501 {
502 HashMap *hashmap = HashMapNew(ConstHash, StringEqual_untyped, free, free, HASH_MAP_INIT_SIZE);
503
504 for (int i = 0; i < 100; i++)
505 {
506 assert_false(HashMapInsert(hashmap, CharTimes('a', i), CharTimes('a', i)));
507 }
508
509 MapKeyValue *item = HashMapGet(hashmap, "aaaa");
510 assert_string_equal(item->key, "aaaa");
511 assert_string_equal(item->value, "aaaa");
512
513 HashMapRemove(hashmap, "aaaa");
514 assert_int_equal(HashMapGet(hashmap, "aaaa"), NULL);
515
516 HashMapDestroy(hashmap);
517 }
518
519 #define ARRAY_STRING_KEY(last_char) {'k', 'e', 'y', last_char, '\0'}
520 #define ARRAY_STRING_VALUE(last_char) {'v', 'a', 'l', 'u', 'e', last_char, '\0'}
521
522 /**
523 * @brief Return pointer to heap allocated string constructed as
524 * "keyX" where X is last_char.
525 */
MallocStringKey(char last_char)526 static char *MallocStringKey(char last_char)
527 {
528 return xstrdup((char[]) ARRAY_STRING_KEY(last_char));
529 }
530
531 /**
532 * @brief Return pointer to heap allocated string constructed as
533 * "valueX" where X is last_char.
534 */
MallocStringValue(char last_char)535 static char *MallocStringValue(char last_char)
536 {
537 return xstrdup((char[]) ARRAY_STRING_VALUE(last_char));
538 }
539
test_array_map_insert(void)540 static void test_array_map_insert(void)
541 {
542 ArrayMap *m = ArrayMapNew(StringEqual_untyped, free, free);
543
544 // Test simple insertion
545 for (int i = 0; i < 3; ++i)
546 {
547 char* k = MallocStringKey('A' + i);
548 char* v = MallocStringValue('A' + i);
549 assert_int_equal(ArrayMapInsert(m, k, v), 2);
550 }
551
552 assert_int_equal(m->size, 3);
553
554 // Test replacing
555 for (int i = 0; i < 3; ++i)
556 {
557 char* k = MallocStringKey('A' + i);
558 char* v = MallocStringKey('0' + i);
559 assert_int_equal(ArrayMapInsert(m, k, v), 1);
560 }
561
562 assert_int_equal(m->size, 3);
563
564 // Fill array up to size 14
565 for (int i = 0; i < 14 - 3; ++i)
566 {
567 ArrayMapInsert(m, MallocStringKey('a' + i), MallocStringValue('a' + i));
568 }
569
570 assert_int_equal(m->size, 14);
571
572 // Test (no) insertion for size > 14
573 for (int i = 0; i < 3; ++i)
574 {
575 char* k = MallocStringKey('\0');
576 char* v = MallocStringValue('\0');
577 assert_int_equal(ArrayMapInsert(m, k, v), 0);
578 free(k);
579 free(v);
580 }
581
582 ArrayMapDestroy(m);
583 }
584
test_array_map_get(void)585 void test_array_map_get(void)
586 {
587 ArrayMap *m = ArrayMapNew(StringEqual_untyped, free, free);
588
589 // Fill with some test strings
590 for (int i = 0; i < 5; ++i)
591 {
592 char *k = MallocStringKey('A' + i);
593 char *v = MallocStringValue('A' + i);
594 assert_int_equal(ArrayMapInsert(m, k, v), 2);
595 }
596
597 // Get all the test strings
598 for (int i = 0; i < 5; ++i)
599 {
600 char k[] = ARRAY_STRING_KEY('A' + i);
601 MapKeyValue *pair = ArrayMapGet(m, k);
602 assert_true(pair != NULL);
603 assert_string_equal(pair->key, (char[]) ARRAY_STRING_KEY('A' + i));
604 assert_string_equal(pair->value, (char[]) ARRAY_STRING_VALUE('A' + i));
605 }
606
607 // Get non existent keys
608 for (int i = 0; i < 5; ++i)
609 {
610 char k[] = ARRAY_STRING_KEY('a' + i);
611 MapKeyValue *pair = ArrayMapGet(m, k);
612 assert_true(pair == NULL);
613 }
614
615 ArrayMapDestroy(m);
616 }
617
test_array_map_remove(void)618 static void test_array_map_remove(void)
619 {
620 ArrayMap *m = ArrayMapNew(StringEqual_untyped, free, free);
621
622 // Fill with some test strings
623 for (int i = 0; i < 5; ++i)
624 {
625 char *k = MallocStringKey('A' + i);
626 char *v = MallocStringValue('A' + i);
627 assert_int_equal(ArrayMapInsert(m, k, v), 2);
628 }
629
630 // Remove all keys one by one in reverse order
631 for (int i = 4; i >= 0; --i)
632 {
633 char k[] = ARRAY_STRING_KEY('A' + 4 - i);
634 assert_true(ArrayMapRemove(m, k));
635 assert_true(ArrayMapGet(m, k) == NULL);
636 }
637
638 // Try to remove non existent keys
639 for (int i = 0; i < 5; ++i)
640 {
641 char k[] = ARRAY_STRING_KEY('A' + i);
642 assert_false(ArrayMapRemove(m, k));
643 }
644
645 ArrayMapDestroy(m);
646 }
647
test_array_map_soft_destroy(void)648 static void test_array_map_soft_destroy(void)
649 {
650 ArrayMap *m = ArrayMapNew(StringEqual_untyped, free, free);
651
652 // Generate some pairs and keep track of values
653 char *values[5];
654
655 for (int i = 0; i < 5; ++i)
656 {
657 char *k = MallocStringKey('A' + i);
658 char *v = MallocStringValue('A' + i);
659 values[i] = v;
660 assert_int_equal(ArrayMapInsert(m, k, v), 2);
661 }
662
663 // Soft destroy and free them manually (should not double free)
664 // DEV: perhaps too... much?
665 ArrayMapSoftDestroy(m);
666
667 for (int i = 0; i < 5; ++i)
668 {
669 free(values[i]);
670 }
671 }
672
673 /* A special struct for *Value* in the Map, that references the Key. */
674 typedef struct
675 {
676 char *keyref; /* pointer to the key */
677 int val; /* arbitrary value */
678 } TestValue;
679
680 /* This tests that in case we insert a pre-existing key, so that the value
681 * gets replaced, the key also gets replaced despite being the same so that
682 * any references in the new value are not invalid. */
test_array_map_key_referenced_in_value(void)683 static void test_array_map_key_referenced_in_value(void)
684 {
685 ArrayMap *m = ArrayMapNew(StringEqual_untyped, free, free);
686
687 char *key1 = xstrdup("blah");
688 TestValue *val1 = xmalloc(sizeof(*val1));
689 val1->keyref = key1;
690 val1->val = 1;
691
692 /* Return value of 2 means: new value was inserted. */
693 assert_int_equal(ArrayMapInsert(m, key1, val1), 2);
694
695 /* Now we insert the same key, so that it replaces the value. */
696
697 char *key2 = xstrdup("blah"); /* same key string */
698 TestValue *val2 = xmalloc(sizeof(*val2));
699 val2->keyref = key2;
700 val2->val = 2;
701
702 /* Return value of 1 means: key preexisted, old data is replaced. */
703 assert_int_equal(ArrayMapInsert(m, key2, val2), 1);
704
705 /* And now the important bit: make sure that both "key" and "val->key" are
706 * the same pointer. */
707 /* WARNING: key1 and val1 must have been freed, but there is no way to
708 * test that. */
709 {
710 MapKeyValue *keyval = ArrayMapGet(m, key2);
711 assert_true(keyval != NULL);
712 char *key = keyval->key;
713 TestValue *val = keyval->value;
714 assert_true(val->keyref == key);
715 assert_int_equal(val->val, 2);
716 /* Valgrind will barf on the next line if the key has freed by
717 * mistake. */
718 assert_true(strcmp(val->keyref, "blah") == 0);
719 /* A bit irrelevant: make sure that using "blah" in the lookup yields
720 * the same results, as the string is the same as in key2. */
721 MapKeyValue *keyval2 = ArrayMapGet(m, "blah");
722 assert_true(keyval2 == keyval);
723 }
724
725 ArrayMapDestroy(m);
726 }
727
test_array_map_iterator(void)728 static void test_array_map_iterator(void)
729 {
730 ArrayMap *m = ArrayMapNew(StringEqual_untyped, free, free);
731
732 // Fill with some test strings
733 for (int i = 0; i < 5; ++i)
734 {
735 char *k = MallocStringKey('A' + i);
736 char *v = MallocStringValue('A' + i);
737 assert_int_equal(ArrayMapInsert(m, k, v), 2);
738 }
739
740 // Consume iterator
741 ArrayMapIterator iter = ArrayMapIteratorInit(m);
742 assert_true(iter.map == m);
743
744 for (int i = 0; i < 5; ++i)
745 {
746 char k[] = ARRAY_STRING_KEY('A' + i);
747 char v[] = ARRAY_STRING_VALUE('A' + i);
748 MapKeyValue *pair = ArrayMapIteratorNext(&iter);
749 assert_true(pair != NULL);
750 assert_string_equal(pair->key, k);
751 assert_string_equal(pair->value, v);
752 }
753
754 // Consumed iterator should return NULL
755 for (int i = 0; i < 5; ++i)
756 {
757 assert_true(ArrayMapIteratorNext(&iter) == NULL);
758 }
759
760 ArrayMapDestroy(m);
761 }
762
763 /* Same purpose as the above test. */
test_hash_map_key_referenced_in_value(void)764 static void test_hash_map_key_referenced_in_value(void)
765 {
766 HashMap *m = HashMapNew(StringHash_untyped, StringEqual_untyped,
767 free, free, HASH_MAP_INIT_SIZE);
768 char *key1 = xstrdup("blah");
769 TestValue *val1 = xmalloc(sizeof(*val1));
770 val1->keyref = key1;
771 val1->val = 1;
772
773 /* Return value false means: new value was inserted. */
774 assert_false(HashMapInsert(m, key1, val1));
775
776 /* Now we insert the same key, so that it replaces the value. */
777
778 char *key2 = xstrdup("blah"); /* same key string */
779 TestValue *val2 = xmalloc(sizeof(*val2));
780 val2->keyref = key2;
781 val2->val = 2;
782
783 /* Return value true means: key preexisted, old data is replaced. */
784 assert_true(HashMapInsert(m, key2, val2));
785
786 /* And now the important bit: make sure that both "key" and "val->key" are
787 * the same pointer. */
788 /* WARNING: key1 and val1 must have been freed, but there is no way to
789 * test that. */
790 {
791 MapKeyValue *keyval = HashMapGet(m, key2);
792 assert_true(keyval != NULL);
793 char *key = keyval->key;
794 TestValue *val = keyval->value;
795 assert_true(val->keyref == key); /* THIS IS WHAT IT'S ALL ABOUT! */
796 assert_int_equal(val->val, 2);
797 /* Valgrind will barf on the next line if the key has freed by
798 * mistake. */
799 assert_true(strcmp(val->keyref, "blah") == 0);
800 /* A bit irrelevant: make sure that using "blah" in the lookup yields
801 * the same results, as the string is the same as in key2. */
802 MapKeyValue *keyval2 = HashMapGet(m, "blah");
803 assert_true(keyval2 == keyval);
804 }
805
806 HashMapDestroy(m);
807 }
808
809
main()810 int main()
811 {
812 PRINT_TEST_BANNER();
813 const UnitTest tests[] =
814 {
815 unit_test(test_new_destroy),
816 unit_test(test_new_hashmap_bad_size),
817 unit_test(test_insert),
818 unit_test(test_insert_jumbo),
819 unit_test(test_remove),
820 unit_test(test_grow),
821 unit_test(test_shrink),
822 unit_test(test_no_shrink_below_init_size),
823 unit_test(test_get),
824 unit_test(test_has_key),
825 unit_test(test_clear),
826 unit_test(test_clear_hashmap),
827 unit_test(test_soft_destroy),
828 unit_test(test_hashmap_new_destroy),
829 unit_test(test_hashmap_degenerate_hash_fn),
830 unit_test(test_array_map_insert),
831 unit_test(test_array_map_get),
832 unit_test(test_array_map_remove),
833 unit_test(test_array_map_soft_destroy),
834 unit_test(test_array_map_key_referenced_in_value),
835 unit_test(test_array_map_iterator),
836 unit_test(test_hash_map_key_referenced_in_value),
837 unit_test(test_iterate_jumbo),
838 #ifndef _AIX
839 unit_test(test_insert_jumbo_more),
840 #endif
841 };
842
843 return run_tests(tests);
844 }
845