Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -307,35 +307,36 @@
 	(root)->rbh_root = NULL;					\
 } while (/*CONSTCOND*/ 0)
 
-#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
+#ifdef _KERNEL
+#include <sys/systm.h>
+#else
+#include <stdbool.h>
+#define	KASSERT(exp, msg)	/* */
+#endif
+#include <stdint.h>
+#define RB_LF(elm, field)		(elm)->field.rbe_left
+#define RB_RT(elm, field)		(elm)->field.rbe_right
+#define RB_FLIP(elm)			(*(__uintptr_t *)&(elm) ^= 1)
+#define RB_FLIP_LF(elm, field)		RB_FLIP(RB_LF(elm, field))
+#define RB_FLIP_RT(elm, field)		RB_FLIP(RB_RT(elm, field))
+#define RB_RED(elm)			((*(__uintptr_t *)&(elm) & 1) != 0)
+#define RB_RED_LF(elm, field)		RB_RED(RB_LF(elm, field))
+#define RB_RED_RT(elm, field)		RB_RED(RB_RT(elm, field))
+#define RB_PTR(elm, field)		((typeof(elm->field.rbe_parent)) \
+					 ((__uintptr_t)(elm) & ~(__uintptr_t)1))
+#define RB_LEFT(elm, field)		RB_PTR(RB_LF(elm, field), field)
+#define RB_RIGHT(elm, field)		RB_PTR(RB_RT(elm, field), field)
 #define RB_PARENT(elm, field)		(elm)->field.rbe_parent
-#define RB_COLOR(elm, field)		(elm)->field.rbe_color
-#define RB_ISRED(elm, field)		((elm) != NULL && RB_COLOR(elm, field) == RB_RED)
 #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 (/*CONSTCOND*/ 0)
-
-#define RB_SET_BLACKRED(black, red, field) do {				\
-	RB_COLOR(black, field) = RB_BLACK;				\
-	RB_COLOR(red, field) = RB_RED;					\
-} while (/*CONSTCOND*/ 0)
-
 /*
  * Something to be invoked in a loop at the root of every modified subtree,
  * from the bottom up to the root, to update augmented node data.
@@ -344,36 +345,43 @@
 #define RB_AUGMENT(x)	break
 #endif
 
+/*
+ * Fix pointers to a parent, and from a parent, as part of rotation.
+ */
+#define RB_ROTATE_PARENT(head, elm, tmp, field) do {			\
+	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) == NULL)    \
+		RB_ROOT(head) = (tmp);					\
+	else if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
+		RB_LF(RB_PARENT(elm, field), field) = (tmp);		\
+	else								\
+		RB_RT(RB_PARENT(elm, field), field) = (tmp);		\
+	RB_PARENT(elm, field) = (tmp);					\
+} while (/*CONSTCOND*/ 0)
+
+/*
+ * Rotation makes the descending node red, and the ascending
+ * node not-red.
+ */
 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
 	(tmp) = RB_RIGHT(elm, field);					\
-	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {	\
+	if ((RB_RT(elm, field) = RB_LF(tmp, field)) != NULL) {		\
 		RB_PARENT(RB_LEFT(tmp, field), field) = (elm);		\
 	}								\
-	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\
-		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_ROTATE_PARENT(head, elm, tmp, field);			\
+	RB_LF(tmp, field) = (elm);					\
+	RB_FLIP_LF(tmp, field);						\
 	RB_PARENT(elm, field) = (tmp);					\
 	RB_AUGMENT(elm);						\
 } while (/*CONSTCOND*/ 0)
 
 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
 	(tmp) = RB_LEFT(elm, field);					\
-	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {	\
+	if ((RB_LF(elm, field) = RB_RT(tmp, field)) != NULL) {		\
 		RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);		\
 	}								\
-	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\
-		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_ROTATE_PARENT(head, elm, tmp, field);			\
+	RB_RT(tmp, field) = (elm);					\
+	RB_FLIP_RT(tmp, field);						\
 	RB_PARENT(elm, field) = (tmp);					\
 	RB_AUGMENT(elm);						\
 } while (/*CONSTCOND*/ 0)
@@ -384,8 +392,8 @@
 #define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\
 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\
-	RB_PROTOTYPE_INSERT_COLOR(name, type, attr);			\
-	RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);			\
+	RB_PROTOTYPE_INSERT_BALANCE(name, type, attr);			\
+	RB_PROTOTYPE_REMOVE_BALANCE(name, type, attr);			\
 	RB_PROTOTYPE_INSERT(name, type, attr);				\
 	RB_PROTOTYPE_REMOVE(name, type, attr);				\
 	RB_PROTOTYPE_FIND(name, type, attr);				\
@@ -394,10 +402,10 @@
 	RB_PROTOTYPE_PREV(name, type, attr);				\
 	RB_PROTOTYPE_MINMAX(name, type, attr);				\
 	RB_PROTOTYPE_REINSERT(name, type, attr);
-#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)			\
-	attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
-#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\
-	attr void name##_RB_REMOVE_COLOR(struct name *, struct type *)
+#define RB_PROTOTYPE_INSERT_BALANCE(name, type, attr)			\
+	attr void name##_RB_INSERT_BALANCE(struct name *, struct type *)
+#define RB_PROTOTYPE_REMOVE_BALANCE(name, type, attr)			\
+	attr void name##_RB_REMOVE_BALANCE(struct name *, struct type *)
 #define RB_PROTOTYPE_REMOVE(name, type, attr)				\
 	attr struct type *name##_RB_REMOVE(struct name *, struct type *)
 #define RB_PROTOTYPE_INSERT(name, type, attr)				\
@@ -423,8 +431,8 @@
 #define	RB_GENERATE_STATIC(name, type, field, cmp)			\
 	RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\
-	RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
-	RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
+	RB_GENERATE_INSERT_BALANCE(name, type, field, attr)		\
+	RB_GENERATE_REMOVE_BALANCE(name, type, field, attr)		\
 	RB_GENERATE_INSERT(name, type, field, cmp, attr)		\
 	RB_GENERATE_REMOVE(name, type, field, attr)			\
 	RB_GENERATE_FIND(name, type, field, cmp, attr)			\
@@ -435,114 +443,108 @@
 	RB_GENERATE_REINSERT(name, type, field, cmp, attr)
 
 
-#define RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
+#define RB_GENERATE_INSERT_BALANCE(name, type, field, attr)		\
 attr void								\
-name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
+name##_RB_INSERT_BALANCE(struct name *head, struct type *elm)		\
 {									\
-	struct type *parent, *gparent, *tmp;				\
-	while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) {	\
-		gparent = RB_PARENT(parent, field);			\
-		if (parent == RB_LEFT(gparent, field)) {		\
-			tmp = RB_RIGHT(gparent, field);			\
-			if (RB_ISRED(tmp, field)) {			\
-				RB_COLOR(tmp, field) = RB_BLACK;	\
-				RB_SET_BLACKRED(parent, gparent, field);\
-				elm = gparent;				\
-				continue;				\
-			}						\
+	struct type *gparent, *parent;					\
+	while ((parent = RB_PARENT(elm, field)) != NULL) {		\
+		if (RB_LEFT(parent, field) == elm)			\
+			RB_FLIP_LF(parent, field);			\
+		else							\
+			RB_FLIP_RT(parent, field);			\
+		if ((gparent = RB_PARENT(parent, field)) == NULL)	\
+			break;						\
+		if (RB_RED_LF(gparent, field) &&			\
+		    RB_RED_RT(gparent, field)) {			\
+			RB_FLIP_LF(gparent, field);			\
+			RB_FLIP_RT(gparent, field);			\
+			elm = gparent;					\
+			continue;					\
+		}							\
+		if (RB_RED_LF(gparent, field) &&			\
+		    parent == RB_LEFT(gparent, field)) { 		\
 			if (RB_RIGHT(parent, field) == elm) {		\
-				RB_ROTATE_LEFT(head, parent, tmp, field);\
-				tmp = parent;				\
+				RB_ROTATE_LEFT(head, parent, elm, field);\
 				parent = elm;				\
-				elm = tmp;				\
 			}						\
-			RB_SET_BLACKRED(parent, gparent, field);	\
-			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\
-		} else {						\
-			tmp = RB_LEFT(gparent, field);			\
-			if (RB_ISRED(tmp, field)) {			\
-				RB_COLOR(tmp, field) = RB_BLACK;	\
-				RB_SET_BLACKRED(parent, gparent, field);\
-				elm = gparent;				\
-				continue;				\
-			}						\
+			RB_ROTATE_RIGHT(head, gparent, parent, field);	\
+		} else if (RB_RED_RT(gparent, field) &&			\
+		    parent == RB_RIGHT(gparent, field)) {		\
 			if (RB_LEFT(parent, field) == elm) {		\
-				RB_ROTATE_RIGHT(head, parent, tmp, field);\
-				tmp = parent;				\
+				RB_ROTATE_RIGHT(head, parent, elm, field);\
 				parent = elm;				\
-				elm = tmp;				\
 			}						\
-			RB_SET_BLACKRED(parent, gparent, field);	\
-			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
+			RB_ROTATE_LEFT(head, gparent, parent, field);	\
 		}							\
+		break;							\
 	}								\
-	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
 }
 
-#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\
+#define RB_GENERATE_REMOVE_BALANCE(name, type, field, attr)		\
 attr void								\
-name##_RB_REMOVE_COLOR(struct name *head, struct type *parent)		\
+name##_RB_REMOVE_BALANCE(struct name *head, struct type *elm)		\
 {									\
-	struct type *elm, *tmp;						\
-	elm = NULL;							\
+	struct type *par, *sib, *tmp;					\
+	bool go_left, left_child, red_par;				\
+	left_child = (RB_LEFT(elm, field) == NULL);			\
 	do {								\
-		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);		\
+		go_left = left_child;					\
+		if (go_left ?						\
+		    !RB_RED_RT(elm, field) :				\
+		    !RB_RED_LF(elm, field)) {				\
+			par = RB_PARENT(elm, field);			\
+			left_child = par != NULL &&			\
+			    RB_LEFT(par, field) == elm;			\
+			red_par = left_child ? RB_RED_LF(par, field) :	\
+			    par == NULL ? true : RB_RED_RT(par, field); \
+		}							\
+		if (go_left) {						\
+			if (RB_RED_RT(elm, field)) {			\
+				red_par = true;				\
+				RB_ROTATE_LEFT(head, elm, par, field);	\
 			}						\
-			if (RB_ISRED(RB_LEFT(tmp, field), field)) {	\
-				struct type *oleft;			\
-				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);		\
-			} else if (!RB_ISRED(RB_RIGHT(tmp, field), field)) { \
-				RB_COLOR(tmp, field) = RB_RED;		\
-				elm = parent;				\
-				parent = RB_PARENT(elm, field);		\
+			sib = RB_RIGHT(elm, field);			\
+			if (RB_RED_LF(sib, field)) {			\
+				RB_ROTATE_RIGHT(head, sib, tmp, field);	\
+				sib = tmp;				\
+			} else if (!RB_RED_RT(sib, field)) {		\
+				RB_FLIP_RT(elm, field);			\
+				elm = par;				\
 				continue;				\
 			}						\
-			if (RB_ISRED(RB_RIGHT(tmp, field), field))	\
-				RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \
-			RB_COLOR(tmp, field) = RB_COLOR(parent, field);	\
-			RB_COLOR(parent, field) = RB_BLACK;		\
-			RB_ROTATE_LEFT(head, parent, tmp, field);	\
-			elm = RB_ROOT(head);				\
+			if (RB_RED_RT(sib, field))			\
+				RB_FLIP_RT(sib, field);			\
+			RB_ROTATE_LEFT(head, elm, sib, field);		\
+			RB_FLIP_LF(sib, field);				\
 			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_RED_LF(elm, field)) {			\
+				red_par = true;				\
+				RB_ROTATE_RIGHT(head, elm, par, field); \
 			}						\
-			if (RB_ISRED(RB_RIGHT(tmp, field), field)) {	\
-				struct type *oright;			\
-				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);		\
-			} else if (!RB_ISRED(RB_LEFT(tmp, field), field)) { \
-				RB_COLOR(tmp, field) = RB_RED;		\
-				elm = parent;				\
-				parent = RB_PARENT(elm, field);		\
+			sib = RB_LEFT(elm, field);			\
+			if (RB_RED_RT(sib, field)) {			\
+				RB_ROTATE_LEFT(head, sib, tmp, field);	\
+				sib = tmp;				\
+			} else if (!RB_RED_LF(sib, field)) {		\
+				RB_FLIP_LF(elm, field);			\
+				elm = par;				\
 				continue;				\
 			}						\
-			if (RB_ISRED(RB_LEFT(tmp, field), field))	\
-				RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \
-			RB_COLOR(tmp, field) = RB_COLOR(parent, field);	\
-			RB_COLOR(parent, field) = RB_BLACK;		\
-			RB_ROTATE_RIGHT(head, parent, tmp, field);	\
-			elm = RB_ROOT(head);				\
+			if (RB_RED_LF(sib, field))			\
+				RB_FLIP_LF(sib, field);			\
+			RB_ROTATE_RIGHT(head, elm, sib, field);		\
+			RB_FLIP_RT(sib, field);				\
 			break;						\
 		}							\
-	} while (!RB_ISRED(elm, field) && parent != NULL);		\
-	RB_COLOR(elm, field) = RB_BLACK;				\
+	} while (!red_par);						\
+	if (par != NULL && red_par) {					\
+		if (left_child)						\
+			RB_FLIP_LF(par, field);				\
+		else							\
+			RB_FLIP_RT(par, field);				\
+	}								\
 }
 
 #define RB_GENERATE_REMOVE(name, type, field, attr)			\
@@ -550,12 +552,11 @@
 name##_RB_REMOVE(struct name *head, struct type *elm)			\
 {									\
 	struct type *child, *old, *parent, *parent_old, *right;		\
-	int color;							\
+	bool old_red, red;						\
 									\
 	old = elm;							\
 	parent_old = parent = RB_PARENT(elm, field);			\
 	right = RB_RIGHT(elm, field);					\
-	color = RB_COLOR(elm, field);					\
 	if (RB_LEFT(elm, field) == NULL)				\
 		elm = child = right;					\
 	else if (right == NULL)						\
@@ -563,32 +564,41 @@
 	else {								\
 		if ((child = RB_LEFT(right, field)) == NULL) {		\
 			child = RB_RIGHT(right, field);			\
-			RB_RIGHT(old, field) = child;			\
+			red = RB_RED_RT(old, field);			\
+			RB_RT(old, field) = child;			\
 			parent = elm = right;				\
 		} else {						\
 			do						\
 				elm = child;				\
 			while ((child = RB_LEFT(elm, field)) != NULL);	\
 			child = RB_RIGHT(elm, field);			\
+			red = RB_RED_RT(parent, field);			\
 			parent = RB_PARENT(elm, field);			\
-			RB_LEFT(parent, field) = child;			\
+			RB_LF(parent, field) = child;			\
 			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
 		}							\
 		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
-		color = RB_COLOR(elm, field);				\
 		elm->field = old->field;				\
 	}								\
-	if (parent_old == NULL)						\
+	if (parent_old == NULL)	{					\
 		RB_ROOT(head) = elm;					\
-	else if (RB_LEFT(parent_old, field) == old)			\
-		RB_LEFT(parent_old, field) = elm;			\
-	else								\
-		RB_RIGHT(parent_old, field) = elm;			\
-	if (child != NULL) {						\
+		old_red = false;					\
+	} else if (RB_LEFT(parent_old, field) == old) {			\
+		old_red = RB_RED_LF(parent_old, field);			\
+		RB_LF(parent_old, field) = elm;				\
+		if (old_red && parent != parent_old)			\
+			RB_FLIP_LF(parent_old, field);			\
+	} else {							\
+		old_red = RB_RED_RT(parent_old, field);			\
+		RB_RT(parent_old, field) = elm;				\
+		if (old_red && parent != parent_old)			\
+			RB_FLIP_RT(parent_old, field);			\
+	}								\
+	if (child != NULL)						\
 		RB_PARENT(child, field) = parent;			\
-		RB_COLOR(child, field) = RB_BLACK;			\
-	} else if (color != RB_RED && parent != NULL)			\
-		name##_RB_REMOVE_COLOR(head, parent);			\
+	else if (parent != NULL &&					\
+		 (parent != parent_old ? !red : !old_red))		\
+		name##_RB_REMOVE_BALANCE(head, parent);			\
 	while (parent != NULL) {					\
 		RB_AUGMENT(parent);					\
 		parent = RB_PARENT(parent, field);			\
@@ -615,15 +625,15 @@
 		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;			\
-	} else								\
+	RB_PARENT(elm, field) = parent;					\
+	RB_LF(elm, field) = RB_RT(elm, field) = NULL;			\
+	if (parent == NULL)						\
 		RB_ROOT(head) = elm;					\
-	name##_RB_INSERT_COLOR(head, elm);				\
+	else if (comp < 0)						\
+		RB_LF(parent, field) = elm;				\
+	else								\
+		RB_RT(parent, field) = elm;				\
+	name##_RB_INSERT_BALANCE(head, elm);				\
 	while (elm != NULL) {						\
 		RB_AUGMENT(elm);					\
 		elm = RB_PARENT(elm, field);				\