filter/tree_test.c

   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 }