Extends set operations in filters.

Allows add/filter/delete clist on clist (set algebra on clists).

Allows number ~ bgppath match.

2 files changed, 63 insertions, 21 deletions

diff --git a/filter/filter.c b/filter/filter.c
index d6d338bf..a087c50b 100644
--- a/filter/filter.c
+++ b/filter/filter.c
@@ -228,6 +228,9 @@ val_simple_in_range(struct f_val v1, struct f_val v2)
 {
   if ((v1.type == T_PATH) && (v2.type == T_PATH_MASK))
     return as_path_match(v1.val.ad, v2.val.path_mask);
+  if ((v1.type == T_INT) && (v2.type == T_PATH))
+    return as_path_is_member(v2.val.ad, v1.val.i);
+
   if (((v1.type == T_PAIR) || (v1.type == T_QUAD)) && (v2.type == T_CLIST))
     return int_set_contains(v2.val.ad, v1.val.i);
 #ifndef IPV6
@@ -320,28 +323,34 @@ eclist_match_set(struct adata *list, struct f_tree *set)
 }
 
 static struct adata *
-clist_filter(struct linpool *pool, struct adata *clist, struct f_tree *set, int pos)
+clist_filter(struct linpool *pool, struct adata *list, struct f_val set, int pos)
 {
-  if (!clist)
+  if (!list)
     return NULL;
 
+  int tree = (set.type == T_SET);	/* 1 -> set is T_SET, 0 -> set is T_CLIST */
   struct f_val v;
-  clist_set_type(set, &v);
+  if (tree)
+    clist_set_type(set.val.t, &v);
+  else
+    v.type = T_PAIR;
 
-  u32 tmp[clist->length/4];
-  u32 *l = (u32 *) clist->data;
+  int len = int_set_get_size(list);
+  u32 *l = int_set_get_data(list);
+  u32 tmp[len];
   u32 *k = tmp;
-  u32 *end = l + clist->length/4;
+  u32 *end = l + len;
 
   while (l < end) {
     v.val.i = *l++;
-    if (pos == !!find_tree(set, v))	/* pos && find_tree || !pos && !find_tree */
+    /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
+    if ((tree ? !!find_tree(set.val.t, v) : int_set_contains(set.val.ad, v.val.i)) == pos)
       *k++ = v.val.i;
   }
 
   int nl = (k - tmp) * 4;
-  if (nl == clist->length)
-    return clist;
+  if (nl == list->length)
+    return list;
 
   struct adata *res = adata_empty(pool, nl);
   memcpy(res->data, tmp, nl);
@@ -349,11 +358,12 @@ clist_filter(struct linpool *pool, struct adata *clist, struct f_tree *set, int
 }
 
 static struct adata *
-eclist_filter(struct linpool *pool, struct adata *list, struct f_tree *set, int pos)
+eclist_filter(struct linpool *pool, struct adata *list, struct f_val set, int pos)
 {
   if (!list)
     return NULL;
 
+  int tree = (set.type == T_SET);	/* 1 -> set is T_SET, 0 -> set is T_CLIST */
   struct f_val v;
 
   int len = int_set_get_size(list);
@@ -365,7 +375,8 @@ eclist_filter(struct linpool *pool, struct adata *list, struct f_tree *set, int
   v.type = T_EC;
   for (i = 0; i < len; i += 2) {
     v.val.ec = ec_get(l, i);
-    if (pos == !!find_tree(set, v)) {	/* pos && find_tree || !pos && !find_tree */
+    /* pos && member(val, set) || !pos && !member(val, set),  member() depends on tree */
+    if ((tree ? !!find_tree(set.val.t, v) : ec_set_contains(set.val.ad, v.val.ec)) == pos) {
       *k++ = l[i];
       *k++ = l[i+1];
     }
@@ -1116,6 +1127,8 @@ interpret(struct f_inst *what)
 #endif
       else if ((v2.type == T_SET) && clist_set_type(v2.val.t, &dummy))
 	arg_set = 1;
+      else if (v2.type == T_CLIST)
+	arg_set = 2;
       else
 	runtime("Can't add/delete non-pair");
 
@@ -1123,22 +1136,25 @@ interpret(struct f_inst *what)
       switch (what->aux)
       {
       case 'a':
-	if (arg_set)
+	if (arg_set == 1)
 	  runtime("Can't add set");
-	res.val.ad = int_set_add(f_pool, v1.val.ad, i);
+	else if (!arg_set)
+	  res.val.ad = int_set_add(f_pool, v1.val.ad, i);
+	else 
+	  res.val.ad = int_set_union(f_pool, v1.val.ad, v2.val.ad);
 	break;
       
       case 'd':
 	if (!arg_set)
 	  res.val.ad = int_set_del(f_pool, v1.val.ad, i);
 	else
-	  res.val.ad = clist_filter(f_pool, v1.val.ad, v2.val.t, 0);
+	  res.val.ad = clist_filter(f_pool, v1.val.ad, v2, 0);
 	break;
 
       case 'f':
 	if (!arg_set)
 	  runtime("Can't filter pair");
-	res.val.ad = clist_filter(f_pool, v1.val.ad, v2.val.t, 1);
+	res.val.ad = clist_filter(f_pool, v1.val.ad, v2, 1);
 	break;
 
       default:
@@ -1153,6 +1169,8 @@ interpret(struct f_inst *what)
       /* v2.val is either EC or EC-set */
       if ((v2.type == T_SET) && eclist_set_type(v2.val.t))
 	arg_set = 1;
+      else if (v2.type == T_ECLIST)
+	arg_set = 2;
       else if (v2.type != T_EC)
 	runtime("Can't add/delete non-pair");
 
@@ -1160,22 +1178,25 @@ interpret(struct f_inst *what)
       switch (what->aux)
       {
       case 'a':
-	if (arg_set)
+	if (arg_set == 1)
 	  runtime("Can't add set");
-	res.val.ad = ec_set_add(f_pool, v1.val.ad, v2.val.ec);
+	else if (!arg_set)
+	  res.val.ad = ec_set_add(f_pool, v1.val.ad, v2.val.ec);
+	else 
+	  res.val.ad = ec_set_union(f_pool, v1.val.ad, v2.val.ad);
 	break;
       
       case 'd':
 	if (!arg_set)
 	  res.val.ad = ec_set_del(f_pool, v1.val.ad, v2.val.ec);
 	else
-	  res.val.ad = eclist_filter(f_pool, v1.val.ad, v2.val.t, 0);
+	  res.val.ad = eclist_filter(f_pool, v1.val.ad, v2, 0);
 	break;
 
       case 'f':
 	if (!arg_set)
 	  runtime("Can't filter ec");
-	res.val.ad = eclist_filter(f_pool, v1.val.ad, v2.val.t, 1);
+	res.val.ad = eclist_filter(f_pool, v1.val.ad, v2, 1);
 	break;
 
       default:
diff --git a/filter/test.conf b/filter/test.conf
index 4f09637c..dbb05de8 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -57,7 +57,9 @@ bgpmask pm1;
 bgpmask pm2;
 bgppath p2;
 clist l;
+clist l2;
 eclist el;
+eclist el2;
 {
 	pm1 =  / 4 3 2 1 /;
 	pm2 = [= 4 3 2 1 =];
@@ -67,10 +69,10 @@ eclist el;
 	p2 = prepend( p2, 3 );
 	p2 = prepend( p2, 4 );
 	print "Testing paths: ", p2;
-	print "Should be true: ", p2 ~ pm1, " ", p2 ~ pm2;
+	print "Should be true: ", p2 ~ pm1, " ", p2 ~ pm2, " ", 3 ~ p2;
 	print "4 = ", p2.len;
 	p2 = prepend( p2, 5 );
-	print "Should be false: ", p2 ~ pm1, " ", p2 ~ pm2;
+	print "Should be false: ", p2 ~ pm1, " ", p2 ~ pm2, " ", 10 ~ p2;
 	print "Should be true: ", p2 ~  / ? 4 3 2 1 /,  " ", p2, " ",  / ? 4 3 2 1 /;
 	print "Should be true: ", p2 ~ [= * 4 3 * 1 =], " ", p2, " ", [= * 4 3 * 1 =];
 	print "Should be true: ", p2 ~ [= (3+2) (2*2) 3 2 1 =], " ", p2 ~ mkpath(5, 4);
@@ -108,6 +110,7 @@ eclist el;
 	l = add( l, (3,3) );
 	l = add( l, (3,4) );
 	l = add( l, (3,5) );
+	l2 = filter( l, [(3,*)] );
 	l = delete( l, [(3,2..4)] );
 	print "Community list (1,2) (3,1) (3,5) ", l;
 	l = add( l, (3,2) );
@@ -120,6 +123,14 @@ eclist el;
 	print "Community list (3,1) ", l;
 	l = delete( l, [(*,(onef(5)))] );
 	print "Community list empty ", l;
+	l2 = add( l2, (3,6) );
+	l = filter( l2, [(3,1..4)] );
+	l2 = filter( l2, [(3,3..6)] );
+	print "clist A (1..4): ", l;
+	print "clist B (3..6): ", l2;
+	print "clist A union B: ", add( l2, l );
+	print "clist A isect B: ", filter( l, l2 );
+	print "clist A \  B: ", delete( l, l2 );
 
 	el = -- empty --;
 	el = add(el, (rt, 10, 20));
@@ -143,6 +154,16 @@ eclist el;
 	print "EC list (rt, 10, 1) (rt, 10, 30): ", el;
 	print "Testing EC list, true: ", (rt, 10, 1) ~ el, " ", el ~ [(rt, 10, ten..40)];
 	print "Testing EC list, false: ", (rt, 10, 20) ~ el, " ", (ro, 10.20.30.40, 100) ~ el, " ", el ~ [(rt, 10, 35..40)], " ", el ~ [(ro, 10, *)];
+	el = add(el, (rt, 10, 40));
+	el2 = filter(el, [(rt, 10, 20..40)] );
+	el2 = add(el2, (rt, 10, 50));
+	print "eclist A (1,30,40): ", el;
+	print "eclist B (30,40,50): ", el2;
+	print "eclist A union B: ", add( el2, el );
+	print "eclist A isect B: ", filter( el, el2 );
+	print "eclist A \  B: ", delete( el, el2 );
+
+
 }
 
 function bla()