heap_test.c 3.33 KB
Newer Older
Ondřej Zajíček's avatar
Ondřej Zajíček committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
/*
 *	BIRD Library -- Universal Heap Macros Tests
 *
 *	(c) 2015 CZ.NIC z.s.p.o.
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#include "test/birdtest.h"
#include "sysdep/config.h"
#include "lib/heap.h"

#define MAX_NUM 1000
#define SPECIAL_KEY -3213

#define MY_CMP(x, y) ((x) < (y))

#define MY_HEAP_SWAP(heap,a,b,t)		\
    do {					\
      bt_debug("swap(%u %u) ", a, b);		\
      HEAP_SWAP(heap,a,b,t);			\
    } while(0)

static int heap[MAX_NUM+1];
static uint num;

/*
 * A valid heap must follow these rules:
 *   - `num >= 0`
 *   - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
 */
static int
is_heap_valid(int heap[], uint num)
{
  uint i;

  if (num > MAX_NUM)
    return 0;

  for (i = 2; i <= num; i++)
    if (heap[i] < heap[i / 2])
      return 0;

  return 1;
}

static void
show_heap(void)
{
  uint i;
  bt_debug("\n");
  bt_debug("numbers %u; ", num);
  for (i = 0; i <= num; i++)
    bt_debug("%d ", heap[i]);
  bt_debug(is_heap_valid(heap, num) ? "OK" : "NON-VALID HEAP!");
  bt_debug("\n");
}

static void
init_heap(void)
{
  uint i;
  num = 0;
  heap[0] = SPECIAL_KEY;		/* heap[0] should be unused */
  for (i = 1; i <= MAX_NUM; i++)
    heap[i] = 0;
}

static int
t_heap_insert(void)
{
  uint i;

  init_heap();

  for (i = MAX_NUM; i >= 1; i--)
  {
    bt_debug("ins %u at pos %u ", i, MAX_NUM - i);
    heap[MAX_NUM - i + 1] = i;
    HEAP_INSERT(heap, ++num, int, MY_CMP, MY_HEAP_SWAP);
    show_heap();
    bt_assert(is_heap_valid(heap, num));
  }

85
  return 1;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
}

static int
t_heap_increase_decrease(void)
{
  uint i;

  t_heap_insert();

  for (i = 1; i <= MAX_NUM; i++)
  {
    if ((int)i > heap[i])
    {
      bt_debug("inc %u ", i);
      heap[i] = i;
      HEAP_INCREASE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
    }
    else if ((int)i < heap[i])
    {
      bt_debug("dec %u ", i);
      heap[i] = i;
      HEAP_INCREASE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
    }
    show_heap();
    bt_assert(is_heap_valid(heap, num));
  }

113
  return 1;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
}

static int
t_heap_delete(void)
{
  uint i;

  t_heap_insert();

  for (i = 1; i <= num; i++)
  {
    bt_debug("del at pos %u ", i);
    HEAP_DELETE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
    show_heap();
    bt_assert(is_heap_valid(heap, num));
  }

131
  return 1;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
132 133 134 135 136 137 138 139 140 141
}

static int
t_heap_0(void)
{
  init_heap();
  t_heap_insert();
  t_heap_increase_decrease();
  t_heap_delete();

142
  return heap[0] == SPECIAL_KEY;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170
}

static int
t_heap_insert_random(void)
{
  int i, j;
  int expected[MAX_NUM+1];

  init_heap();

  for (i = 1; i <= MAX_NUM; i++)
  {
    heap[i] = expected[i] = bt_random();
    HEAP_INSERT(heap, ++num, int, MY_CMP, MY_HEAP_SWAP);
    show_heap();
    bt_assert(is_heap_valid(heap, num));
  }

  for (i = 1; i <= MAX_NUM; i++)
    for (j = 1; j <= MAX_NUM; j++)
      if(expected[i] == heap[j])
	break;
      else if (j == MAX_NUM)
      {
	show_heap();
	bt_abort_msg("Did not find a number %d in heap.", expected[i]);
      }

171
  return 1;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186
}

int
main(int argc, char *argv[])
{
  bt_init(argc, argv);

  bt_test_suite(t_heap_insert, "Inserting a descending sequence of numbers (the worst case)");
  bt_test_suite(t_heap_insert_random, "Inserting pseudo-random numbers");
  bt_test_suite(t_heap_increase_decrease, "Increasing/Decreasing");
  bt_test_suite(t_heap_delete, "Deleting");
  bt_test_suite(t_heap_0, "Is a heap[0] really unused?");

  return bt_exit_value();
}