* [PATCH 0/4] Optimize red-black tree insert/extract
@ 2021-10-05 14:16 Sebastian Huber
2021-10-05 14:16 ` [PATCH 1/4] sys/tree.h: Simplify loop condition Sebastian Huber
` (3 more replies)
0 siblings, 4 replies; 6+ messages in thread
From: Sebastian Huber @ 2021-10-05 14:16 UTC (permalink / raw)
To: newlib; +Cc: devel
Code coverage analysis of the red-black tree insert/extract operations defined
in <sys/tree.h> showed that the macros contain dead code. This patch set
simplifies some expressions and add specialized rotations.
Sebastian Huber (4):
sys/tree.h: Simplify loop condition
sys/tree.h: Simplify chain of conditions
sys/tree.h: Add parent rotations
sys/tree.h: Red child with black sibling rotations
newlib/libc/include/sys/tree.h | 66 +++++++++++++++++++++++++++++-----
1 file changed, 58 insertions(+), 8 deletions(-)
--
2.26.2
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 1/4] sys/tree.h: Simplify loop condition
2021-10-05 14:16 [PATCH 0/4] Optimize red-black tree insert/extract Sebastian Huber
@ 2021-10-05 14:16 ` Sebastian Huber
2021-10-05 14:16 ` [PATCH 2/4] sys/tree.h: Simplify chain of conditions Sebastian Huber
` (2 subsequent siblings)
3 siblings, 0 replies; 6+ messages in thread
From: Sebastian Huber @ 2021-10-05 14:16 UTC (permalink / raw)
To: newlib; +Cc: devel
We have
#define RB_ISRED(elm, field) \
((elm) != NULL && RB_COLOR(elm, field) == RB_RED)
So, the RB_ISRED() contains an implicit check for NULL. In
RB_GENERATE_REMOVE_COLOR() the "elm" pointer cannot be NULL in the while
condition. Use RB_COLOR(elm) == RB_BLACK instead.
---
newlib/libc/include/sys/tree.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index 2af77a499..15831c7dd 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -540,7 +540,7 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \
elm = RB_ROOT(head); \
break; \
} \
- } while (!RB_ISRED(elm, field) && parent != NULL); \
+ } while (RB_COLOR(elm, field) == RB_BLACK && parent != NULL); \
RB_COLOR(elm, field) = RB_BLACK; \
}
--
2.26.2
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 2/4] sys/tree.h: Simplify chain of conditions
2021-10-05 14:16 [PATCH 0/4] Optimize red-black tree insert/extract Sebastian Huber
2021-10-05 14:16 ` [PATCH 1/4] sys/tree.h: Simplify loop condition Sebastian Huber
@ 2021-10-05 14:16 ` Sebastian Huber
2021-10-05 14:16 ` [PATCH 3/4] sys/tree.h: Add parent rotations Sebastian Huber
2021-10-05 14:16 ` [PATCH 4/4] sys/tree.h: Red child with black sibling rotations Sebastian Huber
3 siblings, 0 replies; 6+ messages in thread
From: Sebastian Huber @ 2021-10-05 14:16 UTC (permalink / raw)
To: newlib; +Cc: devel
In RB_GENERATE_REMOVE_COLOR() simplify a chain of conditions of the following
pattern
if (x) {
...
} else if (!x) {
...
}
to
if (x) {
...
} else {
...
}
---
newlib/libc/include/sys/tree.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index 15831c7dd..180809e9b 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -528,7 +528,7 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \
RB_ROTATE_LEFT(head, tmp, oright, field); \
RB_COLOR(oright, field) = RB_BLACK; \
tmp = oright; \
- } else if (!RB_ISRED(RB_LEFT(tmp, field), field)) { \
+ } else { \
RB_COLOR(tmp, field) = RB_RED; \
elm = parent; \
parent = RB_PARENT(elm, field); \
--
2.26.2
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 3/4] sys/tree.h: Add parent rotations
2021-10-05 14:16 [PATCH 0/4] Optimize red-black tree insert/extract Sebastian Huber
2021-10-05 14:16 ` [PATCH 1/4] sys/tree.h: Simplify loop condition Sebastian Huber
2021-10-05 14:16 ` [PATCH 2/4] sys/tree.h: Simplify chain of conditions Sebastian Huber
@ 2021-10-05 14:16 ` Sebastian Huber
[not found] ` <DM3P110MB0522B1D6E23F958DA0732F839AAF9@DM3P110MB0522.NAMP110.PROD.OUTLOOK.COM>
2021-10-05 14:16 ` [PATCH 4/4] sys/tree.h: Red child with black sibling rotations Sebastian Huber
3 siblings, 1 reply; 6+ messages in thread
From: Sebastian Huber @ 2021-10-05 14:16 UTC (permalink / raw)
To: newlib; +Cc: devel
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.
---
newlib/libc/include/sys/tree.h | 36 ++++++++++++++++++++++++++++++----
1 file changed, 32 insertions(+), 4 deletions(-)
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index 180809e9b..5fc052817 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -381,6 +381,30 @@ struct { \
RB_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)
+#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, elm, tmp, field) do { \
+ (tmp) = RB_LEFT(elm, field); \
+ if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
+ RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \
+ } \
+ RB_SET_PARENT(tmp, parent, field); \
+ RB_RIGHT(parent, field) = (tmp); \
+ RB_RIGHT(tmp, field) = (elm); \
+ RB_SET_PARENT(elm, tmp, field); \
+ RB_AUGMENT(elm); \
+} while (/*CONSTCOND*/ 0)
+
/* Generates prototypes and inline functions */
#define RB_PROTOTYPE(name, type, field, cmp) \
RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
@@ -454,7 +478,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 +495,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 +526,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 +552,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 { \
--
2.26.2
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 4/4] sys/tree.h: Red child with black sibling rotations
2021-10-05 14:16 [PATCH 0/4] Optimize red-black tree insert/extract Sebastian Huber
` (2 preceding siblings ...)
2021-10-05 14:16 ` [PATCH 3/4] sys/tree.h: Add parent rotations Sebastian Huber
@ 2021-10-05 14:16 ` Sebastian Huber
3 siblings, 0 replies; 6+ messages in thread
From: Sebastian Huber @ 2021-10-05 14:16 UTC (permalink / raw)
To: newlib; +Cc: devel
Add specialized rotations RB_RED_ROTATE_LEFT() and RB_RED_ROTATE_RIGHT() which
may be used if we rotate a red child which has a black sibling. Such a red
node must have at least two child nodes so that the following red-black tree
invariant is fulfilled:
Every path from a given node to any of its descendant NULL nodes goes through
the same number of black nodes.
PARENT
/ \
BLACK RED
/ \
BLACK BLACK
---
newlib/libc/include/sys/tree.h | 26 ++++++++++++++++++++++++--
1 file changed, 24 insertions(+), 2 deletions(-)
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index 5fc052817..ae5e620c9 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -405,6 +405,28 @@ struct { \
RB_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)
+#define RB_RED_ROTATE_LEFT(head, elm, tmp, field) do { \
+ (tmp) = RB_RIGHT(elm, field); \
+ RB_RIGHT(elm, field) = RB_LEFT(tmp, field); \
+ RB_SET_PARENT(RB_RIGHT(elm, field), elm, field); \
+ RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \
+ RB_SWAP_CHILD(head, elm, tmp, field); \
+ RB_LEFT(tmp, field) = (elm); \
+ RB_SET_PARENT(elm, tmp, field); \
+ RB_AUGMENT(elm); \
+} while (/*CONSTCOND*/ 0)
+
+#define RB_RED_ROTATE_RIGHT(head, elm, tmp, field) do { \
+ (tmp) = RB_LEFT(elm, field); \
+ RB_LEFT(elm, field) = RB_RIGHT(tmp, field); \
+ RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \
+ RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \
+ RB_SWAP_CHILD(head, elm, tmp, field); \
+ RB_RIGHT(tmp, field) = (elm); \
+ RB_SET_PARENT(elm, tmp, field); \
+ RB_AUGMENT(elm); \
+} while (/*CONSTCOND*/ 0)
+
/* Generates prototypes and inline functions */
#define RB_PROTOTYPE(name, type, field, cmp) \
RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
@@ -519,7 +541,7 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \
tmp = RB_RIGHT(parent, field); \
if (RB_COLOR(tmp, field) == RB_RED) { \
RB_SET_BLACKRED(tmp, parent, field); \
- RB_ROTATE_LEFT(head, parent, tmp, field);\
+ RB_RED_ROTATE_LEFT(head, parent, tmp, field); \
tmp = RB_RIGHT(parent, field); \
} \
if (RB_ISRED(RB_RIGHT(tmp, field), field)) \
@@ -545,7 +567,7 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \
tmp = RB_LEFT(parent, field); \
if (RB_COLOR(tmp, field) == RB_RED) { \
RB_SET_BLACKRED(tmp, parent, field); \
- RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ RB_RED_ROTATE_RIGHT(head, parent, tmp, field); \
tmp = RB_LEFT(parent, field); \
} \
if (RB_ISRED(RB_LEFT(tmp, field), field)) \
--
2.26.2
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: Fw: [PATCH 3/4] sys/tree.h: Add parent rotations
[not found] ` <DM3P110MB0522B1D6E23F958DA0732F839AAF9@DM3P110MB0522.NAMP110.PROD.OUTLOOK.COM>
@ 2021-10-05 14:56 ` C Howland
0 siblings, 0 replies; 6+ messages in thread
From: C Howland @ 2021-10-05 14:56 UTC (permalink / raw)
To: newlib
>
>
>
> ------------------------------
> *From:* Newlib <newlib-bounces+craig.howland=caci.com@sourceware.org> on
> behalf of Sebastian Huber <sebastian.huber@embedded-brains.de>
> *Sent:* Tuesday, October 5, 2021 10:16 AM
> *To:* newlib@sourceware.org <newlib@sourceware.org>
> *Cc:* devel@rtems.org <devel@rtems.org>
> *Subject:* [PATCH 3/4] 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.
>
It would seem appropriate for both this patch and #4 to include your
descriptions from the emails about the specialized nature of these new
macros in the source. (Otherwise, how can the conditions on their use be
known?)
Craig
---
> newlib/libc/include/sys/tree.h | 36 ++++++++++++++++++++++++++++++----
> 1 file changed, 32 insertions(+), 4 deletions(-)
>
> diff --git a/newlib/libc/include/sys/tree.h
> b/newlib/libc/include/sys/tree.h
> index 180809e9b..5fc052817 100644
> --- a/newlib/libc/include/sys/tree.h
> +++ b/newlib/libc/include/sys/tree.h
> @@ -381,6 +381,30 @@ struct
> { \
> RB_AUGMENT(elm); \
> } while (/*CONSTCOND*/ 0)
>
> +#define RB_PARENT_ROTATE_LEFT(parent, left, tmp, field) do { \
> ...
> 2.26.2
>
>
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2021-10-05 14:56 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-10-05 14:16 [PATCH 0/4] Optimize red-black tree insert/extract Sebastian Huber
2021-10-05 14:16 ` [PATCH 1/4] sys/tree.h: Simplify loop condition Sebastian Huber
2021-10-05 14:16 ` [PATCH 2/4] sys/tree.h: Simplify chain of conditions Sebastian Huber
2021-10-05 14:16 ` [PATCH 3/4] sys/tree.h: Add parent rotations Sebastian Huber
[not found] ` <DM3P110MB0522B1D6E23F958DA0732F839AAF9@DM3P110MB0522.NAMP110.PROD.OUTLOOK.COM>
2021-10-05 14:56 ` Fw: " C Howland
2021-10-05 14:16 ` [PATCH 4/4] sys/tree.h: Red child with black sibling 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).