]>
Commit | Line | Data |
---|---|---|
9b0a0ba9 OZ |
1 | /* |
2 | * Filters: Utility Functions 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 "test/bt-utils.h" | |
11 | ||
12 | #include "filter/filter.h" | |
4f082dfa | 13 | #include "filter/data.h" |
9b0a0ba9 OZ |
14 | #include "conf/conf.h" |
15 | ||
16 | #define MAX_TREE_HEIGHT 13 | |
17 | ||
18 | static void | |
19 | start_conf_env(void) | |
20 | { | |
21 | bt_bird_init(); | |
22 | ||
23 | pool *p = rp_new(&root_pool, "helper_pool"); | |
05d47bd5 | 24 | linpool *l = lp_new_default(p); |
9b0a0ba9 OZ |
25 | cfg_mem = l; |
26 | } | |
27 | ||
28 | static struct f_tree * | |
29 | new_tree(uint id) | |
30 | { | |
31 | struct f_tree *tree = f_new_tree(); | |
32 | tree->from.type = tree->to.type = T_INT; | |
33 | tree->from.val.i = tree->to.val.i = id; | |
34 | ||
35 | return tree; | |
36 | } | |
37 | ||
38 | /* | |
39 | * Show subtree in infix notation | |
40 | */ | |
41 | static void | |
42 | show_subtree(struct f_tree *node) | |
43 | { | |
44 | if (!node) | |
45 | return; | |
46 | ||
47 | show_subtree(node->left); | |
48 | ||
49 | if (node->from.val.i == node->to.val.i) | |
50 | bt_debug("%u ", node->from.val.i); | |
51 | else | |
52 | bt_debug("%u..%u ", node->from.val.i, node->to.val.i); | |
53 | ||
54 | show_subtree(node->right); | |
55 | } | |
56 | ||
57 | static void | |
58 | show_tree2(struct f_tree *root_node, const char *tree_name) | |
59 | { | |
60 | bt_debug("%s: \n", tree_name); | |
61 | bt_debug("[ "); | |
62 | show_subtree(root_node); | |
63 | bt_debug("]\n\n"); | |
64 | } | |
65 | ||
66 | #define show_tree(tree) show_tree2(tree, #tree); | |
67 | ||
68 | static uint | |
69 | get_nodes_count_full_bin_tree(uint height) | |
70 | { | |
71 | return (bt_naive_pow(2, height+1) - 1); | |
72 | } | |
73 | ||
74 | static struct f_tree * | |
75 | get_balanced_full_subtree(uint height, uint idx) | |
76 | { | |
77 | struct f_tree *node = new_tree(idx); | |
78 | if (height > 0) | |
79 | { | |
80 | uint nodes_in_subtree = get_nodes_count_full_bin_tree(--height); | |
81 | node->left = get_balanced_full_subtree(height, idx - nodes_in_subtree/2 - 1); | |
82 | node->right = get_balanced_full_subtree(height, idx + nodes_in_subtree/2 + 1); | |
83 | } | |
84 | return node; | |
85 | } | |
86 | ||
87 | static struct f_tree * | |
88 | get_balanced_full_tree(uint height) | |
89 | { | |
90 | return get_balanced_full_subtree(height, get_nodes_count_full_bin_tree(height)/2); | |
91 | } | |
92 | ||
93 | static struct f_tree * | |
94 | get_degenerated_left_tree(uint nodes_count) | |
95 | { | |
96 | struct f_tree *old = NULL; | |
97 | struct f_tree *new = NULL; | |
98 | uint i; | |
99 | ||
100 | for (i = 0; i < nodes_count; i++) | |
101 | { | |
102 | old = new; | |
103 | new = new_tree(nodes_count-1-i); | |
104 | new->left = old; | |
105 | } | |
106 | ||
107 | return new; | |
108 | } | |
109 | ||
110 | static struct f_tree * | |
111 | get_random_degenerated_left_tree(uint nodes_count) | |
112 | { | |
113 | struct f_tree *tree = get_degenerated_left_tree(nodes_count); | |
114 | ||
115 | size_t avaible_indexes_size = nodes_count * sizeof(byte); | |
116 | byte *avaible_indexes = malloc(avaible_indexes_size); | |
117 | memset(avaible_indexes, 0, avaible_indexes_size); | |
118 | ||
119 | struct f_tree *n; | |
120 | for (n = tree; n; n = n->left) | |
121 | { | |
122 | uint selected_idx; | |
123 | do | |
124 | { | |
125 | selected_idx = bt_random() % nodes_count; | |
126 | } while(avaible_indexes[selected_idx] != 0); | |
127 | ||
128 | avaible_indexes[selected_idx] = 1; | |
129 | n->from.type = n->to.type = T_INT; | |
130 | n->from.val.i = n->to.val.i = selected_idx; | |
131 | } | |
132 | ||
133 | free(avaible_indexes); | |
134 | return tree; | |
135 | } | |
136 | ||
137 | static struct f_tree * | |
138 | get_balanced_tree_with_ranged_values(uint nodes_count) | |
139 | { | |
140 | struct f_tree *tree = get_degenerated_left_tree(nodes_count); | |
141 | ||
142 | uint idx = 0; | |
143 | struct f_tree *n; | |
144 | for (n = tree; n; n = n->left) | |
145 | { | |
146 | n->from.type = n->to.type = T_INT; | |
147 | n->from.val.i = idx; | |
148 | idx += (uint)bt_random() / nodes_count; /* (... / nodes_count) preventing overflow an uint idx */ | |
149 | n->to.val.i = idx++; | |
150 | } | |
151 | ||
152 | return build_tree(tree); | |
153 | } | |
154 | ||
155 | ||
156 | static int | |
157 | t_balancing(void) | |
158 | { | |
159 | start_conf_env(); | |
160 | ||
161 | uint height; | |
162 | for (height = 1; height < MAX_TREE_HEIGHT; height++) | |
163 | { | |
164 | uint nodes_count = get_nodes_count_full_bin_tree(height); | |
165 | ||
166 | struct f_tree *simple_degenerated_tree = get_degenerated_left_tree(nodes_count); | |
167 | show_tree(simple_degenerated_tree); | |
168 | ||
169 | struct f_tree *expected_balanced_tree = get_balanced_full_tree(height); | |
170 | show_tree(expected_balanced_tree); | |
171 | ||
172 | struct f_tree *balanced_tree_from_simple = build_tree(simple_degenerated_tree); | |
173 | show_tree(balanced_tree_from_simple); | |
174 | ||
175 | bt_assert(same_tree(balanced_tree_from_simple, expected_balanced_tree)); | |
176 | } | |
177 | ||
5e3cd0e5 | 178 | return 1; |
9b0a0ba9 OZ |
179 | } |
180 | ||
181 | ||
182 | static int | |
183 | t_balancing_random(void) | |
184 | { | |
185 | start_conf_env(); | |
186 | ||
187 | uint height; | |
188 | for (height = 1; height < MAX_TREE_HEIGHT; height++) | |
189 | { | |
190 | uint nodes_count = get_nodes_count_full_bin_tree(height); | |
191 | ||
192 | struct f_tree *expected_balanced_tree = get_balanced_full_tree(height); | |
193 | ||
194 | uint i; | |
195 | for(i = 0; i < 10; i++) | |
196 | { | |
197 | struct f_tree *random_degenerated_tree = get_random_degenerated_left_tree(nodes_count); | |
198 | show_tree(random_degenerated_tree); | |
199 | ||
200 | struct f_tree *balanced_tree_from_random = build_tree(random_degenerated_tree); | |
201 | ||
202 | show_tree(expected_balanced_tree); | |
203 | show_tree(balanced_tree_from_random); | |
204 | ||
205 | bt_assert(same_tree(balanced_tree_from_random, expected_balanced_tree)); | |
206 | } | |
207 | } | |
208 | ||
5e3cd0e5 | 209 | return 1; |
9b0a0ba9 OZ |
210 | } |
211 | ||
212 | static int | |
213 | t_find(void) | |
214 | { | |
215 | start_conf_env(); | |
216 | ||
217 | uint height; | |
218 | for (height = 1; height < MAX_TREE_HEIGHT; height++) | |
219 | { | |
220 | uint nodes_count = get_nodes_count_full_bin_tree(height); | |
221 | ||
222 | struct f_tree *tree = get_balanced_full_tree(height); | |
223 | show_tree(tree); | |
224 | ||
225 | struct f_val looking_up_value = { | |
226 | .type = T_INT | |
227 | }; | |
228 | for(looking_up_value.val.i = 0; looking_up_value.val.i < nodes_count; looking_up_value.val.i++) | |
229 | { | |
4c553c5a MM |
230 | const struct f_tree *found_tree = find_tree(tree, &looking_up_value); |
231 | bt_assert((val_compare(&looking_up_value, &(found_tree->from)) == 0) && (val_compare(&looking_up_value, &(found_tree->to)) == 0)); | |
9b0a0ba9 OZ |
232 | } |
233 | } | |
234 | ||
5e3cd0e5 | 235 | return 1; |
9b0a0ba9 OZ |
236 | } |
237 | ||
238 | static uint | |
239 | get_max_value_in_unbalanced_tree(struct f_tree *node, uint max) | |
240 | { | |
241 | if (!node) | |
242 | return max; | |
243 | ||
244 | if (node->to.val.i > max) | |
245 | max = node->to.val.i; | |
246 | ||
247 | uint max_left = get_max_value_in_unbalanced_tree(node->left, max); | |
248 | if (max_left > max) | |
249 | max = max_left; | |
250 | ||
251 | uint max_right = get_max_value_in_unbalanced_tree(node->right, max); | |
252 | if (max_right > max) | |
253 | max = max_right; | |
254 | ||
255 | return max; | |
256 | } | |
257 | ||
258 | static int | |
259 | t_find_ranges(void) | |
260 | { | |
261 | start_conf_env(); | |
262 | ||
263 | uint height; | |
264 | for (height = 1; height < MAX_TREE_HEIGHT; height++) | |
265 | { | |
266 | uint nodes_count = get_nodes_count_full_bin_tree(height); | |
267 | ||
268 | struct f_tree *tree = get_balanced_tree_with_ranged_values(nodes_count); | |
269 | uint max_value = get_max_value_in_unbalanced_tree(tree, 0); | |
270 | ||
271 | show_tree(tree); | |
272 | ||
273 | bt_debug("max_value: %u \n", max_value); | |
274 | ||
275 | struct f_val needle = { | |
276 | .type = T_INT | |
277 | }; | |
278 | uint *i = &needle.val.i; | |
279 | ||
280 | for(*i = 0; *i <= max_value; *i += (uint)bt_random()/nodes_count) | |
281 | { | |
4c553c5a | 282 | const struct f_tree *found_tree = find_tree(tree, &needle); |
9b0a0ba9 OZ |
283 | bt_debug("searching: %u \n", *i); |
284 | bt_assert( | |
4c553c5a MM |
285 | (val_compare(&needle, &(found_tree->from)) == 0) || (val_compare(&needle, &(found_tree->to)) == 0) || |
286 | ((val_compare(&needle, &(found_tree->from)) == 1) && (val_compare(&needle, &(found_tree->to)) == -1)) | |
9b0a0ba9 OZ |
287 | ); |
288 | } | |
289 | } | |
290 | ||
5e3cd0e5 | 291 | return 1; |
9b0a0ba9 OZ |
292 | } |
293 | ||
294 | int | |
295 | main(int argc, char *argv[]) | |
296 | { | |
297 | bt_init(argc, argv); | |
298 | ||
299 | bt_test_suite(t_balancing, "Balancing strong unbalanced trees"); | |
300 | bt_test_suite(t_balancing_random, "Balancing random unbalanced trees"); | |
301 | bt_test_suite(t_find, "Finding values in trees"); | |
302 | bt_test_suite(t_find_ranges, "Finding values in trees with random ranged values"); | |
303 | ||
304 | return bt_exit_value(); | |
305 | } |