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 | 26 +++++++++++++++----------- ldpd/lde.c | 4 ++-- ldpd/ldp_vty_conf.c | 16 ++++++++-------- ldpd/ldpd.c | 22 +++++++++++----------- ldpd/ldpd.h | 9 ++++++--- ldpd/ldpe.c | 4 ++-- 6 files changed, 44 insertions(+), 37 deletions(-) diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c index b339c9c..02f25e1 100644 --- a/ldpd/l2vpn.c +++ b/ldpd/l2vpn.c @@ -28,8 +28,10 @@ static void l2vpn_pw_fec(struct l2vpn_pw *, struct fec *); static __inline int l2vpn_compare(struct l2vpn *, struct l2vpn *); +static __inline int l2vpn_if_compare(struct l2vpn_if *, struct l2vpn_if *); RB_GENERATE(l2vpn_head, l2vpn, entry, l2vpn_compare) +RB_GENERATE(l2vpn_if_head, l2vpn_if, entry, l2vpn_if_compare) static __inline int l2vpn_compare(struct l2vpn *a, struct l2vpn *b) @@ -51,7 +53,7 @@ l2vpn_new(const char *name) l2vpn->mtu = DEFAULT_L2VPN_MTU; l2vpn->pw_type = DEFAULT_PW_TYPE; - LIST_INIT(&l2vpn->if_list); + RB_INIT(&l2vpn->if_tree); LIST_INIT(&l2vpn->pw_list); LIST_INIT(&l2vpn->pw_inactive_list); @@ -72,8 +74,8 @@ l2vpn_del(struct l2vpn *l2vpn) struct l2vpn_if *lif; struct l2vpn_pw *pw; - while ((lif = LIST_FIRST(&l2vpn->if_list)) != NULL) { - LIST_REMOVE(lif, entry); + while ((lif = RB_ROOT(&l2vpn->if_tree)) != NULL) { + RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } while ((pw = LIST_FIRST(&l2vpn->pw_list)) != NULL) { @@ -106,6 +108,12 @@ l2vpn_exit(struct l2vpn *l2vpn) l2vpn_pw_exit(pw); } +static __inline int +l2vpn_if_compare(struct l2vpn_if *a, struct l2vpn_if *b) +{ + return (strcmp(a->ifname, b->ifname)); +} + struct l2vpn_if * l2vpn_if_new(struct l2vpn *l2vpn, struct kif *kif) { @@ -127,7 +135,7 @@ l2vpn_if_find(struct l2vpn *l2vpn, unsigned int ifindex) { struct l2vpn_if *lif; - LIST_FOREACH(lif, &l2vpn->if_list, entry) + RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) if (lif->ifindex == ifindex) return (lif); @@ -137,13 +145,9 @@ l2vpn_if_find(struct l2vpn *l2vpn, unsigned int ifindex) struct l2vpn_if * l2vpn_if_find_name(struct l2vpn *l2vpn, const char *ifname) { - struct l2vpn_if *lif; - - LIST_FOREACH(lif, &l2vpn->if_list, entry) - if (strcmp(lif->ifname, ifname) == 0) - return (lif); - - return (NULL); + struct l2vpn_if lif; + strlcpy(lif.ifname, ifname, sizeof(lif.ifname)); + return (RB_FIND(l2vpn_if_head, &l2vpn->if_tree, &lif)); } diff --git a/ldpd/lde.c b/ldpd/lde.c index 3feb27d..522650c 100644 --- a/ldpd/lde.c +++ b/ldpd/lde.c @@ -510,7 +510,7 @@ lde_dispatch_parent(struct thread *thread) fatal(NULL); memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn)); - LIST_INIT(&nl2vpn->if_list); + RB_INIT(&nl2vpn->if_tree); LIST_INIT(&nl2vpn->pw_list); LIST_INIT(&nl2vpn->pw_inactive_list); @@ -522,7 +522,7 @@ lde_dispatch_parent(struct thread *thread) memcpy(nlif, imsg.data, sizeof(struct l2vpn_if)); nlif->l2vpn = nl2vpn; - LIST_INSERT_HEAD(&nl2vpn->if_list, nlif, entry); + RB_INSERT(l2vpn_if_head, &nl2vpn->if_tree, nlif); break; case IMSG_RECONF_L2VPN_PW: if ((npw = malloc(sizeof(struct l2vpn_pw))) == NULL) diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c index b66d8d4..b979642 100644 --- a/ldpd/ldp_vty_conf.c +++ b/ldpd/ldp_vty_conf.c @@ -354,7 +354,7 @@ ldp_l2vpn_config_write(struct vty *vty) vty_out(vty, " bridge %s%s", l2vpn->br_ifname, VTY_NEWLINE); - LIST_FOREACH(lif, &l2vpn->if_list, entry) + RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) vty_out(vty, " member interface %s%s", lif->ifname, VTY_NEWLINE); @@ -1369,7 +1369,7 @@ ldp_vty_l2vpn_interface(struct vty *vty, struct vty_arg *args[]) if (lif == NULL) goto cancel; - LIST_REMOVE(lif, entry); + RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); ldp_reload(vty_conf); return (CMD_SUCCESS); @@ -1392,7 +1392,7 @@ ldp_vty_l2vpn_interface(struct vty *vty, struct vty_arg *args[]) } lif = l2vpn_if_new(l2vpn, &kif); - LIST_INSERT_HEAD(&l2vpn->if_list, lif, entry); + RB_INSERT(l2vpn_if_head, &l2vpn->if_tree, lif); ldp_reload_ref(vty_conf, (void **)&l2vpn); @@ -1716,8 +1716,8 @@ l2vpn_del_api(struct ldpd_conf *conf, struct l2vpn *l2vpn) struct l2vpn_if *lif; struct l2vpn_pw *pw; - while ((lif = LIST_FIRST(&l2vpn->if_list)) != NULL) { - LIST_REMOVE(lif, entry); + while ((lif = RB_ROOT(&l2vpn->if_tree)) != NULL) { + RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } while ((pw = LIST_FIRST(&l2vpn->pw_list)) != NULL) { @@ -1752,14 +1752,14 @@ l2vpn_if_new_api(struct ldpd_conf *conf, struct l2vpn *l2vpn, } lif = l2vpn_if_new(l2vpn, &kif); - LIST_INSERT_HEAD(&l2vpn->if_list, lif, entry); + RB_INSERT(l2vpn_if_head, &l2vpn->if_tree, lif); return (lif); } void -l2vpn_if_del_api(struct l2vpn_if *lif) +l2vpn_if_del_api(struct l2vpn *l2vpn, struct l2vpn_if *lif) { - LIST_REMOVE(lif, entry); + RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c index dab761d..0df9bbd 100644 --- a/ldpd/ldpd.c +++ b/ldpd/ldpd.c @@ -873,7 +873,7 @@ main_imsg_send_config(struct ldpd_conf *xconf) sizeof(*l2vpn)) == -1) return (-1); - LIST_FOREACH(lif, &l2vpn->if_list, entry) { + RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) { if (main_imsg_compose_both(IMSG_RECONF_L2VPN_IF, lif, sizeof(*lif)) == -1) return (-1); @@ -1053,15 +1053,15 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) } RB_FOREACH(l2vpn, l2vpn_head, &conf->l2vpn_tree) { COPY(xl, l2vpn); - LIST_INIT(&xl->if_list); + RB_INIT(&xl->if_tree); LIST_INIT(&xl->pw_list); LIST_INIT(&xl->pw_inactive_list); RB_INSERT(l2vpn_head, &xconf->l2vpn_tree, xl); - LIST_FOREACH(lif, &l2vpn->if_list, entry) { + RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) { COPY(xf, lif); xf->l2vpn = xl; - LIST_INSERT_HEAD(&xl->if_list, xf, entry); + RB_INSERT(l2vpn_if_head, &xl->if_tree, xf); } LIST_FOREACH(pw, &l2vpn->pw_list, entry) { COPY(xp, pw); @@ -1482,7 +1482,7 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) ldpe_l2vpn_exit(l2vpn); break; case PROC_MAIN: - LIST_FOREACH(lif, &l2vpn->if_list, entry) + RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) QOBJ_UNREG (lif); LIST_FOREACH(pw, &l2vpn->pw_list, entry) QOBJ_UNREG (pw); @@ -1537,27 +1537,27 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void previous_mtu = l2vpn->mtu; /* merge intefaces */ - LIST_FOREACH_SAFE(lif, &l2vpn->if_list, entry, ftmp) { + RB_FOREACH_SAFE(lif, l2vpn_if_head, &l2vpn->if_tree, ftmp) { /* find deleted interfaces */ if ((xf = l2vpn_if_find_name(xl, lif->ifname)) == NULL) { if (ldpd_process == PROC_MAIN) QOBJ_UNREG (lif); - LIST_REMOVE(lif, entry); + RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } } - LIST_FOREACH_SAFE(xf, &xl->if_list, entry, ftmp) { + RB_FOREACH_SAFE(xf, l2vpn_if_head, &xl->if_tree, ftmp) { /* find new interfaces */ if ((lif = l2vpn_if_find_name(l2vpn, xf->ifname)) == NULL) { - LIST_REMOVE(xf, entry); - LIST_INSERT_HEAD(&l2vpn->if_list, xf, entry); + RB_REMOVE(l2vpn_if_head, &xl->if_tree, xf); + RB_INSERT(l2vpn_if_head, &l2vpn->if_tree, xf); xf->l2vpn = l2vpn; if (ldpd_process == PROC_MAIN) QOBJ_REG (xf, l2vpn_if); continue; } - LIST_REMOVE(xf, entry); + RB_REMOVE(l2vpn_if_head, &xl->if_tree, xf); if (ref && *ref == xf) *ref = lif; free(xf); diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h index 72e5dc5..0a21856 100644 --- a/ldpd/ldpd.h +++ b/ldpd/ldpd.h @@ -325,13 +325,15 @@ DECLARE_QOBJ_TYPE(nbr_params) #define F_NBRP_GTSM_HOPS 0x04 struct l2vpn_if { - LIST_ENTRY(l2vpn_if) entry; + RB_ENTRY(l2vpn_if) entry; struct l2vpn *l2vpn; char ifname[IF_NAMESIZE]; unsigned int ifindex; uint16_t flags; QOBJ_FIELDS }; +RB_HEAD(l2vpn_if_head, l2vpn_if); +RB_PROTOTYPE(l2vpn_if_head, l2vpn_if, entry, l2vpn_if_compare); DECLARE_QOBJ_TYPE(l2vpn_if) struct l2vpn_pw { @@ -365,7 +367,7 @@ struct l2vpn { int mtu; char br_ifname[IF_NAMESIZE]; unsigned int br_ifindex; - LIST_HEAD(, l2vpn_if) if_list; + struct l2vpn_if_head if_tree; LIST_HEAD(, l2vpn_pw) pw_list; LIST_HEAD(, l2vpn_pw) pw_inactive_list; QOBJ_FIELDS @@ -651,7 +653,8 @@ 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); +void l2vpn_if_del_api(struct l2vpn *l2vpn, + struct l2vpn_if *lif); struct l2vpn_pw *l2vpn_pw_new_api(struct ldpd_conf *conf, struct l2vpn *l2vpn, const char *ifname); void l2vpn_pw_del_api(struct l2vpn_pw *pw); diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c index 6edd180..2a9fb4c 100644 --- a/ldpd/ldpe.c +++ b/ldpd/ldpe.c @@ -451,7 +451,7 @@ ldpe_dispatch_main(struct thread *thread) fatal(NULL); memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn)); - LIST_INIT(&nl2vpn->if_list); + RB_INIT(&nl2vpn->if_tree); LIST_INIT(&nl2vpn->pw_list); LIST_INIT(&nl2vpn->pw_inactive_list); @@ -463,7 +463,7 @@ ldpe_dispatch_main(struct thread *thread) memcpy(nlif, imsg.data, sizeof(struct l2vpn_if)); nlif->l2vpn = nl2vpn; - LIST_INSERT_HEAD(&nl2vpn->if_list, nlif, entry); + RB_INSERT(l2vpn_if_head, &nl2vpn->if_tree, nlif); break; case IMSG_RECONF_L2VPN_PW: if ((npw = malloc(sizeof(struct l2vpn_pw))) == NULL) -- 1.9.1