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