Merge pull request #730 from opensourcerouting/rbtree-improvement

RB tree improvement

10 files changed, 99 insertions, 91 deletions

diff --git a/ldpd/adjacency.c b/ldpd/adjacency.c
index 52e2776654..e73d1b51a2 100644
--- a/ldpd/adjacency.c
+++ b/ldpd/adjacency.c
@@ -25,9 +25,9 @@
 #include "ldpe.h"
 #include "log.h"
 
-static __inline int adj_compare(struct adj *, struct adj *);
+static __inline int adj_compare(const struct adj *, const struct adj *);
 static int	 adj_itimer(struct thread *);
-static __inline int tnbr_compare(struct tnbr *, struct tnbr *);
+static __inline int tnbr_compare(const struct tnbr *, const struct tnbr *);
 static void	 tnbr_del(struct ldpd_conf *, struct tnbr *);
 static void	 tnbr_start(struct tnbr *);
 static void	 tnbr_stop(struct tnbr *);
@@ -41,7 +41,7 @@ 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)
+adj_compare(const struct adj *a, const struct adj *b)
 {
 	if (adj_get_af(a) < adj_get_af(b))
 		return (-1);
@@ -163,7 +163,7 @@ adj_find(struct in_addr lsr_id, struct hello_source *source)
 }
 
 int
-adj_get_af(struct adj *adj)
+adj_get_af(const struct adj *adj)
 {
 	switch (adj->source.type) {
 	case HELLO_LINK:
@@ -220,7 +220,7 @@ adj_stop_itimer(struct adj *adj)
 /* targeted neighbors */
 
 static __inline int
-tnbr_compare(struct tnbr *a, struct tnbr *b)
+tnbr_compare(const struct tnbr *a, const struct tnbr *b)
 {
 	if (a->af < b->af)
 		return (-1);
diff --git a/ldpd/interface.c b/ldpd/interface.c
index a064a58b2e..ac48520f7b 100644
--- a/ldpd/interface.c
+++ b/ldpd/interface.c
@@ -26,7 +26,7 @@
 
 #include "sockopt.h"
 
-static __inline int	 iface_compare(struct iface *, struct iface *);
+static __inline int	 iface_compare(const struct iface *, const 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);
@@ -43,7 +43,7 @@ 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)
+iface_compare(const struct iface *a, const struct iface *b)
 {
 	return (strcmp(a->name, b->name));
 }
@@ -81,12 +81,12 @@ ldpe_if_init(struct iface *iface)
 	/* ipv4 */
 	iface->ipv4.iface = iface;
 	iface->ipv4.state = IF_STA_DOWN;
-	RB_INIT(&iface->ipv4.adj_tree);
+	RB_INIT(ia_adj_head, &iface->ipv4.adj_tree);
 
 	/* ipv6 */
 	iface->ipv6.iface = iface;
 	iface->ipv6.state = IF_STA_DOWN;
-	RB_INIT(&iface->ipv6.adj_tree);
+	RB_INIT(ia_adj_head, &iface->ipv6.adj_tree);
 }
 
 void
@@ -305,7 +305,7 @@ if_reset(struct iface *iface, int af)
 	ia = iface_af_get(iface, af);
 	if_stop_hello_timer(ia);
 
-	while ((adj = RB_ROOT(&ia->adj_tree)) != NULL)
+	while ((adj = RB_ROOT(ia_adj_head, &ia->adj_tree)) != NULL)
 		adj_del(adj, S_SHUTDOWN);
 
 	/* try to cleanup */
diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c
index 27948f5a1a..f15461d3d2 100644
--- a/ldpd/l2vpn.c
+++ b/ldpd/l2vpn.c
@@ -27,16 +27,16 @@
 #include "log.h"
 
 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 *);
+static __inline int	 l2vpn_compare(const struct l2vpn *, const struct l2vpn *);
+static __inline int	 l2vpn_if_compare(const struct l2vpn_if *, const struct l2vpn_if *);
+static __inline int	 l2vpn_pw_compare(const struct l2vpn_pw *, const 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)
+l2vpn_compare(const struct l2vpn *a, const struct l2vpn *b)
 {
 	return (strcmp(a->name, b->name));
 }
@@ -55,9 +55,9 @@ l2vpn_new(const char *name)
 	l2vpn->mtu = DEFAULT_L2VPN_MTU;
 	l2vpn->pw_type = DEFAULT_PW_TYPE;
 
-	RB_INIT(&l2vpn->if_tree);
-	RB_INIT(&l2vpn->pw_tree);
-	RB_INIT(&l2vpn->pw_inactive_tree);
+	RB_INIT(l2vpn_if_head, &l2vpn->if_tree);
+	RB_INIT(l2vpn_pw_head, &l2vpn->pw_tree);
+	RB_INIT(l2vpn_pw_head, &l2vpn->pw_inactive_tree);
 
 	return (l2vpn);
 }
@@ -76,15 +76,16 @@ l2vpn_del(struct l2vpn *l2vpn)
 	struct l2vpn_if		*lif;
 	struct l2vpn_pw		*pw;
 
-	while ((lif = RB_ROOT(&l2vpn->if_tree)) != NULL) {
+	while ((lif = RB_ROOT(l2vpn_if_head, &l2vpn->if_tree)) != NULL) {
 		RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif);
 		free(lif);
 	}
-	while ((pw = RB_ROOT(&l2vpn->pw_tree)) != NULL) {
+	while ((pw = RB_ROOT(l2vpn_pw_head, &l2vpn->pw_tree)) != NULL) {
 		RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw);
 		free(pw);
 	}
-	while ((pw = RB_ROOT(&l2vpn->pw_inactive_tree)) != NULL) {
+	while ((pw = RB_ROOT(l2vpn_pw_head,
+	    &l2vpn->pw_inactive_tree)) != NULL) {
 		RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
 		free(pw);
 	}
@@ -111,7 +112,7 @@ l2vpn_exit(struct l2vpn *l2vpn)
 }
 
 static __inline int
-l2vpn_if_compare(struct l2vpn_if *a, struct l2vpn_if *b)
+l2vpn_if_compare(const struct l2vpn_if *a, const struct l2vpn_if *b)
 {
 	return (strcmp(a->ifname, b->ifname));
 }
@@ -174,7 +175,7 @@ l2vpn_if_update(struct l2vpn_if *lif)
 }
 
 static __inline int
-l2vpn_pw_compare(struct l2vpn_pw *a, struct l2vpn_pw *b)
+l2vpn_pw_compare(const struct l2vpn_pw *a, const struct l2vpn_pw *b)
 {
 	return (strcmp(a->ifname, b->ifname));
 }
@@ -512,7 +513,7 @@ l2vpn_binding_ctl(pid_t pid)
 
 		fn = (struct fec_node *)f;
 		if (fn->local_label == NO_LABEL &&
-		    RB_EMPTY(&fn->downstream))
+		    RB_EMPTY(lde_map_head, &fn->downstream))
 			continue;
 
 		memset(&pwctl, 0, sizeof(pwctl));
diff --git a/ldpd/lde.c b/ldpd/lde.c
index 4b1ad63d64..0ef46dab3d 100644
--- a/ldpd/lde.c
+++ b/ldpd/lde.c
@@ -41,15 +41,16 @@
 static void		 lde_shutdown(void);
 static int		 lde_dispatch_imsg(struct thread *);
 static int		 lde_dispatch_parent(struct thread *);
-static __inline	int	 lde_nbr_compare(struct lde_nbr *,
-			    struct lde_nbr *);
+static __inline	int	 lde_nbr_compare(const struct lde_nbr *,
+			    const struct lde_nbr *);
 static struct lde_nbr	*lde_nbr_new(uint32_t, struct lde_nbr *);
 static void		 lde_nbr_del(struct lde_nbr *);
 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 __inline int	 lde_map_compare(const struct lde_map *,
+			    const 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 *);
@@ -542,10 +543,10 @@ lde_dispatch_parent(struct thread *thread)
 				fatal(NULL);
 			memcpy(nconf, imsg.data, sizeof(struct ldpd_conf));
 
-			RB_INIT(&nconf->iface_tree);
-			RB_INIT(&nconf->tnbr_tree);
-			RB_INIT(&nconf->nbrp_tree);
-			RB_INIT(&nconf->l2vpn_tree);
+			RB_INIT(iface_head, &nconf->iface_tree);
+			RB_INIT(tnbr_head, &nconf->tnbr_tree);
+			RB_INIT(nbrp_head, &nconf->nbrp_tree);
+			RB_INIT(l2vpn_head, &nconf->l2vpn_tree);
 			break;
 		case IMSG_RECONF_IFACE:
 			if ((niface = malloc(sizeof(struct iface))) == NULL)
@@ -573,9 +574,9 @@ lde_dispatch_parent(struct thread *thread)
 				fatal(NULL);
 			memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn));
 
-			RB_INIT(&nl2vpn->if_tree);
-			RB_INIT(&nl2vpn->pw_tree);
-			RB_INIT(&nl2vpn->pw_inactive_tree);
+			RB_INIT(l2vpn_if_head, &nl2vpn->if_tree);
+			RB_INIT(l2vpn_pw_head, &nl2vpn->pw_tree);
+			RB_INIT(l2vpn_pw_head, &nl2vpn->pw_inactive_tree);
 
 			RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn);
 			break;
@@ -1189,7 +1190,7 @@ lde_send_notification_eol_pwid(struct lde_nbr *ln, uint16_t pw_type)
 }
 
 static __inline int
-lde_nbr_compare(struct lde_nbr *a, struct lde_nbr *b)
+lde_nbr_compare(const struct lde_nbr *a, const struct lde_nbr *b)
 {
 	return (a->peerid - b->peerid);
 }
@@ -1314,7 +1315,7 @@ lde_nbr_clear(void)
 {
 	struct lde_nbr	*ln;
 
-	 while ((ln = RB_ROOT(&lde_nbrs)) != NULL)
+	 while ((ln = RB_ROOT(nbr_tree, &lde_nbrs)) != NULL)
 		lde_nbr_del(ln);
 }
 
@@ -1360,7 +1361,7 @@ 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)
+lde_map_compare(const struct lde_map *a, const struct lde_map *b)
 {
 	return (ldp_addrcmp(AF_INET, (union ldpd_addr *)&a->nexthop->id,
 	    (union ldpd_addr *)&b->nexthop->id));
diff --git a/ldpd/lde_lib.c b/ldpd/lde_lib.c
index 8dc305cac1..edf686537f 100644
--- a/ldpd/lde_lib.c
+++ b/ldpd/lde_lib.c
@@ -25,7 +25,7 @@
 
 #include "mpls.h"
 
-static __inline int	 fec_compare(struct fec *, struct fec *);
+static __inline int	 fec_compare(const struct fec *, const struct fec *);
 static int		 lde_nbr_is_nexthop(struct fec_node *,
 			    struct lde_nbr *);
 static void		 fec_free(void *);
@@ -43,11 +43,11 @@ struct thread		*gc_timer;
 void
 fec_init(struct fec_tree *fh)
 {
-	RB_INIT(fh);
+	RB_INIT(fec_tree, fh);
 }
 
 static __inline int
-fec_compare(struct fec *a, struct fec *b)
+fec_compare(const struct fec *a, const struct fec *b)
 {
 	if (a->type < b->type)
 		return (-1);
@@ -129,7 +129,7 @@ fec_clear(struct fec_tree *fh, void (*free_cb)(void *))
 {
 	struct fec	*f;
 
-	while ((f = RB_ROOT(fh)) != NULL) {
+	while ((f = RB_ROOT(fec_tree, fh)) != NULL) {
 		fec_remove(fh, f);
 		free_cb(f);
 	}
@@ -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 &&
-		    RB_EMPTY(&fn->downstream))
+		    RB_EMPTY(lde_map_head, &fn->downstream))
 			continue;
 
 		memset(&rtctl, 0, sizeof(rtctl));
@@ -179,7 +179,7 @@ rt_dump(pid_t pid)
 		}
 
 		rtctl.local_label = fn->local_label;
-		if (RB_EMPTY(&fn->downstream)) {
+		if (RB_EMPTY(lde_map_head, &fn->downstream)) {
 			rtctl.in_use = 0;
 			rtctl.nexthop.s_addr = INADDR_ANY;
 			rtctl.remote_label = NO_LABEL;
@@ -231,10 +231,10 @@ fec_free(void *arg)
 
 	while ((fnh = LIST_FIRST(&fn->nexthops)))
 		fec_nh_del(fnh);
-	if (!RB_EMPTY(&fn->downstream))
+	if (!RB_EMPTY(lde_map_head, &fn->downstream))
 		log_warnx("%s: fec %s downstream list not empty", __func__,
 		    log_fec(&fn->fec));
-	if (!RB_EMPTY(&fn->upstream))
+	if (!RB_EMPTY(lde_map_head, &fn->upstream))
 		log_warnx("%s: fec %s upstream list not empty", __func__,
 		    log_fec(&fn->fec));
 
@@ -258,8 +258,8 @@ fec_add(struct fec *fec)
 
 	fn->fec = *fec;
 	fn->local_label = NO_LABEL;
-	RB_INIT(&fn->upstream);
-	RB_INIT(&fn->downstream);
+	RB_INIT(lde_map_head, &fn->upstream);
+	RB_INIT(lde_map_head, &fn->downstream);
 	LIST_INIT(&fn->nexthops);
 
 	if (fec_insert(&ft, &fn->fec))
@@ -396,7 +396,8 @@ lde_kernel_update(struct fec *fec)
 		lde_gc_start_timer();
 	} else {
 		fn->local_label = lde_update_label(fn);
-		if (fn->local_label != NO_LABEL && RB_EMPTY(&fn->upstream))
+		if (fn->local_label != NO_LABEL &&
+		    RB_EMPTY(lde_map_head, &fn->upstream))
 			/* FEC.1: perform lsr label distribution procedure */
 			RB_FOREACH(ln, nbr_tree, &lde_nbrs)
 				lde_send_labelmapping(ln, fn, 1);
@@ -904,8 +905,8 @@ lde_gc_timer(struct thread *thread)
 		fn = (struct fec_node *) fec;
 
 		if (!LIST_EMPTY(&fn->nexthops) ||
-		    !RB_EMPTY(&fn->downstream) ||
-		    !RB_EMPTY(&fn->upstream))
+		    !RB_EMPTY(lde_map_head, &fn->downstream) ||
+		    !RB_EMPTY(lde_map_head, &fn->upstream))
 			continue;
 
 		fec_remove(&ft, &fn->fec);
diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c
index c96e69a6c5..532c880afc 100644
--- a/ldpd/ldp_vty_conf.c
+++ b/ldpd/ldp_vty_conf.c
@@ -1553,17 +1553,18 @@ l2vpn_del_api(struct ldpd_conf *conf, struct l2vpn *l2vpn)
 	struct l2vpn_if		*lif;
 	struct l2vpn_pw		*pw;
 
-	while ((lif = RB_ROOT(&l2vpn->if_tree)) != NULL) {
+	while ((lif = RB_ROOT(l2vpn_if_head, &l2vpn->if_tree)) != NULL) {
 		QOBJ_UNREG(lif);
 		RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif);
 		free(lif);
 	}
-	while ((pw = RB_ROOT(&l2vpn->pw_tree)) != NULL) {
+	while ((pw = RB_ROOT(l2vpn_pw_head, &l2vpn->pw_tree)) != NULL) {
 		QOBJ_UNREG(pw);
 		RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw);
 		free(pw);
 	}
-	while ((pw = RB_ROOT(&l2vpn->pw_inactive_tree)) != NULL) {
+	while ((pw = RB_ROOT(l2vpn_pw_head,
+	    &l2vpn->pw_inactive_tree)) != NULL) {
 		QOBJ_UNREG(pw);
 		RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
 		free(pw);
diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c
index 6993ad15cc..abcad79d67 100644
--- a/ldpd/ldpd.c
+++ b/ldpd/ldpd.c
@@ -1043,13 +1043,13 @@ ldp_config_reset_main(struct ldpd_conf *conf)
 	struct iface		*iface;
 	struct nbr_params	*nbrp;
 
-	while ((iface = RB_ROOT(&conf->iface_tree)) != NULL) {
+	while ((iface = RB_ROOT(iface_head, &conf->iface_tree)) != NULL) {
 		QOBJ_UNREG(iface);
 		RB_REMOVE(iface_head, &conf->iface_tree, iface);
 		free(iface);
 	}
 
-	while ((nbrp = RB_ROOT(&conf->nbrp_tree)) != NULL) {
+	while ((nbrp = RB_ROOT(nbrp_head, &conf->nbrp_tree)) != NULL) {
 		QOBJ_UNREG(nbrp);
 		RB_REMOVE(nbrp_head, &conf->nbrp_tree, nbrp);
 		free(nbrp);
@@ -1105,18 +1105,20 @@ ldp_config_reset_l2vpns(struct ldpd_conf *conf)
 	struct l2vpn_if		*lif;
 	struct l2vpn_pw		*pw;
 
-	while ((l2vpn = RB_ROOT(&conf->l2vpn_tree)) != NULL) {
-		while ((lif = RB_ROOT(&l2vpn->if_tree)) != NULL) {
+	while ((l2vpn = RB_ROOT(l2vpn_head, &conf->l2vpn_tree)) != NULL) {
+		while ((lif = RB_ROOT(l2vpn_if_head,
+		    &l2vpn->if_tree)) != NULL) {
 			QOBJ_UNREG(lif);
 			RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif);
 			free(lif);
 		}
-		while ((pw = RB_ROOT(&l2vpn->pw_tree)) != NULL) {
+		while ((pw = RB_ROOT(l2vpn_pw_head, &l2vpn->pw_tree)) != NULL) {
 			QOBJ_UNREG(pw);
 			RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw);
 			free(pw);
 		}
-		while ((pw = RB_ROOT(&l2vpn->pw_inactive_tree)) != NULL) {
+		while ((pw = RB_ROOT(l2vpn_pw_head,
+		    &l2vpn->pw_inactive_tree)) != NULL) {
 			QOBJ_UNREG(pw);
 			RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw);
 			free(pw);
@@ -1135,19 +1137,19 @@ ldp_clear_config(struct ldpd_conf *xconf)
 	struct nbr_params	*nbrp;
 	struct l2vpn		*l2vpn;
 
-	while ((iface = RB_ROOT(&xconf->iface_tree)) != NULL) {
+	while ((iface = RB_ROOT(iface_head, &xconf->iface_tree)) != NULL) {
 		RB_REMOVE(iface_head, &xconf->iface_tree, iface);
 		free(iface);
 	}
-	while ((tnbr = RB_ROOT(&xconf->tnbr_tree)) != NULL) {
+	while ((tnbr = RB_ROOT(tnbr_head, &xconf->tnbr_tree)) != NULL) {
 		RB_REMOVE(tnbr_head, &xconf->tnbr_tree, tnbr);
 		free(tnbr);
 	}
-	while ((nbrp = RB_ROOT(&xconf->nbrp_tree)) != NULL) {
+	while ((nbrp = RB_ROOT(nbrp_head, &xconf->nbrp_tree)) != NULL) {
 		RB_REMOVE(nbrp_head, &xconf->nbrp_tree, nbrp);
 		free(nbrp);
 	}
-	while ((l2vpn = RB_ROOT(&xconf->l2vpn_tree)) != NULL) {
+	while ((l2vpn = RB_ROOT(l2vpn_head, &xconf->l2vpn_tree)) != NULL) {
 		RB_REMOVE(l2vpn_head, &xconf->l2vpn_tree, l2vpn);
 		l2vpn_del(l2vpn);
 	}
@@ -1550,9 +1552,9 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf)
 		if ((l2vpn = l2vpn_find(conf, xl->name)) == NULL) {
 			COPY(l2vpn, xl);
 			RB_INSERT(l2vpn_head, &conf->l2vpn_tree, l2vpn);
-			RB_INIT(&l2vpn->if_tree);
-			RB_INIT(&l2vpn->pw_tree);
-			RB_INIT(&l2vpn->pw_inactive_tree);
+			RB_INIT(l2vpn_if_head, &l2vpn->if_tree);
+			RB_INIT(l2vpn_pw_head, &l2vpn->pw_tree);
+			RB_INIT(l2vpn_pw_head, &l2vpn->pw_inactive_tree);
 
 			switch (ldpd_process) {
 			case PROC_LDE_ENGINE:
@@ -1761,10 +1763,10 @@ config_new_empty(void)
 	if (xconf == NULL)
 		fatal(NULL);
 
-	RB_INIT(&xconf->iface_tree);
-	RB_INIT(&xconf->tnbr_tree);
-	RB_INIT(&xconf->nbrp_tree);
-	RB_INIT(&xconf->l2vpn_tree);
+	RB_INIT(iface_head, &xconf->iface_tree);
+	RB_INIT(tnbr_head, &xconf->tnbr_tree);
+	RB_INIT(nbrp_head, &xconf->nbrp_tree);
+	RB_INIT(l2vpn_head, &xconf->l2vpn_tree);
 
 	/* set default values */
 	ldp_config_reset(xconf);
diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c
index 451d637bcf..ba153dfde2 100644
--- a/ldpd/ldpe.c
+++ b/ldpd/ldpe.c
@@ -152,7 +152,7 @@ ldpe_init(struct ldpd_init *init)
 	control_listen();
 
 	LIST_INIT(&global.addr_list);
-	RB_INIT(&global.adj_tree);
+	RB_INIT(global_adj_head, &global.adj_tree);
 	TAILQ_INIT(&global.pending_conns);
 	if (inet_pton(AF_INET, AllRouters_v4, &global.mcast_addr_v4) != 1)
 		fatal("inet_pton");
@@ -216,7 +216,7 @@ ldpe_shutdown(void)
 		LIST_REMOVE(if_addr, entry);
 		free(if_addr);
 	}
-	while ((adj = RB_ROOT(&global.adj_tree)) != NULL)
+	while ((adj = RB_ROOT(global_adj_head, &global.adj_tree)) != NULL)
 		adj_del(adj, S_SHUTDOWN);
 
 	/* clean up */
@@ -456,10 +456,10 @@ ldpe_dispatch_main(struct thread *thread)
 				fatal(NULL);
 			memcpy(nconf, imsg.data, sizeof(struct ldpd_conf));
 
-			RB_INIT(&nconf->iface_tree);
-			RB_INIT(&nconf->tnbr_tree);
-			RB_INIT(&nconf->nbrp_tree);
-			RB_INIT(&nconf->l2vpn_tree);
+			RB_INIT(iface_head, &nconf->iface_tree);
+			RB_INIT(tnbr_head, &nconf->tnbr_tree);
+			RB_INIT(nbrp_head, &nconf->nbrp_tree);
+			RB_INIT(l2vpn_head, &nconf->l2vpn_tree);
 			break;
 		case IMSG_RECONF_IFACE:
 			if ((niface = malloc(sizeof(struct iface))) == NULL)
@@ -487,9 +487,9 @@ ldpe_dispatch_main(struct thread *thread)
 				fatal(NULL);
 			memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn));
 
-			RB_INIT(&nl2vpn->if_tree);
-			RB_INIT(&nl2vpn->pw_tree);
-			RB_INIT(&nl2vpn->pw_inactive_tree);
+			RB_INIT(l2vpn_if_head, &nl2vpn->if_tree);
+			RB_INIT(l2vpn_pw_head, &nl2vpn->pw_tree);
+			RB_INIT(l2vpn_pw_head, &nl2vpn->pw_inactive_tree);
 
 			RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn);
 			break;
@@ -876,8 +876,8 @@ ldpe_adj_detail_ctl(struct ctl_conn *c)
 			continue;
 
 		strlcpy(ictl.name, iface->name, sizeof(ictl.name));
-		if (RB_EMPTY(&iface->ipv4.adj_tree) &&
-		    RB_EMPTY(&iface->ipv6.adj_tree))
+		if (RB_EMPTY(ia_adj_head, &iface->ipv4.adj_tree) &&
+		    RB_EMPTY(ia_adj_head, &iface->ipv6.adj_tree))
 			ictl.no_adj = 1;
 		imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISC_IFACE, 0, 0,
 		    -1, &ictl, sizeof(ictl));
diff --git a/ldpd/ldpe.h b/ldpd/ldpe.h
index d34ca4dc24..74f6b852b0 100644
--- a/ldpd/ldpe.h
+++ b/ldpd/ldpe.h
@@ -237,7 +237,7 @@ struct adj	*adj_new(struct in_addr, struct hello_source *,
 		    union ldpd_addr *);
 void		 adj_del(struct adj *, uint32_t);
 struct adj	*adj_find(struct in_addr, struct hello_source *);
-int		 adj_get_af(struct adj *adj);
+int		 adj_get_af(const struct adj *adj);
 void		 adj_start_itimer(struct adj *);
 void		 adj_stop_itimer(struct adj *);
 struct tnbr	*tnbr_new(int, union ldpd_addr *);
diff --git a/ldpd/neighbor.c b/ldpd/neighbor.c
index f867db228d..f8d4b5f5fd 100644
--- a/ldpd/neighbor.c
+++ b/ldpd/neighbor.c
@@ -26,9 +26,11 @@
 #include "lde.h"
 #include "log.h"
 
-static __inline int	 nbr_id_compare(struct nbr *, struct nbr *);
-static __inline int	 nbr_addr_compare(struct nbr *, struct nbr *);
-static __inline int	 nbr_pid_compare(struct nbr *, struct nbr *);
+static __inline int	 nbr_id_compare(const struct nbr *, const struct nbr *);
+static __inline int	 nbr_addr_compare(const struct nbr *,
+			    const struct nbr *);
+static __inline int	 nbr_pid_compare(const struct nbr *,
+			    const struct nbr *);
 static void		 nbr_update_peerid(struct nbr *);
 static int		 nbr_ktimer(struct thread *);
 static void		 nbr_start_ktimer(struct nbr *);
@@ -39,8 +41,8 @@ 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 *);
+static __inline int	 nbr_params_compare(const struct nbr_params *,
+			    const 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)
@@ -101,13 +103,13 @@ struct nbr_addr_head nbrs_by_addr = RB_INITIALIZER(&nbrs_by_addr);
 struct nbr_pid_head nbrs_by_pid = RB_INITIALIZER(&nbrs_by_pid);
 
 static __inline int
-nbr_id_compare(struct nbr *a, struct nbr *b)
+nbr_id_compare(const struct nbr *a, const struct nbr *b)
 {
 	return (ntohl(a->id.s_addr) - ntohl(b->id.s_addr));
 }
 
 static __inline int
-nbr_addr_compare(struct nbr *a, struct nbr *b)
+nbr_addr_compare(const struct nbr *a, const struct nbr *b)
 {
 	if (a->af < b->af)
 		return (-1);
@@ -118,7 +120,7 @@ nbr_addr_compare(struct nbr *a, struct nbr *b)
 }
 
 static __inline int
-nbr_pid_compare(struct nbr *a, struct nbr *b)
+nbr_pid_compare(const struct nbr *a, const struct nbr *b)
 {
 	return (a->peerid - b->peerid);
 }
@@ -229,7 +231,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__);
 
-	RB_INIT(&nbr->adj_tree);
+	RB_INIT(nbr_adj_head, &nbr->adj_tree);
 	nbr->state = NBR_STA_PRESENT;
 	nbr->peerid = 0;
 	nbr->af = af;
@@ -764,7 +766,7 @@ nbr_send_labelmappings(struct nbr *nbr)
 }
 
 static __inline int
-nbr_params_compare(struct nbr_params *a, struct nbr_params *b)
+nbr_params_compare(const struct nbr_params *a, const struct nbr_params *b)
 {
 	return (ntohl(a->lsr_id.s_addr) - ntohl(b->lsr_id.s_addr));
 }