Of course I forgot to attach the patches. :)
On Thu, Dec 16, 2021 at 2:41 PM Alexander Zubkov <[email protected]> wrote:
>
> Hi everyone!
>
> I made a couple of patches to do some interesting stuff with communities.
> The first patch allows to pick a component from a standard or a large
> community:
>
> (10, 20, 30) @ 2 --> 20
>
> And the second patch allows to search for minimum or maximum element
> in a community list. This combined allows to do some cool stuff with
> communities like this:
>
> bgp_local_pref = filter(bgp_large_community, [(<as>, <localpref_val>,
> *)]).min @ 3
>
> This will find us the minimum from our "localpref" communities and get
> that number as integer, ready to assign it where we need. Now we use a
> series of if's to check all the possible variants and that is not very
> convenient. I think this features will greatly boost the possibilities
> of working with communities in bird.
commit 1c1c612ae671281e9d7db4376d9664aac9b8492a
Author: Alexander Zubkov <[email protected]>
Date: Thu Dec 16 11:00:27 2021 +0100
Filter: Add operation to pick community components
Add new operation '@', that can be used to pick community components
from pair (community) or from lc (large community) types. For example:
(10, 20) @ 1 --> 10
(10, 20) @ 2 --> 20
(10, 20, 30) @ 1 --> 10
(10, 20, 30) @ 2 --> 20
(10, 20, 30) @ 3 --> 30
Signed-off-by: Alexander Zubkov <[email protected]>
diff --git a/conf/cf-lex.l b/conf/cf-lex.l
index 704a1750..769bb7b6 100644
--- a/conf/cf-lex.l
+++ b/conf/cf-lex.l
@@ -347,7 +347,7 @@ else: {
return DDOT;
}
-[={}:;,.()+*/%<>~\[\]?!\|-] {
+[={}:;,.()+*/%<>~@\[\]?!\|-] {
return yytext[0];
}
diff --git a/conf/confbase.Y b/conf/confbase.Y
index 6985783b..2b9c345a 100644
--- a/conf/confbase.Y
+++ b/conf/confbase.Y
@@ -119,7 +119,7 @@ CF_DECLS
%nonassoc PREFIX_DUMMY
%left AND OR
-%nonassoc '=' '<' '>' '~' GEQ LEQ NEQ NMA PO PC
+%nonassoc '=' '<' '>' '~' '@' GEQ LEQ NEQ NMA PO PC
%left '+' '-'
%left '*' '/' '%'
%left '!'
diff --git a/filter/config.Y b/filter/config.Y
index 7820e719..570f1e32 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -770,6 +770,7 @@ term:
| term GEQ term { $$ = f_new_inst(FI_LTE, $3, $1); }
| term '~' term { $$ = f_new_inst(FI_MATCH, $1, $3); }
| term NMA term { $$ = f_new_inst(FI_NOT_MATCH, $1, $3); }
+ | term '@' term { $$ = f_new_inst(FI_PICK, $1, $3); }
| '!' term { $$ = f_new_inst(FI_NOT, $2); }
| DEFINED '(' term ')' { $$ = f_new_inst(FI_DEFINED, $3); }
diff --git a/filter/f-inst.c b/filter/f-inst.c
index b876a937..ab0d0a2b 100644
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -366,6 +366,32 @@
RESULT(T_PATH_MASK, path_mask, pm);
}
+ INST(FI_PICK, 2, 1) {
+ ARG_ANY(1);
+ ARG(2, T_INT);
+ int index = v2.val.i;
+ switch(v1.type)
+ {
+ case T_PAIR:
+ switch(index) {
+ case 1: RESULT(T_INT, i, v1.val.i >> 16); break;
+ case 2: RESULT(T_INT, i, v1.val.i & 0xFFFF); break;
+ default: runtime( "Invalid index for pair" );
+ }
+ break;
+ case T_LC:
+ switch(index) {
+ case 1: RESULT(T_INT, i, v1.val.lc.asn); break;
+ case 2: RESULT(T_INT, i, v1.val.lc.ldp1); break;
+ case 3: RESULT(T_INT, i, v1.val.lc.ldp2); break;
+ default: runtime( "Invalid index for lc" );
+ }
+ break;
+ default:
+ runtime( "Pair or lc expected" );
+ }
+ }
+
/* Relational operators */
INST(FI_NEQ, 2, 1) {
diff --git a/filter/test.conf b/filter/test.conf
index 3a8804a1..3fa8560c 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -684,6 +684,9 @@ clist l;
clist l2;
clist r;
{
+ bt_assert(((10, 20) @ 1) = 10);
+ bt_assert(((10, 20) @ 2) = 20);
+
l = - empty -;
bt_assert(l !~ [(*,*)]);
bt_assert((l ~ [(*,*)]) != (l !~ [(*,*)]));
@@ -940,6 +943,10 @@ lclist r;
bt_assert(---empty--- = ---empty---);
bt_assert((10, 20, 30) !~ ---empty---);
+ bt_assert(((10, 20, 30) @ 1) = 10);
+ bt_assert(((10, 20, 30) @ 2) = 20);
+ bt_assert(((10, 20, 30) @ 3) = 30);
+
ll = --- empty ---;
ll = add(ll, (ten, 20, 30));
ll = add(ll, (1000, 2000, 3000));
commit ac34dd89126f1dd6fe1a144ee48fbacb17859b45
Author: Alexander Zubkov <[email protected]>
Date: Thu Dec 16 14:17:19 2021 +0100
Filter: Add operators to find minimum and maximum element of sets
Add operators .min and .max to find minumum or maximum element in sets
of types: clist, eclist, lclist. Example usage:
bgp_community.min
bgp_ext_community.max
filter(bgp_large_community, [(as1, as2, *)]).min
Signed-off-by: Alexander Zubkov <[email protected]>
diff --git a/filter/config.Y b/filter/config.Y
index 570f1e32..04700966 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -286,6 +286,7 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN,
DEFINED,
ADD, DELETE, CONTAINS, RESET,
PREPEND, FIRST, LAST, LAST_NONAGGREGATED, MATCH,
+ MIN, MAX,
EMPTY,
FILTER, WHERE, EVAL, ATTRIBUTE,
BT_ASSERT, BT_TEST_SUITE, BT_CHECK_ASSIGN, BT_TEST_SAME, FORMAT)
@@ -797,6 +798,8 @@ term:
| term '.' FIRST { $$ = f_new_inst(FI_AS_PATH_FIRST, $1); }
| term '.' LAST { $$ = f_new_inst(FI_AS_PATH_LAST, $1); }
| term '.' LAST_NONAGGREGATED { $$ = f_new_inst(FI_AS_PATH_LAST_NAG, $1); }
+ | term '.' MIN { $$ = f_new_inst(FI_MIN, $1); }
+ | term '.' MAX { $$ = f_new_inst(FI_MAX, $1); }
/* Communities */
/* This causes one shift/reduce conflict
diff --git a/filter/data.c b/filter/data.c
index 7c33d2cb..56c1fb17 100644
--- a/filter/data.c
+++ b/filter/data.c
@@ -68,6 +68,17 @@ f_type_name(enum f_type t)
return "?";
}
+enum f_type
+f_type_element_type(enum f_type t)
+{
+ switch(t) {
+ case T_CLIST: return T_PAIR;
+ case T_ECLIST: return T_EC;
+ case T_LCLIST: return T_LC;
+ default: return T_VOID;
+ };
+}
+
const struct f_val f_const_empty_path = {
.type = T_PATH,
.val.ad = &null_adata,
diff --git a/filter/data.h b/filter/data.h
index d296776d..bb815c34 100644
--- a/filter/data.h
+++ b/filter/data.h
@@ -188,6 +188,8 @@ void trie_format(const struct f_trie *t, buffer *buf);
const char *f_type_name(enum f_type t);
+enum f_type f_type_element_type(enum f_type t);
+
int val_same(const struct f_val *v1, const struct f_val *v2);
int val_compare(const struct f_val *v1, const struct f_val *v2);
void val_format(const struct f_val *v, buffer *buf);
diff --git a/filter/f-inst.c b/filter/f-inst.c
index ab0d0a2b..af4b2a73 100644
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -977,6 +977,74 @@
RESULT(T_INT, i, as_path_get_last_nonaggregated(v1.val.ad));
}
+ INST(FI_MIN, 1, 1) { /* Get minimum element from set */
+ ARG_ANY(1);
+ RESULT_TYPE(f_type_element_type(v1.type));
+ switch(v1.type)
+ {
+ case T_CLIST:
+ {
+ u32 val = 0;
+ int_set_min(v1.val.ad, &val);
+ RESULT_(T_PAIR, i, val);
+ }
+ break;
+
+ case T_ECLIST:
+ {
+ u64 val = 0;
+ ec_set_min(v1.val.ad, &val);
+ RESULT_(T_EC, ec, val);
+ }
+ break;
+
+ case T_LCLIST:
+ {
+ lcomm val = { 0, 0, 0 };
+ lc_set_min(v1.val.ad, &val);
+ RESULT_(T_LC, lc, val);
+ }
+ break;
+
+ default:
+ runtime( "Clist or lclist expected" );
+ }
+ }
+
+ INST(FI_MAX, 1, 1) { /* Get maximum element from set */
+ ARG_ANY(1);
+ RESULT_TYPE(f_type_element_type(v1.type));
+ switch(v1.type)
+ {
+ case T_CLIST:
+ {
+ u32 val = 0;
+ int_set_max(v1.val.ad, &val);
+ RESULT_(T_PAIR, i, val);
+ }
+ break;
+
+ case T_ECLIST:
+ {
+ u64 val = 0;
+ ec_set_max(v1.val.ad, &val);
+ RESULT_(T_EC, ec, val);
+ }
+ break;
+
+ case T_LCLIST:
+ {
+ lcomm val = { 0, 0, 0 };
+ lc_set_max(v1.val.ad, &val);
+ RESULT_(T_LC, lc, val);
+ }
+ break;
+
+ default:
+ runtime( "Clist or lclist expected" );
+ }
+ }
+
INST(FI_RETURN, 1, 1) {
NEVER_CONSTANT;
/* Acquire the return value */
diff --git a/filter/test.conf b/filter/test.conf
index 3fa8560c..63b64f9f 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -779,6 +779,11 @@ clist r;
r = filter(l, [(3,1), (*,2)]);
bt_assert(r = add(add(-empty-, (3,1)), (3,2)));
bt_assert(format(r) = "(clist (3,1) (3,2))");
+
+ # minimim & maximum element
+ r = add(add(add(-empty-, (1,3)), (2,2)), (3,1));
+ bt_assert(r.min = (1,3));
+ bt_assert(r.max = (3,1));
}
bt_test_suite(t_clist, "Testing lists of communities");
@@ -884,6 +889,11 @@ eclist r;
r = filter(el, [(rt, 10, 1), (rt, 10, 25..30), (ro, 10, 40)]);
bt_assert(r = add(add(--empty--, (rt, 10, 1)), (rt, 10, 30)));
bt_assert(format(r) = "(eclist (rt, 10, 1) (rt, 10, 30))");
+
+ # minimim & maximum element
+ r = add(add(add(--empty--, (rt, 1, 3)), (rt, 2, 2)), (rt, 3, 1));
+ bt_assert(r.min = (rt, 1, 3));
+ bt_assert(r.max = (rt, 3, 1));
}
bt_test_suite(t_eclist, "Testing lists of extended communities");
@@ -993,6 +1003,11 @@ lclist r;
r = filter(ll, [(5..15, *, *), (20, 15..25, *)]);
bt_assert(r = add(add(---empty---, (10, 10, 10)), (20, 20, 20)));
bt_assert(format(r) = "(lclist (10, 10, 10) (20, 20, 20))");
+
+ # minimim & maximum element
+ r = add(add(add(---empty---, (1, 2, 3)), (2, 3, 1)), (3, 1, 2));
+ bt_assert(r.min = (1, 2, 3));
+ bt_assert(r.max = (3, 1, 2));
}
bt_test_suite(t_lclist, "Testing lists of large communities");
diff --git a/nest/a-set.c b/nest/a-set.c
index 1186eb56..71fbac94 100644
--- a/nest/a-set.c
+++ b/nest/a-set.c
@@ -516,6 +516,48 @@ int_set_sort(struct linpool *pool, const struct adata *src)
return dst;
}
+int
+int_set_min(const struct adata *list, u32 *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = (u32 *) list->data;
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ *val = *l++;
+ for (i = 1; i < len; i++, l++)
+ if (int_set_cmp(val, l) > 0)
+ *val = *l;
+
+ return 1;
+}
+
+int
+int_set_max(const struct adata *list, u32 *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = (u32 *) list->data;
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ *val = *l++;
+ for (i = 1; i < len; i++, l++)
+ if (int_set_cmp(val, l) < 0)
+ *val = *l;
+
+ return 1;
+}
+
static int
ec_set_cmp(const void *X, const void *Y)
@@ -541,6 +583,50 @@ ec_set_sort_x(struct adata *set)
qsort(set->data, set->length / 8, 8, ec_set_cmp);
}
+int
+ec_set_min(const struct adata *list, u64 *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = int_set_get_data(list);
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ u32 *res = l; l += 2;
+ for (i = 2; i < len; i += 2, l += 2)
+ if (ec_set_cmp(res, l) > 0)
+ res = l;
+
+ *val = ec_generic(res[0], res[1]);
+ return 1;
+}
+
+int
+ec_set_max(const struct adata *list, u64 *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = int_set_get_data(list);
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ u32 *res = l; l += 2;
+ for (i = 2; i < len; i += 2, l += 2)
+ if (ec_set_cmp(res, l) < 0)
+ res = l;
+
+ *val = ec_generic(res[0], res[1]);
+ return 1;
+}
+
static int
lc_set_cmp(const void *X, const void *Y)
@@ -563,3 +649,47 @@ lc_set_sort(struct linpool *pool, const struct adata *src)
qsort(dst->data, dst->length / LCOMM_LENGTH, LCOMM_LENGTH, lc_set_cmp);
return dst;
}
+
+int
+lc_set_min(const struct adata *list, lcomm *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = int_set_get_data(list);
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ u32 *res = l; l += 3;
+ for (i = 3; i < len; i += 3, l += 3)
+ if (lc_set_cmp(res, l) > 0)
+ res = l;
+
+ *val = (lcomm) { res[0], res[1], res[2] };
+ return 1;
+}
+
+int
+lc_set_max(const struct adata *list, lcomm *val)
+{
+ if (!list)
+ return 0;
+
+ u32 *l = int_set_get_data(list);
+ int len = int_set_get_size(list);
+ int i;
+
+ if (len < 1)
+ return 0;
+
+ u32 *res = l; l += 3;
+ for (i = 3; i < len; i += 3, l += 3)
+ if (lc_set_cmp(res, l) < 0)
+ res = l;
+
+ *val = (lcomm) { res[0], res[1], res[2] };
+ return 1;
+}
diff --git a/nest/attrs.h b/nest/attrs.h
index 50da817b..ef2b95e6 100644
--- a/nest/attrs.h
+++ b/nest/attrs.h
@@ -218,6 +218,12 @@ struct adata *ec_set_del_nontrans(struct linpool *pool, const struct adata *set)
struct adata *int_set_sort(struct linpool *pool, const struct adata *src);
struct adata *ec_set_sort(struct linpool *pool, const struct adata *src);
struct adata *lc_set_sort(struct linpool *pool, const struct adata *src);
+int int_set_min(const struct adata *list, u32 *val);
+int ec_set_min(const struct adata *list, u64 *val);
+int lc_set_min(const struct adata *list, lcomm *val);
+int int_set_max(const struct adata *list, u32 *val);
+int ec_set_max(const struct adata *list, u64 *val);
+int lc_set_max(const struct adata *list, lcomm *val);
void ec_set_sort_x(struct adata *set); /* Sort in place */
