]>
git.proxmox.com Git - ovs.git/blob - tests/test-hmap.c
2 * Copyright (c) 2008, 2009, 2010 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 hmap element. */
32 struct hmap_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 'hmap' contains exactly the 'n' values in 'values'. */
47 check_hmap(struct hmap
*hmap
, const int values
[], size_t n
,
50 int *sort_values
, *hmap_values
;
54 /* Check that all the values are there in iteration. */
55 sort_values
= xmalloc(sizeof *sort_values
* n
);
56 hmap_values
= xmalloc(sizeof *sort_values
* n
);
59 HMAP_FOR_EACH (e
, node
, hmap
) {
61 hmap_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(hmap_values
, n
, sizeof *hmap_values
, compare_ints
);
69 for (i
= 0; i
< n
; i
++) {
70 assert(sort_values
[i
] == hmap_values
[i
]);
76 /* Check that all the values are there in lookup. */
77 for (i
= 0; i
< n
; i
++) {
80 HMAP_FOR_EACH_WITH_HASH (e
, node
, hash(values
[i
]), hmap
) {
81 count
+= e
->value
== values
[i
];
87 assert(hmap_is_empty(hmap
) == !n
);
88 assert(hmap_count(hmap
) == n
);
91 /* Puts the 'n' values in 'values' into 'elements', and then puts those
92 * elements into 'hmap'. */
94 make_hmap(struct hmap
*hmap
, 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 hmap_insert(hmap
, &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
];
119 /* Prints the values in 'hmap', plus 'name' as a title. */
121 print_hmap(const char *name
, struct hmap
*hmap
)
126 HMAP_FOR_EACH (e
, node
, hmap
) {
127 printf(" %d(%zu)", e
->value
, e
->node
.hash
& hmap
->mask
);
132 /* Prints the 'n' values in 'values', plus 'name' as a title. */
134 print_ints(const char *name
, const int *values
, size_t n
)
139 for (i
= 0; i
< n
; i
++) {
140 printf(" %d", values
[i
]);
147 identity_hash(int value
)
155 return hash_int(value
, 0x1234abcd);
159 constant_hash(int value OVS_UNUSED
)
164 /* Tests basic hmap insertion and deletion. */
166 test_hmap_insert_delete(hash_func
*hash
)
168 enum { N_ELEMS
= 100 };
170 struct element elements
[N_ELEMS
];
176 for (i
= 0; i
< N_ELEMS
; i
++) {
177 elements
[i
].value
= i
;
178 hmap_insert(&hmap
, &elements
[i
].node
, hash(i
));
180 check_hmap(&hmap
, values
, i
+ 1, hash
);
182 shuffle(values
, N_ELEMS
);
183 for (i
= 0; i
< N_ELEMS
; i
++) {
184 hmap_remove(&hmap
, &elements
[values
[i
]].node
);
185 check_hmap(&hmap
, values
+ (i
+ 1), N_ELEMS
- (i
+ 1), hash
);
190 /* Tests basic hmap_reserve() and hmap_shrink(). */
192 test_hmap_reserve_shrink(hash_func
*hash
)
194 enum { N_ELEMS
= 32 };
198 for (i
= 0; i
< N_ELEMS
; i
++) {
199 struct element elements
[N_ELEMS
];
205 hmap_reserve(&hmap
, i
);
206 for (j
= 0; j
< N_ELEMS
; j
++) {
207 elements
[j
].value
= j
;
208 hmap_insert(&hmap
, &elements
[j
].node
, hash(j
));
210 check_hmap(&hmap
, values
, j
+ 1, hash
);
212 shuffle(values
, N_ELEMS
);
213 for (j
= 0; j
< N_ELEMS
; j
++) {
214 hmap_remove(&hmap
, &elements
[values
[j
]].node
);
216 check_hmap(&hmap
, values
+ (j
+ 1), N_ELEMS
- (j
+ 1), hash
);
222 /* Tests that HMAP_FOR_EACH_SAFE properly allows for deletion of the current
223 * element of a hmap. */
225 test_hmap_for_each_safe(hash_func
*hash
)
227 enum { MAX_ELEMS
= 10 };
229 unsigned long int pattern
;
231 for (n
= 0; n
<= MAX_ELEMS
; n
++) {
232 for (pattern
= 0; pattern
< 1ul << n
; pattern
++) {
233 struct element elements
[MAX_ELEMS
];
234 int values
[MAX_ELEMS
];
236 struct element
*e
, *next
;
240 make_hmap(&hmap
, elements
, values
, n
, hash
);
244 HMAP_FOR_EACH_SAFE (e
, next
, node
, &hmap
) {
246 if (pattern
& (1ul << e
->value
)) {
248 hmap_remove(&hmap
, &e
->node
);
250 assert(j
< n_remaining
);
251 if (values
[j
] == e
->value
) {
252 values
[j
] = values
[--n_remaining
];
257 check_hmap(&hmap
, values
, n_remaining
, hash
);
262 for (i
= 0; i
< n
; i
++) {
263 if (pattern
& (1ul << i
)) {
267 assert(n
== n_remaining
);
275 run_test(void (*function
)(hash_func
*))
277 hash_func
*hash_funcs
[] = { identity_hash
, good_hash
, constant_hash
};
280 for (i
= 0; i
< ARRAY_SIZE(hash_funcs
); i
++) {
281 function(hash_funcs
[i
]);
290 run_test(test_hmap_insert_delete
);
291 run_test(test_hmap_for_each_safe
);
292 run_test(test_hmap_reserve_shrink
);