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/l2vpn.c | 25 +++++++++++++++---------- ldpd/lde.c | 4 ++-- ldpd/ldp_vty_conf.c | 14 +++++++------- ldpd/ldpd.c | 28 ++++++++++++++-------------- ldpd/ldpd.h | 11 +++++++---- ldpd/ldpe.c | 4 ++-- 6 files changed, 47 insertions(+), 39 deletions(-) diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c index dc9879e..b339c9c 100644 --- a/ldpd/l2vpn.c +++ b/ldpd/l2vpn.c @@ -26,7 +26,16 @@ #include "lde.h" #include "log.h" -static void l2vpn_pw_fec(struct l2vpn_pw *, struct fec *); +static void l2vpn_pw_fec(struct l2vpn_pw *, struct fec *); +static __inline int l2vpn_compare(struct l2vpn *, struct l2vpn *); + +RB_GENERATE(l2vpn_head, l2vpn, entry, l2vpn_compare) + +static __inline int +l2vpn_compare(struct l2vpn *a, struct l2vpn *b) +{ + return (strcmp(a->name, b->name)); +} struct l2vpn * l2vpn_new(const char *name) @@ -52,13 +61,9 @@ l2vpn_new(const char *name) struct l2vpn * l2vpn_find(struct ldpd_conf *xconf, const char *name) { - struct l2vpn *l2vpn; - - LIST_FOREACH(l2vpn, &xconf->l2vpn_list, entry) - if (strcmp(l2vpn->name, name) == 0) - return (l2vpn); - - return (NULL); + struct l2vpn l2vpn; + strlcpy(l2vpn.name, name, sizeof(l2vpn.name)); + return (RB_FIND(l2vpn_head, &xconf->l2vpn_tree, &l2vpn)); } void @@ -399,7 +404,7 @@ l2vpn_sync_pws(int af, union ldpd_addr *addr) struct fec_node *fn; struct fec_nh *fnh; - LIST_FOREACH(l2vpn, &ldeconf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &ldeconf->l2vpn_tree) { LIST_FOREACH(pw, &l2vpn->pw_list, entry) { if (af != pw->af || ldp_addrcmp(af, &pw->addr, addr)) continue; @@ -428,7 +433,7 @@ l2vpn_pw_ctl(pid_t pid) struct l2vpn_pw *pw; static struct ctl_pw pwctl; - LIST_FOREACH(l2vpn, &ldeconf->l2vpn_list, entry) + RB_FOREACH(l2vpn, l2vpn_head, &ldeconf->l2vpn_tree) LIST_FOREACH(pw, &l2vpn->pw_list, entry) { memset(&pwctl, 0, sizeof(pwctl)); strlcpy(pwctl.l2vpn_name, pw->l2vpn->name, diff --git a/ldpd/lde.c b/ldpd/lde.c index 80557ed..3feb27d 100644 --- a/ldpd/lde.c +++ b/ldpd/lde.c @@ -476,7 +476,7 @@ lde_dispatch_parent(struct thread *thread) RB_INIT(&nconf->iface_tree); RB_INIT(&nconf->tnbr_tree); RB_INIT(&nconf->nbrp_tree); - LIST_INIT(&nconf->l2vpn_list); + RB_INIT(&nconf->l2vpn_tree); break; case IMSG_RECONF_IFACE: if ((niface = malloc(sizeof(struct iface))) == NULL) @@ -514,7 +514,7 @@ lde_dispatch_parent(struct thread *thread) LIST_INIT(&nl2vpn->pw_list); LIST_INIT(&nl2vpn->pw_inactive_list); - LIST_INSERT_HEAD(&nconf->l2vpn_list, nl2vpn, entry); + RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn); break; case IMSG_RECONF_L2VPN_IF: if ((nlif = malloc(sizeof(struct l2vpn_if))) == NULL) diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c index 95b0971..b66d8d4 100644 --- a/ldpd/ldp_vty_conf.c +++ b/ldpd/ldp_vty_conf.c @@ -341,7 +341,7 @@ ldp_l2vpn_config_write(struct vty *vty) struct l2vpn_if *lif; struct l2vpn_pw *pw; - LIST_FOREACH(l2vpn, &ldpd_conf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &ldpd_conf->l2vpn_tree) { vty_out(vty, "l2vpn %s type vpls%s", l2vpn->name, VTY_NEWLINE); if (l2vpn->pw_type != DEFAULT_PW_TYPE) @@ -393,7 +393,7 @@ ldp_iface_is_configured(struct ldpd_conf *xconf, const char *ifname) if (if_lookup_name(xconf, ifname)) return (1); - LIST_FOREACH(l2vpn, &xconf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &xconf->l2vpn_tree) { if (l2vpn_if_find_name(l2vpn, ifname)) return (1); if (l2vpn_pw_find_name(l2vpn, ifname)) @@ -1235,7 +1235,7 @@ ldp_vty_l2vpn(struct vty *vty, struct vty_arg *args[]) if (l2vpn == NULL) goto cancel; - LIST_REMOVE(l2vpn, entry); + RB_REMOVE(l2vpn_head, &vty_conf->l2vpn_tree, l2vpn); l2vpn_del(l2vpn); ldp_reload(vty_conf); return (CMD_SUCCESS); @@ -1248,7 +1248,7 @@ ldp_vty_l2vpn(struct vty *vty, struct vty_arg *args[]) l2vpn = l2vpn_new(name_str); l2vpn->type = L2VPN_TYPE_VPLS; - LIST_INSERT_HEAD(&vty_conf->l2vpn_list, l2vpn, entry); + RB_INSERT(l2vpn_head, &vty_conf->l2vpn_tree, l2vpn); ldp_reload_ref(vty_conf, (void **)&l2vpn); VTY_PUSH_CONTEXT(LDP_L2VPN_NODE, l2vpn); @@ -1706,12 +1706,12 @@ l2vpn_new_api(struct ldpd_conf *conf, const char *name) l2vpn = l2vpn_new(name); l2vpn->type = L2VPN_TYPE_VPLS; - LIST_INSERT_HEAD(&conf->l2vpn_list, l2vpn, entry); + RB_INSERT(l2vpn_head, &conf->l2vpn_tree, l2vpn); return (l2vpn); } void -l2vpn_del_api(struct l2vpn *l2vpn) +l2vpn_del_api(struct ldpd_conf *conf, struct l2vpn *l2vpn) { struct l2vpn_if *lif; struct l2vpn_pw *pw; @@ -1728,7 +1728,7 @@ l2vpn_del_api(struct l2vpn *l2vpn) LIST_REMOVE(pw, entry); free(pw); } - LIST_REMOVE(l2vpn, entry); + RB_REMOVE(l2vpn_head, &conf->l2vpn_tree, l2vpn); free(l2vpn); } diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c index 37cc0de..dab761d 100644 --- a/ldpd/ldpd.c +++ b/ldpd/ldpd.c @@ -868,7 +868,7 @@ main_imsg_send_config(struct ldpd_conf *xconf) return (-1); } - LIST_FOREACH(l2vpn, &xconf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &xconf->l2vpn_tree) { if (main_imsg_compose_both(IMSG_RECONF_L2VPN, l2vpn, sizeof(*l2vpn)) == -1) return (-1); @@ -930,7 +930,7 @@ ldp_config_normalize(struct ldpd_conf *xconf, void **ref) ldp_config_reset_af(xconf, AF_INET6, ref); } - LIST_FOREACH(l2vpn, &xconf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &xconf->l2vpn_tree) { LIST_FOREACH(pw, &l2vpn->pw_list, entry) { if (pw->flags & F_PW_STATIC_NBR_ADDR) continue; @@ -1035,7 +1035,7 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) RB_INIT(&xconf->iface_tree); RB_INIT(&xconf->tnbr_tree); RB_INIT(&xconf->nbrp_tree); - LIST_INIT(&xconf->l2vpn_list); + RB_INIT(&xconf->l2vpn_tree); RB_FOREACH(iface, iface_head, &conf->iface_tree) { COPY(xi, iface); @@ -1051,12 +1051,12 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) COPY(xn, nbrp); RB_INSERT(nbrp_head, &xconf->nbrp_tree, xn); } - LIST_FOREACH(l2vpn, &conf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &conf->l2vpn_tree) { COPY(xl, l2vpn); LIST_INIT(&xl->if_list); LIST_INIT(&xl->pw_list); LIST_INIT(&xl->pw_inactive_list); - LIST_INSERT_HEAD(&xconf->l2vpn_list, xl, entry); + RB_INSERT(l2vpn_head, &xconf->l2vpn_tree, xl); LIST_FOREACH(lif, &l2vpn->if_list, entry) { COPY(xf, lif); @@ -1105,8 +1105,8 @@ ldp_clear_config(struct ldpd_conf *xconf) RB_REMOVE(nbrp_head, &xconf->nbrp_tree, nbrp); free(nbrp); } - while ((l2vpn = LIST_FIRST(&xconf->l2vpn_list)) != NULL) { - LIST_REMOVE(l2vpn, entry); + while ((l2vpn = RB_ROOT(&xconf->l2vpn_tree)) != NULL) { + RB_REMOVE(l2vpn_head, &xconf->l2vpn_tree, l2vpn); l2vpn_del(l2vpn); } @@ -1469,10 +1469,10 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) struct l2vpn_if *lif; struct l2vpn_pw *pw; - LIST_FOREACH_SAFE(l2vpn, &conf->l2vpn_list, entry, ltmp) { + RB_FOREACH_SAFE(l2vpn, l2vpn_head, &conf->l2vpn_tree, ltmp) { /* find deleted l2vpns */ if ((xl = l2vpn_find(xconf, l2vpn->name)) == NULL) { - LIST_REMOVE(l2vpn, entry); + RB_REMOVE(l2vpn_head, &conf->l2vpn_tree, l2vpn); switch (ldpd_process) { case PROC_LDE_ENGINE: @@ -1494,11 +1494,11 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) l2vpn_del(l2vpn); } } - LIST_FOREACH_SAFE(xl, &xconf->l2vpn_list, entry, ltmp) { + RB_FOREACH_SAFE(xl, l2vpn_head, &xconf->l2vpn_tree, ltmp) { /* find new l2vpns */ if ((l2vpn = l2vpn_find(conf, xl->name)) == NULL) { - LIST_REMOVE(xl, entry); - LIST_INSERT_HEAD(&conf->l2vpn_list, xl, entry); + RB_REMOVE(l2vpn_head, &xconf->l2vpn_tree, xl); + RB_INSERT(l2vpn_head, &conf->l2vpn_tree, xl); switch (ldpd_process) { case PROC_LDE_ENGINE: @@ -1516,7 +1516,7 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) /* update existing l2vpns */ merge_l2vpn(conf, l2vpn, xl, ref); - LIST_REMOVE(xl, entry); + RB_REMOVE(l2vpn_head, &xconf->l2vpn_tree, xl); if (ref && *ref == xl) *ref = l2vpn; free(xl); @@ -1773,7 +1773,7 @@ config_new_empty(void) RB_INIT(&xconf->iface_tree); RB_INIT(&xconf->tnbr_tree); RB_INIT(&xconf->nbrp_tree); - LIST_INIT(&xconf->l2vpn_list); + RB_INIT(&xconf->l2vpn_tree); return (xconf); } diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h index d8f75a0..72e5dc5 100644 --- a/ldpd/ldpd.h +++ b/ldpd/ldpd.h @@ -358,7 +358,7 @@ DECLARE_QOBJ_TYPE(l2vpn_pw) #define F_PW_STATIC_NBR_ADDR 0x20 /* static neighbor address configured */ struct l2vpn { - LIST_ENTRY(l2vpn) entry; + RB_ENTRY(l2vpn) entry; char name[L2VPN_NAME_LEN]; int type; int pw_type; @@ -370,6 +370,8 @@ struct l2vpn { LIST_HEAD(, l2vpn_pw) pw_inactive_list; QOBJ_FIELDS }; +RB_HEAD(l2vpn_head, l2vpn); +RB_PROTOTYPE(l2vpn_head, l2vpn, entry, l2vpn_compare); DECLARE_QOBJ_TYPE(l2vpn) #define L2VPN_TYPE_VPWS 1 #define L2VPN_TYPE_VPLS 2 @@ -413,7 +415,7 @@ struct ldpd_conf { struct iface_head iface_tree; struct tnbr_head tnbr_tree; struct nbrp_head nbrp_tree; - LIST_HEAD(, l2vpn) l2vpn_list; + struct l2vpn_head l2vpn_tree; uint16_t lhello_holdtime; uint16_t lhello_interval; uint16_t thello_holdtime; @@ -644,8 +646,9 @@ struct nbr_params *nbrp_new_api(struct ldpd_conf *conf, struct in_addr lsr_id); 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 *l2vpn_new_api(struct ldpd_conf *conf, const char *name); +void l2vpn_del_api(struct ldpd_conf *conf, + struct l2vpn *l2vpn); struct l2vpn_if *l2vpn_if_new_api(struct ldpd_conf *conf, struct l2vpn *l2vpn, const char *ifname); void l2vpn_if_del_api(struct l2vpn_if *lif); diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c index e9e45f8..6edd180 100644 --- a/ldpd/ldpe.c +++ b/ldpd/ldpe.c @@ -417,7 +417,7 @@ ldpe_dispatch_main(struct thread *thread) RB_INIT(&nconf->iface_tree); RB_INIT(&nconf->tnbr_tree); RB_INIT(&nconf->nbrp_tree); - LIST_INIT(&nconf->l2vpn_list); + RB_INIT(&nconf->l2vpn_tree); break; case IMSG_RECONF_IFACE: if ((niface = malloc(sizeof(struct iface))) == NULL) @@ -455,7 +455,7 @@ ldpe_dispatch_main(struct thread *thread) LIST_INIT(&nl2vpn->pw_list); LIST_INIT(&nl2vpn->pw_inactive_list); - LIST_INSERT_HEAD(&nconf->l2vpn_list, nl2vpn, entry); + RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn); break; case IMSG_RECONF_L2VPN_IF: if ((nlif = malloc(sizeof(struct l2vpn_if))) == NULL) -- 1.9.1