1 /* A non-exhaustive test for some of the functions and macros declared in
13 /* Sample hmap element. */
16 struct hmap_node node;
19 typedef size_t hash_func(int value);
22 compare_ints(const void *a_, const void *b_)
26 return *a < *b ? -1 : *a > *b;
29 /* Verifies that 'hmap' contains exactly the 'n' values in 'values'. */
31 check_hmap(struct hmap *hmap, const int values[], size_t n,
34 int *sort_values, *hmap_values;
38 /* Check that all the values are there in iteration. */
39 sort_values = xmalloc(sizeof *sort_values * n);
40 hmap_values = xmalloc(sizeof *sort_values * n);
43 HMAP_FOR_EACH (e, struct element, node, hmap) {
45 hmap_values[i++] = e->value;
49 memcpy(sort_values, values, sizeof *sort_values * n);
50 qsort(sort_values, n, sizeof *sort_values, compare_ints);
51 qsort(hmap_values, n, sizeof *hmap_values, compare_ints);
53 for (i = 0; i < n; i++) {
54 assert(sort_values[i] == hmap_values[i]);
60 /* Check that all the values are there in lookup. */
61 for (i = 0; i < n; i++) {
64 HMAP_FOR_EACH_WITH_HASH (e, struct element, node,
65 hash(values[i]), hmap) {
66 count += e->value == values[i];
72 assert(hmap_is_empty(hmap) == !n);
73 assert(hmap_count(hmap) == n);
76 /* Puts the 'n' values in 'values' into 'elements', and then puts those
77 * elements into 'hmap'. */
79 make_hmap(struct hmap *hmap, struct element elements[],
80 int values[], size_t n, hash_func *hash)
85 for (i = 0; i < n; i++) {
86 elements[i].value = i;
87 hmap_insert(hmap, &elements[i].node, hash(elements[i].value));
93 shuffle(int *p, size_t n)
95 for (; n > 1; n--, p++) {
96 int *q = &p[rand() % n];
104 /* Prints the values in 'hmap', plus 'name' as a title. */
106 print_hmap(const char *name, struct hmap *hmap)
111 HMAP_FOR_EACH (e, struct element, node, hmap) {
112 printf(" %d(%zu)", e->value, e->node.hash & hmap->mask);
117 /* Prints the 'n' values in 'values', plus 'name' as a title. */
119 print_ints(const char *name, const int *values, size_t n)
124 for (i = 0; i < n; i++) {
125 printf(" %d", values[i]);
132 identity_hash(int value)
140 return hash_int(value, 0x1234abcd);
144 constant_hash(int value UNUSED)
149 /* Tests basic hmap insertion and deletion. */
151 test_hmap_insert_delete(hash_func *hash)
153 enum { N_ELEMS = 100 };
155 struct element elements[N_ELEMS];
161 for (i = 0; i < N_ELEMS; i++) {
162 elements[i].value = i;
163 hmap_insert(&hmap, &elements[i].node, hash(i));
165 check_hmap(&hmap, values, i + 1, hash);
167 shuffle(values, N_ELEMS);
168 for (i = 0; i < N_ELEMS; i++) {
169 hmap_remove(&hmap, &elements[values[i]].node);
170 check_hmap(&hmap, values + (i + 1), N_ELEMS - (i + 1), hash);
175 /* Tests basic hmap_reserve() and hmap_shrink(). */
177 test_hmap_reserve_shrink(hash_func *hash)
179 enum { N_ELEMS = 32 };
183 for (i = 0; i < N_ELEMS; i++) {
184 struct element elements[N_ELEMS];
190 hmap_reserve(&hmap, i);
191 for (j = 0; j < N_ELEMS; j++) {
192 elements[j].value = j;
193 hmap_insert(&hmap, &elements[j].node, hash(j));
195 check_hmap(&hmap, values, j + 1, hash);
197 shuffle(values, N_ELEMS);
198 for (j = 0; j < N_ELEMS; j++) {
199 hmap_remove(&hmap, &elements[values[j]].node);
201 check_hmap(&hmap, values + (j + 1), N_ELEMS - (j + 1), hash);
207 /* Tests that HMAP_FOR_EACH_SAFE properly allows for deletion of the current
208 * element of a hmap. */
210 test_hmap_for_each_safe(hash_func *hash)
212 enum { MAX_ELEMS = 10 };
214 unsigned long int pattern;
216 for (n = 0; n <= MAX_ELEMS; n++) {
217 for (pattern = 0; pattern < 1ul << n; pattern++) {
218 struct element elements[MAX_ELEMS];
219 int values[MAX_ELEMS];
221 struct element *e, *next;
225 make_hmap(&hmap, elements, values, n, hash);
229 HMAP_FOR_EACH_SAFE (e, next, struct element, node, &hmap) {
231 if (pattern & (1ul << e->value)) {
233 hmap_remove(&hmap, &e->node);
235 assert(j < n_remaining);
236 if (values[j] == e->value) {
237 values[j] = values[--n_remaining];
242 check_hmap(&hmap, values, n_remaining, hash);
247 for (i = 0; i < n; i++) {
248 if (pattern & (1ul << i)) {
252 assert(n == n_remaining);
260 run_test(void (*function)(hash_func *))
262 hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
265 for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
266 function(hash_funcs[i]);
275 run_test(test_hmap_insert_delete);
276 run_test(test_hmap_for_each_safe);
277 run_test(test_hmap_reserve_shrink);