Return to tree.c CVS log

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

Annotation of embedaddon/bird/filter/tree.c, revision 1.1

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