]>
Commit | Line | Data |
---|---|---|
9b0a0ba9 OZ |
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 | ||
5e3cd0e5 | 85 | return 1; |
9b0a0ba9 OZ |
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 | ||
5e3cd0e5 | 113 | return 1; |
9b0a0ba9 OZ |
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 | ||
5e3cd0e5 | 131 | return 1; |
9b0a0ba9 OZ |
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 | ||
5e3cd0e5 | 142 | return heap[0] == SPECIAL_KEY; |
9b0a0ba9 OZ |
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 | ||
5e3cd0e5 | 171 | return 1; |
9b0a0ba9 OZ |
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 | } |