2 * Copyright (c) 2008, 2009, 2010, 2013 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 /* A non-exhaustive test for some of the functions and macros declared in
29 /* Sample hindex element. */
32 struct hindex_node node
;
35 typedef size_t hash_func(int value
);
38 compare_ints(const void *a_
, const void *b_
)
42 return *a
< *b
? -1 : *a
> *b
;
45 /* Verifies that 'hindex' contains exactly the 'n' values in 'values'. */
47 check_hindex(struct hindex
*hindex
, const int values
[], size_t n
,
50 int *sort_values
, *hindex_values
;
54 /* Check that all the values are there in iteration. */
55 sort_values
= xmalloc(sizeof *sort_values
* n
);
56 hindex_values
= xmalloc(sizeof *sort_values
* n
);
59 HINDEX_FOR_EACH (e
, node
, hindex
) {
61 hindex_values
[i
++] = e
->value
;
65 memcpy(sort_values
, values
, sizeof *sort_values
* n
);
66 qsort(sort_values
, n
, sizeof *sort_values
, compare_ints
);
67 qsort(hindex_values
, n
, sizeof *hindex_values
, compare_ints
);
69 for (i
= 0; i
< n
; i
++) {
70 assert(sort_values
[i
] == hindex_values
[i
]);
76 /* Check that all the values are there in lookup. */
77 for (i
= 0; i
< n
; i
++) {
80 HINDEX_FOR_EACH_WITH_HASH (e
, node
, hash(values
[i
]), hindex
) {
81 count
+= e
->value
== values
[i
];
87 assert(hindex_is_empty(hindex
) == !n
);
88 assert(hindex
->n_unique
<= n
);
91 /* Puts the 'n' values in 'values' into 'elements', and then puts those
92 * elements into 'hindex'. */
94 make_hindex(struct hindex
*hindex
, struct element elements
[],
95 int values
[], size_t n
, hash_func
*hash
)
100 for (i
= 0; i
< n
; i
++) {
101 elements
[i
].value
= i
;
102 hindex_insert(hindex
, &elements
[i
].node
, hash(elements
[i
].value
));
108 shuffle(int *p
, size_t n
)
110 for (; n
> 1; n
--, p
++) {
111 int *q
= &p
[rand() % n
];
118 /* Prints the 'n' values in 'values', plus 'name' as a title. */
119 static void OVS_UNUSED
120 print_ints(const char *name
, const int *values
, size_t n
)
125 for (i
= 0; i
< n
; i
++) {
126 printf(" %d", values
[i
]);
131 /* Prints the values in 'hindex', plus 'name' as a title. */
132 static void OVS_UNUSED
133 print_hindex(const char *name
, struct hindex
*hindex
)
138 HINDEX_FOR_EACH (e
, node
, hindex
) {
139 printf(" %d(%zu)", e
->value
, e
->node
.hash
& hindex
->mask
);
145 unique_hash(int value
)
153 return hash_int(value
, 0x1234abcd);
157 constant_hash(int value OVS_UNUSED
)
180 /* Tests basic hindex insertion and deletion. */
182 test_hindex_insert_delete(hash_func
*hash
)
184 enum { N_ELEMS
= 100 };
186 struct element elements
[N_ELEMS
];
188 struct hindex hindex
;
191 hindex_init(&hindex
);
192 for (i
= 0; i
< N_ELEMS
; i
++) {
193 elements
[i
].value
= i
;
194 hindex_insert(&hindex
, &elements
[i
].node
, hash(i
));
196 check_hindex(&hindex
, values
, i
+ 1, hash
);
198 shuffle(values
, N_ELEMS
);
199 for (i
= 0; i
< N_ELEMS
; i
++) {
200 hindex_remove(&hindex
, &elements
[values
[i
]].node
);
201 check_hindex(&hindex
, values
+ (i
+ 1), N_ELEMS
- (i
+ 1), hash
);
203 hindex_destroy(&hindex
);
206 /* Tests basic hindex_reserve() and hindex_shrink(). */
208 test_hindex_reserve_shrink(hash_func
*hash
)
210 enum { N_ELEMS
= 32 };
214 for (i
= 0; i
< N_ELEMS
; i
++) {
215 struct element elements
[N_ELEMS
];
217 struct hindex hindex
;
220 hindex_init(&hindex
);
221 hindex_reserve(&hindex
, i
);
222 for (j
= 0; j
< N_ELEMS
; j
++) {
223 elements
[j
].value
= j
;
224 hindex_insert(&hindex
, &elements
[j
].node
, hash(j
));
226 check_hindex(&hindex
, values
, j
+ 1, hash
);
228 shuffle(values
, N_ELEMS
);
229 for (j
= 0; j
< N_ELEMS
; j
++) {
230 hindex_remove(&hindex
, &elements
[values
[j
]].node
);
231 hindex_shrink(&hindex
);
232 check_hindex(&hindex
, values
+ (j
+ 1), N_ELEMS
- (j
+ 1), hash
);
234 hindex_destroy(&hindex
);
238 /* Tests that HINDEX_FOR_EACH_SAFE properly allows for deletion of the current
239 * element of a hindex. */
241 test_hindex_for_each_safe(hash_func
*hash
)
243 enum { MAX_ELEMS
= 10 };
245 unsigned long int pattern
;
247 for (n
= 0; n
<= MAX_ELEMS
; n
++) {
248 for (pattern
= 0; pattern
< 1ul << n
; pattern
++) {
249 struct element elements
[MAX_ELEMS
];
250 int values
[MAX_ELEMS
];
251 struct hindex hindex
;
252 struct element
*e
, *next
;
256 make_hindex(&hindex
, elements
, values
, n
, hash
);
260 HINDEX_FOR_EACH_SAFE (e
, next
, node
, &hindex
) {
262 if (pattern
& (1ul << e
->value
)) {
264 hindex_remove(&hindex
, &e
->node
);
266 assert(j
< n_remaining
);
267 if (values
[j
] == e
->value
) {
268 values
[j
] = values
[--n_remaining
];
273 check_hindex(&hindex
, values
, n_remaining
, hash
);
278 for (i
= 0; i
< n
; i
++) {
279 if (pattern
& (1ul << i
)) {
283 assert(n
== n_remaining
);
285 hindex_destroy(&hindex
);
291 run_test(void (*function
)(hash_func
*))
293 hash_func
*hash_funcs
[] = {
303 for (i
= 0; i
< ARRAY_SIZE(hash_funcs
); i
++) {
304 function(hash_funcs
[i
]);
313 run_test(test_hindex_insert_delete
);
314 run_test(test_hindex_for_each_safe
);
315 run_test(test_hindex_reserve_shrink
);