iofbirddaemon / lib / heap_test.c @ 9b0a0ba9
History  View  Annotate  Download (3.39 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" : "NONVALID 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 BT_SUCCESS;

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 BT_SUCCESS;

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 BT_SUCCESS;

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) ? BT_SUCCESS : BT_FAILURE; 
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 BT_SUCCESS;

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 pseudorandom 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 
} 