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. */
26 #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(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
278 enum { N_ELEMS
= 7 };
280 uint32_t insert
[N_ELEMS
];
284 for (i
= 0; i
< N_ELEMS
; i
++) {
290 struct element elements
[N_ELEMS
];
293 test_insert_delete__(elements
, insert
, insert
, N_ELEMS
);
294 } while (next_permutation(insert
, N_ELEMS
));
295 assert(n_permutations
== factorial(N_ELEMS
));
299 test_heap_insert_delete_reverse_order(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
301 enum { N_ELEMS
= 7 };
303 uint32_t insert
[N_ELEMS
];
307 for (i
= 0; i
< N_ELEMS
; i
++) {
313 struct element elements
[N_ELEMS
];
314 uint32_t delete[N_ELEMS
];
318 for (i
= 0; i
< N_ELEMS
; i
++) {
319 delete[N_ELEMS
- i
- 1] = insert
[i
];
322 test_insert_delete__(elements
, insert
, delete, N_ELEMS
);
323 } while (next_permutation(insert
, N_ELEMS
));
324 assert(n_permutations
== factorial(N_ELEMS
));
328 test_heap_insert_delete_every_order(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
330 enum { N_ELEMS
= 5 };
332 uint32_t insert
[N_ELEMS
];
333 int outer_permutations
;
336 for (i
= 0; i
< N_ELEMS
; i
++) {
340 outer_permutations
= 0;
342 struct element elements
[N_ELEMS
];
343 uint32_t delete[N_ELEMS
];
344 int inner_permutations
;
346 outer_permutations
++;
348 for (i
= 0; i
< N_ELEMS
; i
++) {
352 inner_permutations
= 0;
354 inner_permutations
++;
355 test_insert_delete__(elements
, insert
, delete, N_ELEMS
);
356 } while (next_permutation(delete, N_ELEMS
));
357 assert(inner_permutations
== factorial(N_ELEMS
));
358 } while (next_permutation(insert
, N_ELEMS
));
359 assert(outer_permutations
== factorial(N_ELEMS
));
363 test_heap_insert_delete_same_order_with_dups(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
365 enum { N_ELEMS
= 7 };
367 unsigned int pattern
;
370 for (pattern
= 0; pattern
< (1u << N_ELEMS
); pattern
+= 2) {
371 int n_permutations
, expected_permutations
;
372 uint32_t insert
[N_ELEMS
];
376 for (i
= 0; i
< N_ELEMS
; i
++) {
377 if (i
&& !(pattern
& (1u << i
))) {
380 insert
[i
] = (j
<< 16) | i
;
383 expected_permutations
= factorial(N_ELEMS
);
384 for (i
= 0; i
< N_ELEMS
; ) {
386 if (pattern
& (1u << i
)) {
387 for (; j
< N_ELEMS
; j
++) {
388 if (!(pattern
& (1u << j
))) {
392 expected_permutations
/= factorial(j
- i
+ 1);
399 struct element elements
[N_ELEMS
];
402 test_insert_delete__(elements
, insert
, insert
, N_ELEMS
);
403 } while (next_permutation(insert
, N_ELEMS
));
404 assert(n_permutations
== expected_permutations
);
409 test_heap_raw_insert(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
411 enum { N_ELEMS
= 7 };
413 uint32_t insert
[N_ELEMS
];
417 for (i
= 0; i
< N_ELEMS
; i
++) {
423 struct element elements
[N_ELEMS
];
426 test_insert_delete_raw__(elements
,
427 insert
, 1u << (N_ELEMS
- 1),
430 } while (next_permutation(insert
, N_ELEMS
));
431 assert(n_permutations
== factorial(N_ELEMS
));
435 test_heap_raw_delete(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
437 enum { N_ELEMS
= 16 };
439 uint32_t insert
[N_ELEMS
];
440 uint32_t delete[N_ELEMS
];
443 for (i
= 0; i
< N_ELEMS
; i
++) {
448 for (i
= 0; i
< 1000; i
++) {
449 struct element elements
[N_ELEMS
];
451 shuffle(insert
, N_ELEMS
);
452 shuffle(delete, N_ELEMS
);
454 test_insert_delete_raw__(elements
,
457 (1u << (N_ELEMS
- 1)) | (1u << (N_ELEMS
/ 2)),
462 static const struct ovs_cmdl_command commands
[] = {
463 { "insert-delete-same-order", NULL
, 0, 0,
464 test_heap_insert_delete_same_order
, },
465 { "insert-delete-reverse-order", NULL
, 0, 0,
466 test_heap_insert_delete_reverse_order
, },
467 { "insert-delete-every-order", NULL
, 0, 0,
468 test_heap_insert_delete_every_order
, },
469 { "insert-delete-same-order-with-dups", NULL
, 0, 0,
470 test_heap_insert_delete_same_order_with_dups
, },
471 { "raw-insert", NULL
, 0, 0, test_heap_raw_insert
, },
472 { "raw-delete", NULL
, 0, 0, test_heap_raw_delete
, },
473 { NULL
, NULL
, 0, 0, NULL
, },
477 test_heap_main(int argc
, char *argv
[])
479 struct ovs_cmdl_context ctx
= {
484 set_program_name(argv
[0]);
486 ovs_cmdl_run_command(&ctx
, commands
);
489 OVSTEST_REGISTER("test-heap", test_heap_main
);