diff options
| -rw-r--r-- | filter/filter.c | 5 | ||||
| -rw-r--r-- | filter/filter.h | 1 | ||||
| -rw-r--r-- | filter/test.conf | 15 | ||||
| -rw-r--r-- | filter/tree.c | 115 |
4 files changed, 65 insertions, 71 deletions
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 * |