Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -647,35 +647,47 @@
 
 #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 *out)			\
 {									\
-	struct type *child, *old, *parent, *right;			\
+	struct type *child, *in, *left, *parent, *right;		\
 									\
-	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);			\
-			parent = RB_PARENT(elm, field);			\
+	left = RB_LEFT(out, field);					\
+	right = RB_RIGHT(out, field);					\
+	if (left == NULL || right == NULL) {				\
+		child = in = (left == NULL) ? right : left;		\
+		parent = RB_PARENT(out, field);				\
+	} else {							\
+		if ((in = RB_LEFT(right, field)) != NULL) {		\
+			while (RB_LEFT(in, field) != NULL)		\
+				in = RB_LEFT(in, field);		\
+			parent = RB_PARENT(in, field);			\
+			child =	RB_RIGHT(in, field);			\
 			RB_LEFT(parent, field) = child;			\
-			RB_SET_PARENT(RB_RIGHT(old, field), elm, field);\
+			RB_SET_PARENT(left, in, field);			\
+		} else if ((in = RB_RIGHT(left, field)) != NULL) {	\
+			if (RB_RIGHT(in, field) != NULL) {		\
+				parent = in;				\
+				in = RB_RIGHT(in, field);		\
+				child = NULL;				\
+			} else {					\
+				parent = left;				\
+				child = RB_LEFT(in, field);		\
+			}						\
+			RB_RIGHT(parent, field) = child;		\
+			RB_SET_PARENT(left, in, field);			\
+		} else if ((child = RB_LEFT(left, field)) == NULL &&	\
+		    (child = RB_RIGHT(right, field)) != NULL) {		\
+			parent = in = right;				\
+			RB_RIGHT(out, field) = child;			\
+			right = left;					\
+		} else {						\
+			parent = in = left;				\
+			RB_LEFT(out, field) = child;			\
 		}							\
-		RB_SET_PARENT(RB_LEFT(old, field), elm, field);		\
-		elm->field = old->field;				\
+		RB_SET_PARENT(right, in, field);			\
+		in->field = out->field;					\
 	}								\
-	RB_SWAP_CHILD(head, old, elm, field);				\
+	RB_SWAP_CHILD(head, out, in, field);				\
 	if (child != NULL)						\
 		RB_SET_PARENT(child, parent, field);			\
 	if (parent != NULL)						\
@@ -684,7 +696,7 @@
 		RB_AUGMENT(parent);					\
 		parent = RB_PARENT(parent, field);			\
 	}								\
-	return (old);							\
+	return (out);							\
 }
 
 #define RB_GENERATE_INSERT(name, type, field, cmp, attr)		\