summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvneesh Sachdev <avneesh@opensourcerouting.org>2012-08-17 08:19:50 -0700
committerDavid Lamparter <equinox@opensourcerouting.org>2012-09-26 21:50:48 +0200
commit28971c8cb1138700e87dc7da673e59b5596bb51b (patch)
tree0e55c3f830681449cd96bb36eb04a6a1293d8b44
parent67174041d2d9d8908f8b2c915bc0d186d8442c68 (diff)
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>
-rw-r--r--bgpd/bgp_table.h78
-rw-r--r--lib/table.c282
-rw-r--r--lib/table.h126
-rw-r--r--tests/.gitignore1
-rw-r--r--tests/Makefile.am4
-rw-r--r--tests/table_test.c555
6 files changed, 1045 insertions, 1 deletions
diff --git a/bgpd/bgp_table.h b/bgpd/bgp_table.h
index ff42399f..04a1d379 100644
--- a/bgpd/bgp_table.h
+++ b/bgpd/bgp_table.h
@@ -67,6 +67,17 @@ struct bgp_node
#define BGP_NODE_PROCESS_SCHEDULED (1 << 0)
};
+/*
+ * bgp_table_iter_t
+ *
+ * Structure that holds state for iterating over a bgp table.
+ */
+typedef struct bgp_table_iter_t_
+{
+ struct bgp_table *table;
+ route_table_iter_t rt_iter;
+} bgp_table_iter_t;
+
extern struct bgp_table *bgp_table_init (afi_t, safi_t);
extern void bgp_table_lock (struct bgp_table *);
extern void bgp_table_unlock (struct bgp_table *);
@@ -274,4 +285,71 @@ bgp_table_count (const struct bgp_table *const table)
return route_table_count (table->route_table);
}
+/*
+ * bgp_table_get_next
+ */
+static inline struct bgp_node *
+bgp_table_get_next (const struct bgp_table *table, struct prefix *p)
+{
+ return bgp_node_from_rnode (route_table_get_next (table->route_table, p));
+}
+
+/*
+ * bgp_table_iter_init
+ */
+static inline void
+bgp_table_iter_init (bgp_table_iter_t * iter, struct bgp_table *table)
+{
+ bgp_table_lock (table);
+ iter->table = table;
+ route_table_iter_init (&iter->rt_iter, table->route_table);
+}
+
+/*
+ * bgp_table_iter_next
+ */
+static inline struct bgp_node *
+bgp_table_iter_next (bgp_table_iter_t * iter)
+{
+ return bgp_node_from_rnode (route_table_iter_next (&iter->rt_iter));
+}
+
+/*
+ * bgp_table_iter_cleanup
+ */
+static inline void
+bgp_table_iter_cleanup (bgp_table_iter_t * iter)
+{
+ route_table_iter_cleanup (&iter->rt_iter);
+ bgp_table_unlock (iter->table);
+ iter->table = NULL;
+}
+
+/*
+ * bgp_table_iter_pause
+ */
+static inline void
+bgp_table_iter_pause (bgp_table_iter_t * iter)
+{
+ route_table_iter_pause (&iter->rt_iter);
+}
+
+/*
+ * bgp_table_iter_is_done
+ */
+static inline int
+bgp_table_iter_is_done (bgp_table_iter_t * iter)
+{
+ return route_table_iter_is_done (&iter->rt_iter);
+}
+
+/*
+ * bgp_table_iter_started
+ */
+static inline int
+bgp_table_iter_started (bgp_table_iter_t * iter)
+{
+ return route_table_iter_started (&iter->rt_iter);
+}
+
#endif /* _QUAGGA_BGP_TABLE_H */
diff --git a/lib/table.c b/lib/table.c
index 6bbc9c62..19b5d1b1 100644
--- a/lib/table.c
+++ b/lib/table.c
@@ -528,3 +528,285 @@ route_table_init (void)
{
return route_table_init_with_delegate (&default_delegate);
}
+
+/**
+ * route_table_prefix_iter_cmp
+ *
+ * Compare two prefixes according to the order in which they appear in
+ * an iteration over a tree.
+ *
+ * @return -1 if p1 occurs before p2 (p1 < p2)
+ * 0 if the prefixes are identical (p1 == p2)
+ * +1 if p1 occurs after p2 (p1 > p2)
+ */
+int
+route_table_prefix_iter_cmp (struct prefix *p1, struct prefix *p2)
+{
+ struct prefix common_space;
+ struct prefix *common = &common_space;
+
+ if (p1->prefixlen <= p2->prefixlen)
+ {
+ if (prefix_match (p1, p2))
+ {
+
+ /*
+ * p1 contains p2, or is equal to it.
+ */
+ return (p1->prefixlen == p2->prefixlen) ? 0 : -1;
+ }
+ }
+ else
+ {
+
+ /*
+ * Check if p2 contains p1.
+ */
+ if (prefix_match (p2, p1))
+ return 1;
+ }
+
+ route_common (p1, p2, common);
+ assert (common->prefixlen < p1->prefixlen);
+ assert (common->prefixlen < p2->prefixlen);
+
+ /*
+ * Both prefixes are longer than the common prefix.
+ *
+ * We need to check the bit after the common prefixlen to determine
+ * which one comes later.
+ */
+ if (prefix_bit (&p1->u.prefix, common->prefixlen))
+ {
+
+ /*
+ * We branch to the right to get to p1 from the common prefix.
+ */
+ assert (!prefix_bit (&p2->u.prefix, common->prefixlen));
+ return 1;
+ }
+
+ /*
+ * We branch to the right to get to p2 from the common prefix.
+ */
+ assert (prefix_bit (&p2->u.prefix, common->prefixlen));
+ return -1;
+}
+
+/*
+ * route_get_subtree_next
+ *
+ * Helper function that returns the first node that follows the nodes
+ * in the sub-tree under 'node' in iteration order.
+ */
+static struct route_node *
+route_get_subtree_next (struct route_node *node)
+{
+ while (node->parent)
+ {
+ if (node->parent->l_left == node && node->parent->l_right)
+ return node->parent->l_right;
+
+ node = node->parent;
+ }
+
+ return NULL;
+}
+
+/**
+ * route_table_get_next_internal
+ *
+ * Helper function to find the node that occurs after the given prefix in
+ * order of iteration.
+ *
+ * @see route_table_get_next
+ */
+static struct route_node *
+route_table_get_next_internal (const struct route_table *table,
+ struct prefix *p)
+{
+ struct route_node *node, *tmp_node;
+ u_char prefixlen;
+ int cmp;
+
+ prefixlen = p->prefixlen;
+
+ node = table->top;
+
+ while (node)
+ {
+ int match;
+
+ if (node->p.prefixlen < p->prefixlen)
+ match = prefix_match (&node->p, p);
+ else
+ match = prefix_match (p, &node->p);
+
+ if (match)
+ {
+ if (node->p.prefixlen == p->prefixlen)
+ {
+
+ /*
+ * The prefix p exists in the tree, just return the next
+ * node.
+ */
+ route_lock_node (node);
+ node = route_next (node);
+ if (node)
+ route_unlock_node (node);
+
+ return (node);
+ }
+
+ if (node->p.prefixlen > p->prefixlen)
+ {
+
+ /*
+ * Node is in the subtree of p, and hence greater than p.
+ */
+ return node;
+ }
+
+ /*
+ * p is in the sub-tree under node.
+ */
+ tmp_node = node->link[prefix_bit (&p->u.prefix, node->p.prefixlen)];
+
+ if (tmp_node)
+ {
+ node = tmp_node;
+ continue;
+ }
+
+ /*
+ * There are no nodes in the direction where p should be. If
+ * node has a right child, then it must be greater than p.
+ */
+ if (node->l_right)
+ return node->l_right;
+
+ /*
+ * No more children to follow, go upwards looking for the next
+ * node.
+ */
+ return route_get_subtree_next (node);
+ }
+
+ /*
+ * Neither node prefix nor 'p' contains the other.
+ */
+ cmp = route_table_prefix_iter_cmp (&node->p, p);
+ if (cmp > 0)
+ {
+
+ /*
+ * Node follows p in iteration order. Return it.
+ */
+ return node;
+ }
+
+ assert (cmp < 0);
+
+ /*
+ * Node and the subtree under it come before prefix p in
+ * iteration order. Prefix p and its sub-tree are not present in
+ * the tree. Go upwards and find the first node that follows the
+ * subtree. That node will also succeed p.
+ */
+ return route_get_subtree_next (node);
+ }
+
+ return NULL;
+}
+
+/**
+ * route_table_get_next
+ *
+ * Find the node that occurs after the given prefix in order of
+ * iteration.
+ */
+struct route_node *
+route_table_get_next (const struct route_table *table, struct prefix *p)
+{
+ struct route_node *node;
+
+ node = route_table_get_next_internal (table, p);
+ if (node)
+ {
+ assert (route_table_prefix_iter_cmp (&node->p, p) > 0);
+ route_lock_node (node);
+ }
+ return node;
+}
+
+/*
+ * route_table_iter_init
+ */
+void
+route_table_iter_init (route_table_iter_t * iter, struct route_table *table)
+{
+ memset (iter, 0, sizeof (*iter));
+ iter->state = RT_ITER_STATE_INIT;
+ iter->table = table;
+}
+
+/*
+ * route_table_iter_pause
+ *
+ * Pause an iteration over the table. This allows the iteration to be
+ * resumed point after arbitrary additions/deletions from the table.
+ * An iteration can be resumed by just calling route_table_iter_next()
+ * on the iterator.
+ */
+void
+route_table_iter_pause (route_table_iter_t * iter)
+{
+ switch (iter->state)
+ {
+
+ case RT_ITER_STATE_INIT:
+ case RT_ITER_STATE_PAUSED:
+ case RT_ITER_STATE_DONE:
+ return;
+
+ case RT_ITER_STATE_ITERATING:
+
+ /*
+ * Save the prefix that we are currently at. The next call to
+ * route_table_iter_next() will return the node after this prefix
+ * in the tree.
+ */
+ prefix_copy (&iter->pause_prefix, &iter->current->p);
+ route_unlock_node (iter->current);
+ iter->current = NULL;
+ iter->state = RT_ITER_STATE_PAUSED;
+ return;
+
+ default:
+ assert (0);
+ }
+
+}
+
+/*
+ * route_table_iter_cleanup
+ *
+ * Release any resources held by the iterator.
+ */
+void
+route_table_iter_cleanup (route_table_iter_t * iter)
+{
+ if (iter->state == RT_ITER_STATE_ITERATING)
+ {
+ route_unlock_node (iter->current);
+ iter->current = NULL;
+ }
+ assert (!iter->current);
+
+ /*
+ * Set the state to RT_ITER_STATE_DONE to make any
+ * route_table_iter_next() calls on this iterator return NULL.
+ */
+ iter->state = RT_ITER_STATE_DONE;
+}
diff --git a/lib/table.h b/lib/table.h
index 4d3eddb1..ab357a07 100644
--- a/lib/table.h
+++ b/lib/table.h
@@ -98,6 +98,43 @@ struct route_node
#define l_right link[1]
};
+typedef struct route_table_iter_t_ route_table_iter_t;
+
+typedef enum
+{
+ RT_ITER_STATE_INIT,
+ RT_ITER_STATE_ITERATING,
+ RT_ITER_STATE_PAUSED,
+ RT_ITER_STATE_DONE
+} route_table_iter_state_t;
+
+/*
+ * route_table_iter_t
+ *
+ * Structure that holds state for iterating over a route table.
+ */
+struct route_table_iter_t_
+{
+
+ route_table_iter_state_t state;
+
+ /*
+ * Routing table that we are iterating over. The caller must ensure
+ * that that table outlives the iterator.
+ */
+ struct route_table *table;
+
+ /*
+ * The node that the iterator is currently on.
+ */
+ struct route_node *current;
+
+ /*
+ * The last prefix that the iterator processed before it was paused.
+ */
+ struct prefix pause_prefix;
+};
+
/* Prototypes. */
extern struct route_table *route_table_init (void);
@@ -125,4 +162,93 @@ extern struct route_node *route_node_match_ipv6 (const struct route_table *,
#endif /* HAVE_IPV6 */
extern unsigned long route_table_count (const struct route_table *);
+
+extern struct route_node *
+route_table_get_next (const struct route_table *table, struct prefix *p);
+extern int
+route_table_prefix_iter_cmp (struct prefix *p1, struct prefix *p2);
+
+/*
+ * Iterator functions.
+ */
+extern void route_table_iter_init (route_table_iter_t *iter,
+ struct route_table *table);
+extern void route_table_iter_pause (route_table_iter_t *iter);
+extern void route_table_iter_cleanup (route_table_iter_t *iter);
+
+/*
+ * Inline functions.
+ */
+
+/*
+ * route_table_iter_next
+ *
+ * Get the next node in the tree.
+ */
+static inline struct route_node *
+route_table_iter_next (route_table_iter_t * iter)
+{
+ struct route_node *node;
+
+ switch (iter->state)
+ {
+
+ case RT_ITER_STATE_INIT:
+
+ /*
+ * We're just starting the iteration.
+ */
+ node = route_top (iter->table);
+ break;
+
+ case RT_ITER_STATE_ITERATING:
+ node = route_next (iter->current);
+ break;
+
+ case RT_ITER_STATE_PAUSED:
+
+ /*
+ * Start with the node following pause_prefix.
+ */
+ node = route_table_get_next (iter->table, &iter->pause_prefix);
+ break;
+
+ case RT_ITER_STATE_DONE:
+ return NULL;
+
+ default:
+ assert (0);
+ }
+
+ iter->current = node;
+ if (node)
+ iter->state = RT_ITER_STATE_ITERATING;
+ else
+ iter->state = RT_ITER_STATE_DONE;
+
+ return node;
+}
+
+/*
+ * route_table_iter_is_done
+ *
+ * Returns TRUE if the iteration is complete.
+ */
+static inline int
+route_table_iter_is_done (route_table_iter_t *iter)
+{
+ return iter->state == RT_ITER_STATE_DONE;
+}
+
+/*
+ * route_table_iter_started
+ *
+ * Returns TRUE if this iterator has started iterating over the tree.
+ */
+static inline int
+route_table_iter_started (route_table_iter_t *iter)
+{
+ return iter->state != RT_ITER_STATE_INIT;
+}
+
#endif /* _ZEBRA_TABLE_H */
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 ();
+}