[newlib-cygwin] For the case when RB_REMOVE requires a nontrivial

[newlib-cygwin] For the case when RB_REMOVE requires a nontrivial

[Sebastian Huber]

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

commit 9db2b545710ad398a9012094d33b7e8884013227
Author: dougm <dougm@FreeBSD.org>
Date:   Thu May 21 05:34:02 2020 +0000

    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

Diff:
---
 newlib/libc/include/sys/tree.h | 52 +++++++++++++++++++-----------------------
 1 file changed, 24 insertions(+), 28 deletions(-)

diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index 5c31ff2ea..b1e5e23a7 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -562,48 +562,44 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm)
 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) {					\