]>
Commit | Line | Data |
---|---|---|
a14bc59f | 1 | /* |
eadd1644 | 2 | * Copyright (c) 2008, 2009, 2010, 2013, 2014 Nicira, Inc. |
a14bc59f BP |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); | |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at: | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
15 | */ | |
16 | ||
064af421 BP |
17 | /* A non-exhaustive test for some of the functions and macros declared in |
18 | * hmap.h. */ | |
19 | ||
20 | #include <config.h> | |
3f636c7e | 21 | #undef NDEBUG |
ee89ea7b | 22 | #include "openvswitch/hmap.h" |
3f636c7e | 23 | #include <assert.h> |
064af421 BP |
24 | #include <string.h> |
25 | #include "hash.h" | |
3f636c7e | 26 | #include "ovstest.h" |
b028db44 | 27 | #include "random.h" |
064af421 | 28 | #include "util.h" |
064af421 BP |
29 | |
30 | /* Sample hmap element. */ | |
31 | struct element { | |
32 | int value; | |
33 | struct hmap_node node; | |
34 | }; | |
35 | ||
36 | typedef size_t hash_func(int value); | |
37 | ||
38 | static int | |
39 | compare_ints(const void *a_, const void *b_) | |
40 | { | |
41 | const int *a = a_; | |
42 | const int *b = b_; | |
43 | return *a < *b ? -1 : *a > *b; | |
44 | } | |
45 | ||
46 | /* Verifies that 'hmap' contains exactly the 'n' values in 'values'. */ | |
47 | static void | |
48 | check_hmap(struct hmap *hmap, const int values[], size_t n, | |
49 | hash_func *hash) | |
50 | { | |
51 | int *sort_values, *hmap_values; | |
52 | struct element *e; | |
53 | size_t i; | |
54 | ||
55 | /* Check that all the values are there in iteration. */ | |
56 | sort_values = xmalloc(sizeof *sort_values * n); | |
57 | hmap_values = xmalloc(sizeof *sort_values * n); | |
58 | ||
59 | i = 0; | |
4e8e4213 | 60 | HMAP_FOR_EACH (e, node, hmap) { |
064af421 BP |
61 | assert(i < n); |
62 | hmap_values[i++] = e->value; | |
63 | } | |
64 | assert(i == n); | |
65 | ||
66 | memcpy(sort_values, values, sizeof *sort_values * n); | |
67 | qsort(sort_values, n, sizeof *sort_values, compare_ints); | |
68 | qsort(hmap_values, n, sizeof *hmap_values, compare_ints); | |
69 | ||
70 | for (i = 0; i < n; i++) { | |
71 | assert(sort_values[i] == hmap_values[i]); | |
72 | } | |
73 | ||
74 | free(hmap_values); | |
75 | free(sort_values); | |
76 | ||
77 | /* Check that all the values are there in lookup. */ | |
78 | for (i = 0; i < n; i++) { | |
79 | size_t count = 0; | |
80 | ||
4e8e4213 | 81 | HMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), hmap) { |
064af421 BP |
82 | count += e->value == values[i]; |
83 | } | |
84 | assert(count == 1); | |
85 | } | |
86 | ||
87 | /* Check counters. */ | |
88 | assert(hmap_is_empty(hmap) == !n); | |
89 | assert(hmap_count(hmap) == n); | |
90 | } | |
91 | ||
92 | /* Puts the 'n' values in 'values' into 'elements', and then puts those | |
93 | * elements into 'hmap'. */ | |
94 | static void | |
95 | make_hmap(struct hmap *hmap, struct element elements[], | |
96 | int values[], size_t n, hash_func *hash) | |
97 | { | |
98 | size_t i; | |
99 | ||
100 | hmap_init(hmap); | |
101 | for (i = 0; i < n; i++) { | |
102 | elements[i].value = i; | |
103 | hmap_insert(hmap, &elements[i].node, hash(elements[i].value)); | |
104 | values[i] = i; | |
105 | } | |
106 | } | |
107 | ||
108 | static void | |
109 | shuffle(int *p, size_t n) | |
110 | { | |
111 | for (; n > 1; n--, p++) { | |
b028db44 | 112 | int *q = &p[random_range(n)]; |
064af421 BP |
113 | int tmp = *p; |
114 | *p = *q; | |
115 | *q = tmp; | |
116 | } | |
117 | } | |
118 | ||
119 | #if 0 | |
120 | /* Prints the values in 'hmap', plus 'name' as a title. */ | |
121 | static void | |
122 | print_hmap(const char *name, struct hmap *hmap) | |
123 | { | |
124 | struct element *e; | |
125 | ||
126 | printf("%s:", name); | |
4e8e4213 | 127 | HMAP_FOR_EACH (e, node, hmap) { |
34582733 | 128 | printf(" %d(%"PRIuSIZE")", e->value, e->node.hash & hmap->mask); |
064af421 BP |
129 | } |
130 | printf("\n"); | |
131 | } | |
132 | ||
133 | /* Prints the 'n' values in 'values', plus 'name' as a title. */ | |
134 | static void | |
135 | print_ints(const char *name, const int *values, size_t n) | |
136 | { | |
137 | size_t i; | |
138 | ||
139 | printf("%s:", name); | |
140 | for (i = 0; i < n; i++) { | |
141 | printf(" %d", values[i]); | |
142 | } | |
143 | printf("\n"); | |
144 | } | |
145 | #endif | |
146 | ||
147 | static size_t | |
148 | identity_hash(int value) | |
149 | { | |
150 | return value; | |
151 | } | |
152 | ||
153 | static size_t | |
154 | good_hash(int value) | |
155 | { | |
156 | return hash_int(value, 0x1234abcd); | |
157 | } | |
158 | ||
159 | static size_t | |
67a4917b | 160 | constant_hash(int value OVS_UNUSED) |
064af421 BP |
161 | { |
162 | return 123; | |
163 | } | |
164 | ||
165 | /* Tests basic hmap insertion and deletion. */ | |
166 | static void | |
167 | test_hmap_insert_delete(hash_func *hash) | |
168 | { | |
169 | enum { N_ELEMS = 100 }; | |
170 | ||
171 | struct element elements[N_ELEMS]; | |
172 | int values[N_ELEMS]; | |
173 | struct hmap hmap; | |
174 | size_t i; | |
175 | ||
176 | hmap_init(&hmap); | |
177 | for (i = 0; i < N_ELEMS; i++) { | |
178 | elements[i].value = i; | |
179 | hmap_insert(&hmap, &elements[i].node, hash(i)); | |
180 | values[i] = i; | |
181 | check_hmap(&hmap, values, i + 1, hash); | |
182 | } | |
183 | shuffle(values, N_ELEMS); | |
184 | for (i = 0; i < N_ELEMS; i++) { | |
185 | hmap_remove(&hmap, &elements[values[i]].node); | |
186 | check_hmap(&hmap, values + (i + 1), N_ELEMS - (i + 1), hash); | |
187 | } | |
188 | hmap_destroy(&hmap); | |
189 | } | |
190 | ||
191 | /* Tests basic hmap_reserve() and hmap_shrink(). */ | |
192 | static void | |
193 | test_hmap_reserve_shrink(hash_func *hash) | |
194 | { | |
195 | enum { N_ELEMS = 32 }; | |
196 | ||
197 | size_t i; | |
198 | ||
199 | for (i = 0; i < N_ELEMS; i++) { | |
200 | struct element elements[N_ELEMS]; | |
201 | int values[N_ELEMS]; | |
202 | struct hmap hmap; | |
203 | size_t j; | |
204 | ||
205 | hmap_init(&hmap); | |
206 | hmap_reserve(&hmap, i); | |
207 | for (j = 0; j < N_ELEMS; j++) { | |
208 | elements[j].value = j; | |
209 | hmap_insert(&hmap, &elements[j].node, hash(j)); | |
210 | values[j] = j; | |
211 | check_hmap(&hmap, values, j + 1, hash); | |
212 | } | |
213 | shuffle(values, N_ELEMS); | |
214 | for (j = 0; j < N_ELEMS; j++) { | |
215 | hmap_remove(&hmap, &elements[values[j]].node); | |
216 | hmap_shrink(&hmap); | |
217 | check_hmap(&hmap, values + (j + 1), N_ELEMS - (j + 1), hash); | |
218 | } | |
219 | hmap_destroy(&hmap); | |
220 | } | |
221 | } | |
222 | ||
223 | /* Tests that HMAP_FOR_EACH_SAFE properly allows for deletion of the current | |
224 | * element of a hmap. */ | |
225 | static void | |
226 | test_hmap_for_each_safe(hash_func *hash) | |
227 | { | |
228 | enum { MAX_ELEMS = 10 }; | |
229 | size_t n; | |
230 | unsigned long int pattern; | |
231 | ||
232 | for (n = 0; n <= MAX_ELEMS; n++) { | |
233 | for (pattern = 0; pattern < 1ul << n; pattern++) { | |
234 | struct element elements[MAX_ELEMS]; | |
235 | int values[MAX_ELEMS]; | |
236 | struct hmap hmap; | |
237 | struct element *e, *next; | |
238 | size_t n_remaining; | |
239 | int i; | |
240 | ||
241 | make_hmap(&hmap, elements, values, n, hash); | |
242 | ||
243 | i = 0; | |
244 | n_remaining = n; | |
4e8e4213 | 245 | HMAP_FOR_EACH_SAFE (e, next, node, &hmap) { |
064af421 BP |
246 | assert(i < n); |
247 | if (pattern & (1ul << e->value)) { | |
248 | size_t j; | |
249 | hmap_remove(&hmap, &e->node); | |
250 | for (j = 0; ; j++) { | |
251 | assert(j < n_remaining); | |
252 | if (values[j] == e->value) { | |
253 | values[j] = values[--n_remaining]; | |
254 | break; | |
255 | } | |
256 | } | |
257 | } | |
258 | check_hmap(&hmap, values, n_remaining, hash); | |
259 | i++; | |
260 | } | |
261 | assert(i == n); | |
262 | ||
263 | for (i = 0; i < n; i++) { | |
264 | if (pattern & (1ul << i)) { | |
265 | n_remaining++; | |
266 | } | |
267 | } | |
268 | assert(n == n_remaining); | |
269 | ||
270 | hmap_destroy(&hmap); | |
271 | } | |
272 | } | |
273 | } | |
274 | ||
4ec3d7c7 DDP |
275 | /* Tests that HMAP_FOR_EACH_POP removes every element of a hmap. */ |
276 | static void | |
277 | test_hmap_for_each_pop(hash_func *hash) | |
278 | { | |
279 | enum { MAX_ELEMS = 10 }; | |
280 | size_t n; | |
281 | ||
282 | for (n = 0; n <= MAX_ELEMS; n++) { | |
283 | struct element elements[MAX_ELEMS]; | |
284 | int values[MAX_ELEMS]; | |
285 | struct hmap hmap; | |
286 | struct element *e; | |
287 | size_t n_remaining, i; | |
288 | ||
289 | make_hmap(&hmap, elements, values, n, hash); | |
290 | ||
291 | i = 0; | |
292 | n_remaining = n; | |
293 | HMAP_FOR_EACH_POP (e, node, &hmap) { | |
294 | size_t j; | |
295 | ||
296 | assert(i < n); | |
297 | ||
298 | for (j = 0; ; j++) { | |
299 | assert(j < n_remaining); | |
300 | if (values[j] == e->value) { | |
301 | values[j] = values[--n_remaining]; | |
302 | break; | |
303 | } | |
304 | } | |
305 | /* Trash the element memory (including the hmap node) */ | |
306 | memset(e, 0, sizeof *e); | |
307 | check_hmap(&hmap, values, n_remaining, hash); | |
308 | i++; | |
309 | } | |
310 | assert(i == n); | |
311 | ||
312 | hmap_destroy(&hmap); | |
313 | } | |
314 | } | |
315 | ||
064af421 BP |
316 | static void |
317 | run_test(void (*function)(hash_func *)) | |
318 | { | |
319 | hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash }; | |
320 | size_t i; | |
321 | ||
322 | for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) { | |
323 | function(hash_funcs[i]); | |
324 | printf("."); | |
325 | fflush(stdout); | |
326 | } | |
327 | } | |
328 | ||
eadd1644 AZ |
329 | static void |
330 | test_hmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
064af421 BP |
331 | { |
332 | run_test(test_hmap_insert_delete); | |
333 | run_test(test_hmap_for_each_safe); | |
334 | run_test(test_hmap_reserve_shrink); | |
4ec3d7c7 | 335 | run_test(test_hmap_for_each_pop); |
064af421 | 336 | printf("\n"); |
064af421 BP |
337 | } |
338 | ||
eadd1644 | 339 | OVSTEST_REGISTER("test-hmap", test_hmap_main); |