diff options
| author | Renato Westphal <renato@opensourcerouting.org> | 2016-12-14 12:14:52 +0100 |
|---|---|---|
| committer | Renato Westphal <renato@opensourcerouting.org> | 2017-02-15 10:19:52 +0100 |
| commit | c485351c5222f0e1106709d77329597d30165a03 (patch) | |
| tree | 4faa190e4e84c83140a217b6d08258af1d847c4d /ldpd/neighbor.c | |
| parent | ldpd: use red-black trees to store 'tnbr' elements (diff) | |
| download | frr-c485351c5222f0e1106709d77329597d30165a03.tar.xz frr-c485351c5222f0e1106709d77329597d30165a03.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 '')
| -rw-r--r-- | ldpd/neighbor.c | 19 |
1 files changed, 12 insertions, 7 deletions
diff --git a/ldpd/neighbor.c b/ldpd/neighbor.c index 8376a0154..5addc4dda 100644 --- a/ldpd/neighbor.c +++ b/ldpd/neighbor.c @@ -39,10 +39,13 @@ static void nbr_start_itimeout(struct nbr *); static int nbr_idtimer(struct thread *); static int nbr_act_session_operational(struct nbr *); static void nbr_send_labelmappings(struct nbr *); +static __inline int nbr_params_compare(struct nbr_params *, + struct nbr_params *); RB_GENERATE(nbr_id_head, nbr, id_tree, nbr_id_compare) RB_GENERATE(nbr_addr_head, nbr, addr_tree, nbr_addr_compare) RB_GENERATE(nbr_pid_head, nbr, pid_tree, nbr_pid_compare) +RB_GENERATE(nbrp_head, nbr_params, entry, nbr_params_compare) struct { int state; @@ -752,6 +755,12 @@ nbr_send_labelmappings(struct nbr *nbr) NULL, 0); } +static __inline int +nbr_params_compare(struct nbr_params *a, struct nbr_params *b) +{ + return (ntohl(a->lsr_id.s_addr) - ntohl(b->lsr_id.s_addr)); +} + struct nbr_params * nbr_params_new(struct in_addr lsr_id) { @@ -769,13 +778,9 @@ nbr_params_new(struct in_addr lsr_id) struct nbr_params * nbr_params_find(struct ldpd_conf *xconf, struct in_addr lsr_id) { - struct nbr_params *nbrp; - - LIST_FOREACH(nbrp, &xconf->nbrp_list, entry) - if (nbrp->lsr_id.s_addr == lsr_id.s_addr) - return (nbrp); - - return (NULL); + struct nbr_params nbrp; + nbrp.lsr_id = lsr_id; + return (RB_FIND(nbrp_head, &xconf->nbrp_tree, &nbrp)); } uint16_t |