[newlib-cygwin] In concluding RB_REMOVE_COLOR, in the case when

[Sebastian Huber <sh@sourceware.org>]

https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;h=d03eaf36dc30bf41fc57f8de100c105f49063429

commit d03eaf36dc30bf41fc57f8de100c105f49063429
Author: dougm <dougm@FreeBSD.org>
Date:   Sat Jun 20 20:25:39 2020 +0000

    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

Diff:
---
 newlib/libc/include/sys/tree.h | 26 +++++++++++---------------
 1 file changed, 11 insertions(+), 15 deletions(-)

diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index 372c001b9..2e1cc1eda 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -493,21 +493,19 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent)		\
 				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_COLOR(oleft, field) = RB_BLACK;	\
-				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(oleft, field) = RB_BLACK;	\
+				tmp = oleft;				\
+			} else {					\
 				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 *parent)		\
 				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);	\