summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ldpd/adjacency.c120
-rw-r--r--ldpd/hello.c6
-rw-r--r--ldpd/interface.c45
-rw-r--r--ldpd/l2vpn.c108
-rw-r--r--ldpd/lde.c49
-rw-r--r--ldpd/lde.h9
-rw-r--r--ldpd/lde_lib.c18
-rw-r--r--ldpd/ldp_debug.c4
-rw-r--r--ldpd/ldp_vty_conf.c88
-rw-r--r--ldpd/ldpd.c212
-rw-r--r--ldpd/ldpd.h72
-rw-r--r--ldpd/ldpe.c56
-rw-r--r--ldpd/ldpe.h14
-rw-r--r--ldpd/neighbor.c29
14 files changed, 460 insertions, 370 deletions
diff --git a/ldpd/adjacency.c b/ldpd/adjacency.c
index d1a6facb30..2e7b43296a 100644
--- a/ldpd/adjacency.c
+++ b/ldpd/adjacency.c
@@ -25,12 +25,55 @@
#include "ldpe.h"
#include "log.h"
+static __inline int adj_compare(struct adj *, struct adj *);
static int adj_itimer(struct thread *);
-static void tnbr_del(struct tnbr *);
+static __inline int tnbr_compare(struct tnbr *, struct tnbr *);
+static void tnbr_del(struct ldpd_conf *, struct tnbr *);
static int tnbr_hello_timer(struct thread *);
static void tnbr_start_hello_timer(struct tnbr *);
static void tnbr_stop_hello_timer(struct tnbr *);
+RB_GENERATE(global_adj_head, adj, global_entry, adj_compare)
+RB_GENERATE(nbr_adj_head, adj, nbr_entry, adj_compare)
+RB_GENERATE(ia_adj_head, adj, ia_entry, adj_compare)
+RB_GENERATE(tnbr_head, tnbr, entry, tnbr_compare)
+
+static __inline int
+adj_compare(struct adj *a, struct adj *b)
+{
+ if (a->source.type < b->source.type)
+ return (-1);
+ if (a->source.type > b->source.type)
+ return (1);
+
+ switch (a->source.type) {
+ case HELLO_LINK:
+ if (strcmp(a->source.link.ia->iface->name,
+ b->source.link.ia->iface->name) < 0)
+ return (-1);
+ if (strcmp(a->source.link.ia->iface->name,
+ b->source.link.ia->iface->name) > 0)
+ return (1);
+ if (a->source.link.ia->af < b->source.link.ia->af)
+ return (-1);
+ if (a->source.link.ia->af > b->source.link.ia->af)
+ return (1);
+ return (ldp_addrcmp(a->source.link.ia->af,
+ &a->source.link.src_addr, &b->source.link.src_addr));
+ case HELLO_TARGETED:
+ if (a->source.target->af < b->source.target->af)
+ return (-1);
+ if (a->source.target->af > b->source.target->af)
+ return (1);
+ return (ldp_addrcmp(a->source.target->af,
+ &a->source.target->addr, &b->source.target->addr));
+ default:
+ fatalx("adj_get_af: unknown hello type");
+ }
+
+ return (0);
+}
+
struct adj *
adj_new(struct in_addr lsr_id, struct hello_source *source,
union ldpd_addr *addr)
@@ -48,11 +91,11 @@ adj_new(struct in_addr lsr_id, struct hello_source *source,
adj->source = *source;
adj->trans_addr = *addr;
- LIST_INSERT_HEAD(&global.adj_list, adj, global_entry);
+ RB_INSERT(global_adj_head, &global.adj_tree, adj);
switch (source->type) {
case HELLO_LINK:
- LIST_INSERT_HEAD(&source->link.ia->adj_list, adj, ia_entry);
+ RB_INSERT(ia_adj_head, &source->link.ia->adj_tree, adj);
break;
case HELLO_TARGETED:
source->target->adj = adj;
@@ -70,12 +113,12 @@ adj_del_single(struct adj *adj)
adj_stop_itimer(adj);
- LIST_REMOVE(adj, global_entry);
+ RB_REMOVE(global_adj_head, &global.adj_tree, adj);
if (adj->nbr)
- LIST_REMOVE(adj, nbr_entry);
+ RB_REMOVE(nbr_adj_head, &adj->nbr->adj_tree, adj);
switch (adj->source.type) {
case HELLO_LINK:
- LIST_REMOVE(adj, ia_entry);
+ RB_REMOVE(ia_adj_head, &adj->source.link.ia->adj_tree, adj);
break;
case HELLO_TARGETED:
adj->source.target->adj = NULL;
@@ -99,7 +142,7 @@ adj_del(struct adj *adj, uint32_t notif_status)
* then delete it.
*/
if (nbr && nbr_adj_count(nbr, nbr->af) == 0) {
- LIST_FOREACH_SAFE(adj, &nbr->adj_list, nbr_entry, atmp)
+ RB_FOREACH_SAFE(adj, nbr_adj_head, &nbr->adj_tree, atmp)
adj_del_single(adj);
session_shutdown(nbr, notif_status, 0, 0);
nbr_del(nbr);
@@ -109,31 +152,9 @@ adj_del(struct adj *adj, uint32_t notif_status)
struct adj *
adj_find(struct hello_source *source)
{
- struct adj *adj;
-
- LIST_FOREACH(adj, &global.adj_list, global_entry) {
- if (adj->source.type != source->type)
- continue;
-
- switch (source->type) {
- case HELLO_LINK:
- if (strcmp(source->link.ia->iface->name,
- adj->source.link.ia->iface->name))
- continue;
-
- if (ldp_addrcmp(source->link.ia->af,
- &adj->source.link.src_addr,
- &source->link.src_addr) == 0)
- return (adj);
- break;
- case HELLO_TARGETED:
- if (adj->source.target == source->target)
- return (adj);
- break;
- }
- }
-
- return (NULL);
+ struct adj adj;
+ adj.source = *source;
+ return (RB_FIND(global_adj_head, &global.adj_tree, &adj));
}
int
@@ -165,7 +186,7 @@ adj_itimer(struct thread *thread)
if (!(adj->source.target->flags & F_TNBR_CONFIGURED) &&
adj->source.target->pw_count == 0) {
/* remove dynamic targeted neighbor */
- tnbr_del(adj->source.target);
+ tnbr_del(leconf, adj->source.target);
return (0);
}
adj->source.target->adj = NULL;
@@ -192,6 +213,17 @@ adj_stop_itimer(struct adj *adj)
/* targeted neighbors */
+static __inline int
+tnbr_compare(struct tnbr *a, struct tnbr *b)
+{
+ if (a->af < b->af)
+ return (-1);
+ if (a->af > b->af)
+ return (1);
+
+ return (ldp_addrcmp(a->af, &a->addr, &b->addr));
+}
+
struct tnbr *
tnbr_new(int af, union ldpd_addr *addr)
{
@@ -208,34 +240,30 @@ tnbr_new(int af, union ldpd_addr *addr)
}
static void
-tnbr_del(struct tnbr *tnbr)
+tnbr_del(struct ldpd_conf *xconf, struct tnbr *tnbr)
{
tnbr_stop_hello_timer(tnbr);
if (tnbr->adj)
adj_del(tnbr->adj, S_SHUTDOWN);
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &xconf->tnbr_tree, tnbr);
free(tnbr);
}
struct tnbr *
tnbr_find(struct ldpd_conf *xconf, int af, union ldpd_addr *addr)
{
- struct tnbr *tnbr;
-
- LIST_FOREACH(tnbr, &xconf->tnbr_list, entry)
- if (af == tnbr->af &&
- ldp_addrcmp(af, addr, &tnbr->addr) == 0)
- return (tnbr);
-
- return (NULL);
+ struct tnbr tnbr;
+ tnbr.af = af;
+ tnbr.addr = *addr;
+ return (RB_FIND(tnbr_head, &xconf->tnbr_tree, &tnbr));
}
struct tnbr *
-tnbr_check(struct tnbr *tnbr)
+tnbr_check(struct ldpd_conf *xconf, struct tnbr *tnbr)
{
if (!(tnbr->flags & (F_TNBR_CONFIGURED|F_TNBR_DYNAMIC)) &&
tnbr->pw_count == 0) {
- tnbr_del(tnbr);
+ tnbr_del(xconf, tnbr);
return (NULL);
}
@@ -280,7 +308,7 @@ tnbr_update_all(int af)
struct tnbr *tnbr;
/* update targeted neighbors */
- LIST_FOREACH(tnbr, &leconf->tnbr_list, entry)
+ RB_FOREACH(tnbr, tnbr_head, &leconf->tnbr_tree)
if (tnbr->af == af || af == AF_UNSPEC)
tnbr_update(tnbr);
}
diff --git a/ldpd/hello.c b/ldpd/hello.c
index 755b25aa85..95be1d5111 100644
--- a/ldpd/hello.c
+++ b/ldpd/hello.c
@@ -261,7 +261,7 @@ recv_hello(struct in_addr lsr_id, struct ldp_msg *msg, int af,
if (tnbr && (tnbr->flags & F_TNBR_DYNAMIC) &&
!((flags & F_HELLO_REQ_TARG))) {
tnbr->flags &= ~F_TNBR_DYNAMIC;
- tnbr = tnbr_check(tnbr);
+ tnbr = tnbr_check(leconf, tnbr);
}
if (!tnbr) {
@@ -273,7 +273,7 @@ recv_hello(struct in_addr lsr_id, struct ldp_msg *msg, int af,
tnbr = tnbr_new(af, src);
tnbr->flags |= F_TNBR_DYNAMIC;
tnbr_update(tnbr);
- LIST_INSERT_HEAD(&leconf->tnbr_list, tnbr, entry);
+ RB_INSERT(tnbr_head, &leconf->tnbr_tree, tnbr);
}
source.type = HELLO_TARGETED;
@@ -364,7 +364,7 @@ recv_hello(struct in_addr lsr_id, struct ldp_msg *msg, int af,
adj = adj_new(lsr_id, &source, &trans_addr);
if (nbr) {
adj->nbr = nbr;
- LIST_INSERT_HEAD(&nbr->adj_list, adj, nbr_entry);
+ RB_INSERT(nbr_adj_head, &nbr->adj_tree, adj);
}
}
diff --git a/ldpd/interface.c b/ldpd/interface.c
index b6472fe5e8..8fea91b878 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)
{
@@ -57,30 +66,18 @@ if_new(struct kif *kif)
iface->ipv4.iface = iface;
iface->ipv4.enabled = 0;
iface->ipv4.state = IF_STA_DOWN;
- LIST_INIT(&iface->ipv4.adj_list);
+ RB_INIT(&iface->ipv4.adj_tree);
/* ipv6 */
iface->ipv6.af = AF_INET6;
iface->ipv6.iface = iface;
iface->ipv6.enabled = 0;
iface->ipv6.state = IF_STA_DOWN;
- LIST_INIT(&iface->ipv6.adj_list);
+ RB_INIT(&iface->ipv6.adj_tree);
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)
{
@@ -288,7 +293,7 @@ if_reset(struct iface *iface, int af)
ia = iface_af_get(iface, af);
if_stop_hello_timer(ia);
- while ((adj = LIST_FIRST(&ia->adj_list)) != NULL)
+ while ((adj = RB_ROOT(&ia->adj_tree)) != NULL)
adj_del(adj, S_SHUTDOWN);
/* try to cleanup */
@@ -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);
}
@@ -460,7 +465,7 @@ if_to_ctl(struct iface_af *ia)
ictl.uptime = 0;
ictl.adj_cnt = 0;
- LIST_FOREACH(adj, &ia->adj_list, ia_entry)
+ RB_FOREACH(adj, ia_adj_head, &ia->adj_tree)
ictl.adj_cnt++;
return (&ictl);
diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c
index 851ff77b73..c1d0437fba 100644
--- a/ldpd/l2vpn.c
+++ b/ldpd/l2vpn.c
@@ -26,7 +26,20 @@
#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 *);
+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)
+{
+ return (strcmp(a->name, b->name));
+}
struct l2vpn *
l2vpn_new(const char *name)
@@ -42,9 +55,9 @@ l2vpn_new(const char *name)
l2vpn->mtu = DEFAULT_L2VPN_MTU;
l2vpn->pw_type = DEFAULT_PW_TYPE;
- LIST_INIT(&l2vpn->if_list);
- LIST_INIT(&l2vpn->pw_list);
- LIST_INIT(&l2vpn->pw_inactive_list);
+ RB_INIT(&l2vpn->if_tree);
+ RB_INIT(&l2vpn->pw_tree);
+ RB_INIT(&l2vpn->pw_inactive_tree);
return (l2vpn);
}
@@ -52,13 +65,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
@@ -67,16 +76,16 @@ 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) {
- 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);
}
@@ -88,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);
}
@@ -97,10 +106,16 @@ 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);
}
+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)
{
@@ -122,7 +137,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);
@@ -132,15 +147,16 @@ 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));
}
+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)
@@ -162,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);
@@ -176,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
@@ -399,8 +413,8 @@ l2vpn_sync_pws(int af, union ldpd_addr *addr)
struct fec_node *fn;
struct fec_nh *fnh;
- LIST_FOREACH(l2vpn, &ldeconf->l2vpn_list, entry) {
- LIST_FOREACH(pw, &l2vpn->pw_list, entry) {
+ RB_FOREACH(l2vpn, l2vpn_head, &ldeconf->l2vpn_tree) {
+ RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) {
if (af != pw->af || ldp_addrcmp(af, &pw->addr, addr))
continue;
@@ -428,8 +442,8 @@ l2vpn_pw_ctl(pid_t pid)
struct l2vpn_pw *pw;
static struct ctl_pw pwctl;
- LIST_FOREACH(l2vpn, &ldeconf->l2vpn_list, entry)
- LIST_FOREACH(pw, &l2vpn->pw_list, entry) {
+ RB_FOREACH(l2vpn, l2vpn_head, &ldeconf->l2vpn_tree)
+ 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));
@@ -459,7 +473,7 @@ l2vpn_binding_ctl(pid_t pid)
fn = (struct fec_node *)f;
if (fn->local_label == NO_LABEL &&
- LIST_EMPTY(&fn->downstream))
+ RB_EMPTY(&fn->downstream))
continue;
memset(&pwctl, 0, sizeof(pwctl));
@@ -477,7 +491,7 @@ l2vpn_binding_ctl(pid_t pid)
} else
pwctl.local_label = NO_LABEL;
- LIST_FOREACH(me, &fn->downstream, entry)
+ RB_FOREACH(me, lde_map_head, &fn->downstream)
if (f->u.pwid.lsr_id.s_addr == me->nexthop->id.s_addr)
break;
@@ -508,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);
}
@@ -517,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);
}
@@ -530,7 +544,7 @@ ldpe_l2vpn_pw_init(struct l2vpn_pw *pw)
if (tnbr == NULL) {
tnbr = tnbr_new(pw->af, &pw->addr);
tnbr_update(tnbr);
- LIST_INSERT_HEAD(&leconf->tnbr_list, tnbr, entry);
+ RB_INSERT(tnbr_head, &leconf->tnbr_tree, tnbr);
}
tnbr->pw_count++;
@@ -544,6 +558,6 @@ ldpe_l2vpn_pw_exit(struct l2vpn_pw *pw)
tnbr = tnbr_find(leconf, pw->af, &pw->addr);
if (tnbr) {
tnbr->pw_count--;
- tnbr_check(tnbr);
+ tnbr_check(leconf, tnbr);
}
}
diff --git a/ldpd/lde.c b/ldpd/lde.c
index c2a5cf088c..0aa422c23a 100644
--- a/ldpd/lde.c
+++ b/ldpd/lde.c
@@ -45,12 +45,14 @@ static struct lde_nbr *lde_nbr_find(uint32_t);
static void lde_nbr_clear(void);
static void lde_nbr_addr_update(struct lde_nbr *,
struct lde_addr *, int);
+static __inline int lde_map_compare(struct lde_map *, struct lde_map *);
static void lde_map_free(void *);
static int lde_address_add(struct lde_nbr *, struct lde_addr *);
static int lde_address_del(struct lde_nbr *, struct lde_addr *);
static void lde_address_list_free(struct lde_nbr *);
RB_GENERATE(nbr_tree, lde_nbr, entry, lde_nbr_compare)
+RB_GENERATE(lde_map_head, lde_map, entry, lde_map_compare)
struct ldpd_conf *ldeconf;
struct nbr_tree lde_nbrs = RB_INITIALIZER(&lde_nbrs);
@@ -471,10 +473,10 @@ lde_dispatch_parent(struct thread *thread)
fatal(NULL);
memcpy(nconf, imsg.data, sizeof(struct ldpd_conf));
- LIST_INIT(&nconf->iface_list);
- LIST_INIT(&nconf->tnbr_list);
- LIST_INIT(&nconf->nbrp_list);
- LIST_INIT(&nconf->l2vpn_list);
+ RB_INIT(&nconf->iface_tree);
+ RB_INIT(&nconf->tnbr_tree);
+ RB_INIT(&nconf->nbrp_tree);
+ RB_INIT(&nconf->l2vpn_tree);
break;
case IMSG_RECONF_IFACE:
if ((niface = malloc(sizeof(struct iface))) == NULL)
@@ -482,37 +484,37 @@ lde_dispatch_parent(struct thread *thread)
memcpy(niface, imsg.data, sizeof(struct iface));
LIST_INIT(&niface->addr_list);
- LIST_INIT(&niface->ipv4.adj_list);
- LIST_INIT(&niface->ipv6.adj_list);
+ RB_INIT(&niface->ipv4.adj_tree);
+ RB_INIT(&niface->ipv6.adj_tree);
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)
fatal(NULL);
memcpy(ntnbr, imsg.data, sizeof(struct tnbr));
- LIST_INSERT_HEAD(&nconf->tnbr_list, ntnbr, entry);
+ RB_INSERT(tnbr_head, &nconf->tnbr_tree, ntnbr);
break;
case IMSG_RECONF_NBRP:
if ((nnbrp = malloc(sizeof(struct nbr_params))) == NULL)
fatal(NULL);
memcpy(nnbrp, imsg.data, sizeof(struct nbr_params));
- LIST_INSERT_HEAD(&nconf->nbrp_list, nnbrp, entry);
+ RB_INSERT(nbrp_head, &nconf->nbrp_tree, nnbrp);
break;
case IMSG_RECONF_L2VPN:
if ((nl2vpn = malloc(sizeof(struct l2vpn))) == NULL)
fatal(NULL);
memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn));
- LIST_INIT(&nl2vpn->if_list);
- LIST_INIT(&nl2vpn->pw_list);
- LIST_INIT(&nl2vpn->pw_inactive_list);
+ RB_INIT(&nl2vpn->if_tree);
+ RB_INIT(&nl2vpn->pw_tree);
+ RB_INIT(&nl2vpn->pw_inactive_tree);
- 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)
@@ -520,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)
@@ -528,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)
@@ -536,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);
@@ -1141,6 +1143,13 @@ lde_nbr_addr_update(struct lde_nbr *ln, struct lde_addr *lde_addr, int removed)
}
}
+static __inline int
+lde_map_compare(struct lde_map *a, struct lde_map *b)
+{
+ return (ldp_addrcmp(AF_INET, (union ldpd_addr *)&a->nexthop->id,
+ (union ldpd_addr *)&b->nexthop->id));
+}
+
struct lde_map *
lde_map_add(struct lde_nbr *ln, struct fec_node *fn, int sent)
{
@@ -1154,13 +1163,15 @@ lde_map_add(struct lde_nbr *ln, struct fec_node *fn, int sent)
me->nexthop = ln;
if (sent) {
- LIST_INSERT_HEAD(&fn->upstream, me, entry);
+ RB_INSERT(lde_map_head, &fn->upstream, me);
+ me->head = &fn->upstream;
if (fec_insert(&ln->sent_map, &me->fec))
log_warnx("failed to add %s to sent map",
log_fec(&me->fec));
/* XXX on failure more cleanup is needed */
} else {
- LIST_INSERT_HEAD(&fn->downstream, me, entry);
+ RB_INSERT(lde_map_head, &fn->downstream, me);
+ me->head = &fn->downstream;
if (fec_insert(&ln->recv_map, &me->fec))
log_warnx("failed to add %s to recv map",
log_fec(&me->fec));
@@ -1185,7 +1196,7 @@ lde_map_free(void *ptr)
{
struct lde_map *map = ptr;
- LIST_REMOVE(map, entry);
+ RB_REMOVE(lde_map_head, map->head, map);
free(map);
}
diff --git a/ldpd/lde.h b/ldpd/lde.h
index 5f5d37defb..fe90b2c852 100644
--- a/ldpd/lde.h
+++ b/ldpd/lde.h
@@ -62,10 +62,13 @@ struct lde_req {
/* mapping entries */
struct lde_map {
struct fec fec;
- LIST_ENTRY(lde_map) entry;
+ struct lde_map_head *head; /* fec_node's upstream/downstream */
+ RB_ENTRY(lde_map) entry;
struct lde_nbr *nexthop;
struct map map;
};
+RB_HEAD(lde_map_head, lde_map);
+RB_PROTOTYPE(lde_map_head, lde_map, entry, lde_map_cmp);
/* withdraw entries */
struct lde_wdraw {
@@ -112,8 +115,8 @@ struct fec_node {
struct fec fec;
LIST_HEAD(, fec_nh) nexthops; /* fib nexthops */
- LIST_HEAD(, lde_map) downstream; /* recv mappings */
- LIST_HEAD(, lde_map) upstream; /* sent mappings */
+ struct lde_map_head downstream; /* recv mappings */
+ struct lde_map_head upstream; /* sent mappings */
uint32_t local_label;
void *data; /* fec specific data */
diff --git a/ldpd/lde_lib.c b/ldpd/lde_lib.c
index 14ac592af9..df65edad1a 100644
--- a/ldpd/lde_lib.c
+++ b/ldpd/lde_lib.c
@@ -159,7 +159,7 @@ rt_dump(pid_t pid)
RB_FOREACH(f, fec_tree, &ft) {
fn = (struct fec_node *)f;
if (fn->local_label == NO_LABEL &&
- LIST_EMPTY(&fn->downstream))
+ RB_EMPTY(&fn->downstream))
continue;
rtctl.first = 1;
@@ -179,7 +179,7 @@ rt_dump(pid_t pid)
}
rtctl.local_label = fn->local_label;
- LIST_FOREACH(me, &fn->downstream, entry) {
+ RB_FOREACH(me, lde_map_head, &fn->downstream) {
rtctl.in_use = lde_nbr_is_nexthop(fn, me->nexthop);
rtctl.nexthop = me->nexthop->id;
rtctl.remote_label = me->map.label;
@@ -188,7 +188,7 @@ rt_dump(pid_t pid)
&rtctl, sizeof(rtctl));
rtctl.first = 0;
}
- if (LIST_EMPTY(&fn->downstream)) {
+ if (RB_EMPTY(&fn->downstream)) {
rtctl.in_use = 0;
rtctl.nexthop.s_addr = INADDR_ANY;
rtctl.remote_label = NO_LABEL;
@@ -224,10 +224,10 @@ fec_free(void *arg)
while ((fnh = LIST_FIRST(&fn->nexthops)))
fec_nh_del(fnh);
- if (!LIST_EMPTY(&fn->downstream))
+ if (!RB_EMPTY(&fn->downstream))
log_warnx("%s: fec %s downstream list not empty", __func__,
log_fec(&fn->fec));
- if (!LIST_EMPTY(&fn->upstream))
+ if (!RB_EMPTY(&fn->upstream))
log_warnx("%s: fec %s upstream list not empty", __func__,
log_fec(&fn->fec));
@@ -251,8 +251,8 @@ fec_add(struct fec *fec)
fn->fec = *fec;
fn->local_label = NO_LABEL;
- LIST_INIT(&fn->upstream);
- LIST_INIT(&fn->downstream);
+ RB_INIT(&fn->upstream);
+ RB_INIT(&fn->downstream);
LIST_INIT(&fn->nexthops);
if (fec_insert(&ft, &fn->fec))
@@ -774,8 +774,8 @@ lde_gc_timer(struct thread *thread)
fn = (struct fec_node *) fec;
if (!LIST_EMPTY(&fn->nexthops) ||
- !LIST_EMPTY(&fn->downstream) ||
- !LIST_EMPTY(&fn->upstream))
+ !RB_EMPTY(&fn->downstream) ||
+ !RB_EMPTY(&fn->upstream))
continue;
fec_remove(&ft, &fn->fec);
diff --git a/ldpd/ldp_debug.c b/ldpd/ldp_debug.c
index 15dd06a0f3..86b679d8aa 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 dd70365f3d..e408abb091 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;
@@ -213,7 +213,7 @@ ldp_af_config_write(struct vty *vty, int af, struct ldpd_conf *conf,
vty_out(vty, " session holdtime %u%s", af_conf->keepalive,
VTY_NEWLINE);
- LIST_FOREACH(tnbr, &ldpd_conf->tnbr_list, entry) {
+ RB_FOREACH(tnbr, tnbr_head, &ldpd_conf->tnbr_tree) {
if (tnbr->af == af) {
vty_out(vty, " !%s", VTY_NEWLINE);
vty_out(vty, " neighbor %s targeted%s",
@@ -265,7 +265,7 @@ ldp_config_write(struct vty *vty)
if (ldpd_conf->flags & F_LDPD_DS_CISCO_INTEROP)
vty_out(vty, " dual-stack cisco-interop%s", VTY_NEWLINE);
- LIST_FOREACH(nbrp, &ldpd_conf->nbrp_list, entry) {
+ RB_FOREACH(nbrp, nbrp_head, &ldpd_conf->nbrp_tree) {
if (nbrp->flags & F_NBRP_KEEPALIVE)
vty_out(vty, " neighbor %s session holdtime %u%s",
inet_ntoa(nbrp->lsr_id), nbrp->keepalive,
@@ -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)
@@ -354,13 +354,13 @@ 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);
- 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);
@@ -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))
@@ -740,7 +740,7 @@ ldp_vty_nbr_session_holdtime(struct vty *vty, struct vty_arg *args[])
} else {
if (nbrp == NULL) {
nbrp = nbr_params_new(lsr_id);
- LIST_INSERT_HEAD(&vty_conf->nbrp_list, nbrp, entry);
+ RB_INSERT(nbrp_head, &vty_conf->nbrp_tree, nbrp);
} else if (nbrp->keepalive == secs)
goto cancel;
@@ -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));
@@ -955,7 +955,7 @@ ldp_vty_neighbor_targeted(struct vty *vty, struct vty_arg *args[])
if (tnbr == NULL)
goto cancel;
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &vty_conf->tnbr_tree, tnbr);
free(tnbr);
ldp_reload(vty_conf);
return (CMD_SUCCESS);
@@ -966,7 +966,7 @@ ldp_vty_neighbor_targeted(struct vty *vty, struct vty_arg *args[])
tnbr = tnbr_new(af, &addr);
tnbr->flags |= F_TNBR_CONFIGURED;
- LIST_INSERT_HEAD(&vty_conf->tnbr_list, tnbr, entry);
+ RB_INSERT(tnbr_head, &vty_conf->tnbr_tree, tnbr);
ldp_reload(vty_conf);
@@ -1129,7 +1129,7 @@ ldp_vty_neighbor_password(struct vty *vty, struct vty_arg *args[])
} else {
if (nbrp == NULL) {
nbrp = nbr_params_new(lsr_id);
- LIST_INSERT_HEAD(&vty_conf->nbrp_list, nbrp, entry);
+ RB_INSERT(nbrp_head, &vty_conf->nbrp_tree, nbrp);
} else if (nbrp->auth.method == AUTH_MD5SIG &&
strcmp(nbrp->auth.md5key, password_str) == 0)
goto cancel;
@@ -1195,7 +1195,7 @@ ldp_vty_neighbor_ttl_security(struct vty *vty, struct vty_arg *args[])
} else {
if (nbrp == NULL) {
nbrp = nbr_params_new(lsr_id);
- LIST_INSERT_HEAD(&vty_conf->nbrp_list, nbrp, entry);
+ RB_INSERT(nbrp_head, &vty_conf->nbrp_tree, nbrp);
}
nbrp->flags |= F_NBRP_GTSM;
@@ -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);
@@ -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);
@@ -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);
@@ -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);
}
@@ -1665,14 +1665,14 @@ tnbr_new_api(struct ldpd_conf *conf, int af, union ldpd_addr *addr)
tnbr = tnbr_new(af, addr);
tnbr->flags |= F_TNBR_CONFIGURED;
- LIST_INSERT_HEAD(&conf->tnbr_list, tnbr, entry);
+ RB_INSERT(tnbr_head, &conf->tnbr_tree, tnbr);
return (tnbr);
}
void
-tnbr_del_api(struct tnbr *tnbr)
+tnbr_del_api(struct ldpd_conf *conf, struct tnbr *tnbr)
{
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr);
free(tnbr);
}
@@ -1685,14 +1685,14 @@ nbrp_new_api(struct ldpd_conf *conf, struct in_addr lsr_id)
return (NULL);
nbrp = nbr_params_new(lsr_id);
- LIST_INSERT_HEAD(&conf->nbrp_list, nbrp, entry);
+ RB_INSERT(nbrp_head, &conf->nbrp_tree, nbrp);
return (nbrp);
}
void
-nbrp_del_api(struct nbr_params *nbrp)
+nbrp_del_api(struct ldpd_conf *conf, struct nbr_params *nbrp)
{
- LIST_REMOVE(nbrp, entry);
+ RB_REMOVE(nbrp_head, &conf->nbrp_tree, nbrp);
free(nbrp);
}
@@ -1706,29 +1706,29 @@ 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;
- 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) {
- 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);
}
- LIST_REMOVE(l2vpn, entry);
+ RB_REMOVE(l2vpn_head, &conf->l2vpn_tree, l2vpn);
free(l2vpn);
}
@@ -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);
}
@@ -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 8a9847bdfd..391e013376 100644
--- a/ldpd/ldpd.c
+++ b/ldpd/ldpd.c
@@ -850,40 +850,40 @@ 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);
}
- LIST_FOREACH(tnbr, &xconf->tnbr_list, entry) {
+ RB_FOREACH(tnbr, tnbr_head, &xconf->tnbr_tree) {
if (main_imsg_compose_both(IMSG_RECONF_TNBR, tnbr,
sizeof(*tnbr)) == -1)
return (-1);
}
- LIST_FOREACH(nbrp, &xconf->nbrp_list, entry) {
+ RB_FOREACH(nbrp, nbrp_head, &xconf->nbrp_tree) {
if (main_imsg_compose_both(IMSG_RECONF_NBRP, nbrp,
sizeof(*nbrp)) == -1)
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);
- 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);
}
- 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);
@@ -930,15 +930,15 @@ ldp_config_normalize(struct ldpd_conf *xconf, void **ref)
ldp_config_reset_af(xconf, AF_INET6, ref);
}
- LIST_FOREACH(l2vpn, &xconf->l2vpn_list, entry) {
- LIST_FOREACH(pw, &l2vpn->pw_list, entry) {
+ RB_FOREACH(l2vpn, l2vpn_head, &xconf->l2vpn_tree) {
+ 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;
@@ -954,17 +954,17 @@ 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);
}
- while ((nbrp = LIST_FIRST(&conf->nbrp_list)) != NULL) {
+ while ((nbrp = RB_ROOT(&conf->nbrp_tree)) != NULL) {
if (ref && *ref == nbrp)
*ref = NULL;
- LIST_REMOVE(nbrp, entry);
+ RB_REMOVE(nbrp_head, &conf->nbrp_tree, nbrp);
free(nbrp);
}
@@ -987,18 +987,18 @@ 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;
}
- LIST_FOREACH_SAFE(tnbr, &conf->tnbr_list, entry, ttmp) {
+ RB_FOREACH_SAFE(tnbr, tnbr_head, &conf->tnbr_tree, ttmp) {
if (tnbr->af != af)
continue;
if (ref && *ref == tnbr)
*ref = NULL;
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr);
free(tnbr);
}
@@ -1032,46 +1032,46 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref)
} while (0)
COPY(xconf, conf);
- LIST_INIT(&xconf->iface_list);
- LIST_INIT(&xconf->tnbr_list);
- LIST_INIT(&xconf->nbrp_list);
- LIST_INIT(&xconf->l2vpn_list);
+ RB_INIT(&xconf->iface_tree);
+ RB_INIT(&xconf->tnbr_tree);
+ RB_INIT(&xconf->nbrp_tree);
+ RB_INIT(&xconf->l2vpn_tree);
- 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) {
+ RB_FOREACH(tnbr, tnbr_head, &conf->tnbr_tree) {
COPY(xt, tnbr);
- LIST_INSERT_HEAD(&xconf->tnbr_list, xt, entry);
+ RB_INSERT(tnbr_head, &xconf->tnbr_tree, xt);
}
- LIST_FOREACH(nbrp, &conf->nbrp_list, entry) {
+ RB_FOREACH(nbrp, nbrp_head, &conf->nbrp_tree) {
COPY(xn, nbrp);
- LIST_INSERT_HEAD(&xconf->nbrp_list, xn, entry);
+ 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_INIT(&xl->if_tree);
+ RB_INIT(&xl->pw_tree);
+ RB_INIT(&xl->pw_inactive_tree);
+ 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) {
+ 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
@@ -1093,20 +1093,20 @@ 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) {
- LIST_REMOVE(tnbr, entry);
+ while ((tnbr = RB_ROOT(&xconf->tnbr_tree)) != NULL) {
+ RB_REMOVE(tnbr_head, &xconf->tnbr_tree, tnbr);
free(tnbr);
}
- while ((nbrp = LIST_FIRST(&xconf->nbrp_list)) != NULL) {
- LIST_REMOVE(nbrp, entry);
+ while ((nbrp = RB_ROOT(&xconf->nbrp_tree)) != NULL) {
+ 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);
}
@@ -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);
@@ -1295,7 +1295,7 @@ merge_tnbrs(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
{
struct tnbr *tnbr, *ttmp, *xt;
- LIST_FOREACH_SAFE(tnbr, &conf->tnbr_list, entry, ttmp) {
+ RB_FOREACH_SAFE(tnbr, tnbr_head, &conf->tnbr_tree, ttmp) {
if (!(tnbr->flags & F_TNBR_CONFIGURED))
continue;
@@ -1303,26 +1303,26 @@ merge_tnbrs(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
if ((xt = tnbr_find(xconf, tnbr->af, &tnbr->addr)) == NULL) {
switch (ldpd_process) {
case PROC_LDE_ENGINE:
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr);
free(tnbr);
break;
case PROC_LDP_ENGINE:
tnbr->flags &= ~F_TNBR_CONFIGURED;
- tnbr_check(tnbr);
+ tnbr_check(conf, tnbr);
break;
case PROC_MAIN:
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr);
QOBJ_UNREG (tnbr);
free(tnbr);
break;
}
}
}
- LIST_FOREACH_SAFE(xt, &xconf->tnbr_list, entry, ttmp) {
+ RB_FOREACH_SAFE(xt, tnbr_head, &xconf->tnbr_tree, ttmp) {
/* find new tnbrs */
if ((tnbr = tnbr_find(conf, xt->af, &xt->addr)) == NULL) {
- LIST_REMOVE(xt, entry);
- LIST_INSERT_HEAD(&conf->tnbr_list, xt, entry);
+ RB_REMOVE(tnbr_head, &xconf->tnbr_tree, xt);
+ RB_INSERT(tnbr_head, &conf->tnbr_tree, xt);
switch (ldpd_process) {
case PROC_LDE_ENGINE:
@@ -1340,7 +1340,7 @@ merge_tnbrs(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
/* update existing tnbrs */
if (!(tnbr->flags & F_TNBR_CONFIGURED))
tnbr->flags |= F_TNBR_CONFIGURED;
- LIST_REMOVE(xt, entry);
+ RB_REMOVE(tnbr_head, &xconf->tnbr_tree, xt);
if (ref && *ref == xt)
*ref = tnbr;
free(xt);
@@ -1354,7 +1354,7 @@ merge_nbrps(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
struct nbr *nbr;
int nbrp_changed;
- LIST_FOREACH_SAFE(nbrp, &conf->nbrp_list, entry, ntmp) {
+ RB_FOREACH_SAFE(nbrp, nbrp_head, &conf->nbrp_tree, ntmp) {
/* find deleted nbrps */
if ((xn = nbr_params_find(xconf, nbrp->lsr_id)) == NULL) {
switch (ldpd_process) {
@@ -1380,15 +1380,15 @@ merge_nbrps(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
QOBJ_UNREG (nbrp);
break;
}
- LIST_REMOVE(nbrp, entry);
+ RB_REMOVE(nbrp_head, &conf->nbrp_tree, nbrp);
free(nbrp);
}
}
- LIST_FOREACH_SAFE(xn, &xconf->nbrp_list, entry, ntmp) {
+ RB_FOREACH_SAFE(xn, nbrp_head, &xconf->nbrp_tree, ntmp) {
/* find new nbrps */
if ((nbrp = nbr_params_find(conf, xn->lsr_id)) == NULL) {
- LIST_REMOVE(xn, entry);
- LIST_INSERT_HEAD(&conf->nbrp_list, xn, entry);
+ RB_REMOVE(nbrp_head, &xconf->nbrp_tree, xn);
+ RB_INSERT(nbrp_head, &conf->nbrp_tree, xn);
switch (ldpd_process) {
case PROC_LDE_ENGINE:
@@ -1455,7 +1455,7 @@ merge_nbrps(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
nbr_establish_connection(nbr);
}
}
- LIST_REMOVE(xn, entry);
+ RB_REMOVE(nbrp_head, &xconf->nbrp_tree, xn);
if (ref && *ref == xn)
*ref = nbrp;
free(xn);
@@ -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:
@@ -1482,11 +1482,11 @@ 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)
+ 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;
@@ -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);
@@ -1530,42 +1530,42 @@ 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;
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);
}
/* 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;
@@ -1770,10 +1770,10 @@ config_new_empty(void)
if (xconf == NULL)
fatal(NULL);
- LIST_INIT(&xconf->iface_list);
- LIST_INIT(&xconf->tnbr_list);
- LIST_INIT(&xconf->nbrp_list);
- LIST_INIT(&xconf->l2vpn_list);
+ RB_INIT(&xconf->iface_tree);
+ RB_INIT(&xconf->tnbr_tree);
+ RB_INIT(&xconf->nbrp_tree);
+ RB_INIT(&xconf->l2vpn_tree);
return (xconf);
}
diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h
index 630b192489..4d575597ae 100644
--- a/ldpd/ldpd.h
+++ b/ldpd/ldpd.h
@@ -196,7 +196,10 @@ enum nbr_action {
NBR_ACT_CLOSE_SESSION
};
-TAILQ_HEAD(mapping_head, mapping_entry);
+/* forward declarations */
+RB_HEAD(global_adj_head, adj);
+RB_HEAD(nbr_adj_head, adj);
+RB_HEAD(ia_adj_head, adj);
struct map {
uint8_t type;
@@ -256,7 +259,7 @@ struct iface_af {
int af;
int enabled;
int state;
- LIST_HEAD(, adj) adj_list;
+ struct ia_adj_head adj_tree;
time_t uptime;
struct thread *hello_timer;
uint16_t hello_holdtime;
@@ -264,7 +267,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,11 +278,13 @@ 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 */
struct tnbr {
- LIST_ENTRY(tnbr) entry;
+ RB_ENTRY(tnbr) entry;
struct thread *hello_timer;
struct adj *adj;
int af;
@@ -289,6 +294,8 @@ struct tnbr {
uint8_t flags;
QOBJ_FIELDS
};
+RB_HEAD(tnbr_head, tnbr);
+RB_PROTOTYPE(tnbr_head, tnbr, entry, tnbr_compare);
DECLARE_QOBJ_TYPE(tnbr)
#define F_TNBR_CONFIGURED 0x01
#define F_TNBR_DYNAMIC 0x02
@@ -300,7 +307,7 @@ enum auth_method {
/* neighbor specific parameters */
struct nbr_params {
- LIST_ENTRY(nbr_params) entry;
+ RB_ENTRY(nbr_params) entry;
struct in_addr lsr_id;
uint16_t keepalive;
int gtsm_enabled;
@@ -313,23 +320,27 @@ struct nbr_params {
uint8_t flags;
QOBJ_FIELDS
};
+RB_HEAD(nbrp_head, nbr_params);
+RB_PROTOTYPE(nbrp_head, nbr_params, entry, nbr_params_compare);
DECLARE_QOBJ_TYPE(nbr_params)
#define F_NBRP_KEEPALIVE 0x01
#define F_NBRP_GTSM 0x02
#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 {
- LIST_ENTRY(l2vpn_pw) entry;
+ RB_ENTRY(l2vpn_pw) entry;
struct l2vpn *l2vpn;
struct in_addr lsr_id;
int af;
@@ -343,6 +354,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 */
@@ -352,18 +365,20 @@ 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;
int mtu;
char br_ifname[IF_NAMESIZE];
unsigned int br_ifindex;
- LIST_HEAD(, l2vpn_if) if_list;
- LIST_HEAD(, l2vpn_pw) pw_list;
- LIST_HEAD(, l2vpn_pw) pw_inactive_list;
+ struct l2vpn_if_head if_tree;
+ struct l2vpn_pw_head pw_tree;
+ struct l2vpn_pw_head pw_inactive_tree;
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
@@ -404,10 +419,10 @@ struct ldpd_conf {
struct in_addr rtr_id;
struct ldpd_af_conf ipv4;
struct ldpd_af_conf ipv6;
- LIST_HEAD(, iface) iface_list;
- LIST_HEAD(, tnbr) tnbr_list;
- LIST_HEAD(, nbr_params) nbrp_list;
- LIST_HEAD(, l2vpn) l2vpn_list;
+ struct iface_head iface_tree;
+ struct tnbr_head tnbr_tree;
+ struct nbrp_head nbrp_tree;
+ struct l2vpn_head l2vpn_tree;
uint16_t lhello_holdtime;
uint16_t lhello_interval;
uint16_t thello_holdtime;
@@ -438,7 +453,7 @@ struct ldpd_global {
uint32_t conf_seqnum;
int pfkeysock;
struct if_addr_head addr_list;
- LIST_HEAD(, adj) adj_list;
+ struct global_adj_head adj_tree;
struct in_addr mcast_addr_v4;
struct in6_addr mcast_addr_v6;
TAILQ_HEAD(, pending_conn) pending_conns;
@@ -627,23 +642,28 @@ 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);
-struct tnbr *tnbr_new_api(struct ldpd_conf *cfg, int af,
+void iface_del_api(struct ldpd_conf *conf,
+ struct iface *iface);
+struct tnbr *tnbr_new_api(struct ldpd_conf *conf, int af,
union ldpd_addr *addr);
-void tnbr_del_api(struct tnbr *tnbr);
-struct nbr_params *nbrp_new_api(struct ldpd_conf *cfg,
+void tnbr_del_api(struct ldpd_conf *conf, struct tnbr *tnbr);
+struct nbr_params *nbrp_new_api(struct ldpd_conf *conf,
struct in_addr lsr_id);
-void nbrp_del_api(struct nbr_params *nbrp);
-struct l2vpn *l2vpn_new_api(struct ldpd_conf *cfg, const char *name);
-void l2vpn_del_api(struct l2vpn *l2vpn);
+void nbrp_del_api(struct ldpd_conf *conf,
+ struct nbr_params *nbrp);
+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);
+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 37a3d79a28..1a60af8f41 100644
--- a/ldpd/ldpe.c
+++ b/ldpd/ldpe.c
@@ -111,7 +111,7 @@ ldpe(const char *user, const char *group)
ldpd_process = PROC_LDP_ENGINE;
LIST_INIT(&global.addr_list);
- LIST_INIT(&global.adj_list);
+ RB_INIT(&global.adj_tree);
TAILQ_INIT(&global.pending_conns);
if (inet_pton(AF_INET, AllRouters_v4, &global.mcast_addr_v4) != 1)
fatal("inet_pton");
@@ -209,7 +209,7 @@ ldpe_shutdown(void)
LIST_REMOVE(if_addr, entry);
free(if_addr);
}
- while ((adj = LIST_FIRST(&global.adj_list)) != NULL)
+ while ((adj = RB_ROOT(&global.adj_tree)) != NULL)
adj_del(adj, S_SHUTDOWN);
/* clean up */
@@ -414,10 +414,10 @@ ldpe_dispatch_main(struct thread *thread)
fatal(NULL);
memcpy(nconf, imsg.data, sizeof(struct ldpd_conf));
- LIST_INIT(&nconf->iface_list);
- LIST_INIT(&nconf->tnbr_list);
- LIST_INIT(&nconf->nbrp_list);
- LIST_INIT(&nconf->l2vpn_list);
+ RB_INIT(&nconf->iface_tree);
+ RB_INIT(&nconf->tnbr_tree);
+ RB_INIT(&nconf->nbrp_tree);
+ RB_INIT(&nconf->l2vpn_tree);
break;
case IMSG_RECONF_IFACE:
if ((niface = malloc(sizeof(struct iface))) == NULL)
@@ -425,37 +425,37 @@ ldpe_dispatch_main(struct thread *thread)
memcpy(niface, imsg.data, sizeof(struct iface));
LIST_INIT(&niface->addr_list);
- LIST_INIT(&niface->ipv4.adj_list);
- LIST_INIT(&niface->ipv6.adj_list);
+ RB_INIT(&niface->ipv4.adj_tree);
+ RB_INIT(&niface->ipv6.adj_tree);
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)
fatal(NULL);
memcpy(ntnbr, imsg.data, sizeof(struct tnbr));
- LIST_INSERT_HEAD(&nconf->tnbr_list, ntnbr, entry);
+ RB_INSERT(tnbr_head, &nconf->tnbr_tree, ntnbr);
break;
case IMSG_RECONF_NBRP:
if ((nnbrp = malloc(sizeof(struct nbr_params))) == NULL)
fatal(NULL);
memcpy(nnbrp, imsg.data, sizeof(struct nbr_params));
- LIST_INSERT_HEAD(&nconf->nbrp_list, nnbrp, entry);
+ RB_INSERT(nbrp_head, &nconf->nbrp_tree, nnbrp);
break;
case IMSG_RECONF_L2VPN:
if ((nl2vpn = malloc(sizeof(struct l2vpn))) == NULL)
fatal(NULL);
memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn));
- LIST_INIT(&nl2vpn->if_list);
- LIST_INIT(&nl2vpn->pw_list);
- LIST_INIT(&nl2vpn->pw_inactive_list);
+ RB_INIT(&nl2vpn->if_tree);
+ RB_INIT(&nl2vpn->pw_tree);
+ RB_INIT(&nl2vpn->pw_inactive_tree);
- 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)
@@ -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)
@@ -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);
@@ -743,12 +743,12 @@ ldpe_remove_dynamic_tnbrs(int af)
{
struct tnbr *tnbr, *safe;
- LIST_FOREACH_SAFE(tnbr, &leconf->tnbr_list, entry, safe) {
+ RB_FOREACH_SAFE(tnbr, tnbr_head, &leconf->tnbr_tree, safe) {
if (tnbr->af != af)
continue;
tnbr->flags &= ~F_TNBR_DYNAMIC;
- tnbr_check(tnbr);
+ tnbr_check(leconf, tnbr);
}
}
@@ -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);
@@ -814,25 +814,25 @@ ldpe_adj_ctl(struct ctl_conn *c)
continue;
strlcpy(ictl.name, iface->name, sizeof(ictl.name));
- if (LIST_EMPTY(&iface->ipv4.adj_list) &&
- LIST_EMPTY(&iface->ipv6.adj_list))
+ if (RB_EMPTY(&iface->ipv4.adj_tree) &&
+ RB_EMPTY(&iface->ipv6.adj_tree))
ictl.no_adj = 1;
imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISC_IFACE, 0, 0,
-1, &ictl, sizeof(ictl));
- LIST_FOREACH(adj, &iface->ipv4.adj_list, ia_entry) {
+ RB_FOREACH(adj, ia_adj_head, &iface->ipv4.adj_tree) {
actl = adj_to_ctl(adj);
imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISC_ADJ,
0, 0, -1, actl, sizeof(struct ctl_adj));
}
- LIST_FOREACH(adj, &iface->ipv6.adj_list, ia_entry) {
+ RB_FOREACH(adj, ia_adj_head, &iface->ipv6.adj_tree) {
actl = adj_to_ctl(adj);
imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISC_ADJ,
0, 0, -1, actl, sizeof(struct ctl_adj));
}
}
- LIST_FOREACH(tnbr, &leconf->tnbr_list, entry) {
+ RB_FOREACH(tnbr, tnbr_head, &leconf->tnbr_tree) {
memset(&tctl, 0, sizeof(tctl));
tctl.af = tnbr->af;
tctl.addr = tnbr->addr;
@@ -869,7 +869,7 @@ ldpe_nbr_ctl(struct ctl_conn *c)
imsg_compose_event(&c->iev, IMSG_CTL_SHOW_NBR, 0, 0, -1, nctl,
sizeof(struct ctl_nbr));
- LIST_FOREACH(adj, &nbr->adj_list, nbr_entry) {
+ RB_FOREACH(adj, nbr_adj_head, &nbr->adj_tree) {
actl = adj_to_ctl(adj);
imsg_compose_event(&c->iev, IMSG_CTL_SHOW_NBR_DISC,
0, 0, -1, actl, sizeof(struct ctl_adj));
diff --git a/ldpd/ldpe.h b/ldpd/ldpe.h
index aab1a7fd9b..81add63836 100644
--- a/ldpd/ldpe.h
+++ b/ldpd/ldpe.h
@@ -32,6 +32,9 @@
#define min(x,y) ((x) <= (y) ? (x) : (y))
#define max(x,y) ((x) > (y) ? (x) : (y))
+/* forward declarations */
+TAILQ_HEAD(mapping_head, mapping_entry);
+
struct hello_source {
enum hello_type type;
struct {
@@ -42,9 +45,7 @@ struct hello_source {
};
struct adj {
- LIST_ENTRY(adj) global_entry;
- LIST_ENTRY(adj) nbr_entry;
- LIST_ENTRY(adj) ia_entry;
+ RB_ENTRY(adj) global_entry, nbr_entry, ia_entry;
struct in_addr lsr_id;
struct nbr *nbr;
int ds_tlv;
@@ -53,6 +54,9 @@ struct adj {
uint16_t holdtime;
union ldpd_addr trans_addr;
};
+RB_PROTOTYPE(global_adj_head, adj, global_entry, adj_compare)
+RB_PROTOTYPE(nbr_adj_head, adj, nbr_entry, adj_compare)
+RB_PROTOTYPE(ia_adj_head, adj, ia_entry, adj_compare)
struct tcp_conn {
struct nbr *nbr;
@@ -67,7 +71,7 @@ struct tcp_conn {
struct nbr {
RB_ENTRY(nbr) id_tree, addr_tree, pid_tree;
struct tcp_conn *tcp;
- LIST_HEAD(, adj) adj_list; /* adjacencies */
+ struct nbr_adj_head adj_tree; /* adjacencies */
struct thread *ev_connect;
struct thread *keepalive_timer;
struct thread *keepalive_timeout;
@@ -225,7 +229,7 @@ void adj_start_itimer(struct adj *);
void adj_stop_itimer(struct adj *);
struct tnbr *tnbr_new(int, union ldpd_addr *);
struct tnbr *tnbr_find(struct ldpd_conf *, int, union ldpd_addr *);
-struct tnbr *tnbr_check(struct tnbr *);
+struct tnbr *tnbr_check(struct ldpd_conf *, struct tnbr *);
void tnbr_update(struct tnbr *);
void tnbr_update_all(int);
uint16_t tnbr_get_hello_holdtime(struct tnbr *);
diff --git a/ldpd/neighbor.c b/ldpd/neighbor.c
index 8376a01549..d24ceb1229 100644
--- a/ldpd/neighbor.c
+++ b/ldpd/neighbor.c
@@ -39,10 +39,13 @@ static void nbr_start_itimeout(struct nbr *);
static int nbr_idtimer(struct thread *);
static int nbr_act_session_operational(struct nbr *);
static void nbr_send_labelmappings(struct nbr *);
+static __inline int nbr_params_compare(struct nbr_params *,
+ struct nbr_params *);
RB_GENERATE(nbr_id_head, nbr, id_tree, nbr_id_compare)
RB_GENERATE(nbr_addr_head, nbr, addr_tree, nbr_addr_compare)
RB_GENERATE(nbr_pid_head, nbr, pid_tree, nbr_pid_compare)
+RB_GENERATE(nbrp_head, nbr_params, entry, nbr_params_compare)
struct {
int state;
@@ -226,7 +229,7 @@ nbr_new(struct in_addr id, int af, int ds_tlv, union ldpd_addr *addr,
if ((nbr = calloc(1, sizeof(*nbr))) == NULL)
fatal(__func__);
- LIST_INIT(&nbr->adj_list);
+ RB_INIT(&nbr->adj_tree);
nbr->state = NBR_STA_PRESENT;
nbr->peerid = 0;
nbr->af = af;
@@ -241,10 +244,10 @@ nbr_new(struct in_addr id, int af, int ds_tlv, union ldpd_addr *addr,
nbr->raddr_scope = scope_id;
nbr->conf_seqnum = 0;
- LIST_FOREACH(adj, &global.adj_list, global_entry) {
+ RB_FOREACH(adj, global_adj_head, &global.adj_tree) {
if (adj->lsr_id.s_addr == nbr->id.s_addr) {
adj->nbr = nbr;
- LIST_INSERT_HEAD(&nbr->adj_list, adj, nbr_entry);
+ RB_INSERT(nbr_adj_head, &nbr->adj_tree, adj);
}
}
@@ -363,7 +366,7 @@ nbr_adj_count(struct nbr *nbr, int af)
struct adj *adj;
int total = 0;
- LIST_FOREACH(adj, &nbr->adj_list, nbr_entry)
+ RB_FOREACH(adj, nbr_adj_head, &nbr->adj_tree)
if (adj_get_af(adj) == af)
total++;
@@ -621,7 +624,7 @@ nbr_establish_connection(struct nbr *nbr)
* Send an extra hello to guarantee that the remote peer has formed
* an adjacency as well.
*/
- LIST_FOREACH(adj, &nbr->adj_list, nbr_entry)
+ RB_FOREACH(adj, nbr_adj_head, &nbr->adj_tree)
send_hello(adj->source.type, adj->source.link.ia,
adj->source.target);
@@ -752,6 +755,12 @@ nbr_send_labelmappings(struct nbr *nbr)
NULL, 0);
}
+static __inline int
+nbr_params_compare(struct nbr_params *a, struct nbr_params *b)
+{
+ return (ntohl(a->lsr_id.s_addr) - ntohl(b->lsr_id.s_addr));
+}
+
struct nbr_params *
nbr_params_new(struct in_addr lsr_id)
{
@@ -769,13 +778,9 @@ nbr_params_new(struct in_addr lsr_id)
struct nbr_params *
nbr_params_find(struct ldpd_conf *xconf, struct in_addr lsr_id)
{
- struct nbr_params *nbrp;
-
- LIST_FOREACH(nbrp, &xconf->nbrp_list, entry)
- if (nbrp->lsr_id.s_addr == lsr_id.s_addr)
- return (nbrp);
-
- return (NULL);
+ struct nbr_params nbrp;
+ nbrp.lsr_id = lsr_id;
+ return (RB_FIND(nbrp_head, &xconf->nbrp_tree, &nbrp));
}
uint16_t
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-12 10:54:23 +0000