ovs-ofctl: Fix del-flows command parsing bugs.
[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, 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, node, hash(values[i]), hmap) {
81             count += e->value == values[i];
82         }
83         assert(count == 1);
84     }
85
86     /* Check counters. */
87     assert(hmap_is_empty(hmap) == !n);
88     assert(hmap_count(hmap) == n);
89 }
90
91 /* Puts the 'n' values in 'values' into 'elements', and then puts those
92  * elements into 'hmap'. */
93 static void
94 make_hmap(struct hmap *hmap, struct element elements[],
95           int values[], size_t n, hash_func *hash)
96 {
97     size_t i;
98
99     hmap_init(hmap);
100     for (i = 0; i < n; i++) {
101         elements[i].value = i;
102         hmap_insert(hmap, &elements[i].node, hash(elements[i].value));
103         values[i] = i;
104     }
105 }
106
107 static void
108 shuffle(int *p, size_t n)
109 {
110     for (; n > 1; n--, p++) {
111         int *q = &p[rand() % n];
112         int tmp = *p;
113         *p = *q;
114         *q = tmp;
115     }
116 }
117
118 #if 0
119 /* Prints the values in 'hmap', plus 'name' as a title. */
120 static void
121 print_hmap(const char *name, struct hmap *hmap)
122 {
123     struct element *e;
124
125     printf("%s:", name);
126     HMAP_FOR_EACH (e, node, hmap) {
127         printf(" %d(%zu)", e->value, e->node.hash & hmap->mask);
128     }
129     printf("\n");
130 }
131
132 /* Prints the 'n' values in 'values', plus 'name' as a title. */
133 static void
134 print_ints(const char *name, const int *values, size_t n)
135 {
136     size_t i;
137
138     printf("%s:", name);
139     for (i = 0; i < n; i++) {
140         printf(" %d", values[i]);
141     }
142     printf("\n");
143 }
144 #endif
145
146 static size_t
147 identity_hash(int value)
148 {
149     return value;
150 }
151
152 static size_t
153 good_hash(int value)
154 {
155     return hash_int(value, 0x1234abcd);
156 }
157
158 static size_t
159 constant_hash(int value OVS_UNUSED)
160 {
161     return 123;
162 }
163
164 /* Tests basic hmap insertion and deletion. */
165 static void
166 test_hmap_insert_delete(hash_func *hash)
167 {
168     enum { N_ELEMS = 100 };
169
170     struct element elements[N_ELEMS];
171     int values[N_ELEMS];
172     struct hmap hmap;
173     size_t i;
174
175     hmap_init(&hmap);
176     for (i = 0; i < N_ELEMS; i++) {
177         elements[i].value = i;
178         hmap_insert(&hmap, &elements[i].node, hash(i));
179         values[i] = i;
180         check_hmap(&hmap, values, i + 1, hash);
181     }
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);
186     }
187     hmap_destroy(&hmap);
188 }
189
190 /* Tests basic hmap_reserve() and hmap_shrink(). */
191 static void
192 test_hmap_reserve_shrink(hash_func *hash)
193 {
194     enum { N_ELEMS = 32 };
195
196     size_t i;
197
198     for (i = 0; i < N_ELEMS; i++) {
199         struct element elements[N_ELEMS];
200         int values[N_ELEMS];
201         struct hmap hmap;
202         size_t j;
203
204         hmap_init(&hmap);
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));
209             values[j] = j;
210             check_hmap(&hmap, values, j + 1, hash);
211         }
212         shuffle(values, N_ELEMS);
213         for (j = 0; j < N_ELEMS; j++) {
214             hmap_remove(&hmap, &elements[values[j]].node);
215             hmap_shrink(&hmap);
216             check_hmap(&hmap, values + (j + 1), N_ELEMS - (j + 1), hash);
217         }
218         hmap_destroy(&hmap);
219     }
220 }
221
222 /* Tests that HMAP_FOR_EACH_SAFE properly allows for deletion of the current
223  * element of a hmap.  */
224 static void
225 test_hmap_for_each_safe(hash_func *hash)
226 {
227     enum { MAX_ELEMS = 10 };
228     size_t n;
229     unsigned long int pattern;
230
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];
235             struct hmap hmap;
236             struct element *e, *next;
237             size_t n_remaining;
238             int i;
239
240             make_hmap(&hmap, elements, values, n, hash);
241
242             i = 0;
243             n_remaining = n;
244             HMAP_FOR_EACH_SAFE (e, next, node, &hmap) {
245                 assert(i < n);
246                 if (pattern & (1ul << e->value)) {
247                     size_t j;
248                     hmap_remove(&hmap, &e->node);
249                     for (j = 0; ; j++) {
250                         assert(j < n_remaining);
251                         if (values[j] == e->value) {
252                             values[j] = values[--n_remaining];
253                             break;
254                         }
255                     }
256                 }
257                 check_hmap(&hmap, values, n_remaining, hash);
258                 i++;
259             }
260             assert(i == n);
261
262             for (i = 0; i < n; i++) {
263                 if (pattern & (1ul << i)) {
264                     n_remaining++;
265                 }
266             }
267             assert(n == n_remaining);
268
269             hmap_destroy(&hmap);
270         }
271     }
272 }
273
274 static void
275 run_test(void (*function)(hash_func *))
276 {
277     hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
278     size_t i;
279
280     for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
281         function(hash_funcs[i]);
282         printf(".");
283         fflush(stdout);
284     }
285 }
286
287 int
288 main(void)
289 {
290     run_test(test_hmap_insert_delete);
291     run_test(test_hmap_for_each_safe);
292     run_test(test_hmap_reserve_shrink);
293     printf("\n");
294     return 0;
295 }
296