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