lib/heap_test.c

   1 /*
   2  *      BIRD Library -- Universal Heap Macros Tests
   3  *
   4  *      (c) 2015 CZ.NIC z.s.p.o.
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 #include "test/birdtest.h"
  10 #include "sysdep/config.h"
  11 #include "lib/heap.h"
  12
  13 #define MAX_NUM 1000
  14 #define SPECIAL_KEY -3213
  15
  16 #define MY_CMP(x, y) ((x) < (y))
  17
  18 #define MY_HEAP_SWAP(heap,a,b,t)                \
  19     do {                                        \
  20       bt_debug("swap(%u %u) ", a, b);           \
  21       HEAP_SWAP(heap,a,b,t);                    \
  22     } while(0)
  23
  24 static int heap[MAX_NUM+1];
  25 static uint num;
  26
  27 /*
  28  * A valid heap must follow these rules:
  29  *   - `num >= 0`
  30  *   - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
  31  */
  32 static int
  33 is_heap_valid(int heap[], uint num)
  34 {
  35   uint i;
  36
  37   if (num > MAX_NUM)
  38     return 0;
  39
  40   for (i = 2; i <= num; i++)
  41     if (heap[i] < heap[i / 2])
  42       return 0;
  43
  44   return 1;
  45 }
  46
  47 static void
  48 show_heap(void)
  49 {
  50   uint i;
  51   bt_debug("\n");
  52   bt_debug("numbers %u; ", num);
  53   for (i = 0; i <= num; i++)
  54     bt_debug("%d ", heap[i]);
  55   bt_debug(is_heap_valid(heap, num) ? "OK" : "NON-VALID HEAP!");
  56   bt_debug("\n");
  57 }
  58
  59 static void
  60 init_heap(void)
  61 {
  62   uint i;
  63   num = 0;
  64   heap[0] = SPECIAL_KEY;                /* heap[0] should be unused */
  65   for (i = 1; i <= MAX_NUM; i++)
  66     heap[i] = 0;
  67 }
  68
  69 static int
  70 t_heap_insert(void)
  71 {
  72   uint i;
  73
  74   init_heap();
  75
  76   for (i = MAX_NUM; i >= 1; i--)
  77   {
  78     bt_debug("ins %u at pos %u ", i, MAX_NUM - i);
  79     heap[MAX_NUM - i + 1] = i;
  80     HEAP_INSERT(heap, ++num, int, MY_CMP, MY_HEAP_SWAP);
  81     show_heap();
  82     bt_assert(is_heap_valid(heap, num));
  83   }
  84
  85   return 1;
  86 }
  87
  88 static int
  89 t_heap_increase_decrease(void)
  90 {
  91   uint i;
  92
  93   t_heap_insert();
  94
  95   for (i = 1; i <= MAX_NUM; i++)
  96   {
  97     if ((int)i > heap[i])
  98     {
  99       bt_debug("inc %u ", i);
 100       heap[i] = i;
 101       HEAP_INCREASE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
 102     }
 103     else if ((int)i < heap[i])
 104     {
 105       bt_debug("dec %u ", i);
 106       heap[i] = i;
 107       HEAP_INCREASE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
 108     }
 109     show_heap();
 110     bt_assert(is_heap_valid(heap, num));
 111   }
 112
 113   return 1;
 114 }
 115
 116 static int
 117 t_heap_delete(void)
 118 {
 119   uint i;
 120
 121   t_heap_insert();
 122
 123   for (i = 1; i <= num; i++)
 124   {
 125     bt_debug("del at pos %u ", i);
 126     HEAP_DELETE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
 127     show_heap();
 128     bt_assert(is_heap_valid(heap, num));
 129   }
 130
 131   return 1;
 132 }
 133
 134 static int
 135 t_heap_0(void)
 136 {
 137   init_heap();
 138   t_heap_insert();
 139   t_heap_increase_decrease();
 140   t_heap_delete();
 141
 142   return heap[0] == SPECIAL_KEY;
 143 }
 144
 145 static int
 146 t_heap_insert_random(void)
 147 {
 148   int i, j;
 149   int expected[MAX_NUM+1];
 150
 151   init_heap();
 152
 153   for (i = 1; i <= MAX_NUM; i++)
 154   {
 155     heap[i] = expected[i] = bt_random();
 156     HEAP_INSERT(heap, ++num, int, MY_CMP, MY_HEAP_SWAP);
 157     show_heap();
 158     bt_assert(is_heap_valid(heap, num));
 159   }
 160
 161   for (i = 1; i <= MAX_NUM; i++)
 162     for (j = 1; j <= MAX_NUM; j++)
 163       if(expected[i] == heap[j])
 164         break;
 165       else if (j == MAX_NUM)
 166       {
 167         show_heap();
 168         bt_abort_msg("Did not find a number %d in heap.", expected[i]);
 169       }
 170
 171   return 1;
 172 }
 173
 174 int
 175 main(int argc, char *argv[])
 176 {
 177   bt_init(argc, argv);
 178
 179   bt_test_suite(t_heap_insert, "Inserting a descending sequence of numbers (the worst case)");
 180   bt_test_suite(t_heap_insert_random, "Inserting pseudo-random numbers");
 181   bt_test_suite(t_heap_increase_decrease, "Increasing/Decreasing");
 182   bt_test_suite(t_heap_delete, "Deleting");
 183   bt_test_suite(t_heap_0, "Is a heap[0] really unused?");
 184
 185   return bt_exit_value();
 186 }