svn commit: r361324 - head/sys/sys

[Doug Moore]

Author: dougm
Date: Thu May 21 05:34:02 2020
New Revision: 361324
URL: https://svnweb.freebsd.org/changeset/base/361324

Log:
  For the case when RB_REMOVE requires a nontrivial search to find the
  node to replace the one being removed, restructure to first remove the
  replacement node and correct the parent pointers around it, and then
  let the all-cases code at the end deal with the parent of the deleted
  node, making it point to the replacement node. This removes one or two
  conditional branches.
  
  Reviewed by:	markj
  Tested by:	pho
  Differential Revision:	https://reviews.freebsd.org/D24845

Modified:
  head/sys/sys/tree.h

Modified: head/sys/sys/tree.h
==============================================================================
--- head/sys/sys/tree.h	Thu May 21 05:02:58 2020	(r361323)
+++ head/sys/sys/tree.h	Thu May 21 05:34:02 2020	(r361324)
@@ -562,48 +562,44 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type 
 attr struct type *							\
 name##_RB_REMOVE(struct name *head, struct type *elm)			\
 {									\
-	struct type *child, *parent, *old = elm;			\
+	struct type *child, *parent, *parent_old, *old = elm;		\
 	int color;							\
-	if (RB_LEFT(elm, field) == NULL)				\
-		child = RB_RIGHT(elm, field);				\
-	else if (RB_RIGHT(elm, field) == NULL)				\
-		child = RB_LEFT(elm, field);				\
-	else {								\
+	parent_old = parent = RB_PARENT(elm, field);			\
+	color = RB_COLOR(elm, field);					\
+	if (RB_LEFT(elm, field) == NULL) {				\
+		elm = child = RB_RIGHT(elm, field);			\
+		if (elm != NULL)					\
+			RB_PARENT(elm, field) = parent;			\
+	} else if (RB_RIGHT(elm, field) == NULL) {			\
+		elm = child = RB_LEFT(elm, field);			\
+		RB_PARENT(elm, field) = parent;				\
+	} else {							\
 		elm = RB_RIGHT(old, field);				\
 		if ((child = RB_LEFT(elm, field)) == NULL) {		\
 			child = RB_RIGHT(elm, field);			\
 			RB_RIGHT(old, field) = child;			\
-			RB_PARENT(elm, field) = elm;			\
+			parent = elm;					\
 		} else {						\
 			do						\
 				elm = child;				\
 			while ((child = RB_LEFT(elm, field)) != NULL);	\
 			child = RB_RIGHT(elm, field);			\
+			parent = RB_PARENT(elm, field);			\
+			RB_LEFT(parent, field) = child;			\
+			if (child != NULL)				\
+				RB_PARENT(child, field) = parent;	\
 			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
 		}							\
 		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
-		parent = RB_PARENT(old, field);				\
-		if (parent != NULL) {					\
-			if (RB_LEFT(parent, field) == old)		\
-				RB_LEFT(parent, field) = elm;		\
-			else						\
-				RB_RIGHT(parent, field) = elm;		\
-		} else							\
-			RB_ROOT(head) = elm;				\
+		color = RB_COLOR(elm, field);				\
+		elm->field = old->field;				\
 	}								\
-	parent = RB_PARENT(elm, field);					\
-	color = RB_COLOR(elm, field);					\
-	if (child != NULL)						\
-		RB_PARENT(child, field) = parent;			\
-	if (parent != NULL) {						\
-		if (RB_LEFT(parent, field) == elm)			\
-			RB_LEFT(parent, field) = child;			\
-		else							\
-			RB_RIGHT(parent, field) = child;		\
-	} else								\
-		RB_ROOT(head) = child;					\
-	if (elm != old)							\
-		(elm)->field = (old)->field;				\
+	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 (color == RB_BLACK)						\
 		name##_RB_REMOVE_COLOR(head, parent, child);		\
 	while (parent != NULL) {					\