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 : : * hindex.h. */
19 : :
20 : : #include <config.h>
21 : : #undef NDEBUG
22 : : #include "hindex.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 hindex element. */
31 : : struct element {
32 : : int value;
33 : : struct hindex_node node;
34 : : };
35 : :
36 : : typedef size_t hash_func(int value);
37 : :
38 : : static int
39 : 4688642 : compare_ints(const void *a_, const void *b_)
40 : : {
41 : 4688642 : const int *a = a_;
42 : 4688642 : const int *b = b_;
43 [ + + ]: 4688642 : return *a < *b ? -1 : *a > *b;
44 : : }
45 : :
46 : : /* Verifies that 'hindex' contains exactly the 'n' values in 'values'. */
47 : : static void
48 : 144774 : check_hindex(struct hindex *hindex, const int values[], size_t n,
49 : : hash_func *hash)
50 : : {
51 : : int *sort_values, *hindex_values;
52 : : struct element *e;
53 : : size_t i;
54 : :
55 : : /* Check that all the values are there in iteration. */
56 : 144774 : sort_values = xmalloc(sizeof *sort_values * n);
57 : 144774 : hindex_values = xmalloc(sizeof *sort_values * n);
58 : :
59 : 144774 : i = 0;
60 [ + + ]: 1304275 : HINDEX_FOR_EACH (e, node, hindex) {
61 [ - + ]: 1159501 : assert(i < n);
62 : 1159501 : hindex_values[i++] = e->value;
63 : : }
64 [ - + ]: 144774 : assert(i == n);
65 : :
66 : 144774 : memcpy(sort_values, values, sizeof *sort_values * n);
67 : 144774 : qsort(sort_values, n, sizeof *sort_values, compare_ints);
68 : 144774 : qsort(hindex_values, n, sizeof *hindex_values, compare_ints);
69 : :
70 [ + + ]: 1304275 : for (i = 0; i < n; i++) {
71 [ - + ]: 1159501 : assert(sort_values[i] == hindex_values[i]);
72 : : }
73 : :
74 : 144774 : free(hindex_values);
75 : 144774 : free(sort_values);
76 : :
77 : : /* Check that all the values are there in lookup. */
78 [ + + ]: 1304275 : for (i = 0; i < n; i++) {
79 : 1159501 : size_t count = 0;
80 : :
81 [ + + ]: 6900582 : HINDEX_FOR_EACH_WITH_HASH (e, node, hash(values[i]), hindex) {
82 : 5741081 : count += e->value == values[i];
83 : : }
84 [ - + ]: 1159501 : assert(count == 1);
85 : : }
86 : :
87 : : /* Check counters. */
88 [ - + ]: 144774 : assert(hindex_is_empty(hindex) == !n);
89 [ - + ]: 144774 : assert(hindex->n_unique <= n);
90 : 144774 : }
91 : :
92 : : /* Puts the 'n' values in 'values' into 'elements', and then puts those
93 : : * elements into 'hindex'. */
94 : : static void
95 : 14329 : make_hindex(struct hindex *hindex, struct element elements[],
96 : : int values[], size_t n, hash_func *hash)
97 : : {
98 : : size_t i;
99 : :
100 : 14329 : hindex_init(hindex);
101 [ + + ]: 143367 : for (i = 0; i < n; i++) {
102 : 129038 : elements[i].value = i;
103 : 129038 : hindex_insert(hindex, &elements[i].node, hash(elements[i].value));
104 : 129038 : values[i] = i;
105 : : }
106 : 14329 : }
107 : :
108 : : static void
109 : 231 : shuffle(int *p, size_t n)
110 : : {
111 [ + + ]: 7868 : for (; n > 1; n--, p++) {
112 : 7637 : int *q = &p[random_range(n)];
113 : 7637 : int tmp = *p;
114 : 7637 : *p = *q;
115 : 7637 : *q = tmp;
116 : : }
117 : 231 : }
118 : :
119 : : /* Prints the 'n' values in 'values', plus 'name' as a title. */
120 : : static void OVS_UNUSED
121 : 0 : print_ints(const char *name, const int *values, size_t n)
122 : : {
123 : : size_t i;
124 : :
125 : 0 : printf("%s:", name);
126 [ # # ]: 0 : for (i = 0; i < n; i++) {
127 : 0 : printf(" %d", values[i]);
128 : : }
129 : 0 : printf("\n");
130 : 0 : }
131 : :
132 : : /* Prints the values in 'hindex', plus 'name' as a title. */
133 : : static void OVS_UNUSED
134 : 0 : print_hindex(const char *name, struct hindex *hindex)
135 : : {
136 : : struct element *e;
137 : :
138 : 0 : printf("%s:", name);
139 [ # # ]: 0 : HINDEX_FOR_EACH (e, node, hindex) {
140 : 0 : printf(" %d(%"PRIuSIZE")", e->value, e->node.hash & hindex->mask);
141 : : }
142 : 0 : printf("\n");
143 : 0 : }
144 : :
145 : : static size_t
146 : 185201 : unique_hash(int value)
147 : : {
148 : 185201 : return value;
149 : : }
150 : :
151 : : static size_t
152 : 185201 : good_hash(int value)
153 : : {
154 : 185201 : return hash_int(value, 0x1234abcd);
155 : : }
156 : :
157 : : static size_t
158 : 370402 : constant_hash(int value OVS_UNUSED)
159 : : {
160 : 370402 : return 123;
161 : : }
162 : :
163 : : static size_t
164 : 370402 : mod4_hash(int value)
165 : : {
166 : 370402 : return value % 4;
167 : : }
168 : :
169 : : static size_t
170 : 185201 : mod3_hash(int value)
171 : : {
172 : 185201 : return value % 3;
173 : : }
174 : :
175 : : static size_t
176 : 185201 : mod2_hash(int value)
177 : : {
178 : 185201 : return value % 2;
179 : : }
180 : :
181 : : static size_t
182 : 185201 : multipart_hash(int value)
183 : : {
184 : 185201 : return (mod4_hash(value) << 16) | (constant_hash(value) & 0xFFFF);
185 : : }
186 : :
187 : : /* Tests basic hindex insertion and deletion. */
188 : : static void
189 : 7 : test_hindex_insert_delete(hash_func *hash)
190 : : {
191 : : enum { N_ELEMS = 100 };
192 : :
193 : : struct element elements[N_ELEMS];
194 : : int values[N_ELEMS];
195 : : struct hindex hindex;
196 : : size_t i;
197 : :
198 : 7 : hindex_init(&hindex);
199 [ + + ]: 707 : for (i = 0; i < N_ELEMS; i++) {
200 : 700 : elements[i].value = i;
201 : 700 : hindex_insert(&hindex, &elements[i].node, hash(i));
202 : 700 : values[i] = i;
203 : 700 : check_hindex(&hindex, values, i + 1, hash);
204 : : }
205 : 7 : shuffle(values, N_ELEMS);
206 [ + + ]: 707 : for (i = 0; i < N_ELEMS; i++) {
207 : 700 : hindex_remove(&hindex, &elements[values[i]].node);
208 : 700 : check_hindex(&hindex, values + (i + 1), N_ELEMS - (i + 1), hash);
209 : : }
210 : 7 : hindex_destroy(&hindex);
211 : 7 : }
212 : :
213 : : /* Tests basic hindex_reserve() and hindex_shrink(). */
214 : : static void
215 : 7 : test_hindex_reserve_shrink(hash_func *hash)
216 : : {
217 : : enum { N_ELEMS = 32 };
218 : :
219 : : size_t i;
220 : :
221 [ + + ]: 231 : for (i = 0; i < N_ELEMS; i++) {
222 : : struct element elements[N_ELEMS];
223 : : int values[N_ELEMS];
224 : : struct hindex hindex;
225 : : size_t j;
226 : :
227 : 224 : hindex_init(&hindex);
228 : 224 : hindex_reserve(&hindex, i);
229 [ + + ]: 7392 : for (j = 0; j < N_ELEMS; j++) {
230 : 7168 : elements[j].value = j;
231 : 7168 : hindex_insert(&hindex, &elements[j].node, hash(j));
232 : 7168 : values[j] = j;
233 : 7168 : check_hindex(&hindex, values, j + 1, hash);
234 : : }
235 : 224 : shuffle(values, N_ELEMS);
236 [ + + ]: 7392 : for (j = 0; j < N_ELEMS; j++) {
237 : 7168 : hindex_remove(&hindex, &elements[values[j]].node);
238 : 7168 : hindex_shrink(&hindex);
239 : 7168 : check_hindex(&hindex, values + (j + 1), N_ELEMS - (j + 1), hash);
240 : : }
241 : 224 : hindex_destroy(&hindex);
242 : : }
243 : 7 : }
244 : :
245 : : /* Tests that HINDEX_FOR_EACH_SAFE properly allows for deletion of the current
246 : : * element of a hindex. */
247 : : static void
248 : 7 : test_hindex_for_each_safe(hash_func *hash)
249 : : {
250 : : enum { MAX_ELEMS = 10 };
251 : : size_t n;
252 : : unsigned long int pattern;
253 : :
254 [ + + ]: 84 : for (n = 0; n <= MAX_ELEMS; n++) {
255 [ + + ]: 14406 : for (pattern = 0; pattern < 1ul << n; pattern++) {
256 : : struct element elements[MAX_ELEMS];
257 : : int values[MAX_ELEMS];
258 : : struct hindex hindex;
259 : : struct element *e, *next;
260 : : size_t n_remaining;
261 : : int i;
262 : :
263 : 14329 : make_hindex(&hindex, elements, values, n, hash);
264 : :
265 : 14329 : i = 0;
266 : 14329 : n_remaining = n;
267 [ + + ][ + + ]: 143367 : HINDEX_FOR_EACH_SAFE (e, next, node, &hindex) {
268 [ - + ]: 129038 : assert(i < n);
269 [ + + ]: 129038 : if (pattern & (1ul << e->value)) {
270 : : size_t j;
271 : 64519 : hindex_remove(&hindex, &e->node);
272 : 64519 : for (j = 0; ; j++) {
273 [ - + ]: 259794 : assert(j < n_remaining);
274 [ + + ]: 259794 : if (values[j] == e->value) {
275 : 64519 : values[j] = values[--n_remaining];
276 : 64519 : break;
277 : : }
278 : 195275 : }
279 : : }
280 : 129038 : check_hindex(&hindex, values, n_remaining, hash);
281 : 129038 : i++;
282 : : }
283 [ - + ]: 14329 : assert(i == n);
284 : :
285 [ + + ]: 143367 : for (i = 0; i < n; i++) {
286 [ + + ]: 129038 : if (pattern & (1ul << i)) {
287 : 64519 : n_remaining++;
288 : : }
289 : : }
290 [ - + ]: 14329 : assert(n == n_remaining);
291 : :
292 : 14329 : hindex_destroy(&hindex);
293 : : }
294 : : }
295 : 7 : }
296 : :
297 : : static void
298 : 3 : run_test(void (*function)(hash_func *))
299 : : {
300 : 3 : hash_func *hash_funcs[] = {
301 : : unique_hash,
302 : : good_hash,
303 : : constant_hash,
304 : : mod4_hash,
305 : : mod3_hash,
306 : : mod2_hash,
307 : : multipart_hash,
308 : : };
309 : : size_t i;
310 : :
311 [ + + ]: 24 : for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
312 : 21 : function(hash_funcs[i]);
313 : 21 : printf(".");
314 : 21 : fflush(stdout);
315 : : }
316 : 3 : }
317 : :
318 : : static void
319 : 1 : test_hindex_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
320 : : {
321 : 1 : run_test(test_hindex_insert_delete);
322 : 1 : run_test(test_hindex_for_each_safe);
323 : 1 : run_test(test_hindex_reserve_shrink);
324 : 1 : printf("\n");
325 : 1 : }
326 : :
327 : 1176 : OVSTEST_REGISTER("test-hindex", test_hindex_main);
|
