Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -378,13 +378,13 @@
 	} while ((rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL); \
 } while (0)
 
-#define RB_SWAP_CHILD(head, out, in, field) do {			\
-	if (RB_PARENT(out, field) == NULL)				\
+#define RB_SWAP_CHILD(head, parent, out, in, field) do {		\
+	if ((parent) == NULL)						\
 		RB_ROOT(head) = (in);					\
-	else if ((out) == RB_LEFT(RB_PARENT(out, field), field))	\
-		RB_LEFT(RB_PARENT(out, field), field) = (in);		\
+	else if ((out) == RB_LEFT(parent, field))			\
+		RB_LEFT(parent, field) = (in);				\
 	else								\
-		RB_RIGHT(RB_PARENT(out, field), field) = (in);		\
+		RB_RIGHT(parent, field) = (in);				\
 } while (/*CONSTCOND*/ 0)
 
 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
@@ -392,7 +392,7 @@
 		RB_SET_PARENT(RB_RIGHT(elm, field), elm, field);	\
 	}								\
 	RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);		\
-	RB_SWAP_CHILD(head, elm, tmp, field);				\
+	RB_SWAP_CHILD(head, RB_PARENT(elm,field), elm, tmp, field);	\
 	RB_LEFT(tmp, field) = (elm);					\
 	RB_SET_PARENT(elm, tmp, field);					\
 } while (/*CONSTCOND*/ 0)
@@ -402,7 +402,7 @@
 		RB_SET_PARENT(RB_LEFT(elm, field), elm, field);		\
 	}								\
 	RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);		\
-	RB_SWAP_CHILD(head, elm, tmp, field);				\
+	RB_SWAP_CHILD(head, RB_PARENT(elm, field), elm, tmp, field);	\
 	RB_RIGHT(tmp, field) = (elm);					\
 	RB_SET_PARENT(elm, tmp, field);					\
 } while (/*CONSTCOND*/ 0)
@@ -667,37 +667,36 @@
 
 #define RB_GENERATE_REMOVE(name, type, field, attr)			\
 attr struct type *							\
-name##_RB_REMOVE(struct name *head, struct type *elm)			\
+name##_RB_REMOVE(struct name *head, struct type *old)			\
 {									\
-	struct type *child, *old, *parent, *right;			\
+	struct type *child, *elm, *old_parent, *old_up, *parent;	\
 									\
-	old = elm;							\
-	parent = RB_PARENT(elm, field);					\
-	right = RB_RIGHT(elm, field);					\
-	if (RB_LEFT(elm, field) == NULL)				\
-		elm = child = right;					\
-	else if (right == NULL)						\
-		elm = child = RB_LEFT(elm, field);			\
-	else {								\
-		if ((child = RB_LEFT(right, field)) == NULL) {		\
-			child = RB_RIGHT(right, field);			\
-			RB_RIGHT(old, field) = child;			\
-			parent = elm = right;				\
-		} else {						\
-			do						\
-				elm = child;				\
-			while ((child = RB_LEFT(elm, field)) != NULL);	\
-			child = RB_RIGHT(elm, field);			\
+	old_up = RB_UP(old, field);					\
+	old_parent = RB_PARENT(old, field);				\
+	elm = RB_RIGHT(old, field);					\
+	child = RB_LEFT(old, field);					\
+	if (elm == NULL || child == NULL) {				\
+		__uintptr_t sum = (__uintptr_t)elm + (__uintptr_t)child; \
+		elm = child = (struct type *)sum;			\
+		parent = old_parent;					\
+	} else {							\
+		parent = elm;						\
+		while (RB_LEFT(elm, field) != NULL)			\
+			elm = RB_LEFT(elm, field);			\
+		RB_SET_PARENT(child, elm, field);			\
+		RB_LEFT(elm, field) = child;				\
+		child = RB_RIGHT(elm, field);				\
+		if (parent != elm) {					\
+			RB_SET_PARENT(parent, elm, field);		\
+			RB_RIGHT(elm, field) = parent;			\
 			parent = RB_PARENT(elm, field);			\
 			RB_LEFT(parent, field) = child;			\
-			RB_SET_PARENT(RB_RIGHT(old, field), elm, field);\
 		}							\
-		RB_SET_PARENT(RB_LEFT(old, field), elm, field);		\
-		elm->field = old->field;				\
+		RB_UP(elm, field) = old_up;				\
 	}								\
-	RB_SWAP_CHILD(head, old, elm, field);				\
+	RB_SWAP_CHILD(head, old_parent, old, elm, field);		\
 	if (child != NULL)						\
-		RB_SET_PARENT(child, parent, field);			\
+		RB_UP(child, field) = parent;				\
 	if (parent != NULL) {						\
 		name##_RB_REMOVE_COLOR(head, parent, child);		\
 		if (parent == elm && RB_LEFT(parent, field) == NULL)	\