lib/table: add route_table_get_next() and iterator

  * lib/table.[ch]

    - Add a function (route_table_get_next()) to get the route_node in
      a tree that succeeds a given prefix in iteration order.

      This allows one to reliably walk nodes in a tree while allowing
      modifications, and is useful for achieving scale and
      performance. Other approaches are also possible -- the main plus
      point of this one is that it does not require any state about
      the walk to be maintained in the table data structures.

    - Add an iterator for walking the nodes in a tree. This introduces
      a new structure (route_table_iter_t) and the following main
      functions.

        route_table_iter_init()
        route_table_iter_pause()
        route_table_iter_next()
        route_table_iter_cleanup()

      The iterator normally uses node pointers and the existing
      route_next() function to walk nodes efficiently. When an
      iteration is 'paused' with route_table_iter_pause(), it stores
      the last prefix processed. The next call to
      route_table_iter_next() transparently invokes
      route_table_get_next() with the prefix to resume iteration.

  * bgpd/bgp_table.[ch]

    Add wrappers for the new table features described above.

  * tests/table_test.c

    Add tests for the new table code.

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

3 files changed, 559 insertions, 1 deletions

diff --git a/tests/.gitignore b/tests/.gitignore
index ca085943..e6ab706c 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -8,6 +8,7 @@ TAGS
 *.lo
 *.la
 *.libs
+tabletest
 testsig
 .arch-inventory
 .arch-ids
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 0c262a4a..e510a158 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -6,7 +6,7 @@ AM_LDFLAGS = $(PILDFLAGS)
 
 noinst_PROGRAMS = testsig testbuffer testmemory heavy heavywq heavythread \
 		aspathtest testprivs teststream testbgpcap ecommtest \
-		testbgpmpattr testchecksum testbgpmpath
+		testbgpmpattr testchecksum testbgpmpath tabletest
 
 testsig_SOURCES = test-sig.c
 testbuffer_SOURCES = test-buffer.c
@@ -22,6 +22,7 @@ ecommtest_SOURCES = ecommunity_test.c
 testbgpmpattr_SOURCES =  bgp_mp_attr_test.c
 testchecksum_SOURCES = test-checksum.c
 testbgpmpath_SOURCES = bgp_mpath_test.c
+tabletest_SOURCES = table_test.c
 
 testsig_LDADD = ../lib/libzebra.la @LIBCAP@
 testbuffer_LDADD = ../lib/libzebra.la @LIBCAP@
@@ -37,3 +38,4 @@ ecommtest_LDADD = ../lib/libzebra.la @LIBCAP@ -lm ../bgpd/libbgp.a
 testbgpmpattr_LDADD = ../lib/libzebra.la @LIBCAP@ -lm ../bgpd/libbgp.a
 testchecksum_LDADD = ../lib/libzebra.la @LIBCAP@ 
 testbgpmpath_LDADD = ../lib/libzebra.la @LIBCAP@ -lm ../bgpd/libbgp.a
+tabletest_LDADD = ../lib/libzebra.la @LIBCAP@ -lm
diff --git a/tests/table_test.c b/tests/table_test.c
new file mode 100644
index 00000000..fc9cc3dd
--- /dev/null
+++ b/tests/table_test.c
@@ -0,0 +1,555 @@
+/* $QuaggaId: Format:%an, %ai, %h$ $
+ *
+ * Routing table test
+ * Copyright (C) 2012 OSR.
+ *
+ * This file is part of Quagga
+ *
+ * Quagga is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * Quagga is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Quagga; see the file COPYING.  If not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
+ */
+
+#include <zebra.h>
+
+#include "prefix.h"
+#include "table.h"
+
+/*
+ * test_node_t
+ *
+ * Information that is kept for each node in the radix tree.
+ */
+typedef struct test_node_t_
+{
+
+  /*
+   * Human readable representation of the string. Allocated using
+   * malloc()/dup().
+   */
+  char *prefix_str;
+} test_node_t;
+
+struct thread_master *master;
+
+/*
+ * add_node
+ *
+ * Add the given prefix (passed in as a string) to the given table.
+ */
+static void
+add_node (struct route_table *table, const char *prefix_str)
+{
+  struct prefix_ipv4 p;
+  test_node_t *node;
+  struct route_node *rn;
+
+  assert (prefix_str);
+
+  if (str2prefix_ipv4 (prefix_str, &p) <= 0)
+    {
+      assert (0);
+    }
+
+  rn = route_node_get (table, (struct prefix *) &p);
+  if (rn->info)
+    {
+      assert (0);
+      return;
+    }
+
+  node = malloc (sizeof (test_node_t));
+  assert (node);
+  node->prefix_str = strdup (prefix_str);
+  assert (node->prefix_str);
+  rn->info = node;
+}
+
+/*
+ * add_nodes
+ *
+ * Convenience function to add a bunch of nodes together.
+ *
+ * The arguments must be prefixes in string format, with a NULL as the
+ * last argument.
+ */
+static void
+add_nodes (struct route_table *table, ...)
+{
+  va_list arglist;
+  char *prefix;
+
+  va_start (arglist, table);
+
+  prefix = va_arg (arglist, char *);
+  while (prefix)
+    {
+      add_node (table, prefix);
+      prefix = va_arg (arglist, char *);
+    }
+
+  va_end (arglist);
+}
+
+/*
+ * print_subtree
+ *
+ * Recursive function to print a route node and its children.
+ *
+ * @see print_table
+ */
+static void
+print_subtree (struct route_node *rn, const char *legend, int indent_level)
+{
+  char buf[INET_ADDRSTRLEN + 4];
+  int i;
+
+  /*
+   * Print this node first.
+   */
+  for (i = 0; i < indent_level; i++)
+    {
+      printf ("  ");
+    }
+
+  prefix2str (&rn->p, buf, sizeof (buf));
+  printf ("%s: %s", legend, buf);
+  if (!rn->info)
+    {
+      printf (" (internal)");
+    }
+  printf ("\n");
+  if (rn->l_left)
+    {
+      print_subtree (rn->l_left, "Left", indent_level + 1);
+    }
+  if (rn->l_right)
+    {
+      print_subtree (rn->l_right, "Right", indent_level + 1);
+    }
+}
+
+/*
+ * print_table
+ *
+ * Function that prints out the internal structure of a route table.
+ */
+static void
+print_table (struct route_table *table)
+{
+  struct route_node *rn;
+
+  rn = table->top;
+
+  if (!rn)
+    {
+      printf ("<Empty Table>\n");
+      return;
+    }
+
+  print_subtree (rn, "Top", 0);
+}
+
+/*
+ * clear_table
+ *
+ * Remove all nodes from the given table.
+ */
+static void
+clear_table (struct route_table *table)
+{
+  route_table_iter_t iter;
+  struct route_node *rn;
+  test_node_t *node;
+
+  route_table_iter_init (&iter, table);
+
+  while ((rn = route_table_iter_next (&iter)))
+    {
+      node = rn->info;
+      if (!node)
+	{
+	  continue;
+	}
+      rn->info = NULL;
+      route_unlock_node (rn);
+      free (node->prefix_str);
+      free (node);
+    }
+
+  route_table_iter_cleanup (&iter);
+
+  assert (table->top == NULL);
+}
+
+/*
+ * verify_next_by_iterating
+ *
+ * Iterate over the tree to make sure that the first prefix after
+ * target_pfx is the expected one. Note that target_pfx may not be
+ * present in the tree.
+ */
+static void
+verify_next_by_iterating (struct route_table *table,
+			  struct prefix *target_pfx, struct prefix *next_pfx)
+{
+  route_table_iter_t iter;
+  struct route_node *rn;
+
+  route_table_iter_init (&iter, table);
+  while ((rn = route_table_iter_next (&iter)))
+    {
+      if (route_table_prefix_iter_cmp (&rn->p, target_pfx) > 0)
+	{
+	  assert (!prefix_cmp (&rn->p, next_pfx));
+	  break;
+	}
+    }
+
+  if (!rn)
+    {
+      assert (!next_pfx);
+    }
+
+  route_table_iter_cleanup (&iter);
+}
+
+/*
+ * verify_next
+ *
+ * Verifies that route_table_get_next() returns the expected result
+ * (result) for the prefix string 'target'.
+ */
+static void
+verify_next (struct route_table *table, const char *target, const char *next)
+{
+  struct prefix_ipv4 target_pfx, next_pfx;
+  struct route_node *rn;
+  char result_buf[INET_ADDRSTRLEN + 4];
+
+  if (str2prefix_ipv4 (target, &target_pfx) <= 0)
+    {
+      assert (0);
+    }
+
+  rn = route_table_get_next (table, (struct prefix *) &target_pfx);
+  if (rn)
+    {
+      prefix2str (&rn->p, result_buf, sizeof (result_buf));
+    }
+  else
+    {
+      snprintf (result_buf, sizeof (result_buf), "(Null)");
+    }
+
+  printf ("\n");
+  print_table (table);
+  printf ("Verifying successor of %s. Expected: %s, Result: %s\n", target,
+	  next ? next : "(Null)", result_buf);
+
+  if (!rn)
+    {
+      assert (!next);
+      verify_next_by_iterating (table, (struct prefix *) &target_pfx, NULL);
+      return;
+    }
+
+  assert (next);
+
+  if (str2prefix_ipv4 (next, &next_pfx) <= 0)
+    {
+      assert (0);
+    }
+
+  if (prefix_cmp (&rn->p, (struct prefix *) &next_pfx))
+    {
+      assert (0);
+    }
+  route_unlock_node (rn);
+
+  verify_next_by_iterating (table, (struct prefix *) &target_pfx,
+			    (struct prefix *) &next_pfx);
+}
+
+/*
+ * test_get_next
+ */
+static void
+test_get_next (void)
+{
+  struct route_table *table;
+
+  printf ("\n\nTesting route_table_get_next()\n");
+  table = route_table_init ();
+
+  /*
+   * Target exists in tree, but has no successor.
+   */
+  add_nodes (table, "1.0.1.0/24", NULL);
+  verify_next (table, "1.0.1.0/24", NULL);
+  clear_table (table);
+
+  /*
+   * Target exists in tree, and there is a node in its left subtree.
+   */
+  add_nodes (table, "1.0.1.0/24", "1.0.1.0/25", NULL);
+  verify_next (table, "1.0.1.0/24", "1.0.1.0/25");
+  clear_table (table);
+
+  /*
+   * Target exists in tree, and there is a node in its right subtree.
+   */
+  add_nodes (table, "1.0.1.0/24", "1.0.1.128/25", NULL);
+  verify_next (table, "1.0.1.0/24", "1.0.1.128/25");
+  clear_table (table);
+
+  /*
+   * Target exists in the tree, next node is outside subtree.
+   */
+  add_nodes (table, "1.0.1.0/24", "1.1.0.0/16", NULL);
+  verify_next (table, "1.0.1.0/24", "1.1.0.0/16");
+  clear_table (table);
+
+  /*
+   * The target node does not exist in the tree for all the test cases
+   * below this point.
+   */
+
+  /*
+   * There is no successor in the tree.
+   */
+  add_nodes (table, "1.0.0.0/16", NULL);
+  verify_next (table, "1.0.1.0/24", NULL);
+  clear_table (table);
+
+  /*
+   * There exists a node that would be in the target's left subtree.
+   */
+  add_nodes (table, "1.0.0.0/16", "1.0.1.0/25", NULL);
+  verify_next (table, "1.0.1.0/24", "1.0.1.0/25");
+  clear_table (table);
+
+  /*
+   * There exists a node would be in the target's right subtree.
+   */
+  add_nodes (table, "1.0.0.0/16", "1.0.1.128/25", NULL);
+  verify_next (table, "1.0.1.0/24", "1.0.1.128/25");
+  clear_table (table);
+
+  /*
+   * A search for the target reaches a node where there are no child
+   * nodes in the direction of the target (left), but the node has a
+   * right child.
+   */
+  add_nodes (table, "1.0.0.0/16", "1.0.128.0/17", NULL);
+  verify_next (table, "1.0.0.0/17", "1.0.128.0/17");
+  clear_table (table);
+
+  /*
+   * A search for the target reaches a node with no children. We have
+   * to go upwards in the tree to find a successor.
+   */
+  add_nodes (table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/24",
+	     "1.0.128.0/17", NULL);
+  verify_next (table, "1.0.1.0/25", "1.0.128.0/17");
+  clear_table (table);
+
+  /*
+   * A search for the target reaches a node where neither the node nor
+   * the target prefix contain each other.
+   *
+   * In first case below the node succeeds the target.
+   *
+   * In the second case, the node comes before the target, so we have
+   * to go up the tree looking for a successor.
+   */
+  add_nodes (table, "1.0.0.0/16", "1.0.1.0/24", NULL);
+  verify_next (table, "1.0.0.0/24", "1.0.1.0/24");
+  clear_table (table);
+
+  add_nodes (table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/25",
+	     "1.0.128.0/17", NULL);
+  verify_next (table, "1.0.1.128/25", "1.0.128.0/17");
+  clear_table (table);
+
+  route_table_finish (table);
+}
+
+/*
+ * verify_prefix_iter_cmp
+ */
+static void
+verify_prefix_iter_cmp (const char *p1, const char *p2, int exp_result)
+{
+  struct prefix_ipv4 p1_pfx, p2_pfx;
+  int result;
+
+  if (str2prefix_ipv4 (p1, &p1_pfx) <= 0)
+    {
+      assert (0);
+    }
+
+  if (str2prefix_ipv4 (p2, &p2_pfx) <= 0)
+    {
+      assert (0);
+    }
+
+  result = route_table_prefix_iter_cmp ((struct prefix *) &p1_pfx,
+					(struct prefix *) &p2_pfx);
+
+  printf ("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
+
+  assert (exp_result == result);
+
+  /*
+   * Also check the reverse comparision.
+   */
+  result = route_table_prefix_iter_cmp ((struct prefix *) &p2_pfx,
+					(struct prefix *) &p1_pfx);
+
+  if (exp_result)
+    {
+      exp_result = -exp_result;
+    }
+
+  printf ("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
+  assert (result == exp_result);
+}
+
+/*
+ * test_prefix_iter_cmp
+ *
+ * Tests comparision of prefixes according to order of iteration.
+ */
+static void
+test_prefix_iter_cmp ()
+{
+  printf ("\n\nTesting route_table_prefix_iter_cmp()\n");
+
+  verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/8", 0);
+
+  verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/16", -1);
+
+  verify_prefix_iter_cmp ("1.0.0.0/16", "1.128.0.0/16", -1);
+}
+
+/*
+ * verify_iter_with_pause
+ *
+ * Iterates over a tree using two methods: 'normal' iteration, and an
+ * iterator that pauses at each node. Verifies that the two methods
+ * yield the same results.
+ */
+static void
+verify_iter_with_pause (struct route_table *table)
+{
+  unsigned long num_nodes;
+  struct route_node *rn, *iter_rn;
+  route_table_iter_t iter_space;
+  route_table_iter_t *iter = &iter_space;
+
+  route_table_iter_init (iter, table);
+  num_nodes = 0;
+
+  for (rn = route_top (table); rn; rn = route_next (rn))
+    {
+      num_nodes++;
+      route_table_iter_pause (iter);
+
+      assert (iter->current == NULL);
+      if (route_table_iter_started (iter))
+	{
+	  assert (iter->state == RT_ITER_STATE_PAUSED);
+	}
+      else
+	{
+	  assert (rn == table->top);
+	  assert (iter->state == RT_ITER_STATE_INIT);
+	}
+
+      iter_rn = route_table_iter_next (iter);
+
+      /*
+       * Make sure both iterations return the same node.
+       */
+      assert (rn == iter_rn);
+    }
+
+  assert (num_nodes == route_table_count (table));
+
+  route_table_iter_pause (iter);
+  iter_rn = route_table_iter_next (iter);
+
+  assert (iter_rn == NULL);
+  assert (iter->state == RT_ITER_STATE_DONE);
+
+  assert (route_table_iter_next (iter) == NULL);
+  assert (iter->state == RT_ITER_STATE_DONE);
+
+  route_table_iter_cleanup (iter);
+
+  print_table (table);
+  printf ("Verified pausing iteration on tree with %lu nodes\n", num_nodes);
+}
+
+/*
+ * test_iter_pause
+ */
+static void
+test_iter_pause (void)
+{
+  struct route_table *table;
+  int i, num_prefixes;
+  const char *prefixes[] = {
+    "1.0.1.0/24",
+    "1.0.1.0/25",
+    "1.0.1.128/25",
+    "1.0.2.0/24",
+    "2.0.0.0/8"
+  };
+
+  num_prefixes = sizeof (prefixes) / sizeof (prefixes[0]);
+
+  printf ("\n\nTesting that route_table_iter_pause() works as expected\n");
+  table = route_table_init ();
+  for (i = 0; i < num_prefixes; i++)
+    {
+      add_nodes (table, prefixes[i], NULL);
+    }
+
+  verify_iter_with_pause (table);
+
+  clear_table (table);
+  route_table_finish (table);
+}
+
+/*
+ * run_tests
+ */
+static void
+run_tests (void)
+{
+  test_prefix_iter_cmp ();
+  test_get_next ();
+  test_iter_pause ();
+}
+
+/*
+ * main
+ */
+int
+main (void)
+{
+  run_tests ();
+}