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/tests/Makefile.am b/tests/Makefile.am
index 0c262a4..e510a15 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -6,7 +6,7 @@
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 @@
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 @@
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