[cmaster-next] [PATCH 07/10] ldpd: use red-black trees to store 'l2vpn' elements
Renato Westphal
renato at opensourcerouting.org
Thu Dec 15 09:55:51 EST 2016
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 at 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
More information about the dev
mailing list