2 * Copyright (c) 2008, 2009, 2010, 2013, 2014 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
31 /* Sample hindex element. */
34 struct hindex_node node;
37 typedef size_t hash_func(int value);
40 compare_ints(const void *a_, const void *b_)
44 return *a < *b ? -1 : *a > *b;
47 /* Verifies that 'hindex' contains exactly the 'n' values in 'values'. */
49 check_hindex(struct hindex *hindex, const int values[], size_t n,
52 int *sort_values, *hindex_values;
56 /* Check that all the values are there in iteration. */
57 sort_values = xmalloc(sizeof *sort_values * n);
58 hindex_values = xmalloc(sizeof *sort_values * n);
61 HINDEX_FOR_EACH (e, node, hindex) {
63 hindex_values[i++] = e->value;
67 memcpy(sort_values, values, sizeof *sort_values * n);
68 qsort(sort_values, n, sizeof *sort_values, compare_ints);
69 qsort(hindex_values, n, sizeof *hindex_values, compare_ints);
71 for (i = 0; i < n; i++) {
72 assert(sort_values[i] == hindex_values[i]);
78 /* Check that all the values are there in lookup. */
79 for (i = 0; i < n; i++) {
82 HINDEX_FOR_EACH_WITH_HASH (e, node, hash(values[i]), hindex) {
83 count += e->value == values[i];
89 assert(hindex_is_empty(hindex) == !n);
90 assert(hindex->n_unique <= n);
93 /* Puts the 'n' values in 'values' into 'elements', and then puts those
94 * elements into 'hindex'. */
96 make_hindex(struct hindex *hindex, struct element elements[],
97 int values[], size_t n, hash_func *hash)
102 for (i = 0; i < n; i++) {
103 elements[i].value = i;
104 hindex_insert(hindex, &elements[i].node, hash(elements[i].value));
110 shuffle(int *p, size_t n)
112 for (; n > 1; n--, p++) {
113 int *q = &p[random_range(n)];
120 /* Prints the 'n' values in 'values', plus 'name' as a title. */
121 static void OVS_UNUSED
122 print_ints(const char *name, const int *values, size_t n)
127 for (i = 0; i < n; i++) {
128 printf(" %d", values[i]);
133 /* Prints the values in 'hindex', plus 'name' as a title. */
134 static void OVS_UNUSED
135 print_hindex(const char *name, struct hindex *hindex)
140 HINDEX_FOR_EACH (e, node, hindex) {
141 printf(" %d(%"PRIuSIZE")", e->value, e->node.hash & hindex->mask);
147 unique_hash(int value)
155 return hash_int(value, 0x1234abcd);
159 constant_hash(int value OVS_UNUSED)
183 multipart_hash(int value)
185 return (mod4_hash(value) << 16) | (constant_hash(value) & 0xFFFF);
188 /* Tests basic hindex insertion and deletion. */
190 test_hindex_insert_delete(hash_func *hash)
192 enum { N_ELEMS = 100 };
194 struct element elements[N_ELEMS];
196 struct hindex hindex;
199 hindex_init(&hindex);
200 for (i = 0; i < N_ELEMS; i++) {
201 elements[i].value = i;
202 hindex_insert(&hindex, &elements[i].node, hash(i));
204 check_hindex(&hindex, values, i + 1, hash);
206 shuffle(values, N_ELEMS);
207 for (i = 0; i < N_ELEMS; i++) {
208 hindex_remove(&hindex, &elements[values[i]].node);
209 check_hindex(&hindex, values + (i + 1), N_ELEMS - (i + 1), hash);
211 hindex_destroy(&hindex);
214 /* Tests basic hindex_reserve() and hindex_shrink(). */
216 test_hindex_reserve_shrink(hash_func *hash)
218 enum { N_ELEMS = 32 };
222 for (i = 0; i < N_ELEMS; i++) {
223 struct element elements[N_ELEMS];
225 struct hindex hindex;
228 hindex_init(&hindex);
229 hindex_reserve(&hindex, i);
230 for (j = 0; j < N_ELEMS; j++) {
231 elements[j].value = j;
232 hindex_insert(&hindex, &elements[j].node, hash(j));
234 check_hindex(&hindex, values, j + 1, hash);
236 shuffle(values, N_ELEMS);
237 for (j = 0; j < N_ELEMS; j++) {
238 hindex_remove(&hindex, &elements[values[j]].node);
239 hindex_shrink(&hindex);
240 check_hindex(&hindex, values + (j + 1), N_ELEMS - (j + 1), hash);
242 hindex_destroy(&hindex);
246 /* Tests that HINDEX_FOR_EACH_SAFE properly allows for deletion of the current
247 * element of a hindex. */
249 test_hindex_for_each_safe(hash_func *hash)
251 enum { MAX_ELEMS = 10 };
253 unsigned long int pattern;
255 for (n = 0; n <= MAX_ELEMS; n++) {
256 for (pattern = 0; pattern < 1ul << n; pattern++) {
257 struct element elements[MAX_ELEMS];
258 int values[MAX_ELEMS];
259 struct hindex hindex;
260 struct element *e, *next;
264 make_hindex(&hindex, elements, values, n, hash);
268 HINDEX_FOR_EACH_SAFE (e, next, node, &hindex) {
270 if (pattern & (1ul << e->value)) {
272 hindex_remove(&hindex, &e->node);
274 assert(j < n_remaining);
275 if (values[j] == e->value) {
276 values[j] = values[--n_remaining];
281 check_hindex(&hindex, values, n_remaining, hash);
286 for (i = 0; i < n; i++) {
287 if (pattern & (1ul << i)) {
291 assert(n == n_remaining);
293 hindex_destroy(&hindex);
299 run_test(void (*function)(hash_func *))
301 hash_func *hash_funcs[] = {
312 for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
313 function(hash_funcs[i]);
320 test_hindex_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
322 run_test(test_hindex_insert_delete);
323 run_test(test_hindex_for_each_safe);
324 run_test(test_hindex_reserve_shrink);
328 OVSTEST_REGISTER("test-hindex", test_hindex_main);