Return to tree.c CVS log

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

bird2 ver 2.0.7

    1: /*
    2:  *	Filters: utility functions
    3:  *
    4:  *	Copyright 1998 Pavel Machek <pavel@ucw.cz>
    5:  *
    6:  *	Can be freely distributed and used under the terms of the GNU GPL.
    7:  */
    8: 
    9: #include "lib/alloca.h"
   10: #include "nest/bird.h"
   11: #include "conf/conf.h"
   12: #include "filter/filter.h"
   13: #include "filter/data.h"
   14: 
   15: /**
   16:  * find_tree
   17:  * @t: tree to search in
   18:  * @val: value to find
   19:  *
   20:  * Search for given value in the tree. I relies on fact that sorted tree is populated
   21:  * by &f_val structures (that can be compared by val_compare()). In each node of tree, 
   22:  * either single value (then t->from==t->to) or range is present.
   23:  *
   24:  * Both set matching and |switch() { }| construction is implemented using this function,
   25:  * thus both are as fast as they can be.
   26:  */
   27: const struct f_tree *
   28: find_tree(const struct f_tree *t, const struct f_val *val)
   29: {
   30:   if (!t)
   31:     return NULL;
   32:   if ((val_compare(&(t->from), val) != 1) &&
   33:       (val_compare(&(t->to), val) != -1))
   34:     return t;
   35:   if (val_compare(&(t->from), val) == -1)
   36:     return find_tree(t->right, val);
   37:   else
   38:     return find_tree(t->left, val);
   39: }
   40: 
   41: static struct f_tree *
   42: build_tree_rec(struct f_tree **buf, int l, int h)
   43: {
   44:   struct f_tree *n;
   45:   int pos;
   46: 
   47:   if (l >= h)
   48:     return NULL;
   49: 
   50:   pos = (l+h)/2;
   51:   n = buf[pos];
   52:   n->left = build_tree_rec(buf, l, pos);
   53:   n->right = build_tree_rec(buf, pos+1, h);
   54:   return n;
   55: }
   56: 
   57: static int 
   58: tree_compare(const void *p1, const void *p2)
   59: {
   60:   return val_compare(&((* (struct f_tree **) p1)->from), &((* (struct f_tree **) p2)->from));
   61: }
   62: 
   63: /**
   64:  * build_tree
   65:  * @from: degenerated tree (linked by @tree->left) to be transformed into form suitable for find_tree()
   66:  *
   67:  * Transforms degenerated tree into balanced tree.
   68:  */
   69: struct f_tree *
   70: build_tree(struct f_tree *from)
   71: {
   72:   struct f_tree *tmp, *root;
   73:   struct f_tree **buf;
   74:   int len, i;
   75: 
   76:   if (from == NULL)
   77:     return NULL;
   78: 
   79:   len = 0;
   80:   for (tmp = from; tmp != NULL; tmp = tmp->left)
   81:     len++;
   82: 
   83:   if (len <= 1024)
   84:     buf = alloca(len * sizeof(struct f_tree *));
   85:   else
   86:     buf = xmalloc(len * sizeof(struct f_tree *));
   87: 
   88:   /* Convert a degenerated tree into an sorted array */
   89:   i = 0;
   90:   for (tmp = from; tmp != NULL; tmp = tmp->left)
   91:     buf[i++] = tmp;
   92: 
   93:   qsort(buf, len, sizeof(struct f_tree *), tree_compare);
   94: 
   95:   root = build_tree_rec(buf, 0, len);
   96: 
   97:   if (len > 1024)
   98:     xfree(buf);
   99: 
  100:   return root;
  101: }
  102: 
  103: struct f_tree *
  104: f_new_tree(void)
  105: {
  106:   struct f_tree * ret;
  107:   ret = cfg_alloc(sizeof(struct f_tree));
  108:   ret->left = ret->right = NULL;
  109:   ret->from.type = ret->to.type = T_VOID;
  110:   ret->from.val.i = ret->to.val.i = 0;
  111:   ret->data = NULL;
  112:   return ret;
  113: }
  114: 
  115: /**
  116:  * same_tree
  117:  * @t1: first tree to be compared
  118:  * @t2: second one
  119:  *
  120:  * Compares two trees and returns 1 if they are same
  121:  */
  122: int
  123: same_tree(const struct f_tree *t1, const struct f_tree *t2)
  124: {
  125:   if ((!!t1) != (!!t2))
  126:     return 0;
  127:   if (!t1)
  128:     return 1;
  129:   if (val_compare(&(t1->from), &(t2->from)))
  130:     return 0;
  131:   if (val_compare(&(t1->to), &(t2->to)))
  132:     return 0;
  133:   if (!same_tree(t1->left, t2->left))
  134:     return 0;
  135:   if (!same_tree(t1->right, t2->right))
  136:     return 0;
  137:   if (!f_same(t1->data, t2->data))
  138:     return 0;
  139:   return 1;
  140: }
  141: 
  142: 
  143: static void
  144: tree_node_format(const struct f_tree *t, buffer *buf)
  145: {
  146:   if (t == NULL)
  147:     return;
  148: 
  149:   tree_node_format(t->left, buf);
  150: 
  151:   val_format(&(t->from), buf);
  152:   if (val_compare(&(t->from), &(t->to)) != 0)
  153:   {
  154:     buffer_puts(buf, "..");
  155:     val_format(&(t->to), buf);
  156:   }
  157:   buffer_puts(buf, ", ");
  158: 
  159:   tree_node_format(t->right, buf);
  160: }
  161: 
  162: void
  163: tree_format(const struct f_tree *t, buffer *buf)
  164: {
  165:   buffer_puts(buf, "[");
  166: 
  167:   tree_node_format(t, buf);
  168: 
  169:   if (buf->pos == buf->end)
  170:     return;
  171: 
  172:   /* Undo last separator */
  173:   if (buf->pos[-1] != '[')
  174:     buf->pos -= 2;
  175: 
  176:   buffer_puts(buf, "]");
  177: }