summaryrefslogtreecommitdiffstats
path: root/filter
diff options
context:
space:
mode:
authorOndrej Zajicek <santiago@crfreenet.org>2010-03-11 18:55:59 +0100
committerOndrej Zajicek <santiago@crfreenet.org>2010-03-11 18:55:59 +0100
commit54305181f6ee3af57dd3d15d53ea2e851b36ed23 (patch)
treea5aed631b68df033cba372f841d47a0cba5d7021 /filter
parente7b76b976084006e430543f4b872f624326dbfe6 (diff)
parentafa9f66c27e2f96b92059131def53cc7b2497705 (diff)
downloadbird-54305181f6ee3af57dd3d15d53ea2e851b36ed23.tar
bird-54305181f6ee3af57dd3d15d53ea2e851b36ed23.zip
Merge branch 'new' into socket2
Diffstat (limited to 'filter')
-rw-r--r--filter/config.Y13
-rw-r--r--filter/filter.c5
-rw-r--r--filter/filter.h1
-rw-r--r--filter/test.conf15
-rw-r--r--filter/tree.c115
5 files changed, 72 insertions, 77 deletions
diff --git a/filter/config.Y b/filter/config.Y
index f8674e5..fcbee71 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -273,16 +273,17 @@ fprefix_set:
;
switch_body: /* EMPTY */ { $$ = NULL; }
- | set_item ':' cmds switch_body {
- $$ = $1;
- $$->data = $3;
- $$->left = $4;
+ | switch_body set_item ':' cmds {
+ $$ = $2;
+ $$->data = $4;
+ $$->left = $1;
}
- | ELSE ':' cmds {
+ | switch_body ELSE ':' cmds {
$$ = f_new_tree();
$$->from.type = T_VOID;
$$->to.type = T_VOID;
- $$->data = $3;
+ $$->data = $4;
+ $$->left = $1;
}
;
diff --git a/filter/filter.c b/filter/filter.c
index b88039f..ec155ee 100644
--- a/filter/filter.c
+++ b/filter/filter.c
@@ -164,6 +164,11 @@ val_compare(struct f_val v1, struct f_val v2)
}
}
+int
+tree_compare(const void *p1, const void *p2)
+{
+ return val_compare((* (struct f_tree **) p1)->from, (* (struct f_tree **) p2)->from);
+}
void
f_prefix_get_bounds(struct f_prefix *px, int *l, int *h)
diff --git a/filter/filter.h b/filter/filter.h
index e526a79..11e0623 100644
--- a/filter/filter.h
+++ b/filter/filter.h
@@ -91,6 +91,7 @@ void f_prefix_get_bounds(struct f_prefix *px, int *l, int *h);
void f_prefix_get_bounds(struct f_prefix *px, int *l, int *h);
int val_compare(struct f_val v1, struct f_val v2);
+int tree_compare(const void *p1, const void *p2);
void val_print(struct f_val v);
#define F_NOP 0
diff --git a/filter/test.conf b/filter/test.conf
index fb35afb..395699b 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -131,6 +131,9 @@ prefix px;
ip p;
pair pp;
int set is;
+int set is1;
+int set is2;
+int set is3;
prefix set pxs;
string s;
{
@@ -156,6 +159,18 @@ string s;
print " must be true: ", defined(1), ",", defined(1.2.3.4), ",", 1 != 2, ",", 1 <= 2;
print " data types: must be false: ", 1 ~ [ 2, 3, 4 ], ",", 5 ~ is, ",", 1.2.3.4 ~ [ 1.2.3.3, 1.2.3.5 ], ",", (1,2) > (2,2), ",", (1,1) > (1,1), ",", 1.0.0.0/9 ~ [ 1.0.0.0/8- ], ",", 1.2.0.0/17 ~ [ 1.0.0.0/8{ 15 , 16 } ], ",", true && false;
+ is1 = [2, 3, 5, 8, 11, 15, 17, 19];
+ is2 = [19, 17, 15, 11, 8, 5, 3, 2];
+ is3 = [5, 17, 2, 11, 8, 15, 3, 19];
+
+ print " must be true: ", 2 ~ is1, " ", 2 ~ is2, " ", 2 ~ is3;
+ print " must be false: ", 4 ~ is1, " ", 4 ~ is2, " ", 4 ~ is3;
+ print " must be false: ", 10 ~ is1, " ", 10 ~ is2, " ", 10 ~ is3;
+ print " must be true: ", 15 ~ is1, " ", 15 ~ is2, " ", 15 ~ is3;
+ print " must be false: ", 18 ~ is1, " ", 18 ~ is2, " ", 18 ~ is3;
+ print " must be true: ", 19 ~ is1, " ", 19 ~ is2, " ", 19 ~ is3;
+ print " must be false: ", 20 ~ is1, " ", 20 ~ is2, " ", 20 ~ is3;
+
px = 1.2.0.0/18;
print "Testing prefixes: 1.2.0.0/18 = ", px;
print " must be true: ", 192.168.0.0/16 ~ 192.168.0.0/16, " ", 192.168.0.0/17 ~ 192.168.0.0/16, " ", 192.168.254.0/24 ~ 192.168.0.0/16;
diff --git a/filter/tree.c b/filter/tree.c
index a67ddd0..f6ab75b 100644
--- a/filter/tree.c
+++ b/filter/tree.c
@@ -6,61 +6,11 @@
* Can be freely distributed and used under the terms of the GNU GPL.
*/
+#include "lib/alloca.h"
#include "nest/bird.h"
#include "conf/conf.h"
#include "filter/filter.h"
-/*
- * find_nth - finds n-th element in linked list. Don't be confused by types, it is really a linked list.
- */
-static struct f_tree *
-find_nth(struct f_tree *from, int nth)
-{
- struct f_tree *pivot;
- int lcount = 0, rcount = 0;
- struct f_tree *left, *right, *next;
-
- pivot = from;
-
- left = right = NULL;
- next = from->right;
- while (from = next) {
- next = from->right;
- if (val_compare(pivot->from, from->from)==1) {
- from->right = left;
- left = from;
- lcount++;
- } else {
- from->right = right;
- right = from;
- rcount++;
- }
- }
- if (lcount == nth)
- return pivot;
- if (lcount < nth)
- return find_nth(right, nth-lcount-1);
- return find_nth(left, nth);
-}
-
-/*
- * find_median - Gets list linked by @left, finds its median, trashes pointers in @right.
- */
-static struct f_tree *
-find_median(struct f_tree *from)
-{
- struct f_tree *t = from;
- int cnt = 0;
-
- if (!from)
- return NULL;
- do {
- t->right = t->left;
- cnt++;
- } while (t = t->left);
- return find_nth(from, cnt/2);
-}
-
/**
* find_tree
* @t: tree to search in
@@ -87,6 +37,23 @@ find_tree(struct f_tree *t, struct f_val val)
return find_tree(t->left, val);
}
+static struct f_tree *
+build_tree_rec(struct f_tree **buf, int l, int h)
+{
+ struct f_tree *n;
+ int pos;
+
+ if (l >= h)
+ return NULL;
+
+ pos = (l+h)/2;
+ n = buf[pos];
+ n->left = build_tree_rec(buf, l, pos);
+ n->right = build_tree_rec(buf, pos+1, h);
+ return n;
+}
+
+
/**
* build_tree
* @from: degenerated tree (linked by @tree->left) to be transformed into form suitable for find_tree()
@@ -96,29 +63,35 @@ find_tree(struct f_tree *t, struct f_val val)
struct f_tree *
build_tree(struct f_tree *from)
{
- struct f_tree *median, *t = from, *next, *left = NULL, *right = NULL;
+ struct f_tree *tmp, *root;
+ struct f_tree **buf;
+ int len, i;
- median = find_median(from);
- if (!median)
+ if (from == NULL)
return NULL;
- do {
- next = t->left;
- if (t == median)
- continue;
-
- if (val_compare(median->from, t->from)==1) {
- t->left = left;
- left = t;
- } else {
- t->left = right;
- right = t;
- }
- } while(t = next);
-
- median->left = build_tree(left);
- median->right = build_tree(right);
- return median;
+ len = 0;
+ for (tmp = from; tmp != NULL; tmp = tmp->left)
+ len++;
+
+ if (len <= 1024)
+ buf = alloca(len * sizeof(struct f_tree *));
+ else
+ buf = malloc(len * sizeof(struct f_tree *));
+
+ /* Convert a degenerated tree into an sorted array */
+ i = 0;
+ for (tmp = from; tmp != NULL; tmp = tmp->left)
+ buf[i++] = tmp;
+
+ qsort(buf, len, sizeof(struct f_tree *), tree_compare);
+
+ root = build_tree_rec(buf, 0, len);
+
+ if (len > 1024)
+ free(buf);
+
+ return root;
}
struct f_tree *