1 #ifdef HAVE_CONFIG_H
2 #include <config.h>
3 #endif
4
5 #include <check.h>
6 #include <pulsecore/hashmap.h>
7
8 struct int_entry {
9 int key;
10 int value;
11 };
12
int_trivial_hash_func(const void * pa)13 static 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
int_compare_func(const void * pa,const void * pb)21 static 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. */
START_TEST(single_key_test)35 START_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 }
81 END_TEST
82
83 /* remove_all_test checks that pa_hashmap_remove_all really removes all entries
84 * from the map.*/
START_TEST(remove_all_test)85 START_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 }
114 END_TEST
115
116 /* fill_all_buckets hits the hashmap with enough keys to exercise the bucket
117 * linked list for every bucket. */
START_TEST(fill_all_buckets)118 START_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 }
167 END_TEST
168
169 /* iterate_test exercises the iteration list maintained by the hashtable. */
START_TEST(iterate_test)170 START_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 }
235 END_TEST
236
main(int argc,char ** argv)237 int 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