summaryrefslogtreecommitdiff
path: root/filter
diff options
context:
space:
mode:
Diffstat (limited to 'filter')
-rw-r--r--filter/Makefile2
-rw-r--r--filter/config.Y24
-rw-r--r--filter/filter.c107
-rw-r--r--filter/filter.h13
-rw-r--r--filter/tree.c125
5 files changed, 235 insertions, 36 deletions
diff --git a/filter/Makefile b/filter/Makefile
index 81bd355b..f41d7a3d 100644
--- a/filter/Makefile
+++ b/filter/Makefile
@@ -1,4 +1,4 @@
-source=f-util.c filter.c
+source=f-util.c filter.c tree.c
root-rel=../
dir-name=filter
diff --git a/filter/config.Y b/filter/config.Y
index a3eeef7e..4f910c26 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -18,7 +18,7 @@ CF_HDR
CF_DECLS
-CF_KEYWORDS(FUNCTION, PRINTDEBUG, PRINT, CONST, PUTS,
+CF_KEYWORDS(FUNCTION, PRINT, CONST,
ACCEPT, REJECT, ERROR, QUITBIRD,
INT, BOOL, IP, PREFIX, PAIR, SET, STRING,
IF, THEN, ELSE,
@@ -29,6 +29,8 @@ CF_KEYWORDS(FUNCTION, PRINTDEBUG, PRINT, CONST, PUTS,
%type <x> term block cmds cmd function_body ifthen constant print_one print_list
%type <f> filter filter_body
%type <i> type break_command
+%type <e> set_item set_items
+%type <v> set_atom
CF_GRAMMAR
@@ -128,12 +130,29 @@ block:
}
;
+set_atom:
+ NUM { $$.type = T_INT; $$.val.i = $1; }
+ | IPA { $$.type = T_IP; $$.val.ip = $1; }
+ ;
+
+set_item:
+ set_atom { $$ = f_new_tree(); $$->from = $$->to = $1 }
+ | set_atom '.' '.' set_atom { $$ = f_new_tree(); $$->from = $1; $$->to = $4; }
+ ;
+
+set_items:
+ set_item { $$ = $1; }
+ | set_items ',' set_item { $$ = $3; $$->left = $1; }
+ ;
+
constant:
CONST '(' expr ')' { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_INT; $$->a2.i = $3; }
| NUM { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_INT; $$->a2.i = $1; }
| TRUE { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_BOOL; $$->a2.i = 1; }
| FALSE { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_BOOL; $$->a2.i = 0; }
- | TEXT { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_STRING; $$->a2.p = $1; }
+ | TEXT { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_STRING; $$->a2.p = $1; }
+ | IPA { struct f_val * val; val = cfg_alloc(sizeof(struct f_val)); $$ = f_new_inst(); $$->code = 'C'; $$->a1.p = val; val->type = T_IP; val->val.ip = $1; }
+ | '[' set_items ']' { printf( "We've got a set here..." ); $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_SET; $$->a2.p = build_tree($2); printf( "ook\n" ); }
;
term:
@@ -145,6 +164,7 @@ term:
| term '<' '=' term { $$ = f_new_inst(); $$->code = '<='; $$->a1.p = $1; $$->a2.p = $4; }
| term '>' term { $$ = f_new_inst(); $$->code = '<'; $$->a1.p = $3; $$->a2.p = $1; }
| term '>' '=' term { $$ = f_new_inst(); $$->code = '<='; $$->a1.p = $4; $$->a2.p = $1; }
+ | term '~' term { $$ = f_new_inst(); $$->code = '~'; $$->a1.p = $1; $$->a2.p = $3; }
| SYM {
$$ = f_new_inst();
diff --git a/filter/filter.c b/filter/filter.c
index 4d48cfb3..a83067df 100644
--- a/filter/filter.c
+++ b/filter/filter.c
@@ -16,6 +16,7 @@
#include "lib/lists.h"
#include "lib/resource.h"
#include "lib/socket.h"
+#include "lib/string.h"
#include "nest/route.h"
#include "nest/protocol.h"
#include "nest/iface.h"
@@ -43,11 +44,59 @@ struct f_inst *startup_func = NULL;
if (v1.type != v2.type) \
runtime( "Can not operate with values of incompatible types" );
+#define CMP_ERROR 999
+
+/* Compare two values, returns -1, 0, 1 compared, ERROR 999 */
+int
+val_compare(struct f_val v1, struct f_val v2)
+{
+ switch (v1.type) {
+ case T_INT:
+ if (v1.val.i == v2.val.i) return 0;
+ if (v1.val.i < v2.val.i) return -1;
+ return 1;
+ default: return CMP_ERROR;
+ }
+}
+
+static void
+tree_print(struct f_tree *t)
+{
+ if (!t) {
+ printf( "() " );
+ return;
+ }
+ printf( "[ " );
+ tree_print( t->left );
+ printf( ", " ); val_print( t->from ); printf( ".." ); val_print( t->to ); printf( ", " );
+ tree_print( t->right );
+ printf( "] " );
+}
+
+void
+val_print(struct f_val v)
+{
+ char buf[2048];
+#define PRINTF(a...) bsnprintf( buf, 2040, a )
+ buf[0] = 0;
+ switch (v.type) {
+ case T_VOID: PRINTF( "(void)" ); break;
+ case T_BOOL: PRINTF( v.val.i ? "TRUE" : "FALSE" ); break;
+ case T_INT: PRINTF( "%d ", v.val.i ); break;
+ case T_STRING: PRINTF( "%s", v.val.s ); break;
+ case T_IP: PRINTF( "%I", v.val.ip ); break;
+ case T_SET: tree_print( v.val.t ); PRINTF( "\n" ); break;
+ default: PRINTF( "[unknown type %x]", v.type );
+ }
+ printf( buf );
+}
+
static struct f_val
interpret(struct f_inst *what)
{
struct symbol *sym;
struct f_val v1, v2, res;
+ int i,j,k;
res.type = T_VOID;
if (!what)
@@ -80,38 +129,32 @@ interpret(struct f_inst *what)
break;
/* Relational operators */
- case '!=':
- case '==':
- TWOARGS_C;
- res.type = T_BOOL;
- switch (v1.type) {
- case T_VOID: runtime( "Can not operate with values of type void" );
- case T_INT: res.val.i = (v1.val.i == v2.val.i); break;
- default: runtime( "Usage of unknown type" );
- }
- if (what->code == '!=')
- res.val.i = !(res.val.i);
- break;
- case '<':
- TWOARGS_C;
- res.type = T_BOOL;
- switch (v1.type) {
- case T_VOID: runtime( "Can not operate with values of type void" );
- case T_INT: res.val.i = (v1.val.i < v2.val.i); break;
- default: runtime( "Usage of unknown type" );
- }
+
+#define COMPARE(x) \
+ TWOARGS_C; \
+ res.type = T_BOOL; \
+ i = val_compare(v1, v2); \
+ if (i==CMP_ERROR) \
+ runtime( "Error in comparation" ); \
+ res.val.i = (x); \
break;
- case '<=':
- TWOARGS_C;
+
+ case '!=': COMPARE(i!=0);
+ case '==': COMPARE(i==0);
+ case '<': COMPARE(i==-1);
+ case '<=': COMPARE(i!=1);
+
+ case '~':
+ TWOARGS;
res.type = T_BOOL;
- switch (v1.type) {
- case T_VOID: runtime( "Can not operate with values of type void" );
- case T_INT: res.val.i = (v1.val.i <= v2.val.i); break;
- default: runtime( "Usage of unknown type" );
+ if (((v1.type == T_INT) || (v1.type == T_IP)) && (v2.type == T_SET)) {
+ res.val.i = !! find_tree(v2.val.t, v1);
+ break;
}
+ runtime( "~ applied on unknown type pair" );
break;
-/* Set */
+ /* Set to consant, a1 = type, a2 = value */
case 's':
ARG(v2, a2.p);
sym = what->a1.p;
@@ -129,18 +172,16 @@ interpret(struct f_inst *what)
res.type = what->a1.i;
res.val.i = (int) what->a2.p;
break;
+ case 'C':
+ res = * ((struct f_val *) what->a1.p);
+ break;
case 'i':
res.type = what->a1.i;
res.val.i = * ((int *) what->a2.p);
break;
case 'p':
ONEARG;
- switch (v1.type) {
- case T_VOID: printf( "(void)" ); break;
- case T_INT: printf( "%d ", v1.val.i ); break;
- case T_STRING: printf( "%s", v1.val.i ); break;
- default: runtime( "Print of variable of unknown type" );
- }
+ val_print(v1);
break;
case '?': /* ? has really strange error value, so we can implement if ... else nicely :-) */
ONEARG;
diff --git a/filter/filter.h b/filter/filter.h
index ffb50b3f..cc3fef12 100644
--- a/filter/filter.h
+++ b/filter/filter.h
@@ -40,6 +40,7 @@ struct f_val {
ip_addr ip;
struct prefix px;
char *s;
+ struct f_tree *t;
} val;
};
@@ -50,10 +51,16 @@ struct filter {
void filters_postconfig(void);
struct f_inst *f_new_inst(void);
+struct f_tree *f_new_tree(void);
+
+struct f_tree *build_tree(struct f_tree *);
+struct f_tree *find_tree(struct f_tree *t, struct f_val val);
int f_run(struct filter *filter, struct rte **rte, struct ea_list **tmp_attrs, struct linpool *tmp_pool);
char *filter_name(struct filter *filter);
+int val_compare(struct f_val v1, struct f_val v2);
+void val_print(struct f_val v);
#define F_NOP 0
#define F_ACCEPT 1 /* Need to preserve ordering: accepts < rejects! */
@@ -85,4 +92,10 @@ char *filter_name(struct filter *filter);
#define T_SET 0x80
+struct f_tree {
+ struct f_tree *left, *right;
+ struct f_val from, to;
+ void *data;
+};
+
#endif
diff --git a/filter/tree.c b/filter/tree.c
new file mode 100644
index 00000000..ea1f18f2
--- /dev/null
+++ b/filter/tree.c
@@ -0,0 +1,125 @@
+/*
+ * Filters: utility functions
+ *
+ * Copyright 1998 Pavel Machek <pavel@ucw.cz>
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include <stdio.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <sys/signal.h>
+#include <setjmp.h>
+
+#include "nest/bird.h"
+#include "lib/lists.h"
+#include "lib/resource.h"
+#include "lib/socket.h"
+#include "nest/route.h"
+#include "nest/protocol.h"
+#include "nest/iface.h"
+#include "conf/conf.h"
+#include "filter/filter.h"
+
+/* Finds n-th item in list linked by right. Trashes pointers in right. */
+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);
+}
+
+/* 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);
+}
+
+struct f_tree *
+find_tree(struct f_tree *t, struct f_val val)
+{
+ if (!t)
+ return 0;
+ if ((val_compare(t->from, val) != 1) &&
+ (val_compare(t->to, val) != -1))
+ return t;
+ if (val_compare(t->from, val) == -1)
+ return find_tree(t->right, val);
+ else
+ return find_tree(t->left, val);
+}
+
+/* Gets list linked by left */
+struct f_tree *
+build_tree(struct f_tree *from)
+{
+ struct f_tree *median, *t = from, *next, *left = NULL, *right = NULL;
+
+ median = find_median(from);
+ if (!median)
+ 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;
+}
+
+struct f_tree *
+f_new_tree(void)
+{
+ struct f_tree * ret;
+ ret = cfg_alloc(sizeof(struct f_tree));
+ ret->left = ret->right = NULL;
+ ret->from.type = ret->to.type = T_VOID;
+ ret->from.val.i = ret->to.val.i = 0;
+ ret->data = NULL;
+ return ret;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-25 14:25:55 +0000