2 * Copyright (c) 2012, 2014 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"
32 /* Sample heap element. */
35 struct heap_node heap_node;
38 static struct element *
39 element_from_heap_node(const struct heap_node *node)
41 return CONTAINER_OF(node, struct element, heap_node);
45 compare_uint32s(const void *a_, const void *b_)
47 const uint32_t *a = a_;
48 const uint32_t *b = b_;
49 return *a < *b ? -1 : *a > *b;
52 /* Verifies that 'heap' is internally consistent and contains all 'n' of the
55 check_heap(const struct heap *heap, const uint32_t priorities[], size_t n)
57 uint32_t *priorities_copy;
58 uint32_t *elements_copy;
59 struct element *element;
62 assert(heap_count(heap) == n);
63 assert(heap_is_empty(heap) == !n);
65 assert(heap_max(heap) == heap->array[1]);
69 for (i = 1; i <= n; i++) {
70 assert(heap->array[i]->idx == i);
73 /* Check that priority values are internally consistent. */
74 for (i = 1; i <= n; i++) {
75 element = element_from_heap_node(heap->array[i]);
76 assert(element->heap_node.priority == (element->full_pri >> 16));
79 /* Check the heap property. */
80 for (i = 1; i <= n; i++) {
81 size_t parent = heap_parent__(i);
82 size_t left = heap_left__(i);
83 size_t right = heap_right__(i);
86 assert(heap->array[parent]->priority >= heap->array[i]->priority);
89 assert(heap->array[left]->priority <= heap->array[i]->priority);
92 assert(heap->array[right]->priority <= heap->array[i]->priority);
96 /* Check that HEAP_FOR_EACH iterates all the nodes in order. */
98 HEAP_FOR_EACH (element, heap_node, heap) {
100 assert(&element->heap_node == heap->array[i + 1]);
105 priorities_copy = xmemdup(priorities, n * sizeof *priorities);
106 elements_copy = xmalloc(n * sizeof *priorities);
108 HEAP_FOR_EACH (element, heap_node, heap) {
109 elements_copy[i++] = element->heap_node.priority;
112 qsort(priorities_copy, n, sizeof *priorities_copy, compare_uint32s);
113 qsort(elements_copy, n, sizeof *elements_copy, compare_uint32s);
114 for (i = 0; i < n; i++) {
115 assert((priorities_copy[i] >> 16) == elements_copy[i]);
118 free(priorities_copy);
123 shuffle(uint32_t *p, size_t n)
125 for (; n > 1; n--, p++) {
126 uint32_t *q = &p[random_range(n)];
133 /* Prints the values in 'heap', plus 'name' as a title. */
134 static void OVS_UNUSED
135 print_heap(const char *name, struct heap *heap)
140 HEAP_FOR_EACH (e, heap_node, heap) {
141 printf(" %"PRIu32":%"PRIu32, e->full_pri >> 16, e->full_pri & 0xffff);
147 factorial(int n_items)
152 for (i = 2; i <= n_items; i++) {
159 swap(uint32_t *a, uint32_t *b)
167 reverse(uint32_t *a, int n)
171 for (i = 0; i < n / 2; i++) {
178 next_permutation(uint32_t *a, int n)
182 for (k = n - 2; k >= 0; k--) {
183 if ((a[k] >> 16) < (a[k + 1] >> 16)) {
186 for (l = n - 1; ; l--) {
187 if ((a[l] >> 16) > (a[k] >> 16)) {
189 reverse(a + (k + 1), n - (k + 1));
199 test_insert_delete__(struct element *elements,
200 const uint32_t *insert,
201 const uint32_t *delete,
208 check_heap(&heap, NULL, 0);
209 for (i = 0; i < n; i++) {
210 uint32_t priority = insert[i];
212 elements[i].full_pri = priority;
213 heap_insert(&heap, &elements[i].heap_node, priority >> 16);
214 check_heap(&heap, insert, i + 1);
217 for (i = 0; i < n; i++) {
218 struct element *element;
220 HEAP_FOR_EACH (element, heap_node, &heap) {
221 if (element->full_pri == delete[i]) {
228 heap_remove(&heap, &element->heap_node);
229 check_heap(&heap, delete + i + 1, n - (i + 1));
235 test_insert_delete_raw__(struct element *elements,
236 const uint32_t *insert, unsigned int insert_pattern,
237 const uint32_t *delete, unsigned int delete_pattern,
244 check_heap(&heap, NULL, 0);
245 for (i = 0; i < n; i++) {
246 uint32_t priority = insert[i];
248 elements[i].full_pri = priority;
249 heap_raw_insert(&heap, &elements[i].heap_node, priority >> 16);
250 if (insert_pattern & (1u << i)) {
252 check_heap(&heap, insert, i + 1);
256 for (i = 0; i < n; i++) {
257 struct element *element;
259 HEAP_FOR_EACH (element, heap_node, &heap) {
260 if (element->full_pri == delete[i]) {
267 heap_raw_remove(&heap, &element->heap_node);
268 if (delete_pattern & (1u << i)) {
270 check_heap(&heap, delete + i + 1, n - (i + 1));
277 test_heap_insert_delete_same_order(int argc OVS_UNUSED,
278 char *argv[] OVS_UNUSED)
280 enum { N_ELEMS = 7 };
282 uint32_t insert[N_ELEMS];
286 for (i = 0; i < N_ELEMS; i++) {
292 struct element elements[N_ELEMS];
295 test_insert_delete__(elements, insert, insert, N_ELEMS);
296 } while (next_permutation(insert, N_ELEMS));
297 assert(n_permutations == factorial(N_ELEMS));
301 test_heap_insert_delete_reverse_order(int argc OVS_UNUSED,
302 char *argv[] OVS_UNUSED)
304 enum { N_ELEMS = 7 };
306 uint32_t insert[N_ELEMS];
310 for (i = 0; i < N_ELEMS; i++) {
316 struct element elements[N_ELEMS];
317 uint32_t delete[N_ELEMS];
321 for (i = 0; i < N_ELEMS; i++) {
322 delete[N_ELEMS - i - 1] = insert[i];
325 test_insert_delete__(elements, insert, delete, N_ELEMS);
326 } while (next_permutation(insert, N_ELEMS));
327 assert(n_permutations == factorial(N_ELEMS));
331 test_heap_insert_delete_every_order(int argc OVS_UNUSED,
332 char *argv[] OVS_UNUSED)
334 enum { N_ELEMS = 5 };
336 uint32_t insert[N_ELEMS];
337 int outer_permutations;
340 for (i = 0; i < N_ELEMS; i++) {
344 outer_permutations = 0;
346 struct element elements[N_ELEMS];
347 uint32_t delete[N_ELEMS];
348 int inner_permutations;
350 outer_permutations++;
352 for (i = 0; i < N_ELEMS; i++) {
356 inner_permutations = 0;
358 inner_permutations++;
359 test_insert_delete__(elements, insert, delete, N_ELEMS);
360 } while (next_permutation(delete, N_ELEMS));
361 assert(inner_permutations == factorial(N_ELEMS));
362 } while (next_permutation(insert, N_ELEMS));
363 assert(outer_permutations == factorial(N_ELEMS));
367 test_heap_insert_delete_same_order_with_dups(int argc OVS_UNUSED,
368 char *argv[] OVS_UNUSED)
370 enum { N_ELEMS = 7 };
372 unsigned int pattern;
375 for (pattern = 0; pattern < (1u << N_ELEMS); pattern += 2) {
376 int n_permutations, expected_permutations;
377 uint32_t insert[N_ELEMS];
381 for (i = 0; i < N_ELEMS; i++) {
382 if (i && !(pattern & (1u << i))) {
385 insert[i] = (j << 16) | i;
388 expected_permutations = factorial(N_ELEMS);
389 for (i = 0; i < N_ELEMS; ) {
391 if (pattern & (1u << i)) {
392 for (; j < N_ELEMS; j++) {
393 if (!(pattern & (1u << j))) {
397 expected_permutations /= factorial(j - i + 1);
404 struct element elements[N_ELEMS];
407 test_insert_delete__(elements, insert, insert, N_ELEMS);
408 } while (next_permutation(insert, N_ELEMS));
409 assert(n_permutations == expected_permutations);
414 test_heap_raw_insert(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
416 enum { N_ELEMS = 7 };
418 uint32_t insert[N_ELEMS];
422 for (i = 0; i < N_ELEMS; i++) {
428 struct element elements[N_ELEMS];
431 test_insert_delete_raw__(elements,
432 insert, 1u << (N_ELEMS - 1),
435 } while (next_permutation(insert, N_ELEMS));
436 assert(n_permutations == factorial(N_ELEMS));
440 test_heap_raw_delete(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
442 enum { N_ELEMS = 16 };
444 uint32_t insert[N_ELEMS];
445 uint32_t delete[N_ELEMS];
448 for (i = 0; i < N_ELEMS; i++) {
453 for (i = 0; i < 1000; i++) {
454 struct element elements[N_ELEMS];
456 shuffle(insert, N_ELEMS);
457 shuffle(delete, N_ELEMS);
459 test_insert_delete_raw__(elements,
462 (1u << (N_ELEMS - 1)) | (1u << (N_ELEMS / 2)),
467 static const struct command commands[] = {
468 { "insert-delete-same-order", 0, 0, test_heap_insert_delete_same_order, },
469 { "insert-delete-reverse-order", 0, 0,
470 test_heap_insert_delete_reverse_order, },
471 { "insert-delete-every-order", 0, 0,
472 test_heap_insert_delete_every_order, },
473 { "insert-delete-same-order-with-dups", 0, 0,
474 test_heap_insert_delete_same_order_with_dups, },
475 { "raw-insert", 0, 0, test_heap_raw_insert, },
476 { "raw-delete", 0, 0, test_heap_raw_delete, },
477 { NULL, 0, 0, NULL, },
481 test_heap_main(int argc, char *argv[])
483 set_program_name(argv[0]);
485 run_command(argc - 1, argv + 1, commands);
488 OVSTEST_REGISTER("test-heap", test_heap_main);