1#ifdef HAVE_CONFIG_H
2#include <config.h>
3#endif
4
5#include <check.h>
6#include <pulsecore/hashmap.h>
7
8struct int_entry {
9    int key;
10    int value;
11};
12
13static unsigned int_trivial_hash_func(const void* pa) {
14    int a = *((unsigned*) pa);
15    if (a < 0) {
16        return -a;
17    }
18    return a;
19}
20
21static int int_compare_func(const void* pa, const void* pb) {
22    int a, b;
23    a = *((int*) pa);
24    b = *((int*) pb);
25    if (a < b) {
26        return -1;
27    }
28    if (a == b) {
29        return 0;
30    }
31    return 1;
32}
33
34/* single_key_test exercises basic hashmap functionality on a single key. */
35START_TEST(single_key_test)
36    {
37        pa_hashmap* map;
38        struct int_entry entry;
39        int lookup_key;
40        int put_ret;
41        void* get_ret;
42        unsigned size_ret;
43
44        entry.key = 0;
45        entry.value = 0;
46
47        lookup_key = 0;
48
49        map = pa_hashmap_new(int_trivial_hash_func, int_compare_func);
50
51        if ((put_ret = pa_hashmap_put(map, &entry.key, &entry)) != 0) {
52            ck_abort_msg("Hashmap rejected k=0/v=0; got %d, want %d", put_ret, 0);
53        }
54
55        if ((size_ret = pa_hashmap_size(map)) != 1) {
56            ck_abort_msg("Hashmap reported wrong size; got %u, want 1", size_ret);
57        }
58
59        if ((get_ret = pa_hashmap_get(map, &lookup_key)) != &entry) {
60            ck_abort_msg("Got wrong value from hashmap for k=0; got %p, want %p", get_ret, &entry);
61        }
62
63        if ((put_ret = pa_hashmap_put(map, &entry.key, &entry)) == 0) {
64            ck_abort_msg("Hashmap allowed duplicate key for k=0; got %d, want non-zero", put_ret);
65        }
66
67        if ((size_ret = pa_hashmap_size(map)) != 1) {
68            ck_abort_msg("Hashmap reported wrong size; got %u, want 1", size_ret);
69        }
70
71        if ((get_ret = pa_hashmap_remove(map, &lookup_key)) != &entry) {
72            ck_abort_msg("Hashmap returned wrong value during free; got %p, want %p", get_ret, &entry);
73        }
74
75        if ((size_ret = pa_hashmap_size(map)) != 0) {
76            ck_abort_msg("Hashmap reported wrong size; got %u, want 1", size_ret);
77        }
78
79        pa_hashmap_free(map);
80    }
81END_TEST
82
83/* remove_all_test checks that pa_hashmap_remove_all really removes all entries
84 * from the map.*/
85START_TEST(remove_all_test)
86    {
87        pa_hashmap* map;
88        struct int_entry entries[1000];
89        unsigned size;
90
91        for (int i = 0; i < 1000; i++) {
92            entries[i].key = i;
93            entries[i].value = i;
94        }
95
96        map = pa_hashmap_new(int_trivial_hash_func, int_compare_func);
97
98        for (int i = 0; i < 1000; i++) {
99            pa_hashmap_put(map, &entries[i].key, &entries[i]);
100        }
101
102        if ((size = pa_hashmap_size(map)) != 1000) {
103            ck_abort_msg("Hashmap has wrong size; got %u, want 1000", size);
104        }
105
106        pa_hashmap_remove_all(map);
107
108        if ((size = pa_hashmap_size(map)) != 0) {
109            ck_abort_msg("Hashmap has wrong size; got %u, want 0", size);
110        }
111
112        pa_hashmap_free(map);
113    }
114END_TEST
115
116/* fill_all_buckets hits the hashmap with enough keys to exercise the bucket
117 * linked list for every bucket. */
118START_TEST(fill_all_buckets)
119    {
120        pa_hashmap* map;
121        struct int_entry entries[1000];
122        int lookup_keys[1000]; /* Don't share addresses with insertion keys */
123
124        map = pa_hashmap_new(int_trivial_hash_func, int_compare_func);
125
126        for (int i = 0; i < 1000; i++) {
127            entries[i].key = i;
128            lookup_keys[i] = i;
129            entries[i].value = i;
130        }
131
132        for (int i = 0; i < 1000; i++) {
133            int put_ret;
134            unsigned size_ret;
135
136            if ((put_ret = pa_hashmap_put(map, &entries[i].key, &entries[i])) != 0) {
137                ck_abort_msg("Unexpected failure putting k=%d v=%d into the map", entries[i].key, entries[i].value);
138            }
139
140            if ((size_ret = pa_hashmap_size(map)) != i + 1) {
141                ck_abort_msg("Hashmap reported wrong size; got %u, want %d", size_ret, i);
142            }
143        }
144
145        for (int i = 0; i < 1000; i++) {
146            unsigned size_ret;
147            int* k;
148            struct int_entry* v;
149
150            k = lookup_keys + i;
151
152            v = (struct int_entry*) pa_hashmap_remove(map, k);
153            if (v == NULL) {
154                ck_abort_msg("Hashmap returned NULL for k=%d; wanted nonnull", *k);
155            }
156            if ((*v).value != i) {
157                ck_abort_msg("Hashmap returned wrong value for k=%d; got %d, want %d", *k, (*v).value, i);
158            }
159
160            if ((size_ret = pa_hashmap_size(map)) != 1000 - i - 1) {
161                ck_abort_msg("Hashmap reported wrong size; got %u, want %d", size_ret, 1000 - i);
162            }
163        }
164
165        pa_hashmap_free(map);
166    }
167END_TEST
168
169/* iterate_test exercises the iteration list maintained by the hashtable. */
170START_TEST(iterate_test)
171    {
172        pa_hashmap* map;
173        struct int_entry entries[1000];
174        void* state;
175        struct int_entry* v;
176        int expected;
177
178        for (int i = 0; i < 1000; i++) {
179            entries[i].key = i;
180            entries[i].value = i;
181        }
182
183        map = pa_hashmap_new(int_trivial_hash_func, int_compare_func);
184
185        for (int i = 0; i < 1000; i++) {
186            if (pa_hashmap_put(map, &(entries[i].key), &(entries[i])) != 0) {
187                ck_abort_msg("Unexpected failure putting k=%d v=%d into the map", entries[i].key, entries[i].value);
188            }
189        }
190
191        expected = 0;
192        PA_HASHMAP_FOREACH (v, map, state) {
193            if ((*v).value != expected) {
194                ck_abort_msg("Got bad order iterating over hashmap: got %d, want %d", v->value, expected);
195            }
196            expected++;
197        }
198
199        expected = 999;
200        PA_HASHMAP_FOREACH_BACKWARDS (v, map, state) {
201            if ((*v).value != expected) {
202                ck_abort_msg("Got bad order iterating over hashmap: got %d, want %d", v->value, expected);
203            }
204            expected--;
205        }
206
207        /* Now empty out the hashmap.  The iteration list should be empty. */
208        for(int i = 0; i < 1000; i++) {
209          pa_hashmap_remove(map, &(entries[i].key));
210        }
211
212        PA_HASHMAP_FOREACH(v, map, state) {
213          ck_abort_msg("Iteration over empty map returned entries");
214        }
215
216        /* Now add one element back. The iteration list should only contain this
217         * one element, even though the entry nodes are reused. */
218        if(pa_hashmap_put(map, &(entries[0].key), &(entries[0])) != 0) {
219          ck_abort_msg("Unexpected failure putting k=%d v=%d into the map", entries[0].key, entries[0].value);
220        }
221
222        expected = 0;
223        PA_HASHMAP_FOREACH(v, map, state) {
224           if ((*v).value != expected) {
225                ck_abort_msg("Got bad order iterating over hashmap: got %d, want %d", v->value, expected);
226            }
227           expected++;
228        }
229        if (expected != 1) {
230          ck_abort_msg("Got too many elements while iterating: got %d, want 1", expected);
231        }
232
233        pa_hashmap_free(map);
234    }
235END_TEST
236
237int main(int argc, char** argv) {
238    int failed = 0;
239    Suite* s;
240    TCase* tc;
241    SRunner* sr;
242
243    s = suite_create("HashMap");
244    tc = tcase_create("hashmap");
245    tcase_add_test(tc, single_key_test);
246    tcase_add_test(tc, remove_all_test);
247    tcase_add_test(tc, fill_all_buckets);
248    tcase_add_test(tc, iterate_test);
249    suite_add_tcase(s, tc);
250
251    sr = srunner_create(s);
252    srunner_run_all(sr, CK_NORMAL);
253    failed = srunner_ntests_failed(sr);
254    srunner_free(sr);
255
256    if (failed > 0) {
257        return EXIT_FAILURE;
258    }
259    return EXIT_SUCCESS;
260}
261