lib: improve the RB implementation

Switch the RB tree implementation completely to the new dlg@'s version
that uses pre-declared functions instead of macros for tree functions.

Original e-mail/diff:
https://marc.info/?l=openbsd-tech&m=147087487111068&w=2

Pros:

* Reduces the amount of code that the usage of those macros generate
* Allows the compiler to do a better compile-time check job
* Might have better i-cache utilization since the tree code is shared

Con:

* dlg@ benchmarks shows it has 'very slightly slower' insertions
* imported RB_* code must adapt the following calls:
  RB_INIT(), RB_GENERATE(), RB_ROOT(), RB_EMPTY(), make compare
  functions use 'const' (if not already) and maybe others.

15 files changed, 975 insertions, 523 deletions

diff --git a/ldpd/adjacency.c b/ldpd/adjacency.c
index 52e277665..8a2252e72 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);
@@ -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 a064a58b2..527a6bc96 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(iface_head, &iface->ipv4.adj_tree);
 
 	/* ipv6 */
 	iface->ipv6.iface = iface;
 	iface->ipv6.state = IF_STA_DOWN;
-	RB_INIT(&iface->ipv6.adj_tree);
+	RB_INIT(iface_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(iface_head, &ia->adj_tree)) != NULL)
 		adj_del(adj, S_SHUTDOWN);
 
 	/* try to cleanup */
diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c
index 27948f5a1..f15461d3d 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 4b1ad63d6..0ef46dab3 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 8dc305cac..edf686537 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 839490714..87f76d3d0 100644
--- a/ldpd/ldp_vty_conf.c
+++ b/ldpd/ldp_vty_conf.c
@@ -1725,17 +1725,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 6993ad15c..abcad79d6 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 451d637bc..ba153dfde 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/neighbor.c b/ldpd/neighbor.c
index f867db228..f8d4b5f5f 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));
 }
diff --git a/lib/Makefile.am b/lib/Makefile.am
index a1b78d3c4..4a8b4290a 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -15,7 +15,7 @@ libfrr_la_LDFLAGS = -version-info 0:0:0
 
 libfrr_la_SOURCES = \
 	network.c pid_output.c getopt.c getopt1.c \
-	checksum.c vector.c linklist.c vty.c \
+	checksum.c vector.c linklist.c vty.c openbsd-tree.c \
 	graph.c command_parse.y command_lex.l command_match.c \
 	command_graph.c \
 	command.c \
diff --git a/lib/ns.c b/lib/ns.c
index 8c489d68f..68dc3fa34 100644
--- a/lib/ns.c
+++ b/lib/ns.c
@@ -39,7 +39,7 @@
 DEFINE_MTYPE_STATIC(LIB, NS,        "Logical-Router")
 DEFINE_MTYPE_STATIC(LIB, NS_NAME,   "Logical-Router Name")
 
-static __inline int ns_compare (struct ns *, struct ns *);
+static __inline int ns_compare (const struct ns *, const struct ns *);
 static struct ns *ns_lookup (ns_id_t);
 
 RB_GENERATE (ns_head, ns, entry, ns_compare)
@@ -108,7 +108,7 @@ static int ns_enable (struct ns *ns);
 static void ns_disable (struct ns *ns);
 
 static __inline int
-ns_compare(struct ns *a, struct ns *b)
+ns_compare(const struct ns *a, const struct ns *b)
 {
   return (a->ns_id - b->ns_id);
 }
@@ -453,7 +453,7 @@ ns_terminate (void)
 {
   struct ns *ns;
 
-  while ((ns = RB_ROOT (&ns_tree)) != NULL)
+  while ((ns = RB_ROOT (ns_head, &ns_tree)) != NULL)
     ns_delete (ns);
 }
 
diff --git a/lib/openbsd-tree.c b/lib/openbsd-tree.c
new file mode 100644
index 000000000..37762abc1
--- /dev/null
+++ b/lib/openbsd-tree.c
@@ -0,0 +1,640 @@
+/*	$OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */
+
+/*
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <stdlib.h>
+
+#include <lib/openbsd-tree.h>
+
+static inline struct rb_entry *
+rb_n2e(const struct rb_type *t, void *node)
+{
+	unsigned long addr = (unsigned long)node;
+
+	return ((struct rb_entry *)(addr + t->t_offset));
+}
+
+static inline void *
+rb_e2n(const struct rb_type *t, struct rb_entry *rbe)
+{
+	unsigned long addr = (unsigned long)rbe;
+
+	return ((void *)(addr - t->t_offset));
+}
+
+#define RBE_LEFT(_rbe)		(_rbe)->rbt_left
+#define RBE_RIGHT(_rbe)		(_rbe)->rbt_right
+#define RBE_PARENT(_rbe)	(_rbe)->rbt_parent
+#define RBE_COLOR(_rbe)		(_rbe)->rbt_color
+
+#define RBH_ROOT(_rbt)		(_rbt)->rbt_root
+
+static inline void
+rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
+{
+	RBE_PARENT(rbe) = parent;
+	RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
+	RBE_COLOR(rbe) = RB_RED;
+}
+
+static inline void
+rbe_set_blackred(struct rb_entry *black, struct rb_entry *red)
+{
+	RBE_COLOR(black) = RB_BLACK;
+	RBE_COLOR(red) = RB_RED;
+}
+
+static inline void
+rbe_augment(const struct rb_type *t, struct rb_entry *rbe)
+{
+	(*t->t_augment)(rb_e2n(t, rbe));
+}
+
+static inline void
+rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe)
+{
+	if (t->t_augment != NULL)
+		rbe_augment(t, rbe);
+}
+
+static inline void
+rbe_rotate_left(const struct rb_type *t, struct rb_tree *rbt,
+    struct rb_entry *rbe)
+{
+	struct rb_entry *parent;
+	struct rb_entry *tmp;
+
+	tmp = RBE_RIGHT(rbe);
+	RBE_RIGHT(rbe) = RBE_LEFT(tmp);
+	if (RBE_RIGHT(rbe) != NULL)
+		RBE_PARENT(RBE_LEFT(tmp)) = rbe;
+
+	parent = RBE_PARENT(rbe);
+	RBE_PARENT(tmp) = parent;
+	if (parent != NULL) {
+		if (rbe == RBE_LEFT(parent))
+			RBE_LEFT(parent) = tmp;
+		else
+			RBE_RIGHT(parent) = tmp;
+	} else
+		RBH_ROOT(rbt) = tmp;
+
+	RBE_LEFT(tmp) = rbe;
+	RBE_PARENT(rbe) = tmp;
+
+	if (t->t_augment != NULL) {
+		rbe_augment(t, rbe);
+		rbe_augment(t, tmp);
+		parent = RBE_PARENT(tmp);
+		if (parent != NULL)
+			rbe_augment(t, parent);
+	}
+}
+
+static inline void
+rbe_rotate_right(const struct rb_type *t, struct rb_tree *rbt,
+    struct rb_entry *rbe)
+{
+	struct rb_entry *parent;
+	struct rb_entry *tmp;
+
+	tmp = RBE_LEFT(rbe);
+	RBE_LEFT(rbe) = RBE_RIGHT(tmp);
+	if (RBE_LEFT(rbe) != NULL)
+		RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
+
+	parent = RBE_PARENT(rbe);
+	RBE_PARENT(tmp) = parent;
+	if (parent != NULL) {
+		if (rbe == RBE_LEFT(parent))
+			RBE_LEFT(parent) = tmp;
+		else
+			RBE_RIGHT(parent) = tmp;
+	} else
+		RBH_ROOT(rbt) = tmp;
+
+	RBE_RIGHT(tmp) = rbe;
+	RBE_PARENT(rbe) = tmp;
+
+	if (t->t_augment != NULL) {
+		rbe_augment(t, rbe);
+		rbe_augment(t, tmp);
+		parent = RBE_PARENT(tmp);
+		if (parent != NULL)
+			rbe_augment(t, parent);
+	}
+}
+
+static inline void
+rbe_insert_color(const struct rb_type *t, struct rb_tree *rbt,
+    struct rb_entry *rbe)
+{
+	struct rb_entry *parent, *gparent, *tmp;
+
+	while ((parent = RBE_PARENT(rbe)) != NULL &&
+	    RBE_COLOR(parent) == RB_RED) {
+		gparent = RBE_PARENT(parent);
+
+		if (parent == RBE_LEFT(gparent)) {
+			tmp = RBE_RIGHT(gparent);
+			if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
+				RBE_COLOR(tmp) = RB_BLACK;
+				rbe_set_blackred(parent, gparent);
+				rbe = gparent;
+				continue;
+			}
+
+			if (RBE_RIGHT(parent) == rbe) {
+				rbe_rotate_left(t, rbt, parent);
+				tmp = parent;
+				parent = rbe;
+				rbe = tmp;
+			}
+
+			rbe_set_blackred(parent, gparent);
+			rbe_rotate_right(t, rbt, gparent);
+		} else {
+			tmp = RBE_LEFT(gparent);
+			if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
+				RBE_COLOR(tmp) = RB_BLACK;
+				rbe_set_blackred(parent, gparent);
+				rbe = gparent;
+				continue;
+			}
+
+			if (RBE_LEFT(parent) == rbe) {
+				rbe_rotate_right(t, rbt, parent);
+				tmp = parent;
+				parent = rbe;
+				rbe = tmp;
+			}
+
+			rbe_set_blackred(parent, gparent);
+			rbe_rotate_left(t, rbt, gparent);
+		}
+	}
+
+	RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
+}
+
+static inline void
+rbe_remove_color(const struct rb_type *t, struct rb_tree *rbt,
+    struct rb_entry *parent, struct rb_entry *rbe)
+{
+	struct rb_entry *tmp;
+
+	while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) &&
+	    rbe != RBH_ROOT(rbt)) {
+		if (RBE_LEFT(parent) == rbe) {
+			tmp = RBE_RIGHT(parent);
+			if (RBE_COLOR(tmp) == RB_RED) {
+				rbe_set_blackred(tmp, parent);
+				rbe_rotate_left(t, rbt, parent);
+				tmp = RBE_RIGHT(parent);
+			}
+			if ((RBE_LEFT(tmp) == NULL ||
+			     RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) &&
+			    (RBE_RIGHT(tmp) == NULL ||
+			     RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
+				RBE_COLOR(tmp) = RB_RED;
+				rbe = parent;
+				parent = RBE_PARENT(rbe);
+			} else {
+				if (RBE_RIGHT(tmp) == NULL ||
+				    RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
+					struct rb_entry *oleft;
+
+					oleft = RBE_LEFT(tmp);
+					if (oleft != NULL)
+						RBE_COLOR(oleft) = RB_BLACK;
+
+					RBE_COLOR(tmp) = RB_RED;
+					rbe_rotate_right(t, rbt, tmp);
+					tmp = RBE_RIGHT(parent);
+				}
+
+				RBE_COLOR(tmp) = RBE_COLOR(parent);
+				RBE_COLOR(parent) = RB_BLACK;
+				if (RBE_RIGHT(tmp))
+					RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
+
+				rbe_rotate_left(t, rbt, parent);
+				rbe = RBH_ROOT(rbt);
+				break;
+			}
+		} else {
+			tmp = RBE_LEFT(parent);
+			if (RBE_COLOR(tmp) == RB_RED) {
+				rbe_set_blackred(tmp, parent);
+				rbe_rotate_right(t, rbt, parent);
+				tmp = RBE_LEFT(parent);
+			}
+
+			if ((RBE_LEFT(tmp) == NULL ||
+			     RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) &&
+			    (RBE_RIGHT(tmp) == NULL ||
+			     RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
+				RBE_COLOR(tmp) = RB_RED;
+				rbe = parent;
+				parent = RBE_PARENT(rbe);
+			} else {
+				if (RBE_LEFT(tmp) == NULL ||
+				    RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
+					struct rb_entry *oright;
+
+					oright = RBE_RIGHT(tmp);
+					if (oright != NULL)
+						RBE_COLOR(oright) = RB_BLACK;
+
+					RBE_COLOR(tmp) = RB_RED;
+					rbe_rotate_left(t, rbt, tmp);
+					tmp = RBE_LEFT(parent);
+				}
+
+				RBE_COLOR(tmp) = RBE_COLOR(parent);
+				RBE_COLOR(parent) = RB_BLACK;
+				if (RBE_LEFT(tmp) != NULL)
+					RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
+
+				rbe_rotate_right(t, rbt, parent);
+				rbe = RBH_ROOT(rbt);
+				break;
+			}
+		}
+	}
+
+	if (rbe != NULL)
+		RBE_COLOR(rbe) = RB_BLACK;
+}
+
+static inline struct rb_entry *
+rbe_remove(const struct rb_type *t, struct rb_tree *rbt, struct rb_entry *rbe)
+{
+	struct rb_entry *child, *parent, *old = rbe;
+	unsigned int color;
+
+	if (RBE_LEFT(rbe) == NULL)
+		child = RBE_RIGHT(rbe);
+	else if (RBE_RIGHT(rbe) == NULL)
+		child = RBE_LEFT(rbe);
+	else {
+		struct rb_entry *tmp;
+
+		rbe = RBE_RIGHT(rbe);
+		while ((tmp = RBE_LEFT(rbe)) != NULL)
+			rbe = tmp;
+
+		child = RBE_RIGHT(rbe);
+		parent = RBE_PARENT(rbe);
+		color = RBE_COLOR(rbe);
+		if (child != NULL)
+			RBE_PARENT(child) = parent;
+		if (parent != NULL) {
+			if (RBE_LEFT(parent) == rbe)
+				RBE_LEFT(parent) = child;
+			else
+				RBE_RIGHT(parent) = child;
+
+			rbe_if_augment(t, parent);
+		} else
+			RBH_ROOT(rbt) = child;
+		if (RBE_PARENT(rbe) == old)
+			parent = rbe;
+		*rbe = *old;
+
+		tmp = RBE_PARENT(old);
+		if (tmp != NULL) {
+			if (RBE_LEFT(tmp) == old)
+				RBE_LEFT(tmp) = rbe;
+			else
+				RBE_RIGHT(tmp) = rbe;
+
+			rbe_if_augment(t, parent);
+		} else
+			RBH_ROOT(rbt) = rbe;
+
+		RBE_PARENT(RBE_LEFT(old)) = rbe;
+		if (RBE_RIGHT(old))
+			RBE_PARENT(RBE_RIGHT(old)) = rbe;
+
+		if (t->t_augment != NULL && parent != NULL) {
+			tmp = parent;
+			do {
+				rbe_augment(t, tmp);
+				tmp = RBE_PARENT(tmp);
+			} while (tmp != NULL);
+		}
+
+		goto color;
+	}
+
+	parent = RBE_PARENT(rbe);
+	color = RBE_COLOR(rbe);
+
+	if (child != NULL)
+		RBE_PARENT(child) = parent;
+	if (parent != NULL) {
+		if (RBE_LEFT(parent) == rbe)
+			RBE_LEFT(parent) = child;
+		else
+			RBE_RIGHT(parent) = child;
+
+		rbe_if_augment(t, parent);
+	} else
+		RBH_ROOT(rbt) = child;
+color:
+	if (color == RB_BLACK)
+		rbe_remove_color(t, rbt, parent, child);
+
+	return (old);
+}
+
+void *
+_rb_remove(const struct rb_type *t, struct rb_tree *rbt, void *elm)
+{
+	struct rb_entry *rbe = rb_n2e(t, elm);
+	struct rb_entry *old;
+
+	old = rbe_remove(t, rbt, rbe);
+
+	return (old == NULL ? NULL : rb_e2n(t, old));
+}
+
+void *
+_rb_insert(const struct rb_type *t, struct rb_tree *rbt, void *elm)
+{
+	struct rb_entry *rbe = rb_n2e(t, elm);
+	struct rb_entry *tmp;
+	struct rb_entry *parent = NULL;
+	void *node;
+	int comp = 0;
+
+	tmp = RBH_ROOT(rbt);
+	while (tmp != NULL) {
+		parent = tmp;
+
+		node = rb_e2n(t, tmp);
+		comp = (*t->t_compare)(elm, node);
+		if (comp < 0)
+			tmp = RBE_LEFT(tmp);
+		else if (comp > 0)
+			tmp = RBE_RIGHT(tmp);
+		else
+			return (node);
+	}
+
+	rbe_set(rbe, parent);
+
+	if (parent != NULL) {
+		if (comp < 0)
+			RBE_LEFT(parent) = rbe;
+		else
+			RBE_RIGHT(parent) = rbe;
+
+		rbe_if_augment(t, parent);
+	} else
+		RBH_ROOT(rbt) = rbe;
+
+	rbe_insert_color(t, rbt, rbe);
+
+	return (NULL);
+}
+
+/* Finds the node with the same key as elm */
+void *
+_rb_find(const struct rb_type *t, struct rb_tree *rbt, const void *key)
+{
+	struct rb_entry *tmp = RBH_ROOT(rbt);
+	void *node;
+	int comp;
+
+	while (tmp != NULL) {
+		node = rb_e2n(t, tmp);
+		comp = (*t->t_compare)(key, node);
+		if (comp < 0)
+			tmp = RBE_LEFT(tmp);
+		else if (comp > 0)
+			tmp = RBE_RIGHT(tmp);
+		else
+			return (node);
+	}
+
+	return (NULL);
+}
+
+/* Finds the first node greater than or equal to the search key */
+void *
+_rb_nfind(const struct rb_type *t, struct rb_tree *rbt, const void *key)
+{
+	struct rb_entry *tmp = RBH_ROOT(rbt);
+	void *node;
+	void *res = NULL;
+	int comp;
+
+	while (tmp != NULL) {
+		node = rb_e2n(t, tmp);
+		comp = (*t->t_compare)(key, node);
+		if (comp < 0) {
+			res = node;
+			tmp = RBE_LEFT(tmp);
+		} else if (comp > 0)
+			tmp = RBE_RIGHT(tmp);
+		else
+			return (node);
+	}
+
+	return (res);
+}
+
+void *
+_rb_next(const struct rb_type *t, void *elm)
+{
+	struct rb_entry *rbe = rb_n2e(t, elm);
+
+	if (RBE_RIGHT(rbe) != NULL) {
+		rbe = RBE_RIGHT(rbe);
+		while (RBE_LEFT(rbe) != NULL)
+			rbe = RBE_LEFT(rbe);
+	} else {
+		if (RBE_PARENT(rbe) &&
+		    (rbe == RBE_LEFT(RBE_PARENT(rbe))))
+			rbe = RBE_PARENT(rbe);
+		else {
+			while (RBE_PARENT(rbe) &&
+			    (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
+				rbe = RBE_PARENT(rbe);
+			rbe = RBE_PARENT(rbe);
+		}
+	}
+
+	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
+}
+
+void *
+_rb_prev(const struct rb_type *t, void *elm)
+{
+	struct rb_entry *rbe = rb_n2e(t, elm);
+
+	if (RBE_LEFT(rbe)) {
+		rbe = RBE_LEFT(rbe);
+		while (RBE_RIGHT(rbe))
+			rbe = RBE_RIGHT(rbe);
+	} else {
+		if (RBE_PARENT(rbe) &&
+		    (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
+			rbe = RBE_PARENT(rbe);
+		else {
+			while (RBE_PARENT(rbe) &&
+			    (rbe == RBE_LEFT(RBE_PARENT(rbe))))
+				rbe = RBE_PARENT(rbe);
+			rbe = RBE_PARENT(rbe);
+		}
+	}
+
+	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
+}
+
+void *
+_rb_root(const struct rb_type *t, struct rb_tree *rbt)
+{
+	struct rb_entry *rbe = RBH_ROOT(rbt);
+
+	return (rbe == NULL ? rbe : rb_e2n(t, rbe));
+}
+
+void *
+_rb_min(const struct rb_type *t, struct rb_tree *rbt)
+{
+	struct rb_entry *rbe = RBH_ROOT(rbt);
+	struct rb_entry *parent = NULL;
+
+	while (rbe != NULL) {
+		parent = rbe;
+		rbe = RBE_LEFT(rbe);
+	}
+
+	return (parent == NULL ? NULL : rb_e2n(t, parent));
+}
+
+void *
+_rb_max(const struct rb_type *t, struct rb_tree *rbt)
+{
+	struct rb_entry *rbe = RBH_ROOT(rbt);
+	struct rb_entry *parent = NULL;
+
+	while (rbe != NULL) {
+		parent = rbe;
+		rbe = RBE_RIGHT(rbe);
+	}
+
+	return (parent == NULL ? NULL : rb_e2n(t, parent));
+}
+
+void *
+_rb_left(const struct rb_type *t, void *node)
+{
+	struct rb_entry *rbe = rb_n2e(t, node);
+	rbe = RBE_LEFT(rbe);
+	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
+}
+
+void *
+_rb_right(const struct rb_type *t, void *node)
+{
+	struct rb_entry *rbe = rb_n2e(t, node);
+	rbe = RBE_RIGHT(rbe);
+	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
+}
+
+void *
+_rb_parent(const struct rb_type *t, void *node)
+{
+	struct rb_entry *rbe = rb_n2e(t, node);
+	rbe = RBE_PARENT(rbe);
+	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
+}
+
+void
+_rb_set_left(const struct rb_type *t, void *node, void *left)
+{
+	struct rb_entry *rbe = rb_n2e(t, node);
+	struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left);
+
+	RBE_LEFT(rbe) = rbl;
+}
+
+void
+_rb_set_right(const struct rb_type *t, void *node, void *right)
+{
+	struct rb_entry *rbe = rb_n2e(t, node);
+	struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right);
+
+	RBE_RIGHT(rbe) = rbr;
+}
+
+void
+_rb_set_parent(const struct rb_type *t, void *node, void *parent)
+{
+	struct rb_entry *rbe = rb_n2e(t, node);
+	struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent);
+
+	RBE_PARENT(rbe) = rbp;
+}
+
+void
+_rb_poison(const struct rb_type *t, void *node, unsigned long poison)
+{
+	struct rb_entry *rbe = rb_n2e(t, node);
+
+	RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
+	    (struct rb_entry *)poison;
+}
+
+int
+_rb_check(const struct rb_type *t, void *node, unsigned long poison)
+{
+	struct rb_entry *rbe = rb_n2e(t, node);
+
+	return ((unsigned long)RBE_PARENT(rbe) == poison &&
+	    (unsigned long)RBE_LEFT(rbe) == poison &&
+	    (unsigned long)RBE_RIGHT(rbe) == poison);
+}
diff --git a/lib/openbsd-tree.h b/lib/openbsd-tree.h
index e6502b1e7..8cf1a3df7 100644
--- a/lib/openbsd-tree.h
+++ b/lib/openbsd-tree.h
@@ -287,462 +287,266 @@ void name##_SPLAY_MINMAX(struct name *head, int __comp) \
 	     (x) != NULL;						\
 	     (x) = SPLAY_NEXT(name, head, x))
 
-/* Macros that define a red-black tree */
-#define RB_HEAD(name, type)						\
-struct name {								\
-	struct type *rbh_root; /* root of the tree */			\
-}
-
-#define RB_INITIALIZER(root)						\
-	{ NULL }
-
-#define RB_INIT(root) do {						\
-	(root)->rbh_root = NULL;					\
-} while (0)
+/*
+ * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
 
 #define RB_BLACK	0
 #define RB_RED		1
-#define RB_ENTRY(type)							\
-struct {								\
-	struct type *rbe_left;		/* left element */		\
-	struct type *rbe_right;		/* right element */		\
-	struct type *rbe_parent;	/* parent element */		\
-	int rbe_color;			/* node color */		\
-}
-
-#define RB_LEFT(elm, field)		(elm)->field.rbe_left
-#define RB_RIGHT(elm, field)		(elm)->field.rbe_right
-#define RB_PARENT(elm, field)		(elm)->field.rbe_parent
-#define RB_COLOR(elm, field)		(elm)->field.rbe_color
-#define RB_ROOT(head)			(head)->rbh_root
-#define RB_EMPTY(head)			(RB_ROOT(head) == NULL)
-
-#define RB_SET(elm, parent, field) do {					\
-	RB_PARENT(elm, field) = parent;					\
-	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;		\
-	RB_COLOR(elm, field) = RB_RED;					\
-} while (0)
 
-#define RB_SET_BLACKRED(black, red, field) do {				\
-	RB_COLOR(black, field) = RB_BLACK;				\
-	RB_COLOR(red, field) = RB_RED;					\
-} while (0)
+struct rb_type {
+	int		(*t_compare)(const void *, const void *);
+	void		(*t_augment)(void *);
+	unsigned int	  t_offset;	/* offset of rb_entry in type */
+};
+
+struct rb_tree {
+	struct rb_entry	*rbt_root;
+};
+
+struct rb_entry {
+	struct rb_entry	 *rbt_parent;
+	struct rb_entry	 *rbt_left;
+	struct rb_entry	 *rbt_right;
+	unsigned int	  rbt_color;
+};
+
+#define RB_HEAD(_name, _type)						\
+struct _name {								\
+	struct rb_tree rbh_root;					\
+}
 
-#ifndef RB_AUGMENT
-#define RB_AUGMENT(x)	do {} while (0)
-#endif
+#define RB_ENTRY(_type)	struct rb_entry
 
-#define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
-	(tmp) = RB_RIGHT(elm, field);					\
-	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {		\
-		RB_PARENT(RB_LEFT(tmp, field), field) = (elm);		\
-	}								\
-	RB_AUGMENT(elm);						\
-	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {		\
-		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
-			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
-		else							\
-			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
-	} else								\
-		(head)->rbh_root = (tmp);				\
-	RB_LEFT(tmp, field) = (elm);					\
-	RB_PARENT(elm, field) = (tmp);					\
-	RB_AUGMENT(tmp);						\
-	if ((RB_PARENT(tmp, field)))					\
-		RB_AUGMENT(RB_PARENT(tmp, field));			\
-} while (0)
+static inline void
+_rb_init(struct rb_tree *rbt)
+{
+	rbt->rbt_root = NULL;
+}
 
-#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
-	(tmp) = RB_LEFT(elm, field);					\
-	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {		\
-		RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);		\
-	}								\
-	RB_AUGMENT(elm);						\
-	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {		\
-		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
-			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
-		else							\
-			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
-	} else								\
-		(head)->rbh_root = (tmp);				\
-	RB_RIGHT(tmp, field) = (elm);					\
-	RB_PARENT(elm, field) = (tmp);					\
-	RB_AUGMENT(tmp);						\
-	if ((RB_PARENT(tmp, field)))					\
-		RB_AUGMENT(RB_PARENT(tmp, field));			\
-} while (0)
+static inline int
+_rb_empty(struct rb_tree *rbt)
+{
+	return (rbt->rbt_root == NULL);
+}
 
-/* Generates prototypes and inline functions */
-#define	RB_PROTOTYPE(name, type, field, cmp)				\
-	RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
-#define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\
-	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
-#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\
-attr void name##_RB_INSERT_COLOR(struct name *, struct type *);		\
-attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
-attr struct type *name##_RB_REMOVE(struct name *, struct type *);	\
-attr struct type *name##_RB_INSERT(struct name *, struct type *);	\
-attr struct type *name##_RB_FIND(struct name *, struct type *);		\
-attr struct type *name##_RB_NFIND(struct name *, struct type *);	\
-attr struct type *name##_RB_NEXT(struct type *);			\
-attr struct type *name##_RB_PREV(struct type *);			\
-attr struct type *name##_RB_MINMAX(struct name *, int);			\
+void	*_rb_insert(const struct rb_type *, struct rb_tree *, void *);
+void	*_rb_remove(const struct rb_type *, struct rb_tree *, void *);
+void	*_rb_find(const struct rb_type *, struct rb_tree *, const void *);
+void	*_rb_nfind(const struct rb_type *, struct rb_tree *, const void *);
+void	*_rb_root(const struct rb_type *, struct rb_tree *);
+void	*_rb_min(const struct rb_type *, struct rb_tree *);
+void	*_rb_max(const struct rb_type *, struct rb_tree *);
+void	*_rb_next(const struct rb_type *, void *);
+void	*_rb_prev(const struct rb_type *, void *);
+void	*_rb_left(const struct rb_type *, void *);
+void	*_rb_right(const struct rb_type *, void *);
+void	*_rb_parent(const struct rb_type *, void *);
+void	 _rb_set_left(const struct rb_type *, void *, void *);
+void	 _rb_set_right(const struct rb_type *, void *, void *);
+void	 _rb_set_parent(const struct rb_type *, void *, void *);
+void	 _rb_poison(const struct rb_type *, void *, unsigned long);
+int	 _rb_check(const struct rb_type *, void *, unsigned long);
+
+#define RB_INITIALIZER(_head)	{ { NULL } }
+
+#ifndef __unused
+#define __unused __attribute__((__unused__))
+#endif /* __unused */
+
+#define RB_PROTOTYPE(_name, _type, _field, _cmp)			\
+extern const struct rb_type *const _name##_RB_TYPE;			\
 									\
-
-/* Main rb operation.
- * Moves node close to the key of elm to top
- */
-#define	RB_GENERATE(name, type, field, cmp)				\
-	RB_GENERATE_INTERNAL(name, type, field, cmp,)
-#define	RB_GENERATE_STATIC(name, type, field, cmp)			\
-	RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
-#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\
-attr void								\
-name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
+__unused static inline void						\
+_name##_RB_INIT(struct _name *head)					\
 {									\
-	struct type *parent, *gparent, *tmp;				\
-	while ((parent = RB_PARENT(elm, field)) &&			\
-	    RB_COLOR(parent, field) == RB_RED) {			\
-		gparent = RB_PARENT(parent, field);			\
-		if (parent == RB_LEFT(gparent, field)) {		\
-			tmp = RB_RIGHT(gparent, field);			\
-			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
-				RB_COLOR(tmp, field) = RB_BLACK;	\
-				RB_SET_BLACKRED(parent, gparent, field);\
-				elm = gparent;				\
-				continue;				\
-			}						\
-			if (RB_RIGHT(parent, field) == elm) {		\
-				RB_ROTATE_LEFT(head, parent, tmp, field);\
-				tmp = parent;				\
-				parent = elm;				\
-				elm = tmp;				\
-			}						\
-			RB_SET_BLACKRED(parent, gparent, field);	\
-			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\
-		} else {						\
-			tmp = RB_LEFT(gparent, field);			\
-			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
-				RB_COLOR(tmp, field) = RB_BLACK;	\
-				RB_SET_BLACKRED(parent, gparent, field);\
-				elm = gparent;				\
-				continue;				\
-			}						\
-			if (RB_LEFT(parent, field) == elm) {		\
-				RB_ROTATE_RIGHT(head, parent, tmp, field);\
-				tmp = parent;				\
-				parent = elm;				\
-				elm = tmp;				\
-			}						\
-			RB_SET_BLACKRED(parent, gparent, field);	\
-			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
-		}							\
-	}								\
-	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
+	_rb_init(&head->rbh_root);					\
 }									\
 									\
-attr void								\
-name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
+__unused static inline struct _type *					\
+_name##_RB_INSERT(struct _name *head, struct _type *elm)		\
 {									\
-	struct type *tmp;						\
-	while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&	\
-	    elm != RB_ROOT(head)) {					\
-		if (RB_LEFT(parent, field) == elm) {			\
-			tmp = RB_RIGHT(parent, field);			\
-			if (RB_COLOR(tmp, field) == RB_RED) {		\
-				RB_SET_BLACKRED(tmp, parent, field);	\
-				RB_ROTATE_LEFT(head, parent, tmp, field);\
-				tmp = RB_RIGHT(parent, field);		\
-			}						\
-			if ((RB_LEFT(tmp, field) == NULL ||		\
-			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
-			    (RB_RIGHT(tmp, field) == NULL ||		\
-			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
-				RB_COLOR(tmp, field) = RB_RED;		\
-				elm = parent;				\
-				parent = RB_PARENT(elm, field);		\
-			} else {					\
-				if (RB_RIGHT(tmp, field) == NULL ||	\
-				    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
-					struct type *oleft;		\
-					if ((oleft = RB_LEFT(tmp, field)))\
-						RB_COLOR(oleft, field) = RB_BLACK;\
-					RB_COLOR(tmp, field) = RB_RED;	\
-					RB_ROTATE_RIGHT(head, tmp, oleft, field);\
-					tmp = RB_RIGHT(parent, field);	\
-				}					\
-				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
-				RB_COLOR(parent, field) = RB_BLACK;	\
-				if (RB_RIGHT(tmp, field))		\
-					RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
-				RB_ROTATE_LEFT(head, parent, tmp, field);\
-				elm = RB_ROOT(head);			\
-				break;					\
-			}						\
-		} else {						\
-			tmp = RB_LEFT(parent, field);			\
-			if (RB_COLOR(tmp, field) == RB_RED) {		\
-				RB_SET_BLACKRED(tmp, parent, field);	\
-				RB_ROTATE_RIGHT(head, parent, tmp, field);\
-				tmp = RB_LEFT(parent, field);		\
-			}						\
-			if ((RB_LEFT(tmp, field) == NULL ||		\
-			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
-			    (RB_RIGHT(tmp, field) == NULL ||		\
-			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
-				RB_COLOR(tmp, field) = RB_RED;		\
-				elm = parent;				\
-				parent = RB_PARENT(elm, field);		\
-			} else {					\
-				if (RB_LEFT(tmp, field) == NULL ||	\
-				    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
-					struct type *oright;		\
-					if ((oright = RB_RIGHT(tmp, field)))\
-						RB_COLOR(oright, field) = RB_BLACK;\
-					RB_COLOR(tmp, field) = RB_RED;	\
-					RB_ROTATE_LEFT(head, tmp, oright, field);\
-					tmp = RB_LEFT(parent, field);	\
-				}					\
-				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
-				RB_COLOR(parent, field) = RB_BLACK;	\
-				if (RB_LEFT(tmp, field))		\
-					RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
-				RB_ROTATE_RIGHT(head, parent, tmp, field);\
-				elm = RB_ROOT(head);			\
-				break;					\
-			}						\
-		}							\
-	}								\
-	if (elm)							\
-		RB_COLOR(elm, field) = RB_BLACK;			\
+	return _rb_insert(_name##_RB_TYPE, &head->rbh_root, elm);	\
 }									\
 									\
-attr struct type *							\
-name##_RB_REMOVE(struct name *head, struct type *elm)			\
+__unused static inline struct _type *					\
+_name##_RB_REMOVE(struct _name *head, struct _type *elm)		\
 {									\
-	struct type *child, *parent, *old = elm;			\
-	int color;							\
-	if (RB_LEFT(elm, field) == NULL)				\
-		child = RB_RIGHT(elm, field);				\
-	else if (RB_RIGHT(elm, field) == NULL)				\
-		child = RB_LEFT(elm, field);				\
-	else {								\
-		struct type *left;					\
-		elm = RB_RIGHT(elm, field);				\
-		while ((left = RB_LEFT(elm, field)))			\
-			elm = left;					\
-		child = RB_RIGHT(elm, field);				\
-		parent = RB_PARENT(elm, field);				\
-		color = RB_COLOR(elm, field);				\
-		if (child)						\
-			RB_PARENT(child, field) = parent;		\
-		if (parent) {						\
-			if (RB_LEFT(parent, field) == elm)		\
-				RB_LEFT(parent, field) = child;		\
-			else						\
-				RB_RIGHT(parent, field) = child;	\
-			RB_AUGMENT(parent);				\
-		} else							\
-			RB_ROOT(head) = child;				\
-		if (RB_PARENT(elm, field) == old)			\
-			parent = elm;					\
-		(elm)->field = (old)->field;				\
-		if (RB_PARENT(old, field)) {				\
-			if (RB_LEFT(RB_PARENT(old, field), field) == old)\
-				RB_LEFT(RB_PARENT(old, field), field) = elm;\
-			else						\
-				RB_RIGHT(RB_PARENT(old, field), field) = elm;\
-			RB_AUGMENT(RB_PARENT(old, field));		\
-		} else							\
-			RB_ROOT(head) = elm;				\
-		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
-		if (RB_RIGHT(old, field))				\
-			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
-		if (parent) {						\
-			left = parent;					\
-			do {						\
-				RB_AUGMENT(left);			\
-			} while ((left = RB_PARENT(left, field)));	\
-		}							\
-		goto color;						\
-	}								\
-	parent = RB_PARENT(elm, field);					\
-	color = RB_COLOR(elm, field);					\
-	if (child)							\
-		RB_PARENT(child, field) = parent;			\
-	if (parent) {							\
-		if (RB_LEFT(parent, field) == elm)			\
-			RB_LEFT(parent, field) = child;			\
-		else							\
-			RB_RIGHT(parent, field) = child;		\
-		RB_AUGMENT(parent);					\
-	} else								\
-		RB_ROOT(head) = child;					\
-color:									\
-	if (color == RB_BLACK)						\
-		name##_RB_REMOVE_COLOR(head, parent, child);		\
-	return (old);							\
+	return _rb_remove(_name##_RB_TYPE, &head->rbh_root, elm);	\
 }									\
 									\
-/* Inserts a node into the RB tree */					\
-attr struct type *							\
-name##_RB_INSERT(struct name *head, struct type *elm)			\
+__unused static inline struct _type *					\
+_name##_RB_FIND(struct _name *head, const struct _type *key)		\
 {									\
-	struct type *tmp;						\
-	struct type *parent = NULL;					\
-	int comp = 0;							\
-	tmp = RB_ROOT(head);						\
-	while (tmp) {							\
-		parent = tmp;						\
-		comp = (cmp)(elm, parent);				\
-		if (comp < 0)						\
-			tmp = RB_LEFT(tmp, field);			\
-		else if (comp > 0)					\
-			tmp = RB_RIGHT(tmp, field);			\
-		else							\
-			return (tmp);					\
-	}								\
-	RB_SET(elm, parent, field);					\
-	if (parent != NULL) {						\
-		if (comp < 0)						\
-			RB_LEFT(parent, field) = elm;			\
-		else							\
-			RB_RIGHT(parent, field) = elm;			\
-		RB_AUGMENT(parent);					\
-	} else								\
-		RB_ROOT(head) = elm;					\
-	name##_RB_INSERT_COLOR(head, elm);				\
-	return (NULL);							\
+	return _rb_find(_name##_RB_TYPE, &head->rbh_root, key);	\
 }									\
 									\
-/* Finds the node with the same key as elm */				\
-attr struct type *							\
-name##_RB_FIND(struct name *head, struct type *elm)			\
+__unused static inline struct _type *					\
+_name##_RB_NFIND(struct _name *head, const struct _type *key)		\
 {									\
-	struct type *tmp = RB_ROOT(head);				\
-	int comp;							\
-	while (tmp) {							\
-		comp = cmp(elm, tmp);					\
-		if (comp < 0)						\
-			tmp = RB_LEFT(tmp, field);			\
-		else if (comp > 0)					\
-			tmp = RB_RIGHT(tmp, field);			\
-		else							\
-			return (tmp);					\
-	}								\
-	return (NULL);							\
+	return _rb_nfind(_name##_RB_TYPE, &head->rbh_root, key);	\
 }									\
 									\
-/* Finds the first node greater than or equal to the search key */	\
-attr struct type *							\
-name##_RB_NFIND(struct name *head, struct type *elm)			\
+__unused static inline struct _type *					\
+_name##_RB_ROOT(struct _name *head)					\
 {									\
-	struct type *tmp = RB_ROOT(head);				\
-	struct type *res = NULL;					\
-	int comp;							\
-	while (tmp) {							\
-		comp = cmp(elm, tmp);					\
-		if (comp < 0) {						\
-			res = tmp;					\
-			tmp = RB_LEFT(tmp, field);			\
-		}							\
-		else if (comp > 0)					\
-			tmp = RB_RIGHT(tmp, field);			\
-		else							\
-			return (tmp);					\
-	}								\
-	return (res);							\
+	return _rb_root(_name##_RB_TYPE, &head->rbh_root);		\
 }									\
 									\
-/* ARGSUSED */								\
-attr struct type *							\
-name##_RB_NEXT(struct type *elm)					\
+__unused static inline int						\
+_name##_RB_EMPTY(struct _name *head)					\
 {									\
-	if (RB_RIGHT(elm, field)) {					\
-		elm = RB_RIGHT(elm, field);				\
-		while (RB_LEFT(elm, field))				\
-			elm = RB_LEFT(elm, field);			\
-	} else {							\
-		if (RB_PARENT(elm, field) &&				\
-		    (elm == RB_LEFT(RB_PARENT(elm, field), field)))	\
-			elm = RB_PARENT(elm, field);			\
-		else {							\
-			while (RB_PARENT(elm, field) &&			\
-			    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
-				elm = RB_PARENT(elm, field);		\
-			elm = RB_PARENT(elm, field);			\
-		}							\
-	}								\
-	return (elm);							\
+	return _rb_empty(&head->rbh_root);				\
 }									\
 									\
-/* ARGSUSED */								\
-attr struct type *							\
-name##_RB_PREV(struct type *elm)					\
+__unused static inline struct _type *					\
+_name##_RB_MIN(struct _name *head)					\
 {									\
-	if (RB_LEFT(elm, field)) {					\
-		elm = RB_LEFT(elm, field);				\
-		while (RB_RIGHT(elm, field))				\
-			elm = RB_RIGHT(elm, field);			\
-	} else {							\
-		if (RB_PARENT(elm, field) &&				\
-		    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))	\
-			elm = RB_PARENT(elm, field);			\
-		else {							\
-			while (RB_PARENT(elm, field) &&			\
-			    (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
-				elm = RB_PARENT(elm, field);		\
-			elm = RB_PARENT(elm, field);			\
-		}							\
-	}								\
-	return (elm);							\
+	return _rb_min(_name##_RB_TYPE, &head->rbh_root);		\
 }									\
 									\
-attr struct type *							\
-name##_RB_MINMAX(struct name *head, int val)				\
+__unused static inline struct _type *					\
+_name##_RB_MAX(struct _name *head)					\
 {									\
-	struct type *tmp = RB_ROOT(head);				\
-	struct type *parent = NULL;					\
-	while (tmp) {							\
-		parent = tmp;						\
-		if (val < 0)						\
-			tmp = RB_LEFT(tmp, field);			\
-		else							\
-			tmp = RB_RIGHT(tmp, field);			\
-	}								\
-	return (parent);						\
+	return _rb_max(_name##_RB_TYPE, &head->rbh_root);		\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_RB_NEXT(struct _type *elm)					\
+{									\
+	return _rb_next(_name##_RB_TYPE, elm);				\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_RB_PREV(struct _type *elm)					\
+{									\
+	return _rb_prev(_name##_RB_TYPE, elm);				\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_RB_LEFT(struct _type *elm)					\
+{									\
+	return _rb_left(_name##_RB_TYPE, elm);				\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_RB_RIGHT(struct _type *elm)					\
+{									\
+	return _rb_right(_name##_RB_TYPE, elm);			\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_RB_PARENT(struct _type *elm)					\
+{									\
+	return _rb_parent(_name##_RB_TYPE, elm);			\
+}									\
+									\
+__unused static inline void						\
+_name##_RB_SET_LEFT(struct _type *elm, struct _type *left)		\
+{									\
+	return _rb_set_left(_name##_RB_TYPE, elm, left);		\
+}									\
+									\
+__unused static inline void						\
+_name##_RB_SET_RIGHT(struct _type *elm, struct _type *right)		\
+{									\
+	return _rb_set_right(_name##_RB_TYPE, elm, right);		\
+}									\
+									\
+__unused static inline void						\
+_name##_RB_SET_PARENT(struct _type *elm, struct _type *parent)		\
+{									\
+	return _rb_set_parent(_name##_RB_TYPE, elm, parent);		\
+}									\
+									\
+__unused static inline void						\
+_name##_RB_POISON(struct _type *elm, unsigned long poison)		\
+{									\
+	return _rb_poison(_name##_RB_TYPE, elm, poison);		\
+}									\
+									\
+__unused static inline int						\
+_name##_RB_CHECK(struct _type *elm, unsigned long poison)		\
+{									\
+	return _rb_check(_name##_RB_TYPE, elm, poison);		\
 }
 
-#define RB_NEGINF	-1
-#define RB_INF	1
-
-#define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)
-#define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)
-#define RB_FIND(name, x, y)	name##_RB_FIND(x, y)
-#define RB_NFIND(name, x, y)	name##_RB_NFIND(x, y)
-#define RB_NEXT(name, x, y)	name##_RB_NEXT(y)
-#define RB_PREV(name, x, y)	name##_RB_PREV(y)
-#define RB_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)
-#define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)
-
-#define RB_FOREACH(x, name, head)					\
-	for ((x) = RB_MIN(name, head);					\
-	     (x) != NULL;						\
-	     (x) = name##_RB_NEXT(x))
-
-#define RB_FOREACH_SAFE(x, name, head, y)				\
-	for ((x) = RB_MIN(name, head);					\
-	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1);		\
-	     (x) = (y))
-
-#define RB_FOREACH_REVERSE(x, name, head)				\
-	for ((x) = RB_MAX(name, head);					\
-	     (x) != NULL;						\
-	     (x) = name##_RB_PREV(x))
-
-#define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\
-	for ((x) = RB_MAX(name, head);					\
-	    ((x) != NULL) && ((y) = name##_RB_PREV(x), 1);		\
-	     (x) = (y))
+#define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug)		\
+static int								\
+_name##_RB_COMPARE(const void *lptr, const void *rptr)			\
+{									\
+	const struct _type *l = lptr, *r = rptr;			\
+	return _cmp(l, r);						\
+}									\
+static const struct rb_type _name##_RB_INFO = {			\
+	_name##_RB_COMPARE,						\
+	_aug,								\
+	offsetof(struct _type, _field),					\
+};									\
+const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO;
+
+#define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug)		\
+static void								\
+_name##_RB_AUGMENT(void *ptr)						\
+{									\
+	struct _type *p = ptr;						\
+	return _aug(p);							\
+}									\
+RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT)
+
+#define RB_GENERATE(_name, _type, _field, _cmp)			\
+    RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL)
+
+#define RB_INIT(_name, _head)		_name##_RB_INIT(_head)
+#define RB_INSERT(_name, _head, _elm)	_name##_RB_INSERT(_head, _elm)
+#define RB_REMOVE(_name, _head, _elm)	_name##_RB_REMOVE(_head, _elm)
+#define RB_FIND(_name, _head, _key)	_name##_RB_FIND(_head, _key)
+#define RB_NFIND(_name, _head, _key)	_name##_RB_NFIND(_head, _key)
+#define RB_ROOT(_name, _head)		_name##_RB_ROOT(_head)
+#define RB_EMPTY(_name, _head)		_name##_RB_EMPTY(_head)
+#define RB_MIN(_name, _head)		_name##_RB_MIN(_head)
+#define RB_MAX(_name, _head)		_name##_RB_MAX(_head)
+#define RB_NEXT(_name, _elm)		_name##_RB_NEXT(_elm)
+#define RB_PREV(_name, _elm)		_name##_RB_PREV(_elm)
+#define RB_LEFT(_name, _elm)		_name##_RB_LEFT(_elm)
+#define RB_RIGHT(_name, _elm)		_name##_RB_RIGHT(_elm)
+#define RB_PARENT(_name, _elm)		_name##_RB_PARENT(_elm)
+#define RB_SET_LEFT(_name, _elm, _l)	_name##_RB_SET_LEFT(_elm, _l)
+#define RB_SET_RIGHT(_name, _elm, _r)	_name##_RB_SET_RIGHT(_elm, _r)
+#define RB_SET_PARENT(_name, _elm, _p)	_name##_RB_SET_PARENT(_elm, _p)
+#define RB_POISON(_name, _elm, _p)	_name##_RB_POISON(_elm, _p)
+#define RB_CHECK(_name, _elm, _p)	_name##_RB_CHECK(_elm, _p)
+
+#define RB_FOREACH(_e, _name, _head)					\
+	for ((_e) = RB_MIN(_name, (_head));				\
+	     (_e) != NULL;						\
+	     (_e) = RB_NEXT(_name, (_e)))
+
+#define RB_FOREACH_SAFE(_e, _name, _head, _n)				\
+	for ((_e) = RB_MIN(_name, (_head));				\
+	     (_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1);	\
+	     (_e) = (_n))
+
+#define RB_FOREACH_REVERSE(_e, _name, _head)				\
+	for ((_e) = RB_MAX(_name, (_head));				\
+	     (_e) != NULL;						\
+	     (_e) = RB_PREV(_name, (_e)))
+
+#define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n)			\
+	for ((_e) = RB_MAX(_name, (_head));				\
+	     (_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1);	\
+	     (_e) = (_n))
 
 #endif	/* _SYS_TREE_H_ */
diff --git a/lib/vrf.c b/lib/vrf.c
index c4e527db5..42debe5f1 100644
--- a/lib/vrf.c
+++ b/lib/vrf.c
@@ -35,11 +35,11 @@ DEFINE_MTYPE_STATIC(LIB, VRF_BITMAP, "VRF bit-map")
 
 DEFINE_QOBJ_TYPE(vrf)
 
-static __inline int vrf_id_compare (struct vrf *, struct vrf *);
-static __inline int vrf_name_compare (struct vrf *, struct vrf *);
+static __inline int vrf_id_compare (const struct vrf *, const struct vrf *);
+static __inline int vrf_name_compare (const struct vrf *, const struct vrf *);
 
-RB_GENERATE (vrf_id_head, vrf, id_entry, vrf_id_compare)
-RB_GENERATE (vrf_name_head, vrf, name_entry, vrf_name_compare)
+RB_GENERATE (vrf_id_head, vrf, id_entry, vrf_id_compare);
+RB_GENERATE (vrf_name_head, vrf, name_entry, vrf_name_compare);
 
 struct vrf_id_head vrfs_by_id = RB_INITIALIZER (&vrfs_by_id);
 struct vrf_name_head vrfs_by_name = RB_INITIALIZER (&vrfs_by_name);
@@ -72,13 +72,13 @@ vrf_lookup_by_name (const char *name)
 }
 
 static __inline int
-vrf_id_compare (struct vrf *a, struct vrf *b)
+vrf_id_compare (const struct vrf *a, const struct vrf *b)
 {
   return (a->vrf_id - b->vrf_id);
 }
 
 static int
-vrf_name_compare (struct vrf *a, struct vrf *b)
+vrf_name_compare (const struct vrf *a, const struct vrf *b)
 {
   return strcmp (a->name, b->name);
 }
@@ -419,9 +419,9 @@ vrf_terminate (void)
   if (debug_vrf)
     zlog_debug ("%s: Shutting down vrf subsystem", __PRETTY_FUNCTION__);
 
-  while ((vrf = RB_ROOT (&vrfs_by_id)) != NULL)
+  while ((vrf = RB_ROOT (vrf_id_head, &vrfs_by_id)) != NULL)
     vrf_delete (vrf);
-  while ((vrf = RB_ROOT (&vrfs_by_name)) != NULL)
+  while ((vrf = RB_ROOT (vrf_name_head, &vrfs_by_name)) != NULL)
     vrf_delete (vrf);
 }
 
diff --git a/zebra/zebra_rib.c b/zebra/zebra_rib.c
index e9ccac1c9..c2af0a0d2 100644
--- a/zebra/zebra_rib.c
+++ b/zebra/zebra_rib.c
@@ -2897,7 +2897,7 @@ vrf_id_get_next (vrf_id_t vrf_id, vrf_id_t *next_id_p)
   vrf = vrf_lookup_by_id (vrf_id);
   if (vrf)
     {
-      vrf = RB_NEXT (vrf_id_head, &vrfs_by_id, vrf);
+      vrf = RB_NEXT (vrf_id_head, vrf);
       if (vrf) {
 	  *next_id_p = vrf->vrf_id;
 	  return 1;