2 * Copyright (c) 2012 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 test for for functions and macros declared in heap.h. */
24 #include "command-line.h"
31 /* Sample heap element. */
34 struct heap_node heap_node;
37 static struct element *
38 element_from_heap_node(const struct heap_node *node)
40 return CONTAINER_OF(node, struct element, heap_node);
44 compare_uint32s(const void *a_, const void *b_)
46 const uint32_t *a = a_;
47 const uint32_t *b = b_;
48 return *a < *b ? -1 : *a > *b;
51 /* Verifies that 'heap' is internally consistent and contains all 'n' of the
54 check_heap(const struct heap *heap, const uint32_t priorities[], size_t n)
56 uint32_t *priorities_copy;
57 uint32_t *elements_copy;
58 struct element *element;
61 assert(heap_count(heap) == n);
62 assert(heap_is_empty(heap) == !n);
64 assert(heap_max(heap) == heap->array[1]);
68 for (i = 1; i <= n; i++) {
69 assert(heap->array[i]->idx == i);
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));
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);
85 assert(heap->array[parent]->priority >= heap->array[i]->priority);
88 assert(heap->array[left]->priority <= heap->array[i]->priority);
91 assert(heap->array[right]->priority <= heap->array[i]->priority);
95 /* Check that HEAP_FOR_EACH iterates all the nodes in order. */
97 HEAP_FOR_EACH (element, heap_node, heap) {
99 assert(&element->heap_node == heap->array[i + 1]);
104 priorities_copy = xmemdup(priorities, n * sizeof *priorities);
105 elements_copy = xmalloc(n * sizeof *priorities);
107 HEAP_FOR_EACH (element, heap_node, heap) {
108 elements_copy[i++] = element->heap_node.priority;
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]);
117 free(priorities_copy);
122 shuffle(uint32_t *p, size_t n)
124 for (; n > 1; n--, p++) {
125 uint32_t *q = &p[random_range(n)];
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)
139 HEAP_FOR_EACH (e, heap_node, heap) {
140 printf(" %"PRIu32":%"PRIu32, e->full_pri >> 16, e->full_pri & 0xffff);
146 factorial(int n_items)
151 for (i = 2; i <= n_items; i++) {
158 swap(uint32_t *a, uint32_t *b)
166 reverse(uint32_t *a, int n)
170 for (i = 0; i < n / 2; i++) {
177 next_permutation(uint32_t *a, int n)
181 for (k = n - 2; k >= 0; k--) {
182 if ((a[k] >> 16) < (a[k + 1] >> 16)) {
185 for (l = n - 1; ; l--) {
186 if ((a[l] >> 16) > (a[k] >> 16)) {
188 reverse(a + (k + 1), n - (k + 1));
198 test_insert_delete__(struct element *elements,
199 const uint32_t *insert,
200 const uint32_t *delete,
207 check_heap(&heap, NULL, 0);
208 for (i = 0; i < n; i++) {
209 uint32_t priority = insert[i];
211 elements[i].full_pri = priority;
212 heap_insert(&heap, &elements[i].heap_node, priority >> 16);
213 check_heap(&heap, insert, i + 1);
216 for (i = 0; i < n; i++) {
217 struct element *element;
219 HEAP_FOR_EACH (element, heap_node, &heap) {
220 if (element->full_pri == delete[i]) {
227 heap_remove(&heap, &element->heap_node);
228 check_heap(&heap, delete + i + 1, n - (i + 1));
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,
243 check_heap(&heap, NULL, 0);
244 for (i = 0; i < n; i++) {
245 uint32_t priority = insert[i];
247 elements[i].full_pri = priority;
248 heap_raw_insert(&heap, &elements[i].heap_node, priority >> 16);
249 if (insert_pattern & (1u << i)) {
251 check_heap(&heap, insert, i + 1);
255 for (i = 0; i < n; i++) {
256 struct element *element;
258 HEAP_FOR_EACH (element, heap_node, &heap) {
259 if (element->full_pri == delete[i]) {
266 heap_raw_remove(&heap, &element->heap_node);
267 if (delete_pattern & (1u << i)) {
269 check_heap(&heap, delete + i + 1, n - (i + 1));
276 test_heap_insert_delete_same_order(int argc OVS_UNUSED,
277 char *argv[] OVS_UNUSED)
279 enum { N_ELEMS = 7 };
281 uint32_t insert[N_ELEMS];
285 for (i = 0; i < N_ELEMS; i++) {
291 struct element elements[N_ELEMS];
294 test_insert_delete__(elements, insert, insert, N_ELEMS);
295 } while (next_permutation(insert, N_ELEMS));
296 assert(n_permutations == factorial(N_ELEMS));
300 test_heap_insert_delete_reverse_order(int argc OVS_UNUSED,
301 char *argv[] OVS_UNUSED)
303 enum { N_ELEMS = 7 };
305 uint32_t insert[N_ELEMS];
309 for (i = 0; i < N_ELEMS; i++) {
315 struct element elements[N_ELEMS];
316 uint32_t delete[N_ELEMS];
320 for (i = 0; i < N_ELEMS; i++) {
321 delete[N_ELEMS - i - 1] = insert[i];
324 test_insert_delete__(elements, insert, delete, N_ELEMS);
325 } while (next_permutation(insert, N_ELEMS));
326 assert(n_permutations == factorial(N_ELEMS));
330 test_heap_insert_delete_every_order(int argc OVS_UNUSED,
331 char *argv[] OVS_UNUSED)
333 enum { N_ELEMS = 5 };
335 uint32_t insert[N_ELEMS];
336 int outer_permutations;
339 for (i = 0; i < N_ELEMS; i++) {
343 outer_permutations = 0;
345 struct element elements[N_ELEMS];
346 uint32_t delete[N_ELEMS];
347 int inner_permutations;
349 outer_permutations++;
351 for (i = 0; i < N_ELEMS; i++) {
355 inner_permutations = 0;
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));
366 test_heap_insert_delete_same_order_with_dups(int argc OVS_UNUSED,
367 char *argv[] OVS_UNUSED)
369 enum { N_ELEMS = 7 };
371 unsigned int pattern;
374 for (pattern = 0; pattern < (1u << N_ELEMS); pattern += 2) {
375 int n_permutations, expected_permutations;
376 uint32_t insert[N_ELEMS];
380 for (i = 0; i < N_ELEMS; i++) {
381 if (i && !(pattern & (1u << i))) {
384 insert[i] = (j << 16) | i;
387 expected_permutations = factorial(N_ELEMS);
388 for (i = 0; i < N_ELEMS; ) {
390 if (pattern & (1u << i)) {
391 for (; j < N_ELEMS; j++) {
392 if (!(pattern & (1u << j))) {
396 expected_permutations /= factorial(j - i + 1);
403 struct element elements[N_ELEMS];
406 test_insert_delete__(elements, insert, insert, N_ELEMS);
407 } while (next_permutation(insert, N_ELEMS));
408 assert(n_permutations == expected_permutations);
413 test_heap_raw_insert(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
415 enum { N_ELEMS = 7 };
417 uint32_t insert[N_ELEMS];
421 for (i = 0; i < N_ELEMS; i++) {
427 struct element elements[N_ELEMS];
430 test_insert_delete_raw__(elements,
431 insert, 1u << (N_ELEMS - 1),
434 } while (next_permutation(insert, N_ELEMS));
435 assert(n_permutations == factorial(N_ELEMS));
439 test_heap_raw_delete(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
441 enum { N_ELEMS = 16 };
443 uint32_t insert[N_ELEMS];
444 uint32_t delete[N_ELEMS];
447 for (i = 0; i < N_ELEMS; i++) {
452 for (i = 0; i < 1000; i++) {
453 struct element elements[N_ELEMS];
455 shuffle(insert, N_ELEMS);
456 shuffle(delete, N_ELEMS);
458 test_insert_delete_raw__(elements,
461 (1u << (N_ELEMS - 1)) | (1u << (N_ELEMS / 2)),
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, },
479 main(int argc, char *argv[])
481 set_program_name(argv[0]);
483 run_command(argc - 1, argv + 1, commands);