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/>.
20 #include "alloc-util.h"
22 #include "string-util.h"
26 void test_hashmap_funcs(void);
28 static void test_hashmap_replace(void) {
30 char *val1, *val2, *val3, *val4, *val5, *r;
32 m = hashmap_new(&string_hash_ops);
34 val1 = strdup("val1");
36 val2 = strdup("val2");
38 val3 = strdup("val3");
40 val4 = strdup("val4");
42 val5 = strdup("val5");
45 hashmap_put(m, "key 1", val1);
46 hashmap_put(m, "key 2", val2);
47 hashmap_put(m, "key 3", val3);
48 hashmap_put(m, "key 4", val4);
50 hashmap_replace(m, "key 3", val1);
51 r = hashmap_get(m, "key 3");
52 assert_se(streq(r, "val1"));
54 hashmap_replace(m, "key 5", val5);
55 r = hashmap_get(m, "key 5");
56 assert_se(streq(r, "val5"));
66 static void test_hashmap_copy(void) {
68 char *val1, *val2, *val3, *val4, *r;
70 val1 = strdup("val1");
72 val2 = strdup("val2");
74 val3 = strdup("val3");
76 val4 = strdup("val4");
79 m = hashmap_new(&string_hash_ops);
81 hashmap_put(m, "key 1", val1);
82 hashmap_put(m, "key 2", val2);
83 hashmap_put(m, "key 3", val3);
84 hashmap_put(m, "key 4", val4);
86 copy = hashmap_copy(m);
88 r = hashmap_get(copy, "key 1");
89 assert_se(streq(r, "val1"));
90 r = hashmap_get(copy, "key 2");
91 assert_se(streq(r, "val2"));
92 r = hashmap_get(copy, "key 3");
93 assert_se(streq(r, "val3"));
94 r = hashmap_get(copy, "key 4");
95 assert_se(streq(r, "val4"));
97 hashmap_free_free(copy);
101 static void test_hashmap_get_strv(void) {
104 char *val1, *val2, *val3, *val4;
106 val1 = strdup("val1");
108 val2 = strdup("val2");
110 val3 = strdup("val3");
112 val4 = strdup("val4");
115 m = hashmap_new(&string_hash_ops);
117 hashmap_put(m, "key 1", val1);
118 hashmap_put(m, "key 2", val2);
119 hashmap_put(m, "key 3", val3);
120 hashmap_put(m, "key 4", val4);
122 strv = hashmap_get_strv(m);
125 strv = strv_sort(strv);
128 assert_se(streq(strv[0], "val1"));
129 assert_se(streq(strv[1], "val2"));
130 assert_se(streq(strv[2], "val3"));
131 assert_se(streq(strv[3], "val4"));
138 static void test_hashmap_move_one(void) {
140 char *val1, *val2, *val3, *val4, *r;
142 val1 = strdup("val1");
144 val2 = strdup("val2");
146 val3 = strdup("val3");
148 val4 = strdup("val4");
151 m = hashmap_new(&string_hash_ops);
152 n = hashmap_new(&string_hash_ops);
154 hashmap_put(m, "key 1", val1);
155 hashmap_put(m, "key 2", val2);
156 hashmap_put(m, "key 3", val3);
157 hashmap_put(m, "key 4", val4);
159 assert_se(hashmap_move_one(n, NULL, "key 3") == -ENOENT);
160 assert_se(hashmap_move_one(n, m, "key 5") == -ENOENT);
161 assert_se(hashmap_move_one(n, m, "key 3") == 0);
162 assert_se(hashmap_move_one(n, m, "key 4") == 0);
164 r = hashmap_get(n, "key 3");
165 assert_se(r && streq(r, "val3"));
166 r = hashmap_get(n, "key 4");
167 assert_se(r && streq(r, "val4"));
168 r = hashmap_get(m, "key 3");
171 assert_se(hashmap_move_one(n, m, "key 3") == -EEXIST);
173 hashmap_free_free(m);
174 hashmap_free_free(n);
177 static void test_hashmap_move(void) {
179 char *val1, *val2, *val3, *val4, *r;
181 val1 = strdup("val1");
183 val2 = strdup("val2");
185 val3 = strdup("val3");
187 val4 = strdup("val4");
190 m = hashmap_new(&string_hash_ops);
191 n = hashmap_new(&string_hash_ops);
193 hashmap_put(n, "key 1", strdup(val1));
194 hashmap_put(m, "key 1", val1);
195 hashmap_put(m, "key 2", val2);
196 hashmap_put(m, "key 3", val3);
197 hashmap_put(m, "key 4", val4);
199 assert_se(hashmap_move(n, NULL) == 0);
200 assert_se(hashmap_move(n, m) == 0);
202 assert_se(hashmap_size(m) == 1);
203 r = hashmap_get(m, "key 1");
204 assert_se(r && streq(r, "val1"));
206 r = hashmap_get(n, "key 1");
207 assert_se(r && streq(r, "val1"));
208 r = hashmap_get(n, "key 2");
209 assert_se(r && streq(r, "val2"));
210 r = hashmap_get(n, "key 3");
211 assert_se(r && streq(r, "val3"));
212 r = hashmap_get(n, "key 4");
213 assert_se(r && streq(r, "val4"));
215 hashmap_free_free(m);
216 hashmap_free_free(n);
219 static void test_hashmap_update(void) {
221 char *val1, *val2, *r;
223 m = hashmap_new(&string_hash_ops);
224 val1 = strdup("old_value");
226 val2 = strdup("new_value");
229 hashmap_put(m, "key 1", val1);
230 r = hashmap_get(m, "key 1");
231 assert_se(streq(r, "old_value"));
233 assert_se(hashmap_update(m, "key 2", val2) == -ENOENT);
234 r = hashmap_get(m, "key 1");
235 assert_se(streq(r, "old_value"));
237 assert_se(hashmap_update(m, "key 1", val2) == 0);
238 r = hashmap_get(m, "key 1");
239 assert_se(streq(r, "new_value"));
246 static void test_hashmap_put(void) {
248 int valid_hashmap_put;
249 void *val1 = (void*) "val 1";
250 void *val2 = (void*) "val 2";
251 _cleanup_free_ char* key1 = NULL;
253 assert_se(hashmap_ensure_allocated(&m, &string_hash_ops) >= 0);
256 valid_hashmap_put = hashmap_put(m, "key 1", val1);
257 assert_se(valid_hashmap_put == 1);
258 assert_se(hashmap_put(m, "key 1", val1) == 0);
259 assert_se(hashmap_put(m, "key 1", val2) == -EEXIST);
260 key1 = strdup("key 1");
261 assert_se(hashmap_put(m, key1, val1) == 0);
262 assert_se(hashmap_put(m, key1, val2) == -EEXIST);
267 static void test_hashmap_remove(void) {
268 _cleanup_hashmap_free_ Hashmap *m = NULL;
271 r = hashmap_remove(NULL, "key 1");
272 assert_se(r == NULL);
274 m = hashmap_new(&string_hash_ops);
277 r = hashmap_remove(m, "no such key");
278 assert_se(r == NULL);
280 hashmap_put(m, "key 1", (void*) "val 1");
281 hashmap_put(m, "key 2", (void*) "val 2");
283 r = hashmap_remove(m, "key 1");
284 assert_se(streq(r, "val 1"));
286 r = hashmap_get(m, "key 2");
287 assert_se(streq(r, "val 2"));
288 assert_se(!hashmap_get(m, "key 1"));
291 static void test_hashmap_remove2(void) {
292 _cleanup_hashmap_free_free_free_ Hashmap *m = NULL;
293 char key1[] = "key 1";
294 char key2[] = "key 2";
295 char val1[] = "val 1";
296 char val2[] = "val 2";
299 r = hashmap_remove2(NULL, "key 1", &r2);
300 assert_se(r == NULL);
302 m = hashmap_new(&string_hash_ops);
305 r = hashmap_remove2(m, "no such key", &r2);
306 assert_se(r == NULL);
308 hashmap_put(m, strdup(key1), strdup(val1));
309 hashmap_put(m, strdup(key2), strdup(val2));
311 r = hashmap_remove2(m, key1, &r2);
312 assert_se(streq(r, val1));
313 assert_se(streq(r2, key1));
317 r = hashmap_get(m, key2);
318 assert_se(streq(r, val2));
319 assert_se(!hashmap_get(m, key1));
322 static void test_hashmap_remove_value(void) {
323 _cleanup_hashmap_free_ Hashmap *m = NULL;
326 char val1[] = "val 1";
327 char val2[] = "val 2";
329 r = hashmap_remove_value(NULL, "key 1", val1);
330 assert_se(r == NULL);
332 m = hashmap_new(&string_hash_ops);
335 r = hashmap_remove_value(m, "key 1", val1);
336 assert_se(r == NULL);
338 hashmap_put(m, "key 1", val1);
339 hashmap_put(m, "key 2", val2);
341 r = hashmap_remove_value(m, "key 1", val1);
342 assert_se(streq(r, "val 1"));
344 r = hashmap_get(m, "key 2");
345 assert_se(streq(r, "val 2"));
346 assert_se(!hashmap_get(m, "key 1"));
348 r = hashmap_remove_value(m, "key 2", val1);
349 assert_se(r == NULL);
351 r = hashmap_get(m, "key 2");
352 assert_se(streq(r, "val 2"));
353 assert_se(!hashmap_get(m, "key 1"));
356 static void test_hashmap_remove_and_put(void) {
357 _cleanup_hashmap_free_ Hashmap *m = NULL;
361 m = hashmap_new(&string_hash_ops);
364 valid = hashmap_remove_and_put(m, "invalid key", "new key", NULL);
365 assert_se(valid == -ENOENT);
367 valid = hashmap_put(m, "key 1", (void*) (const char *) "val 1");
368 assert_se(valid == 1);
370 valid = hashmap_remove_and_put(NULL, "key 1", "key 2", (void*) (const char *) "val 2");
371 assert_se(valid == -ENOENT);
373 valid = hashmap_remove_and_put(m, "key 1", "key 2", (void*) (const char *) "val 2");
374 assert_se(valid == 0);
376 r = hashmap_get(m, "key 2");
377 assert_se(streq(r, "val 2"));
378 assert_se(!hashmap_get(m, "key 1"));
380 valid = hashmap_put(m, "key 3", (void*) (const char *) "val 3");
381 assert_se(valid == 1);
382 valid = hashmap_remove_and_put(m, "key 3", "key 2", (void*) (const char *) "val 2");
383 assert_se(valid == -EEXIST);
386 static void test_hashmap_remove_and_replace(void) {
387 _cleanup_hashmap_free_ Hashmap *m = NULL;
389 void *key1 = UINT_TO_PTR(1);
390 void *key2 = UINT_TO_PTR(2);
391 void *key3 = UINT_TO_PTR(3);
395 m = hashmap_new(&trivial_hash_ops);
398 valid = hashmap_remove_and_replace(m, key1, key2, NULL);
399 assert_se(valid == -ENOENT);
401 valid = hashmap_put(m, key1, key1);
402 assert_se(valid == 1);
404 valid = hashmap_remove_and_replace(NULL, key1, key2, key2);
405 assert_se(valid == -ENOENT);
407 valid = hashmap_remove_and_replace(m, key1, key2, key2);
408 assert_se(valid == 0);
410 r = hashmap_get(m, key2);
411 assert_se(r == key2);
412 assert_se(!hashmap_get(m, key1));
414 valid = hashmap_put(m, key3, key3);
415 assert_se(valid == 1);
416 valid = hashmap_remove_and_replace(m, key3, key2, key2);
417 assert_se(valid == 0);
418 r = hashmap_get(m, key2);
419 assert_se(r == key2);
420 assert_se(!hashmap_get(m, key3));
422 /* Repeat this test several times to increase the chance of hitting
423 * the less likely case in hashmap_remove_and_replace where it
424 * compensates for the backward shift. */
425 for (i = 0; i < 20; i++) {
428 for (j = 1; j < 7; j++)
429 hashmap_put(m, UINT_TO_PTR(10*i + j), UINT_TO_PTR(10*i + j));
430 valid = hashmap_remove_and_replace(m, UINT_TO_PTR(10*i + 1),
431 UINT_TO_PTR(10*i + 2),
432 UINT_TO_PTR(10*i + 2));
433 assert_se(valid == 0);
434 assert_se(!hashmap_get(m, UINT_TO_PTR(10*i + 1)));
435 for (j = 2; j < 7; j++) {
436 r = hashmap_get(m, UINT_TO_PTR(10*i + j));
437 assert_se(r == UINT_TO_PTR(10*i + j));
442 static void test_hashmap_ensure_allocated(void) {
446 m = hashmap_new(&string_hash_ops);
448 valid_hashmap = hashmap_ensure_allocated(&m, &string_hash_ops);
449 assert_se(valid_hashmap == 0);
455 static void test_hashmap_foreach_key(void) {
458 bool key_found[] = { false, false, false, false };
461 static const char key_table[] =
467 m = hashmap_new(&string_hash_ops);
469 NULSTR_FOREACH(key, key_table)
470 hashmap_put(m, key, (void*) (const char*) "my dummy val");
472 HASHMAP_FOREACH_KEY(s, key, m, i) {
474 if (!key_found[0] && streq(key, "key 1"))
476 else if (!key_found[1] && streq(key, "key 2"))
478 else if (!key_found[2] && streq(key, "key 3"))
480 else if (!key_found[3] && streq(key, "fail"))
485 assert_se(key_found[0] && key_found[1] && key_found[2] && !key_found[3]);
490 static void test_hashmap_foreach(void) {
493 bool value_found[] = { false, false, false, false };
494 char *val1, *val2, *val3, *val4, *s;
497 val1 = strdup("my val1");
499 val2 = strdup("my val2");
501 val3 = strdup("my val3");
503 val4 = strdup("my val4");
509 HASHMAP_FOREACH(s, m, i)
511 assert_se(count == 0);
513 m = hashmap_new(&string_hash_ops);
516 HASHMAP_FOREACH(s, m, i)
518 assert_se(count == 0);
520 hashmap_put(m, "Key 1", val1);
521 hashmap_put(m, "Key 2", val2);
522 hashmap_put(m, "Key 3", val3);
523 hashmap_put(m, "Key 4", val4);
525 HASHMAP_FOREACH(s, m, i) {
526 if (!value_found[0] && streq(s, val1))
527 value_found[0] = true;
528 else if (!value_found[1] && streq(s, val2))
529 value_found[1] = true;
530 else if (!value_found[2] && streq(s, val3))
531 value_found[2] = true;
532 else if (!value_found[3] && streq(s, val4))
533 value_found[3] = true;
537 assert_se(value_found[0] && value_found[1] && value_found[2] && value_found[3]);
539 hashmap_free_free(m);
542 static void test_hashmap_merge(void) {
545 char *val1, *val2, *val3, *val4, *r;
547 val1 = strdup("my val1");
549 val2 = strdup("my val2");
551 val3 = strdup("my val3");
553 val4 = strdup("my val4");
556 n = hashmap_new(&string_hash_ops);
557 m = hashmap_new(&string_hash_ops);
559 hashmap_put(m, "Key 1", val1);
560 hashmap_put(m, "Key 2", val2);
561 hashmap_put(n, "Key 3", val3);
562 hashmap_put(n, "Key 4", val4);
564 assert_se(hashmap_merge(m, n) == 0);
565 r = hashmap_get(m, "Key 3");
566 assert_se(r && streq(r, "my val3"));
567 r = hashmap_get(m, "Key 4");
568 assert_se(r && streq(r, "my val4"));
573 hashmap_free_free(m);
576 static void test_hashmap_contains(void) {
580 val1 = strdup("my val");
583 m = hashmap_new(&string_hash_ops);
585 assert_se(!hashmap_contains(m, "Key 1"));
586 hashmap_put(m, "Key 1", val1);
587 assert_se(hashmap_contains(m, "Key 1"));
588 assert_se(!hashmap_contains(m, "Key 2"));
590 assert_se(!hashmap_contains(NULL, "Key 1"));
593 hashmap_free_free(m);
596 static void test_hashmap_isempty(void) {
600 val1 = strdup("my val");
603 m = hashmap_new(&string_hash_ops);
605 assert_se(hashmap_isempty(m));
606 hashmap_put(m, "Key 1", val1);
607 assert_se(!hashmap_isempty(m));
610 hashmap_free_free(m);
613 static void test_hashmap_size(void) {
615 char *val1, *val2, *val3, *val4;
617 val1 = strdup("my val");
619 val2 = strdup("my val");
621 val3 = strdup("my val");
623 val4 = strdup("my val");
626 assert_se(hashmap_size(NULL) == 0);
627 assert_se(hashmap_buckets(NULL) == 0);
629 m = hashmap_new(&string_hash_ops);
631 hashmap_put(m, "Key 1", val1);
632 hashmap_put(m, "Key 2", val2);
633 hashmap_put(m, "Key 3", val3);
634 hashmap_put(m, "Key 4", val4);
637 assert_se(hashmap_size(m) == 4);
638 assert_se(hashmap_buckets(m) >= 4);
639 hashmap_free_free(m);
642 static void test_hashmap_get(void) {
647 val = strdup("my val");
650 r = hashmap_get(NULL, "Key 1");
651 assert_se(r == NULL);
653 m = hashmap_new(&string_hash_ops);
655 hashmap_put(m, "Key 1", val);
657 r = hashmap_get(m, "Key 1");
658 assert_se(streq(r, val));
660 r = hashmap_get(m, "no such key");
661 assert_se(r == NULL);
664 hashmap_free_free(m);
667 static void test_hashmap_get2(void) {
671 char key_orig[] = "Key 1";
674 val = strdup("my val");
677 key_copy = strdup(key_orig);
680 r = hashmap_get2(NULL, key_orig, &key_copy);
681 assert_se(r == NULL);
683 m = hashmap_new(&string_hash_ops);
685 hashmap_put(m, key_copy, val);
688 r = hashmap_get2(m, key_orig, &key_copy);
689 assert_se(streq(r, val));
690 assert_se(key_orig != key_copy);
691 assert_se(streq(key_orig, key_copy));
693 r = hashmap_get2(m, "no such key", NULL);
694 assert_se(r == NULL);
697 hashmap_free_free_free(m);
700 static void crippled_hashmap_func(const void *p, struct siphash *state) {
701 return trivial_hash_func(INT_TO_PTR(PTR_TO_INT(p) & 0xff), state);
704 static const struct hash_ops crippled_hashmap_ops = {
705 .hash = crippled_hashmap_func,
706 .compare = trivial_compare_func,
709 static void test_hashmap_many(void) {
713 static const struct {
714 const struct hash_ops *ops;
717 { .ops = NULL, .n_entries = 1 << 20 },
718 { .ops = &crippled_hashmap_ops, .n_entries = 1 << 14 },
722 for (j = 0; j < ELEMENTSOF(tests); j++) {
723 assert_se(h = hashmap_new(tests[j].ops));
725 for (i = 1; i < tests[j].n_entries*3; i+=3) {
726 assert_se(hashmap_put(h, UINT_TO_PTR(i), UINT_TO_PTR(i)) >= 0);
727 assert_se(PTR_TO_UINT(hashmap_get(h, UINT_TO_PTR(i))) == i);
730 for (i = 1; i < tests[j].n_entries*3; i++)
731 assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1));
733 log_info("%u <= %u * 0.8 = %g", hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.8);
735 assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.8);
736 assert_se(hashmap_size(h) == tests[j].n_entries);
738 while (!hashmap_isempty(h)) {
739 k = hashmap_first_key(h);
740 v = hashmap_remove(h, k);
748 static void test_hashmap_first(void) {
749 _cleanup_hashmap_free_ Hashmap *m = NULL;
751 m = hashmap_new(&string_hash_ops);
754 assert_se(!hashmap_first(m));
755 assert_se(hashmap_put(m, "key 1", (void*) "val 1") == 1);
756 assert_se(streq(hashmap_first(m), "val 1"));
757 assert_se(hashmap_put(m, "key 2", (void*) "val 2") == 1);
759 assert_se(streq(hashmap_first(m), "val 1"));
760 assert_se(hashmap_remove(m, "key 1"));
761 assert_se(streq(hashmap_first(m), "val 2"));
765 static void test_hashmap_first_key(void) {
766 _cleanup_hashmap_free_ Hashmap *m = NULL;
768 m = hashmap_new(&string_hash_ops);
771 assert_se(!hashmap_first_key(m));
772 assert_se(hashmap_put(m, "key 1", NULL) == 1);
773 assert_se(streq(hashmap_first_key(m), "key 1"));
774 assert_se(hashmap_put(m, "key 2", NULL) == 1);
776 assert_se(streq(hashmap_first_key(m), "key 1"));
777 assert_se(hashmap_remove(m, "key 1") == NULL);
778 assert_se(streq(hashmap_first_key(m), "key 2"));
782 static void test_hashmap_steal_first_key(void) {
783 _cleanup_hashmap_free_ Hashmap *m = NULL;
785 m = hashmap_new(&string_hash_ops);
788 assert_se(!hashmap_steal_first_key(m));
789 assert_se(hashmap_put(m, "key 1", NULL) == 1);
790 assert_se(streq(hashmap_steal_first_key(m), "key 1"));
792 assert_se(hashmap_isempty(m));
795 static void test_hashmap_steal_first(void) {
796 _cleanup_hashmap_free_ Hashmap *m = NULL;
800 m = hashmap_new(&string_hash_ops);
803 assert_se(hashmap_put(m, "key 1", (void*) "1") == 1);
804 assert_se(hashmap_put(m, "key 2", (void*) "22") == 1);
805 assert_se(hashmap_put(m, "key 3", (void*) "333") == 1);
807 while ((val = hashmap_steal_first(m)))
808 seen[strlen(val) - 1]++;
810 assert_se(seen[0] == 1 && seen[1] == 1 && seen[2] == 1);
812 assert_se(hashmap_isempty(m));
815 static void test_hashmap_clear_free_free(void) {
816 _cleanup_hashmap_free_ Hashmap *m = NULL;
818 m = hashmap_new(&string_hash_ops);
821 assert_se(hashmap_put(m, strdup("key 1"), NULL) == 1);
822 assert_se(hashmap_put(m, strdup("key 2"), NULL) == 1);
823 assert_se(hashmap_put(m, strdup("key 3"), NULL) == 1);
825 hashmap_clear_free_free(m);
826 assert_se(hashmap_isempty(m));
829 static void test_hashmap_reserve(void) {
830 _cleanup_hashmap_free_ Hashmap *m = NULL;
832 m = hashmap_new(&string_hash_ops);
834 assert_se(hashmap_reserve(m, 1) == 0);
835 assert_se(hashmap_buckets(m) < 1000);
836 assert_se(hashmap_reserve(m, 1000) == 0);
837 assert_se(hashmap_buckets(m) >= 1000);
838 assert_se(hashmap_isempty(m));
840 assert_se(hashmap_put(m, "key 1", (void*) "val 1") == 1);
842 assert_se(hashmap_reserve(m, UINT_MAX) == -ENOMEM);
843 assert_se(hashmap_reserve(m, UINT_MAX - 1) == -ENOMEM);
846 void test_hashmap_funcs(void) {
848 test_hashmap_get_strv();
849 test_hashmap_move_one();
851 test_hashmap_replace();
852 test_hashmap_update();
854 test_hashmap_remove();
855 test_hashmap_remove2();
856 test_hashmap_remove_value();
857 test_hashmap_remove_and_put();
858 test_hashmap_remove_and_replace();
859 test_hashmap_ensure_allocated();
860 test_hashmap_foreach();
861 test_hashmap_foreach_key();
862 test_hashmap_contains();
863 test_hashmap_merge();
864 test_hashmap_isempty();
869 test_hashmap_first();
870 test_hashmap_first_key();
871 test_hashmap_steal_first_key();
872 test_hashmap_steal_first();
873 test_hashmap_clear_free_free();
874 test_hashmap_reserve();