2 This file is part of systemd
4 Copyright 2013 Daniel Buch
6 systemd is free software; you can redistribute it and/or modify it
7 under the terms of the GNU Lesser General Public License as published by
8 the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version.
11 systemd is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public License
17 along with systemd; If not, see <http://www.gnu.org/licenses/>.
24 void test_hashmap_funcs(void);
26 static void test_hashmap_replace(void) {
28 char *val1, *val2, *val3, *val4, *val5, *r;
30 m = hashmap_new(&string_hash_ops);
32 val1 = strdup("val1");
34 val2 = strdup("val2");
36 val3 = strdup("val3");
38 val4 = strdup("val4");
40 val5 = strdup("val5");
43 hashmap_put(m, "key 1", val1);
44 hashmap_put(m, "key 2", val2);
45 hashmap_put(m, "key 3", val3);
46 hashmap_put(m, "key 4", val4);
48 hashmap_replace(m, "key 3", val1);
49 r = hashmap_get(m, "key 3");
50 assert_se(streq(r, "val1"));
52 hashmap_replace(m, "key 5", val5);
53 r = hashmap_get(m, "key 5");
54 assert_se(streq(r, "val5"));
64 static void test_hashmap_copy(void) {
66 char *val1, *val2, *val3, *val4, *r;
68 val1 = strdup("val1");
70 val2 = strdup("val2");
72 val3 = strdup("val3");
74 val4 = strdup("val4");
77 m = hashmap_new(&string_hash_ops);
79 hashmap_put(m, "key 1", val1);
80 hashmap_put(m, "key 2", val2);
81 hashmap_put(m, "key 3", val3);
82 hashmap_put(m, "key 4", val4);
84 copy = hashmap_copy(m);
86 r = hashmap_get(copy, "key 1");
87 assert_se(streq(r, "val1"));
88 r = hashmap_get(copy, "key 2");
89 assert_se(streq(r, "val2"));
90 r = hashmap_get(copy, "key 3");
91 assert_se(streq(r, "val3"));
92 r = hashmap_get(copy, "key 4");
93 assert_se(streq(r, "val4"));
95 hashmap_free_free(copy);
99 static void test_hashmap_get_strv(void) {
102 char *val1, *val2, *val3, *val4;
104 val1 = strdup("val1");
106 val2 = strdup("val2");
108 val3 = strdup("val3");
110 val4 = strdup("val4");
113 m = hashmap_new(&string_hash_ops);
115 hashmap_put(m, "key 1", val1);
116 hashmap_put(m, "key 2", val2);
117 hashmap_put(m, "key 3", val3);
118 hashmap_put(m, "key 4", val4);
120 strv = hashmap_get_strv(m);
123 strv = strv_sort(strv);
126 assert_se(streq(strv[0], "val1"));
127 assert_se(streq(strv[1], "val2"));
128 assert_se(streq(strv[2], "val3"));
129 assert_se(streq(strv[3], "val4"));
136 static void test_hashmap_move_one(void) {
138 char *val1, *val2, *val3, *val4, *r;
140 val1 = strdup("val1");
142 val2 = strdup("val2");
144 val3 = strdup("val3");
146 val4 = strdup("val4");
149 m = hashmap_new(&string_hash_ops);
150 n = hashmap_new(&string_hash_ops);
152 hashmap_put(m, "key 1", val1);
153 hashmap_put(m, "key 2", val2);
154 hashmap_put(m, "key 3", val3);
155 hashmap_put(m, "key 4", val4);
157 assert_se(hashmap_move_one(n, NULL, "key 3") == -ENOENT);
158 assert_se(hashmap_move_one(n, m, "key 5") == -ENOENT);
159 assert_se(hashmap_move_one(n, m, "key 3") == 0);
160 assert_se(hashmap_move_one(n, m, "key 4") == 0);
162 r = hashmap_get(n, "key 3");
163 assert_se(r && streq(r, "val3"));
164 r = hashmap_get(n, "key 4");
165 assert_se(r && streq(r, "val4"));
166 r = hashmap_get(m, "key 3");
169 assert_se(hashmap_move_one(n, m, "key 3") == -EEXIST);
171 hashmap_free_free(m);
172 hashmap_free_free(n);
175 static void test_hashmap_move(void) {
177 char *val1, *val2, *val3, *val4, *r;
179 val1 = strdup("val1");
181 val2 = strdup("val2");
183 val3 = strdup("val3");
185 val4 = strdup("val4");
188 m = hashmap_new(&string_hash_ops);
189 n = hashmap_new(&string_hash_ops);
191 hashmap_put(n, "key 1", strdup(val1));
192 hashmap_put(m, "key 1", val1);
193 hashmap_put(m, "key 2", val2);
194 hashmap_put(m, "key 3", val3);
195 hashmap_put(m, "key 4", val4);
197 assert_se(hashmap_move(n, NULL) == 0);
198 assert_se(hashmap_move(n, m) == 0);
200 assert_se(hashmap_size(m) == 1);
201 r = hashmap_get(m, "key 1");
202 assert_se(r && streq(r, "val1"));
204 r = hashmap_get(n, "key 1");
205 assert_se(r && streq(r, "val1"));
206 r = hashmap_get(n, "key 2");
207 assert_se(r && streq(r, "val2"));
208 r = hashmap_get(n, "key 3");
209 assert_se(r && streq(r, "val3"));
210 r = hashmap_get(n, "key 4");
211 assert_se(r && streq(r, "val4"));
213 hashmap_free_free(m);
214 hashmap_free_free(n);
217 static void test_hashmap_update(void) {
219 char *val1, *val2, *r;
221 m = hashmap_new(&string_hash_ops);
222 val1 = strdup("old_value");
224 val2 = strdup("new_value");
227 hashmap_put(m, "key 1", val1);
228 r = hashmap_get(m, "key 1");
229 assert_se(streq(r, "old_value"));
231 assert_se(hashmap_update(m, "key 2", val2) == -ENOENT);
232 r = hashmap_get(m, "key 1");
233 assert_se(streq(r, "old_value"));
235 assert_se(hashmap_update(m, "key 1", val2) == 0);
236 r = hashmap_get(m, "key 1");
237 assert_se(streq(r, "new_value"));
244 static void test_hashmap_put(void) {
246 int valid_hashmap_put;
247 void *val1 = (void*) "val 1";
249 assert_se(hashmap_ensure_allocated(&m, &string_hash_ops) >= 0);
252 valid_hashmap_put = hashmap_put(m, "key 1", val1);
253 assert_se(valid_hashmap_put == 1);
254 assert_se(hashmap_put(m, "key 1", val1) == 0);
255 assert_se(hashmap_put(m, "key 1", (void *)"val 2") == -EEXIST);
260 static void test_hashmap_remove(void) {
261 _cleanup_hashmap_free_ Hashmap *m = NULL;
264 r = hashmap_remove(NULL, "key 1");
265 assert_se(r == NULL);
267 m = hashmap_new(&string_hash_ops);
270 r = hashmap_remove(m, "no such key");
271 assert_se(r == NULL);
273 hashmap_put(m, "key 1", (void*) "val 1");
274 hashmap_put(m, "key 2", (void*) "val 2");
276 r = hashmap_remove(m, "key 1");
277 assert_se(streq(r, "val 1"));
279 r = hashmap_get(m, "key 2");
280 assert_se(streq(r, "val 2"));
281 assert_se(!hashmap_get(m, "key 1"));
284 static void test_hashmap_remove2(void) {
285 _cleanup_hashmap_free_free_free_ Hashmap *m = NULL;
286 char key1[] = "key 1";
287 char key2[] = "key 2";
288 char val1[] = "val 1";
289 char val2[] = "val 2";
292 r = hashmap_remove2(NULL, "key 1", &r2);
293 assert_se(r == NULL);
295 m = hashmap_new(&string_hash_ops);
298 r = hashmap_remove2(m, "no such key", &r2);
299 assert_se(r == NULL);
301 hashmap_put(m, strdup(key1), strdup(val1));
302 hashmap_put(m, strdup(key2), strdup(val2));
304 r = hashmap_remove2(m, key1, &r2);
305 assert_se(streq(r, val1));
306 assert_se(streq(r2, key1));
310 r = hashmap_get(m, key2);
311 assert_se(streq(r, val2));
312 assert_se(!hashmap_get(m, key1));
315 static void test_hashmap_remove_value(void) {
316 _cleanup_hashmap_free_ Hashmap *m = NULL;
319 r = hashmap_remove_value(NULL, "key 1", (void*) "val 1");
320 assert_se(r == NULL);
322 m = hashmap_new(&string_hash_ops);
325 r = hashmap_remove_value(m, "key 1", (void*) "val 1");
326 assert_se(r == NULL);
328 hashmap_put(m, "key 1", (void*) "val 1");
329 hashmap_put(m, "key 2", (void*) "val 2");
331 r = hashmap_remove_value(m, "key 1", (void*) "val 1");
332 assert_se(streq(r, "val 1"));
334 r = hashmap_get(m, "key 2");
335 assert_se(streq(r, "val 2"));
336 assert_se(!hashmap_get(m, "key 1"));
338 r = hashmap_remove_value(m, "key 2", (void*) "val 1");
339 assert_se(r == NULL);
341 r = hashmap_get(m, "key 2");
342 assert_se(streq(r, "val 2"));
343 assert_se(!hashmap_get(m, "key 1"));
346 static void test_hashmap_remove_and_put(void) {
347 _cleanup_hashmap_free_ Hashmap *m = NULL;
351 m = hashmap_new(&string_hash_ops);
354 valid = hashmap_remove_and_put(m, "invalid key", "new key", NULL);
355 assert_se(valid == -ENOENT);
357 valid = hashmap_put(m, "key 1", (void*) (const char *) "val 1");
358 assert_se(valid == 1);
360 valid = hashmap_remove_and_put(NULL, "key 1", "key 2", (void*) (const char *) "val 2");
361 assert_se(valid == -ENOENT);
363 valid = hashmap_remove_and_put(m, "key 1", "key 2", (void*) (const char *) "val 2");
364 assert_se(valid == 0);
366 r = hashmap_get(m, "key 2");
367 assert_se(streq(r, "val 2"));
368 assert_se(!hashmap_get(m, "key 1"));
370 valid = hashmap_put(m, "key 3", (void*) (const char *) "val 3");
371 assert_se(valid == 1);
372 valid = hashmap_remove_and_put(m, "key 3", "key 2", (void*) (const char *) "val 2");
373 assert_se(valid == -EEXIST);
376 static void test_hashmap_remove_and_replace(void) {
377 _cleanup_hashmap_free_ Hashmap *m = NULL;
379 void *key1 = UINT_TO_PTR(1);
380 void *key2 = UINT_TO_PTR(2);
381 void *key3 = UINT_TO_PTR(3);
385 m = hashmap_new(&trivial_hash_ops);
388 valid = hashmap_remove_and_replace(m, key1, key2, NULL);
389 assert_se(valid == -ENOENT);
391 valid = hashmap_put(m, key1, key1);
392 assert_se(valid == 1);
394 valid = hashmap_remove_and_replace(NULL, key1, key2, key2);
395 assert_se(valid == -ENOENT);
397 valid = hashmap_remove_and_replace(m, key1, key2, key2);
398 assert_se(valid == 0);
400 r = hashmap_get(m, key2);
401 assert_se(r == key2);
402 assert_se(!hashmap_get(m, key1));
404 valid = hashmap_put(m, key3, key3);
405 assert_se(valid == 1);
406 valid = hashmap_remove_and_replace(m, key3, key2, key2);
407 assert_se(valid == 0);
408 r = hashmap_get(m, key2);
409 assert_se(r == key2);
410 assert_se(!hashmap_get(m, key3));
412 /* Repeat this test several times to increase the chance of hitting
413 * the less likely case in hashmap_remove_and_replace where it
414 * compensates for the backward shift. */
415 for (i = 0; i < 20; i++) {
418 for (j = 1; j < 7; j++)
419 hashmap_put(m, UINT_TO_PTR(10*i + j), UINT_TO_PTR(10*i + j));
420 valid = hashmap_remove_and_replace(m, UINT_TO_PTR(10*i + 1),
421 UINT_TO_PTR(10*i + 2),
422 UINT_TO_PTR(10*i + 2));
423 assert_se(valid == 0);
424 assert_se(!hashmap_get(m, UINT_TO_PTR(10*i + 1)));
425 for (j = 2; j < 7; j++) {
426 r = hashmap_get(m, UINT_TO_PTR(10*i + j));
427 assert_se(r == UINT_TO_PTR(10*i + j));
432 static void test_hashmap_ensure_allocated(void) {
436 m = hashmap_new(&string_hash_ops);
438 valid_hashmap = hashmap_ensure_allocated(&m, &string_hash_ops);
439 assert_se(valid_hashmap == 0);
445 static void test_hashmap_foreach_key(void) {
448 bool key_found[] = { false, false, false, false };
451 static const char key_table[] =
457 m = hashmap_new(&string_hash_ops);
459 NULSTR_FOREACH(key, key_table)
460 hashmap_put(m, key, (void*) (const char*) "my dummy val");
462 HASHMAP_FOREACH_KEY(s, key, m, i) {
463 if (!key_found[0] && streq(key, "key 1"))
465 else if (!key_found[1] && streq(key, "key 2"))
467 else if (!key_found[2] && streq(key, "key 3"))
469 else if (!key_found[3] && streq(key, "fail"))
474 assert_se(key_found[0] && key_found[1] && key_found[2] && !key_found[3]);
479 static void test_hashmap_foreach(void) {
482 bool value_found[] = { false, false, false, false };
483 char *val1, *val2, *val3, *val4, *s;
486 val1 = strdup("my val1");
488 val2 = strdup("my val2");
490 val3 = strdup("my val3");
492 val4 = strdup("my val4");
498 HASHMAP_FOREACH(s, m, i)
500 assert_se(count == 0);
502 m = hashmap_new(&string_hash_ops);
505 HASHMAP_FOREACH(s, m, i)
507 assert_se(count == 0);
509 hashmap_put(m, "Key 1", val1);
510 hashmap_put(m, "Key 2", val2);
511 hashmap_put(m, "Key 3", val3);
512 hashmap_put(m, "Key 4", val4);
514 HASHMAP_FOREACH(s, m, i) {
515 if (!value_found[0] && streq(s, val1))
516 value_found[0] = true;
517 else if (!value_found[1] && streq(s, val2))
518 value_found[1] = true;
519 else if (!value_found[2] && streq(s, val3))
520 value_found[2] = true;
521 else if (!value_found[3] && streq(s, val4))
522 value_found[3] = true;
526 assert_se(value_found[0] && value_found[1] && value_found[2] && value_found[3]);
528 hashmap_free_free(m);
531 static void test_hashmap_merge(void) {
534 char *val1, *val2, *val3, *val4, *r;
536 val1 = strdup("my val1");
538 val2 = strdup("my val2");
540 val3 = strdup("my val3");
542 val4 = strdup("my val4");
545 n = hashmap_new(&string_hash_ops);
546 m = hashmap_new(&string_hash_ops);
548 hashmap_put(m, "Key 1", val1);
549 hashmap_put(m, "Key 2", val2);
550 hashmap_put(n, "Key 3", val3);
551 hashmap_put(n, "Key 4", val4);
553 assert_se(hashmap_merge(m, n) == 0);
554 r = hashmap_get(m, "Key 3");
555 assert_se(r && streq(r, "my val3"));
556 r = hashmap_get(m, "Key 4");
557 assert_se(r && streq(r, "my val4"));
562 hashmap_free_free(m);
565 static void test_hashmap_contains(void) {
569 val1 = strdup("my val");
572 m = hashmap_new(&string_hash_ops);
574 assert_se(!hashmap_contains(m, "Key 1"));
575 hashmap_put(m, "Key 1", val1);
576 assert_se(hashmap_contains(m, "Key 1"));
577 assert_se(!hashmap_contains(m, "Key 2"));
579 assert_se(!hashmap_contains(NULL, "Key 1"));
582 hashmap_free_free(m);
585 static void test_hashmap_isempty(void) {
589 val1 = strdup("my val");
592 m = hashmap_new(&string_hash_ops);
594 assert_se(hashmap_isempty(m));
595 hashmap_put(m, "Key 1", val1);
596 assert_se(!hashmap_isempty(m));
599 hashmap_free_free(m);
602 static void test_hashmap_size(void) {
604 char *val1, *val2, *val3, *val4;
606 val1 = strdup("my val");
608 val2 = strdup("my val");
610 val3 = strdup("my val");
612 val4 = strdup("my val");
615 assert_se(hashmap_size(NULL) == 0);
616 assert_se(hashmap_buckets(NULL) == 0);
618 m = hashmap_new(&string_hash_ops);
620 hashmap_put(m, "Key 1", val1);
621 hashmap_put(m, "Key 2", val2);
622 hashmap_put(m, "Key 3", val3);
623 hashmap_put(m, "Key 4", val4);
626 assert_se(hashmap_size(m) == 4);
627 assert_se(hashmap_buckets(m) >= 4);
628 hashmap_free_free(m);
631 static void test_hashmap_get(void) {
636 val = strdup("my val");
639 r = hashmap_get(NULL, "Key 1");
640 assert_se(r == NULL);
642 m = hashmap_new(&string_hash_ops);
644 hashmap_put(m, "Key 1", val);
646 r = hashmap_get(m, "Key 1");
647 assert_se(streq(r, val));
649 r = hashmap_get(m, "no such key");
650 assert_se(r == NULL);
653 hashmap_free_free(m);
656 static void test_hashmap_get2(void) {
660 char key_orig[] = "Key 1";
663 val = strdup("my val");
666 key_copy = strdup(key_orig);
669 r = hashmap_get2(NULL, key_orig, &key_copy);
670 assert_se(r == NULL);
672 m = hashmap_new(&string_hash_ops);
674 hashmap_put(m, key_copy, val);
677 r = hashmap_get2(m, key_orig, &key_copy);
678 assert_se(streq(r, val));
679 assert_se(key_orig != key_copy);
680 assert_se(streq(key_orig, key_orig));
682 r = hashmap_get2(m, "no such key", NULL);
683 assert_se(r == NULL);
686 hashmap_free_free_free(m);
689 static unsigned long crippled_hashmap_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
690 return trivial_hash_func(p, hash_key) & 0xff;
693 static const struct hash_ops crippled_hashmap_ops = {
694 .hash = crippled_hashmap_func,
695 .compare = trivial_compare_func,
698 static void test_hashmap_many(void) {
702 static const struct {
703 const struct hash_ops *ops;
706 { .ops = NULL, .n_entries = 1 << 20 },
707 { .ops = &crippled_hashmap_ops, .n_entries = 1 << 11 },
711 for (j = 0; j < ELEMENTSOF(tests); j++) {
712 assert_se(h = hashmap_new(tests[j].ops));
714 for (i = 1; i < tests[j].n_entries*3; i+=3) {
715 assert_se(hashmap_put(h, UINT_TO_PTR(i), UINT_TO_PTR(i)) >= 0);
716 assert_se(PTR_TO_UINT(hashmap_get(h, UINT_TO_PTR(i))) == i);
719 for (i = 1; i < tests[j].n_entries*3; i++)
720 assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1));
722 log_info("%u <= %u * 0.8 = %g", hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.8);
724 assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.8);
725 assert_se(hashmap_size(h) == tests[j].n_entries);
727 while (!hashmap_isempty(h)) {
728 k = hashmap_first_key(h);
729 v = hashmap_remove(h, k);
737 static void test_hashmap_first(void) {
738 _cleanup_hashmap_free_ Hashmap *m = NULL;
740 m = hashmap_new(&string_hash_ops);
743 assert_se(!hashmap_first(m));
744 assert_se(hashmap_put(m, "key 1", (void*) "val 1") == 1);
745 assert_se(streq(hashmap_first(m), "val 1"));
746 assert_se(hashmap_put(m, "key 2", (void*) "val 2") == 1);
748 assert_se(streq(hashmap_first(m), "val 1"));
749 assert_se(hashmap_remove(m, "key 1"));
750 assert_se(streq(hashmap_first(m), "val 2"));
754 static void test_hashmap_first_key(void) {
755 _cleanup_hashmap_free_ Hashmap *m = NULL;
757 m = hashmap_new(&string_hash_ops);
760 assert_se(!hashmap_first_key(m));
761 assert_se(hashmap_put(m, "key 1", NULL) == 1);
762 assert_se(streq(hashmap_first_key(m), "key 1"));
763 assert_se(hashmap_put(m, "key 2", NULL) == 1);
765 assert_se(streq(hashmap_first_key(m), "key 1"));
766 assert_se(hashmap_remove(m, "key 1") == NULL);
767 assert_se(streq(hashmap_first_key(m), "key 2"));
771 static void test_hashmap_steal_first_key(void) {
772 _cleanup_hashmap_free_ Hashmap *m = NULL;
774 m = hashmap_new(&string_hash_ops);
777 assert_se(!hashmap_steal_first_key(m));
778 assert_se(hashmap_put(m, "key 1", NULL) == 1);
779 assert_se(streq(hashmap_steal_first_key(m), "key 1"));
781 assert_se(hashmap_isempty(m));
784 static void test_hashmap_steal_first(void) {
785 _cleanup_hashmap_free_ Hashmap *m = NULL;
789 m = hashmap_new(&string_hash_ops);
792 assert_se(hashmap_put(m, "key 1", (void*) "1") == 1);
793 assert_se(hashmap_put(m, "key 2", (void*) "22") == 1);
794 assert_se(hashmap_put(m, "key 3", (void*) "333") == 1);
796 while ((val = hashmap_steal_first(m)))
797 seen[strlen(val) - 1]++;
799 assert_se(seen[0] == 1 && seen[1] == 1 && seen[2] == 1);
801 assert_se(hashmap_isempty(m));
804 static void test_hashmap_clear_free_free(void) {
805 _cleanup_hashmap_free_ Hashmap *m = NULL;
807 m = hashmap_new(&string_hash_ops);
810 assert_se(hashmap_put(m, strdup("key 1"), NULL) == 1);
811 assert_se(hashmap_put(m, strdup("key 2"), NULL) == 1);
812 assert_se(hashmap_put(m, strdup("key 3"), NULL) == 1);
814 hashmap_clear_free_free(m);
815 assert_se(hashmap_isempty(m));
818 static void test_hashmap_reserve(void) {
819 _cleanup_hashmap_free_ Hashmap *m = NULL;
821 m = hashmap_new(&string_hash_ops);
823 assert_se(hashmap_reserve(m, 1) == 0);
824 assert_se(hashmap_buckets(m) < 1000);
825 assert_se(hashmap_reserve(m, 1000) == 0);
826 assert_se(hashmap_buckets(m) >= 1000);
827 assert_se(hashmap_isempty(m));
829 assert_se(hashmap_put(m, "key 1", (void*) "val 1") == 1);
831 assert_se(hashmap_reserve(m, UINT_MAX) == -ENOMEM);
832 assert_se(hashmap_reserve(m, UINT_MAX - 1) == -ENOMEM);
835 void test_hashmap_funcs(void) {
837 test_hashmap_get_strv();
838 test_hashmap_move_one();
840 test_hashmap_replace();
841 test_hashmap_update();
843 test_hashmap_remove();
844 test_hashmap_remove2();
845 test_hashmap_remove_value();
846 test_hashmap_remove_and_put();
847 test_hashmap_remove_and_replace();
848 test_hashmap_ensure_allocated();
849 test_hashmap_foreach();
850 test_hashmap_foreach_key();
851 test_hashmap_contains();
852 test_hashmap_merge();
853 test_hashmap_isempty();
858 test_hashmap_first();
859 test_hashmap_first_key();
860 test_hashmap_steal_first_key();
861 test_hashmap_steal_first();
862 test_hashmap_clear_free_free();
863 test_hashmap_reserve();