]> git.proxmox.com Git - ovs.git/blame - tests/test-hindex.c
dpif-netdev: Incremental addition/deletion of PMD threads.
[ovs.git] / tests / test-hindex.c
CommitLineData
822b7f52 1/*
eadd1644 2 * Copyright (c) 2008, 2009, 2010, 2013, 2014 Nicira, Inc.
822b7f52
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
17/* A non-exhaustive test for some of the functions and macros declared in
18 * hindex.h. */
19
20#include <config.h>
3f636c7e 21#undef NDEBUG
822b7f52 22#include "hindex.h"
3f636c7e 23#include <assert.h>
822b7f52
BP
24#include <string.h>
25#include "hash.h"
3f636c7e 26#include "ovstest.h"
b028db44 27#include "random.h"
822b7f52 28#include "util.h"
822b7f52
BP
29
30/* Sample hindex element. */
31struct element {
32 int value;
33 struct hindex_node node;
34};
35
36typedef size_t hash_func(int value);
37
38static int
39compare_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 'hindex' contains exactly the 'n' values in 'values'. */
47static void
48check_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 sort_values = xmalloc(sizeof *sort_values * n);
57 hindex_values = xmalloc(sizeof *sort_values * n);
58
59 i = 0;
60 HINDEX_FOR_EACH (e, node, hindex) {
61 assert(i < n);
62 hindex_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(hindex_values, n, sizeof *hindex_values, compare_ints);
69
70 for (i = 0; i < n; i++) {
71 assert(sort_values[i] == hindex_values[i]);
72 }
73
74 free(hindex_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
81 HINDEX_FOR_EACH_WITH_HASH (e, node, hash(values[i]), hindex) {
82 count += e->value == values[i];
83 }
84 assert(count == 1);
85 }
86
87 /* Check counters. */
88 assert(hindex_is_empty(hindex) == !n);
89 assert(hindex->n_unique <= n);
90}
91
92/* Puts the 'n' values in 'values' into 'elements', and then puts those
93 * elements into 'hindex'. */
94static void
95make_hindex(struct hindex *hindex, struct element elements[],
96 int values[], size_t n, hash_func *hash)
97{
98 size_t i;
99
100 hindex_init(hindex);
101 for (i = 0; i < n; i++) {
102 elements[i].value = i;
103 hindex_insert(hindex, &elements[i].node, hash(elements[i].value));
104 values[i] = i;
105 }
106}
107
108static void
109shuffle(int *p, size_t n)
110{
111 for (; n > 1; n--, p++) {
b028db44 112 int *q = &p[random_range(n)];
822b7f52
BP
113 int tmp = *p;
114 *p = *q;
115 *q = tmp;
116 }
117}
118
119/* Prints the 'n' values in 'values', plus 'name' as a title. */
120static void OVS_UNUSED
121print_ints(const char *name, const int *values, size_t n)
122{
123 size_t i;
124
125 printf("%s:", name);
126 for (i = 0; i < n; i++) {
127 printf(" %d", values[i]);
128 }
129 printf("\n");
130}
131
132/* Prints the values in 'hindex', plus 'name' as a title. */
133static void OVS_UNUSED
134print_hindex(const char *name, struct hindex *hindex)
135{
136 struct element *e;
137
138 printf("%s:", name);
139 HINDEX_FOR_EACH (e, node, hindex) {
34582733 140 printf(" %d(%"PRIuSIZE")", e->value, e->node.hash & hindex->mask);
822b7f52
BP
141 }
142 printf("\n");
143}
144
145static size_t
146unique_hash(int value)
147{
148 return value;
149}
150
151static size_t
152good_hash(int value)
153{
154 return hash_int(value, 0x1234abcd);
155}
156
157static size_t
158constant_hash(int value OVS_UNUSED)
159{
160 return 123;
161}
162
163static size_t
164mod4_hash(int value)
165{
166 return value % 4;
167}
168
169static size_t
170mod3_hash(int value)
171{
172 return value % 3;
173}
174
175static size_t
176mod2_hash(int value)
177{
178 return value % 2;
179}
180
30cc7d29
Z
181static size_t
182multipart_hash(int value)
183{
184 return (mod4_hash(value) << 16) | (constant_hash(value) & 0xFFFF);
185}
186
822b7f52
BP
187/* Tests basic hindex insertion and deletion. */
188static void
189test_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 hindex_init(&hindex);
199 for (i = 0; i < N_ELEMS; i++) {
200 elements[i].value = i;
201 hindex_insert(&hindex, &elements[i].node, hash(i));
202 values[i] = i;
203 check_hindex(&hindex, values, i + 1, hash);
204 }
205 shuffle(values, N_ELEMS);
206 for (i = 0; i < N_ELEMS; i++) {
207 hindex_remove(&hindex, &elements[values[i]].node);
208 check_hindex(&hindex, values + (i + 1), N_ELEMS - (i + 1), hash);
209 }
210 hindex_destroy(&hindex);
211}
212
213/* Tests basic hindex_reserve() and hindex_shrink(). */
214static void
215test_hindex_reserve_shrink(hash_func *hash)
216{
217 enum { N_ELEMS = 32 };
218
219 size_t i;
220
221 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 hindex_init(&hindex);
228 hindex_reserve(&hindex, i);
229 for (j = 0; j < N_ELEMS; j++) {
230 elements[j].value = j;
231 hindex_insert(&hindex, &elements[j].node, hash(j));
232 values[j] = j;
233 check_hindex(&hindex, values, j + 1, hash);
234 }
235 shuffle(values, N_ELEMS);
236 for (j = 0; j < N_ELEMS; j++) {
237 hindex_remove(&hindex, &elements[values[j]].node);
238 hindex_shrink(&hindex);
239 check_hindex(&hindex, values + (j + 1), N_ELEMS - (j + 1), hash);
240 }
241 hindex_destroy(&hindex);
242 }
243}
244
245/* Tests that HINDEX_FOR_EACH_SAFE properly allows for deletion of the current
246 * element of a hindex. */
247static void
248test_hindex_for_each_safe(hash_func *hash)
249{
250 enum { MAX_ELEMS = 10 };
251 size_t n;
252 unsigned long int pattern;
253
254 for (n = 0; n <= MAX_ELEMS; n++) {
255 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 make_hindex(&hindex, elements, values, n, hash);
264
265 i = 0;
266 n_remaining = n;
267 HINDEX_FOR_EACH_SAFE (e, next, node, &hindex) {
268 assert(i < n);
269 if (pattern & (1ul << e->value)) {
270 size_t j;
271 hindex_remove(&hindex, &e->node);
272 for (j = 0; ; j++) {
273 assert(j < n_remaining);
274 if (values[j] == e->value) {
275 values[j] = values[--n_remaining];
276 break;
277 }
278 }
279 }
280 check_hindex(&hindex, values, n_remaining, hash);
281 i++;
282 }
283 assert(i == n);
284
285 for (i = 0; i < n; i++) {
286 if (pattern & (1ul << i)) {
287 n_remaining++;
288 }
289 }
290 assert(n == n_remaining);
291
292 hindex_destroy(&hindex);
293 }
294 }
295}
296
297static void
298run_test(void (*function)(hash_func *))
299{
300 hash_func *hash_funcs[] = {
301 unique_hash,
302 good_hash,
303 constant_hash,
304 mod4_hash,
305 mod3_hash,
306 mod2_hash,
30cc7d29 307 multipart_hash,
822b7f52
BP
308 };
309 size_t i;
310
311 for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
312 function(hash_funcs[i]);
313 printf(".");
314 fflush(stdout);
315 }
316}
317
eadd1644
AZ
318static void
319test_hindex_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
822b7f52
BP
320{
321 run_test(test_hindex_insert_delete);
322 run_test(test_hindex_for_each_safe);
323 run_test(test_hindex_reserve_shrink);
324 printf("\n");
822b7f52
BP
325}
326
eadd1644 327OVSTEST_REGISTER("test-hindex", test_hindex_main);