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

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