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
30 /* Sample hindex element. */
33 struct hindex_node node
;
36 typedef size_t hash_func(int value
);
39 compare_ints(const void *a_
, const void *b_
)
43 return *a
< *b
? -1 : *a
> *b
;
46 /* Verifies that 'hindex' contains exactly the 'n' values in 'values'. */
48 check_hindex(struct hindex
*hindex
, const int values
[], size_t n
,
51 int *sort_values
, *hindex_values
;
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
);
60 HINDEX_FOR_EACH (e
, node
, hindex
) {
62 hindex_values
[i
++] = e
->value
;
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
);
70 for (i
= 0; i
< n
; i
++) {
71 assert(sort_values
[i
] == hindex_values
[i
]);
77 /* Check that all the values are there in lookup. */
78 for (i
= 0; i
< n
; i
++) {
81 HINDEX_FOR_EACH_WITH_HASH (e
, node
, hash(values
[i
]), hindex
) {
82 count
+= e
->value
== values
[i
];
88 assert(hindex_is_empty(hindex
) == !n
);
89 assert(hindex
->n_unique
<= n
);
92 /* Puts the 'n' values in 'values' into 'elements', and then puts those
93 * elements into 'hindex'. */
95 make_hindex(struct hindex
*hindex
, struct element elements
[],
96 int values
[], size_t n
, hash_func
*hash
)
101 for (i
= 0; i
< n
; i
++) {
102 elements
[i
].value
= i
;
103 hindex_insert(hindex
, &elements
[i
].node
, hash(elements
[i
].value
));
109 shuffle(int *p
, size_t n
)
111 for (; n
> 1; n
--, p
++) {
112 int *q
= &p
[random_range(n
)];
119 /* Prints the 'n' values in 'values', plus 'name' as a title. */
120 static void OVS_UNUSED
121 print_ints(const char *name
, const int *values
, size_t n
)
126 for (i
= 0; i
< n
; i
++) {
127 printf(" %d", values
[i
]);
132 /* Prints the values in 'hindex', plus 'name' as a title. */
133 static void OVS_UNUSED
134 print_hindex(const char *name
, struct hindex
*hindex
)
139 HINDEX_FOR_EACH (e
, node
, hindex
) {
140 printf(" %d(%zu)", e
->value
, e
->node
.hash
& hindex
->mask
);
146 unique_hash(int value
)
154 return hash_int(value
, 0x1234abcd);
158 constant_hash(int value OVS_UNUSED
)
181 /* Tests basic hindex insertion and deletion. */
183 test_hindex_insert_delete(hash_func
*hash
)
185 enum { N_ELEMS
= 100 };
187 struct element elements
[N_ELEMS
];
189 struct hindex hindex
;
192 hindex_init(&hindex
);
193 for (i
= 0; i
< N_ELEMS
; i
++) {
194 elements
[i
].value
= i
;
195 hindex_insert(&hindex
, &elements
[i
].node
, hash(i
));
197 check_hindex(&hindex
, values
, i
+ 1, hash
);
199 shuffle(values
, N_ELEMS
);
200 for (i
= 0; i
< N_ELEMS
; i
++) {
201 hindex_remove(&hindex
, &elements
[values
[i
]].node
);
202 check_hindex(&hindex
, values
+ (i
+ 1), N_ELEMS
- (i
+ 1), hash
);
204 hindex_destroy(&hindex
);
207 /* Tests basic hindex_reserve() and hindex_shrink(). */
209 test_hindex_reserve_shrink(hash_func
*hash
)
211 enum { N_ELEMS
= 32 };
215 for (i
= 0; i
< N_ELEMS
; i
++) {
216 struct element elements
[N_ELEMS
];
218 struct hindex hindex
;
221 hindex_init(&hindex
);
222 hindex_reserve(&hindex
, i
);
223 for (j
= 0; j
< N_ELEMS
; j
++) {
224 elements
[j
].value
= j
;
225 hindex_insert(&hindex
, &elements
[j
].node
, hash(j
));
227 check_hindex(&hindex
, values
, j
+ 1, hash
);
229 shuffle(values
, N_ELEMS
);
230 for (j
= 0; j
< N_ELEMS
; j
++) {
231 hindex_remove(&hindex
, &elements
[values
[j
]].node
);
232 hindex_shrink(&hindex
);
233 check_hindex(&hindex
, values
+ (j
+ 1), N_ELEMS
- (j
+ 1), hash
);
235 hindex_destroy(&hindex
);
239 /* Tests that HINDEX_FOR_EACH_SAFE properly allows for deletion of the current
240 * element of a hindex. */
242 test_hindex_for_each_safe(hash_func
*hash
)
244 enum { MAX_ELEMS
= 10 };
246 unsigned long int pattern
;
248 for (n
= 0; n
<= MAX_ELEMS
; n
++) {
249 for (pattern
= 0; pattern
< 1ul << n
; pattern
++) {
250 struct element elements
[MAX_ELEMS
];
251 int values
[MAX_ELEMS
];
252 struct hindex hindex
;
253 struct element
*e
, *next
;
257 make_hindex(&hindex
, elements
, values
, n
, hash
);
261 HINDEX_FOR_EACH_SAFE (e
, next
, node
, &hindex
) {
263 if (pattern
& (1ul << e
->value
)) {
265 hindex_remove(&hindex
, &e
->node
);
267 assert(j
< n_remaining
);
268 if (values
[j
] == e
->value
) {
269 values
[j
] = values
[--n_remaining
];
274 check_hindex(&hindex
, values
, n_remaining
, hash
);
279 for (i
= 0; i
< n
; i
++) {
280 if (pattern
& (1ul << i
)) {
284 assert(n
== n_remaining
);
286 hindex_destroy(&hindex
);
292 run_test(void (*function
)(hash_func
*))
294 hash_func
*hash_funcs
[] = {
304 for (i
= 0; i
< ARRAY_SIZE(hash_funcs
); i
++) {
305 function(hash_funcs
[i
]);
314 run_test(test_hindex_insert_delete
);
315 run_test(test_hindex_for_each_safe
);
316 run_test(test_hindex_reserve_shrink
);