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
);