]>
git.proxmox.com Git - mirror_ovs.git/blob - tests/test-hmap.c
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
30 /* Sample hmap element. */
33 struct hmap_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 'hmap' contains exactly the 'n' values in 'values'. */
48 check_hmap(struct hmap
*hmap
, const int values
[], size_t n
,
51 int *sort_values
, *hmap_values
;
55 /* Check that all the values are there in iteration. */
56 sort_values
= xmalloc(sizeof *sort_values
* n
);
57 hmap_values
= xmalloc(sizeof *sort_values
* n
);
60 HMAP_FOR_EACH (e
, node
, hmap
) {
62 hmap_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(hmap_values
, n
, sizeof *hmap_values
, compare_ints
);
70 for (i
= 0; i
< n
; i
++) {
71 assert(sort_values
[i
] == hmap_values
[i
]);
77 /* Check that all the values are there in lookup. */
78 for (i
= 0; i
< n
; i
++) {
81 HMAP_FOR_EACH_WITH_HASH (e
, node
, hash(values
[i
]), hmap
) {
82 count
+= e
->value
== values
[i
];
88 assert(hmap_is_empty(hmap
) == !n
);
89 assert(hmap_count(hmap
) == n
);
92 /* Puts the 'n' values in 'values' into 'elements', and then puts those
93 * elements into 'hmap'. */
95 make_hmap(struct hmap
*hmap
, 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 hmap_insert(hmap
, &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
)];
120 /* Prints the values in 'hmap', plus 'name' as a title. */
122 print_hmap(const char *name
, struct hmap
*hmap
)
127 HMAP_FOR_EACH (e
, node
, hmap
) {
128 printf(" %d(%"PRIuSIZE
")", e
->value
, e
->node
.hash
& hmap
->mask
);
133 /* Prints the 'n' values in 'values', plus 'name' as a title. */
135 print_ints(const char *name
, const int *values
, size_t n
)
140 for (i
= 0; i
< n
; i
++) {
141 printf(" %d", values
[i
]);
148 identity_hash(int value
)
156 return hash_int(value
, 0x1234abcd);
160 constant_hash(int value OVS_UNUSED
)
165 /* Tests basic hmap insertion and deletion. */
167 test_hmap_insert_delete(hash_func
*hash
)
169 enum { N_ELEMS
= 100 };
171 struct element elements
[N_ELEMS
];
177 for (i
= 0; i
< N_ELEMS
; i
++) {
178 elements
[i
].value
= i
;
179 hmap_insert(&hmap
, &elements
[i
].node
, hash(i
));
181 check_hmap(&hmap
, values
, i
+ 1, hash
);
183 shuffle(values
, N_ELEMS
);
184 for (i
= 0; i
< N_ELEMS
; i
++) {
185 hmap_remove(&hmap
, &elements
[values
[i
]].node
);
186 check_hmap(&hmap
, values
+ (i
+ 1), N_ELEMS
- (i
+ 1), hash
);
191 /* Tests basic hmap_reserve() and hmap_shrink(). */
193 test_hmap_reserve_shrink(hash_func
*hash
)
195 enum { N_ELEMS
= 32 };
199 for (i
= 0; i
< N_ELEMS
; i
++) {
200 struct element elements
[N_ELEMS
];
206 hmap_reserve(&hmap
, i
);
207 for (j
= 0; j
< N_ELEMS
; j
++) {
208 elements
[j
].value
= j
;
209 hmap_insert(&hmap
, &elements
[j
].node
, hash(j
));
211 check_hmap(&hmap
, values
, j
+ 1, hash
);
213 shuffle(values
, N_ELEMS
);
214 for (j
= 0; j
< N_ELEMS
; j
++) {
215 hmap_remove(&hmap
, &elements
[values
[j
]].node
);
217 check_hmap(&hmap
, values
+ (j
+ 1), N_ELEMS
- (j
+ 1), hash
);
223 /* Tests that HMAP_FOR_EACH_SAFE properly allows for deletion of the current
224 * element of a hmap. */
226 test_hmap_for_each_safe(hash_func
*hash
)
228 enum { MAX_ELEMS
= 10 };
230 unsigned long int pattern
;
232 for (n
= 0; n
<= MAX_ELEMS
; n
++) {
233 for (pattern
= 0; pattern
< 1ul << n
; pattern
++) {
234 struct element elements
[MAX_ELEMS
];
235 int values
[MAX_ELEMS
];
237 struct element
*e
, *next
;
241 make_hmap(&hmap
, elements
, values
, n
, hash
);
245 HMAP_FOR_EACH_SAFE (e
, next
, node
, &hmap
) {
247 if (pattern
& (1ul << e
->value
)) {
249 hmap_remove(&hmap
, &e
->node
);
251 assert(j
< n_remaining
);
252 if (values
[j
] == e
->value
) {
253 values
[j
] = values
[--n_remaining
];
258 check_hmap(&hmap
, values
, n_remaining
, hash
);
263 for (i
= 0; i
< n
; i
++) {
264 if (pattern
& (1ul << i
)) {
268 assert(n
== n_remaining
);
276 run_test(void (*function
)(hash_func
*))
278 hash_func
*hash_funcs
[] = { identity_hash
, good_hash
, constant_hash
};
281 for (i
= 0; i
< ARRAY_SIZE(hash_funcs
); i
++) {
282 function(hash_funcs
[i
]);
289 test_hmap_main(int argc OVS_UNUSED
, char *argv
[] OVS_UNUSED
)
291 run_test(test_hmap_insert_delete
);
292 run_test(test_hmap_for_each_safe
);
293 run_test(test_hmap_reserve_shrink
);
297 OVSTEST_REGISTER("test-hmap", test_hmap_main
);