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";
248 void *val2 = (void*) "val 2";
249 _cleanup_free_ char* key1 = NULL;
251 assert_se(hashmap_ensure_allocated(&m, &string_hash_ops) >= 0);
254 valid_hashmap_put = hashmap_put(m, "key 1", val1);
255 assert_se(valid_hashmap_put == 1);
256 assert_se(hashmap_put(m, "key 1", val1) == 0);
257 assert_se(hashmap_put(m, "key 1", val2) == -EEXIST);
258 key1 = strdup("key 1");
259 assert_se(hashmap_put(m, key1, val1) == 0);
260 assert_se(hashmap_put(m, key1, val2) == -EEXIST);
265 static void test_hashmap_remove(void) {
266 _cleanup_hashmap_free_ Hashmap *m = NULL;
269 r = hashmap_remove(NULL, "key 1");
270 assert_se(r == NULL);
272 m = hashmap_new(&string_hash_ops);
275 r = hashmap_remove(m, "no such key");
276 assert_se(r == NULL);
278 hashmap_put(m, "key 1", (void*) "val 1");
279 hashmap_put(m, "key 2", (void*) "val 2");
281 r = hashmap_remove(m, "key 1");
282 assert_se(streq(r, "val 1"));
284 r = hashmap_get(m, "key 2");
285 assert_se(streq(r, "val 2"));
286 assert_se(!hashmap_get(m, "key 1"));
289 static void test_hashmap_remove2(void) {
290 _cleanup_hashmap_free_free_free_ Hashmap *m = NULL;
291 char key1[] = "key 1";
292 char key2[] = "key 2";
293 char val1[] = "val 1";
294 char val2[] = "val 2";
297 r = hashmap_remove2(NULL, "key 1", &r2);
298 assert_se(r == NULL);
300 m = hashmap_new(&string_hash_ops);
303 r = hashmap_remove2(m, "no such key", &r2);
304 assert_se(r == NULL);
306 hashmap_put(m, strdup(key1), strdup(val1));
307 hashmap_put(m, strdup(key2), strdup(val2));
309 r = hashmap_remove2(m, key1, &r2);
310 assert_se(streq(r, val1));
311 assert_se(streq(r2, key1));
315 r = hashmap_get(m, key2);
316 assert_se(streq(r, val2));
317 assert_se(!hashmap_get(m, key1));
320 static void test_hashmap_remove_value(void) {
321 _cleanup_hashmap_free_ Hashmap *m = NULL;
324 r = hashmap_remove_value(NULL, "key 1", (void*) "val 1");
325 assert_se(r == NULL);
327 m = hashmap_new(&string_hash_ops);
330 r = hashmap_remove_value(m, "key 1", (void*) "val 1");
331 assert_se(r == NULL);
333 hashmap_put(m, "key 1", (void*) "val 1");
334 hashmap_put(m, "key 2", (void*) "val 2");
336 r = hashmap_remove_value(m, "key 1", (void*) "val 1");
337 assert_se(streq(r, "val 1"));
339 r = hashmap_get(m, "key 2");
340 assert_se(streq(r, "val 2"));
341 assert_se(!hashmap_get(m, "key 1"));
343 r = hashmap_remove_value(m, "key 2", (void*) "val 1");
344 assert_se(r == NULL);
346 r = hashmap_get(m, "key 2");
347 assert_se(streq(r, "val 2"));
348 assert_se(!hashmap_get(m, "key 1"));
351 static void test_hashmap_remove_and_put(void) {
352 _cleanup_hashmap_free_ Hashmap *m = NULL;
356 m = hashmap_new(&string_hash_ops);
359 valid = hashmap_remove_and_put(m, "invalid key", "new key", NULL);
360 assert_se(valid == -ENOENT);
362 valid = hashmap_put(m, "key 1", (void*) (const char *) "val 1");
363 assert_se(valid == 1);
365 valid = hashmap_remove_and_put(NULL, "key 1", "key 2", (void*) (const char *) "val 2");
366 assert_se(valid == -ENOENT);
368 valid = hashmap_remove_and_put(m, "key 1", "key 2", (void*) (const char *) "val 2");
369 assert_se(valid == 0);
371 r = hashmap_get(m, "key 2");
372 assert_se(streq(r, "val 2"));
373 assert_se(!hashmap_get(m, "key 1"));
375 valid = hashmap_put(m, "key 3", (void*) (const char *) "val 3");
376 assert_se(valid == 1);
377 valid = hashmap_remove_and_put(m, "key 3", "key 2", (void*) (const char *) "val 2");
378 assert_se(valid == -EEXIST);
381 static void test_hashmap_remove_and_replace(void) {
382 _cleanup_hashmap_free_ Hashmap *m = NULL;
384 void *key1 = UINT_TO_PTR(1);
385 void *key2 = UINT_TO_PTR(2);
386 void *key3 = UINT_TO_PTR(3);
390 m = hashmap_new(&trivial_hash_ops);
393 valid = hashmap_remove_and_replace(m, key1, key2, NULL);
394 assert_se(valid == -ENOENT);
396 valid = hashmap_put(m, key1, key1);
397 assert_se(valid == 1);
399 valid = hashmap_remove_and_replace(NULL, key1, key2, key2);
400 assert_se(valid == -ENOENT);
402 valid = hashmap_remove_and_replace(m, key1, key2, key2);
403 assert_se(valid == 0);
405 r = hashmap_get(m, key2);
406 assert_se(r == key2);
407 assert_se(!hashmap_get(m, key1));
409 valid = hashmap_put(m, key3, key3);
410 assert_se(valid == 1);
411 valid = hashmap_remove_and_replace(m, key3, key2, key2);
412 assert_se(valid == 0);
413 r = hashmap_get(m, key2);
414 assert_se(r == key2);
415 assert_se(!hashmap_get(m, key3));
417 /* Repeat this test several times to increase the chance of hitting
418 * the less likely case in hashmap_remove_and_replace where it
419 * compensates for the backward shift. */
420 for (i = 0; i < 20; i++) {
423 for (j = 1; j < 7; j++)
424 hashmap_put(m, UINT_TO_PTR(10*i + j), UINT_TO_PTR(10*i + j));
425 valid = hashmap_remove_and_replace(m, UINT_TO_PTR(10*i + 1),
426 UINT_TO_PTR(10*i + 2),
427 UINT_TO_PTR(10*i + 2));
428 assert_se(valid == 0);
429 assert_se(!hashmap_get(m, UINT_TO_PTR(10*i + 1)));
430 for (j = 2; j < 7; j++) {
431 r = hashmap_get(m, UINT_TO_PTR(10*i + j));
432 assert_se(r == UINT_TO_PTR(10*i + j));
437 static void test_hashmap_ensure_allocated(void) {
441 m = hashmap_new(&string_hash_ops);
443 valid_hashmap = hashmap_ensure_allocated(&m, &string_hash_ops);
444 assert_se(valid_hashmap == 0);
450 static void test_hashmap_foreach_key(void) {
453 bool key_found[] = { false, false, false, false };
456 static const char key_table[] =
462 m = hashmap_new(&string_hash_ops);
464 NULSTR_FOREACH(key, key_table)
465 hashmap_put(m, key, (void*) (const char*) "my dummy val");
467 HASHMAP_FOREACH_KEY(s, key, m, i) {
468 if (!key_found[0] && streq(key, "key 1"))
470 else if (!key_found[1] && streq(key, "key 2"))
472 else if (!key_found[2] && streq(key, "key 3"))
474 else if (!key_found[3] && streq(key, "fail"))
479 assert_se(key_found[0] && key_found[1] && key_found[2] && !key_found[3]);
484 static void test_hashmap_foreach(void) {
487 bool value_found[] = { false, false, false, false };
488 char *val1, *val2, *val3, *val4, *s;
491 val1 = strdup("my val1");
493 val2 = strdup("my val2");
495 val3 = strdup("my val3");
497 val4 = strdup("my val4");
503 HASHMAP_FOREACH(s, m, i)
505 assert_se(count == 0);
507 m = hashmap_new(&string_hash_ops);
510 HASHMAP_FOREACH(s, m, i)
512 assert_se(count == 0);
514 hashmap_put(m, "Key 1", val1);
515 hashmap_put(m, "Key 2", val2);
516 hashmap_put(m, "Key 3", val3);
517 hashmap_put(m, "Key 4", val4);
519 HASHMAP_FOREACH(s, m, i) {
520 if (!value_found[0] && streq(s, val1))
521 value_found[0] = true;
522 else if (!value_found[1] && streq(s, val2))
523 value_found[1] = true;
524 else if (!value_found[2] && streq(s, val3))
525 value_found[2] = true;
526 else if (!value_found[3] && streq(s, val4))
527 value_found[3] = true;
531 assert_se(value_found[0] && value_found[1] && value_found[2] && value_found[3]);
533 hashmap_free_free(m);
536 static void test_hashmap_merge(void) {
539 char *val1, *val2, *val3, *val4, *r;
541 val1 = strdup("my val1");
543 val2 = strdup("my val2");
545 val3 = strdup("my val3");
547 val4 = strdup("my val4");
550 n = hashmap_new(&string_hash_ops);
551 m = hashmap_new(&string_hash_ops);
553 hashmap_put(m, "Key 1", val1);
554 hashmap_put(m, "Key 2", val2);
555 hashmap_put(n, "Key 3", val3);
556 hashmap_put(n, "Key 4", val4);
558 assert_se(hashmap_merge(m, n) == 0);
559 r = hashmap_get(m, "Key 3");
560 assert_se(r && streq(r, "my val3"));
561 r = hashmap_get(m, "Key 4");
562 assert_se(r && streq(r, "my val4"));
567 hashmap_free_free(m);
570 static void test_hashmap_contains(void) {
574 val1 = strdup("my val");
577 m = hashmap_new(&string_hash_ops);
579 assert_se(!hashmap_contains(m, "Key 1"));
580 hashmap_put(m, "Key 1", val1);
581 assert_se(hashmap_contains(m, "Key 1"));
582 assert_se(!hashmap_contains(m, "Key 2"));
584 assert_se(!hashmap_contains(NULL, "Key 1"));
587 hashmap_free_free(m);
590 static void test_hashmap_isempty(void) {
594 val1 = strdup("my val");
597 m = hashmap_new(&string_hash_ops);
599 assert_se(hashmap_isempty(m));
600 hashmap_put(m, "Key 1", val1);
601 assert_se(!hashmap_isempty(m));
604 hashmap_free_free(m);
607 static void test_hashmap_size(void) {
609 char *val1, *val2, *val3, *val4;
611 val1 = strdup("my val");
613 val2 = strdup("my val");
615 val3 = strdup("my val");
617 val4 = strdup("my val");
620 assert_se(hashmap_size(NULL) == 0);
621 assert_se(hashmap_buckets(NULL) == 0);
623 m = hashmap_new(&string_hash_ops);
625 hashmap_put(m, "Key 1", val1);
626 hashmap_put(m, "Key 2", val2);
627 hashmap_put(m, "Key 3", val3);
628 hashmap_put(m, "Key 4", val4);
631 assert_se(hashmap_size(m) == 4);
632 assert_se(hashmap_buckets(m) >= 4);
633 hashmap_free_free(m);
636 static void test_hashmap_get(void) {
641 val = strdup("my val");
644 r = hashmap_get(NULL, "Key 1");
645 assert_se(r == NULL);
647 m = hashmap_new(&string_hash_ops);
649 hashmap_put(m, "Key 1", val);
651 r = hashmap_get(m, "Key 1");
652 assert_se(streq(r, val));
654 r = hashmap_get(m, "no such key");
655 assert_se(r == NULL);
658 hashmap_free_free(m);
661 static void test_hashmap_get2(void) {
665 char key_orig[] = "Key 1";
668 val = strdup("my val");
671 key_copy = strdup(key_orig);
674 r = hashmap_get2(NULL, key_orig, &key_copy);
675 assert_se(r == NULL);
677 m = hashmap_new(&string_hash_ops);
679 hashmap_put(m, key_copy, val);
682 r = hashmap_get2(m, key_orig, &key_copy);
683 assert_se(streq(r, val));
684 assert_se(key_orig != key_copy);
685 assert_se(streq(key_orig, key_orig));
687 r = hashmap_get2(m, "no such key", NULL);
688 assert_se(r == NULL);
691 hashmap_free_free_free(m);
694 static unsigned long crippled_hashmap_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
695 return trivial_hash_func(p, hash_key) & 0xff;
698 static const struct hash_ops crippled_hashmap_ops = {
699 .hash = crippled_hashmap_func,
700 .compare = trivial_compare_func,
703 static void test_hashmap_many(void) {
707 static const struct {
708 const struct hash_ops *ops;
711 { .ops = NULL, .n_entries = 1 << 20 },
712 { .ops = &crippled_hashmap_ops, .n_entries = 1 << 11 },
716 for (j = 0; j < ELEMENTSOF(tests); j++) {
717 assert_se(h = hashmap_new(tests[j].ops));
719 for (i = 1; i < tests[j].n_entries*3; i+=3) {
720 assert_se(hashmap_put(h, UINT_TO_PTR(i), UINT_TO_PTR(i)) >= 0);
721 assert_se(PTR_TO_UINT(hashmap_get(h, UINT_TO_PTR(i))) == i);
724 for (i = 1; i < tests[j].n_entries*3; i++)
725 assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1));
727 log_info("%u <= %u * 0.8 = %g", hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.8);
729 assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.8);
730 assert_se(hashmap_size(h) == tests[j].n_entries);
732 while (!hashmap_isempty(h)) {
733 k = hashmap_first_key(h);
734 v = hashmap_remove(h, k);
742 static void test_hashmap_first(void) {
743 _cleanup_hashmap_free_ Hashmap *m = NULL;
745 m = hashmap_new(&string_hash_ops);
748 assert_se(!hashmap_first(m));
749 assert_se(hashmap_put(m, "key 1", (void*) "val 1") == 1);
750 assert_se(streq(hashmap_first(m), "val 1"));
751 assert_se(hashmap_put(m, "key 2", (void*) "val 2") == 1);
753 assert_se(streq(hashmap_first(m), "val 1"));
754 assert_se(hashmap_remove(m, "key 1"));
755 assert_se(streq(hashmap_first(m), "val 2"));
759 static void test_hashmap_first_key(void) {
760 _cleanup_hashmap_free_ Hashmap *m = NULL;
762 m = hashmap_new(&string_hash_ops);
765 assert_se(!hashmap_first_key(m));
766 assert_se(hashmap_put(m, "key 1", NULL) == 1);
767 assert_se(streq(hashmap_first_key(m), "key 1"));
768 assert_se(hashmap_put(m, "key 2", NULL) == 1);
770 assert_se(streq(hashmap_first_key(m), "key 1"));
771 assert_se(hashmap_remove(m, "key 1") == NULL);
772 assert_se(streq(hashmap_first_key(m), "key 2"));
776 static void test_hashmap_steal_first_key(void) {
777 _cleanup_hashmap_free_ Hashmap *m = NULL;
779 m = hashmap_new(&string_hash_ops);
782 assert_se(!hashmap_steal_first_key(m));
783 assert_se(hashmap_put(m, "key 1", NULL) == 1);
784 assert_se(streq(hashmap_steal_first_key(m), "key 1"));
786 assert_se(hashmap_isempty(m));
789 static void test_hashmap_steal_first(void) {
790 _cleanup_hashmap_free_ Hashmap *m = NULL;
794 m = hashmap_new(&string_hash_ops);
797 assert_se(hashmap_put(m, "key 1", (void*) "1") == 1);
798 assert_se(hashmap_put(m, "key 2", (void*) "22") == 1);
799 assert_se(hashmap_put(m, "key 3", (void*) "333") == 1);
801 while ((val = hashmap_steal_first(m)))
802 seen[strlen(val) - 1]++;
804 assert_se(seen[0] == 1 && seen[1] == 1 && seen[2] == 1);
806 assert_se(hashmap_isempty(m));
809 static void test_hashmap_clear_free_free(void) {
810 _cleanup_hashmap_free_ Hashmap *m = NULL;
812 m = hashmap_new(&string_hash_ops);
815 assert_se(hashmap_put(m, strdup("key 1"), NULL) == 1);
816 assert_se(hashmap_put(m, strdup("key 2"), NULL) == 1);
817 assert_se(hashmap_put(m, strdup("key 3"), NULL) == 1);
819 hashmap_clear_free_free(m);
820 assert_se(hashmap_isempty(m));
823 static void test_hashmap_reserve(void) {
824 _cleanup_hashmap_free_ Hashmap *m = NULL;
826 m = hashmap_new(&string_hash_ops);
828 assert_se(hashmap_reserve(m, 1) == 0);
829 assert_se(hashmap_buckets(m) < 1000);
830 assert_se(hashmap_reserve(m, 1000) == 0);
831 assert_se(hashmap_buckets(m) >= 1000);
832 assert_se(hashmap_isempty(m));
834 assert_se(hashmap_put(m, "key 1", (void*) "val 1") == 1);
836 assert_se(hashmap_reserve(m, UINT_MAX) == -ENOMEM);
837 assert_se(hashmap_reserve(m, UINT_MAX - 1) == -ENOMEM);
840 void test_hashmap_funcs(void) {
842 test_hashmap_get_strv();
843 test_hashmap_move_one();
845 test_hashmap_replace();
846 test_hashmap_update();
848 test_hashmap_remove();
849 test_hashmap_remove2();
850 test_hashmap_remove_value();
851 test_hashmap_remove_and_put();
852 test_hashmap_remove_and_replace();
853 test_hashmap_ensure_allocated();
854 test_hashmap_foreach();
855 test_hashmap_foreach_key();
856 test_hashmap_contains();
857 test_hashmap_merge();
858 test_hashmap_isempty();
863 test_hashmap_first();
864 test_hashmap_first_key();
865 test_hashmap_steal_first_key();
866 test_hashmap_steal_first();
867 test_hashmap_clear_free_free();
868 test_hashmap_reserve();