2 * Filters: Utility Functions Tests
4 * (c) 2015 CZ.NIC z.s.p.o.
6 * Can be freely distributed and used under the terms of the GNU GPL.
9 #include "test/birdtest.h"
10 #include "test/bt-utils.h"
12 #include "filter/filter.h"
13 #include "filter/data.h"
14 #include "conf/conf.h"
16 #define MAX_TREE_HEIGHT 13
23 pool
*p
= rp_new(&root_pool
, "helper_pool");
24 linpool
*l
= lp_new_default(p
);
28 static struct f_tree
*
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
;
39 * Show subtree in infix notation
42 show_subtree(struct f_tree
*node
)
47 show_subtree(node
->left
);
49 if (node
->from
.val
.i
== node
->to
.val
.i
)
50 bt_debug("%u ", node
->from
.val
.i
);
52 bt_debug("%u..%u ", node
->from
.val
.i
, node
->to
.val
.i
);
54 show_subtree(node
->right
);
58 show_tree2(struct f_tree
*root_node
, const char *tree_name
)
60 bt_debug("%s: \n", tree_name
);
62 show_subtree(root_node
);
66 #define show_tree(tree) show_tree2(tree, #tree);
69 get_nodes_count_full_bin_tree(uint height
)
71 return (bt_naive_pow(2, height
+1) - 1);
74 static struct f_tree
*
75 get_balanced_full_subtree(uint height
, uint idx
)
77 struct f_tree
*node
= new_tree(idx
);
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);
87 static struct f_tree
*
88 get_balanced_full_tree(uint height
)
90 return get_balanced_full_subtree(height
, get_nodes_count_full_bin_tree(height
)/2);
93 static struct f_tree
*
94 get_degenerated_left_tree(uint nodes_count
)
96 struct f_tree
*old
= NULL
;
97 struct f_tree
*new = NULL
;
100 for (i
= 0; i
< nodes_count
; i
++)
103 new = new_tree(nodes_count
-1-i
);
110 static struct f_tree
*
111 get_random_degenerated_left_tree(uint nodes_count
)
113 struct f_tree
*tree
= get_degenerated_left_tree(nodes_count
);
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
);
120 for (n
= tree
; n
; n
= n
->left
)
125 selected_idx
= bt_random() % nodes_count
;
126 } while(avaible_indexes
[selected_idx
] != 0);
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
;
133 free(avaible_indexes
);
137 static struct f_tree
*
138 get_balanced_tree_with_ranged_values(uint nodes_count
)
140 struct f_tree
*tree
= get_degenerated_left_tree(nodes_count
);
144 for (n
= tree
; n
; n
= n
->left
)
146 n
->from
.type
= n
->to
.type
= T_INT
;
148 idx
+= (uint
)bt_random() / nodes_count
; /* (... / nodes_count) preventing overflow an uint idx */
152 return build_tree(tree
);
162 for (height
= 1; height
< MAX_TREE_HEIGHT
; height
++)
164 uint nodes_count
= get_nodes_count_full_bin_tree(height
);
166 struct f_tree
*simple_degenerated_tree
= get_degenerated_left_tree(nodes_count
);
167 show_tree(simple_degenerated_tree
);
169 struct f_tree
*expected_balanced_tree
= get_balanced_full_tree(height
);
170 show_tree(expected_balanced_tree
);
172 struct f_tree
*balanced_tree_from_simple
= build_tree(simple_degenerated_tree
);
173 show_tree(balanced_tree_from_simple
);
175 bt_assert(same_tree(balanced_tree_from_simple
, expected_balanced_tree
));
183 t_balancing_random(void)
188 for (height
= 1; height
< MAX_TREE_HEIGHT
; height
++)
190 uint nodes_count
= get_nodes_count_full_bin_tree(height
);
192 struct f_tree
*expected_balanced_tree
= get_balanced_full_tree(height
);
195 for(i
= 0; i
< 10; i
++)
197 struct f_tree
*random_degenerated_tree
= get_random_degenerated_left_tree(nodes_count
);
198 show_tree(random_degenerated_tree
);
200 struct f_tree
*balanced_tree_from_random
= build_tree(random_degenerated_tree
);
202 show_tree(expected_balanced_tree
);
203 show_tree(balanced_tree_from_random
);
205 bt_assert(same_tree(balanced_tree_from_random
, expected_balanced_tree
));
218 for (height
= 1; height
< MAX_TREE_HEIGHT
; height
++)
220 uint nodes_count
= get_nodes_count_full_bin_tree(height
);
222 struct f_tree
*tree
= get_balanced_full_tree(height
);
225 struct f_val looking_up_value
= {
228 for(looking_up_value
.val
.i
= 0; looking_up_value
.val
.i
< nodes_count
; looking_up_value
.val
.i
++)
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));
239 get_max_value_in_unbalanced_tree(struct f_tree
*node
, uint max
)
244 if (node
->to
.val
.i
> max
)
245 max
= node
->to
.val
.i
;
247 uint max_left
= get_max_value_in_unbalanced_tree(node
->left
, max
);
251 uint max_right
= get_max_value_in_unbalanced_tree(node
->right
, max
);
264 for (height
= 1; height
< MAX_TREE_HEIGHT
; height
++)
266 uint nodes_count
= get_nodes_count_full_bin_tree(height
);
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);
273 bt_debug("max_value: %u \n", max_value
);
275 struct f_val needle
= {
278 uint
*i
= &needle
.val
.i
;
280 for(*i
= 0; *i
<= max_value
; *i
+= (uint
)bt_random()/nodes_count
)
282 const struct f_tree
*found_tree
= find_tree(tree
, &needle
);
283 bt_debug("searching: %u \n", *i
);
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))
295 main(int argc
, char *argv
[])
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");
304 return bt_exit_value();