From 28971c8cb1138700e87dc7da673e59b5596bb51b Mon Sep 17 00:00:00 2001 From: Avneesh Sachdev Date: Fri, 17 Aug 2012 08:19:50 -0700 Subject: 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 --- bgpd/bgp_table.h | 78 ++++++++ lib/table.c | 282 +++++++++++++++++++++++++++ lib/table.h | 126 ++++++++++++ tests/.gitignore | 1 + tests/Makefile.am | 4 +- tests/table_test.c | 555 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 1045 insertions(+), 1 deletion(-) create mode 100644 tests/table_test.c 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 + +#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 ("\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 (); +} -- cgit v1.2.1