configure: Enable OpenSSL support by default.
[sliver-openvswitch.git] / tests / test-hmap.c
1 /*
2  * Copyright (c) 2008, 2009, 2010 Nicira Networks.
3  *
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:
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
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.
15  */
16
17 /* A non-exhaustive test for some of the functions and macros declared in
18  * hmap.h. */
19
20 #include <config.h>
21 #include "hmap.h"
22 #include <string.h>
23 #include "hash.h"
24 #include "util.h"
25
26 #undef NDEBUG
27 #include <assert.h>
28
29 /* Sample hmap element. */
30 struct element {
31     int value;
32     struct hmap_node node;
33 };
34
35 typedef size_t hash_func(int value);
36
37 static int
38 compare_ints(const void *a_, const void *b_)
39 {
40     const int *a = a_;
41     const int *b = b_;
42     return *a < *b ? -1 : *a > *b;
43 }
44
45 /* Verifies that 'hmap' contains exactly the 'n' values in 'values'. */
46 static void
47 check_hmap(struct hmap *hmap, const int values[], size_t n,
48            hash_func *hash)
49 {
50     int *sort_values, *hmap_values;
51     struct element *e;
52     size_t i;
53
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);
57
58     i = 0;
59     HMAP_FOR_EACH (e, struct element, node, hmap) {
60         assert(i < n);
61         hmap_values[i++] = e->value;
62     }
63     assert(i == n);
64
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);
68
69     for (i = 0; i < n; i++) {
70         assert(sort_values[i] == hmap_values[i]);
71     }
72
73     free(hmap_values);
74     free(sort_values);
75
76     /* Check that all the values are there in lookup. */
77     for (i = 0; i < n; i++) {
78         size_t count = 0;
79
80         HMAP_FOR_EACH_WITH_HASH (e, struct element, node,
81                                  hash(values[i]), hmap) {
82             count += e->value == values[i];
83         }
84         assert(count == 1);
85     }
86
87     /* Check counters. */
88     assert(hmap_is_empty(hmap) == !n);
89     assert(hmap_count(hmap) == n);
90 }
91
92 /* Puts the 'n' values in 'values' into 'elements', and then puts those
93  * elements into 'hmap'. */
94 static void
95 make_hmap(struct hmap *hmap, struct element elements[],
96           int values[], size_t n, hash_func *hash)
97 {
98     size_t i;
99
100     hmap_init(hmap);
101     for (i = 0; i < n; i++) {
102         elements[i].value = i;
103         hmap_insert(hmap, &elements[i].node, hash(elements[i].value));
104         values[i] = i;
105     }
106 }
107
108 static void
109 shuffle(int *p, size_t n)
110 {
111     for (; n > 1; n--, p++) {
112         int *q = &p[rand() % n];
113         int tmp = *p;
114         *p = *q;
115         *q = tmp;
116     }
117 }
118
119 #if 0
120 /* Prints the values in 'hmap', plus 'name' as a title. */
121 static void
122 print_hmap(const char *name, struct hmap *hmap)
123 {
124     struct element *e;
125
126     printf("%s:", name);
127     HMAP_FOR_EACH (e, struct element, node, hmap) {
128         printf(" %d(%zu)", e->value, e->node.hash & hmap->mask);
129     }
130     printf("\n");
131 }
132
133 /* Prints the 'n' values in 'values', plus 'name' as a title. */
134 static void
135 print_ints(const char *name, const int *values, size_t n)
136 {
137     size_t i;
138
139     printf("%s:", name);
140     for (i = 0; i < n; i++) {
141         printf(" %d", values[i]);
142     }
143     printf("\n");
144 }
145 #endif
146
147 static size_t
148 identity_hash(int value)
149 {
150     return value;
151 }
152
153 static size_t
154 good_hash(int value)
155 {
156     return hash_int(value, 0x1234abcd);
157 }
158
159 static size_t
160 constant_hash(int value OVS_UNUSED)
161 {
162     return 123;
163 }
164
165 /* Tests basic hmap insertion and deletion. */
166 static void
167 test_hmap_insert_delete(hash_func *hash)
168 {
169     enum { N_ELEMS = 100 };
170
171     struct element elements[N_ELEMS];
172     int values[N_ELEMS];
173     struct hmap hmap;
174     size_t i;
175
176     hmap_init(&hmap);
177     for (i = 0; i < N_ELEMS; i++) {
178         elements[i].value = i;
179         hmap_insert(&hmap, &elements[i].node, hash(i));
180         values[i] = i;
181         check_hmap(&hmap, values, i + 1, hash);
182     }
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);
187     }
188     hmap_destroy(&hmap);
189 }
190
191 /* Tests basic hmap_reserve() and hmap_shrink(). */
192 static void
193 test_hmap_reserve_shrink(hash_func *hash)
194 {
195     enum { N_ELEMS = 32 };
196
197     size_t i;
198
199     for (i = 0; i < N_ELEMS; i++) {
200         struct element elements[N_ELEMS];
201         int values[N_ELEMS];
202         struct hmap hmap;
203         size_t j;
204
205         hmap_init(&hmap);
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));
210             values[j] = j;
211             check_hmap(&hmap, values, j + 1, hash);
212         }
213         shuffle(values, N_ELEMS);
214         for (j = 0; j < N_ELEMS; j++) {
215             hmap_remove(&hmap, &elements[values[j]].node);
216             hmap_shrink(&hmap);
217             check_hmap(&hmap, values + (j + 1), N_ELEMS - (j + 1), hash);
218         }
219         hmap_destroy(&hmap);
220     }
221 }
222
223 /* Tests that HMAP_FOR_EACH_SAFE properly allows for deletion of the current
224  * element of a hmap.  */
225 static void
226 test_hmap_for_each_safe(hash_func *hash)
227 {
228     enum { MAX_ELEMS = 10 };
229     size_t n;
230     unsigned long int pattern;
231
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];
236             struct hmap hmap;
237             struct element *e, *next;
238             size_t n_remaining;
239             int i;
240
241             make_hmap(&hmap, elements, values, n, hash);
242
243             i = 0;
244             n_remaining = n;
245             HMAP_FOR_EACH_SAFE (e, next, struct element, node, &hmap) {
246                 assert(i < n);
247                 if (pattern & (1ul << e->value)) {
248                     size_t j;
249                     hmap_remove(&hmap, &e->node);
250                     for (j = 0; ; j++) {
251                         assert(j < n_remaining);
252                         if (values[j] == e->value) {
253                             values[j] = values[--n_remaining];
254                             break;
255                         }
256                     }
257                 }
258                 check_hmap(&hmap, values, n_remaining, hash);
259                 i++;
260             }
261             assert(i == n);
262
263             for (i = 0; i < n; i++) {
264                 if (pattern & (1ul << i)) {
265                     n_remaining++;
266                 }
267             }
268             assert(n == n_remaining);
269
270             hmap_destroy(&hmap);
271         }
272     }
273 }
274
275 static void
276 run_test(void (*function)(hash_func *))
277 {
278     hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
279     size_t i;
280
281     for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
282         function(hash_funcs[i]);
283         printf(".");
284         fflush(stdout);
285     }
286 }
287
288 int
289 main(void)
290 {
291     run_test(test_hmap_insert_delete);
292     run_test(test_hmap_for_each_safe);
293     run_test(test_hmap_reserve_shrink);
294     printf("\n");
295     return 0;
296 }
297