Return to tree_test.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / filter

bird2 ver 2.0.7

    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: }