public inbox for newlib-cvs@sourceware.org
help / color / mirror / Atom feed
* [newlib-cygwin] In concluding RB_REMOVE_COLOR, in the case when
@ 2020-10-26 13:32 Sebastian Huber
0 siblings, 0 replies; only message in thread
From: Sebastian Huber @ 2020-10-26 13:32 UTC (permalink / raw)
To: newlib-cvs
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); \
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2020-10-26 13:32 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-10-26 13:32 [newlib-cygwin] In concluding RB_REMOVE_COLOR, in the case when Sebastian Huber
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).