Index: lib/libc/Makefile.inc
===================================================================
RCS file: /cvs/src/lib/libc/Makefile.inc,v
retrieving revision 1.29
diff -u -p -r1.29 Makefile.inc
--- lib/libc/Makefile.inc	7 May 2016 19:05:21 -0000	1.29
+++ lib/libc/Makefile.inc	18 Oct 2016 01:51:49 -0000
@@ -63,6 +63,7 @@ AINC+=  -nostdinc -idirafter ${DESTDIR}/
 .include "${LIBCSRCDIR}/termios/Makefile.inc"
 .include "${LIBCSRCDIR}/thread/Makefile.inc"
 .include "${LIBCSRCDIR}/time/Makefile.inc"
+.include "${LIBCSRCDIR}/tree/Makefile.inc"
 .include "${LIBCSRCDIR}/uuid/Makefile.inc"
 .include "${LIBCSRCDIR}/sys/Makefile.inc"
 .if (${YP:L} == "yes")
Index: lib/libc/shlib_version
===================================================================
RCS file: /cvs/src/lib/libc/shlib_version,v
retrieving revision 1.187
diff -u -p -r1.187 shlib_version
--- lib/libc/shlib_version	17 Sep 2016 20:13:48 -0000	1.187
+++ lib/libc/shlib_version	18 Oct 2016 01:51:49 -0000
@@ -1,4 +1,4 @@
 major=89
-minor=2
+minor=3
 # note: If changes were made to include/thread_private.h or if system
 # calls were added/changed then librthread/shlib_version also be updated.
Index: lib/libc/stdlib/malloc.c
===================================================================
RCS file: /cvs/src/lib/libc/stdlib/malloc.c,v
retrieving revision 1.202
diff -u -p -r1.202 malloc.c
--- lib/libc/stdlib/malloc.c	15 Oct 2016 18:24:40 -0000	1.202
+++ lib/libc/stdlib/malloc.c	18 Oct 2016 01:51:49 -0000
@@ -1781,18 +1781,19 @@ struct malloc_leak {
 };
 
 struct leaknode {
-	RB_ENTRY(leaknode) entry;
+	RBT_ENTRY(leaknode) entry;
 	struct malloc_leak d;
 };
 
-static int
-leakcmp(struct leaknode *e1, struct leaknode *e2)
+static inline int
+leakcmp(const struct leaknode *e1, const struct leaknode *e2)
 {
 	return e1->d.f < e2->d.f ? -1 : e1->d.f > e2->d.f;
 }
 
-static RB_HEAD(leaktree, leaknode) leakhead;
-RB_GENERATE_STATIC(leaktree, leaknode, entry, leakcmp)
+static RBT_HEAD(leaktree, leaknode) leakhead;
+RBT_PROTOTYPE(leaktree, leaknode, entry, leakcmp);
+RBT_GENERATE(leaktree, leaknode, entry, leakcmp);
 
 static void
 putleakinfo(void *f, size_t sz, int cnt)
@@ -1805,7 +1806,7 @@ putleakinfo(void *f, size_t sz, int cnt)
 		return;
 
 	key.d.f = f;
-	p = RB_FIND(leaktree, &leakhead, &key);
+	p = RBT_FIND(leaktree, &leakhead, &key);
 	if (p == NULL) {
 		if (page == NULL ||
 		    used >= MALLOC_PAGESIZE / sizeof(struct leaknode)) {
@@ -1818,7 +1819,7 @@ putleakinfo(void *f, size_t sz, int cnt)
 		p->d.f = f;
 		p->d.total_size = sz * cnt;
 		p->d.count = cnt;
-		RB_INSERT(leaktree, &leakhead, p);
+		RBT_INSERT(leaktree, &leakhead, p);
 	} else {
 		p->d.total_size += sz * cnt;
 		p->d.count += cnt;
@@ -1847,7 +1848,7 @@ dump_leaks(int fd)
 		malloc_leaks = MMAP(MALLOC_PAGESIZE);
 	if (malloc_leaks != MAP_FAILED)
 		memset(malloc_leaks, 0, MALLOC_PAGESIZE);
-	RB_FOREACH(p, leaktree, &leakhead) {
+	RBT_FOREACH(p, leaktree, &leakhead) {
 		snprintf(buf, sizeof(buf), "%18p %7zu %6u %6zu\n", p->d.f,
 		    p->d.total_size, p->d.count, p->d.total_size / p->d.count);
 		write(fd, buf, strlen(buf));
@@ -2012,7 +2013,7 @@ malloc_dump(int fd, struct dir_info *poo
 		pool->delayed_chunks[i] = NULL;
 	}
 	/* XXX leak when run multiple times */
-	RB_INIT(&leakhead);
+	RBT_INIT(leaktree, &leakhead);
 	malloc_dump1(fd, pool);
 	errno = saved_errno;
 }
Index: lib/libc/tree/Makefile.inc
===================================================================
RCS file: lib/libc/tree/Makefile.inc
diff -N lib/libc/tree/Makefile.inc
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ lib/libc/tree/Makefile.inc	18 Oct 2016 01:51:49 -0000
@@ -0,0 +1,6 @@
+#	$OpenBSD$
+
+# sources
+.PATH: ${LIBCSRCDIR}/tree
+
+SRCS+=	tree.c
Index: lib/libc/tree/tree.c
===================================================================
RCS file: lib/libc/tree/tree.c
diff -N lib/libc/tree/tree.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ lib/libc/tree/tree.c	18 Oct 2016 01:51:49 -0000
@@ -0,0 +1,627 @@
+/*	$OpenBSD: subr_tree.c,v 1.6 2016/09/20 01:11:27 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 <sys/tree.h>
+
+static inline void *
+rb_n2e(const struct rb_type *t, void *node)
+{
+	unsigned long addr = (unsigned long)node;
+
+	return ((void *)(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_BLACK		0
+#define RBE_RED			1
+
+#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) = RBE_RED;
+}
+
+static inline void
+rbe_set_blackred(struct rb_entry *black, struct rb_entry *red)
+{
+	RBE_COLOR(black) = RBE_BLACK;
+	RBE_COLOR(red) = RBE_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) == RBE_RED) {
+		gparent = RBE_PARENT(parent);
+
+		if (parent == RBE_LEFT(gparent)) {
+			tmp = RBE_RIGHT(gparent);
+			if (tmp != NULL && RBE_COLOR(tmp) == RBE_RED) {
+				RBE_COLOR(tmp) = RBE_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) == RBE_RED) {
+				RBE_COLOR(tmp) = RBE_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)) = RBE_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) == RBE_BLACK) &&
+	    rbe != RBH_ROOT(rbt)) {
+		if (RBE_LEFT(parent) == rbe) {
+			tmp = RBE_RIGHT(parent);
+			if (RBE_COLOR(tmp) == RBE_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)) == RBE_BLACK) &&
+			    (RBE_RIGHT(tmp) == NULL ||
+			     RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK)) {
+				RBE_COLOR(tmp) = RBE_RED;
+				rbe = parent;
+				parent = RBE_PARENT(rbe);
+			} else {
+				if (RBE_RIGHT(tmp) == NULL ||
+				    RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK) {
+					struct rb_entry *oleft;
+
+					oleft = RBE_LEFT(tmp);
+					if (oleft != NULL)
+						RBE_COLOR(oleft) = RBE_BLACK;
+
+					RBE_COLOR(tmp) = RBE_RED;
+					rbe_rotate_right(t, rbt, tmp);
+					tmp = RBE_RIGHT(parent);
+				}
+
+				RBE_COLOR(tmp) = RBE_COLOR(parent);
+				RBE_COLOR(parent) = RBE_BLACK;
+				if (RBE_RIGHT(tmp))
+					RBE_COLOR(RBE_RIGHT(tmp)) = RBE_BLACK;
+
+				rbe_rotate_left(t, rbt, parent);
+				rbe = RBH_ROOT(rbt);
+				break;
+			}
+		} else {
+			tmp = RBE_LEFT(parent);
+			if (RBE_COLOR(tmp) == RBE_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)) == RBE_BLACK) &&
+			    (RBE_RIGHT(tmp) == NULL ||
+			     RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK)) {
+				RBE_COLOR(tmp) = RBE_RED;
+				rbe = parent;
+				parent = RBE_PARENT(rbe);
+			} else {
+				if (RBE_LEFT(tmp) == NULL ||
+				    RBE_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) {
+					struct rb_entry *oright;
+
+					oright = RBE_RIGHT(tmp);
+					if (oright != NULL)
+						RBE_COLOR(oright) = RBE_BLACK;
+
+					RBE_COLOR(tmp) = RBE_RED;
+					rbe_rotate_left(t, rbt, tmp);
+					tmp = RBE_LEFT(parent);
+				}
+
+				RBE_COLOR(tmp) = RBE_COLOR(parent);
+				RBE_COLOR(parent) = RBE_BLACK;
+				if (RBE_LEFT(tmp) != NULL)
+					RBE_COLOR(RBE_LEFT(tmp)) = RBE_BLACK;
+
+				rbe_rotate_right(t, rbt, parent);
+				rbe = RBH_ROOT(rbt);
+				break;
+			}
+		}
+	}
+
+	if (rbe != NULL)
+		RBE_COLOR(rbe) = RBE_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 == RBE_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));
+}
+DEF_STRONG(_rb_remove);
+
+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);
+}
+DEF_STRONG(_rb_insert);
+
+/* 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);
+}
+DEF_STRONG(_rb_find);
+
+/* 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);
+}
+DEF_STRONG(_rb_nfind);
+
+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));
+}
+DEF_STRONG(_rb_next);
+
+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));
+}
+DEF_STRONG(_rb_prev);
+
+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));
+}
+DEF_STRONG(_rb_min);
+
+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));
+}
+DEF_STRONG(_rb_max);
+
+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));
+}
+DEF_STRONG(_rb_left);
+
+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));
+}
+DEF_STRONG(_rb_right);
+
+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));
+}
+DEF_STRONG(_rb_parent);
+
+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;
+}
+DEF_STRONG(_rb_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);
+}
+DEF_STRONG(_rb_check);
Index: sys/sys/tree.h
===================================================================
RCS file: /cvs/src/sys/sys/tree.h,v
retrieving revision 1.25
diff -u -p -r1.25 tree.h
--- sys/sys/tree.h	26 Sep 2016 08:08:51 -0000	1.25
+++ sys/sys/tree.h	18 Oct 2016 01:51:49 -0000
@@ -788,8 +788,6 @@ struct _name {								\
 
 #define RBT_ENTRY(_type)	struct rb_entry
 
-#ifdef _KERNEL
-
 static inline void
 _rb_init(struct rb_tree *rbt)
 {
@@ -981,7 +979,5 @@ RBT_GENERATE_INTERNAL(_name, _type, _fie
 	for ((_e) = RBT_MAX(_name, (_head));				\
 	     (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1);	\
 	     (_e) = (_n))
-
-#endif /* _KERNEL */
 
 #endif	/* _SYS_TREE_H_ */