diff options
| author | Renato Westphal <renato@opensourcerouting.org> | 2016-12-14 17:39:28 -0200 |
|---|---|---|
| committer | Renato Westphal <renato@opensourcerouting.org> | 2017-01-03 22:07:13 -0200 |
| commit | 057d48bd58776c31db20ec8cf3044cb1d20140d5 (patch) | |
| tree | fff0a4472f2e1b59b52408f43dc0e97e57897976 /ldpd/interface.c | |
| parent | 20bacaeba2381b7b199166e006576606defbaf0f (diff) | |
ldpd: use red-black trees to store 'adj' 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>
Diffstat (limited to 'ldpd/interface.c')
| -rw-r--r-- | ldpd/interface.c | 8 |
1 files changed, 4 insertions, 4 deletions
diff --git a/ldpd/interface.c b/ldpd/interface.c index 06d36fef72..8fea91b878 100644 --- a/ldpd/interface.c +++ b/ldpd/interface.c @@ -66,14 +66,14 @@ if_new(struct kif *kif) iface->ipv4.iface = iface; iface->ipv4.enabled = 0; iface->ipv4.state = IF_STA_DOWN; - LIST_INIT(&iface->ipv4.adj_list); + RB_INIT(&iface->ipv4.adj_tree); /* ipv6 */ iface->ipv6.af = AF_INET6; iface->ipv6.iface = iface; iface->ipv6.enabled = 0; iface->ipv6.state = IF_STA_DOWN; - LIST_INIT(&iface->ipv6.adj_list); + RB_INIT(&iface->ipv6.adj_tree); return (iface); } @@ -293,7 +293,7 @@ if_reset(struct iface *iface, int af) ia = iface_af_get(iface, af); if_stop_hello_timer(ia); - while ((adj = LIST_FIRST(&ia->adj_list)) != NULL) + while ((adj = RB_ROOT(&ia->adj_tree)) != NULL) adj_del(adj, S_SHUTDOWN); /* try to cleanup */ @@ -465,7 +465,7 @@ if_to_ctl(struct iface_af *ia) ictl.uptime = 0; ictl.adj_cnt = 0; - LIST_FOREACH(adj, &ia->adj_list, ia_entry) + RB_FOREACH(adj, ia_adj_head, &ia->adj_tree) ictl.adj_cnt++; return (&ictl); |