Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2008, 2009, 2010, 2013, 2014 Nicira, Inc.
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 : :
17 : : /* A non-exhaustive test for some of the functions and macros declared in
18 : : * hmap.h. */
19 : :
20 : : #include <config.h>
21 : : #undef NDEBUG
22 : : #include "openvswitch/hmap.h"
23 : : #include <assert.h>
24 : : #include <string.h>
25 : : #include "hash.h"
26 : : #include "ovstest.h"
27 : : #include "random.h"
28 : : #include "util.h"
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 : 1943159 : compare_ints(const void *a_, const void *b_)
40 : : {
41 : 1943159 : const int *a = a_;
42 : 1943159 : const int *b = b_;
43 [ + + ]: 1943159 : return *a < *b ? -1 : *a > *b;
44 : : }
45 : :
46 : : /* Verifies that 'hmap' contains exactly the 'n' values in 'values'. */
47 : : static void
48 : 62211 : 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 : 62211 : sort_values = xmalloc(sizeof *sort_values * n);
57 : 62211 : hmap_values = xmalloc(sizeof *sort_values * n);
58 : :
59 : 62211 : i = 0;
60 [ + + ][ - + ]: 559635 : HMAP_FOR_EACH (e, node, hmap) {
61 [ - + ]: 497424 : assert(i < n);
62 : 497424 : hmap_values[i++] = e->value;
63 : : }
64 [ - + ]: 62211 : assert(i == n);
65 : :
66 : 62211 : memcpy(sort_values, values, sizeof *sort_values * n);
67 : 62211 : qsort(sort_values, n, sizeof *sort_values, compare_ints);
68 : 62211 : qsort(hmap_values, n, sizeof *hmap_values, compare_ints);
69 : :
70 [ + + ]: 559635 : for (i = 0; i < n; i++) {
71 [ - + ]: 497424 : assert(sort_values[i] == hmap_values[i]);
72 : : }
73 : :
74 : 62211 : free(hmap_values);
75 : 62211 : free(sort_values);
76 : :
77 : : /* Check that all the values are there in lookup. */
78 [ + + ]: 559635 : for (i = 0; i < n; i++) {
79 : 497424 : size_t count = 0;
80 : :
81 [ + + ][ - + ]: 3084806 : HMAP_FOR_EACH_WITH_HASH (e, node, hash(values[i]), hmap) {
82 : 2587382 : count += e->value == values[i];
83 : : }
84 [ - + ]: 497424 : assert(count == 1);
85 : : }
86 : :
87 : : /* Check counters. */
88 [ - + ]: 62211 : assert(hmap_is_empty(hmap) == !n);
89 [ - + ]: 62211 : assert(hmap_count(hmap) == n);
90 : 62211 : }
91 : :
92 : : /* Puts the 'n' values in 'values' into 'elements', and then puts those
93 : : * elements into 'hmap'. */
94 : : static void
95 : 6174 : make_hmap(struct hmap *hmap, struct element elements[],
96 : : int values[], size_t n, hash_func *hash)
97 : : {
98 : : size_t i;
99 : :
100 : 6174 : hmap_init(hmap);
101 [ + + ]: 61641 : for (i = 0; i < n; i++) {
102 : 55467 : elements[i].value = i;
103 : 55467 : hmap_insert(hmap, &elements[i].node, hash(elements[i].value));
104 : 55467 : values[i] = i;
105 : : }
106 : 6174 : }
107 : :
108 : : static void
109 : 99 : shuffle(int *p, size_t n)
110 : : {
111 [ + + ]: 3372 : for (; n > 1; n--, p++) {
112 : 3273 : int *q = &p[random_range(n)];
113 : 3273 : int tmp = *p;
114 : 3273 : *p = *q;
115 : 3273 : *q = tmp;
116 : : }
117 : 99 : }
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);
127 : : HMAP_FOR_EACH (e, node, hmap) {
128 : : printf(" %d(%"PRIuSIZE")", e->value, e->node.hash & hmap->mask);
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 : 185421 : identity_hash(int value)
149 : : {
150 : 185421 : return value;
151 : : }
152 : :
153 : : static size_t
154 : 185421 : good_hash(int value)
155 : : {
156 : 185421 : return hash_int(value, 0x1234abcd);
157 : : }
158 : :
159 : : static size_t
160 : 185421 : constant_hash(int value OVS_UNUSED)
161 : : {
162 : 185421 : return 123;
163 : : }
164 : :
165 : : /* Tests basic hmap insertion and deletion. */
166 : : static void
167 : 3 : 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 : 3 : hmap_init(&hmap);
177 [ + + ]: 303 : for (i = 0; i < N_ELEMS; i++) {
178 : 300 : elements[i].value = i;
179 : 300 : hmap_insert(&hmap, &elements[i].node, hash(i));
180 : 300 : values[i] = i;
181 : 300 : check_hmap(&hmap, values, i + 1, hash);
182 : : }
183 : 3 : shuffle(values, N_ELEMS);
184 [ + + ]: 303 : for (i = 0; i < N_ELEMS; i++) {
185 : 300 : hmap_remove(&hmap, &elements[values[i]].node);
186 : 300 : check_hmap(&hmap, values + (i + 1), N_ELEMS - (i + 1), hash);
187 : : }
188 : 3 : hmap_destroy(&hmap);
189 : 3 : }
190 : :
191 : : /* Tests basic hmap_reserve() and hmap_shrink(). */
192 : : static void
193 : 3 : test_hmap_reserve_shrink(hash_func *hash)
194 : : {
195 : : enum { N_ELEMS = 32 };
196 : :
197 : : size_t i;
198 : :
199 [ + + ]: 99 : 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 : 96 : hmap_init(&hmap);
206 : 96 : hmap_reserve(&hmap, i);
207 [ + + ]: 3168 : for (j = 0; j < N_ELEMS; j++) {
208 : 3072 : elements[j].value = j;
209 : 3072 : hmap_insert(&hmap, &elements[j].node, hash(j));
210 : 3072 : values[j] = j;
211 : 3072 : check_hmap(&hmap, values, j + 1, hash);
212 : : }
213 : 96 : shuffle(values, N_ELEMS);
214 [ + + ]: 3168 : for (j = 0; j < N_ELEMS; j++) {
215 : 3072 : hmap_remove(&hmap, &elements[values[j]].node);
216 : 3072 : hmap_shrink(&hmap);
217 : 3072 : check_hmap(&hmap, values + (j + 1), N_ELEMS - (j + 1), hash);
218 : : }
219 : 96 : hmap_destroy(&hmap);
220 : : }
221 : 3 : }
222 : :
223 : : /* Tests that HMAP_FOR_EACH_SAFE properly allows for deletion of the current
224 : : * element of a hmap. */
225 : : static void
226 : 3 : 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 [ + + ]: 36 : for (n = 0; n <= MAX_ELEMS; n++) {
233 [ + + ]: 6174 : 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 : 6141 : make_hmap(&hmap, elements, values, n, hash);
242 : :
243 : 6141 : i = 0;
244 : 6141 : n_remaining = n;
245 [ + + ][ - + ]: 61443 : HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
[ + + ]
246 [ - + ]: 55302 : assert(i < n);
247 [ + + ]: 55302 : if (pattern & (1ul << e->value)) {
248 : : size_t j;
249 : 27651 : hmap_remove(&hmap, &e->node);
250 : 27651 : for (j = 0; ; j++) {
251 [ - + ]: 116026 : assert(j < n_remaining);
252 [ + + ]: 116026 : if (values[j] == e->value) {
253 : 27651 : values[j] = values[--n_remaining];
254 : 27651 : break;
255 : : }
256 : 88375 : }
257 : : }
258 : 55302 : check_hmap(&hmap, values, n_remaining, hash);
259 : 55302 : i++;
260 : : }
261 [ - + ]: 6141 : assert(i == n);
262 : :
263 [ + + ]: 61443 : for (i = 0; i < n; i++) {
264 [ + + ]: 55302 : if (pattern & (1ul << i)) {
265 : 27651 : n_remaining++;
266 : : }
267 : : }
268 [ - + ]: 6141 : assert(n == n_remaining);
269 : :
270 : 6141 : hmap_destroy(&hmap);
271 : : }
272 : : }
273 : 3 : }
274 : :
275 : : /* Tests that HMAP_FOR_EACH_POP removes every element of a hmap. */
276 : : static void
277 : 3 : test_hmap_for_each_pop(hash_func *hash)
278 : : {
279 : : enum { MAX_ELEMS = 10 };
280 : : size_t n;
281 : :
282 [ + + ]: 36 : 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 : 33 : make_hmap(&hmap, elements, values, n, hash);
290 : :
291 : 33 : i = 0;
292 : 33 : n_remaining = n;
293 [ + + ][ - + ]: 198 : HMAP_FOR_EACH_POP (e, node, &hmap) {
[ + + ]
294 : : size_t j;
295 : :
296 [ - + ]: 165 : assert(i < n);
297 : :
298 : 165 : for (j = 0; ; j++) {
299 [ - + ]: 408 : assert(j < n_remaining);
300 [ + + ]: 408 : if (values[j] == e->value) {
301 : 165 : values[j] = values[--n_remaining];
302 : 165 : break;
303 : : }
304 : 243 : }
305 : : /* Trash the element memory (including the hmap node) */
306 : 165 : memset(e, 0, sizeof *e);
307 : 165 : check_hmap(&hmap, values, n_remaining, hash);
308 : 165 : i++;
309 : : }
310 [ - + ]: 33 : assert(i == n);
311 : :
312 : 33 : hmap_destroy(&hmap);
313 : : }
314 : 3 : }
315 : :
316 : : static void
317 : 4 : run_test(void (*function)(hash_func *))
318 : : {
319 : 4 : hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
320 : : size_t i;
321 : :
322 [ + + ]: 16 : for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
323 : 12 : function(hash_funcs[i]);
324 : 12 : printf(".");
325 : 12 : fflush(stdout);
326 : : }
327 : 4 : }
328 : :
329 : : static void
330 : 1 : test_hmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
331 : : {
332 : 1 : run_test(test_hmap_insert_delete);
333 : 1 : run_test(test_hmap_for_each_safe);
334 : 1 : run_test(test_hmap_reserve_shrink);
335 : 1 : run_test(test_hmap_for_each_pop);
336 : 1 : printf("\n");
337 : 1 : }
338 : :
339 : 1176 : OVSTEST_REGISTER("test-hmap", test_hmap_main);
|
