Index: sys/tree.h
===================================================================
RCS file: /cvs/src/sys/sys/tree.h,v
retrieving revision 1.25
diff -u -p -d -r1.25 tree.h
--- sys/tree.h	26 Sep 2016 08:08:51 -0000	1.25
+++ sys/tree.h	31 Oct 2016 03:20:25 -0000
@@ -764,159 +764,167 @@ name##_RB_MINMAX(struct name *head, int 
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */
 
-struct rb_type {
+struct bst_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 bst_entry {
+	struct bst_entry *bst_parent;
+	struct bst_entry *bst_children[2];
+	unsigned int	  bst_data;
 };
 
-struct rb_entry {
-	struct rb_entry	 *rbt_parent;
-	struct rb_entry	 *rbt_left;
-	struct rb_entry	 *rbt_right;
-	unsigned int	  rbt_color;
+struct bstree {
+	struct bst_entry *bst_root;
 };
 
-#define RBT_HEAD(_name, _type)						\
-struct _name {								\
-	struct rb_tree rbh_root;					\
-}
-
-#define RBT_ENTRY(_type)	struct rb_entry
-
-#ifdef _KERNEL
+#define BST_INITIALIZER()	{ NULL }
 
 static inline void
-_rb_init(struct rb_tree *rbt)
+_bst_init(struct bstree *bst)
 {
-	rbt->rbt_root = NULL;
+	bst->bst_root = NULL;
 }
 
 static inline int
-_rb_empty(struct rb_tree *rbt)
+_bst_empty(struct bstree *bst)
 {
-	return (rbt->rbt_root == NULL);
+	return (bst->bst_root == NULL);
 }
 
-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_color(const struct rb_type *, void *);
-void	 _rb_poison(const struct rb_type *, void *, unsigned long);
-int	 _rb_check(const struct rb_type *, void *, unsigned long);
+void	*_bst_find(const struct bst_type *, struct bstree *, const void *);
+void	*_bst_nfind(const struct bst_type *, struct bstree *, const void *);
+void	*_bst_root(const struct bst_type *, struct bstree *);
+void	*_bst_min(const struct bst_type *, struct bstree *);
+void	*_bst_max(const struct bst_type *, struct bstree *);
+void	*_bst_next(const struct bst_type *, void *);
+void	*_bst_prev(const struct bst_type *, void *);
+void	*_bst_left(const struct bst_type *, void *);
+void	*_bst_right(const struct bst_type *, void *);
+void	*_bst_parent(const struct bst_type *, void *);
+void	 _bst_poison(const struct bst_type *, void *, unsigned long);
+int	 _bst_check(const struct bst_type *, void *, unsigned long);
 
-#define RBT_INITIALIZER(_head)	{ { NULL } }
+/*
+ * red-black tree
+ */
+struct rbt_type {
+	void		(*t_augment)(void *);
+	struct bst_type	  t_bst;
+};
+
+#define RBT_HEAD(_name, _type)						\
+struct _name {								\
+	struct bstree	 rb_tree;					\
+}
+
+#define RBT_ENTRY(_type)	struct bst_entry
+
+#define RBT_INITIALIZER(_head)	{ BST_INITIALIZER() }
+
+void	*_rbt_insert(const struct rbt_type *, struct bstree *, void *);
+void	*_rbt_remove(const struct rbt_type *, struct bstree *, void *);
 
 #define RBT_PROTOTYPE(_name, _type, _field, _cmp)			\
-extern const struct rb_type *const _name##_RBT_TYPE;			\
+extern const struct rbt_type _name##_RBT_TYPE;				\
 									\
 __unused static inline void						\
 _name##_RBT_INIT(struct _name *head)					\
 {									\
-	_rb_init(&head->rbh_root);					\
+	_bst_init(&head->rb_tree);					\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_INSERT(struct _name *head, struct _type *elm)		\
 {									\
-	return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm);	\
+	return _rbt_insert(&_name##_RBT_TYPE, &head->rb_tree, elm);	\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_REMOVE(struct _name *head, struct _type *elm)		\
 {									\
-	return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm);	\
+	return _rbt_remove(&_name##_RBT_TYPE, &head->rb_tree, elm);	\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_FIND(struct _name *head, const struct _type *key)		\
 {									\
-	return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key);	\
+	return _bst_find(&_name##_RBT_TYPE.t_bst,			\
+	    &head->rb_tree, key);					\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_NFIND(struct _name *head, const struct _type *key)		\
 {									\
-	return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key);	\
+	return _bst_nfind(&_name##_RBT_TYPE.t_bst,			\
+	    &head->rb_tree, key);					\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_ROOT(struct _name *head)					\
 {									\
-	return _rb_root(_name##_RBT_TYPE, &head->rbh_root);		\
+	return _bst_root(&_name##_RBT_TYPE.t_bst, &head->rb_tree);	\
 }									\
 									\
 __unused static inline int						\
 _name##_RBT_EMPTY(struct _name *head)					\
 {									\
-	return _rb_empty(&head->rbh_root);				\
+	return _bst_empty(&head->rb_tree);				\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_MIN(struct _name *head)					\
 {									\
-	return _rb_min(_name##_RBT_TYPE, &head->rbh_root);		\
+	return _bst_min(&_name##_RBT_TYPE.t_bst, &head->rb_tree);	\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_MAX(struct _name *head)					\
 {									\
-	return _rb_max(_name##_RBT_TYPE, &head->rbh_root);		\
+	return _bst_max(&_name##_RBT_TYPE.t_bst, &head->rb_tree);	\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_NEXT(struct _type *elm)					\
 {									\
-	return _rb_next(_name##_RBT_TYPE, elm);				\
+	return _bst_next(&_name##_RBT_TYPE.t_bst, elm);			\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_PREV(struct _type *elm)					\
 {									\
-	return _rb_prev(_name##_RBT_TYPE, elm);				\
+	return _bst_prev(&_name##_RBT_TYPE.t_bst, elm);			\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_LEFT(struct _type *elm)					\
 {									\
-	return _rb_left(_name##_RBT_TYPE, elm);				\
+	return _bst_left(&_name##_RBT_TYPE.t_bst, elm);			\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_RIGHT(struct _type *elm)					\
 {									\
-	return _rb_right(_name##_RBT_TYPE, elm);			\
+	return _bst_right(&_name##_RBT_TYPE.t_bst, elm);		\
 }									\
 									\
 __unused static inline struct _type *					\
 _name##_RBT_PARENT(struct _type *elm)					\
 {									\
-	return _rb_parent(_name##_RBT_TYPE, elm);			\
+	return _bst_parent(&_name##_RBT_TYPE.t_bst, elm);		\
 }									\
 									\
 __unused static inline void						\
 _name##_RBT_POISON(struct _type *elm, unsigned long poison)		\
 {									\
-	return _rb_poison(_name##_RBT_TYPE, elm, poison);		\
+	return _bst_poison(&_name##_RBT_TYPE.t_bst, elm, poison);	\
 }									\
 									\
 __unused static inline int						\
 _name##_RBT_CHECK(struct _type *elm, unsigned long poison)		\
 {									\
-	return _rb_check(_name##_RBT_TYPE, elm, poison);		\
+	return _bst_check(&_name##_RBT_TYPE.t_bst, elm, poison);	\
 }
 
 #define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug)		\
@@ -926,12 +934,13 @@ _name##_RBT_COMPARE(const void *lptr, co
 	const struct _type *l = lptr, *r = rptr;			\
 	return _cmp(l, r);						\
 }									\
-static const struct rb_type _name##_RBT_INFO = {			\
-	_name##_RBT_COMPARE,						\
+const struct rbt_type _name##_RBT_TYPE = {				\
 	_aug,								\
-	offsetof(struct _type, _field),					\
-};									\
-const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO
+	{								\
+		_name##_RBT_COMPARE,					\
+		offsetof(struct _type, _field),				\
+	},								\
+}
 
 #define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug)		\
 static void								\
@@ -982,6 +991,169 @@ RBT_GENERATE_INTERNAL(_name, _type, _fie
 	     (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1);	\
 	     (_e) = (_n))
 
-#endif /* _KERNEL */
+/*
+ * AVL tree
+ */
+
+#define AVL_HEAD(_name, _type)						\
+struct _name {								\
+	struct bstree	 avl_tree;					\
+}
+
+#define AVL_ENTRY(_type)	struct bst_entry
+
+#define AVL_INITIALIZER(_head)	{ BST_INITIALIZER() }
+
+void	*_avl_insert(const struct bst_type *, struct bstree *, void *);
+void	*_avl_remove(const struct bst_type *, struct bstree *, void *);
+
+#define AVL_PROTOTYPE(_name, _type, _field, _cmp)			\
+extern const struct bst_type _name##_AVL_TYPE;				\
+									\
+__unused static inline void						\
+_name##_AVL_INIT(struct _name *head)					\
+{									\
+	_bst_init(&head->avl_tree);					\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_INSERT(struct _name *head, struct _type *elm)		\
+{									\
+	return _avl_insert(&_name##_AVL_TYPE, &head->avl_tree, elm);	\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_REMOVE(struct _name *head, struct _type *elm)		\
+{									\
+	return _avl_remove(&_name##_AVL_TYPE, &head->avl_tree, elm);	\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_FIND(struct _name *head, const struct _type *key)		\
+{									\
+	return _bst_find(&_name##_AVL_TYPE, &head->avl_tree, key);	\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_NFIND(struct _name *head, const struct _type *key)		\
+{									\
+	return _bst_nfind(&_name##_AVL_TYPE, &head->avl_tree, key);	\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_ROOT(struct _name *head)					\
+{									\
+	return _bst_root(&_name##_AVL_TYPE, &head->avl_tree);		\
+}									\
+									\
+__unused static inline int						\
+_name##_AVL_EMPTY(struct _name *head)					\
+{									\
+	return _bst_empty(&head->avl_tree);				\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_MIN(struct _name *head)					\
+{									\
+	return _bst_min(&_name##_AVL_TYPE, &head->avl_tree);		\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_MAX(struct _name *head)					\
+{									\
+	return _bst_max(&_name##_AVL_TYPE, &head->avl_tree);		\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_NEXT(struct _type *elm)					\
+{									\
+	return _bst_next(&_name##_AVL_TYPE, elm);			\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_PREV(struct _type *elm)					\
+{									\
+	return _bst_prev(&_name##_AVL_TYPE, elm);			\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_LEFT(struct _type *elm)					\
+{									\
+	return _bst_left(&_name##_AVL_TYPE, elm);			\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_RIGHT(struct _type *elm)					\
+{									\
+	return _bst_right(&_name##_AVL_TYPE, elm);			\
+}									\
+									\
+__unused static inline struct _type *					\
+_name##_AVL_PARENT(struct _type *elm)					\
+{									\
+	return _bst_parent(&_name##_AVL_TYPE, elm);			\
+}									\
+									\
+__unused static inline void						\
+_name##_AVL_POISON(struct _type *elm, unsigned long poison)		\
+{									\
+	return _bst_poison(&_name##_AVL_TYPE, elm, poison);		\
+}									\
+									\
+__unused static inline int						\
+_name##_AVL_CHECK(struct _type *elm, unsigned long poison)		\
+{									\
+	return _bst_check(&_name##_AVL_TYPE, elm, poison);		\
+}
+
+#define AVL_GENERATE(_name, _type, _field, _cmp)			\
+static int								\
+_name##_AVL_COMPARE(const void *lptr, const void *rptr)			\
+{									\
+	const struct _type *l = lptr, *r = rptr;			\
+	return _cmp(l, r);						\
+}									\
+const struct bst_type _name##_AVL_TYPE = {				\
+	_name##_AVL_COMPARE,						\
+	offsetof(struct _type, _field),					\
+}
+
+#define AVL_INIT(_name, _head)		_name##_AVL_INIT(_head)
+#define AVL_INSERT(_name, _head, _elm)	_name##_AVL_INSERT(_head, _elm)
+#define AVL_REMOVE(_name, _head, _elm)	_name##_AVL_REMOVE(_head, _elm)
+#define AVL_FIND(_name, _head, _key)	_name##_AVL_FIND(_head, _key)
+#define AVL_NFIND(_name, _head, _key)	_name##_AVL_NFIND(_head, _key)
+#define AVL_ROOT(_name, _head)		_name##_AVL_ROOT(_head)
+#define AVL_EMPTY(_name, _head)		_name##_AVL_EMPTY(_head)
+#define AVL_MIN(_name, _head)		_name##_AVL_MIN(_head)
+#define AVL_MAX(_name, _head)		_name##_AVL_MAX(_head)
+#define AVL_NEXT(_name, _elm)		_name##_AVL_NEXT(_elm)
+#define AVL_PREV(_name, _elm)		_name##_AVL_PREV(_elm)
+#define AVL_LEFT(_name, _elm)		_name##_AVL_LEFT(_elm)
+#define AVL_RIGHT(_name, _elm)		_name##_AVL_RIGHT(_elm)
+#define AVL_PARENT(_name, _elm)		_name##_AVL_PARENT(_elm)
+#define AVL_POISON(_name, _elm, _p)	_name##_AVL_POISON(_elm, _p)
+#define AVL_CHECK(_name, _elm, _p)	_name##_AVL_CHECK(_elm, _p)
+
+#define AVL_FOREACH(_e, _name, _head)					\
+	for ((_e) = AVL_MIN(_name, (_head));				\
+	     (_e) != NULL;						\
+	     (_e) = AVL_NEXT(_name, (_e)))
+
+#define AVL_FOREACH_SAFE(_e, _name, _head, _n)				\
+	for ((_e) = AVL_MIN(_name, (_head));				\
+	     (_e) != NULL && ((_n) = AVL_NEXT(_name, (_e)), 1);	\
+	     (_e) = (_n))
+
+#define AVL_FOREACH_REVERSE(_e, _name, _head)				\
+	for ((_e) = AVL_MAX(_name, (_head));				\
+	     (_e) != NULL;						\
+	     (_e) = AVL_PREV(_name, (_e)))
+
+#define AVL_FOREACH_REVERSE_SAFE(_e, _name, _head, _n)			\
+	for ((_e) = AVL_MAX(_name, (_head));				\
+	     (_e) != NULL && ((_n) = AVL_PREV(_name, (_e)), 1);	\
+	     (_e) = (_n))
+
 
 #endif	/* _SYS_TREE_H_ */
Index: kern/subr_tree.c
===================================================================
RCS file: /cvs/src/sys/kern/subr_tree.c,v
retrieving revision 1.6
diff -u -p -d -r1.6 subr_tree.c
--- kern/subr_tree.c	20 Sep 2016 01:11:27 -0000	1.6
+++ kern/subr_tree.c	31 Oct 2016 03:20:25 -0000
@@ -44,63 +44,264 @@
 #include <sys/param.h>
 #include <sys/tree.h>
 
-static inline void *
-rb_n2e(const struct rb_type *t, void *node)
+static inline struct bst_entry *
+bst_n2e(const struct bst_type *t, void *node)
 {
-	caddr_t addr = (caddr_t)node;
+	unsigned long addr = (unsigned long)node;
 
-	return ((void *)(addr + t->t_offset));
+	return ((struct bst_entry *)(addr + t->t_offset));
 }
 
 static inline void *
-rb_e2n(const struct rb_type *t, struct rb_entry *rbe)
+bst_e2n(const struct bst_type *t, struct bst_entry *rbe)
 {
-	caddr_t addr = (caddr_t)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 BST_CHILD(_bse, _c)	(_bse)->bst_children[(_c)]
+#define BST_LEFT(_bse)		BST_CHILD((_bse), 0)
+#define BST_RIGHT(_bse)		BST_CHILD((_bse), 1)
+#define BST_PARENT(_bse)	(_bse)->bst_parent
+#define BST_DATA(_bse)		(_bse)->bst_data
 
-#define RBH_ROOT(_rbt)		(_rbt)->rbt_root
+#define BST_ROOT(_bst)		(_bst)->bst_root
+
+/* Finds the node with the same key as elm */
+void *
+_bst_find(const struct bst_type *t, struct bstree *bst, const void *key)
+{
+	struct bst_entry *tmp = BST_ROOT(bst);
+	void *node;
+	int comp;
+
+	while (tmp != NULL) {
+		node = bst_e2n(t, tmp);
+		comp = (*t->t_compare)(key, node);
+		if (comp < 0)
+			tmp = BST_LEFT(tmp);
+		else if (comp > 0)
+			tmp = BST_RIGHT(tmp);
+		else
+			return (node);
+	}
+
+	return (NULL);
+}
+
+/* Finds the first node greater than or equal to the search key */
+void *
+_bst_nfind(const struct bst_type *t, struct bstree *bst, const void *key)
+{
+	struct bst_entry *tmp = BST_ROOT(bst);
+	void *node;
+	void *res = NULL;
+	int comp;
+
+	while (tmp != NULL) {
+		node = bst_e2n(t, tmp);
+		comp = (*t->t_compare)(key, node);
+		if (comp < 0) {
+			res = node;
+			tmp = BST_LEFT(tmp);
+		} else if (comp > 0)
+			tmp = BST_RIGHT(tmp);
+		else
+			return (node);
+	}
+
+	return (res);
+}
+
+void *
+_bst_next(const struct bst_type *t, void *elm)
+{
+	struct bst_entry *bste = bst_n2e(t, elm);
+
+	if (BST_RIGHT(bste) != NULL) {
+		bste = BST_RIGHT(bste);
+		while (BST_LEFT(bste) != NULL)
+			bste = BST_LEFT(bste);
+	} else {
+		if (BST_PARENT(bste) != NULL &&
+		    (bste == BST_LEFT(BST_PARENT(bste))))
+			bste = BST_PARENT(bste);
+		else {
+			while (BST_PARENT(bste) != NULL &&
+			    (bste == BST_RIGHT(BST_PARENT(bste))))
+				bste = BST_PARENT(bste);
+			bste = BST_PARENT(bste);
+		}
+	}
+
+	return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void *
+_bst_prev(const struct bst_type *t, void *elm)
+{
+	struct bst_entry *bste = bst_n2e(t, elm);
+
+	if (BST_LEFT(bste) != NULL) {
+		bste = BST_LEFT(bste);
+		while (BST_RIGHT(bste) != NULL)
+			bste = BST_RIGHT(bste);
+	} else {
+		if (BST_PARENT(bste) != NULL &&
+		    (bste == BST_RIGHT(BST_PARENT(bste))))
+			bste = BST_PARENT(bste);
+		else {
+			while (BST_PARENT(bste) != NULL &&
+			    (bste == BST_LEFT(BST_PARENT(bste))))
+				bste = BST_PARENT(bste);
+			bste = BST_PARENT(bste);
+		}
+	}
+
+	return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void *
+_bst_root(const struct bst_type *t, struct bstree *bst)
+{
+	struct bst_entry *bste = BST_ROOT(bst);
+
+	return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void *
+_bst_min(const struct bst_type *t, struct bstree *bst)
+{
+	struct bst_entry *bste = BST_ROOT(bst);
+	struct bst_entry *parent = NULL;
+
+	while (bste != NULL) {
+		parent = bste;
+		bste = BST_LEFT(bste);
+	}
+
+	return (parent == NULL ? NULL : bst_e2n(t, parent));
+}
+
+void *
+_bst_max(const struct bst_type *t, struct bstree *bst)
+{
+	struct bst_entry *bste = BST_ROOT(bst);
+	struct bst_entry *parent = NULL;
+
+	while (bste != NULL) {
+		parent = bste;
+		bste = BST_RIGHT(bste);
+	}
+
+	return (parent == NULL ? NULL : bst_e2n(t, parent));
+}
+
+void *
+_bst_left(const struct bst_type *t, void *node)
+{
+	struct bst_entry *bste = bst_n2e(t, node);
+	bste = BST_LEFT(bste);
+	return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void *
+_bst_right(const struct bst_type *t, void *node)
+{
+	struct bst_entry *bste = bst_n2e(t, node);
+	bste = BST_RIGHT(bste);
+	return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void *
+_bst_parent(const struct bst_type *t, void *node)
+{
+	struct bst_entry *bste = bst_n2e(t, node);
+	bste = BST_PARENT(bste);
+	return (bste == NULL ? NULL : bst_e2n(t, bste));
+}
+
+void
+_bst_poison(const struct bst_type *t, void *node, unsigned long poison)
+{
+	struct bst_entry *bste = bst_n2e(t, node);
+
+	BST_PARENT(bste) = BST_LEFT(bste) = BST_RIGHT(bste) =
+	    (struct bst_entry *)poison;
+}
+
+int
+_bst_check(const struct bst_type *t, void *node, unsigned long poison)
+{
+	struct bst_entry *bste = bst_n2e(t, node);
+
+	return ((unsigned long)BST_PARENT(bste) == poison &&
+	    (unsigned long)BST_LEFT(bste) == poison &&
+	    (unsigned long)BST_RIGHT(bste) == poison);
+}
+
+/*
+ * Red-Black Trees
+ */
+
+static inline struct bst_entry *
+rbt_n2e(const struct rbt_type *t, void *node)
+{
+	return bst_n2e(&t->t_bst, node);
+}
+
+static inline void *
+rbt_e2n(const struct rbt_type *t, struct bst_entry *rbe)
+{
+	return bst_e2n(&t->t_bst, rbe);
+}
+
+#define RBE_BLACK		0
+#define RBE_RED			1
+
+#define RBE_CHILD(_rbe, _c)	BST_CHILD((_rbe), (_c))
+#define RBE_LEFT(_rbe)		BST_LEFT(_rbe)
+#define RBE_RIGHT(_rbe)		BST_RIGHT(_rbe)
+#define RBE_PARENT(_rbe)	BST_PARENT(_rbe)
+#define RBE_COLOR(_rbe)		BST_DATA(_rbe)
+
+#define RBH_ROOT(_rbt)		BST_ROOT(_rbt)
 
 static inline void
-rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
+rbe_set(struct bst_entry *rbe, struct bst_entry *parent)
 {
 	RBE_PARENT(rbe) = parent;
 	RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
-	RBE_COLOR(rbe) = RB_RED;
+	RBE_COLOR(rbe) = RBE_RED;
 }
 
 static inline void
-rbe_set_blackred(struct rb_entry *black, struct rb_entry *red)
+rbe_set_blackred(struct bst_entry *black, struct bst_entry *red)
 {
-	RBE_COLOR(black) = RB_BLACK;
-	RBE_COLOR(red) = RB_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)
+rbe_augment(const struct rbt_type *t, struct bst_entry *rbe)
 {
-	(*t->t_augment)(rb_e2n(t, rbe));
+	(*t->t_augment)(rbt_e2n(t, rbe));
 }
 
 static inline void
-rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe)
+rbe_if_augment(const struct rbt_type *t, struct bst_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)
+rbe_rotate_left(const struct rbt_type *t, struct bstree *rbt,
+    struct bst_entry *rbe)
 {
-	struct rb_entry *parent;
-	struct rb_entry *tmp;
+	struct bst_entry *parent;
+	struct bst_entry *tmp;
 
 	tmp = RBE_RIGHT(rbe);
 	RBE_RIGHT(rbe) = RBE_LEFT(tmp);
@@ -130,11 +331,11 @@ rbe_rotate_left(const struct rb_type *t,
 }
 
 static inline void
-rbe_rotate_right(const struct rb_type *t, struct rb_tree *rbt,
-    struct rb_entry *rbe)
+rbe_rotate_right(const struct rbt_type *t, struct bstree *rbt,
+    struct bst_entry *rbe)
 {
-	struct rb_entry *parent;
-	struct rb_entry *tmp;
+	struct bst_entry *parent;
+	struct bst_entry *tmp;
 
 	tmp = RBE_LEFT(rbe);
 	RBE_LEFT(rbe) = RBE_RIGHT(tmp);
@@ -164,19 +365,19 @@ rbe_rotate_right(const struct rb_type *t
 }
 
 static inline void
-rbe_insert_color(const struct rb_type *t, struct rb_tree *rbt,
-    struct rb_entry *rbe)
+rbe_insert_color(const struct rbt_type *t, struct bstree *rbt,
+    struct bst_entry *rbe)
 {
-	struct rb_entry *parent, *gparent, *tmp;
+	struct bst_entry *parent, *gparent, *tmp;
 
 	while ((parent = RBE_PARENT(rbe)) != NULL &&
-	    RBE_COLOR(parent) == RB_RED) {
+	    RBE_COLOR(parent) == RBE_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;
+			if (tmp != NULL && RBE_COLOR(tmp) == RBE_RED) {
+				RBE_COLOR(tmp) = RBE_BLACK;
 				rbe_set_blackred(parent, gparent);
 				rbe = gparent;
 				continue;
@@ -193,8 +394,8 @@ rbe_insert_color(const struct rb_type *t
 			rbe_rotate_right(t, rbt, gparent);
 		} else {
 			tmp = RBE_LEFT(gparent);
-			if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
-				RBE_COLOR(tmp) = RB_BLACK;
+			if (tmp != NULL && RBE_COLOR(tmp) == RBE_RED) {
+				RBE_COLOR(tmp) = RBE_BLACK;
 				rbe_set_blackred(parent, gparent);
 				rbe = gparent;
 				continue;
@@ -212,49 +413,49 @@ rbe_insert_color(const struct rb_type *t
 		}
 	}
 
-	RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
+	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)
+rbe_remove_color(const struct rbt_type *t, struct bstree *rbt,
+    struct bst_entry *parent, struct bst_entry *rbe)
 {
-	struct rb_entry *tmp;
+	struct bst_entry *tmp;
 
-	while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) &&
+	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) == RB_RED) {
+			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)) == RB_BLACK) &&
+			     RBE_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) &&
 			    (RBE_RIGHT(tmp) == NULL ||
-			     RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
-				RBE_COLOR(tmp) = RB_RED;
+			     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)) == RB_BLACK) {
-					struct rb_entry *oleft;
+				    RBE_COLOR(RBE_RIGHT(tmp)) == RBE_BLACK) {
+					struct bst_entry *oleft;
 
 					oleft = RBE_LEFT(tmp);
 					if (oleft != NULL)
-						RBE_COLOR(oleft) = RB_BLACK;
+						RBE_COLOR(oleft) = RBE_BLACK;
 
-					RBE_COLOR(tmp) = RB_RED;
+					RBE_COLOR(tmp) = RBE_RED;
 					rbe_rotate_right(t, rbt, tmp);
 					tmp = RBE_RIGHT(parent);
 				}
 
 				RBE_COLOR(tmp) = RBE_COLOR(parent);
-				RBE_COLOR(parent) = RB_BLACK;
+				RBE_COLOR(parent) = RBE_BLACK;
 				if (RBE_RIGHT(tmp))
-					RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
+					RBE_COLOR(RBE_RIGHT(tmp)) = RBE_BLACK;
 
 				rbe_rotate_left(t, rbt, parent);
 				rbe = RBH_ROOT(rbt);
@@ -262,37 +463,37 @@ rbe_remove_color(const struct rb_type *t
 			}
 		} else {
 			tmp = RBE_LEFT(parent);
-			if (RBE_COLOR(tmp) == RB_RED) {
+			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)) == RB_BLACK) &&
+			     RBE_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) &&
 			    (RBE_RIGHT(tmp) == NULL ||
-			     RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
-				RBE_COLOR(tmp) = RB_RED;
+			     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)) == RB_BLACK) {
-					struct rb_entry *oright;
+				    RBE_COLOR(RBE_LEFT(tmp)) == RBE_BLACK) {
+					struct bst_entry *oright;
 
 					oright = RBE_RIGHT(tmp);
 					if (oright != NULL)
-						RBE_COLOR(oright) = RB_BLACK;
+						RBE_COLOR(oright) = RBE_BLACK;
 
-					RBE_COLOR(tmp) = RB_RED;
+					RBE_COLOR(tmp) = RBE_RED;
 					rbe_rotate_left(t, rbt, tmp);
 					tmp = RBE_LEFT(parent);
 				}
 
 				RBE_COLOR(tmp) = RBE_COLOR(parent);
-				RBE_COLOR(parent) = RB_BLACK;
+				RBE_COLOR(parent) = RBE_BLACK;
 				if (RBE_LEFT(tmp) != NULL)
-					RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
+					RBE_COLOR(RBE_LEFT(tmp)) = RBE_BLACK;
 
 				rbe_rotate_right(t, rbt, parent);
 				rbe = RBH_ROOT(rbt);
@@ -302,13 +503,13 @@ rbe_remove_color(const struct rb_type *t
 	}
 
 	if (rbe != NULL)
-		RBE_COLOR(rbe) = RB_BLACK;
+		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)
+static inline struct bst_entry *
+rbe_remove(const struct rbt_type *t, struct bstree *rbt, struct bst_entry *rbe)
 {
-	struct rb_entry *child, *parent, *old = rbe;
+	struct bst_entry *child, *parent, *old = rbe;
 	unsigned int color;
 
 	if (RBE_LEFT(rbe) == NULL)
@@ -316,7 +517,7 @@ rbe_remove(const struct rb_type *t, stru
 	else if (RBE_RIGHT(rbe) == NULL)
 		child = RBE_LEFT(rbe);
 	else {
-		struct rb_entry *tmp;
+		struct bst_entry *tmp;
 
 		rbe = RBE_RIGHT(rbe);
 		while ((tmp = RBE_LEFT(rbe)) != NULL)
@@ -381,29 +582,29 @@ rbe_remove(const struct rb_type *t, stru
 	} else
 		RBH_ROOT(rbt) = child;
 color:
-	if (color == RB_BLACK)
+	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)
+_rbt_remove(const struct rbt_type *t, struct bstree *rbt, void *elm)
 {
-	struct rb_entry *rbe = rb_n2e(t, elm);
-	struct rb_entry *old;
+	struct bst_entry *rbe = rbt_n2e(t, elm);
+	struct bst_entry *old;
 
 	old = rbe_remove(t, rbt, rbe);
 
-	return (old == NULL ? NULL : rb_e2n(t, old));
+	return (old == NULL ? NULL : rbt_e2n(t, old));
 }
 
 void *
-_rb_insert(const struct rb_type *t, struct rb_tree *rbt, void *elm)
+_rbt_insert(const struct rbt_type *t, struct bstree *rbt, void *elm)
 {
-	struct rb_entry *rbe = rb_n2e(t, elm);
-	struct rb_entry *tmp;
-	struct rb_entry *parent = NULL;
+	struct bst_entry *rbe = rbt_n2e(t, elm);
+	struct bst_entry *tmp;
+	struct bst_entry *parent = NULL;
 	void *node;
 	int comp = 0;
 
@@ -411,24 +612,19 @@ _rb_insert(const struct rb_type *t, stru
 	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
+		node = rbt_e2n(t, tmp);
+		comp = (*t->t_bst.t_compare)(elm, node);
+		if (comp == 0)
 			return (node);
+
+		comp = comp > 0;
+		tmp = RBE_CHILD(tmp, comp);
 	}
 
 	rbe_set(rbe, parent);
 
 	if (parent != NULL) {
-		if (comp < 0)
-			RBE_LEFT(parent) = rbe;
-		else
-			RBE_RIGHT(parent) = rbe;
-
+		RBE_CHILD(parent, comp) = rbe;
 		rbe_if_augment(t, parent);
 	} else
 		RBH_ROOT(rbt) = rbe;
@@ -438,175 +634,260 @@ _rb_insert(const struct rb_type *t, stru
 	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)
+/*
+ * AVL Trees
+ */
+
+#define avl_n2e(_t, _elm)	bst_n2e((_t), (_elm))
+#define avl_e2n(_t, _avle)	bst_e2n((_t), (_avle))
+
+#define AVLT_ROOT(_avlt)	BST_ROOT(_avlt)
+
+#define AVLE_CHILD(_avle, _c)	BST_CHILD((_avle), (_c))
+#define AVLE_LEFT(_avle)	BST_LEFT(_avle)
+#define AVLE_RIGHT(_avle)	BST_RIGHT(_avle)
+#define AVLE_PARENT(_avle)	BST_PARENT(_avle)
+#define AVLE_BALANCE(_avle)	BST_DATA(_avle)
+
+static const int avl_balances[2] = { -1, 1 };
+
+/*
+ * rotate "left"
+ *
+ *     /             /
+ *    B             D
+ *   / \           / \
+ *  A   D   ==>   B   E
+ *     / \       / \
+ *    C   E     A   C
+ */
+
+static inline struct bst_entry *
+avl_rotate(struct bst_entry *avle, int d)
 {
-	struct rb_entry *tmp = RBH_ROOT(rbt);
-	void *node;
-	int comp;
+	struct bst_entry *child, *gchild;
 
-	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);
+	child = AVLE_CHILD(avle, !d);
+	gchild = AVLE_CHILD(child, d);
+
+	AVLE_CHILD(child, d) = avle;
+	AVLE_PARENT(avle) = child;
+
+	AVLE_CHILD(avle, !d) = gchild;
+	if (gchild != NULL)
+		AVLE_PARENT(gchild) = avle;
+
+	return (child);
+}
+
+static inline int
+avl_rebalance(struct bstree *avlt, struct bst_entry *parent,
+    struct bst_entry **avlep, int balance)
+{
+	struct bst_entry *avle = *avlep;
+	struct bst_entry *child;
+	int cbalance;
+	int diff;
+	int d;
+
+	d = balance > 0;
+	child = AVLE_CHILD(avle, d);
+
+	cbalance = AVLE_BALANCE(child);
+	if (avl_balances[!d] == cbalance) {
+		struct bst_entry *gchild;
+
+		gchild = AVLE_CHILD(child, !d);
+
+		cbalance = AVLE_BALANCE(gchild);
+		AVLE_BALANCE(avle) =
+		    (cbalance == avl_balances[d]) ? avl_balances[!d] : 0;
+		AVLE_BALANCE(child) =
+		    (cbalance == avl_balances[!d]) ? avl_balances[d] : 0;
+		AVLE_BALANCE(gchild) = 0;
+
+		child = avl_rotate(child, d);
+		AVLE_CHILD(avle, d) = child;
+		AVLE_PARENT(child) = avle;
+
+		diff = 1; /* tree is always shorter after double rotation */
+	} else {
+		cbalance += avl_balances[!d];
+
+		AVLE_BALANCE(child) = cbalance;
+		AVLE_BALANCE(avle) = -cbalance;
+
+		diff = (cbalance == 0) ? 1 : 0;
 	}
 
-	return (NULL);
+	child = avl_rotate(avle, !d);
+	if (parent != NULL) {
+		d = AVLE_RIGHT(parent) == avle;
+		AVLE_CHILD(parent, d) = child;
+	} else
+		AVLT_ROOT(avlt) = child;
+	AVLE_PARENT(child) = parent;
+
+	*avlep = child;
+	return (diff);
 }
 
-/* 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)
+_avl_insert(const struct bst_type *t, struct bstree *avlt, void *elm)
 {
-	struct rb_entry *tmp = RBH_ROOT(rbt);
+	struct bst_entry *avle = avl_n2e(t, elm);
+	struct bst_entry *tmp;
+	struct bst_entry *parent = NULL;
 	void *node;
-	void *res = NULL;
-	int comp;
+	int comp = 0;
 
+	tmp = AVLT_ROOT(avlt);
 	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
+		parent = tmp;
+
+		node = avl_e2n(t, tmp);
+		comp = (*t->t_compare)(elm, node);
+		if (comp == 0)
 			return (node);
-	}
 
-	return (res);
-}
+		comp = (comp > 0);
+		tmp = AVLE_CHILD(tmp, comp);
+	}
 
-void *
-_rb_next(const struct rb_type *t, void *elm)
-{
-	struct rb_entry *rbe = rb_n2e(t, elm);
+	AVLE_PARENT(avle) = parent;
+	AVLE_LEFT(avle) = AVLE_RIGHT(avle) = NULL;
+	AVLE_BALANCE(avle) = 0;
 
-	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);
-		}
+	if (parent == NULL) {
+		AVLT_ROOT(avlt) = avle;
+		return (NULL);
 	}
 
-	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
-}
+	AVLE_CHILD(parent, comp) = avle;
 
-void *
-_rb_prev(const struct rb_type *t, void *elm)
-{
-	struct rb_entry *rbe = rb_n2e(t, elm);
+	for (;;) {
+		int obalance, nbalance;
 
-	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);
+		avle = parent;
+
+		obalance = AVLE_BALANCE(avle);
+		nbalance = obalance + avl_balances[comp];
+
+		/* the balance has gone from a lean to equality */
+		if (nbalance == 0) {
+			AVLE_BALANCE(avle) = 0;
+			break;
+		}
+
+		parent = AVLE_PARENT(avle);
+
+		/* an existing lean has increased, so rebalance */
+		if (obalance != 0) {
+			avl_rebalance(avlt, parent, &avle, nbalance);
+			break;
 		}
+
+		AVLE_BALANCE(avle) = nbalance;
+
+		if (parent == NULL)
+			break;
+
+		comp = AVLE_RIGHT(parent) == avle;
 	}
 
-	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
+	return (NULL);
 }
 
+
 void *
-_rb_root(const struct rb_type *t, struct rb_tree *rbt)
+_avl_remove(const struct bst_type *t, struct bstree *avlt, void *elm)
 {
-	struct rb_entry *rbe = RBH_ROOT(rbt);
+	struct bst_entry *avle = avl_n2e(t, elm);
+	struct bst_entry *parent;
+	struct bst_entry *next;
+	struct bst_entry sentinel;
+	int comp;
 
-	return (rbe == NULL ? rbe : rb_e2n(t, rbe));
-}
+	parent = AVLE_PARENT(avle);
 
-void *
-_rb_min(const struct rb_type *t, struct rb_tree *rbt)
-{
-	struct rb_entry *rbe = RBH_ROOT(rbt);
-	struct rb_entry *parent = NULL;
+	if (AVLE_LEFT(avle) != NULL && AVLE_RIGHT(avle) != NULL) {
+		/* two children exist, so shuffle tree around */
+		struct bst_entry *nparent = parent;
 
-	while (rbe != NULL) {
-		parent = rbe;
-		rbe = RBE_LEFT(rbe);
+		/* find the next (well, previous) ordered node */
+		next = AVLE_LEFT(avle);
+		if (AVLE_RIGHT(next) == NULL) {
+			/* avle is going to swap with its immediate child */
+
+			parent = next; /* so next will be the avle parent */
+			AVLE_PARENT(next) = parent;
+
+			AVLE_LEFT(avle) = &sentinel;
+		} else {
+			do {
+				parent = next;
+				next = AVLE_RIGHT(next);
+			} while (AVLE_RIGHT(next) != NULL);
+
+			AVLE_RIGHT(parent) = &sentinel;
+		}
+
+		/* swap the target entry with the next entry */
+		sentinel = *next;
+		*next = *avle;
+
+		/* patch the next node into the surrounding tree */
+		AVLE_PARENT(AVLE_LEFT(avle)) = next;
+		AVLE_PARENT(AVLE_RIGHT(avle)) = next;
+		if (nparent != NULL) {
+			comp = AVLE_RIGHT(nparent) == avle;
+			AVLE_CHILD(nparent, comp) = next;
+		} else
+			AVLT_ROOT(avlt) = next;
+
+		avle = &sentinel;
 	}
 
-	return (parent == NULL ? NULL : rb_e2n(t, parent));
-}
+	next = AVLE_LEFT(avle);
+	if (next == NULL)
+		next = AVLE_RIGHT(avle);
 
-void *
-_rb_max(const struct rb_type *t, struct rb_tree *rbt)
-{
-	struct rb_entry *rbe = RBH_ROOT(rbt);
-	struct rb_entry *parent = NULL;
+	if (next != NULL)
+		AVLE_PARENT(next) = parent;
 
-	while (rbe != NULL) {
-		parent = rbe;
-		rbe = RBE_RIGHT(rbe);
+	if (parent == NULL) {
+		AVLT_ROOT(avlt) = next;
+		return (elm);
 	}
 
-	return (parent == NULL ? NULL : rb_e2n(t, parent));
-}
+	comp = AVLE_RIGHT(parent) == avle;
+	AVLE_CHILD(parent, comp) = next;
 
-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));
-}
+	for (;;) {
+		int obalance, nbalance;
 
-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));
-}
+		avle = parent;
 
-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));
-}
+		obalance = AVLE_BALANCE(avle);
+		nbalance = obalance - avl_balances[comp];
 
-void
-_rb_poison(const struct rb_type *t, void *node, unsigned long poison)
-{
-	struct rb_entry *rbe = rb_n2e(t, node);
+		if (obalance == 0) {
+			AVLE_BALANCE(avle) = nbalance;
+			break;
+		}
 
-	RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
-	    (struct rb_entry *)poison;
-}
+		parent = AVLE_PARENT(avle);
 
-int
-_rb_check(const struct rb_type *t, void *node, unsigned long poison)
-{
-	struct rb_entry *rbe = rb_n2e(t, node);
+		if (nbalance == 0)
+			AVLE_BALANCE(avle) = 0;
+		else if (avl_rebalance(avlt, parent, &avle, nbalance) == 0)
+			break;
 
-	return ((unsigned long)RBE_PARENT(rbe) == poison &&
-	    (unsigned long)RBE_LEFT(rbe) == poison &&
-	    (unsigned long)RBE_RIGHT(rbe) == poison);
+		if (parent == NULL)
+			break;
+
+		comp = AVLE_RIGHT(parent) == avle;
+	}
+
+	return (elm);
 }