tests/test-heap.c

   1 /*
   2  * Copyright (c) 2012 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 #include "heap.h"
  21 #include <inttypes.h>
  22 #include <limits.h>
  23 #include <stdlib.h>
  24 #include "command-line.h"
  25 #include "random.h"
  26 #include "util.h"
  27
  28 #undef NDEBUG
  29 #include <assert.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 element_from_heap_node(const struct heap_node *node)
  39 {
  40     return CONTAINER_OF(node, struct element, heap_node);
  41 }
  42
  43 static int
  44 compare_uint32s(const void *a_, const void *b_)
  45 {
  46     const uint32_t *a = a_;
  47     const uint32_t *b = b_;
  48     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 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     assert(heap_count(heap) == n);
  62     assert(heap_is_empty(heap) == !n);
  63     if (n > 0) {
  64         assert(heap_max(heap) == heap->array[1]);
  65     }
  66
  67     /* Check indexes. */
  68     for (i = 1; i <= n; i++) {
  69         assert(heap->array[i]->idx == i);
  70     }
  71
  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));
  76     }
  77
  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);
  83
  84         if (parent >= 1) {
  85             assert(heap->array[parent]->priority >= heap->array[i]->priority);
  86         }
  87         if (left <= n) {
  88             assert(heap->array[left]->priority <= heap->array[i]->priority);
  89         }
  90         if (right <= n) {
  91             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     i = 0;
  97     HEAP_FOR_EACH (element, heap_node, heap) {
  98         assert(i < n);
  99         assert(&element->heap_node == heap->array[i + 1]);
 100         i++;
 101     }
 102     assert(i == n);
 103
 104     priorities_copy = xmemdup(priorities, n * sizeof *priorities);
 105     elements_copy = xmalloc(n * sizeof *priorities);
 106     i = 0;
 107     HEAP_FOR_EACH (element, heap_node, heap) {
 108         elements_copy[i++] = element->heap_node.priority;
 109     }
 110
 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]);
 115     }
 116
 117     free(priorities_copy);
 118     free(elements_copy);
 119 }
 120
 121 static void
 122 shuffle(uint32_t *p, size_t n)
 123 {
 124     for (; n > 1; n--, p++) {
 125         uint32_t *q = &p[random_range(n)];
 126         uint32_t tmp = *p;
 127         *p = *q;
 128         *q = tmp;
 129     }
 130 }
 131
 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)
 135 {
 136     struct element *e;
 137
 138     printf("%s:", name);
 139     HEAP_FOR_EACH (e, heap_node, heap) {
 140         printf(" %"PRIu32":%"PRIu32, e->full_pri >> 16, e->full_pri & 0xffff);
 141     }
 142     printf("\n");
 143 }
 144
 145 static int
 146 factorial(int n_items)
 147 {
 148     int n, i;
 149
 150     n = 1;
 151     for (i = 2; i <= n_items; i++) {
 152         n *= i;
 153     }
 154     return n;
 155 }
 156
 157 static void
 158 swap(uint32_t *a, uint32_t *b)
 159 {
 160     uint32_t tmp = *a;
 161     *a = *b;
 162     *b = tmp;
 163 }
 164
 165 static void
 166 reverse(uint32_t *a, int n)
 167 {
 168     int i;
 169
 170     for (i = 0; i < n / 2; i++) {
 171         int j = n - (i + 1);
 172         swap(&a[i], &a[j]);
 173     }
 174 }
 175
 176 static bool
 177 next_permutation(uint32_t *a, int n)
 178 {
 179     int k;
 180
 181     for (k = n - 2; k >= 0; k--) {
 182         if ((a[k] >> 16) < (a[k + 1] >> 16)) {
 183             int l;
 184
 185             for (l = n - 1; ; l--) {
 186                 if ((a[l] >> 16) > (a[k] >> 16)) {
 187                     swap(&a[k], &a[l]);
 188                     reverse(a + (k + 1), n - (k + 1));
 189                     return true;
 190                 }
 191             }
 192         }
 193     }
 194     return false;
 195 }
 196
 197 static void
 198 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     heap_init(&heap);
 207     check_heap(&heap, NULL, 0);
 208     for (i = 0; i < n; i++) {
 209         uint32_t priority = insert[i];
 210
 211         elements[i].full_pri = priority;
 212         heap_insert(&heap, &elements[i].heap_node, priority >> 16);
 213         check_heap(&heap, insert, i + 1);
 214     }
 215
 216     for (i = 0; i < n; i++) {
 217         struct element *element;
 218
 219         HEAP_FOR_EACH (element, heap_node, &heap) {
 220             if (element->full_pri == delete[i]) {
 221                 goto found;
 222             }
 223         }
 224         OVS_NOT_REACHED();
 225
 226     found:
 227         heap_remove(&heap, &element->heap_node);
 228         check_heap(&heap, delete + i + 1, n - (i + 1));
 229     }
 230     heap_destroy(&heap);
 231 }
 232
 233 static void
 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,
 237                          size_t n)
 238 {
 239     struct heap heap;
 240     size_t i;
 241
 242     heap_init(&heap);
 243     check_heap(&heap, NULL, 0);
 244     for (i = 0; i < n; i++) {
 245         uint32_t priority = insert[i];
 246
 247         elements[i].full_pri = priority;
 248         heap_raw_insert(&heap, &elements[i].heap_node, priority >> 16);
 249         if (insert_pattern & (1u << i)) {
 250             heap_rebuild(&heap);
 251             check_heap(&heap, insert, i + 1);
 252         }
 253     }
 254
 255     for (i = 0; i < n; i++) {
 256         struct element *element;
 257
 258         HEAP_FOR_EACH (element, heap_node, &heap) {
 259             if (element->full_pri == delete[i]) {
 260                 goto found;
 261             }
 262         }
 263         OVS_NOT_REACHED();
 264
 265     found:
 266         heap_raw_remove(&heap, &element->heap_node);
 267         if (delete_pattern & (1u << i)) {
 268             heap_rebuild(&heap);
 269             check_heap(&heap, delete + i + 1, n - (i + 1));
 270         }
 271     }
 272     heap_destroy(&heap);
 273 }
 274
 275 static void
 276 test_heap_insert_delete_same_order(int argc OVS_UNUSED,
 277                                    char *argv[] OVS_UNUSED)
 278 {
 279     enum { N_ELEMS = 7 };
 280
 281     uint32_t insert[N_ELEMS];
 282     int n_permutations;
 283     size_t i;
 284
 285     for (i = 0; i < N_ELEMS; i++) {
 286         insert[i] = i << 16;
 287     }
 288
 289     n_permutations = 0;
 290     do {
 291         struct element elements[N_ELEMS];
 292
 293         n_permutations++;
 294         test_insert_delete__(elements, insert, insert, N_ELEMS);
 295     } while (next_permutation(insert, N_ELEMS));
 296     assert(n_permutations == factorial(N_ELEMS));
 297 }
 298
 299 static void
 300 test_heap_insert_delete_reverse_order(int argc OVS_UNUSED,
 301                                       char *argv[] OVS_UNUSED)
 302 {
 303     enum { N_ELEMS = 7 };
 304
 305     uint32_t insert[N_ELEMS];
 306     int n_permutations;
 307     size_t i;
 308
 309     for (i = 0; i < N_ELEMS; i++) {
 310         insert[i] = i << 16;
 311     }
 312
 313     n_permutations = 0;
 314     do {
 315         struct element elements[N_ELEMS];
 316         uint32_t delete[N_ELEMS];
 317
 318         n_permutations++;
 319
 320         for (i = 0; i < N_ELEMS; i++) {
 321             delete[N_ELEMS - i - 1] = insert[i];
 322         }
 323
 324         test_insert_delete__(elements, insert, delete, N_ELEMS);
 325     } while (next_permutation(insert, N_ELEMS));
 326     assert(n_permutations == factorial(N_ELEMS));
 327 }
 328
 329 static void
 330 test_heap_insert_delete_every_order(int argc OVS_UNUSED,
 331                                     char *argv[] OVS_UNUSED)
 332 {
 333     enum { N_ELEMS = 5 };
 334
 335     uint32_t insert[N_ELEMS];
 336     int outer_permutations;
 337     size_t i;
 338
 339     for (i = 0; i < N_ELEMS; i++) {
 340         insert[i] = i << 16;
 341     }
 342
 343     outer_permutations = 0;
 344     do {
 345         struct element elements[N_ELEMS];
 346         uint32_t delete[N_ELEMS];
 347         int inner_permutations;
 348
 349         outer_permutations++;
 350
 351         for (i = 0; i < N_ELEMS; i++) {
 352             delete[i] = i << 16;
 353         }
 354
 355         inner_permutations = 0;
 356         do {
 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));
 363 }
 364
 365 static void
 366 test_heap_insert_delete_same_order_with_dups(int argc OVS_UNUSED,
 367                                              char *argv[] OVS_UNUSED)
 368 {
 369     enum { N_ELEMS = 7 };
 370
 371     unsigned int pattern;
 372     size_t i;
 373
 374     for (pattern = 0; pattern < (1u << N_ELEMS); pattern += 2) {
 375         int n_permutations, expected_permutations;
 376         uint32_t insert[N_ELEMS];
 377         int j;
 378
 379         j = 0;
 380         for (i = 0; i < N_ELEMS; i++) {
 381             if (i && !(pattern & (1u << i))) {
 382                 j++;
 383             }
 384             insert[i] = (j << 16) | i;
 385         }
 386
 387         expected_permutations = factorial(N_ELEMS);
 388         for (i = 0; i < N_ELEMS; ) {
 389             j = i + 1;
 390             if (pattern & (1u << i)) {
 391                 for (; j < N_ELEMS; j++) {
 392                     if (!(pattern & (1u << j))) {
 393                         break;
 394                     }
 395                 }
 396                 expected_permutations /= factorial(j - i + 1);
 397             }
 398             i = j;
 399         }
 400
 401         n_permutations = 0;
 402         do {
 403             struct element elements[N_ELEMS];
 404
 405             n_permutations++;
 406             test_insert_delete__(elements, insert, insert, N_ELEMS);
 407         } while (next_permutation(insert, N_ELEMS));
 408         assert(n_permutations == expected_permutations);
 409     }
 410 }
 411
 412 static void
 413 test_heap_raw_insert(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 414 {
 415     enum { N_ELEMS = 7 };
 416
 417     uint32_t insert[N_ELEMS];
 418     int n_permutations;
 419     size_t i;
 420
 421     for (i = 0; i < N_ELEMS; i++) {
 422         insert[i] = i << 16;
 423     }
 424
 425     n_permutations = 0;
 426     do {
 427         struct element elements[N_ELEMS];
 428
 429         n_permutations++;
 430         test_insert_delete_raw__(elements,
 431                                  insert, 1u << (N_ELEMS - 1),
 432                                  insert, UINT_MAX,
 433                                  N_ELEMS);
 434     } while (next_permutation(insert, N_ELEMS));
 435     assert(n_permutations == factorial(N_ELEMS));
 436 }
 437
 438 static void
 439 test_heap_raw_delete(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 440 {
 441     enum { N_ELEMS = 16 };
 442
 443     uint32_t insert[N_ELEMS];
 444     uint32_t delete[N_ELEMS];
 445     size_t i;
 446
 447     for (i = 0; i < N_ELEMS; i++) {
 448         insert[i] = i << 16;
 449         delete[i] = i << 16;
 450     }
 451
 452     for (i = 0; i < 1000; i++) {
 453         struct element elements[N_ELEMS];
 454
 455         shuffle(insert, N_ELEMS);
 456         shuffle(delete, N_ELEMS);
 457
 458         test_insert_delete_raw__(elements,
 459                                  insert, 0,
 460                                  delete,
 461                                  (1u << (N_ELEMS - 1)) | (1u << (N_ELEMS / 2)),
 462                                  N_ELEMS);
 463     }
 464 }
 465
 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, },
 476 };
 477
 478 int
 479 main(int argc, char *argv[])
 480 {
 481     set_program_name(argv[0]);
 482
 483     run_command(argc - 1, argv + 1, commands);
 484
 485     return 0;
 486 }