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> --- ldpd/lde.c | 4 ++-- ldpd/ldp_vty_conf.c | 14 +++++++------- ldpd/ldpd.c | 30 +++++++++++++++--------------- ldpd/ldpd.h | 11 +++++++---- ldpd/ldpe.c | 4 ++-- ldpd/neighbor.c | 19 ++++++++++++------- 6 files changed, 45 insertions(+), 37 deletions(-) diff --git a/ldpd/lde.c b/ldpd/lde.c index 4b957c5..80557ed 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) diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c index f5c98eb..95b0971 100644 --- a/ldpd/ldp_vty_conf.c +++ b/ldpd/ldp_vty_conf.c @@ -265,7 +265,7 @@ ldp_config_write(struct vty *vty) if (ldpd_conf->flags & F_LDPD_DS_CISCO_INTEROP) vty_out(vty, " dual-stack cisco-interop%s", VTY_NEWLINE); - LIST_FOREACH(nbrp, &ldpd_conf->nbrp_list, entry) { + RB_FOREACH(nbrp, nbrp_head, &ldpd_conf->nbrp_tree) { if (nbrp->flags & F_NBRP_KEEPALIVE) vty_out(vty, " neighbor %s session holdtime %u%s", inet_ntoa(nbrp->lsr_id), nbrp->keepalive, @@ -740,7 +740,7 @@ ldp_vty_nbr_session_holdtime(struct vty *vty, struct vty_arg *args[]) } else { if (nbrp == NULL) { nbrp = nbr_params_new(lsr_id); - LIST_INSERT_HEAD(&vty_conf->nbrp_list, nbrp, entry); + RB_INSERT(nbrp_head, &vty_conf->nbrp_tree, nbrp); } else if (nbrp->keepalive == secs) goto cancel; @@ -1129,7 +1129,7 @@ ldp_vty_neighbor_password(struct vty *vty, struct vty_arg *args[]) } else { if (nbrp == NULL) { nbrp = nbr_params_new(lsr_id); - LIST_INSERT_HEAD(&vty_conf->nbrp_list, nbrp, entry); + RB_INSERT(nbrp_head, &vty_conf->nbrp_tree, nbrp); } else if (nbrp->auth.method == AUTH_MD5SIG && strcmp(nbrp->auth.md5key, password_str) == 0) goto cancel; @@ -1195,7 +1195,7 @@ ldp_vty_neighbor_ttl_security(struct vty *vty, struct vty_arg *args[]) } else { if (nbrp == NULL) { nbrp = nbr_params_new(lsr_id); - LIST_INSERT_HEAD(&vty_conf->nbrp_list, nbrp, entry); + RB_INSERT(nbrp_head, &vty_conf->nbrp_tree, nbrp); } nbrp->flags |= F_NBRP_GTSM; @@ -1685,14 +1685,14 @@ nbrp_new_api(struct ldpd_conf *conf, struct in_addr lsr_id) return (NULL); nbrp = nbr_params_new(lsr_id); - LIST_INSERT_HEAD(&conf->nbrp_list, nbrp, entry); + RB_INSERT(nbrp_head, &conf->nbrp_tree, nbrp); return (nbrp); } void -nbrp_del_api(struct nbr_params *nbrp) +nbrp_del_api(struct ldpd_conf *conf, struct nbr_params *nbrp) { - LIST_REMOVE(nbrp, entry); + RB_REMOVE(nbrp_head, &conf->nbrp_tree, nbrp); free(nbrp); } diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c index cf793f5..37cc0de 100644 --- a/ldpd/ldpd.c +++ b/ldpd/ldpd.c @@ -862,7 +862,7 @@ main_imsg_send_config(struct ldpd_conf *xconf) return (-1); } - LIST_FOREACH(nbrp, &xconf->nbrp_list, entry) { + RB_FOREACH(nbrp, nbrp_head, &xconf->nbrp_tree) { if (main_imsg_compose_both(IMSG_RECONF_NBRP, nbrp, sizeof(*nbrp)) == -1) return (-1); @@ -961,10 +961,10 @@ ldp_config_reset_main(struct ldpd_conf *conf, void **ref) free(iface); } - while ((nbrp = LIST_FIRST(&conf->nbrp_list)) != NULL) { + while ((nbrp = RB_ROOT(&conf->nbrp_tree)) != NULL) { if (ref && *ref == nbrp) *ref = NULL; - LIST_REMOVE(nbrp, entry); + RB_REMOVE(nbrp_head, &conf->nbrp_tree, nbrp); free(nbrp); } @@ -1034,7 +1034,7 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) COPY(xconf, conf); RB_INIT(&xconf->iface_tree); RB_INIT(&xconf->tnbr_tree); - LIST_INIT(&xconf->nbrp_list); + RB_INIT(&xconf->nbrp_tree); LIST_INIT(&xconf->l2vpn_list); RB_FOREACH(iface, iface_head, &conf->iface_tree) { @@ -1047,9 +1047,9 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) COPY(xt, tnbr); RB_INSERT(tnbr_head, &xconf->tnbr_tree, xt); } - LIST_FOREACH(nbrp, &conf->nbrp_list, entry) { + RB_FOREACH(nbrp, nbrp_head, &conf->nbrp_tree) { COPY(xn, nbrp); - LIST_INSERT_HEAD(&xconf->nbrp_list, xn, entry); + RB_INSERT(nbrp_head, &xconf->nbrp_tree, xn); } LIST_FOREACH(l2vpn, &conf->l2vpn_list, entry) { COPY(xl, l2vpn); @@ -1101,8 +1101,8 @@ ldp_clear_config(struct ldpd_conf *xconf) RB_REMOVE(tnbr_head, &xconf->tnbr_tree, tnbr); free(tnbr); } - while ((nbrp = LIST_FIRST(&xconf->nbrp_list)) != NULL) { - LIST_REMOVE(nbrp, entry); + while ((nbrp = RB_ROOT(&xconf->nbrp_tree)) != NULL) { + RB_REMOVE(nbrp_head, &xconf->nbrp_tree, nbrp); free(nbrp); } while ((l2vpn = LIST_FIRST(&xconf->l2vpn_list)) != NULL) { @@ -1354,7 +1354,7 @@ merge_nbrps(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) struct nbr *nbr; int nbrp_changed; - LIST_FOREACH_SAFE(nbrp, &conf->nbrp_list, entry, ntmp) { + RB_FOREACH_SAFE(nbrp, nbrp_head, &conf->nbrp_tree, ntmp) { /* find deleted nbrps */ if ((xn = nbr_params_find(xconf, nbrp->lsr_id)) == NULL) { switch (ldpd_process) { @@ -1380,15 +1380,15 @@ merge_nbrps(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) QOBJ_UNREG (nbrp); break; } - LIST_REMOVE(nbrp, entry); + RB_REMOVE(nbrp_head, &conf->nbrp_tree, nbrp); free(nbrp); } } - LIST_FOREACH_SAFE(xn, &xconf->nbrp_list, entry, ntmp) { + RB_FOREACH_SAFE(xn, nbrp_head, &xconf->nbrp_tree, ntmp) { /* find new nbrps */ if ((nbrp = nbr_params_find(conf, xn->lsr_id)) == NULL) { - LIST_REMOVE(xn, entry); - LIST_INSERT_HEAD(&conf->nbrp_list, xn, entry); + RB_REMOVE(nbrp_head, &xconf->nbrp_tree, xn); + RB_INSERT(nbrp_head, &conf->nbrp_tree, xn); switch (ldpd_process) { case PROC_LDE_ENGINE: @@ -1455,7 +1455,7 @@ merge_nbrps(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) nbr_establish_connection(nbr); } } - LIST_REMOVE(xn, entry); + RB_REMOVE(nbrp_head, &xconf->nbrp_tree, xn); if (ref && *ref == xn) *ref = nbrp; free(xn); @@ -1772,7 +1772,7 @@ config_new_empty(void) RB_INIT(&xconf->iface_tree); RB_INIT(&xconf->tnbr_tree); - LIST_INIT(&xconf->nbrp_list); + RB_INIT(&xconf->nbrp_tree); LIST_INIT(&xconf->l2vpn_list); return (xconf); diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h index 7e5b424..d8f75a0 100644 --- a/ldpd/ldpd.h +++ b/ldpd/ldpd.h @@ -304,7 +304,7 @@ enum auth_method { /* neighbor specific parameters */ struct nbr_params { - LIST_ENTRY(nbr_params) entry; + RB_ENTRY(nbr_params) entry; struct in_addr lsr_id; uint16_t keepalive; int gtsm_enabled; @@ -317,6 +317,8 @@ struct nbr_params { uint8_t flags; QOBJ_FIELDS }; +RB_HEAD(nbrp_head, nbr_params); +RB_PROTOTYPE(nbrp_head, nbr_params, entry, nbr_params_compare); DECLARE_QOBJ_TYPE(nbr_params) #define F_NBRP_KEEPALIVE 0x01 #define F_NBRP_GTSM 0x02 @@ -410,7 +412,7 @@ struct ldpd_conf { struct ldpd_af_conf ipv6; struct iface_head iface_tree; struct tnbr_head tnbr_tree; - LIST_HEAD(, nbr_params) nbrp_list; + struct nbrp_head nbrp_tree; LIST_HEAD(, l2vpn) l2vpn_list; uint16_t lhello_holdtime; uint16_t lhello_interval; @@ -638,9 +640,10 @@ void iface_del_api(struct ldpd_conf *conf, struct tnbr *tnbr_new_api(struct ldpd_conf *conf, int af, union ldpd_addr *addr); void tnbr_del_api(struct ldpd_conf *conf, struct tnbr *tnbr); -struct nbr_params *nbrp_new_api(struct ldpd_conf *cfg, +struct nbr_params *nbrp_new_api(struct ldpd_conf *conf, struct in_addr lsr_id); -void nbrp_del_api(struct nbr_params *nbrp); +void nbrp_del_api(struct ldpd_conf *conf, + struct nbr_params *nbrp); struct l2vpn *l2vpn_new_api(struct ldpd_conf *cfg, const char *name); void l2vpn_del_api(struct l2vpn *l2vpn); struct l2vpn_if *l2vpn_if_new_api(struct ldpd_conf *conf, diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c index 699ce50..e9e45f8 100644 --- a/ldpd/ldpe.c +++ b/ldpd/ldpe.c @@ -416,7 +416,7 @@ ldpe_dispatch_main(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: @@ -444,7 +444,7 @@ ldpe_dispatch_main(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) diff --git a/ldpd/neighbor.c b/ldpd/neighbor.c index 8376a01..5addc4d 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 -- 1.9.1