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
22 cfg_mem
= tmp_linpool
;
25 static struct f_tree
*
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
;
36 * Show subtree in infix notation
39 show_subtree(struct f_tree
*node
)
44 show_subtree(node
->left
);
46 if (node
->from
.val
.i
== node
->to
.val
.i
)
47 bt_debug("%u ", node
->from
.val
.i
);
49 bt_debug("%u..%u ", node
->from
.val
.i
, node
->to
.val
.i
);
51 show_subtree(node
->right
);
55 show_tree2(struct f_tree
*root_node
, const char *tree_name
)
57 bt_debug("%s: \n", tree_name
);
59 show_subtree(root_node
);
63 #define show_tree(tree) show_tree2(tree, #tree);
66 get_nodes_count_full_bin_tree(uint height
)
68 return (bt_naive_pow(2, height
+1) - 1);
71 static struct f_tree
*
72 get_balanced_full_subtree(uint height
, uint idx
)
74 struct f_tree
*node
= new_tree(idx
);
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);
84 static struct f_tree
*
85 get_balanced_full_tree(uint height
)
87 return get_balanced_full_subtree(height
, get_nodes_count_full_bin_tree(height
)/2);
90 static struct f_tree
*
91 get_degenerated_left_tree(uint nodes_count
)
93 struct f_tree
*old
= NULL
;
94 struct f_tree
*new = NULL
;
97 for (i
= 0; i
< nodes_count
; i
++)
100 new = new_tree(nodes_count
-1-i
);
107 static struct f_tree
*
108 get_random_degenerated_left_tree(uint nodes_count
)
110 struct f_tree
*tree
= get_degenerated_left_tree(nodes_count
);
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
);
117 for (n
= tree
; n
; n
= n
->left
)
122 selected_idx
= bt_random() % nodes_count
;
123 } while(avaible_indexes
[selected_idx
] != 0);
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
;
130 free(avaible_indexes
);
134 static struct f_tree
*
135 get_balanced_tree_with_ranged_values(uint nodes_count
)
137 struct f_tree
*tree
= get_degenerated_left_tree(nodes_count
);
141 for (n
= tree
; n
; n
= n
->left
)
143 n
->from
.type
= n
->to
.type
= T_INT
;
145 idx
+= (uint
)bt_random() / nodes_count
; /* (... / nodes_count) preventing overflow an uint idx */
149 return build_tree(tree
);
159 for (height
= 1; height
< MAX_TREE_HEIGHT
; height
++)
161 uint nodes_count
= get_nodes_count_full_bin_tree(height
);
163 struct f_tree
*simple_degenerated_tree
= get_degenerated_left_tree(nodes_count
);
164 show_tree(simple_degenerated_tree
);
166 struct f_tree
*expected_balanced_tree
= get_balanced_full_tree(height
);
167 show_tree(expected_balanced_tree
);
169 struct f_tree
*balanced_tree_from_simple
= build_tree(simple_degenerated_tree
);
170 show_tree(balanced_tree_from_simple
);
172 bt_assert(same_tree(balanced_tree_from_simple
, expected_balanced_tree
));
180 t_balancing_random(void)
185 for (height
= 1; height
< MAX_TREE_HEIGHT
; height
++)
187 uint nodes_count
= get_nodes_count_full_bin_tree(height
);
189 struct f_tree
*expected_balanced_tree
= get_balanced_full_tree(height
);
192 for(i
= 0; i
< 10; i
++)
194 struct f_tree
*random_degenerated_tree
= get_random_degenerated_left_tree(nodes_count
);
195 show_tree(random_degenerated_tree
);
197 struct f_tree
*balanced_tree_from_random
= build_tree(random_degenerated_tree
);
199 show_tree(expected_balanced_tree
);
200 show_tree(balanced_tree_from_random
);
202 bt_assert(same_tree(balanced_tree_from_random
, expected_balanced_tree
));
215 for (height
= 1; height
< MAX_TREE_HEIGHT
; height
++)
217 uint nodes_count
= get_nodes_count_full_bin_tree(height
);
219 struct f_tree
*tree
= get_balanced_full_tree(height
);
222 struct f_val looking_up_value
= {
225 for(looking_up_value
.val
.i
= 0; looking_up_value
.val
.i
< nodes_count
; looking_up_value
.val
.i
++)
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));
236 get_max_value_in_unbalanced_tree(struct f_tree
*node
, uint max
)
241 if (node
->to
.val
.i
> max
)
242 max
= node
->to
.val
.i
;
244 uint max_left
= get_max_value_in_unbalanced_tree(node
->left
, max
);
248 uint max_right
= get_max_value_in_unbalanced_tree(node
->right
, max
);
261 for (height
= 1; height
< MAX_TREE_HEIGHT
; height
++)
263 uint nodes_count
= get_nodes_count_full_bin_tree(height
);
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);
270 bt_debug("max_value: %u \n", max_value
);
272 struct f_val needle
= {
275 uint
*i
= &needle
.val
.i
;
277 for(*i
= 0; *i
<= max_value
; *i
+= (uint
)bt_random()/nodes_count
)
279 const struct f_tree
*found_tree
= find_tree(tree
, &needle
);
280 bt_debug("searching: %u \n", *i
);
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))
292 main(int argc
, char *argv
[])
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");
301 return bt_exit_value();