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