Merge branch 'master' into mq-filter-stack

[thirdparty/bird.git] / filter / trie.c

diff --git a/filter/trie.c b/filter/trie.c
index fba395d13fd28a43f4bfb6e06735057160de1a74..3038f5ecf2aca9f4f53ea01cefd4c10feebd7a8b 100644 (file)
--- a/filter/trie.c
+++ b/filter/trie.c
@@ -73,6 +73,20 @@
 #include "lib/string.h"
 #include "conf/conf.h"
 #include "filter/filter.h"
+#include "filter/data.h"
+
+
+/*
+ * In the trie code, the prefix length is internally treated as for the whole
+ * ip_addr, regardless whether it contains an IPv4 or IPv6 address. Therefore,
+ * remaining definitions make sense.
+ */
+
+#define ipa_mkmask(x) ip6_mkmask(x)
+#define ipa_masklen(x) ip6_masklen(&x)
+#define ipa_pxlen(x,y) ip6_pxlen(x,y)
+#define ipa_getbit(x,n) ip6_getbit(x,n)
+
 
 /**
  * f_new_trie - allocates and returns a new empty trie
@@ -109,12 +123,11 @@ attach_node(struct f_trie_node *parent, struct f_trie_node *child)
 /**
  * trie_add_prefix
  * @t: trie to add to
- * @px: prefix address
- * @plen: prefix length
+ * @net: IP network prefix
  * @l: prefix lower bound
  * @h: prefix upper bound
  *
- * Adds prefix (prefix pattern) @px/@plen to trie @t.  @l and @h are lower
+ * Adds prefix (prefix pattern) @n to trie @t.  @l and @h are lower
  * and upper bounds on accepted prefix lengths, both inclusive.
  * 0 <= l, h <= 32 (128 for IPv6).
  *
@@ -124,8 +137,19 @@ attach_node(struct f_trie_node *parent, struct f_trie_node *child)
  */
 
 void *
-trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
+trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
 {
+  ip_addr px = net_prefix(net);
+  uint plen = net_pxlen(net);
+
+  if (net->type == NET_IP4)
+  {
+    const uint delta = IP6_MAX_PREFIX_LENGTH - IP4_MAX_PREFIX_LENGTH;
+    plen += delta;
+    l += delta;
+    h += delta;
+  }
+
   if (l == 0)
     t->zero = 1;
   else
@@ -140,7 +164,7 @@ trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
   struct f_trie_node *o = NULL;
   struct f_trie_node *n = t->root;
 
-  while(n)
+  while (n)
     {
       ip_addr cmask = ipa_and(n->mask, pmask);
 
@@ -196,18 +220,8 @@ trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
   return a;
 }
 
-/**
- * trie_match_prefix
- * @t: trie
- * @px: prefix address
- * @plen: prefix length
- *
- * Tries to find a matching prefix pattern in the trie such that
- * prefix @px/@plen matches that prefix pattern. Returns 1 if there
- * is such prefix pattern in the trie.
- */
-int
-trie_match_prefix(struct f_trie *t, ip_addr px, int plen)
+static int
+trie_match_prefix(const struct f_trie *t, ip_addr px, uint plen)
 {
   ip_addr pmask = ipa_mkmask(plen);
   ip_addr paddr = ipa_and(px, pmask);
@@ -216,7 +230,7 @@ trie_match_prefix(struct f_trie *t, ip_addr px, int plen)
     return t->zero;
 
   int plentest = plen - 1;
-  struct f_trie_node *n = t->root;
+  const struct f_trie_node *n = t->root;
 
   while(n)
     {
@@ -241,8 +255,32 @@ trie_match_prefix(struct f_trie *t, ip_addr px, int plen)
   return 0;
 }
 
+/**
+ * trie_match_net
+ * @t: trie
+ * @n: net address
+ *
+ * Tries to find a matching net in the trie such that
+ * prefix @n matches that prefix pattern. Returns 1 if there
+ * is such prefix pattern in the trie.
+ */
+int
+trie_match_net(const struct f_trie *t, const net_addr *n)
+{
+  uint add = 0;
+
+  switch (n->type) {
+    case NET_IP4:
+    case NET_VPN4:
+    case NET_ROA4:
+      add = IP6_MAX_PREFIX_LENGTH - IP4_MAX_PREFIX_LENGTH;
+  }
+
+  return trie_match_prefix(t, net_prefix(n), net_pxlen(n) + add);
+}
+
 static int
-trie_node_same(struct f_trie_node *t1, struct f_trie_node *t2)
+trie_node_same(const struct f_trie_node *t1, const struct f_trie_node *t2)
 {
   if ((t1 == NULL) && (t2 == NULL))
     return 1;
@@ -266,13 +304,13 @@ trie_node_same(struct f_trie_node *t1, struct f_trie_node *t2)
  * Compares two tries and returns 1 if they are same
  */
 int
-trie_same(struct f_trie *t1, struct f_trie *t2)
+trie_same(const struct f_trie *t1, const struct f_trie *t2)
 {
   return (t1->zero == t2->zero) && trie_node_same(t1->root, t2->root);
 }
 
 static void
-trie_node_format(struct f_trie_node *t, buffer *buf)
+trie_node_format(const struct f_trie_node *t, buffer *buf)
 {
   if (t == NULL)
     return;
@@ -292,7 +330,7 @@ trie_node_format(struct f_trie_node *t, buffer *buf)
  * Prints the trie to the supplied buffer.
  */
 void
-trie_format(struct f_trie *t, buffer *buf)
+trie_format(const struct f_trie *t, buffer *buf)
 {
   buffer_puts(buf, "[");
 
@@ -300,6 +338,9 @@ trie_format(struct f_trie *t, buffer *buf)
     buffer_print(buf, "%I/%d, ", IPA_NONE, 0);
   trie_node_format(t->root, buf);
 
+  if (buf->pos == buf->end)
+    return;
+
   /* Undo last separator */
   if (buf->pos[-1] != '[')
     buf->pos -= 2;