chiark / gitweb /
update TODO
[elogind.git] / src / test / test-hashmap.c
1 /***
2   This file is part of systemd
3
4   Copyright 2013 Daniel Buch
5
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.
10
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.
15
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/>.
18 ***/
19
20 #include <inttypes.h>
21 #include "strv.h"
22 #include "util.h"
23 #include "hashmap.h"
24
25 static void test_hashmap_replace(void) {
26         Hashmap *m;
27         char *val1, *val2, *val3, *val4, *val5, *r;
28
29         m = hashmap_new(string_hash_func, string_compare_func);
30
31         val1 = strdup("val1");
32         assert_se(val1);
33         val2 = strdup("val2");
34         assert_se(val2);
35         val3 = strdup("val3");
36         assert_se(val3);
37         val4 = strdup("val4");
38         assert_se(val4);
39         val5 = strdup("val5");
40         assert_se(val5);
41
42         hashmap_put(m, "key 1", val1);
43         hashmap_put(m, "key 2", val2);
44         hashmap_put(m, "key 3", val3);
45         hashmap_put(m, "key 4", val4);
46
47         hashmap_replace(m, "key 3", val1);
48         r = hashmap_get(m, "key 3");
49         assert_se(streq(r, "val1"));
50
51         hashmap_replace(m, "key 5", val5);
52         r = hashmap_get(m, "key 5");
53         assert_se(streq(r, "val5"));
54
55         free(val1);
56         free(val2);
57         free(val3);
58         free(val4);
59         free(val5);
60         hashmap_free(m);
61 }
62
63 static void test_hashmap_copy(void) {
64         Hashmap *m, *copy;
65         char *val1, *val2, *val3, *val4, *r;
66
67         val1 = strdup("val1");
68         assert_se(val1);
69         val2 = strdup("val2");
70         assert_se(val2);
71         val3 = strdup("val3");
72         assert_se(val3);
73         val4 = strdup("val4");
74         assert_se(val4);
75
76         m = hashmap_new(string_hash_func, string_compare_func);
77
78         hashmap_put(m, "key 1", val1);
79         hashmap_put(m, "key 2", val2);
80         hashmap_put(m, "key 3", val3);
81         hashmap_put(m, "key 4", val4);
82
83         copy = hashmap_copy(m);
84
85         r = hashmap_get(copy, "key 1");
86         assert_se(streq(r, "val1"));
87         r = hashmap_get(copy, "key 2");
88         assert_se(streq(r, "val2"));
89         r = hashmap_get(copy, "key 3");
90         assert_se(streq(r, "val3"));
91         r = hashmap_get(copy, "key 4");
92         assert_se(streq(r, "val4"));
93
94         hashmap_free_free(copy);
95         hashmap_free(m);
96 }
97
98 static void test_hashmap_get_strv(void) {
99         Hashmap *m;
100         char **strv;
101         char *val1, *val2, *val3, *val4;
102
103         val1 = strdup("val1");
104         assert_se(val1);
105         val2 = strdup("val2");
106         assert_se(val2);
107         val3 = strdup("val3");
108         assert_se(val3);
109         val4 = strdup("val4");
110         assert_se(val4);
111
112         m = hashmap_new(string_hash_func, string_compare_func);
113
114         hashmap_put(m, "key 1", val1);
115         hashmap_put(m, "key 2", val2);
116         hashmap_put(m, "key 3", val3);
117         hashmap_put(m, "key 4", val4);
118
119         strv = hashmap_get_strv(m);
120
121         assert_se(streq(strv[0], "val1"));
122         assert_se(streq(strv[1], "val2"));
123         assert_se(streq(strv[2], "val3"));
124         assert_se(streq(strv[3], "val4"));
125
126         strv_free(strv);
127
128         hashmap_free(m);
129 }
130
131 static void test_hashmap_move_one(void) {
132         Hashmap *m, *n;
133         char *val1, *val2, *val3, *val4, *r;
134
135         val1 = strdup("val1");
136         assert_se(val1);
137         val2 = strdup("val2");
138         assert_se(val2);
139         val3 = strdup("val3");
140         assert_se(val3);
141         val4 = strdup("val4");
142         assert_se(val4);
143
144         m = hashmap_new(string_hash_func, string_compare_func);
145         n = hashmap_new(string_hash_func, string_compare_func);
146
147         hashmap_put(m, "key 1", val1);
148         hashmap_put(m, "key 2", val2);
149         hashmap_put(m, "key 3", val3);
150         hashmap_put(m, "key 4", val4);
151
152         hashmap_move_one(n, m, "key 3");
153         hashmap_move_one(n, m, "key 4");
154
155         r = hashmap_get(n, "key 3");
156         assert_se(r && streq(r, "val3"));
157         r = hashmap_get(n, "key 4");
158         assert_se(r && streq(r, "val4"));
159         r = hashmap_get(m, "key 3");
160         assert_se(!r);
161
162
163         hashmap_free_free(m);
164         hashmap_free_free(n);
165 }
166
167 static void test_hashmap_next(void) {
168         Hashmap *m;
169         char *val1, *val2, *val3, *val4, *r;
170
171         m = hashmap_new(string_hash_func, string_compare_func);
172         val1 = strdup("val1");
173         assert_se(val1);
174         val2 = strdup("val2");
175         assert_se(val2);
176         val3 = strdup("val3");
177         assert_se(val3);
178         val4 = strdup("val4");
179         assert_se(val4);
180
181         hashmap_put(m, "key 1", val1);
182         hashmap_put(m, "key 2", val2);
183         hashmap_put(m, "key 3", val3);
184         hashmap_put(m, "key 4", val4);
185
186         r = hashmap_next(m, "key 1");
187         assert_se(streq(r, val2));
188         r = hashmap_next(m, "key 2");
189         assert_se(streq(r, val3));
190         r = hashmap_next(m, "key 3");
191         assert_se(streq(r, val4));
192         r = hashmap_next(m, "key 4");
193         assert_se(!r);
194
195         hashmap_free_free(m);
196 }
197
198 static void test_hashmap_update(void) {
199         Hashmap *m;
200         char *val1, *val2, *r;
201
202         m = hashmap_new(string_hash_func, string_compare_func);
203         val1 = strdup("old_value");
204         assert_se(val1);
205         val2 = strdup("new_value");
206         assert_se(val2);
207
208         hashmap_put(m, "key 1", val1);
209         r = hashmap_get(m, "key 1");
210         assert_se(streq(r, "old_value"));
211
212         hashmap_update(m, "key 1", val2);
213         r = hashmap_get(m, "key 1");
214         assert_se(streq(r, "new_value"));
215
216         free(val1);
217         free(val2);
218         hashmap_free(m);
219 }
220
221 static void test_hashmap_put(void) {
222         Hashmap *m;
223         int valid_hashmap_put;
224
225         m = hashmap_new(string_hash_func, string_compare_func);
226
227         valid_hashmap_put = hashmap_put(m, "key 1", (void*) (const char *) "val 1");
228         assert_se(valid_hashmap_put == 1);
229
230         assert_se(m);
231         hashmap_free(m);
232 }
233
234 static void test_hashmap_ensure_allocated(void) {
235         Hashmap *m;
236         int valid_hashmap;
237
238         m = hashmap_new(string_hash_func, string_compare_func);
239
240         valid_hashmap = hashmap_ensure_allocated(&m, string_hash_func, string_compare_func);
241         assert_se(valid_hashmap == 0);
242
243         assert_se(m);
244         hashmap_free(m);
245 }
246
247 static void test_hashmap_foreach_key(void) {
248         Hashmap *m;
249         Iterator i;
250         bool key_found[] = { false, false, false, false };
251         const char *s;
252         const char *key;
253         static const char key_table[] =
254                 "key 1\0"
255                 "key 2\0"
256                 "key 3\0"
257                 "key 4\0";
258
259         m = hashmap_new(string_hash_func, string_compare_func);
260
261         NULSTR_FOREACH(key, key_table)
262                 hashmap_put(m, key, (void*) (const char*) "my dummy val");
263
264         HASHMAP_FOREACH_KEY(s, key, m, i) {
265                 if (!key_found[0] && streq(key, "key 1"))
266                         key_found[0] = true;
267                 else if (!key_found[1] && streq(key, "key 2"))
268                         key_found[1] = true;
269                 else if (!key_found[2] && streq(key, "key 3"))
270                         key_found[2] = true;
271                 else if (!key_found[3] && streq(key, "fail"))
272                         key_found[3] = true;
273         }
274
275         assert_se(m);
276         assert_se(key_found[0] && key_found[1] && key_found[2] && !key_found[3]);
277
278         hashmap_free(m);
279 }
280
281 static void test_hashmap_foreach(void) {
282         Hashmap *m;
283         Iterator i;
284         bool value_found[] = { false, false, false, false };
285         char *val1, *val2, *val3, *val4, *s;
286
287         val1 = strdup("my val1");
288         assert_se(val1);
289         val2 = strdup("my val2");
290         assert_se(val2);
291         val3 = strdup("my val3");
292         assert_se(val3);
293         val4 = strdup("my val4");
294         assert_se(val4);
295
296         m = hashmap_new(string_hash_func, string_compare_func);
297
298         hashmap_put(m, "Key 1", val1);
299         hashmap_put(m, "Key 2", val2);
300         hashmap_put(m, "Key 3", val3);
301         hashmap_put(m, "Key 4", val4);
302
303         HASHMAP_FOREACH(s, m, i) {
304                 if (!value_found[0] && streq(s, val1))
305                         value_found[0] = true;
306                 else if (!value_found[1] && streq(s, val2))
307                         value_found[1] = true;
308                 else if (!value_found[2] && streq(s, val3))
309                         value_found[2] = true;
310                 else if (!value_found[3] && streq(s, val4))
311                         value_found[3] = true;
312         }
313
314         assert_se(m);
315         assert_se(value_found[0] && value_found[1] && value_found[2] && value_found[3]);
316
317         hashmap_free_free(m);
318 }
319
320 static void test_hashmap_foreach_backwards(void) {
321         Hashmap *m;
322         Iterator i;
323         char *val1, *val2, *val3, *val4, *s;
324         bool value_found[] = { false, false, false, false };
325
326         val1 = strdup("my val1");
327         assert_se(val1);
328         val2 = strdup("my val2");
329         assert_se(val2);
330         val3 = strdup("my val3");
331         assert_se(val3);
332         val4 = strdup("my val4");
333         assert_se(val4);
334
335         m = hashmap_new(string_hash_func, string_compare_func);
336         hashmap_put(m, "Key 1", val1);
337         hashmap_put(m, "Key 2", val2);
338         hashmap_put(m, "Key 3", val3);
339         hashmap_put(m, "Key 4", val4);
340
341         HASHMAP_FOREACH_BACKWARDS(s, m, i) {
342                 if (!value_found[0] && streq(s, val1))
343                         value_found[0] = true;
344                 else if (!value_found[1] && streq(s, val2))
345                         value_found[1] = true;
346                 else if (!value_found[2] && streq(s, val3))
347                         value_found[2] = true;
348                 else if (!value_found[3] && streq(s, val4))
349                         value_found[3] = true;
350         }
351
352         assert_se(m);
353         assert_se(value_found[0] && value_found[1] && value_found[2] && value_found[3]);
354
355         hashmap_free_free(m);
356 }
357
358 static void test_hashmap_merge(void) {
359         Hashmap *m;
360         Hashmap *n;
361         char *val1, *val2, *val3, *val4, *r;
362
363         val1 = strdup("my val1");
364         assert_se(val1);
365         val2 = strdup("my val2");
366         assert_se(val2);
367         val3 = strdup("my val3");
368         assert_se(val3);
369         val4 = strdup("my val4");
370         assert_se(val4);
371
372         n = hashmap_new(string_hash_func, string_compare_func);
373         m = hashmap_new(string_hash_func, string_compare_func);
374
375         hashmap_put(m, "Key 1", val1);
376         hashmap_put(m, "Key 2", val2);
377         hashmap_put(n, "Key 3", val3);
378         hashmap_put(n, "Key 4", val4);
379
380         assert_se(hashmap_merge(m, n) == 0);
381         r = hashmap_get(m, "Key 3");
382         assert_se(r && streq(r, "my val3"));
383         r = hashmap_get(m, "Key 4");
384         assert_se(r && streq(r, "my val4"));
385
386         assert_se(n);
387         assert_se(m);
388         hashmap_free(n);
389         hashmap_free_free(m);
390 }
391
392 static void test_hashmap_contains(void) {
393         Hashmap *m;
394         char *val1;
395
396         val1 = strdup("my val");
397         assert_se(val1);
398
399         m = hashmap_new(string_hash_func, string_compare_func);
400
401         assert_se(!hashmap_contains(m, "Key 1"));
402         hashmap_put(m, "Key 1", val1);
403         assert_se(hashmap_contains(m, "Key 1"));
404
405         assert_se(m);
406         hashmap_free_free(m);
407 }
408
409 static void test_hashmap_isempty(void) {
410         Hashmap *m;
411         char *val1;
412
413         val1 = strdup("my val");
414         assert_se(val1);
415
416         m = hashmap_new(string_hash_func, string_compare_func);
417
418         assert_se(hashmap_isempty(m));
419         hashmap_put(m, "Key 1", val1);
420         assert_se(!hashmap_isempty(m));
421
422         assert_se(m);
423         hashmap_free_free(m);
424 }
425
426 static void test_hashmap_size(void) {
427         Hashmap *m;
428         char *val1, *val2, *val3, *val4;
429
430         val1 = strdup("my val");
431         assert_se(val1);
432         val2 = strdup("my val");
433         assert_se(val2);
434         val3 = strdup("my val");
435         assert_se(val3);
436         val4 = strdup("my val");
437         assert_se(val4);
438
439         m = hashmap_new(string_hash_func, string_compare_func);
440
441         hashmap_put(m, "Key 1", val1);
442         hashmap_put(m, "Key 2", val2);
443         hashmap_put(m, "Key 3", val3);
444         hashmap_put(m, "Key 4", val4);
445
446         assert_se(m);
447         assert_se(hashmap_size(m) == 4);
448         hashmap_free_free(m);
449 }
450
451 static void test_hashmap_get(void) {
452         Hashmap *m;
453         char *r;
454         char *val;
455
456         val = strdup("my val");
457         assert_se(val);
458
459         m = hashmap_new(string_hash_func, string_compare_func);
460
461         hashmap_put(m, "Key 1", val);
462
463         r = hashmap_get(m, "Key 1");
464         assert_se(streq(r, val));
465
466         assert_se(m);
467         hashmap_free_free(m);
468 }
469
470 static void test_hashmap_many(void) {
471         Hashmap *h;
472         unsigned i;
473
474 #define N_ENTRIES 100000
475
476         assert_se(h = hashmap_new(NULL, NULL));
477
478         for (i = 1; i < N_ENTRIES*3; i+=3) {
479                 assert_se(hashmap_put(h, UINT_TO_PTR(i), UINT_TO_PTR(i)) >= 0);
480                 assert_se(PTR_TO_UINT(hashmap_get(h, UINT_TO_PTR(i))) == i);
481         }
482
483         for (i = 1; i < N_ENTRIES*3; i++)
484                 assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1));
485
486         log_info("%u <= %u * 0.75 = %g", hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.75);
487
488         assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.75);
489         assert_se(hashmap_size(h) == N_ENTRIES);
490
491         hashmap_free(h);
492 }
493
494 static void test_uint64_compare_func(void) {
495         const uint64_t a = 0x100, b = 0x101;
496
497         assert_se(uint64_compare_func(&a, &a) == 0);
498         assert_se(uint64_compare_func(&a, &b) == -1);
499         assert_se(uint64_compare_func(&b, &a) == 1);
500 }
501
502 static void test_trivial_compare_func(void) {
503         assert_se(trivial_compare_func(INT_TO_PTR('a'), INT_TO_PTR('a')) == 0);
504         assert_se(trivial_compare_func(INT_TO_PTR('a'), INT_TO_PTR('b')) == -1);
505         assert_se(trivial_compare_func(INT_TO_PTR('b'), INT_TO_PTR('a')) == 1);
506 }
507
508 static void test_string_compare_func(void) {
509         assert_se(!string_compare_func("fred", "wilma") == 0);
510         assert_se(string_compare_func("fred", "fred") == 0);
511 }
512
513 int main(int argc, const char *argv[]) {
514         test_hashmap_copy();
515         test_hashmap_get_strv();
516         test_hashmap_move_one();
517         test_hashmap_next();
518         test_hashmap_replace();
519         test_hashmap_update();
520         test_hashmap_put();
521         test_hashmap_ensure_allocated();
522         test_hashmap_foreach();
523         test_hashmap_foreach_backwards();
524         test_hashmap_foreach_key();
525         test_hashmap_contains();
526         test_hashmap_merge();
527         test_hashmap_isempty();
528         test_hashmap_get();
529         test_hashmap_size();
530         test_hashmap_many();
531         test_uint64_compare_func();
532         test_trivial_compare_func();
533         test_string_compare_func();
534 }