--- sys/sys/tree.h.orig	2008-03-21 14:07:15.000000000 +0100
+++ sys/sys/tree.h	2010-05-04 20:16:08.000000000 +0200
@@ -324,15 +324,11 @@
 	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)
-
 #ifndef RB_AUGMENT
 #define RB_AUGMENT(x) (void)(x)
 #endif
 
+/* After rotation, tmp will be the new top element (new elm's parent) */
 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
 	(tmp) = RB_RIGHT(elm, field);					\
 	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {	\
@@ -345,7 +341,7 @@
 		else							\
 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
 	} else								\
-		(head)->rbh_root = (tmp);				\
+		RB_ROOT(head) = (tmp);					\
 	RB_LEFT(tmp, field) = (elm);					\
 	RB_PARENT(elm, field) = (tmp);					\
 	RB_AUGMENT(tmp);						\
@@ -365,7 +361,7 @@
 		else							\
 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
 	} else								\
-		(head)->rbh_root = (tmp);				\
+		RB_ROOT(head) = (tmp);					\
 	RB_RIGHT(tmp, field) = (elm);					\
 	RB_PARENT(elm, field) = (tmp);					\
 	RB_AUGMENT(tmp);						\
@@ -405,41 +401,40 @@
 	while ((parent = RB_PARENT(elm, field)) != NULL &&		\
 	    RB_COLOR(parent, field) == RB_RED) {			\
 		gparent = RB_PARENT(parent, field);			\
+		RB_COLOR(gparent, field) = RB_RED;			\
 		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);\
+				RB_COLOR(parent, field) = RB_BLACK;	\
 				elm = gparent;				\
 				continue;				\
 			}						\
 			if (RB_RIGHT(parent, field) == elm) {		\
 				RB_ROTATE_LEFT(head, parent, tmp, field);\
-				tmp = parent;				\
-				parent = elm;				\
-				elm = tmp;				\
+				elm = parent;				\
+				parent = tmp;				\
 			}						\
-			RB_SET_BLACKRED(parent, gparent, field);	\
+			RB_COLOR(parent, field) = RB_BLACK;		\
 			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);\
+				RB_COLOR(parent, field) = RB_BLACK;	\
 				elm = gparent;				\
 				continue;				\
 			}						\
 			if (RB_LEFT(parent, field) == elm) {		\
 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
-				tmp = parent;				\
-				parent = elm;				\
-				elm = tmp;				\
+				elm = parent;				\
+				parent = tmp;				\
 			}						\
-			RB_SET_BLACKRED(parent, gparent, field);	\
+			RB_COLOR(parent, field) = RB_BLACK;		\
 			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
 		}							\
 	}								\
-	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
+	RB_COLOR(RB_ROOT(head), field) = RB_BLACK;			\
 }									\
 									\
 attr void								\
@@ -451,7 +446,8 @@
 		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_COLOR(tmp, field) = RB_BLACK;	\
+				RB_COLOR(parent, field) = RB_RED;	\
 				RB_ROTATE_LEFT(head, parent, tmp, field);\
 				tmp = RB_RIGHT(parent, field);		\
 			}						\
@@ -465,18 +461,12 @@
 			} 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)) \
-					    != NULL)			\
-						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_ROTATE_RIGHT(head, tmp, elm, field);\
+					tmp = elm;			\
 				}					\
 				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_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
 				RB_ROTATE_LEFT(head, parent, tmp, field);\
 				elm = RB_ROOT(head);			\
 				break;					\
@@ -484,7 +474,8 @@
 		} else {						\
 			tmp = RB_LEFT(parent, field);			\
 			if (RB_COLOR(tmp, field) == RB_RED) {		\
-				RB_SET_BLACKRED(tmp, parent, field);	\
+				RB_COLOR(tmp, field) = RB_BLACK;	\
+				RB_COLOR(parent, field) = RB_RED;	\
 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
 				tmp = RB_LEFT(parent, field);		\
 			}						\
@@ -498,18 +489,12 @@
 			} 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)) \
-					    != NULL)			\
-						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_ROTATE_LEFT(head, tmp, elm, field);\
+					tmp = elm;			\
 				}					\
 				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_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
 				elm = RB_ROOT(head);			\
 				break;					\