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>

1 files changed, 78 insertions, 0 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 */