filter/tree.c

   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/f-util.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 }