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>
diff --git a/bgpd/bgp_table.h b/bgpd/bgp_table.h
index ff42399..04a1d37 100644
--- a/bgpd/bgp_table.h
+++ b/bgpd/bgp_table.h
@@ -67,6 +67,17 @@
#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 @@
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 */