]> git.puffer.fish Git - matthieu/frr.git/commit
ldpd: use red-black trees to store 'lde_map' elements
authorRenato Westphal <renato@opensourcerouting.org>
Sat, 3 Dec 2016 23:14:44 +0000 (21:14 -0200)
committerRenato Westphal <renato@opensourcerouting.org>
Wed, 4 Jan 2017 00:07:13 +0000 (22:07 -0200)
commitd3e1887ad6b5ae2199710b3278c277838e6ef913
tree36470ff324cefc0af07208863ec81f5e805f48c6
parent607c1cbfd290e4e19c983c43dae22bd9a0ab827f
ldpd: use red-black trees to store 'lde_map' elements

Using red-black trees instead of linked lists brings the following
benefits:
1 - Elements are naturally ordered (no need to reorder anything before
    outputting data to the user);
2 - Faster lookups/deletes: O(log n) time complexity against O(n).

The insert operation with red-black trees is more expensive though,
but that's not a big issue since lookups are much more frequent.

Signed-off-by: Renato Westphal <renato@opensourcerouting.org>
ldpd/l2vpn.c
ldpd/lde.c
ldpd/lde.h
ldpd/lde_lib.c