Sets of integers now actually work. Sets of IP will work as soon as

compare function is ready.

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;
+}