ovs-vsctl: Allow "fake bridges" to be created for VLAN 0.
[openvswitch] / tests / test-heap.c
1 /*
2  * Copyright (c) 2012 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 test for for functions and macros declared in heap.h. */
18
19 #include <config.h>
20 #include "heap.h"
21 #include <inttypes.h>
22 #include <limits.h>
23 #include <stdlib.h>
24 #include "command-line.h"
25 #include "random.h"
26 #include "util.h"
27
28 #undef NDEBUG
29 #include <assert.h>
30
31 /* Sample heap element. */
32 struct element {
33     uint32_t full_pri;
34     struct heap_node heap_node;
35 };
36
37 static struct element *
38 element_from_heap_node(const struct heap_node *node)
39 {
40     return CONTAINER_OF(node, struct element, heap_node);
41 }
42
43 static int
44 compare_uint32s(const void *a_, const void *b_)
45 {
46     const uint32_t *a = a_;
47     const uint32_t *b = b_;
48     return *a < *b ? -1 : *a > *b;
49 }
50
51 /* Verifies that 'heap' is internally consistent and contains all 'n' of the
52  * 'priorities'. */
53 static void
54 check_heap(const struct heap *heap, const uint32_t priorities[], size_t n)
55 {
56     uint32_t *priorities_copy;
57     uint32_t *elements_copy;
58     struct element *element;
59     size_t i;
60
61     assert(heap_count(heap) == n);
62     assert(heap_is_empty(heap) == !n);
63     if (n > 0) {
64         assert(heap_max(heap) == heap->array[1]);
65     }
66
67     /* Check indexes. */
68     for (i = 1; i <= n; i++) {
69         assert(heap->array[i]->idx == i);
70     }
71
72     /* Check that priority values are internally consistent. */
73     for (i = 1; i <= n; i++) {
74         element = element_from_heap_node(heap->array[i]);
75         assert(element->heap_node.priority == (element->full_pri >> 16));
76     }
77
78     /* Check the heap property. */
79     for (i = 1; i <= n; i++) {
80         size_t parent = heap_parent__(i);
81         size_t left = heap_left__(i);
82         size_t right = heap_right__(i);
83
84         if (parent >= 1) {
85             assert(heap->array[parent]->priority >= heap->array[i]->priority);
86         }
87         if (left <= n) {
88             assert(heap->array[left]->priority <= heap->array[i]->priority);
89         }
90         if (right <= n) {
91             assert(heap->array[right]->priority <= heap->array[i]->priority);
92         }
93     }
94
95     /* Check that HEAP_FOR_EACH iterates all the nodes in order. */
96     i = 0;
97     HEAP_FOR_EACH (element, heap_node, heap) {
98         assert(i < n);
99         assert(&element->heap_node == heap->array[i + 1]);
100         i++;
101     }
102     assert(i == n);
103
104     priorities_copy = xmemdup(priorities, n * sizeof *priorities);
105     elements_copy = xmalloc(n * sizeof *priorities);
106     i = 0;
107     HEAP_FOR_EACH (element, heap_node, heap) {
108         elements_copy[i++] = element->heap_node.priority;
109     }
110
111     qsort(priorities_copy, n, sizeof *priorities_copy, compare_uint32s);
112     qsort(elements_copy, n, sizeof *elements_copy, compare_uint32s);
113     for (i = 0; i < n; i++) {
114         assert((priorities_copy[i] >> 16) == elements_copy[i]);
115     }
116
117     free(priorities_copy);
118     free(elements_copy);
119 }
120
121 static void
122 shuffle(uint32_t *p, size_t n)
123 {
124     for (; n > 1; n--, p++) {
125         uint32_t *q = &p[random_range(n)];
126         uint32_t tmp = *p;
127         *p = *q;
128         *q = tmp;
129     }
130 }
131
132 /* Prints the values in 'heap', plus 'name' as a title. */
133 static void OVS_UNUSED
134 print_heap(const char *name, struct heap *heap)
135 {
136     struct element *e;
137
138     printf("%s:", name);
139     HEAP_FOR_EACH (e, heap_node, heap) {
140         printf(" %"PRIu32":%"PRIu32, e->full_pri >> 16, e->full_pri & 0xffff);
141     }
142     printf("\n");
143 }
144
145 static int
146 factorial(int n_items)
147 {
148     int n, i;
149
150     n = 1;
151     for (i = 2; i <= n_items; i++) {
152         n *= i;
153     }
154     return n;
155 }
156
157 static void
158 swap(uint32_t *a, uint32_t *b)
159 {
160     uint32_t tmp = *a;
161     *a = *b;
162     *b = tmp;
163 }
164
165 static void
166 reverse(uint32_t *a, int n)
167 {
168     int i;
169
170     for (i = 0; i < n / 2; i++) {
171         int j = n - (i + 1);
172         swap(&a[i], &a[j]);
173     }
174 }
175
176 static bool
177 next_permutation(uint32_t *a, int n)
178 {
179     int k;
180
181     for (k = n - 2; k >= 0; k--) {
182         if ((a[k] >> 16) < (a[k + 1] >> 16)) {
183             int l;
184
185             for (l = n - 1; ; l--) {
186                 if ((a[l] >> 16) > (a[k] >> 16)) {
187                     swap(&a[k], &a[l]);
188                     reverse(a + (k + 1), n - (k + 1));
189                     return true;
190                 }
191             }
192         }
193     }
194     return false;
195 }
196
197 static void
198 test_insert_delete__(struct element *elements,
199                      const uint32_t *insert,
200                      const uint32_t *delete,
201                      size_t n)
202 {
203     struct heap heap;
204     size_t i;
205
206     heap_init(&heap);
207     check_heap(&heap, NULL, 0);
208     for (i = 0; i < n; i++) {
209         uint32_t priority = insert[i];
210
211         elements[i].full_pri = priority;
212         heap_insert(&heap, &elements[i].heap_node, priority >> 16);
213         check_heap(&heap, insert, i + 1);
214     }
215
216     for (i = 0; i < n; i++) {
217         struct element *element;
218
219         HEAP_FOR_EACH (element, heap_node, &heap) {
220             if (element->full_pri == delete[i]) {
221                 goto found;
222             }
223         }
224         NOT_REACHED();
225
226     found:
227         heap_remove(&heap, &element->heap_node);
228         check_heap(&heap, delete + i + 1, n - (i + 1));
229     }
230     heap_destroy(&heap);
231 }
232
233 static void
234 test_insert_delete_raw__(struct element *elements,
235                          const uint32_t *insert, unsigned int insert_pattern,
236                          const uint32_t *delete, unsigned int delete_pattern,
237                          size_t n)
238 {
239     struct heap heap;
240     size_t i;
241
242     heap_init(&heap);
243     check_heap(&heap, NULL, 0);
244     for (i = 0; i < n; i++) {
245         uint32_t priority = insert[i];
246
247         elements[i].full_pri = priority;
248         heap_raw_insert(&heap, &elements[i].heap_node, priority >> 16);
249         if (insert_pattern & (1u << i)) {
250             heap_rebuild(&heap);
251             check_heap(&heap, insert, i + 1);
252         }
253     }
254
255     for (i = 0; i < n; i++) {
256         struct element *element;
257
258         HEAP_FOR_EACH (element, heap_node, &heap) {
259             if (element->full_pri == delete[i]) {
260                 goto found;
261             }
262         }
263         NOT_REACHED();
264
265     found:
266         heap_raw_remove(&heap, &element->heap_node);
267         if (delete_pattern & (1u << i)) {
268             heap_rebuild(&heap);
269             check_heap(&heap, delete + i + 1, n - (i + 1));
270         }
271     }
272     heap_destroy(&heap);
273 }
274
275 static void
276 test_heap_insert_delete_same_order(int argc OVS_UNUSED,
277                                    char *argv[] OVS_UNUSED)
278 {
279     enum { N_ELEMS = 7 };
280
281     uint32_t insert[N_ELEMS];
282     int n_permutations;
283     size_t i;
284
285     for (i = 0; i < N_ELEMS; i++) {
286         insert[i] = i << 16;
287     }
288
289     n_permutations = 0;
290     do {
291         struct element elements[N_ELEMS];
292
293         n_permutations++;
294         test_insert_delete__(elements, insert, insert, N_ELEMS);
295     } while (next_permutation(insert, N_ELEMS));
296     assert(n_permutations == factorial(N_ELEMS));
297 }
298
299 static void
300 test_heap_insert_delete_reverse_order(int argc OVS_UNUSED,
301                                       char *argv[] OVS_UNUSED)
302 {
303     enum { N_ELEMS = 7 };
304
305     uint32_t insert[N_ELEMS];
306     int n_permutations;
307     size_t i;
308
309     for (i = 0; i < N_ELEMS; i++) {
310         insert[i] = i << 16;
311     }
312
313     n_permutations = 0;
314     do {
315         struct element elements[N_ELEMS];
316         uint32_t delete[N_ELEMS];
317
318         n_permutations++;
319
320         for (i = 0; i < N_ELEMS; i++) {
321             delete[N_ELEMS - i - 1] = insert[i];
322         }
323
324         test_insert_delete__(elements, insert, delete, N_ELEMS);
325     } while (next_permutation(insert, N_ELEMS));
326     assert(n_permutations == factorial(N_ELEMS));
327 }
328
329 static void
330 test_heap_insert_delete_every_order(int argc OVS_UNUSED,
331                                     char *argv[] OVS_UNUSED)
332 {
333     enum { N_ELEMS = 5 };
334
335     uint32_t insert[N_ELEMS];
336     int outer_permutations;
337     size_t i;
338
339     for (i = 0; i < N_ELEMS; i++) {
340         insert[i] = i << 16;
341     }
342
343     outer_permutations = 0;
344     do {
345         struct element elements[N_ELEMS];
346         uint32_t delete[N_ELEMS];
347         int inner_permutations;
348
349         outer_permutations++;
350
351         for (i = 0; i < N_ELEMS; i++) {
352             delete[i] = i << 16;
353         }
354
355         inner_permutations = 0;
356         do {
357             inner_permutations++;
358             test_insert_delete__(elements, insert, delete, N_ELEMS);
359         } while (next_permutation(delete, N_ELEMS));
360         assert(inner_permutations == factorial(N_ELEMS));
361     } while (next_permutation(insert, N_ELEMS));
362     assert(outer_permutations == factorial(N_ELEMS));
363 }
364
365 static void
366 test_heap_insert_delete_same_order_with_dups(int argc OVS_UNUSED,
367                                              char *argv[] OVS_UNUSED)
368 {
369     enum { N_ELEMS = 7 };
370
371     unsigned int pattern;
372     size_t i;
373
374     for (pattern = 0; pattern < (1u << N_ELEMS); pattern += 2) {
375         int n_permutations, expected_permutations;
376         uint32_t insert[N_ELEMS];
377         int j;
378
379         j = 0;
380         for (i = 0; i < N_ELEMS; i++) {
381             if (i && !(pattern & (1u << i))) {
382                 j++;
383             }
384             insert[i] = (j << 16) | i;
385         }
386
387         expected_permutations = factorial(N_ELEMS);
388         for (i = 0; i < N_ELEMS; ) {
389             j = i + 1;
390             if (pattern & (1u << i)) {
391                 for (; j < N_ELEMS; j++) {
392                     if (!(pattern & (1u << j))) {
393                         break;
394                     }
395                 }
396                 expected_permutations /= factorial(j - i + 1);
397             }
398             i = j;
399         }
400
401         n_permutations = 0;
402         do {
403             struct element elements[N_ELEMS];
404
405             n_permutations++;
406             test_insert_delete__(elements, insert, insert, N_ELEMS);
407         } while (next_permutation(insert, N_ELEMS));
408         assert(n_permutations == expected_permutations);
409     }
410 }
411
412 static void
413 test_heap_raw_insert(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
414 {
415     enum { N_ELEMS = 7 };
416
417     uint32_t insert[N_ELEMS];
418     int n_permutations;
419     size_t i;
420
421     for (i = 0; i < N_ELEMS; i++) {
422         insert[i] = i << 16;
423     }
424
425     n_permutations = 0;
426     do {
427         struct element elements[N_ELEMS];
428
429         n_permutations++;
430         test_insert_delete_raw__(elements,
431                                  insert, 1u << (N_ELEMS - 1),
432                                  insert, UINT_MAX,
433                                  N_ELEMS);
434     } while (next_permutation(insert, N_ELEMS));
435     assert(n_permutations == factorial(N_ELEMS));
436 }
437
438 static void
439 test_heap_raw_delete(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
440 {
441     enum { N_ELEMS = 16 };
442
443     uint32_t insert[N_ELEMS];
444     uint32_t delete[N_ELEMS];
445     size_t i;
446
447     for (i = 0; i < N_ELEMS; i++) {
448         insert[i] = i << 16;
449         delete[i] = i << 16;
450     }
451
452     for (i = 0; i < 1000; i++) {
453         struct element elements[N_ELEMS];
454
455         shuffle(insert, N_ELEMS);
456         shuffle(delete, N_ELEMS);
457
458         test_insert_delete_raw__(elements,
459                                  insert, 0,
460                                  delete,
461                                  (1u << (N_ELEMS - 1)) | (1u << (N_ELEMS / 2)),
462                                  N_ELEMS);
463     }
464 }
465
466 static const struct command commands[] = {
467     { "insert-delete-same-order", 0, 0, test_heap_insert_delete_same_order, },
468     { "insert-delete-reverse-order", 0, 0,
469       test_heap_insert_delete_reverse_order, },
470     { "insert-delete-every-order", 0, 0,
471       test_heap_insert_delete_every_order, },
472     { "insert-delete-same-order-with-dups", 0, 0,
473       test_heap_insert_delete_same_order_with_dups, },
474     { "raw-insert", 0, 0, test_heap_raw_insert, },
475     { "raw-delete", 0, 0, test_heap_raw_delete, },
476 };
477
478 int
479 main(int argc, char *argv[])
480 {
481     set_program_name(argv[0]);
482
483     run_command(argc - 1, argv + 1, commands);
484
485     return 0;
486 }