Index: sys/compat/linuxkpi/common/include/linux/rbtree.h
===================================================================
--- sys/compat/linuxkpi/common/include/linux/rbtree.h
+++ sys/compat/linuxkpi/common/include/linux/rbtree.h
@@ -41,8 +41,8 @@
 struct rb_node {
 	RB_ENTRY(rb_node)	__entry;
 };
-#define	rb_left		__entry.rbe_left
-#define	rb_right	__entry.rbe_right
+#define	rb_left		__entry.rbe_link[RB_RED_L]
+#define	rb_right	__entry.rbe_link[RB_RED_R]
 
 /*
  * We provide a false structure that has the same bit pattern as tree.h
@@ -74,8 +74,11 @@
 #define RB_EMPTY_NODE(node)     (RB_PARENT(node, __entry) == node)
 #define RB_CLEAR_NODE(node)     RB_SET_PARENT(node, node, __entry)
 
-#define	rb_insert_color(node, root)					\
-	linux_root_RB_INSERT_COLOR((struct linux_root *)(root), (node))
+#define	rb_insert_color(node, root) do {				\
+	if (rb_parent(node))						\
+		linux_root_RB_INSERT_COLOR((struct linux_root *)(root),	\
+		    rb_parent(node), (node));				\
+} while (0)
 #define	rb_erase(node, root)						\
 	linux_root_RB_REMOVE((struct linux_root *)(root), (node))
 #define	rb_next(node)	RB_NEXT(linux_root, NULL, (node))
@@ -132,7 +135,8 @@
     struct rb_root *root)
 {
 
-	RB_SWAP_CHILD((struct linux_root *)root, victim, new, __entry);
+	RB_SWAP_CHILD((struct linux_root *)root, rb_parent(victim),
+	    victim, new, __entry);
 	if (victim->rb_left)
 		RB_SET_PARENT(victim->rb_left, new, __entry);
 	if (victim->rb_right)
@@ -144,7 +148,9 @@
 rb_insert_color_cached(struct rb_node *node, struct rb_root_cached *root,
     bool leftmost)
 {
-	linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, node);
+	if (rb_parent(node))
+		linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root,
+		    rb_parent(node), node);
 	if (leftmost)
 		root->rb_leftmost = node;
 }
Index: sys/kern/subr_stats.c
===================================================================
--- sys/kern/subr_stats.c
+++ sys/kern/subr_stats.c
@@ -3406,6 +3406,13 @@
 
 				Q_TOSTR(rbctd64->mu, -1, 10, qstr,
 				    sizeof(qstr));
+				struct voistatdata_tdgstctd64 *parent;
+				parent = RB_PARENT(rbctd64, rblnk);
+				int rb_color =
+					!parent ? 0 :
+					RB_LEFT(parent, rblnk) == rbctd64 ?
+					(RB_BITS(parent, rblnk) & RB_RED_L) != 0 :
+					(RB_BITS(parent, rblnk) & RB_RED_R) != 0;
 				printf(" RB ctd=%3d p=%3d l=%3d r=%3d c=%2d "
 				    "mu=%s\n",
 				    (int)ARB_SELFIDX(ctd64tree, rbctd64),
@@ -3415,7 +3422,7 @@
 				      RB_LEFT(rbctd64, rblnk)),
 				    (int)ARB_SELFIDX(ctd64tree,
 				      RB_RIGHT(rbctd64, rblnk)),
-				    RB_COLOR(rbctd64, rblnk),
+				    rb_color,
 				    qstr);
 
 				panic("RB@%p and ARB@%p trees differ\n",
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -318,13 +318,9 @@
 
 #define RB_ENTRY(type)							\
 struct {								\
-	struct type *rbe_left;		/* left element */		\
-	struct type *rbe_right;		/* right element */		\
-	struct type *rbe_parent;	/* parent element */		\
+	struct type *rbe_link[3];					\
 }
-
-#define RB_LEFT(elm, field)		(elm)->field.rbe_left
-#define RB_RIGHT(elm, field)		(elm)->field.rbe_right
+#define RB_LINK(elm, dir, field)	(elm)->field.rbe_link[dir]
 
 /*
  * With the expectation that any object of struct type has an
@@ -333,16 +329,16 @@
  * always zero, this implementation sets those bits to indicate
  * that the left or right child of the tree node is "red".
  */
-#define RB_UP(elm, field)		(elm)->field.rbe_parent
+#define RB_UP(elm, field)		RB_LINK(elm, 0, field)
 #define RB_BITS(elm, field)		(*(__uintptr_t *)&RB_UP(elm, field))
 #define RB_RED_L			((__uintptr_t)1)
 #define RB_RED_R			((__uintptr_t)2)
 #define RB_RED_MASK			((__uintptr_t)3)
+#define RB_LEFT(elm, field)		RB_LINK(elm, RB_RED_L, field)
+#define RB_RIGHT(elm, field)		RB_LINK(elm, RB_RED_R, field)
 #define RB_FLIP_LEFT(elm, field)	(RB_BITS(elm, field) ^= RB_RED_L)
 #define RB_FLIP_RIGHT(elm, field)	(RB_BITS(elm, field) ^= RB_RED_R)
 #define RB_FLIP_ALL(elm, field)		(RB_BITS(elm, field) ^= RB_RED_MASK)
-#define RB_RED_LEFT(elm, field)		((RB_BITS(elm, field) & RB_RED_L) != 0)
-#define RB_RED_RIGHT(elm, field)	((RB_BITS(elm, field) & RB_RED_R) != 0)
 #define RB_PARENT(elm, field)		((__typeof(RB_UP(elm, field)))	\
 					 (RB_BITS(elm, field) & ~RB_RED_MASK))
 #define RB_ROOT(head)			(head)->rbh_root
@@ -358,52 +354,36 @@
 	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;		\
 } while (/*CONSTCOND*/ 0)
 
-#define RB_COLOR(elm, field)	(RB_PARENT(elm, field) == NULL ? 0 :	\
-				RB_LEFT(RB_PARENT(elm, field), field) == elm ? \
-				RB_RED_LEFT(RB_PARENT(elm, field), field) : \
-				RB_RED_RIGHT(RB_PARENT(elm, field), field))
-
 /*
  * 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.
  */
 #ifndef RB_AUGMENT
-#define RB_AUGMENT(x)	break
-#endif
-
+#define RB_AUGMENT(x)	do {} while (0)
+#define RB_UPDATE_AUGMENT(elm, field) do {} while (0)
+#else
 #define RB_UPDATE_AUGMENT(elm, field) do {				\
 	__typeof(elm) rb_update_tmp = (elm);				\
 	do {								\
 		RB_AUGMENT(rb_update_tmp);				\
 	} while ((rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL); \
 } while (0)
+#endif
 
-#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);		\
-} while (/*CONSTCOND*/ 0)
-
-#define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
-	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {	\
-		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_LEFT(tmp, field) = (elm);					\
-	RB_SET_PARENT(elm, tmp, field);					\
+		RB_RIGHT(parent, field) = (in);				\
 } while (/*CONSTCOND*/ 0)
 
-#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
-	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {	\
-		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_RIGHT(tmp, field) = (elm);					\
+#define RB_ROTATE(elm, tmp, dir, field) do {				\
+	if ((RB_LINK(elm, dir ^ RB_RED_MASK, field) =			\
+	    RB_LINK(tmp, dir, field)) != NULL)				\
+		RB_SET_PARENT(RB_LINK(tmp, dir, field), elm, field);	\
+	RB_LINK(tmp, dir, field) = (elm);				\
 	RB_SET_PARENT(elm, tmp, field);					\
 } while (/*CONSTCOND*/ 0)
 
@@ -424,7 +404,8 @@
 	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 *)
+	attr void name##_RB_INSERT_COLOR(struct name *,			\
+	    struct type *, struct type *)
 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\
 	attr void name##_RB_REMOVE_COLOR(struct name *,			\
 	    struct type *, struct type *)
@@ -466,7 +447,8 @@
 
 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\
 attr void								\
-name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
+name##_RB_INSERT_COLOR(struct name *head,				\
+    struct type *parent, struct type *elm)				\
 {									\
 	/*								\
 	 * Initially, elm is a leaf.  Either its parent was previously	\
@@ -479,69 +461,43 @@
 	 * when a value has been assigned to 'child' in the previous    \
 	 * one.								\
 	 */								\
-	struct type *child, *parent;					\
-	while ((parent = RB_PARENT(elm, field)) != NULL) {		\
-		if (RB_LEFT(parent, field) == elm) {			\
-			if (RB_RED_LEFT(parent, field)) {		\
-				RB_FLIP_LEFT(parent, field);		\
-				return;					\
-			}						\
-			RB_FLIP_RIGHT(parent, field);			\
-			if (RB_RED_RIGHT(parent, field)) {		\
-				child = elm;				\
-				elm = parent;				\
-				continue;				\
-			}						\
-			if (RB_RED_RIGHT(elm, field))			\
-				child = elm;				\
-			else {						\
-				/* coverity[uninit_use] */		\
-				RB_ROTATE_LEFT(head, elm, child, field);\
-				if (RB_RED_RIGHT(child, field))		\
-					RB_FLIP_LEFT(parent, field);	\
-				if (RB_RED_LEFT(child, field))		\
-					RB_FLIP_ALL(elm, field);	\
-				else					\
-					RB_FLIP_LEFT(elm, field);	\
-				if ((RB_BITS(child, field) &		\
-				    RB_RED_MASK) == 0)			\
-					elm = child;			\
-			}						\
-			RB_ROTATE_RIGHT(head, parent, child, field);	\
-		} else {						\
-			if (RB_RED_RIGHT(parent, field)) {		\
-				RB_FLIP_RIGHT(parent, field);		\
-				return;					\
-			}						\
-			RB_FLIP_LEFT(parent, field);			\
-			if (RB_RED_LEFT(parent, field)) {		\
-				child = elm;				\
-				elm = parent;				\
-				continue;				\
-			}						\
-			if (RB_RED_LEFT(elm, field))			\
-				child = elm;				\
-			else {						\
-				/* coverity[uninit_use] */		\
-				RB_ROTATE_RIGHT(head, elm, child, field);\
-				if (RB_RED_LEFT(child, field))		\
-					RB_FLIP_RIGHT(parent, field);	\
-				if (RB_RED_RIGHT(child, field))		\
-					RB_FLIP_ALL(elm, field);	\
-				else					\
-					RB_FLIP_RIGHT(elm, field);	\
-				if ((RB_BITS(child, field) &		\
-				    RB_RED_MASK) == 0)			\
-					elm = child;			\
-			}						\
-			RB_ROTATE_LEFT(head, parent, child, field);	\
+	struct type *child, *gpar;					\
+	__uintptr_t dir, red;						\
+	do {								\
+		dir = RB_LEFT(parent, field) == elm ?			\
+		    RB_RED_L : RB_RED_R;				\
+		red = RB_BITS(parent, field);				\
+		gpar = RB_PARENT(parent, field);			\
+		if (red & dir) {					\
+			RB_BITS(parent, field) ^= dir;			\
+			return;						\
 		}							\
-		RB_BITS(child, field) &= ~RB_RED_MASK;			\
-		if (elm != child)					\
-			RB_AUGMENT(elm);				\
-		RB_AUGMENT(parent);					\
-		break;							\
-	}								\
+		RB_BITS(parent, field) ^= dir ^ RB_RED_MASK;		\
+		if (red & RB_RED_MASK)					\
+			break;						\
+	} while (child = elm, elm = parent, parent = gpar);		\
+	if (!parent)							\
+		return;							\
+	if (RB_BITS(elm, field) & dir) {				\
+		/* coverity[uninit_use] */				\
+		RB_ROTATE(elm, child, dir, field);			\
+		red = RB_BITS(child, field);				\
+		if (red & (dir ^ RB_RED_MASK))				\
+			RB_BITS(parent, field) ^= dir;			\
+		if (red & dir)						\
+			RB_FLIP_ALL(elm, field);			\
+		else							\
+			RB_BITS(elm, field) ^= dir;			\
+		if (!(red & RB_RED_MASK))				\
+			elm = child;					\
+	} else								\
+		child = elm;						\
+	RB_ROTATE(parent, child, dir ^ RB_RED_MASK, field);		\
+	RB_UP(child, field) = gpar;					\
+	RB_SWAP_CHILD(head, gpar, parent, child, field);		\
+	if (elm != child)						\
+		RB_AUGMENT(elm);					\
+	RB_AUGMENT(parent);						\
 }
 
 #ifndef RB_STRICT_HST
@@ -560,144 +516,99 @@
 name##_RB_REMOVE_COLOR(struct name *head,				\
     struct type *parent, struct type *elm)				\
 {									\
-	struct type *sib;						\
-	if (RB_LEFT(parent, field) == elm &&				\
-	    RB_RIGHT(parent, field) == elm) {				\
-		RB_BITS(parent, field) &= ~RB_RED_MASK;			\
+	struct type *gpar, *sib;					\
+	__uintptr_t dir, red;						\
+	if (RB_LEFT(parent, field) == RB_RIGHT(parent, field)) {	\
 		elm = parent;						\
-		parent = RB_PARENT(elm, field);				\
-		if (parent == NULL)					\
+		RB_BITS(elm, field) &= ~RB_RED_MASK;			\
+		if ((parent = RB_UP(elm, field)) == NULL)		\
 			return;						\
 	}								\
 	do {								\
-		if (RB_LEFT(parent, field) == elm) {			\
-			if (!RB_RED_LEFT(parent, field)) {		\
-				RB_FLIP_LEFT(parent, field);		\
-				return;					\
-			}						\
-			if (RB_RED_RIGHT(parent, field)) {		\
-				RB_FLIP_RIGHT(parent, field);		\
-				elm = parent;				\
-				continue;				\
-			}						\
-			sib = RB_RIGHT(parent, field);			\
-			switch (RB_BITS(sib, field) & RB_RED_MASK) {	\
-			case RB_RED_MASK:				\
-				RB_FLIP_ALL(sib, field);		\
-				elm = parent;				\
-				continue;				\
-			case RB_RED_R:					\
-				elm = RB_LEFT(sib, field);		\
-				RB_ROTATE_RIGHT(head, sib, elm, field);	\
-				if (RB_RED_LEFT(elm, field))		\
-					RB_FLIP_ALL(parent, field);	\
-				else					\
-					RB_FLIP_LEFT(parent, field);	\
-				if (RB_RED_RIGHT(elm, field))		\
-					RB_FLIP_ALL(sib, field);	\
-				else					\
-					RB_FLIP_RIGHT(sib, field);	\
-				RB_BITS(elm, field) |= RB_RED_MASK;	\
-				break;					\
-			case RB_RED_L:					\
-				if (RB_STRICT_HST && elm != NULL) {	\
-					RB_FLIP_RIGHT(parent, field);	\
-					RB_FLIP_ALL(sib, field);	\
-					elm = sib;			\
-					break;				\
-				}					\
-				RB_FLIP_LEFT(parent, field);		\
-				/* FALLTHROUGH */			\
-			default:					\
-				RB_FLIP_RIGHT(sib, field);		\
-				elm = sib;				\
-				break;					\
-			}						\
-			RB_ROTATE_LEFT(head, parent, elm, field);	\
-		} else {						\
-			if (!RB_RED_RIGHT(parent, field)) {		\
-				RB_FLIP_RIGHT(parent, field);		\
-				return;					\
-			}						\
-			if (RB_RED_LEFT(parent, field)) {		\
-				RB_FLIP_LEFT(parent, field);		\
-				elm = parent;				\
-				continue;				\
-			}						\
-			sib = RB_LEFT(parent, field);			\
-			switch (RB_BITS(sib, field) & RB_RED_MASK) {	\
-			case RB_RED_MASK:				\
-				RB_FLIP_ALL(sib, field);		\
-				elm = parent;				\
-				continue;				\
-			case RB_RED_L:					\
-				elm = RB_RIGHT(sib, field);		\
-				RB_ROTATE_LEFT(head, sib, elm, field);	\
-				if (RB_RED_RIGHT(elm, field))		\
-					RB_FLIP_ALL(parent, field);	\
-				else					\
-					RB_FLIP_RIGHT(parent, field);	\
-				if (RB_RED_LEFT(elm, field))		\
-					RB_FLIP_ALL(sib, field);	\
-				else					\
-					RB_FLIP_LEFT(sib, field);	\
-				RB_BITS(elm, field) |= RB_RED_MASK;	\
-				break;					\
-			case RB_RED_R:					\
-				if (RB_STRICT_HST && elm != NULL) {	\
-					RB_FLIP_LEFT(parent, field);	\
-					RB_FLIP_ALL(sib, field);	\
-					elm = sib;			\
-					break;				\
-				}					\
-				RB_FLIP_RIGHT(parent, field);		\
-				/* FALLTHROUGH */			\
-			default:					\
-				RB_FLIP_LEFT(sib, field);		\
-				elm = sib;				\
-				break;					\
-			}						\
-			RB_ROTATE_RIGHT(head, parent, elm, field);	\
+		dir = RB_LEFT(parent, field) == elm ?			\
+		    RB_RED_L : RB_RED_R;				\
+		red = RB_BITS(parent, field);				\
+		gpar = RB_PARENT(parent, field);			\
+		if (~red & dir) {					\
+			RB_BITS(parent, field) ^= dir;			\
+			return;						\
 		}							\
-		if (sib != elm)						\
-			RB_AUGMENT(sib);				\
-		break;							\
-	} while ((parent = RB_PARENT(elm, field)) != NULL);		\
+		if (!(~red & RB_RED_MASK)) {				\
+			RB_BITS(parent, field) ^= dir ^ RB_RED_MASK;	\
+			continue;					\
+		}							\
+		sib = RB_LINK(parent, dir ^ RB_RED_MASK, field);	\
+		red = RB_BITS(sib, field);				\
+		if (~red & RB_RED_MASK)					\
+			break;						\
+		RB_FLIP_ALL(sib, field);				\
+	} while (elm = parent, parent = gpar);				\
+	if (!parent)							\
+		return;							\
+	if (red & (dir ^ RB_RED_MASK)) {				\
+		elm = RB_LINK(sib, dir, field);				\
+		RB_ROTATE(sib, elm, dir ^ RB_RED_MASK, field);		\
+		red = RB_BITS(elm, field);				\
+		if (red & dir)						\
+			RB_FLIP_ALL(parent, field);			\
+		else							\
+			RB_BITS(parent, field) ^= dir;			\
+		if (red & (dir ^ RB_RED_MASK))				\
+			RB_FLIP_ALL(sib, field);			\
+		else							\
+			RB_BITS(sib, field) ^= dir ^ RB_RED_MASK;	\
+		RB_BITS(elm, field) |= RB_RED_MASK;			\
+	} else {							\
+		if ((red & dir) && RB_STRICT_HST && elm != NULL) {	\
+			RB_BITS(parent, field) ^= dir ^ RB_RED_MASK;	\
+			RB_FLIP_ALL(sib, field);			\
+		} else if (red & dir) {					\
+			RB_BITS(parent, field) ^= dir;			\
+			RB_BITS(sib, field) ^= dir ^ RB_RED_MASK;	\
+		} else							\
+			RB_BITS(sib, field) ^= dir ^ RB_RED_MASK;	\
+		elm = sib;						\
+	}								\
+	RB_ROTATE(parent, elm, dir, field);				\
+	RB_SET_PARENT(elm, gpar, field);				\
+	RB_SWAP_CHILD(head, gpar, parent, elm, field);			\
+	if (sib != elm)							\
+		RB_AUGMENT(sib);					\
 }
 
 #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) {				\
+		if (elm == NULL)					\
+			elm = child;					\
+		child = elm;						\
+		parent = old_parent;					\
+	} else {							\
+		parent = elm;						\
+		while (RB_LEFT(elm, field))				\
+			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)	\
@@ -712,28 +623,23 @@
 attr struct type *							\
 name##_RB_INSERT(struct name *head, struct type *elm)			\
 {									\
-	struct type *tmp;						\
 	struct type *parent = NULL;					\
-	__typeof(cmp(NULL, NULL)) comp = 0;				\
-	tmp = RB_ROOT(head);						\
-	while (tmp) {							\
-		parent = tmp;						\
+	struct type **tmp = &RB_ROOT(head);				\
+	__typeof(cmp(NULL, NULL)) comp;					\
+	while (*tmp) {							\
+		parent = *tmp;						\
 		comp = (cmp)(elm, parent);				\
 		if (comp < 0)						\
-			tmp = RB_LEFT(tmp, field);			\
+			tmp = &RB_LEFT(parent, field);			\
 		else if (comp > 0)					\
-			tmp = RB_RIGHT(tmp, field);			\
+			tmp = &RB_RIGHT(parent, field);			\
 		else							\
-			return (tmp);					\
+			return (parent);				\
 	}								\
+	*tmp = elm;							\
 	RB_SET(elm, parent, field);					\
-	if (parent == NULL)						\
-		RB_ROOT(head) = elm;					\
-	else if (comp < 0)						\
-		RB_LEFT(parent, field) = elm;				\
-	else								\
-		RB_RIGHT(parent, field) = elm;				\
-	name##_RB_INSERT_COLOR(head, elm);				\
+	if (parent != NULL)						\
+		name##_RB_INSERT_COLOR(head, parent, elm);		\
 	RB_UPDATE_AUGMENT(elm, field);					\
 	return (NULL);							\
 }