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/neighbor.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/neighbor.c')
| -rw-r--r-- | ldpd/neighbor.c | 10 |
1 files changed, 5 insertions, 5 deletions
diff --git a/ldpd/neighbor.c b/ldpd/neighbor.c index 5addc4dda2..d24ceb1229 100644 --- a/ldpd/neighbor.c +++ b/ldpd/neighbor.c @@ -229,7 +229,7 @@ nbr_new(struct in_addr id, int af, int ds_tlv, union ldpd_addr *addr, if ((nbr = calloc(1, sizeof(*nbr))) == NULL) fatal(__func__); - LIST_INIT(&nbr->adj_list); + RB_INIT(&nbr->adj_tree); nbr->state = NBR_STA_PRESENT; nbr->peerid = 0; nbr->af = af; @@ -244,10 +244,10 @@ nbr_new(struct in_addr id, int af, int ds_tlv, union ldpd_addr *addr, nbr->raddr_scope = scope_id; nbr->conf_seqnum = 0; - LIST_FOREACH(adj, &global.adj_list, global_entry) { + RB_FOREACH(adj, global_adj_head, &global.adj_tree) { if (adj->lsr_id.s_addr == nbr->id.s_addr) { adj->nbr = nbr; - LIST_INSERT_HEAD(&nbr->adj_list, adj, nbr_entry); + RB_INSERT(nbr_adj_head, &nbr->adj_tree, adj); } } @@ -366,7 +366,7 @@ nbr_adj_count(struct nbr *nbr, int af) struct adj *adj; int total = 0; - LIST_FOREACH(adj, &nbr->adj_list, nbr_entry) + RB_FOREACH(adj, nbr_adj_head, &nbr->adj_tree) if (adj_get_af(adj) == af) total++; @@ -624,7 +624,7 @@ nbr_establish_connection(struct nbr *nbr) * Send an extra hello to guarantee that the remote peer has formed * an adjacency as well. */ - LIST_FOREACH(adj, &nbr->adj_list, nbr_entry) + RB_FOREACH(adj, nbr_adj_head, &nbr->adj_tree) send_hello(adj->source.type, adj->source.link.ia, adj->source.target); |