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/ldpe.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/ldpe.c')
| -rw-r--r-- | ldpd/ldpe.c | 18 |
1 files changed, 9 insertions, 9 deletions
diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c index c3640d4131..c960acf3b1 100644 --- a/ldpd/ldpe.c +++ b/ldpd/ldpe.c @@ -111,7 +111,7 @@ ldpe(const char *user, const char *group) ldpd_process = PROC_LDP_ENGINE; LIST_INIT(&global.addr_list); - LIST_INIT(&global.adj_list); + RB_INIT(&global.adj_tree); TAILQ_INIT(&global.pending_conns); if (inet_pton(AF_INET, AllRouters_v4, &global.mcast_addr_v4) != 1) fatal("inet_pton"); @@ -209,7 +209,7 @@ ldpe_shutdown(void) LIST_REMOVE(if_addr, entry); free(if_addr); } - while ((adj = LIST_FIRST(&global.adj_list)) != NULL) + while ((adj = RB_ROOT(&global.adj_tree)) != NULL) adj_del(adj, S_SHUTDOWN); /* clean up */ @@ -425,8 +425,8 @@ ldpe_dispatch_main(struct thread *thread) memcpy(niface, imsg.data, sizeof(struct iface)); LIST_INIT(&niface->addr_list); - LIST_INIT(&niface->ipv4.adj_list); - LIST_INIT(&niface->ipv6.adj_list); + RB_INIT(&niface->ipv4.adj_tree); + RB_INIT(&niface->ipv6.adj_tree); niface->ipv4.iface = niface; niface->ipv6.iface = niface; @@ -814,18 +814,18 @@ ldpe_adj_ctl(struct ctl_conn *c) continue; strlcpy(ictl.name, iface->name, sizeof(ictl.name)); - if (LIST_EMPTY(&iface->ipv4.adj_list) && - LIST_EMPTY(&iface->ipv6.adj_list)) + if (RB_EMPTY(&iface->ipv4.adj_tree) && + RB_EMPTY(&iface->ipv6.adj_tree)) ictl.no_adj = 1; imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISC_IFACE, 0, 0, -1, &ictl, sizeof(ictl)); - LIST_FOREACH(adj, &iface->ipv4.adj_list, ia_entry) { + RB_FOREACH(adj, ia_adj_head, &iface->ipv4.adj_tree) { actl = adj_to_ctl(adj); imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISC_ADJ, 0, 0, -1, actl, sizeof(struct ctl_adj)); } - LIST_FOREACH(adj, &iface->ipv6.adj_list, ia_entry) { + RB_FOREACH(adj, ia_adj_head, &iface->ipv6.adj_tree) { actl = adj_to_ctl(adj); imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISC_ADJ, 0, 0, -1, actl, sizeof(struct ctl_adj)); @@ -869,7 +869,7 @@ ldpe_nbr_ctl(struct ctl_conn *c) imsg_compose_event(&c->iev, IMSG_CTL_SHOW_NBR, 0, 0, -1, nctl, sizeof(struct ctl_nbr)); - LIST_FOREACH(adj, &nbr->adj_list, nbr_entry) { + RB_FOREACH(adj, nbr_adj_head, &nbr->adj_tree) { actl = adj_to_ctl(adj); imsg_compose_event(&c->iev, IMSG_CTL_SHOW_NBR_DISC, 0, 0, -1, actl, sizeof(struct ctl_adj)); |