public inbox for newlib-cvs@sourceware.org
help / color / mirror / Atom feed
* [newlib-cygwin] sys/tree.h: Add parent rotations
@ 2021-10-07 16:02 Sebastian Huber
0 siblings, 0 replies; only message in thread
From: Sebastian Huber @ 2021-10-07 16:02 UTC (permalink / raw)
To: newlib-cvs
https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;h=5f7f27c81736c11c35c119cc5f18231eb8aaecec
commit 5f7f27c81736c11c35c119cc5f18231eb8aaecec
Author: Sebastian Huber <sebastian.huber@embedded-brains.de>
Date: Tue Oct 5 15:43:34 2021 +0200
sys/tree.h: Add parent rotations
Add specialized rotations RB_PARENT_ROTATE_LEFT() and RB_PARENT_ROTATE_RIGHT()
which may be used if the parent node exists and the direction of the child is
known. The specialized rotations are derived from RB_ROTATE_LEFT() and
RB_ROTATE_RIGHT() where the RB_SWAP_CHILD() was replaced by a simple
assignment.
Diff:
---
newlib/libc/include/sys/tree.h | 43 ++++++++++++++++++++++++++++++++++++++----
1 file changed, 39 insertions(+), 4 deletions(-)
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index 180809e9b..f6190f7f4 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -381,6 +381,37 @@ struct { \
RB_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)
+/*
+ * The RB_PARENT_ROTATE_LEFT() and RB_PARENT_ROTATE_RIGHT() rotations are
+ * specialized versions of RB_ROTATE_LEFT() and RB_ROTATE_RIGHT() which may be
+ * used if the parent node exists and the direction of the child element is
+ * known.
+ */
+
+#define RB_PARENT_ROTATE_LEFT(parent, left, tmp, field) do { \
+ (tmp) = RB_RIGHT(left, field); \
+ if ((RB_RIGHT(left, field) = RB_LEFT(tmp, field)) != NULL) { \
+ RB_SET_PARENT(RB_RIGHT(left, field), left, field); \
+ } \
+ RB_SET_PARENT(tmp, parent, field); \
+ RB_LEFT(parent, field) = (tmp); \
+ RB_LEFT(tmp, field) = (left); \
+ RB_SET_PARENT(left, tmp, field); \
+ RB_AUGMENT(left); \
+} while (/*CONSTCOND*/ 0)
+
+#define RB_PARENT_ROTATE_RIGHT(parent, right, tmp, field) do { \
+ (tmp) = RB_LEFT(right, field); \
+ if ((RB_LEFT(right, field) = RB_RIGHT(tmp, field)) != NULL) { \
+ RB_SET_PARENT(RB_LEFT(right, field), right, field); \
+ } \
+ RB_SET_PARENT(tmp, parent, field); \
+ RB_RIGHT(parent, field) = (tmp); \
+ RB_RIGHT(tmp, field) = (right); \
+ RB_SET_PARENT(right, tmp, field); \
+ RB_AUGMENT(right); \
+} while (/*CONSTCOND*/ 0)
+
/* Generates prototypes and inline functions */
#define RB_PROTOTYPE(name, type, field, cmp) \
RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
@@ -454,7 +485,8 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
continue; \
} \
if (RB_RIGHT(parent, field) == elm) { \
- RB_ROTATE_LEFT(head, parent, tmp, field);\
+ RB_PARENT_ROTATE_LEFT(gparent, parent, \
+ tmp, field); \
tmp = parent; \
parent = elm; \
elm = tmp; \
@@ -470,7 +502,8 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
continue; \
} \
if (RB_LEFT(parent, field) == elm) { \
- RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ RB_PARENT_ROTATE_RIGHT(gparent, parent, \
+ tmp, field); \
tmp = parent; \
parent = elm; \
elm = tmp; \
@@ -500,7 +533,8 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \
RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \
else if (RB_ISRED(RB_LEFT(tmp, field), field)) { \
struct type *oleft; \
- RB_ROTATE_RIGHT(head, tmp, oleft, field); \
+ RB_PARENT_ROTATE_RIGHT(parent, tmp, \
+ oleft, field); \
RB_COLOR(oleft, field) = RB_BLACK; \
tmp = oleft; \
} else { \
@@ -525,7 +559,8 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \
RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \
else if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \
struct type *oright; \
- RB_ROTATE_LEFT(head, tmp, oright, field); \
+ RB_PARENT_ROTATE_LEFT(parent, tmp, \
+ oright, field); \
RB_COLOR(oright, field) = RB_BLACK; \
tmp = oright; \
} else { \
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2021-10-07 16:02 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-10-07 16:02 [newlib-cygwin] sys/tree.h: Add parent rotations 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).