Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2012, 2014 Nicira, Inc.
3 : : *
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:
7 : : *
8 : : * http://www.apache.org/licenses/LICENSE-2.0
9 : : *
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.
15 : : */
16 : :
17 : : /* A test for for functions and macros declared in heap.h. */
18 : :
19 : : #include <config.h>
20 : : #undef NDEBUG
21 : : #include "heap.h"
22 : : #include <assert.h>
23 : : #include <inttypes.h>
24 : : #include <limits.h>
25 : : #include <stdlib.h>
26 : : #include "command-line.h"
27 : : #include "ovstest.h"
28 : : #include "random.h"
29 : : #include "util.h"
30 : :
31 : : /* Sample heap element. */
32 : : struct element {
33 : : uint32_t full_pri;
34 : : struct heap_node heap_node;
35 : : };
36 : :
37 : : static struct element *
38 : 3319397 : element_from_heap_node(const struct heap_node *node)
39 : : {
40 : 3319397 : return CONTAINER_OF(node, struct element, heap_node);
41 : : }
42 : :
43 : : static int
44 : 8258552 : compare_uint32s(const void *a_, const void *b_)
45 : : {
46 : 8258552 : const uint32_t *a = a_;
47 : 8258552 : const uint32_t *b = b_;
48 [ + + ]: 8258552 : return *a < *b ? -1 : *a > *b;
49 : : }
50 : :
51 : : /* Verifies that 'heap' is internally consistent and contains all 'n' of the
52 : : * 'priorities'. */
53 : : static void
54 : 1067355 : check_heap(const struct heap *heap, const uint32_t priorities[], size_t n)
55 : : {
56 : : uint32_t *priorities_copy;
57 : : uint32_t *elements_copy;
58 : : struct element *element;
59 : : size_t i;
60 : :
61 [ - + ]: 1067355 : assert(heap_count(heap) == n);
62 [ - + ]: 1067355 : assert(heap_is_empty(heap) == !n);
63 [ + + ]: 1067355 : if (n > 0) {
64 [ - + ]: 911729 : assert(heap_max(heap) == heap->array[1]);
65 : : }
66 : :
67 : : /* Check indexes. */
68 [ + + ]: 4386752 : for (i = 1; i <= n; i++) {
69 [ - + ]: 3319397 : assert(heap->array[i]->idx == i);
70 : : }
71 : :
72 : : /* Check that priority values are internally consistent. */
73 [ + + ]: 4386752 : for (i = 1; i <= n; i++) {
74 : 3319397 : element = element_from_heap_node(heap->array[i]);
75 [ - + ]: 3319397 : assert(element->heap_node.priority == (element->full_pri >> 16));
76 : : }
77 : :
78 : : /* Check the heap property. */
79 [ + + ]: 4386752 : for (i = 1; i <= n; i++) {
80 : 3319397 : size_t parent = heap_parent__(i);
81 : 3319397 : size_t left = heap_left__(i);
82 : 3319397 : size_t right = heap_right__(i);
83 : :
84 [ + + ]: 3319397 : if (parent >= 1) {
85 [ - + ]: 2407668 : assert(heap->array[parent]->priority >= heap->array[i]->priority);
86 : : }
87 [ + + ]: 3319397 : if (left <= n) {
88 [ - + ]: 1412313 : assert(heap->array[left]->priority <= heap->array[i]->priority);
89 : : }
90 [ + + ]: 3319397 : if (right <= n) {
91 [ - + ]: 995355 : assert(heap->array[right]->priority <= heap->array[i]->priority);
92 : : }
93 : : }
94 : :
95 : : /* Check that HEAP_FOR_EACH iterates all the nodes in order. */
96 : 1067355 : i = 0;
97 [ + + ][ + + ]: 4386752 : HEAP_FOR_EACH (element, heap_node, heap) {
[ + + ]
98 [ - + ]: 3319397 : assert(i < n);
99 [ - + ]: 3319397 : assert(&element->heap_node == heap->array[i + 1]);
100 : 3319397 : i++;
101 : : }
102 [ - + ]: 1067355 : assert(i == n);
103 : :
104 : 1067355 : priorities_copy = xmemdup(priorities, n * sizeof *priorities);
105 : 1067355 : elements_copy = xmalloc(n * sizeof *priorities);
106 : 1067355 : i = 0;
107 [ + + ][ + + ]: 4386752 : HEAP_FOR_EACH (element, heap_node, heap) {
[ + + ]
108 : 3319397 : elements_copy[i++] = element->heap_node.priority;
109 : : }
110 : :
111 : 1067355 : qsort(priorities_copy, n, sizeof *priorities_copy, compare_uint32s);
112 : 1067355 : qsort(elements_copy, n, sizeof *elements_copy, compare_uint32s);
113 [ + + ]: 4386752 : for (i = 0; i < n; i++) {
114 [ - + ]: 3319397 : assert((priorities_copy[i] >> 16) == elements_copy[i]);
115 : : }
116 : :
117 : 1067355 : free(priorities_copy);
118 : 1067355 : free(elements_copy);
119 : 1067355 : }
120 : :
121 : : static void
122 : 2000 : shuffle(uint32_t *p, size_t n)
123 : : {
124 [ + + ]: 32000 : for (; n > 1; n--, p++) {
125 : 30000 : uint32_t *q = &p[random_range(n)];
126 : 30000 : uint32_t tmp = *p;
127 : 30000 : *p = *q;
128 : 30000 : *q = tmp;
129 : : }
130 : 2000 : }
131 : :
132 : : /* Prints the values in 'heap', plus 'name' as a title. */
133 : : static void OVS_UNUSED
134 : 0 : print_heap(const char *name, struct heap *heap)
135 : : {
136 : : struct element *e;
137 : :
138 : 0 : printf("%s:", name);
139 [ # # ][ # # ]: 0 : HEAP_FOR_EACH (e, heap_node, heap) {
[ # # ]
140 : 0 : printf(" %"PRIu32":%"PRIu32, e->full_pri >> 16, e->full_pri & 0xffff);
141 : : }
142 : 0 : printf("\n");
143 : 0 : }
144 : :
145 : : static int
146 : 300 : factorial(int n_items)
147 : : {
148 : : int n, i;
149 : :
150 : 300 : n = 1;
151 [ + + ]: 1378 : for (i = 2; i <= n_items; i++) {
152 : 1078 : n *= i;
153 : : }
154 : 300 : return n;
155 : : }
156 : :
157 : : static void
158 : 122030 : swap(uint32_t *a, uint32_t *b)
159 : : {
160 : 122030 : uint32_t tmp = *a;
161 : 122030 : *a = *b;
162 : 122030 : *b = tmp;
163 : 122030 : }
164 : :
165 : : static void
166 : 76745 : reverse(uint32_t *a, int n)
167 : : {
168 : : int i;
169 : :
170 [ + + ]: 122030 : for (i = 0; i < n / 2; i++) {
171 : 45285 : int j = n - (i + 1);
172 : 45285 : swap(&a[i], &a[j]);
173 : : }
174 : 76745 : }
175 : :
176 : : static bool
177 : 76933 : next_permutation(uint32_t *a, int n)
178 : : {
179 : : int k;
180 : :
181 [ + + ]: 139295 : for (k = n - 2; k >= 0; k--) {
182 [ + + ]: 139107 : if ((a[k] >> 16) < (a[k + 1] >> 16)) {
183 : : int l;
184 : :
185 : 76745 : for (l = n - 1; ; l--) {
186 [ + + ]: 107483 : if ((a[l] >> 16) > (a[k] >> 16)) {
187 : 76745 : swap(&a[k], &a[l]);
188 : 76745 : reverse(a + (k + 1), n - (k + 1));
189 : 76745 : return true;
190 : : }
191 : 30738 : }
192 : : }
193 : : }
194 : 188 : return false;
195 : : }
196 : :
197 : : static void
198 : 71773 : test_insert_delete__(struct element *elements,
199 : : const uint32_t *insert,
200 : : const uint32_t *delete,
201 : : size_t n)
202 : : {
203 : : struct heap heap;
204 : : size_t i;
205 : :
206 : 71773 : heap_init(&heap);
207 : 71773 : check_heap(&heap, NULL, 0);
208 [ + + ]: 545384 : for (i = 0; i < n; i++) {
209 : 473611 : uint32_t priority = insert[i];
210 : :
211 : 473611 : elements[i].full_pri = priority;
212 : 473611 : heap_insert(&heap, &elements[i].heap_node, priority >> 16);
213 : 473611 : check_heap(&heap, insert, i + 1);
214 : : }
215 : :
216 [ + + ]: 545384 : for (i = 0; i < n; i++) {
217 : : struct element *element;
218 : :
219 [ + - ][ + - ]: 1093295 : HEAP_FOR_EACH (element, heap_node, &heap) {
[ + - ]
220 [ + + ]: 1093295 : if (element->full_pri == delete[i]) {
221 : 473611 : goto found;
222 : : }
223 : : }
224 : 0 : OVS_NOT_REACHED();
225 : :
226 : : found:
227 : 473611 : heap_remove(&heap, &element->heap_node);
228 : 473611 : check_heap(&heap, delete + i + 1, n - (i + 1));
229 : : }
230 : 71773 : heap_destroy(&heap);
231 : 71773 : }
232 : :
233 : : static void
234 : 6040 : 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,
237 : : size_t n)
238 : : {
239 : : struct heap heap;
240 : : size_t i;
241 : :
242 : 6040 : heap_init(&heap);
243 : 6040 : check_heap(&heap, NULL, 0);
244 [ + + ]: 57320 : for (i = 0; i < n; i++) {
245 : 51280 : uint32_t priority = insert[i];
246 : :
247 : 51280 : elements[i].full_pri = priority;
248 : 51280 : heap_raw_insert(&heap, &elements[i].heap_node, priority >> 16);
249 [ + + ]: 51280 : if (insert_pattern & (1u << i)) {
250 : 5040 : heap_rebuild(&heap);
251 : 5040 : check_heap(&heap, insert, i + 1);
252 : : }
253 : : }
254 : :
255 [ + + ]: 57320 : for (i = 0; i < n; i++) {
256 : : struct element *element;
257 : :
258 [ + - ][ + - ]: 162515 : HEAP_FOR_EACH (element, heap_node, &heap) {
[ + - ]
259 [ + + ]: 162515 : if (element->full_pri == delete[i]) {
260 : 51280 : goto found;
261 : : }
262 : : }
263 : 0 : OVS_NOT_REACHED();
264 : :
265 : : found:
266 : 51280 : heap_raw_remove(&heap, &element->heap_node);
267 [ + + ]: 51280 : if (delete_pattern & (1u << i)) {
268 : 37280 : heap_rebuild(&heap);
269 : 37280 : check_heap(&heap, delete + i + 1, n - (i + 1));
270 : : }
271 : : }
272 : 6040 : heap_destroy(&heap);
273 : 6040 : }
274 : :
275 : : static void
276 : 1 : test_heap_insert_delete_same_order(struct ovs_cmdl_context *ctx OVS_UNUSED)
277 : : {
278 : : enum { N_ELEMS = 7 };
279 : :
280 : : uint32_t insert[N_ELEMS];
281 : : int n_permutations;
282 : : size_t i;
283 : :
284 [ + + ]: 8 : for (i = 0; i < N_ELEMS; i++) {
285 : 7 : insert[i] = i << 16;
286 : : }
287 : :
288 : 1 : n_permutations = 0;
289 : : do {
290 : : struct element elements[N_ELEMS];
291 : :
292 : 5040 : n_permutations++;
293 : 5040 : test_insert_delete__(elements, insert, insert, N_ELEMS);
294 [ + + ]: 5040 : } while (next_permutation(insert, N_ELEMS));
295 [ - + ]: 1 : assert(n_permutations == factorial(N_ELEMS));
296 : 1 : }
297 : :
298 : : static void
299 : 1 : test_heap_insert_delete_reverse_order(struct ovs_cmdl_context *ctx OVS_UNUSED)
300 : : {
301 : : enum { N_ELEMS = 7 };
302 : :
303 : : uint32_t insert[N_ELEMS];
304 : : int n_permutations;
305 : : size_t i;
306 : :
307 [ + + ]: 8 : for (i = 0; i < N_ELEMS; i++) {
308 : 7 : insert[i] = i << 16;
309 : : }
310 : :
311 : 1 : n_permutations = 0;
312 : : do {
313 : : struct element elements[N_ELEMS];
314 : : uint32_t delete[N_ELEMS];
315 : :
316 : 5040 : n_permutations++;
317 : :
318 [ + + ]: 40320 : for (i = 0; i < N_ELEMS; i++) {
319 : 35280 : delete[N_ELEMS - i - 1] = insert[i];
320 : : }
321 : :
322 : 5040 : test_insert_delete__(elements, insert, delete, N_ELEMS);
323 [ + + ]: 5040 : } while (next_permutation(insert, N_ELEMS));
324 [ - + ]: 1 : assert(n_permutations == factorial(N_ELEMS));
325 : 1 : }
326 : :
327 : : static void
328 : 1 : test_heap_insert_delete_every_order(struct ovs_cmdl_context *ctx OVS_UNUSED)
329 : : {
330 : : enum { N_ELEMS = 5 };
331 : :
332 : : uint32_t insert[N_ELEMS];
333 : : int outer_permutations;
334 : : size_t i;
335 : :
336 [ + + ]: 6 : for (i = 0; i < N_ELEMS; i++) {
337 : 5 : insert[i] = i << 16;
338 : : }
339 : :
340 : 1 : outer_permutations = 0;
341 : : do {
342 : : struct element elements[N_ELEMS];
343 : : uint32_t delete[N_ELEMS];
344 : : int inner_permutations;
345 : :
346 : 120 : outer_permutations++;
347 : :
348 [ + + ]: 720 : for (i = 0; i < N_ELEMS; i++) {
349 : 600 : delete[i] = i << 16;
350 : : }
351 : :
352 : 120 : inner_permutations = 0;
353 : : do {
354 : 14400 : inner_permutations++;
355 : 14400 : test_insert_delete__(elements, insert, delete, N_ELEMS);
356 [ + + ]: 14400 : } while (next_permutation(delete, N_ELEMS));
357 [ - + ]: 120 : assert(inner_permutations == factorial(N_ELEMS));
358 [ + + ]: 120 : } while (next_permutation(insert, N_ELEMS));
359 [ - + ]: 1 : assert(outer_permutations == factorial(N_ELEMS));
360 : 1 : }
361 : :
362 : : static void
363 : 1 : test_heap_insert_delete_same_order_with_dups(struct ovs_cmdl_context *ctx OVS_UNUSED)
364 : : {
365 : : enum { N_ELEMS = 7 };
366 : :
367 : : unsigned int pattern;
368 : : size_t i;
369 : :
370 [ + + ]: 65 : for (pattern = 0; pattern < (1u << N_ELEMS); pattern += 2) {
371 : : int n_permutations, expected_permutations;
372 : : uint32_t insert[N_ELEMS];
373 : : int j;
374 : :
375 : 64 : j = 0;
376 [ + + ]: 512 : for (i = 0; i < N_ELEMS; i++) {
377 [ + + ][ + + ]: 448 : if (i && !(pattern & (1u << i))) {
378 : 192 : j++;
379 : : }
380 : 448 : insert[i] = (j << 16) | i;
381 : : }
382 : :
383 : 64 : expected_permutations = factorial(N_ELEMS);
384 [ + + ]: 432 : for (i = 0; i < N_ELEMS; ) {
385 : 368 : j = i + 1;
386 [ + + ]: 368 : if (pattern & (1u << i)) {
387 [ + + ]: 192 : for (; j < N_ELEMS; j++) {
388 [ + + ]: 160 : if (!(pattern & (1u << j))) {
389 : 80 : break;
390 : : }
391 : : }
392 : 112 : expected_permutations /= factorial(j - i + 1);
393 : : }
394 : 368 : i = j;
395 : : }
396 : :
397 : 64 : n_permutations = 0;
398 : : do {
399 : : struct element elements[N_ELEMS];
400 : :
401 : 47293 : n_permutations++;
402 : 47293 : test_insert_delete__(elements, insert, insert, N_ELEMS);
403 [ + + ]: 47293 : } while (next_permutation(insert, N_ELEMS));
404 [ - + ]: 64 : assert(n_permutations == expected_permutations);
405 : : }
406 : 1 : }
407 : :
408 : : static void
409 : 1 : test_heap_raw_insert(struct ovs_cmdl_context *ctx OVS_UNUSED)
410 : : {
411 : : enum { N_ELEMS = 7 };
412 : :
413 : : uint32_t insert[N_ELEMS];
414 : : int n_permutations;
415 : : size_t i;
416 : :
417 [ + + ]: 8 : for (i = 0; i < N_ELEMS; i++) {
418 : 7 : insert[i] = i << 16;
419 : : }
420 : :
421 : 1 : n_permutations = 0;
422 : : do {
423 : : struct element elements[N_ELEMS];
424 : :
425 : 5040 : n_permutations++;
426 : 5040 : test_insert_delete_raw__(elements,
427 : : insert, 1u << (N_ELEMS - 1),
428 : : insert, UINT_MAX,
429 : : N_ELEMS);
430 [ + + ]: 5040 : } while (next_permutation(insert, N_ELEMS));
431 [ - + ]: 1 : assert(n_permutations == factorial(N_ELEMS));
432 : 1 : }
433 : :
434 : : static void
435 : 1 : test_heap_raw_delete(struct ovs_cmdl_context *ctx OVS_UNUSED)
436 : : {
437 : : enum { N_ELEMS = 16 };
438 : :
439 : : uint32_t insert[N_ELEMS];
440 : : uint32_t delete[N_ELEMS];
441 : : size_t i;
442 : :
443 [ + + ]: 17 : for (i = 0; i < N_ELEMS; i++) {
444 : 16 : insert[i] = i << 16;
445 : 16 : delete[i] = i << 16;
446 : : }
447 : :
448 [ + + ]: 1001 : for (i = 0; i < 1000; i++) {
449 : : struct element elements[N_ELEMS];
450 : :
451 : 1000 : shuffle(insert, N_ELEMS);
452 : 1000 : shuffle(delete, N_ELEMS);
453 : :
454 : 1000 : test_insert_delete_raw__(elements,
455 : : insert, 0,
456 : : delete,
457 : : (1u << (N_ELEMS - 1)) | (1u << (N_ELEMS / 2)),
458 : : N_ELEMS);
459 : : }
460 : 1 : }
461 : :
462 : : static const struct ovs_cmdl_command commands[] = {
463 : : { "insert-delete-same-order", NULL, 0, 0,
464 : : test_heap_insert_delete_same_order, OVS_RO },
465 : : { "insert-delete-reverse-order", NULL, 0, 0,
466 : : test_heap_insert_delete_reverse_order, OVS_RO },
467 : : { "insert-delete-every-order", NULL, 0, 0,
468 : : test_heap_insert_delete_every_order, OVS_RO },
469 : : { "insert-delete-same-order-with-dups", NULL, 0, 0,
470 : : test_heap_insert_delete_same_order_with_dups, OVS_RO },
471 : : { "raw-insert", NULL, 0, 0, test_heap_raw_insert, OVS_RO },
472 : : { "raw-delete", NULL, 0, 0, test_heap_raw_delete, OVS_RO },
473 : : { NULL, NULL, 0, 0, NULL, OVS_RO },
474 : : };
475 : :
476 : : static void
477 : 6 : test_heap_main(int argc, char *argv[])
478 : : {
479 : 18 : struct ovs_cmdl_context ctx = {
480 : 6 : .argc = argc - 1,
481 : 6 : .argv = argv + 1,
482 : : };
483 : :
484 : 6 : set_program_name(argv[0]);
485 : :
486 : 6 : ovs_cmdl_run_command(&ctx, commands);
487 : 6 : }
488 : :
489 : 1186 : OVSTEST_REGISTER("test-heap", test_heap_main);
|
