Extends pair set syntax, matching and deleting against clist.

Expressions like (123,*) can be used in pair set literals, clists can be
matched against pair sets (community ~ pairset) and pair sets can be
used to specify items to delete from clists (community.delete(pairset)).

4 files changed, 103 insertions, 10 deletions

diff --git a/doc/bird.sgml b/doc/bird.sgml
index 61ebc7a..a6fa4df 100644
--- a/doc/bird.sgml
+++ b/doc/bird.sgml
@@ -706,7 +706,8 @@ incompatible with each other (that is to prevent you from shooting in the foot).
 	  Filters recognize four types of sets. Sets are similar to strings: you can pass them around
 	  but you can't modify them. Literals of type <cf>int set</cf> look like <cf>
 	  [ 1, 2, 5..7 ]</cf>. As you can see, both simple values and ranges are permitted in
-	  sets.
+	  sets. For pair sets, expressions like <cf/(123,*)/ can be used to denote ranges (in
+	  that case <cf/(123,0)..(123,65535)/).
 
 	  Sets of prefixes are special: their literals does not allow ranges, but allows
 	  prefix patterns that are written as <cf><M>ipaddress</M>/<M>pxlen</M>{<M>low</M>,<M>high</M>}</cf>.
@@ -777,9 +778,16 @@ incompatible with each other (that is to prevent you from shooting in the foot).
 	  no literals of this type. There are two special operators on
 	  clists:
 
-          <cf>add(<m/C/,<m/P/)</cf> adds pair (or quad) <m/P/ to clist <m/C/ and returns the result.
+          <cf>add(<m/C/,<m/P/)</cf> adds pair (or quad) <m/P/ to clist
+	  <m/C/ and returns the result.  If item <m/P/ is already in
+	  clist <m/C/, it does nothing.
 
-          <cf>delete(<m/C/,<m/P/)</cf> deletes pair (or quad) <m/P/ from clist <m/C/ and returns the result.
+          <cf>delete(<m/C/,<m/P/)</cf> deletes pair (or quad)
+	  <m/P/ from clist <m/C/ and returns the result.  If clist
+	  <m/C/ does not contain item <m/P/, it does nothing.
+	  <m/P/ may also be a pair (or quad) set, in that case the
+	  operator deletes all items from clist <m/C/ that are also
+	  members of set <m/P/.
 
           Statement <cf><m/C/ = add(<m/C/, <m/P/);</cf> can be shortened to
           <cf><m/C/.add(<m/P/);</cf> if <m/C/ is appropriate route attribute
@@ -794,7 +802,7 @@ incompatible with each other (that is to prevent you from shooting in the foot).
 Special operators include <cf/&tilde;/ for "is element of a set" operation - it can be
 used on element and set of elements of the same type (returning true if element is contained in the given set), or
 on two strings (returning true if first string matches a shell-like pattern stored in second string) or on IP and prefix (returning true if IP is within the range defined by that prefix), or on
-prefix and prefix (returning true if first prefix is more specific than second one) or on bgppath and bgpmask (returning true if the path matches the mask) or on pair and clist (returning true if the pair (or quad) is element of the clist).
+prefix and prefix (returning true if first prefix is more specific than second one) or on bgppath and bgpmask (returning true if the path matches the mask) or on pair/quad and clist (returning true if the pair/quad is element of the clist) or on clist and pair/quad set (returning true if there is an element of the clist that is also a member of the pair/quad set).
 
 
 <sect>Control structures
diff --git a/filter/config.Y b/filter/config.Y
index 7723658..0140c0c 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -243,7 +243,13 @@ set_atom:
  ; 
 
 set_item:
-   set_atom { 
+   '(' NUM ',' '*' ')' { 
+	$$ = f_new_tree(); 
+	$$->from.type = $$->to.type = T_PAIR;
+	$$->from.val.i = make_pair($2, 0); 
+	$$->to.val.i = make_pair($2, 0xffff);
+   }
+ | set_atom { 
 	$$ = f_new_tree(); 
 	$$->from = $1; 
 	$$->to = $1;
diff --git a/filter/filter.c b/filter/filter.c
index 3230610..5492f80 100644
--- a/filter/filter.c
+++ b/filter/filter.c
@@ -230,6 +230,76 @@ val_simple_in_range(struct f_val v1, struct f_val v2)
   return CMP_ERROR;
 }
 
+static int
+clist_set_type(struct f_tree *set, struct f_val *v)
+{
+ switch (set->from.type) {
+  case T_PAIR:
+    v->type = T_PAIR;
+    return 1;
+  case T_QUAD:
+#ifndef IPV6
+  case T_IP:
+#endif
+    v->type = T_QUAD;
+    return 1;
+    break;
+  default:
+    v->type = T_VOID;
+    return 0;
+  }
+}
+
+static int
+clist_match_set(struct adata *clist, struct f_tree *set)
+{
+  if (!clist)
+    return 0;
+
+  struct f_val v;
+  if (!clist_set_type(set, &v))
+    return CMP_ERROR;
+
+  u32 *l = (u32 *) clist->data;
+  u32 *end = l + clist->length/4;
+  while (l < end) {
+    v.val.i = *l++;
+    if (find_tree(set, v))
+      return 1;
+  }
+  return 0;
+}
+
+static struct adata *
+clist_del_matching(struct linpool *pool, struct adata *clist, struct f_tree *set)
+{
+  if (!clist)
+    return NULL;
+
+  struct f_val v;
+  clist_set_type(set, &v);
+
+  u32 tmp[clist->length/4];
+  u32 *l = (u32 *) clist->data;
+  u32 *k = tmp;
+  u32 *end = l + clist->length/4;
+
+  while (l < end) {
+    v.val.i = *l++;
+    if (!find_tree(set, v))
+      *k++ = v.val.i;
+  }
+
+  int nl = (k - tmp) * 4;
+  if (nl == clist->length)
+    return clist;
+
+  struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl);
+  res->length = nl;
+  memcpy(res->data, tmp, nl);
+  return res;
+}
+
 /**
  * val_in_range - implement |~| operator
  * @v1: element
@@ -251,6 +321,9 @@ val_in_range(struct f_val v1, struct f_val v2)
   if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX_SET))
     return trie_match_prefix(v2.val.ti, &v1.val.px);
 
+  if ((v1.type == T_CLIST) && (v2.type == T_SET))
+    return clist_match_set(v1.val.ad, v2.val.t);
+
   if (v2.type == T_SET)
     switch (v1.type) {
     case T_ENUM:
@@ -845,6 +918,7 @@ interpret(struct f_inst *what)
     if (v1.type != T_CLIST)
       runtime("Can't add/delete to non-clist");
 
+    struct f_val dummy;
     if ((v2.type == T_PAIR) || (v2.type == T_QUAD))
       i = v2.val.i;
 #ifndef IPV6
@@ -852,6 +926,8 @@ interpret(struct f_inst *what)
     else if (v2.type == T_IP)
       i = ipa_to_u32(v2.val.px.ip);
 #endif
+    else if ((v2.type == T_SET) && (what->aux == 'd') && clist_set_type(v2.val.t, &dummy))
+      what->aux = 'D';
     else
       runtime("Can't add/delete non-pair");
 
@@ -859,6 +935,7 @@ interpret(struct f_inst *what)
     switch (what->aux) {
     case 'a': res.val.ad = int_set_add(f_pool, v1.val.ad, i); break;
     case 'd': res.val.ad = int_set_del(f_pool, v1.val.ad, i); break;
+    case 'D': res.val.ad = clist_del_matching(f_pool, v1.val.ad, v2.val.t); break;
     default: bug("unknown Ca operation");
     }
     break;
diff --git a/filter/test.conf b/filter/test.conf
index aca049c..4814396 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -79,10 +79,11 @@ clist l;
 	l = add( l, (1,2) );
 	l = add( l, (2,3) );
 	print "Community list (1,2) (2,3) ", l;
-	print "Should be true: ", (2,3) ~ l;
-	l = delete( l, (2,3) );
+	print "Should be true: ", (2,3) ~ l, " ", l ~ [(1,*)], " ", l ~ [(2,3)];
+	l = add( l, (2,5) );
+	l = delete( l, [(2,*)] );
 	print "Community list (1,2) ", l;
-	print "Should be false: ", (2,3) ~ l;
+	print "Should be false: ", (2,3) ~ l, " ", l ~ [(2,*)];
 }
 
 function bla()
@@ -196,8 +197,9 @@ string s;
 		", true: ", RTS_STATIC ~ [RTS_STATIC, RTS_DEVICE],
 		", false: ", RTS_BGP ~ [RTS_STATIC, RTS_DEVICE];
 
-	ps = [(1,2), (3,4)..(3,8)];
-	print "Testing pair set (TTF):", pp ~ ps,  " ", (3,5) ~ ps, " ", (3,9) ~ ps;
+	ps = [(1,2), (3,4)..(4,8), (5,*)];
+	print "Testing pair set, true:  ", pp ~ ps,  " ", (3,5) ~ ps, " ", (4,1) ~ ps, " ", (5,4) ~ ps, " ", (5,65535) ~ ps;
+	print "Testing pair set, false: ", (3,3) ~ ps, " ", (4,9) ~ ps, " ", (4,65535) ~ ps, " ", (6,0) ~ ps ;
 
 	qq = 1.2.3.4;
 	print "Testinq quad: 1.2.3.4 = ", qq,