svn commit: r362450 - head/sys/sys

[Doug Moore]

Author: dougm
Date: Sat Jun 20 20:25:39 2020
New Revision: 362450
URL: https://svnweb.freebsd.org/changeset/base/362450

Log:
  In concluding RB_REMOVE_COLOR, in the case when the sibling of the
  root of the too-short tree is black and at least one of the children
  of that sibling is red, either one or two rotations finish the
  rebalancing. In the case when both of the children are red, the
  current implementation uses two rotations where only one is
  necessary. This change removes that extra rotation, and in that case
  also removes a needless black-to-red-to-black recoloring.
  
  Reviewed by:	markj
  Differential Revision:	https://reviews.freebsd.org/D25335

Modified:
  head/sys/sys/tree.h

Modified: head/sys/sys/tree.h
==============================================================================
--- head/sys/sys/tree.h	Sat Jun 20 20:21:04 2020	(r362449)
+++ head/sys/sys/tree.h	Sat Jun 20 20:25:39 2020	(r362450)
@@ -493,21 +493,19 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type 
 				RB_ROTATE_LEFT(head, parent, tmp, field);\
 				tmp = RB_RIGHT(parent, field);		\
 			}						\
-			if (RB_ISRED(RB_LEFT(tmp, field), field)) {	\
+			if (RB_ISRED(RB_RIGHT(tmp, field), field))	\
+				RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \
+			else if (RB_ISRED(RB_LEFT(tmp, field), field)) { \
 				struct type *oleft;			\
-				oleft = RB_LEFT(tmp, field);		\
+				RB_ROTATE_RIGHT(head, tmp, oleft, field); \
 				RB_COLOR(oleft, field) = RB_BLACK;	\
+				tmp = oleft;				\
+			} else {					\
 				RB_COLOR(tmp, field) = RB_RED;		\
-				RB_ROTATE_RIGHT(head, tmp, oleft, field); \
-				tmp = RB_RIGHT(parent, field);		\
-			} else if (!RB_ISRED(RB_RIGHT(tmp, field), field)) { \
-				RB_COLOR(tmp, field) = RB_RED;		\
 				elm = parent;				\
 				parent = RB_PARENT(elm, field);		\
 				continue;				\
 			}						\
-			if (RB_ISRED(RB_RIGHT(tmp, field), field))	\
-				RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \
 			RB_COLOR(tmp, field) = RB_COLOR(parent, field);	\
 			RB_COLOR(parent, field) = RB_BLACK;		\
 			RB_ROTATE_LEFT(head, parent, tmp, field);	\
@@ -520,21 +518,19 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type 
 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
 				tmp = RB_LEFT(parent, field);		\
 			}						\
-			if (RB_ISRED(RB_RIGHT(tmp, field), field)) {	\
+			if (RB_ISRED(RB_LEFT(tmp, field), field))	\
+				RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \
+			else if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \
 				struct type *oright;			\
-				oright = RB_RIGHT(tmp, field);		\
-				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_COLOR(oright, field) = RB_BLACK;	\
+				tmp = oright;				\
 			} else if (!RB_ISRED(RB_LEFT(tmp, field), field)) { \
 				RB_COLOR(tmp, field) = RB_RED;		\
 				elm = parent;				\
 				parent = RB_PARENT(elm, field);		\
 				continue;				\
 			}						\
-			if (RB_ISRED(RB_LEFT(tmp, field), field))	\
-				RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \
 			RB_COLOR(tmp, field) = RB_COLOR(parent, field);	\
 			RB_COLOR(parent, field) = RB_BLACK;		\
 			RB_ROTATE_RIGHT(head, parent, tmp, field);	\