tests/test-heap.c

   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 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(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     for (i = 0; i < N_ELEMS; i++) {
 285         insert[i] = i << 16;
 286     }
 287
 288     n_permutations = 0;
 289     do {
 290         struct element elements[N_ELEMS];
 291
 292         n_permutations++;
 293         test_insert_delete__(elements, insert, insert, N_ELEMS);
 294     } while (next_permutation(insert, N_ELEMS));
 295     assert(n_permutations == factorial(N_ELEMS));
 296 }
 297
 298 static void
 299 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     for (i = 0; i < N_ELEMS; i++) {
 308         insert[i] = i << 16;
 309     }
 310
 311     n_permutations = 0;
 312     do {
 313         struct element elements[N_ELEMS];
 314         uint32_t delete[N_ELEMS];
 315
 316         n_permutations++;
 317
 318         for (i = 0; i < N_ELEMS; i++) {
 319             delete[N_ELEMS - i - 1] = insert[i];
 320         }
 321
 322         test_insert_delete__(elements, insert, delete, N_ELEMS);
 323     } while (next_permutation(insert, N_ELEMS));
 324     assert(n_permutations == factorial(N_ELEMS));
 325 }
 326
 327 static void
 328 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     for (i = 0; i < N_ELEMS; i++) {
 337         insert[i] = i << 16;
 338     }
 339
 340     outer_permutations = 0;
 341     do {
 342         struct element elements[N_ELEMS];
 343         uint32_t delete[N_ELEMS];
 344         int inner_permutations;
 345
 346         outer_permutations++;
 347
 348         for (i = 0; i < N_ELEMS; i++) {
 349             delete[i] = i << 16;
 350         }
 351
 352         inner_permutations = 0;
 353         do {
 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));
 360 }
 361
 362 static void
 363 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     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         j = 0;
 376         for (i = 0; i < N_ELEMS; i++) {
 377             if (i && !(pattern & (1u << i))) {
 378                 j++;
 379             }
 380             insert[i] = (j << 16) | i;
 381         }
 382
 383         expected_permutations = factorial(N_ELEMS);
 384         for (i = 0; i < N_ELEMS; ) {
 385             j = i + 1;
 386             if (pattern & (1u << i)) {
 387                 for (; j < N_ELEMS; j++) {
 388                     if (!(pattern & (1u << j))) {
 389                         break;
 390                     }
 391                 }
 392                 expected_permutations /= factorial(j - i + 1);
 393             }
 394             i = j;
 395         }
 396
 397         n_permutations = 0;
 398         do {
 399             struct element elements[N_ELEMS];
 400
 401             n_permutations++;
 402             test_insert_delete__(elements, insert, insert, N_ELEMS);
 403         } while (next_permutation(insert, N_ELEMS));
 404         assert(n_permutations == expected_permutations);
 405     }
 406 }
 407
 408 static void
 409 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     for (i = 0; i < N_ELEMS; i++) {
 418         insert[i] = i << 16;
 419     }
 420
 421     n_permutations = 0;
 422     do {
 423         struct element elements[N_ELEMS];
 424
 425         n_permutations++;
 426         test_insert_delete_raw__(elements,
 427                                  insert, 1u << (N_ELEMS - 1),
 428                                  insert, UINT_MAX,
 429                                  N_ELEMS);
 430     } while (next_permutation(insert, N_ELEMS));
 431     assert(n_permutations == factorial(N_ELEMS));
 432 }
 433
 434 static void
 435 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     for (i = 0; i < N_ELEMS; i++) {
 444         insert[i] = i << 16;
 445         delete[i] = i << 16;
 446     }
 447
 448     for (i = 0; i < 1000; i++) {
 449         struct element elements[N_ELEMS];
 450
 451         shuffle(insert, N_ELEMS);
 452         shuffle(delete, N_ELEMS);
 453
 454         test_insert_delete_raw__(elements,
 455                                  insert, 0,
 456                                  delete,
 457                                  (1u << (N_ELEMS - 1)) | (1u << (N_ELEMS / 2)),
 458                                  N_ELEMS);
 459     }
 460 }
 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 test_heap_main(int argc, char *argv[])
 478 {
 479     struct ovs_cmdl_context ctx = {
 480         .argc = argc - 1,
 481         .argv = argv + 1,
 482     };
 483
 484     set_program_name(argv[0]);
 485
 486     ovs_cmdl_run_command(&ctx, commands);
 487 }
 488
 489 OVSTEST_REGISTER("test-heap", test_heap_main);