Branch data     Line data    Source code

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