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/interface.c | 37 +++++++++++++++++++++---------------- ldpd/lde.c | 4 ++-- ldpd/ldp_debug.c | 4 ++-- ldpd/ldp_vty_conf.c | 10 +++++----- ldpd/ldpd.c | 32 ++++++++++++++++---------------- ldpd/ldpd.h | 11 +++++++---- ldpd/ldpe.c | 8 ++++---- 7 files changed, 57 insertions(+), 49 deletions(-) diff --git a/ldpd/interface.c b/ldpd/interface.c index b6472fe..06d36fe 100644 --- a/ldpd/interface.c +++ b/ldpd/interface.c @@ -26,6 +26,7 @@ #include "sockopt.h" +static __inline int iface_compare(struct iface *, struct iface *); static struct if_addr *if_addr_new(struct kaddr *); static struct if_addr *if_addr_lookup(struct if_addr_head *, struct kaddr *); static int if_start(struct iface *, int); @@ -39,6 +40,14 @@ static int if_leave_ipv4_group(struct iface *, struct in_addr *); static int if_join_ipv6_group(struct iface *, struct in6_addr *); static int if_leave_ipv6_group(struct iface *, struct in6_addr *); +RB_GENERATE(iface_head, iface, entry, iface_compare) + +static __inline int +iface_compare(struct iface *a, struct iface *b) +{ + return (strcmp(a->name, b->name)); +} + struct iface * if_new(struct kif *kif) { @@ -69,18 +78,6 @@ if_new(struct kif *kif) return (iface); } -struct iface * -if_lookup(struct ldpd_conf *xconf, unsigned short ifindex) -{ - struct iface *iface; - - LIST_FOREACH(iface, &xconf->iface_list, entry) - if (iface->ifindex == ifindex) - return (iface); - - return (NULL); -} - void if_exit(struct iface *iface) { @@ -100,17 +97,25 @@ if_exit(struct iface *iface) } struct iface * -if_lookup_name(struct ldpd_conf *xconf, const char *ifname) +if_lookup(struct ldpd_conf *xconf, unsigned short ifindex) { struct iface *iface; - LIST_FOREACH(iface, &xconf->iface_list, entry) - if (strcmp(iface->name, ifname) == 0) + RB_FOREACH(iface, iface_head, &xconf->iface_tree) + if (iface->ifindex == ifindex) return (iface); return (NULL); } +struct iface * +if_lookup_name(struct ldpd_conf *xconf, const char *ifname) +{ + struct iface iface; + strlcpy(iface.name, ifname, sizeof(iface.name)); + return (RB_FIND(iface_head, &xconf->iface_tree, &iface)); +} + void if_update_info(struct iface *iface, struct kif *kif) { @@ -380,7 +385,7 @@ if_update_all(int af) { struct iface *iface; - LIST_FOREACH(iface, &leconf->iface_list, entry) + RB_FOREACH(iface, iface_head, &leconf->iface_tree) if_update(iface, af); } diff --git a/ldpd/lde.c b/ldpd/lde.c index a1309c6..1e36218 100644 --- a/ldpd/lde.c +++ b/ldpd/lde.c @@ -473,7 +473,7 @@ lde_dispatch_parent(struct thread *thread) fatal(NULL); memcpy(nconf, imsg.data, sizeof(struct ldpd_conf)); - LIST_INIT(&nconf->iface_list); + RB_INIT(&nconf->iface_tree); LIST_INIT(&nconf->tnbr_list); LIST_INIT(&nconf->nbrp_list); LIST_INIT(&nconf->l2vpn_list); @@ -489,7 +489,7 @@ lde_dispatch_parent(struct thread *thread) niface->ipv4.iface = niface; niface->ipv6.iface = niface; - LIST_INSERT_HEAD(&nconf->iface_list, niface, entry); + RB_INSERT(iface_head, &nconf->iface_tree, niface); break; case IMSG_RECONF_TNBR: if ((ntnbr = malloc(sizeof(struct tnbr))) == NULL) diff --git a/ldpd/ldp_debug.c b/ldpd/ldp_debug.c index 15dd06a..86b679d 100644 --- a/ldpd/ldp_debug.c +++ b/ldpd/ldp_debug.c @@ -74,7 +74,7 @@ ldp_vty_debug(struct vty *vty, struct vty_arg *args[]) DEBUG_OFF(event, EVENT); else DEBUG_ON(event, EVENT); - } else if (strcmp(type_str, "messages") == 0) { + } else if (strcmp(type_str, "messages") == 0) { all = (vty_get_arg_value(args, "all")) ? 1 : 0; dir_str = vty_get_arg_value(args, "dir"); if (dir_str == NULL) @@ -99,7 +99,7 @@ ldp_vty_debug(struct vty *vty, struct vty_arg *args[]) DEBUG_ON(msg, MSG_SEND_ALL); } } - } else if (strcmp(type_str, "zebra") == 0) { + } else if (strcmp(type_str, "zebra") == 0) { if (disable) DEBUG_OFF(zebra, ZEBRA); else diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c index dd70365..689554d 100644 --- a/ldpd/ldp_vty_conf.c +++ b/ldpd/ldp_vty_conf.c @@ -142,7 +142,7 @@ ldp_af_iface_config_write(struct vty *vty, int af) struct iface *iface; struct iface_af *ia; - LIST_FOREACH(iface, &ldpd_conf->iface_list, entry) { + RB_FOREACH(iface, iface_head, &ldpd_conf->iface_tree) { ia = iface_af_get(iface, af); if (!ia->enabled) continue; @@ -857,7 +857,7 @@ ldp_vty_interface(struct vty *vty, struct vty_arg *args[]) ia = iface_af_get(iface, af); ia->enabled = 1; - LIST_INSERT_HEAD(&vty_conf->iface_list, iface, entry); + RB_INSERT(iface_head, &vty_conf->iface_tree, iface); ldp_reload_ref(vty_conf, (void **)&iface); } else { memset(&kif, 0, sizeof(kif)); @@ -1641,14 +1641,14 @@ iface_new_api(struct ldpd_conf *conf, const char *name) } iface = if_new(&kif); - LIST_INSERT_HEAD(&conf->iface_list, iface, entry); + RB_INSERT(iface_head, &conf->iface_tree, iface); return (iface); } void -iface_del_api(struct iface *iface) +iface_del_api(struct ldpd_conf *conf, struct iface *iface) { - LIST_REMOVE(iface, entry); + RB_REMOVE(iface_head, &conf->iface_tree, iface); free(iface); } diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c index aa1dc57..14cfaff 100644 --- a/ldpd/ldpd.c +++ b/ldpd/ldpd.c @@ -850,7 +850,7 @@ main_imsg_send_config(struct ldpd_conf *xconf) sizeof(*xconf)) == -1) return (-1); - LIST_FOREACH(iface, &xconf->iface_list, entry) { + RB_FOREACH(iface, iface_head, &xconf->iface_tree) { if (main_imsg_compose_both(IMSG_RECONF_IFACE, iface, sizeof(*iface)) == -1) return (-1); @@ -954,10 +954,10 @@ ldp_config_reset_main(struct ldpd_conf *conf, void **ref) struct iface *iface; struct nbr_params *nbrp; - while ((iface = LIST_FIRST(&conf->iface_list)) != NULL) { + while ((iface = RB_ROOT(&conf->iface_tree)) != NULL) { if (ref && *ref == iface) *ref = NULL; - LIST_REMOVE(iface, entry); + RB_REMOVE(iface_head, &conf->iface_tree, iface); free(iface); } @@ -987,7 +987,7 @@ ldp_config_reset_af(struct ldpd_conf *conf, int af, void **ref) struct iface_af *ia; struct tnbr *tnbr, *ttmp; - LIST_FOREACH(iface, &conf->iface_list, entry) { + RB_FOREACH(iface, iface_head, &conf->iface_tree) { ia = iface_af_get(iface, af); ia->enabled = 0; } @@ -1032,16 +1032,16 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) } while (0) COPY(xconf, conf); - LIST_INIT(&xconf->iface_list); + RB_INIT(&xconf->iface_tree); LIST_INIT(&xconf->tnbr_list); LIST_INIT(&xconf->nbrp_list); LIST_INIT(&xconf->l2vpn_list); - LIST_FOREACH(iface, &conf->iface_list, entry) { + RB_FOREACH(iface, iface_head, &conf->iface_tree) { COPY(xi, iface); xi->ipv4.iface = xi; xi->ipv6.iface = xi; - LIST_INSERT_HEAD(&xconf->iface_list, xi, entry); + RB_INSERT(iface_head, &xconf->iface_tree, xi); } LIST_FOREACH(tnbr, &conf->tnbr_list, entry) { COPY(xt, tnbr); @@ -1093,8 +1093,8 @@ ldp_clear_config(struct ldpd_conf *xconf) struct nbr_params *nbrp; struct l2vpn *l2vpn; - while ((iface = LIST_FIRST(&xconf->iface_list)) != NULL) { - LIST_REMOVE(iface, entry); + while ((iface = RB_ROOT(&xconf->iface_tree)) != NULL) { + RB_REMOVE(iface_head, &xconf->iface_tree, iface); free(iface); } while ((tnbr = LIST_FIRST(&xconf->tnbr_list)) != NULL) { @@ -1236,10 +1236,10 @@ merge_ifaces(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) { struct iface *iface, *itmp, *xi; - LIST_FOREACH_SAFE(iface, &conf->iface_list, entry, itmp) { + RB_FOREACH_SAFE(iface, iface_head, &conf->iface_tree, itmp) { /* find deleted interfaces */ if ((xi = if_lookup_name(xconf, iface->name)) == NULL) { - LIST_REMOVE(iface, entry); + RB_REMOVE(iface_head, &conf->iface_tree, iface); switch (ldpd_process) { case PROC_LDE_ENGINE: @@ -1254,11 +1254,11 @@ merge_ifaces(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) free(iface); } } - LIST_FOREACH_SAFE(xi, &xconf->iface_list, entry, itmp) { + RB_FOREACH_SAFE(xi, iface_head, &xconf->iface_tree, itmp) { /* find new interfaces */ if ((iface = if_lookup_name(conf, xi->name)) == NULL) { - LIST_REMOVE(xi, entry); - LIST_INSERT_HEAD(&conf->iface_list, xi, entry); + RB_REMOVE(iface_head, &xconf->iface_tree, xi); + RB_INSERT(iface_head, &conf->iface_tree, xi); if (ldpd_process == PROC_MAIN) { QOBJ_REG (xi, iface); @@ -1271,7 +1271,7 @@ merge_ifaces(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) /* update existing interfaces */ merge_iface_af(&iface->ipv4, &xi->ipv4); merge_iface_af(&iface->ipv6, &xi->ipv6); - LIST_REMOVE(xi, entry); + RB_REMOVE(iface_head, &xconf->iface_tree, xi); if (ref && *ref == xi) *ref = iface; free(xi); @@ -1770,7 +1770,7 @@ config_new_empty(void) if (xconf == NULL) fatal(NULL); - LIST_INIT(&xconf->iface_list); + RB_INIT(&xconf->iface_tree); LIST_INIT(&xconf->tnbr_list); LIST_INIT(&xconf->nbrp_list); LIST_INIT(&xconf->l2vpn_list); diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h index 630b192..2c516c0 100644 --- a/ldpd/ldpd.h +++ b/ldpd/ldpd.h @@ -264,7 +264,7 @@ struct iface_af { }; struct iface { - LIST_ENTRY(iface) entry; + RB_ENTRY(iface) entry; char name[IF_NAMESIZE]; unsigned int ifindex; struct if_addr_head addr_list; @@ -275,6 +275,8 @@ struct iface { struct iface_af ipv6; QOBJ_FIELDS }; +RB_HEAD(iface_head, iface); +RB_PROTOTYPE(iface_head, iface, entry, iface_compare); DECLARE_QOBJ_TYPE(iface) /* source of targeted hellos */ @@ -404,7 +406,7 @@ struct ldpd_conf { struct in_addr rtr_id; struct ldpd_af_conf ipv4; struct ldpd_af_conf ipv6; - LIST_HEAD(, iface) iface_list; + struct iface_head iface_tree; LIST_HEAD(, tnbr) tnbr_list; LIST_HEAD(, nbr_params) nbrp_list; LIST_HEAD(, l2vpn) l2vpn_list; @@ -627,9 +629,10 @@ void config_clear(struct ldpd_conf *); /* ldp_vty_conf.c */ /* NOTE: the parameters' names should be preserved because of codegen */ -struct iface *iface_new_api(struct ldpd_conf *cfg, +struct iface *iface_new_api(struct ldpd_conf *conf, const char *name); -void iface_del_api(struct iface *iface); +void iface_del_api(struct ldpd_conf *conf, + struct iface *iface); struct tnbr *tnbr_new_api(struct ldpd_conf *cfg, int af, union ldpd_addr *addr); void tnbr_del_api(struct tnbr *tnbr); diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c index aef33c8..16910a3 100644 --- a/ldpd/ldpe.c +++ b/ldpd/ldpe.c @@ -414,7 +414,7 @@ ldpe_dispatch_main(struct thread *thread) fatal(NULL); memcpy(nconf, imsg.data, sizeof(struct ldpd_conf)); - LIST_INIT(&nconf->iface_list); + RB_INIT(&nconf->iface_tree); LIST_INIT(&nconf->tnbr_list); LIST_INIT(&nconf->nbrp_list); LIST_INIT(&nconf->l2vpn_list); @@ -430,7 +430,7 @@ ldpe_dispatch_main(struct thread *thread) niface->ipv4.iface = niface; niface->ipv6.iface = niface; - LIST_INSERT_HEAD(&nconf->iface_list, niface, entry); + RB_INSERT(iface_head, &nconf->iface_tree, niface); break; case IMSG_RECONF_TNBR: if ((ntnbr = malloc(sizeof(struct tnbr))) == NULL) @@ -772,7 +772,7 @@ ldpe_iface_af_ctl(struct ctl_conn *c, int af, unsigned int idx) struct iface_af *ia; struct ctl_iface *ictl; - LIST_FOREACH(iface, &leconf->iface_list, entry) { + RB_FOREACH(iface, iface_head, &leconf->iface_tree) { if (idx == 0 || idx == iface->ifindex) { ia = iface_af_get(iface, af); if (!ia->enabled) @@ -805,7 +805,7 @@ ldpe_adj_ctl(struct ctl_conn *c) imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISCOVERY, 0, 0, -1, NULL, 0); - LIST_FOREACH(iface, &leconf->iface_list, entry) { + RB_FOREACH(iface, iface_head, &leconf->iface_tree) { memset(&ictl, 0, sizeof(ictl)); ictl.active_v4 = (iface->ipv4.state == IF_STA_ACTIVE); ictl.active_v6 = (iface->ipv6.state == IF_STA_ACTIVE); -- 1.9.1