Line data Source code
1 : /* SPDX-License-Identifier: LGPL-2.1+ */
2 :
3 : #include "alloc-util.h"
4 : #include "hashmap.h"
5 : #include "log.h"
6 : #include "nulstr-util.h"
7 : #include "stdio-util.h"
8 : #include "string-util.h"
9 : #include "strv.h"
10 : #include "time-util.h"
11 : #include "tests.h"
12 :
13 : void test_hashmap_funcs(void);
14 :
15 1 : static void test_hashmap_replace(void) {
16 : Hashmap *m;
17 : char *val1, *val2, *val3, *val4, *val5, *r;
18 :
19 1 : log_info("/* %s */", __func__);
20 :
21 1 : m = hashmap_new(&string_hash_ops);
22 :
23 1 : val1 = strdup("val1");
24 1 : assert_se(val1);
25 1 : val2 = strdup("val2");
26 1 : assert_se(val2);
27 1 : val3 = strdup("val3");
28 1 : assert_se(val3);
29 1 : val4 = strdup("val4");
30 1 : assert_se(val4);
31 1 : val5 = strdup("val5");
32 1 : assert_se(val5);
33 :
34 1 : hashmap_put(m, "key 1", val1);
35 1 : hashmap_put(m, "key 2", val2);
36 1 : hashmap_put(m, "key 3", val3);
37 1 : hashmap_put(m, "key 4", val4);
38 :
39 1 : hashmap_replace(m, "key 3", val1);
40 1 : r = hashmap_get(m, "key 3");
41 1 : assert_se(streq(r, "val1"));
42 :
43 1 : hashmap_replace(m, "key 5", val5);
44 1 : r = hashmap_get(m, "key 5");
45 1 : assert_se(streq(r, "val5"));
46 :
47 1 : free(val1);
48 1 : free(val2);
49 1 : free(val3);
50 1 : free(val4);
51 1 : free(val5);
52 1 : hashmap_free(m);
53 1 : }
54 :
55 1 : static void test_hashmap_copy(void) {
56 : Hashmap *m, *copy;
57 : char *val1, *val2, *val3, *val4, *r;
58 :
59 1 : log_info("/* %s */", __func__);
60 :
61 1 : val1 = strdup("val1");
62 1 : assert_se(val1);
63 1 : val2 = strdup("val2");
64 1 : assert_se(val2);
65 1 : val3 = strdup("val3");
66 1 : assert_se(val3);
67 1 : val4 = strdup("val4");
68 1 : assert_se(val4);
69 :
70 1 : m = hashmap_new(&string_hash_ops);
71 :
72 1 : hashmap_put(m, "key 1", val1);
73 1 : hashmap_put(m, "key 2", val2);
74 1 : hashmap_put(m, "key 3", val3);
75 1 : hashmap_put(m, "key 4", val4);
76 :
77 1 : copy = hashmap_copy(m);
78 :
79 1 : r = hashmap_get(copy, "key 1");
80 1 : assert_se(streq(r, "val1"));
81 1 : r = hashmap_get(copy, "key 2");
82 1 : assert_se(streq(r, "val2"));
83 1 : r = hashmap_get(copy, "key 3");
84 1 : assert_se(streq(r, "val3"));
85 1 : r = hashmap_get(copy, "key 4");
86 1 : assert_se(streq(r, "val4"));
87 :
88 1 : hashmap_free_free(copy);
89 1 : hashmap_free(m);
90 1 : }
91 :
92 1 : static void test_hashmap_get_strv(void) {
93 : Hashmap *m;
94 : char **strv;
95 : char *val1, *val2, *val3, *val4;
96 :
97 1 : log_info("/* %s */", __func__);
98 :
99 1 : val1 = strdup("val1");
100 1 : assert_se(val1);
101 1 : val2 = strdup("val2");
102 1 : assert_se(val2);
103 1 : val3 = strdup("val3");
104 1 : assert_se(val3);
105 1 : val4 = strdup("val4");
106 1 : assert_se(val4);
107 :
108 1 : m = hashmap_new(&string_hash_ops);
109 :
110 1 : hashmap_put(m, "key 1", val1);
111 1 : hashmap_put(m, "key 2", val2);
112 1 : hashmap_put(m, "key 3", val3);
113 1 : hashmap_put(m, "key 4", val4);
114 :
115 1 : strv = hashmap_get_strv(m);
116 :
117 : #ifndef ORDERED
118 1 : strv = strv_sort(strv);
119 : #endif
120 :
121 1 : assert_se(streq(strv[0], "val1"));
122 1 : assert_se(streq(strv[1], "val2"));
123 1 : assert_se(streq(strv[2], "val3"));
124 1 : assert_se(streq(strv[3], "val4"));
125 :
126 1 : strv_free(strv);
127 :
128 1 : hashmap_free(m);
129 1 : }
130 :
131 1 : static void test_hashmap_move_one(void) {
132 : Hashmap *m, *n;
133 : char *val1, *val2, *val3, *val4, *r;
134 :
135 1 : log_info("/* %s */", __func__);
136 :
137 1 : val1 = strdup("val1");
138 1 : assert_se(val1);
139 1 : val2 = strdup("val2");
140 1 : assert_se(val2);
141 1 : val3 = strdup("val3");
142 1 : assert_se(val3);
143 1 : val4 = strdup("val4");
144 1 : assert_se(val4);
145 :
146 1 : m = hashmap_new(&string_hash_ops);
147 1 : n = hashmap_new(&string_hash_ops);
148 :
149 1 : hashmap_put(m, "key 1", val1);
150 1 : hashmap_put(m, "key 2", val2);
151 1 : hashmap_put(m, "key 3", val3);
152 1 : hashmap_put(m, "key 4", val4);
153 :
154 1 : assert_se(hashmap_move_one(n, NULL, "key 3") == -ENOENT);
155 1 : assert_se(hashmap_move_one(n, m, "key 5") == -ENOENT);
156 1 : assert_se(hashmap_move_one(n, m, "key 3") == 0);
157 1 : assert_se(hashmap_move_one(n, m, "key 4") == 0);
158 :
159 1 : r = hashmap_get(n, "key 3");
160 1 : assert_se(r && streq(r, "val3"));
161 1 : r = hashmap_get(n, "key 4");
162 1 : assert_se(r && streq(r, "val4"));
163 1 : r = hashmap_get(m, "key 3");
164 1 : assert_se(!r);
165 :
166 1 : assert_se(hashmap_move_one(n, m, "key 3") == -EEXIST);
167 :
168 1 : hashmap_free_free(m);
169 1 : hashmap_free_free(n);
170 1 : }
171 :
172 1 : static void test_hashmap_move(void) {
173 : Hashmap *m, *n;
174 : char *val1, *val2, *val3, *val4, *r;
175 :
176 1 : log_info("/* %s */", __func__);
177 :
178 1 : val1 = strdup("val1");
179 1 : assert_se(val1);
180 1 : val2 = strdup("val2");
181 1 : assert_se(val2);
182 1 : val3 = strdup("val3");
183 1 : assert_se(val3);
184 1 : val4 = strdup("val4");
185 1 : assert_se(val4);
186 :
187 1 : m = hashmap_new(&string_hash_ops);
188 1 : n = hashmap_new(&string_hash_ops);
189 :
190 1 : hashmap_put(n, "key 1", strdup(val1));
191 1 : hashmap_put(m, "key 1", val1);
192 1 : hashmap_put(m, "key 2", val2);
193 1 : hashmap_put(m, "key 3", val3);
194 1 : hashmap_put(m, "key 4", val4);
195 :
196 1 : assert_se(hashmap_move(n, NULL) == 0);
197 1 : assert_se(hashmap_move(n, m) == 0);
198 :
199 1 : assert_se(hashmap_size(m) == 1);
200 1 : r = hashmap_get(m, "key 1");
201 1 : assert_se(r && streq(r, "val1"));
202 :
203 1 : r = hashmap_get(n, "key 1");
204 1 : assert_se(r && streq(r, "val1"));
205 1 : r = hashmap_get(n, "key 2");
206 1 : assert_se(r && streq(r, "val2"));
207 1 : r = hashmap_get(n, "key 3");
208 1 : assert_se(r && streq(r, "val3"));
209 1 : r = hashmap_get(n, "key 4");
210 1 : assert_se(r && streq(r, "val4"));
211 :
212 1 : hashmap_free_free(m);
213 1 : hashmap_free_free(n);
214 1 : }
215 :
216 1 : static void test_hashmap_update(void) {
217 : Hashmap *m;
218 : char *val1, *val2, *r;
219 :
220 1 : log_info("/* %s */", __func__);
221 :
222 1 : m = hashmap_new(&string_hash_ops);
223 1 : val1 = strdup("old_value");
224 1 : assert_se(val1);
225 1 : val2 = strdup("new_value");
226 1 : assert_se(val2);
227 :
228 1 : hashmap_put(m, "key 1", val1);
229 1 : r = hashmap_get(m, "key 1");
230 1 : assert_se(streq(r, "old_value"));
231 :
232 1 : assert_se(hashmap_update(m, "key 2", val2) == -ENOENT);
233 1 : r = hashmap_get(m, "key 1");
234 1 : assert_se(streq(r, "old_value"));
235 :
236 1 : assert_se(hashmap_update(m, "key 1", val2) == 0);
237 1 : r = hashmap_get(m, "key 1");
238 1 : assert_se(streq(r, "new_value"));
239 :
240 1 : free(val1);
241 1 : free(val2);
242 1 : hashmap_free(m);
243 1 : }
244 :
245 1 : static void test_hashmap_put(void) {
246 1 : Hashmap *m = NULL;
247 : int valid_hashmap_put;
248 1 : void *val1 = (void*) "val 1";
249 1 : void *val2 = (void*) "val 2";
250 1 : _cleanup_free_ char* key1 = NULL;
251 :
252 1 : log_info("/* %s */", __func__);
253 :
254 1 : assert_se(hashmap_ensure_allocated(&m, &string_hash_ops) >= 0);
255 1 : assert_se(m);
256 :
257 1 : valid_hashmap_put = hashmap_put(m, "key 1", val1);
258 1 : assert_se(valid_hashmap_put == 1);
259 1 : assert_se(hashmap_put(m, "key 1", val1) == 0);
260 1 : assert_se(hashmap_put(m, "key 1", val2) == -EEXIST);
261 1 : key1 = strdup("key 1");
262 1 : assert_se(hashmap_put(m, key1, val1) == 0);
263 1 : assert_se(hashmap_put(m, key1, val2) == -EEXIST);
264 :
265 1 : hashmap_free(m);
266 1 : }
267 :
268 1 : static void test_hashmap_remove(void) {
269 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
270 : char *r;
271 :
272 1 : log_info("/* %s */", __func__);
273 :
274 1 : r = hashmap_remove(NULL, "key 1");
275 1 : assert_se(r == NULL);
276 :
277 1 : m = hashmap_new(&string_hash_ops);
278 1 : assert_se(m);
279 :
280 1 : r = hashmap_remove(m, "no such key");
281 1 : assert_se(r == NULL);
282 :
283 1 : hashmap_put(m, "key 1", (void*) "val 1");
284 1 : hashmap_put(m, "key 2", (void*) "val 2");
285 :
286 1 : r = hashmap_remove(m, "key 1");
287 1 : assert_se(streq(r, "val 1"));
288 :
289 1 : r = hashmap_get(m, "key 2");
290 1 : assert_se(streq(r, "val 2"));
291 1 : assert_se(!hashmap_get(m, "key 1"));
292 1 : }
293 :
294 1 : static void test_hashmap_remove2(void) {
295 1 : _cleanup_hashmap_free_free_free_ Hashmap *m = NULL;
296 1 : char key1[] = "key 1";
297 1 : char key2[] = "key 2";
298 1 : char val1[] = "val 1";
299 1 : char val2[] = "val 2";
300 : void *r, *r2;
301 :
302 1 : log_info("/* %s */", __func__);
303 :
304 1 : r = hashmap_remove2(NULL, "key 1", &r2);
305 1 : assert_se(r == NULL);
306 :
307 1 : m = hashmap_new(&string_hash_ops);
308 1 : assert_se(m);
309 :
310 1 : r = hashmap_remove2(m, "no such key", &r2);
311 1 : assert_se(r == NULL);
312 :
313 1 : hashmap_put(m, strdup(key1), strdup(val1));
314 1 : hashmap_put(m, strdup(key2), strdup(val2));
315 :
316 1 : r = hashmap_remove2(m, key1, &r2);
317 1 : assert_se(streq(r, val1));
318 1 : assert_se(streq(r2, key1));
319 1 : free(r);
320 1 : free(r2);
321 :
322 1 : r = hashmap_get(m, key2);
323 1 : assert_se(streq(r, val2));
324 1 : assert_se(!hashmap_get(m, key1));
325 1 : }
326 :
327 1 : static void test_hashmap_remove_value(void) {
328 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
329 : char *r;
330 :
331 1 : char val1[] = "val 1";
332 1 : char val2[] = "val 2";
333 :
334 1 : log_info("/* %s */", __func__);
335 :
336 1 : r = hashmap_remove_value(NULL, "key 1", val1);
337 1 : assert_se(r == NULL);
338 :
339 1 : m = hashmap_new(&string_hash_ops);
340 1 : assert_se(m);
341 :
342 1 : r = hashmap_remove_value(m, "key 1", val1);
343 1 : assert_se(r == NULL);
344 :
345 1 : hashmap_put(m, "key 1", val1);
346 1 : hashmap_put(m, "key 2", val2);
347 :
348 1 : r = hashmap_remove_value(m, "key 1", val1);
349 1 : assert_se(streq(r, "val 1"));
350 :
351 1 : r = hashmap_get(m, "key 2");
352 1 : assert_se(streq(r, "val 2"));
353 1 : assert_se(!hashmap_get(m, "key 1"));
354 :
355 1 : r = hashmap_remove_value(m, "key 2", val1);
356 1 : assert_se(r == NULL);
357 :
358 1 : r = hashmap_get(m, "key 2");
359 1 : assert_se(streq(r, "val 2"));
360 1 : assert_se(!hashmap_get(m, "key 1"));
361 1 : }
362 :
363 1 : static void test_hashmap_remove_and_put(void) {
364 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
365 : int valid;
366 : char *r;
367 :
368 1 : log_info("/* %s */", __func__);
369 :
370 1 : m = hashmap_new(&string_hash_ops);
371 1 : assert_se(m);
372 :
373 1 : valid = hashmap_remove_and_put(m, "invalid key", "new key", NULL);
374 1 : assert_se(valid == -ENOENT);
375 :
376 1 : valid = hashmap_put(m, "key 1", (void*) (const char *) "val 1");
377 1 : assert_se(valid == 1);
378 :
379 1 : valid = hashmap_remove_and_put(NULL, "key 1", "key 2", (void*) (const char *) "val 2");
380 1 : assert_se(valid == -ENOENT);
381 :
382 1 : valid = hashmap_remove_and_put(m, "key 1", "key 2", (void*) (const char *) "val 2");
383 1 : assert_se(valid == 0);
384 :
385 1 : r = hashmap_get(m, "key 2");
386 1 : assert_se(streq(r, "val 2"));
387 1 : assert_se(!hashmap_get(m, "key 1"));
388 :
389 1 : valid = hashmap_put(m, "key 3", (void*) (const char *) "val 3");
390 1 : assert_se(valid == 1);
391 1 : valid = hashmap_remove_and_put(m, "key 3", "key 2", (void*) (const char *) "val 2");
392 1 : assert_se(valid == -EEXIST);
393 1 : }
394 :
395 1 : static void test_hashmap_remove_and_replace(void) {
396 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
397 : int valid;
398 1 : void *key1 = UINT_TO_PTR(1);
399 1 : void *key2 = UINT_TO_PTR(2);
400 1 : void *key3 = UINT_TO_PTR(3);
401 : void *r;
402 : int i, j;
403 :
404 1 : log_info("/* %s */", __func__);
405 :
406 1 : m = hashmap_new(&trivial_hash_ops);
407 1 : assert_se(m);
408 :
409 1 : valid = hashmap_remove_and_replace(m, key1, key2, NULL);
410 1 : assert_se(valid == -ENOENT);
411 :
412 1 : valid = hashmap_put(m, key1, key1);
413 1 : assert_se(valid == 1);
414 :
415 1 : valid = hashmap_remove_and_replace(NULL, key1, key2, key2);
416 1 : assert_se(valid == -ENOENT);
417 :
418 1 : valid = hashmap_remove_and_replace(m, key1, key2, key2);
419 1 : assert_se(valid == 0);
420 :
421 1 : r = hashmap_get(m, key2);
422 1 : assert_se(r == key2);
423 1 : assert_se(!hashmap_get(m, key1));
424 :
425 1 : valid = hashmap_put(m, key3, key3);
426 1 : assert_se(valid == 1);
427 1 : valid = hashmap_remove_and_replace(m, key3, key2, key2);
428 1 : assert_se(valid == 0);
429 1 : r = hashmap_get(m, key2);
430 1 : assert_se(r == key2);
431 1 : assert_se(!hashmap_get(m, key3));
432 :
433 : /* Repeat this test several times to increase the chance of hitting
434 : * the less likely case in hashmap_remove_and_replace where it
435 : * compensates for the backward shift. */
436 21 : for (i = 0; i < 20; i++) {
437 20 : hashmap_clear(m);
438 :
439 140 : for (j = 1; j < 7; j++)
440 120 : hashmap_put(m, UINT_TO_PTR(10*i + j), UINT_TO_PTR(10*i + j));
441 40 : valid = hashmap_remove_and_replace(m, UINT_TO_PTR(10*i + 1),
442 20 : UINT_TO_PTR(10*i + 2),
443 20 : UINT_TO_PTR(10*i + 2));
444 20 : assert_se(valid == 0);
445 20 : assert_se(!hashmap_get(m, UINT_TO_PTR(10*i + 1)));
446 120 : for (j = 2; j < 7; j++) {
447 100 : r = hashmap_get(m, UINT_TO_PTR(10*i + j));
448 100 : assert_se(r == UINT_TO_PTR(10*i + j));
449 : }
450 : }
451 1 : }
452 :
453 1 : static void test_hashmap_ensure_allocated(void) {
454 : Hashmap *m;
455 : int valid_hashmap;
456 :
457 1 : log_info("/* %s */", __func__);
458 :
459 1 : m = hashmap_new(&string_hash_ops);
460 :
461 1 : valid_hashmap = hashmap_ensure_allocated(&m, &string_hash_ops);
462 1 : assert_se(valid_hashmap == 0);
463 :
464 1 : assert_se(m);
465 1 : hashmap_free(m);
466 1 : }
467 :
468 1 : static void test_hashmap_foreach_key(void) {
469 : Hashmap *m;
470 : Iterator i;
471 1 : bool key_found[] = { false, false, false, false };
472 : const char *s;
473 : const char *key;
474 : static const char key_table[] =
475 : "key 1\0"
476 : "key 2\0"
477 : "key 3\0"
478 : "key 4\0";
479 :
480 1 : log_info("/* %s */", __func__);
481 :
482 1 : m = hashmap_new(&string_hash_ops);
483 :
484 5 : NULSTR_FOREACH(key, key_table)
485 4 : hashmap_put(m, key, (void*) (const char*) "my dummy val");
486 :
487 5 : HASHMAP_FOREACH_KEY(s, key, m, i) {
488 4 : assert(s);
489 4 : if (!key_found[0] && streq(key, "key 1"))
490 1 : key_found[0] = true;
491 3 : else if (!key_found[1] && streq(key, "key 2"))
492 1 : key_found[1] = true;
493 2 : else if (!key_found[2] && streq(key, "key 3"))
494 1 : key_found[2] = true;
495 1 : else if (!key_found[3] && streq(key, "fail"))
496 0 : key_found[3] = true;
497 : }
498 :
499 1 : assert_se(m);
500 1 : assert_se(key_found[0] && key_found[1] && key_found[2] && !key_found[3]);
501 :
502 1 : hashmap_free(m);
503 1 : }
504 :
505 1 : static void test_hashmap_foreach(void) {
506 : Hashmap *m;
507 : Iterator i;
508 1 : bool value_found[] = { false, false, false, false };
509 : char *val1, *val2, *val3, *val4, *s;
510 : unsigned count;
511 :
512 1 : log_info("/* %s */", __func__);
513 :
514 1 : val1 = strdup("my val1");
515 1 : assert_se(val1);
516 1 : val2 = strdup("my val2");
517 1 : assert_se(val2);
518 1 : val3 = strdup("my val3");
519 1 : assert_se(val3);
520 1 : val4 = strdup("my val4");
521 1 : assert_se(val4);
522 :
523 1 : m = NULL;
524 :
525 1 : count = 0;
526 1 : HASHMAP_FOREACH(s, m, i)
527 0 : count++;
528 1 : assert_se(count == 0);
529 :
530 1 : m = hashmap_new(&string_hash_ops);
531 :
532 1 : count = 0;
533 1 : HASHMAP_FOREACH(s, m, i)
534 0 : count++;
535 1 : assert_se(count == 0);
536 :
537 1 : hashmap_put(m, "Key 1", val1);
538 1 : hashmap_put(m, "Key 2", val2);
539 1 : hashmap_put(m, "Key 3", val3);
540 1 : hashmap_put(m, "Key 4", val4);
541 :
542 5 : HASHMAP_FOREACH(s, m, i) {
543 4 : if (!value_found[0] && streq(s, val1))
544 1 : value_found[0] = true;
545 3 : else if (!value_found[1] && streq(s, val2))
546 1 : value_found[1] = true;
547 2 : else if (!value_found[2] && streq(s, val3))
548 1 : value_found[2] = true;
549 1 : else if (!value_found[3] && streq(s, val4))
550 1 : value_found[3] = true;
551 : }
552 :
553 1 : assert_se(m);
554 1 : assert_se(value_found[0] && value_found[1] && value_found[2] && value_found[3]);
555 :
556 1 : hashmap_free_free(m);
557 1 : }
558 :
559 1 : static void test_hashmap_merge(void) {
560 : Hashmap *m;
561 : Hashmap *n;
562 : char *val1, *val2, *val3, *val4, *r;
563 :
564 1 : log_info("/* %s */", __func__);
565 :
566 1 : val1 = strdup("my val1");
567 1 : assert_se(val1);
568 1 : val2 = strdup("my val2");
569 1 : assert_se(val2);
570 1 : val3 = strdup("my val3");
571 1 : assert_se(val3);
572 1 : val4 = strdup("my val4");
573 1 : assert_se(val4);
574 :
575 1 : n = hashmap_new(&string_hash_ops);
576 1 : m = hashmap_new(&string_hash_ops);
577 :
578 1 : hashmap_put(m, "Key 1", val1);
579 1 : hashmap_put(m, "Key 2", val2);
580 1 : hashmap_put(n, "Key 3", val3);
581 1 : hashmap_put(n, "Key 4", val4);
582 :
583 1 : assert_se(hashmap_merge(m, n) == 0);
584 1 : r = hashmap_get(m, "Key 3");
585 1 : assert_se(r && streq(r, "my val3"));
586 1 : r = hashmap_get(m, "Key 4");
587 1 : assert_se(r && streq(r, "my val4"));
588 :
589 1 : assert_se(n);
590 1 : assert_se(m);
591 1 : hashmap_free(n);
592 1 : hashmap_free_free(m);
593 1 : }
594 :
595 1 : static void test_hashmap_contains(void) {
596 : Hashmap *m;
597 : char *val1;
598 :
599 1 : log_info("/* %s */", __func__);
600 :
601 1 : val1 = strdup("my val");
602 1 : assert_se(val1);
603 :
604 1 : m = hashmap_new(&string_hash_ops);
605 :
606 1 : assert_se(!hashmap_contains(m, "Key 1"));
607 1 : hashmap_put(m, "Key 1", val1);
608 1 : assert_se(hashmap_contains(m, "Key 1"));
609 1 : assert_se(!hashmap_contains(m, "Key 2"));
610 :
611 1 : assert_se(!hashmap_contains(NULL, "Key 1"));
612 :
613 1 : assert_se(m);
614 1 : hashmap_free_free(m);
615 1 : }
616 :
617 1 : static void test_hashmap_isempty(void) {
618 : Hashmap *m;
619 : char *val1;
620 :
621 1 : log_info("/* %s */", __func__);
622 :
623 1 : val1 = strdup("my val");
624 1 : assert_se(val1);
625 :
626 1 : m = hashmap_new(&string_hash_ops);
627 :
628 1 : assert_se(hashmap_isempty(m));
629 1 : hashmap_put(m, "Key 1", val1);
630 1 : assert_se(!hashmap_isempty(m));
631 :
632 1 : assert_se(m);
633 1 : hashmap_free_free(m);
634 1 : }
635 :
636 1 : static void test_hashmap_size(void) {
637 : Hashmap *m;
638 : char *val1, *val2, *val3, *val4;
639 :
640 1 : log_info("/* %s */", __func__);
641 :
642 1 : val1 = strdup("my val");
643 1 : assert_se(val1);
644 1 : val2 = strdup("my val");
645 1 : assert_se(val2);
646 1 : val3 = strdup("my val");
647 1 : assert_se(val3);
648 1 : val4 = strdup("my val");
649 1 : assert_se(val4);
650 :
651 1 : assert_se(hashmap_size(NULL) == 0);
652 1 : assert_se(hashmap_buckets(NULL) == 0);
653 :
654 1 : m = hashmap_new(&string_hash_ops);
655 :
656 1 : hashmap_put(m, "Key 1", val1);
657 1 : hashmap_put(m, "Key 2", val2);
658 1 : hashmap_put(m, "Key 3", val3);
659 1 : hashmap_put(m, "Key 4", val4);
660 :
661 1 : assert_se(m);
662 1 : assert_se(hashmap_size(m) == 4);
663 1 : assert_se(hashmap_buckets(m) >= 4);
664 1 : hashmap_free_free(m);
665 1 : }
666 :
667 1 : static void test_hashmap_get(void) {
668 : Hashmap *m;
669 : char *r;
670 : char *val;
671 :
672 1 : log_info("/* %s */", __func__);
673 :
674 1 : val = strdup("my val");
675 1 : assert_se(val);
676 :
677 1 : r = hashmap_get(NULL, "Key 1");
678 1 : assert_se(r == NULL);
679 :
680 1 : m = hashmap_new(&string_hash_ops);
681 :
682 1 : hashmap_put(m, "Key 1", val);
683 :
684 1 : r = hashmap_get(m, "Key 1");
685 1 : assert_se(streq(r, val));
686 :
687 1 : r = hashmap_get(m, "no such key");
688 1 : assert_se(r == NULL);
689 :
690 1 : assert_se(m);
691 1 : hashmap_free_free(m);
692 1 : }
693 :
694 1 : static void test_hashmap_get2(void) {
695 : Hashmap *m;
696 : char *r;
697 : char *val;
698 1 : char key_orig[] = "Key 1";
699 : void *key_copy;
700 :
701 1 : log_info("/* %s */", __func__);
702 :
703 1 : val = strdup("my val");
704 1 : assert_se(val);
705 :
706 1 : key_copy = strdup(key_orig);
707 1 : assert_se(key_copy);
708 :
709 1 : r = hashmap_get2(NULL, key_orig, &key_copy);
710 1 : assert_se(r == NULL);
711 :
712 1 : m = hashmap_new(&string_hash_ops);
713 :
714 1 : hashmap_put(m, key_copy, val);
715 1 : key_copy = NULL;
716 :
717 1 : r = hashmap_get2(m, key_orig, &key_copy);
718 1 : assert_se(streq(r, val));
719 1 : assert_se(key_orig != key_copy);
720 1 : assert_se(streq(key_orig, key_copy));
721 :
722 1 : r = hashmap_get2(m, "no such key", NULL);
723 1 : assert_se(r == NULL);
724 :
725 1 : assert_se(m);
726 1 : hashmap_free_free_free(m);
727 1 : }
728 :
729 1033 : static void crippled_hashmap_func(const void *p, struct siphash *state) {
730 1033 : return trivial_hash_func(INT_TO_PTR(PTR_TO_INT(p) & 0xff), state);
731 : }
732 :
733 : static const struct hash_ops crippled_hashmap_ops = {
734 : .hash = crippled_hashmap_func,
735 : .compare = trivial_compare_func,
736 : };
737 :
738 1 : static void test_hashmap_many(void) {
739 : Hashmap *h;
740 : unsigned i, j;
741 : void *v, *k;
742 1 : bool slow = slow_tests_enabled();
743 : const struct {
744 : const char *title;
745 : const struct hash_ops *ops;
746 : unsigned n_entries;
747 3 : } tests[] = {
748 1 : { "trivial_hashmap_ops", NULL, slow ? 1 << 20 : 240 },
749 1 : { "crippled_hashmap_ops", &crippled_hashmap_ops, slow ? 1 << 14 : 140 },
750 : };
751 :
752 1 : log_info("/* %s (%s) */", __func__, slow ? "slow" : "fast");
753 :
754 3 : for (j = 0; j < ELEMENTSOF(tests); j++) {
755 2 : usec_t ts = now(CLOCK_MONOTONIC), n;
756 : char b[FORMAT_TIMESPAN_MAX];
757 :
758 2 : assert_se(h = hashmap_new(tests[j].ops));
759 :
760 382 : for (i = 1; i < tests[j].n_entries*3; i+=3) {
761 380 : assert_se(hashmap_put(h, UINT_TO_PTR(i), UINT_TO_PTR(i)) >= 0);
762 380 : assert_se(PTR_TO_UINT(hashmap_get(h, UINT_TO_PTR(i))) == i);
763 : }
764 :
765 1140 : for (i = 1; i < tests[j].n_entries*3; i++)
766 1138 : assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1));
767 :
768 2 : log_info("%s %u <= %u * 0.8 = %g",
769 : tests[j].title, hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.8);
770 :
771 2 : assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.8);
772 2 : assert_se(hashmap_size(h) == tests[j].n_entries);
773 :
774 382 : while (!hashmap_isempty(h)) {
775 380 : k = hashmap_first_key(h);
776 380 : v = hashmap_remove(h, k);
777 380 : assert_se(v == k);
778 : }
779 :
780 2 : hashmap_free(h);
781 :
782 2 : n = now(CLOCK_MONOTONIC);
783 2 : log_info("test took %s", format_timespan(b, sizeof b, n - ts, 0));
784 : }
785 1 : }
786 :
787 : extern unsigned custom_counter;
788 : extern const struct hash_ops boring_hash_ops, custom_hash_ops;
789 :
790 1 : static void test_hashmap_free(void) {
791 : Hashmap *h;
792 1 : bool slow = slow_tests_enabled();
793 : usec_t ts, n;
794 : char b[FORMAT_TIMESPAN_MAX];
795 1 : unsigned n_entries = slow ? 1 << 20 : 240;
796 :
797 : const struct {
798 : const char *title;
799 : const struct hash_ops *ops;
800 : unsigned expect_counter;
801 2 : } tests[] = {
802 1 : { "string_hash_ops", &boring_hash_ops, 2 * n_entries},
803 : { "custom_free_hash_ops", &custom_hash_ops, 0 },
804 : };
805 :
806 1 : log_info("/* %s (%s, %u entries) */", __func__, slow ? "slow" : "fast", n_entries);
807 :
808 3 : for (unsigned j = 0; j < ELEMENTSOF(tests); j++) {
809 2 : ts = now(CLOCK_MONOTONIC);
810 2 : assert_se(h = hashmap_new(tests[j].ops));
811 :
812 2 : custom_counter = 0;
813 482 : for (unsigned i = 0; i < n_entries; i++) {
814 : char s[DECIMAL_STR_MAX(unsigned)];
815 : char *k, *v;
816 :
817 480 : xsprintf(s, "%u", i);
818 480 : assert_se(k = strdup(s));
819 480 : assert_se(v = strdup(s));
820 480 : custom_counter += 2;
821 :
822 480 : assert_se(hashmap_put(h, k, v) >= 0);
823 : }
824 :
825 2 : hashmap_free(h);
826 :
827 2 : n = now(CLOCK_MONOTONIC);
828 2 : log_info("%s test took %s", tests[j].title, format_timespan(b, sizeof b, n - ts, 0));
829 :
830 2 : assert_se(custom_counter == tests[j].expect_counter);
831 : }
832 1 : }
833 :
834 : typedef struct Item {
835 : int seen;
836 : } Item;
837 3 : static void item_seen(Item *item) {
838 3 : item->seen++;
839 3 : }
840 :
841 1 : static void test_hashmap_free_with_destructor(void) {
842 : Hashmap *m;
843 1 : struct Item items[4] = {};
844 : unsigned i;
845 :
846 1 : log_info("/* %s */", __func__);
847 :
848 1 : assert_se(m = hashmap_new(NULL));
849 4 : for (i = 0; i < ELEMENTSOF(items) - 1; i++)
850 3 : assert_se(hashmap_put(m, INT_TO_PTR(i), items + i) == 1);
851 :
852 4 : m = hashmap_free_with_destructor(m, item_seen);
853 1 : assert_se(items[0].seen == 1);
854 1 : assert_se(items[1].seen == 1);
855 1 : assert_se(items[2].seen == 1);
856 1 : assert_se(items[3].seen == 0);
857 1 : }
858 :
859 1 : static void test_hashmap_first(void) {
860 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
861 :
862 1 : log_info("/* %s */", __func__);
863 :
864 1 : m = hashmap_new(&string_hash_ops);
865 1 : assert_se(m);
866 :
867 1 : assert_se(!hashmap_first(m));
868 1 : assert_se(hashmap_put(m, "key 1", (void*) "val 1") == 1);
869 1 : assert_se(streq(hashmap_first(m), "val 1"));
870 1 : assert_se(hashmap_put(m, "key 2", (void*) "val 2") == 1);
871 : #ifdef ORDERED
872 : assert_se(streq(hashmap_first(m), "val 1"));
873 : assert_se(hashmap_remove(m, "key 1"));
874 : assert_se(streq(hashmap_first(m), "val 2"));
875 : #endif
876 1 : }
877 :
878 1 : static void test_hashmap_first_key(void) {
879 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
880 :
881 1 : log_info("/* %s */", __func__);
882 :
883 1 : m = hashmap_new(&string_hash_ops);
884 1 : assert_se(m);
885 :
886 1 : assert_se(!hashmap_first_key(m));
887 1 : assert_se(hashmap_put(m, "key 1", NULL) == 1);
888 1 : assert_se(streq(hashmap_first_key(m), "key 1"));
889 1 : assert_se(hashmap_put(m, "key 2", NULL) == 1);
890 : #ifdef ORDERED
891 : assert_se(streq(hashmap_first_key(m), "key 1"));
892 : assert_se(hashmap_remove(m, "key 1") == NULL);
893 : assert_se(streq(hashmap_first_key(m), "key 2"));
894 : #endif
895 1 : }
896 :
897 1 : static void test_hashmap_steal_first_key(void) {
898 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
899 :
900 1 : log_info("/* %s */", __func__);
901 :
902 1 : m = hashmap_new(&string_hash_ops);
903 1 : assert_se(m);
904 :
905 1 : assert_se(!hashmap_steal_first_key(m));
906 1 : assert_se(hashmap_put(m, "key 1", NULL) == 1);
907 1 : assert_se(streq(hashmap_steal_first_key(m), "key 1"));
908 :
909 1 : assert_se(hashmap_isempty(m));
910 1 : }
911 :
912 1 : static void test_hashmap_steal_first(void) {
913 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
914 1 : int seen[3] = {};
915 : char *val;
916 :
917 1 : log_info("/* %s */", __func__);
918 :
919 1 : m = hashmap_new(&string_hash_ops);
920 1 : assert_se(m);
921 :
922 1 : assert_se(hashmap_put(m, "key 1", (void*) "1") == 1);
923 1 : assert_se(hashmap_put(m, "key 2", (void*) "22") == 1);
924 1 : assert_se(hashmap_put(m, "key 3", (void*) "333") == 1);
925 :
926 4 : while ((val = hashmap_steal_first(m)))
927 3 : seen[strlen(val) - 1]++;
928 :
929 1 : assert_se(seen[0] == 1 && seen[1] == 1 && seen[2] == 1);
930 :
931 1 : assert_se(hashmap_isempty(m));
932 1 : }
933 :
934 1 : static void test_hashmap_clear_free_free(void) {
935 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
936 :
937 1 : log_info("/* %s */", __func__);
938 :
939 1 : m = hashmap_new(&string_hash_ops);
940 1 : assert_se(m);
941 :
942 1 : assert_se(hashmap_put(m, strdup("key 1"), NULL) == 1);
943 1 : assert_se(hashmap_put(m, strdup("key 2"), NULL) == 1);
944 1 : assert_se(hashmap_put(m, strdup("key 3"), NULL) == 1);
945 :
946 1 : hashmap_clear_free_free(m);
947 1 : assert_se(hashmap_isempty(m));
948 :
949 1 : assert_se(hashmap_put(m, strdup("key 1"), strdup("value 1")) == 1);
950 1 : assert_se(hashmap_put(m, strdup("key 2"), strdup("value 2")) == 1);
951 1 : assert_se(hashmap_put(m, strdup("key 3"), strdup("value 3")) == 1);
952 :
953 1 : hashmap_clear_free_free(m);
954 1 : assert_se(hashmap_isempty(m));
955 1 : }
956 :
957 3 : DEFINE_PRIVATE_HASH_OPS_WITH_KEY_DESTRUCTOR(test_hash_ops_key, char, string_hash_func, string_compare_func, free);
958 6 : DEFINE_PRIVATE_HASH_OPS_FULL(test_hash_ops_full, char, string_hash_func, string_compare_func, free, char, free);
959 :
960 1 : static void test_hashmap_clear_free_with_destructor(void) {
961 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
962 :
963 1 : log_info("/* %s */", __func__);
964 :
965 1 : m = hashmap_new(&test_hash_ops_key);
966 1 : assert_se(m);
967 :
968 1 : assert_se(hashmap_put(m, strdup("key 1"), NULL) == 1);
969 1 : assert_se(hashmap_put(m, strdup("key 2"), NULL) == 1);
970 1 : assert_se(hashmap_put(m, strdup("key 3"), NULL) == 1);
971 :
972 1 : hashmap_clear_free(m);
973 1 : assert_se(hashmap_isempty(m));
974 1 : m = hashmap_free(m);
975 :
976 1 : m = hashmap_new(&test_hash_ops_full);
977 1 : assert_se(m);
978 :
979 1 : assert_se(hashmap_put(m, strdup("key 1"), strdup("value 1")) == 1);
980 1 : assert_se(hashmap_put(m, strdup("key 2"), strdup("value 2")) == 1);
981 1 : assert_se(hashmap_put(m, strdup("key 3"), strdup("value 3")) == 1);
982 :
983 1 : hashmap_clear_free(m);
984 1 : assert_se(hashmap_isempty(m));
985 1 : }
986 :
987 1 : static void test_hashmap_reserve(void) {
988 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
989 :
990 1 : log_info("/* %s */", __func__);
991 :
992 1 : m = hashmap_new(&string_hash_ops);
993 :
994 1 : assert_se(hashmap_reserve(m, 1) == 0);
995 1 : assert_se(hashmap_buckets(m) < 1000);
996 1 : assert_se(hashmap_reserve(m, 1000) == 0);
997 1 : assert_se(hashmap_buckets(m) >= 1000);
998 1 : assert_se(hashmap_isempty(m));
999 :
1000 1 : assert_se(hashmap_put(m, "key 1", (void*) "val 1") == 1);
1001 :
1002 1 : assert_se(hashmap_reserve(m, UINT_MAX) == -ENOMEM);
1003 1 : assert_se(hashmap_reserve(m, UINT_MAX - 1) == -ENOMEM);
1004 1 : }
1005 :
1006 1 : static void test_path_hashmap(void) {
1007 1 : _cleanup_hashmap_free_ Hashmap *h = NULL;
1008 :
1009 1 : log_info("/* %s */", __func__);
1010 :
1011 1 : assert_se(h = hashmap_new(&path_hash_ops));
1012 :
1013 1 : assert_se(hashmap_put(h, "foo", INT_TO_PTR(1)) >= 0);
1014 1 : assert_se(hashmap_put(h, "/foo", INT_TO_PTR(2)) >= 0);
1015 1 : assert_se(hashmap_put(h, "//foo", INT_TO_PTR(3)) == -EEXIST);
1016 1 : assert_se(hashmap_put(h, "//foox/", INT_TO_PTR(4)) >= 0);
1017 1 : assert_se(hashmap_put(h, "/foox////", INT_TO_PTR(5)) == -EEXIST);
1018 1 : assert_se(hashmap_put(h, "foo//////bar/quux//", INT_TO_PTR(6)) >= 0);
1019 1 : assert_se(hashmap_put(h, "foo/bar//quux/", INT_TO_PTR(8)) == -EEXIST);
1020 :
1021 1 : assert_se(hashmap_get(h, "foo") == INT_TO_PTR(1));
1022 1 : assert_se(hashmap_get(h, "foo/") == INT_TO_PTR(1));
1023 1 : assert_se(hashmap_get(h, "foo////") == INT_TO_PTR(1));
1024 1 : assert_se(hashmap_get(h, "/foo") == INT_TO_PTR(2));
1025 1 : assert_se(hashmap_get(h, "//foo") == INT_TO_PTR(2));
1026 1 : assert_se(hashmap_get(h, "/////foo////") == INT_TO_PTR(2));
1027 1 : assert_se(hashmap_get(h, "/////foox////") == INT_TO_PTR(4));
1028 1 : assert_se(hashmap_get(h, "/foox/") == INT_TO_PTR(4));
1029 1 : assert_se(hashmap_get(h, "/foox") == INT_TO_PTR(4));
1030 1 : assert_se(!hashmap_get(h, "foox"));
1031 1 : assert_se(hashmap_get(h, "foo/bar/quux") == INT_TO_PTR(6));
1032 1 : assert_se(hashmap_get(h, "foo////bar////quux/////") == INT_TO_PTR(6));
1033 1 : assert_se(!hashmap_get(h, "/foo////bar////quux/////"));
1034 1 : }
1035 :
1036 1 : static void test_string_strv_hashmap(void) {
1037 1 : _cleanup_hashmap_free_ Hashmap *m = NULL;
1038 : char **s;
1039 :
1040 1 : log_info("/* %s */", __func__);
1041 :
1042 1 : assert_se(string_strv_hashmap_put(&m, "foo", "bar") == 1);
1043 1 : assert_se(string_strv_hashmap_put(&m, "foo", "bar") == 0);
1044 1 : assert_se(string_strv_hashmap_put(&m, "foo", "BAR") == 1);
1045 1 : assert_se(string_strv_hashmap_put(&m, "foo", "BAR") == 0);
1046 1 : assert_se(string_strv_hashmap_put(&m, "foo", "bar") == 0);
1047 1 : assert_se(hashmap_contains(m, "foo"));
1048 :
1049 1 : s = hashmap_get(m, "foo");
1050 1 : assert_se(strv_equal(s, STRV_MAKE("bar", "BAR")));
1051 :
1052 1 : assert_se(string_strv_hashmap_put(&m, "xxx", "bar") == 1);
1053 1 : assert_se(string_strv_hashmap_put(&m, "xxx", "bar") == 0);
1054 1 : assert_se(string_strv_hashmap_put(&m, "xxx", "BAR") == 1);
1055 1 : assert_se(string_strv_hashmap_put(&m, "xxx", "BAR") == 0);
1056 1 : assert_se(string_strv_hashmap_put(&m, "xxx", "bar") == 0);
1057 1 : assert_se(hashmap_contains(m, "xxx"));
1058 :
1059 1 : s = hashmap_get(m, "xxx");
1060 1 : assert_se(strv_equal(s, STRV_MAKE("bar", "BAR")));
1061 1 : }
1062 :
1063 1 : void test_hashmap_funcs(void) {
1064 1 : log_info("/************ %s ************/", __func__);
1065 :
1066 1 : test_hashmap_copy();
1067 1 : test_hashmap_get_strv();
1068 1 : test_hashmap_move_one();
1069 1 : test_hashmap_move();
1070 1 : test_hashmap_replace();
1071 1 : test_hashmap_update();
1072 1 : test_hashmap_put();
1073 1 : test_hashmap_remove();
1074 1 : test_hashmap_remove2();
1075 1 : test_hashmap_remove_value();
1076 1 : test_hashmap_remove_and_put();
1077 1 : test_hashmap_remove_and_replace();
1078 1 : test_hashmap_ensure_allocated();
1079 1 : test_hashmap_foreach();
1080 1 : test_hashmap_foreach_key();
1081 1 : test_hashmap_contains();
1082 1 : test_hashmap_merge();
1083 1 : test_hashmap_isempty();
1084 1 : test_hashmap_get();
1085 1 : test_hashmap_get2();
1086 1 : test_hashmap_size();
1087 1 : test_hashmap_many();
1088 1 : test_hashmap_free();
1089 1 : test_hashmap_free_with_destructor();
1090 1 : test_hashmap_first();
1091 1 : test_hashmap_first_key();
1092 1 : test_hashmap_steal_first_key();
1093 1 : test_hashmap_steal_first();
1094 1 : test_hashmap_clear_free_free();
1095 1 : test_hashmap_clear_free_with_destructor();
1096 1 : test_hashmap_reserve();
1097 1 : test_path_hashmap();
1098 1 : test_string_strv_hashmap();
1099 1 : }
|
