]> git.proxmox.com Git - mirror_frr.git/commit - bgpd/bgp_table.h
lib/table: add route_table_get_next() and iterator
authorAvneesh Sachdev <avneesh@opensourcerouting.org>
Fri, 17 Aug 2012 15:19:50 +0000 (08:19 -0700)
committerDavid Lamparter <equinox@opensourcerouting.org>
Wed, 26 Sep 2012 19:50:48 +0000 (21:50 +0200)
commit28971c8cb1138700e87dc7da673e59b5596bb51b
tree0e55c3f830681449cd96bb36eb04a6a1293d8b44
parent67174041d2d9d8908f8b2c915bc0d186d8442c68
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>
bgpd/bgp_table.h
lib/table.c
lib/table.h
tests/.gitignore
tests/Makefile.am
tests/table_test.c [new file with mode: 0644]