Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / lib / heap_test.c @ 6b3f1a54

History | View | Annotate | Download (3.33 KB)

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
}