Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / filter / tree_test.c @ 6b3f1a54

History | View | Annotate | Download (6.77 KB)

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 "conf/conf.h"
14

    
15
#define MAX_TREE_HEIGHT 13
16

    
17
static void
18
start_conf_env(void)
19
{
20
  bt_bird_init();
21

    
22
  pool *p = rp_new(&root_pool, "helper_pool");
23
  linpool *l = lp_new_default(p);
24
  cfg_mem = l;
25
}
26

    
27
static struct f_tree *
28
new_tree(uint id)
29
{
30
  struct f_tree *tree = f_new_tree();
31
  tree->from.type  = tree->to.type  = T_INT;
32
  tree->from.val.i = tree->to.val.i = id;
33

    
34
  return tree;
35
}
36

    
37
/*
38
 * Show subtree in infix notation
39
 */
40
static void
41
show_subtree(struct f_tree *node)
42
{
43
  if (!node)
44
    return;
45

    
46
  show_subtree(node->left);
47

    
48
  if (node->from.val.i == node->to.val.i)
49
    bt_debug("%u ", node->from.val.i);
50
  else
51
    bt_debug("%u..%u ", node->from.val.i, node->to.val.i);
52

    
53
  show_subtree(node->right);
54
}
55

    
56
static void
57
show_tree2(struct f_tree *root_node, const char *tree_name)
58
{
59
  bt_debug("%s: \n", tree_name);
60
  bt_debug("[ ");
61
  show_subtree(root_node);
62
  bt_debug("]\n\n");
63
}
64

    
65
#define show_tree(tree) show_tree2(tree, #tree);
66

    
67
static uint
68
get_nodes_count_full_bin_tree(uint height)
69
{
70
  return (bt_naive_pow(2, height+1) - 1);
71
}
72

    
73
static struct f_tree *
74
get_balanced_full_subtree(uint height, uint idx)
75
{
76
  struct f_tree *node = new_tree(idx);
77
  if (height > 0)
78
  {
79
    uint nodes_in_subtree = get_nodes_count_full_bin_tree(--height);
80
    node->left  = get_balanced_full_subtree(height, idx - nodes_in_subtree/2 - 1);
81
    node->right = get_balanced_full_subtree(height, idx + nodes_in_subtree/2 + 1);
82
  }
83
  return node;
84
}
85

    
86
static struct f_tree *
87
get_balanced_full_tree(uint height)
88
{
89
  return get_balanced_full_subtree(height, get_nodes_count_full_bin_tree(height)/2);
90
}
91

    
92
static struct f_tree *
93
get_degenerated_left_tree(uint nodes_count)
94
{
95
  struct f_tree *old = NULL;
96
  struct f_tree *new = NULL;
97
  uint i;
98

    
99
  for (i = 0; i < nodes_count; i++)
100
  {
101
    old = new;
102
    new = new_tree(nodes_count-1-i);
103
    new->left = old;
104
  }
105

    
106
  return new;
107
}
108

    
109
static struct f_tree *
110
get_random_degenerated_left_tree(uint nodes_count)
111
{
112
  struct f_tree *tree = get_degenerated_left_tree(nodes_count);
113

    
114
  size_t avaible_indexes_size = nodes_count * sizeof(byte);
115
  byte *avaible_indexes = malloc(avaible_indexes_size);
116
  memset(avaible_indexes, 0, avaible_indexes_size);
117

    
118
  struct f_tree *n;
119
  for (n = tree; n; n = n->left)
120
  {
121
    uint selected_idx;
122
    do
123
    {
124
      selected_idx = bt_random() % nodes_count;
125
    } while(avaible_indexes[selected_idx] != 0);
126

    
127
    avaible_indexes[selected_idx] = 1;
128
    n->from.type  = n->to.type  = T_INT;
129
    n->from.val.i = n->to.val.i = selected_idx;
130
  }
131

    
132
  free(avaible_indexes);
133
  return tree;
134
}
135

    
136
static struct f_tree *
137
get_balanced_tree_with_ranged_values(uint nodes_count)
138
{
139
  struct f_tree *tree = get_degenerated_left_tree(nodes_count);
140

    
141
  uint idx = 0;
142
  struct f_tree *n;
143
  for (n = tree; n; n = n->left)
144
  {
145
    n->from.type = n->to.type = T_INT;
146
    n->from.val.i = idx;
147
    idx += (uint)bt_random() / nodes_count;        /* (... / nodes_count) preventing overflow an uint idx */
148
    n->to.val.i = idx++;
149
  }
150

    
151
  return build_tree(tree);
152
}
153

    
154

    
155
static int
156
t_balancing(void)
157
{
158
  start_conf_env();
159

    
160
  uint height;
161
  for (height = 1; height < MAX_TREE_HEIGHT; height++)
162
  {
163
    uint nodes_count = get_nodes_count_full_bin_tree(height);
164

    
165
    struct f_tree *simple_degenerated_tree = get_degenerated_left_tree(nodes_count);
166
    show_tree(simple_degenerated_tree);
167

    
168
    struct f_tree *expected_balanced_tree = get_balanced_full_tree(height);
169
    show_tree(expected_balanced_tree);
170

    
171
    struct f_tree *balanced_tree_from_simple = build_tree(simple_degenerated_tree);
172
    show_tree(balanced_tree_from_simple);
173

    
174
    bt_assert(same_tree(balanced_tree_from_simple, expected_balanced_tree));
175
  }
176

    
177
  return 1;
178
}
179

    
180

    
181
static int
182
t_balancing_random(void)
183
{
184
  start_conf_env();
185

    
186
  uint height;
187
  for (height = 1; height < MAX_TREE_HEIGHT; height++)
188
  {
189
    uint nodes_count = get_nodes_count_full_bin_tree(height);
190

    
191
    struct f_tree *expected_balanced_tree = get_balanced_full_tree(height);
192

    
193
    uint i;
194
    for(i = 0; i < 10; i++)
195
    {
196
      struct f_tree *random_degenerated_tree = get_random_degenerated_left_tree(nodes_count);
197
      show_tree(random_degenerated_tree);
198

    
199
      struct f_tree *balanced_tree_from_random = build_tree(random_degenerated_tree);
200

    
201
      show_tree(expected_balanced_tree);
202
      show_tree(balanced_tree_from_random);
203

    
204
      bt_assert(same_tree(balanced_tree_from_random, expected_balanced_tree));
205
    }
206
  }
207

    
208
  return 1;
209
}
210

    
211
static int
212
t_find(void)
213
{
214
  start_conf_env();
215

    
216
  uint height;
217
  for (height = 1; height < MAX_TREE_HEIGHT; height++)
218
  {
219
    uint nodes_count = get_nodes_count_full_bin_tree(height);
220

    
221
    struct f_tree *tree = get_balanced_full_tree(height);
222
    show_tree(tree);
223

    
224
    struct f_val looking_up_value = {
225
        .type = T_INT
226
    };
227
    for(looking_up_value.val.i = 0; looking_up_value.val.i < nodes_count; looking_up_value.val.i++)
228
    {
229
      struct f_tree *found_tree = find_tree(tree, looking_up_value);
230
      bt_assert((val_compare(looking_up_value, found_tree->from) == 0) && (val_compare(looking_up_value, found_tree->to) == 0));
231
    }
232
  }
233

    
234
  return 1;
235
}
236

    
237
static uint
238
get_max_value_in_unbalanced_tree(struct f_tree *node, uint max)
239
{
240
  if (!node)
241
    return max;
242

    
243
  if (node->to.val.i > max)
244
    max = node->to.val.i;
245

    
246
  uint max_left  = get_max_value_in_unbalanced_tree(node->left, max);
247
  if (max_left > max)
248
    max = max_left;
249

    
250
  uint max_right = get_max_value_in_unbalanced_tree(node->right, max);
251
  if (max_right > max)
252
    max = max_right;
253

    
254
  return max;
255
}
256

    
257
static int
258
t_find_ranges(void)
259
{
260
  start_conf_env();
261

    
262
  uint height;
263
  for (height = 1; height < MAX_TREE_HEIGHT; height++)
264
  {
265
    uint nodes_count = get_nodes_count_full_bin_tree(height);
266

    
267
    struct f_tree *tree = get_balanced_tree_with_ranged_values(nodes_count);
268
    uint max_value = get_max_value_in_unbalanced_tree(tree, 0);
269

    
270
    show_tree(tree);
271

    
272
    bt_debug("max_value: %u \n", max_value);
273

    
274
    struct f_val needle = {
275
        .type = T_INT
276
    };
277
    uint *i = &needle.val.i;
278

    
279
    for(*i = 0; *i <= max_value; *i += (uint)bt_random()/nodes_count)
280
    {
281
      struct f_tree *found_tree = find_tree(tree, needle);
282
      bt_debug("searching: %u \n", *i);
283
      bt_assert(
284
          (val_compare(needle, found_tree->from) == 0) || (val_compare(needle, found_tree->to) == 0) ||
285
         ((val_compare(needle, found_tree->from) == 1) && (val_compare(needle, found_tree->to) == -1))
286
      );
287
    }
288
  }
289

    
290
  return 1;
291
}
292

    
293
int
294
main(int argc, char *argv[])
295
{
296
  bt_init(argc, argv);
297

    
298
  bt_test_suite(t_balancing, "Balancing strong unbalanced trees");
299
  bt_test_suite(t_balancing_random, "Balancing random unbalanced trees");
300
  bt_test_suite(t_find, "Finding values in trees");
301
  bt_test_suite(t_find_ranges, "Finding values in trees with random ranged values");
302

    
303
  return bt_exit_value();
304
}