diff options
| author | Renato Westphal <renato@opensourcerouting.org> | 2016-12-14 12:14:52 +0100 |
|---|---|---|
| committer | Renato Westphal <renato@opensourcerouting.org> | 2017-01-04 01:07:13 +0100 |
| commit | 76c4abd19f322288394be872c9198c7d17cfac10 (patch) | |
| tree | 7135c07742879dc2d4d74c830be8a62dbe3f8a91 /ldpd/lde.c | |
| parent | ldpd: use red-black trees to store 'tnbr' elements (diff) | |
| download | frr-76c4abd19f322288394be872c9198c7d17cfac10.tar.xz frr-76c4abd19f322288394be872c9198c7d17cfac10.zip | |
ldpd: use red-black trees to store 'nbr_params' 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/lde.c')
| -rw-r--r-- | ldpd/lde.c | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/ldpd/lde.c b/ldpd/lde.c index 4b957c55e..80557ed4e 100644 --- a/ldpd/lde.c +++ b/ldpd/lde.c @@ -475,7 +475,7 @@ lde_dispatch_parent(struct thread *thread) RB_INIT(&nconf->iface_tree); RB_INIT(&nconf->tnbr_tree); - LIST_INIT(&nconf->nbrp_list); + RB_INIT(&nconf->nbrp_tree); LIST_INIT(&nconf->l2vpn_list); break; case IMSG_RECONF_IFACE: @@ -503,7 +503,7 @@ lde_dispatch_parent(struct thread *thread) fatal(NULL); memcpy(nnbrp, imsg.data, sizeof(struct nbr_params)); - LIST_INSERT_HEAD(&nconf->nbrp_list, nnbrp, entry); + RB_INSERT(nbrp_head, &nconf->nbrp_tree, nnbrp); break; case IMSG_RECONF_L2VPN: if ((nl2vpn = malloc(sizeof(struct l2vpn))) == NULL) |