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"
13: #include "filter/data.h"
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");
24: linpool *l = lp_new_default(p);
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:
178: return 1;
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:
209: return 1;
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: {
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));
232: }
233: }
234:
235: return 1;
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: {
282: const struct f_tree *found_tree = find_tree(tree, &needle);
283: bt_debug("searching: %u \n", *i);
284: bt_assert(
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))
287: );
288: }
289: }
290:
291: return 1;
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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>