[cmaster-next] [PATCH 09/10] ldpd: use red-black trees to store 'l2vpn_pw' elements
Renato Westphal
renato at opensourcerouting.org
Thu Dec 15 09:55:53 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 | 49 +++++++++++++++++++++------------------
ldpd/lde.c | 8 +++----
ldpd/ldp_vty_conf.c | 22 +++++++++---------
ldpd/ldpd.c | 66 ++++++++++++++++++++++++++---------------------------
ldpd/ldpd.h | 11 +++++----
ldpd/ldpe.c | 8 +++----
6 files changed, 86 insertions(+), 78 deletions(-)
diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c
index 02f25e1..c1d0437 100644
--- a/ldpd/l2vpn.c
+++ b/ldpd/l2vpn.c
@@ -29,9 +29,11 @@
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 *);
+static __inline int l2vpn_pw_compare(struct l2vpn_pw *, struct l2vpn_pw *);
RB_GENERATE(l2vpn_head, l2vpn, entry, l2vpn_compare)
RB_GENERATE(l2vpn_if_head, l2vpn_if, entry, l2vpn_if_compare)
+RB_GENERATE(l2vpn_pw_head, l2vpn_pw, entry, l2vpn_pw_compare)
static __inline int
l2vpn_compare(struct l2vpn *a, struct l2vpn *b)
@@ -54,8 +56,8 @@ l2vpn_new(const char *name)
l2vpn->pw_type = DEFAULT_PW_TYPE;
RB_INIT(&l2vpn->if_tree);
- LIST_INIT(&l2vpn->pw_list);
- LIST_INIT(&l2vpn->pw_inactive_list);
+ RB_INIT(&l2vpn->pw_tree);
+ RB_INIT(&l2vpn->pw_inactive_tree);
return (l2vpn);
}
@@ -78,12 +80,12 @@ l2vpn_del(struct l2vpn *l2vpn)
RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif);
free(lif);
}
- while ((pw = LIST_FIRST(&l2vpn->pw_list)) != NULL) {
- LIST_REMOVE(pw, entry);
+ while ((pw = RB_ROOT(&l2vpn->pw_tree)) != NULL) {
+ RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw);
free(pw);
}
- while ((pw = LIST_FIRST(&l2vpn->pw_inactive_list)) != NULL) {
- LIST_REMOVE(pw, entry);
+ while ((pw = RB_ROOT(&l2vpn->pw_inactive_tree)) != NULL) {
+ RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
free(pw);
}
@@ -95,7 +97,7 @@ l2vpn_init(struct l2vpn *l2vpn)
{
struct l2vpn_pw *pw;
- LIST_FOREACH(pw, &l2vpn->pw_list, entry)
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree)
l2vpn_pw_init(pw);
}
@@ -104,7 +106,7 @@ l2vpn_exit(struct l2vpn *l2vpn)
{
struct l2vpn_pw *pw;
- LIST_FOREACH(pw, &l2vpn->pw_list, entry)
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree)
l2vpn_pw_exit(pw);
}
@@ -150,6 +152,11 @@ l2vpn_if_find_name(struct l2vpn *l2vpn, const char *ifname)
return (RB_FIND(l2vpn_if_head, &l2vpn->if_tree, &lif));
}
+static __inline int
+l2vpn_pw_compare(struct l2vpn_pw *a, struct l2vpn_pw *b)
+{
+ return (strcmp(a->ifname, b->ifname));
+}
struct l2vpn_pw *
l2vpn_pw_new(struct l2vpn *l2vpn, struct kif *kif)
@@ -171,10 +178,10 @@ l2vpn_pw_find(struct l2vpn *l2vpn, unsigned int ifindex)
{
struct l2vpn_pw *pw;
- LIST_FOREACH(pw, &l2vpn->pw_list, entry)
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree)
if (pw->ifindex == ifindex)
return (pw);
- LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry)
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree)
if (pw->ifindex == ifindex)
return (pw);
@@ -185,15 +192,13 @@ struct l2vpn_pw *
l2vpn_pw_find_name(struct l2vpn *l2vpn, const char *ifname)
{
struct l2vpn_pw *pw;
+ struct l2vpn_pw s;
- LIST_FOREACH(pw, &l2vpn->pw_list, entry)
- if (strcmp(pw->ifname, ifname) == 0)
- return (pw);
- LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry)
- if (strcmp(pw->ifname, ifname) == 0)
- return (pw);
-
- return (NULL);
+ strlcpy(s.ifname, ifname, sizeof(s.ifname));
+ pw = RB_FIND(l2vpn_pw_head, &l2vpn->pw_tree, &s);
+ if (pw)
+ return (pw);
+ return (RB_FIND(l2vpn_pw_head, &l2vpn->pw_inactive_tree, &s));
}
void
@@ -409,7 +414,7 @@ l2vpn_sync_pws(int af, union ldpd_addr *addr)
struct fec_nh *fnh;
RB_FOREACH(l2vpn, l2vpn_head, &ldeconf->l2vpn_tree) {
- LIST_FOREACH(pw, &l2vpn->pw_list, entry) {
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) {
if (af != pw->af || ldp_addrcmp(af, &pw->addr, addr))
continue;
@@ -438,7 +443,7 @@ l2vpn_pw_ctl(pid_t pid)
static struct ctl_pw pwctl;
RB_FOREACH(l2vpn, l2vpn_head, &ldeconf->l2vpn_tree)
- LIST_FOREACH(pw, &l2vpn->pw_list, entry) {
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) {
memset(&pwctl, 0, sizeof(pwctl));
strlcpy(pwctl.l2vpn_name, pw->l2vpn->name,
sizeof(pwctl.l2vpn_name));
@@ -517,7 +522,7 @@ ldpe_l2vpn_init(struct l2vpn *l2vpn)
{
struct l2vpn_pw *pw;
- LIST_FOREACH(pw, &l2vpn->pw_list, entry)
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree)
ldpe_l2vpn_pw_init(pw);
}
@@ -526,7 +531,7 @@ ldpe_l2vpn_exit(struct l2vpn *l2vpn)
{
struct l2vpn_pw *pw;
- LIST_FOREACH(pw, &l2vpn->pw_list, entry)
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree)
ldpe_l2vpn_pw_exit(pw);
}
diff --git a/ldpd/lde.c b/ldpd/lde.c
index 522650c..aa83ef0 100644
--- a/ldpd/lde.c
+++ b/ldpd/lde.c
@@ -511,8 +511,8 @@ lde_dispatch_parent(struct thread *thread)
memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn));
RB_INIT(&nl2vpn->if_tree);
- LIST_INIT(&nl2vpn->pw_list);
- LIST_INIT(&nl2vpn->pw_inactive_list);
+ RB_INIT(&nl2vpn->pw_tree);
+ RB_INIT(&nl2vpn->pw_inactive_tree);
RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn);
break;
@@ -530,7 +530,7 @@ lde_dispatch_parent(struct thread *thread)
memcpy(npw, imsg.data, sizeof(struct l2vpn_pw));
npw->l2vpn = nl2vpn;
- LIST_INSERT_HEAD(&nl2vpn->pw_list, npw, entry);
+ RB_INSERT(l2vpn_pw_head, &nl2vpn->pw_tree, npw);
break;
case IMSG_RECONF_L2VPN_IPW:
if ((npw = malloc(sizeof(struct l2vpn_pw))) == NULL)
@@ -538,7 +538,7 @@ lde_dispatch_parent(struct thread *thread)
memcpy(npw, imsg.data, sizeof(struct l2vpn_pw));
npw->l2vpn = nl2vpn;
- LIST_INSERT_HEAD(&nl2vpn->pw_inactive_list, npw, entry);
+ RB_INSERT(l2vpn_pw_head, &nl2vpn->pw_inactive_tree, npw);
break;
case IMSG_RECONF_END:
merge_config(ldeconf, nconf);
diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c
index b979642..e408abb 100644
--- a/ldpd/ldp_vty_conf.c
+++ b/ldpd/ldp_vty_conf.c
@@ -358,9 +358,9 @@ ldp_l2vpn_config_write(struct vty *vty)
vty_out(vty, " member interface %s%s", lif->ifname,
VTY_NEWLINE);
- LIST_FOREACH(pw, &l2vpn->pw_list, entry)
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree)
ldp_l2vpn_pw_config_write(vty, pw);
- LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry)
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree)
ldp_l2vpn_pw_config_write(vty, pw);
vty_out(vty, " !%s", VTY_NEWLINE);
@@ -1425,7 +1425,7 @@ ldp_vty_l2vpn_pseudowire(struct vty *vty, struct vty_arg *args[])
if (pw == NULL)
goto cancel;
- LIST_REMOVE(pw, entry);
+ RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
free(pw);
ldp_reload(vty_conf);
return (CMD_SUCCESS);
@@ -1451,7 +1451,7 @@ ldp_vty_l2vpn_pseudowire(struct vty *vty, struct vty_arg *args[])
pw = l2vpn_pw_new(l2vpn, &kif);
pw->flags = F_PW_STATUSTLV_CONF|F_PW_CWORD_CONF;
- LIST_INSERT_HEAD(&l2vpn->pw_inactive_list, pw, entry);
+ RB_INSERT(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
ldp_reload_ref(vty_conf, (void **)&pw);
VTY_PUSH_CONTEXT_SUB(LDP_PSEUDOWIRE_NODE, pw);
@@ -1720,12 +1720,12 @@ l2vpn_del_api(struct ldpd_conf *conf, struct l2vpn *l2vpn)
RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif);
free(lif);
}
- while ((pw = LIST_FIRST(&l2vpn->pw_list)) != NULL) {
- LIST_REMOVE(pw, entry);
+ while ((pw = RB_ROOT(&l2vpn->pw_tree)) != NULL) {
+ RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw);
free(pw);
}
- while ((pw = LIST_FIRST(&l2vpn->pw_inactive_list)) != NULL) {
- LIST_REMOVE(pw, entry);
+ while ((pw = RB_ROOT(&l2vpn->pw_inactive_tree)) != NULL) {
+ RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
free(pw);
}
RB_REMOVE(l2vpn_head, &conf->l2vpn_tree, l2vpn);
@@ -1784,13 +1784,13 @@ l2vpn_pw_new_api(struct ldpd_conf *conf, struct l2vpn *l2vpn,
pw = l2vpn_pw_new(l2vpn, &kif);
pw->flags = F_PW_STATUSTLV_CONF|F_PW_CWORD_CONF;
- LIST_INSERT_HEAD(&l2vpn->pw_inactive_list, pw, entry);
+ RB_INSERT(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
return (pw);
}
void
-l2vpn_pw_del_api(struct l2vpn_pw *pw)
+l2vpn_pw_del_api(struct l2vpn *l2vpn, struct l2vpn_pw *pw)
{
- LIST_REMOVE(pw, entry);
+ RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
free(pw);
}
diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c
index 0df9bbd..943129f 100644
--- a/ldpd/ldpd.c
+++ b/ldpd/ldpd.c
@@ -878,12 +878,12 @@ main_imsg_send_config(struct ldpd_conf *xconf)
sizeof(*lif)) == -1)
return (-1);
}
- LIST_FOREACH(pw, &l2vpn->pw_list, entry) {
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) {
if (main_imsg_compose_both(IMSG_RECONF_L2VPN_PW, pw,
sizeof(*pw)) == -1)
return (-1);
}
- LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry) {
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree) {
if (main_imsg_compose_both(IMSG_RECONF_L2VPN_IPW, pw,
sizeof(*pw)) == -1)
return (-1);
@@ -931,14 +931,14 @@ ldp_config_normalize(struct ldpd_conf *xconf, void **ref)
}
RB_FOREACH(l2vpn, l2vpn_head, &xconf->l2vpn_tree) {
- LIST_FOREACH(pw, &l2vpn->pw_list, entry) {
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) {
if (pw->flags & F_PW_STATIC_NBR_ADDR)
continue;
pw->af = AF_INET;
pw->addr.v4 = pw->lsr_id;
}
- LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry) {
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree) {
if (pw->flags & F_PW_STATIC_NBR_ADDR)
continue;
@@ -1054,8 +1054,8 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref)
RB_FOREACH(l2vpn, l2vpn_head, &conf->l2vpn_tree) {
COPY(xl, l2vpn);
RB_INIT(&xl->if_tree);
- LIST_INIT(&xl->pw_list);
- LIST_INIT(&xl->pw_inactive_list);
+ RB_INIT(&xl->pw_tree);
+ RB_INIT(&xl->pw_inactive_tree);
RB_INSERT(l2vpn_head, &xconf->l2vpn_tree, xl);
RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) {
@@ -1063,15 +1063,15 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref)
xf->l2vpn = xl;
RB_INSERT(l2vpn_if_head, &xl->if_tree, xf);
}
- LIST_FOREACH(pw, &l2vpn->pw_list, entry) {
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) {
COPY(xp, pw);
xp->l2vpn = xl;
- LIST_INSERT_HEAD(&xl->pw_list, xp, entry);
+ RB_INSERT(l2vpn_pw_head, &xl->pw_tree, xp);
}
- LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry) {
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree) {
COPY(xp, pw);
xp->l2vpn = xl;
- LIST_INSERT_HEAD(&xl->pw_inactive_list, xp, entry);
+ RB_INSERT(l2vpn_pw_head, &xl->pw_inactive_tree, xp);
}
}
#undef COPY
@@ -1484,9 +1484,9 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
case PROC_MAIN:
RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree)
QOBJ_UNREG (lif);
- LIST_FOREACH(pw, &l2vpn->pw_list, entry)
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree)
QOBJ_UNREG (pw);
- LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry)
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree)
QOBJ_UNREG (pw);
QOBJ_UNREG (l2vpn);
break;
@@ -1530,7 +1530,7 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void
struct l2vpn_pw *pw, *ptmp, *xp;
struct nbr *nbr;
int reset_nbr, reinstall_pwfec, reinstall_tnbr;
- LIST_HEAD(, l2vpn_pw) pw_aux_list;
+ struct l2vpn_pw_head pw_aux_list;
int previous_pw_type, previous_mtu;
previous_pw_type = l2vpn->pw_type;
@@ -1564,8 +1564,8 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void
}
/* merge active pseudowires */
- LIST_INIT(&pw_aux_list);
- LIST_FOREACH_SAFE(pw, &l2vpn->pw_list, entry, ptmp) {
+ RB_INIT(&pw_aux_list);
+ RB_FOREACH_SAFE(pw, l2vpn_pw_head, &l2vpn->pw_tree, ptmp) {
/* find deleted active pseudowires */
if ((xp = l2vpn_pw_find_name(xl, pw->ifname)) == NULL) {
switch (ldpd_process) {
@@ -1580,15 +1580,15 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void
break;
}
- LIST_REMOVE(pw, entry);
+ RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw);
free(pw);
}
}
- LIST_FOREACH_SAFE(xp, &xl->pw_list, entry, ptmp) {
+ RB_FOREACH_SAFE(xp, l2vpn_pw_head, &xl->pw_tree, ptmp) {
/* find new active pseudowires */
if ((pw = l2vpn_pw_find_name(l2vpn, xp->ifname)) == NULL) {
- LIST_REMOVE(xp, entry);
- LIST_INSERT_HEAD(&l2vpn->pw_list, xp, entry);
+ RB_REMOVE(l2vpn_pw_head, &xl->pw_tree, xp);
+ RB_INSERT(l2vpn_pw_head, &l2vpn->pw_tree, xp);
xp->l2vpn = l2vpn;
switch (ldpd_process) {
@@ -1644,8 +1644,8 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void
}
/* remove from active list */
- LIST_REMOVE(pw, entry);
- LIST_INSERT_HEAD(&pw_aux_list, pw, entry);
+ RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw);
+ RB_INSERT(l2vpn_pw_head, &pw_aux_list, pw);
}
if (ldpd_process == PROC_LDP_ENGINE) {
@@ -1689,27 +1689,27 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void
l2vpn->mtu = previous_mtu;
}
- LIST_REMOVE(xp, entry);
+ RB_REMOVE(l2vpn_pw_head, &xl->pw_tree, xp);
if (ref && *ref == xp)
*ref = pw;
free(xp);
}
/* merge inactive pseudowires */
- LIST_FOREACH_SAFE(pw, &l2vpn->pw_inactive_list, entry, ptmp) {
+ RB_FOREACH_SAFE(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree, ptmp) {
/* find deleted inactive pseudowires */
if ((xp = l2vpn_pw_find_name(xl, pw->ifname)) == NULL) {
- LIST_REMOVE(pw, entry);
+ RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
if (ldpd_process == PROC_MAIN)
QOBJ_UNREG (pw);
free(pw);
}
}
- LIST_FOREACH_SAFE(xp, &xl->pw_inactive_list, entry, ptmp) {
+ RB_FOREACH_SAFE(xp, l2vpn_pw_head, &xl->pw_inactive_tree, ptmp) {
/* find new inactive pseudowires */
if ((pw = l2vpn_pw_find_name(l2vpn, xp->ifname)) == NULL) {
- LIST_REMOVE(xp, entry);
- LIST_INSERT_HEAD(&l2vpn->pw_inactive_list, xp, entry);
+ RB_REMOVE(l2vpn_pw_head, &xl->pw_inactive_tree, xp);
+ RB_INSERT(l2vpn_pw_head, &l2vpn->pw_inactive_tree, xp);
xp->l2vpn = l2vpn;
if (ldpd_process == PROC_MAIN)
QOBJ_REG (xp, l2vpn_pw);
@@ -1728,8 +1728,8 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void
/* check if the pseudowire should be activated */
if (pw->lsr_id.s_addr != INADDR_ANY && pw->pwid != 0) {
/* remove from inactive list */
- LIST_REMOVE(pw, entry);
- LIST_INSERT_HEAD(&l2vpn->pw_list, pw, entry);
+ RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
+ RB_INSERT(l2vpn_pw_head, &l2vpn->pw_tree, pw);
switch (ldpd_process) {
case PROC_LDE_ENGINE:
@@ -1743,16 +1743,16 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void
}
}
- LIST_REMOVE(xp, entry);
+ RB_REMOVE(l2vpn_pw_head, &xl->pw_inactive_tree, xp);
if (ref && *ref == xp)
*ref = pw;
free(xp);
}
/* insert pseudowires that were disabled in the inactive list */
- LIST_FOREACH_SAFE(pw, &pw_aux_list, entry, ptmp) {
- LIST_REMOVE(pw, entry);
- LIST_INSERT_HEAD(&l2vpn->pw_inactive_list, pw, entry);
+ RB_FOREACH_SAFE(pw, l2vpn_pw_head, &pw_aux_list, ptmp) {
+ RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw);
+ RB_INSERT(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
}
l2vpn->pw_type = xl->pw_type;
diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h
index 0a21856..6836920 100644
--- a/ldpd/ldpd.h
+++ b/ldpd/ldpd.h
@@ -337,7 +337,7 @@ RB_PROTOTYPE(l2vpn_if_head, l2vpn_if, entry, l2vpn_if_compare);
DECLARE_QOBJ_TYPE(l2vpn_if)
struct l2vpn_pw {
- LIST_ENTRY(l2vpn_pw) entry;
+ RB_ENTRY(l2vpn_pw) entry;
struct l2vpn *l2vpn;
struct in_addr lsr_id;
int af;
@@ -351,6 +351,8 @@ struct l2vpn_pw {
uint8_t flags;
QOBJ_FIELDS
};
+RB_HEAD(l2vpn_pw_head, l2vpn_pw);
+RB_PROTOTYPE(l2vpn_pw_head, l2vpn_pw, entry, l2vpn_pw_compare);
DECLARE_QOBJ_TYPE(l2vpn_pw)
#define F_PW_STATUSTLV_CONF 0x01 /* status tlv configured */
#define F_PW_STATUSTLV 0x02 /* status tlv negotiated */
@@ -368,8 +370,8 @@ struct l2vpn {
char br_ifname[IF_NAMESIZE];
unsigned int br_ifindex;
struct l2vpn_if_head if_tree;
- LIST_HEAD(, l2vpn_pw) pw_list;
- LIST_HEAD(, l2vpn_pw) pw_inactive_list;
+ struct l2vpn_pw_head pw_tree;
+ struct l2vpn_pw_head pw_inactive_tree;
QOBJ_FIELDS
};
RB_HEAD(l2vpn_head, l2vpn);
@@ -657,7 +659,8 @@ 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);
+void l2vpn_pw_del_api(struct l2vpn *l2vpn,
+ struct l2vpn_pw *pw);
/* socket.c */
int ldp_create_socket(int, enum socket_type);
diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c
index 2a9fb4c..c3640d4 100644
--- a/ldpd/ldpe.c
+++ b/ldpd/ldpe.c
@@ -452,8 +452,8 @@ ldpe_dispatch_main(struct thread *thread)
memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn));
RB_INIT(&nl2vpn->if_tree);
- LIST_INIT(&nl2vpn->pw_list);
- LIST_INIT(&nl2vpn->pw_inactive_list);
+ RB_INIT(&nl2vpn->pw_tree);
+ RB_INIT(&nl2vpn->pw_inactive_tree);
RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn);
break;
@@ -471,7 +471,7 @@ ldpe_dispatch_main(struct thread *thread)
memcpy(npw, imsg.data, sizeof(struct l2vpn_pw));
npw->l2vpn = nl2vpn;
- LIST_INSERT_HEAD(&nl2vpn->pw_list, npw, entry);
+ RB_INSERT(l2vpn_pw_head, &nl2vpn->pw_tree, npw);
break;
case IMSG_RECONF_L2VPN_IPW:
if ((npw = malloc(sizeof(struct l2vpn_pw))) == NULL)
@@ -479,7 +479,7 @@ ldpe_dispatch_main(struct thread *thread)
memcpy(npw, imsg.data, sizeof(struct l2vpn_pw));
npw->l2vpn = nl2vpn;
- LIST_INSERT_HEAD(&nl2vpn->pw_inactive_list, npw, entry);
+ RB_INSERT(l2vpn_pw_head, &nl2vpn->pw_inactive_tree, npw);
break;
case IMSG_RECONF_END:
merge_config(leconf, nconf);
--
1.9.1
More information about the dev
mailing list