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