git.ozlabs.org Git - ccan/blob - ccan/heap/test/run.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3
   4 #include <ccan/heap/heap.h>
   5 /* Include the C files directly. */
   6 #include <ccan/heap/heap.c>
   7 #include <ccan/tap/tap.h>
   8
   9 struct item {
  10         void *foobar;
  11         int v;
  12 };
  13
  14 static bool heap_ok(const struct heap *h, heap_less_func_t less, int i)
  15 {
  16         int l, r;
  17
  18         l = 2 * i + 1;
  19         r = l + 1;
  20
  21         if (l < h->len) {
  22                 if (less(h->data[l], h->data[i])) {
  23                         fprintf(stderr, "heap property violation\n");
  24                         return false;
  25                 }
  26                 if (!heap_ok(h, less, l))
  27                         return false;
  28         }
  29         if (r < h->len) {
  30                 if (less(h->data[r], h->data[i])) {
  31                         fprintf(stderr, "heap property violation\n");
  32                         return false;
  33                 }
  34                 if (!heap_ok(h, less, r))
  35                         return false;
  36         }
  37         return true;
  38 }
  39
  40 static bool less(const struct item *a, const struct item *b)
  41 {
  42         return a->v < b->v;
  43 }
  44
  45 static bool __less(const void *a, const void *b)
  46 {
  47         return less(a, b);
  48 }
  49
  50 static bool more(const struct item *a, const struct item *b)
  51 {
  52         return a->v > b->v;
  53 }
  54
  55 static bool __more(const void *a, const void *b)
  56 {
  57         return more(a, b);
  58 }
  59
  60 static bool some_test(size_t n, bool is_less)
  61 {
  62         struct item *items = calloc(n, sizeof(*items));
  63         struct item *item, *prev;
  64         struct heap *h;
  65         int i;
  66
  67         if (items == NULL) {
  68                 perror("items");
  69                 exit(EXIT_FAILURE);
  70         }
  71
  72         if (is_less)
  73                 h = heap_init(__less);
  74         else
  75                 h = heap_init(__more);
  76         if (h == NULL) {
  77                 perror("heap_init");
  78                 exit(EXIT_FAILURE);
  79         }
  80
  81         for (i = 0; i < n; i++) {
  82                 item = &items[i];
  83
  84                 item->v = rand();
  85                 printf("pushing %d\n", item->v);
  86                 heap_push(h, item);
  87                 if (!heap_ok(h, is_less ? __less : __more, 0))
  88                         return false;
  89         }
  90         if (is_less) {
  91                 heap_ify(h, __more);
  92                 if (!heap_ok(h, __more, 0))
  93                         return false;
  94                 heap_ify(h, __less);
  95                 if (!heap_ok(h, __less, 0))
  96                         return false;
  97         } else {
  98                 heap_ify(h, NULL);
  99                 if (!heap_ok(h, __more, 0))
 100                         return false;
 101         }
 102
 103         for (i = 0; i < n; i++) {
 104                 item = heap_pop(h);
 105                 if (!heap_ok(h, is_less ? __less : __more, 0))
 106                         return false;
 107                 printf("popped %d\n", item->v);
 108                 if (i > 0) {
 109                         if (is_less) {
 110                                 if (less(item, prev))
 111                                         return false;
 112                         } else {
 113                                 if (more(item, prev))
 114                                         return false;
 115                         }
 116                 }
 117                 prev = item;
 118         }
 119         heap_free(h);
 120         free(items);
 121         return true;
 122 }
 123
 124 int main(void)
 125 {
 126         plan_tests(3);
 127
 128         ok1(some_test(5000, true));
 129         ok1(some_test(1, true));
 130         ok1(some_test(33, false));
 131
 132         return exit_status();
 133 }