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/adjacency.c | 40 +++++++++++++++++++++++++--------------- ldpd/hello.c | 4 ++-- ldpd/l2vpn.c | 4 ++-- ldpd/lde.c | 4 ++-- ldpd/ldp_vty_conf.c | 12 ++++++------ ldpd/ldpd.c | 34 +++++++++++++++++----------------- ldpd/ldpd.h | 10 ++++++---- ldpd/ldpe.c | 10 +++++----- ldpd/ldpe.h | 2 +- 9 files changed, 66 insertions(+), 54 deletions(-) diff --git a/ldpd/adjacency.c b/ldpd/adjacency.c index d1a6fac..3f478df 100644 --- a/ldpd/adjacency.c +++ b/ldpd/adjacency.c @@ -26,11 +26,14 @@ #include "log.h" static int adj_itimer(struct thread *); -static void tnbr_del(struct tnbr *); +static __inline int tnbr_compare(struct tnbr *, struct tnbr *); +static void tnbr_del(struct ldpd_conf *, struct tnbr *); static int tnbr_hello_timer(struct thread *); static void tnbr_start_hello_timer(struct tnbr *); static void tnbr_stop_hello_timer(struct tnbr *); +RB_GENERATE(tnbr_head, tnbr, entry, tnbr_compare) + struct adj * adj_new(struct in_addr lsr_id, struct hello_source *source, union ldpd_addr *addr) @@ -165,7 +168,7 @@ adj_itimer(struct thread *thread) if (!(adj->source.target->flags & F_TNBR_CONFIGURED) && adj->source.target->pw_count == 0) { /* remove dynamic targeted neighbor */ - tnbr_del(adj->source.target); + tnbr_del(leconf, adj->source.target); return (0); } adj->source.target->adj = NULL; @@ -192,6 +195,17 @@ adj_stop_itimer(struct adj *adj) /* targeted neighbors */ +static __inline int +tnbr_compare(struct tnbr *a, struct tnbr *b) +{ + if (a->af < b->af) + return (-1); + if (a->af > b->af) + return (1); + + return (ldp_addrcmp(a->af, &a->addr, &b->addr)); +} + struct tnbr * tnbr_new(int af, union ldpd_addr *addr) { @@ -208,34 +222,30 @@ tnbr_new(int af, union ldpd_addr *addr) } static void -tnbr_del(struct tnbr *tnbr) +tnbr_del(struct ldpd_conf *xconf, struct tnbr *tnbr) { tnbr_stop_hello_timer(tnbr); if (tnbr->adj) adj_del(tnbr->adj, S_SHUTDOWN); - LIST_REMOVE(tnbr, entry); + RB_REMOVE(tnbr_head, &xconf->tnbr_tree, tnbr); free(tnbr); } struct tnbr * tnbr_find(struct ldpd_conf *xconf, int af, union ldpd_addr *addr) { - struct tnbr *tnbr; - - LIST_FOREACH(tnbr, &xconf->tnbr_list, entry) - if (af == tnbr->af && - ldp_addrcmp(af, addr, &tnbr->addr) == 0) - return (tnbr); - - return (NULL); + struct tnbr tnbr; + tnbr.af = af; + tnbr.addr = *addr; + return (RB_FIND(tnbr_head, &xconf->tnbr_tree, &tnbr)); } struct tnbr * -tnbr_check(struct tnbr *tnbr) +tnbr_check(struct ldpd_conf *xconf, struct tnbr *tnbr) { if (!(tnbr->flags & (F_TNBR_CONFIGURED|F_TNBR_DYNAMIC)) && tnbr->pw_count == 0) { - tnbr_del(tnbr); + tnbr_del(xconf, tnbr); return (NULL); } @@ -280,7 +290,7 @@ tnbr_update_all(int af) struct tnbr *tnbr; /* update targeted neighbors */ - LIST_FOREACH(tnbr, &leconf->tnbr_list, entry) + RB_FOREACH(tnbr, tnbr_head, &leconf->tnbr_tree) if (tnbr->af == af || af == AF_UNSPEC) tnbr_update(tnbr); } diff --git a/ldpd/hello.c b/ldpd/hello.c index 755b25a..0833ebb 100644 --- a/ldpd/hello.c +++ b/ldpd/hello.c @@ -261,7 +261,7 @@ recv_hello(struct in_addr lsr_id, struct ldp_msg *msg, int af, if (tnbr && (tnbr->flags & F_TNBR_DYNAMIC) && !((flags & F_HELLO_REQ_TARG))) { tnbr->flags &= ~F_TNBR_DYNAMIC; - tnbr = tnbr_check(tnbr); + tnbr = tnbr_check(leconf, tnbr); } if (!tnbr) { @@ -273,7 +273,7 @@ recv_hello(struct in_addr lsr_id, struct ldp_msg *msg, int af, tnbr = tnbr_new(af, src); tnbr->flags |= F_TNBR_DYNAMIC; tnbr_update(tnbr); - LIST_INSERT_HEAD(&leconf->tnbr_list, tnbr, entry); + RB_INSERT(tnbr_head, &leconf->tnbr_tree, tnbr); } source.type = HELLO_TARGETED; diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c index c0f6586..dc9879e 100644 --- a/ldpd/l2vpn.c +++ b/ldpd/l2vpn.c @@ -530,7 +530,7 @@ ldpe_l2vpn_pw_init(struct l2vpn_pw *pw) if (tnbr == NULL) { tnbr = tnbr_new(pw->af, &pw->addr); tnbr_update(tnbr); - LIST_INSERT_HEAD(&leconf->tnbr_list, tnbr, entry); + RB_INSERT(tnbr_head, &leconf->tnbr_tree, tnbr); } tnbr->pw_count++; @@ -544,6 +544,6 @@ ldpe_l2vpn_pw_exit(struct l2vpn_pw *pw) tnbr = tnbr_find(leconf, pw->af, &pw->addr); if (tnbr) { tnbr->pw_count--; - tnbr_check(tnbr); + tnbr_check(leconf, tnbr); } } diff --git a/ldpd/lde.c b/ldpd/lde.c index 1e36218..4b957c5 100644 --- a/ldpd/lde.c +++ b/ldpd/lde.c @@ -474,7 +474,7 @@ lde_dispatch_parent(struct thread *thread) memcpy(nconf, imsg.data, sizeof(struct ldpd_conf)); RB_INIT(&nconf->iface_tree); - LIST_INIT(&nconf->tnbr_list); + RB_INIT(&nconf->tnbr_tree); LIST_INIT(&nconf->nbrp_list); LIST_INIT(&nconf->l2vpn_list); break; @@ -496,7 +496,7 @@ lde_dispatch_parent(struct thread *thread) fatal(NULL); memcpy(ntnbr, imsg.data, sizeof(struct tnbr)); - LIST_INSERT_HEAD(&nconf->tnbr_list, ntnbr, entry); + RB_INSERT(tnbr_head, &nconf->tnbr_tree, ntnbr); break; case IMSG_RECONF_NBRP: if ((nnbrp = malloc(sizeof(struct nbr_params))) == NULL) diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c index 689554d..f5c98eb 100644 --- a/ldpd/ldp_vty_conf.c +++ b/ldpd/ldp_vty_conf.c @@ -213,7 +213,7 @@ ldp_af_config_write(struct vty *vty, int af, struct ldpd_conf *conf, vty_out(vty, " session holdtime %u%s", af_conf->keepalive, VTY_NEWLINE); - LIST_FOREACH(tnbr, &ldpd_conf->tnbr_list, entry) { + RB_FOREACH(tnbr, tnbr_head, &ldpd_conf->tnbr_tree) { if (tnbr->af == af) { vty_out(vty, " !%s", VTY_NEWLINE); vty_out(vty, " neighbor %s targeted%s", @@ -955,7 +955,7 @@ ldp_vty_neighbor_targeted(struct vty *vty, struct vty_arg *args[]) if (tnbr == NULL) goto cancel; - LIST_REMOVE(tnbr, entry); + RB_REMOVE(tnbr_head, &vty_conf->tnbr_tree, tnbr); free(tnbr); ldp_reload(vty_conf); return (CMD_SUCCESS); @@ -966,7 +966,7 @@ ldp_vty_neighbor_targeted(struct vty *vty, struct vty_arg *args[]) tnbr = tnbr_new(af, &addr); tnbr->flags |= F_TNBR_CONFIGURED; - LIST_INSERT_HEAD(&vty_conf->tnbr_list, tnbr, entry); + RB_INSERT(tnbr_head, &vty_conf->tnbr_tree, tnbr); ldp_reload(vty_conf); @@ -1665,14 +1665,14 @@ tnbr_new_api(struct ldpd_conf *conf, int af, union ldpd_addr *addr) tnbr = tnbr_new(af, addr); tnbr->flags |= F_TNBR_CONFIGURED; - LIST_INSERT_HEAD(&conf->tnbr_list, tnbr, entry); + RB_INSERT(tnbr_head, &conf->tnbr_tree, tnbr); return (tnbr); } void -tnbr_del_api(struct tnbr *tnbr) +tnbr_del_api(struct ldpd_conf *conf, struct tnbr *tnbr) { - LIST_REMOVE(tnbr, entry); + RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr); free(tnbr); } diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c index 14cfaff..cf793f5 100644 --- a/ldpd/ldpd.c +++ b/ldpd/ldpd.c @@ -856,7 +856,7 @@ main_imsg_send_config(struct ldpd_conf *xconf) return (-1); } - LIST_FOREACH(tnbr, &xconf->tnbr_list, entry) { + RB_FOREACH(tnbr, tnbr_head, &xconf->tnbr_tree) { if (main_imsg_compose_both(IMSG_RECONF_TNBR, tnbr, sizeof(*tnbr)) == -1) return (-1); @@ -992,13 +992,13 @@ ldp_config_reset_af(struct ldpd_conf *conf, int af, void **ref) ia->enabled = 0; } - LIST_FOREACH_SAFE(tnbr, &conf->tnbr_list, entry, ttmp) { + RB_FOREACH_SAFE(tnbr, tnbr_head, &conf->tnbr_tree, ttmp) { if (tnbr->af != af) continue; if (ref && *ref == tnbr) *ref = NULL; - LIST_REMOVE(tnbr, entry); + RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr); free(tnbr); } @@ -1033,7 +1033,7 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) COPY(xconf, conf); RB_INIT(&xconf->iface_tree); - LIST_INIT(&xconf->tnbr_list); + RB_INIT(&xconf->tnbr_tree); LIST_INIT(&xconf->nbrp_list); LIST_INIT(&xconf->l2vpn_list); @@ -1043,9 +1043,9 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) xi->ipv6.iface = xi; RB_INSERT(iface_head, &xconf->iface_tree, xi); } - LIST_FOREACH(tnbr, &conf->tnbr_list, entry) { + RB_FOREACH(tnbr, tnbr_head, &conf->tnbr_tree) { COPY(xt, tnbr); - LIST_INSERT_HEAD(&xconf->tnbr_list, xt, entry); + RB_INSERT(tnbr_head, &xconf->tnbr_tree, xt); } LIST_FOREACH(nbrp, &conf->nbrp_list, entry) { COPY(xn, nbrp); @@ -1097,8 +1097,8 @@ ldp_clear_config(struct ldpd_conf *xconf) RB_REMOVE(iface_head, &xconf->iface_tree, iface); free(iface); } - while ((tnbr = LIST_FIRST(&xconf->tnbr_list)) != NULL) { - LIST_REMOVE(tnbr, entry); + while ((tnbr = RB_ROOT(&xconf->tnbr_tree)) != NULL) { + RB_REMOVE(tnbr_head, &xconf->tnbr_tree, tnbr); free(tnbr); } while ((nbrp = LIST_FIRST(&xconf->nbrp_list)) != NULL) { @@ -1295,7 +1295,7 @@ merge_tnbrs(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) { struct tnbr *tnbr, *ttmp, *xt; - LIST_FOREACH_SAFE(tnbr, &conf->tnbr_list, entry, ttmp) { + RB_FOREACH_SAFE(tnbr, tnbr_head, &conf->tnbr_tree, ttmp) { if (!(tnbr->flags & F_TNBR_CONFIGURED)) continue; @@ -1303,26 +1303,26 @@ merge_tnbrs(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) if ((xt = tnbr_find(xconf, tnbr->af, &tnbr->addr)) == NULL) { switch (ldpd_process) { case PROC_LDE_ENGINE: - LIST_REMOVE(tnbr, entry); + RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr); free(tnbr); break; case PROC_LDP_ENGINE: tnbr->flags &= ~F_TNBR_CONFIGURED; - tnbr_check(tnbr); + tnbr_check(conf, tnbr); break; case PROC_MAIN: - LIST_REMOVE(tnbr, entry); + RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr); QOBJ_UNREG (tnbr); free(tnbr); break; } } } - LIST_FOREACH_SAFE(xt, &xconf->tnbr_list, entry, ttmp) { + RB_FOREACH_SAFE(xt, tnbr_head, &xconf->tnbr_tree, ttmp) { /* find new tnbrs */ if ((tnbr = tnbr_find(conf, xt->af, &xt->addr)) == NULL) { - LIST_REMOVE(xt, entry); - LIST_INSERT_HEAD(&conf->tnbr_list, xt, entry); + RB_REMOVE(tnbr_head, &xconf->tnbr_tree, xt); + RB_INSERT(tnbr_head, &conf->tnbr_tree, xt); switch (ldpd_process) { case PROC_LDE_ENGINE: @@ -1340,7 +1340,7 @@ merge_tnbrs(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) /* update existing tnbrs */ if (!(tnbr->flags & F_TNBR_CONFIGURED)) tnbr->flags |= F_TNBR_CONFIGURED; - LIST_REMOVE(xt, entry); + RB_REMOVE(tnbr_head, &xconf->tnbr_tree, xt); if (ref && *ref == xt) *ref = tnbr; free(xt); @@ -1771,7 +1771,7 @@ config_new_empty(void) fatal(NULL); RB_INIT(&xconf->iface_tree); - LIST_INIT(&xconf->tnbr_list); + RB_INIT(&xconf->tnbr_tree); LIST_INIT(&xconf->nbrp_list); LIST_INIT(&xconf->l2vpn_list); diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h index 2c516c0..7e5b424 100644 --- a/ldpd/ldpd.h +++ b/ldpd/ldpd.h @@ -281,7 +281,7 @@ DECLARE_QOBJ_TYPE(iface) /* source of targeted hellos */ struct tnbr { - LIST_ENTRY(tnbr) entry; + RB_ENTRY(tnbr) entry; struct thread *hello_timer; struct adj *adj; int af; @@ -291,6 +291,8 @@ struct tnbr { uint8_t flags; QOBJ_FIELDS }; +RB_HEAD(tnbr_head, tnbr); +RB_PROTOTYPE(tnbr_head, tnbr, entry, tnbr_compare); DECLARE_QOBJ_TYPE(tnbr) #define F_TNBR_CONFIGURED 0x01 #define F_TNBR_DYNAMIC 0x02 @@ -407,7 +409,7 @@ struct ldpd_conf { struct ldpd_af_conf ipv4; struct ldpd_af_conf ipv6; struct iface_head iface_tree; - LIST_HEAD(, tnbr) tnbr_list; + struct tnbr_head tnbr_tree; LIST_HEAD(, nbr_params) nbrp_list; LIST_HEAD(, l2vpn) l2vpn_list; uint16_t lhello_holdtime; @@ -633,9 +635,9 @@ struct iface *iface_new_api(struct ldpd_conf *conf, const char *name); void iface_del_api(struct ldpd_conf *conf, struct iface *iface); -struct tnbr *tnbr_new_api(struct ldpd_conf *cfg, int af, +struct tnbr *tnbr_new_api(struct ldpd_conf *conf, int af, union ldpd_addr *addr); -void tnbr_del_api(struct tnbr *tnbr); +void tnbr_del_api(struct ldpd_conf *conf, struct tnbr *tnbr); struct nbr_params *nbrp_new_api(struct ldpd_conf *cfg, struct in_addr lsr_id); void nbrp_del_api(struct nbr_params *nbrp); diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c index 16910a3..699ce50 100644 --- a/ldpd/ldpe.c +++ b/ldpd/ldpe.c @@ -415,7 +415,7 @@ ldpe_dispatch_main(struct thread *thread) memcpy(nconf, imsg.data, sizeof(struct ldpd_conf)); RB_INIT(&nconf->iface_tree); - LIST_INIT(&nconf->tnbr_list); + RB_INIT(&nconf->tnbr_tree); LIST_INIT(&nconf->nbrp_list); LIST_INIT(&nconf->l2vpn_list); break; @@ -437,7 +437,7 @@ ldpe_dispatch_main(struct thread *thread) fatal(NULL); memcpy(ntnbr, imsg.data, sizeof(struct tnbr)); - LIST_INSERT_HEAD(&nconf->tnbr_list, ntnbr, entry); + RB_INSERT(tnbr_head, &nconf->tnbr_tree, ntnbr); break; case IMSG_RECONF_NBRP: if ((nnbrp = malloc(sizeof(struct nbr_params))) == NULL) @@ -743,12 +743,12 @@ ldpe_remove_dynamic_tnbrs(int af) { struct tnbr *tnbr, *safe; - LIST_FOREACH_SAFE(tnbr, &leconf->tnbr_list, entry, safe) { + RB_FOREACH_SAFE(tnbr, tnbr_head, &leconf->tnbr_tree, safe) { if (tnbr->af != af) continue; tnbr->flags &= ~F_TNBR_DYNAMIC; - tnbr_check(tnbr); + tnbr_check(leconf, tnbr); } } @@ -832,7 +832,7 @@ ldpe_adj_ctl(struct ctl_conn *c) } } - LIST_FOREACH(tnbr, &leconf->tnbr_list, entry) { + RB_FOREACH(tnbr, tnbr_head, &leconf->tnbr_tree) { memset(&tctl, 0, sizeof(tctl)); tctl.af = tnbr->af; tctl.addr = tnbr->addr; diff --git a/ldpd/ldpe.h b/ldpd/ldpe.h index aab1a7f..52899fd 100644 --- a/ldpd/ldpe.h +++ b/ldpd/ldpe.h @@ -225,7 +225,7 @@ void adj_start_itimer(struct adj *); void adj_stop_itimer(struct adj *); struct tnbr *tnbr_new(int, union ldpd_addr *); struct tnbr *tnbr_find(struct ldpd_conf *, int, union ldpd_addr *); -struct tnbr *tnbr_check(struct tnbr *); +struct tnbr *tnbr_check(struct ldpd_conf *, struct tnbr *); void tnbr_update(struct tnbr *); void tnbr_update_all(int); uint16_t tnbr_get_hello_holdtime(struct tnbr *); -- 1.9.1