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 <green@qrator.net>

diff --git a/filter/config.Y b/filter/config.Y
index 2fb55e4e7a1e8df10cc5f6ccd2650865e7113c3a..8916ea9770964183724af1843b89f4adec228679 100644 (file)
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -287,6 +287,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)
@@ -800,6 +801,8 @@ term:
  | term '.' DATA { $$ = f_new_inst(FI_PAIR_DATA, $1); }
  | term '.' DATA1 { $$ = f_new_inst(FI_LC_DATA1, $1); }
  | term '.' DATA2 { $$ = f_new_inst(FI_LC_DATA2, $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 7c33d2cb681a72d406f6f3551aecc788e395b98f..56c1fb177b8e2788f21624837965a12c3011ad2d 100644 (file)
--- 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 d296776d934d3cca124eb92e0ced1db83cbd9b16..bb815c341547de09edbfa1722df165fd7e0a1833 100644 (file)
--- 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 7e9e77d239cb1214b120618b9b2835f76dad61b0..901d29391377f7bfe1fc1f83192ac93fe8173653 100644 (file)
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -983,6 +983,74 @@
     RESULT(T_INT, i, v1.val.lc.ldp2);
   }
 
+  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 6f2f6fb56ed748e6a75998e21a319cf132f36ef0..6a28e4b3dc0feb00d7501d6c0192141e0ad8f508 100644 (file)
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -781,6 +781,12 @@ 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(add(add(-empty-, (2,1)), (1,3)), (2,2)), (3,1)), (2,3));
+       bt_assert(format(r) = "(clist (2,1) (1,3) (2,2) (3,1) (2,3))");
+       bt_assert(r.min = (1,3));
+       bt_assert(r.max = (3,1));
 }
 
 bt_test_suite(t_clist, "Testing lists of communities");
@@ -886,6 +892,12 @@ 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(add(add(--empty--, (rt, 2, 1)), (rt, 1, 3)), (rt, 2, 2)), (rt, 3, 1)), (rt, 2, 3));
+       bt_assert(format(r) = "(eclist (rt, 2, 1) (rt, 1, 3) (rt, 2, 2) (rt, 3, 1) (rt, 2, 3))");
+       bt_assert(r.min = (rt, 1, 3));
+       bt_assert(r.max = (rt, 3, 1));
 }
 
 bt_test_suite(t_eclist, "Testing lists of extended communities");
@@ -995,6 +1007,12 @@ 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(add(add(---empty---, (2, 3, 3)), (1, 2, 3)), (2, 3, 1)), (3, 1, 2)), (2, 1, 3));
+       bt_assert(format(r) = "(lclist (2, 3, 3) (1, 2, 3) (2, 3, 1) (3, 1, 2) (2, 1, 3))");
+       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 1186eb56f8172518e0c3412b27ababdd9f18d975..71fbac946b3013d68be44156806321ad6f39c4d9 100644 (file)
--- 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 50da817be20aca3cffe1571c8bff73569d661879..ef2b95e68e99caff31d313a72599dce2bf9fbad6 100644 (file)
--- 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 */