* [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD
@ 2020-10-19 16:05 Sebastian Huber
2020-10-19 16:05 ` [PATCH 01/11] Add RB_REINSERT(3), a low overhead alternative to Sebastian Huber
` (9 more replies)
0 siblings, 10 replies; 11+ messages in thread
From: Sebastian Huber @ 2020-10-19 16:05 UTC (permalink / raw)
To: newlib
This patch set adds some changes after the last synchronization point with
FreeBSD to Newlib. In a simple benchmark, the node insert/extract performance
improved.
In an intermediate step of this patch set the node color member is removed.
Later it is restored. I propose to keep the patch series as is to have the
same change history as FreeBSD.
FreeBSD also changed the implementation to so that the node color is stored in
the parent pointer in follow up patches. In addition, they changed the
algorithm from red-black to weak AVL. These changes are NOT INCLUDED, since
they break the ABI/API. I did some rough benchmarking and was not immediately
convinced that the new implementation in FreeBSD is better.
dougm (10):
Correct the use of RB_AUGMENT in the RB_TREE
For the case when RB_REMOVE requires a nontrivial
RB_REMOVE invokes RB_REMOVE_COLOR either when
Remove from RB_REMOVE_COLOR some null checks
To reduce the size of an rb_node, drop the color
Restore an RB_COLOR macro, for the benefit of
Fixup r361997 by balancing parens. Duh.
Linuxkpi uses the rb-tree structures
In concluding RB_REMOVE_COLOR, in the case when
Define RB_SET_PARENT to do all assignments
trasz (1):
Add RB_REINSERT(3), a low overhead alternative to
newlib/libc/include/sys/tree.h | 273 ++++++++++++++++-----------------
1 file changed, 130 insertions(+), 143 deletions(-)
--
2.26.2
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 01/11] Add RB_REINSERT(3), a low overhead alternative to
2020-10-19 16:05 [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Sebastian Huber
@ 2020-10-19 16:05 ` Sebastian Huber
2020-10-19 16:05 ` [PATCH 02/11] Correct the use of RB_AUGMENT in the RB_TREE Sebastian Huber
` (8 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Sebastian Huber @ 2020-10-19 16:05 UTC (permalink / raw)
To: newlib
From: trasz <trasz@FreeBSD.org>
removing a node and reinserting it back with an updated key.
This is one of dependencies for the upcoming stats(3) code.
Reviewed by: cem
Obtained from: Netflix
MFC after: 2 weeks
Sponsored by: Klara Inc, Netflix
Differential Revision: https://reviews.freebsd.org/D21786
---
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 fd66ceba1..0eacf951d 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -393,7 +393,8 @@ struct { \
RB_PROTOTYPE_NFIND(name, type, attr); \
RB_PROTOTYPE_NEXT(name, type, attr); \
RB_PROTOTYPE_PREV(name, type, attr); \
- RB_PROTOTYPE_MINMAX(name, type, attr);
+ RB_PROTOTYPE_MINMAX(name, type, attr); \
+ RB_PROTOTYPE_REINSERT(name, type, attr);
#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
@@ -412,6 +413,8 @@ struct { \
attr struct type *name##_RB_PREV(struct type *)
#define RB_PROTOTYPE_MINMAX(name, type, attr) \
attr struct type *name##_RB_MINMAX(struct name *, int)
+#define RB_PROTOTYPE_REINSERT(name, type, attr) \
+ attr struct type *name##_RB_REINSERT(struct name *, struct type *)
/* Main rb operation.
* Moves node close to the key of elm to top
@@ -429,7 +432,9 @@ struct { \
RB_GENERATE_NFIND(name, type, field, cmp, attr) \
RB_GENERATE_NEXT(name, type, field, attr) \
RB_GENERATE_PREV(name, type, field, attr) \
- RB_GENERATE_MINMAX(name, type, field, attr)
+ RB_GENERATE_MINMAX(name, type, field, attr) \
+ RB_GENERATE_REINSERT(name, type, field, cmp, attr)
+
#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
attr void \
@@ -758,6 +763,22 @@ name##_RB_MINMAX(struct name *head, int val) \
return (parent); \
}
+#define RB_GENERATE_REINSERT(name, type, field, cmp, attr) \
+attr struct type * \
+name##_RB_REINSERT(struct name *head, struct type *elm) \
+{ \
+ struct type *cmpelm; \
+ if (((cmpelm = RB_PREV(name, head, elm)) != NULL && \
+ cmp(cmpelm, elm) >= 0) || \
+ ((cmpelm = RB_NEXT(name, head, elm)) != NULL && \
+ cmp(elm, cmpelm) >= 0)) { \
+ /* XXXLAS: Remove/insert is heavy handed. */ \
+ RB_REMOVE(name, head, elm); \
+ return (RB_INSERT(name, head, elm)); \
+ } \
+ return (NULL); \
+} \
+
#define RB_NEGINF -1
#define RB_INF 1
@@ -769,6 +790,7 @@ name##_RB_MINMAX(struct name *head, int val) \
#define RB_PREV(name, x, y) name##_RB_PREV(y)
#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
+#define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y)
#define RB_FOREACH(x, name, head) \
for ((x) = RB_MIN(name, head); \
--
2.26.2
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 02/11] Correct the use of RB_AUGMENT in the RB_TREE
2020-10-19 16:05 [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Sebastian Huber
2020-10-19 16:05 ` [PATCH 01/11] Add RB_REINSERT(3), a low overhead alternative to Sebastian Huber
@ 2020-10-19 16:05 ` Sebastian Huber
2020-10-19 16:05 ` [PATCH 03/11] For the case when RB_REMOVE requires a nontrivial Sebastian Huber
` (7 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Sebastian Huber @ 2020-10-19 16:05 UTC (permalink / raw)
To: newlib
From: dougm <dougm@FreeBSD.org>
macros so that is invoked at the root of every subtree that changes in an
insert or delete, and only once, and ordered from the bottom of the tree to the
top. For intel_gas.c, the only user of RB_AUGMENT I can find, change the
augmenting routine so that it does not climb from entry to tree root on every
call, and remove a 'tree correcting' function that can be supplanted by proper
tree augmentation.
Reviewed by: kib
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D23189
---
newlib/libc/include/sys/tree.h | 88 +++++++++++++++-------------------
1 file changed, 38 insertions(+), 50 deletions(-)
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index 0eacf951d..5c31ff2ea 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -335,8 +335,12 @@ struct { \
RB_COLOR(red, field) = RB_RED; \
} while (/*CONSTCOND*/ 0)
+/*
+ * Something to be invoked in a loop at the root of every modified subtree,
+ * from the bottom up to the root, to update augmented node data.
+ */
#ifndef RB_AUGMENT
-#define RB_AUGMENT(x) do {} while (0)
+#define RB_AUGMENT(x) break
#endif
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
@@ -344,7 +348,6 @@ struct { \
if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
} \
- RB_AUGMENT(elm); \
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
@@ -354,9 +357,7 @@ struct { \
(head)->rbh_root = (tmp); \
RB_LEFT(tmp, field) = (elm); \
RB_PARENT(elm, field) = (tmp); \
- RB_AUGMENT(tmp); \
- if ((RB_PARENT(tmp, field))) \
- RB_AUGMENT(RB_PARENT(tmp, field)); \
+ RB_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
@@ -364,7 +365,6 @@ struct { \
if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
} \
- RB_AUGMENT(elm); \
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
@@ -374,9 +374,7 @@ struct { \
(head)->rbh_root = (tmp); \
RB_RIGHT(tmp, field) = (elm); \
RB_PARENT(elm, field) = (tmp); \
- RB_AUGMENT(tmp); \
- if ((RB_PARENT(tmp, field))) \
- RB_AUGMENT(RB_PARENT(tmp, field)); \
+ RB_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)
/* Generates prototypes and inline functions */
@@ -571,62 +569,49 @@ name##_RB_REMOVE(struct name *head, struct type *elm) \
else if (RB_RIGHT(elm, field) == NULL) \
child = RB_LEFT(elm, field); \
else { \
- struct type *left; \
- elm = RB_RIGHT(elm, field); \
- while ((left = RB_LEFT(elm, field)) != NULL) \
- elm = left; \
- child = RB_RIGHT(elm, field); \
- parent = RB_PARENT(elm, field); \
- color = RB_COLOR(elm, field); \
- if (child) \
- RB_PARENT(child, field) = parent; \
- if (parent) { \
- if (RB_LEFT(parent, field) == elm) \
- RB_LEFT(parent, field) = child; \
- else \
- RB_RIGHT(parent, field) = child; \
- RB_AUGMENT(parent); \
- } else \
- RB_ROOT(head) = child; \
- if (RB_PARENT(elm, field) == old) \
- parent = elm; \
- (elm)->field = (old)->field; \
- if (RB_PARENT(old, field)) { \
- if (RB_LEFT(RB_PARENT(old, field), field) == old)\
- RB_LEFT(RB_PARENT(old, field), field) = elm;\
+ 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; \
+ } else { \
+ do \
+ elm = child; \
+ while ((child = RB_LEFT(elm, field)) != NULL); \
+ child = RB_RIGHT(elm, field); \
+ 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(RB_PARENT(old, field), field) = elm;\
- RB_AUGMENT(RB_PARENT(old, field)); \
+ RB_RIGHT(parent, field) = elm; \
} else \
RB_ROOT(head) = elm; \
- RB_PARENT(RB_LEFT(old, field), field) = elm; \
- if (RB_RIGHT(old, field)) \
- RB_PARENT(RB_RIGHT(old, field), field) = elm; \
- if (parent) { \
- left = parent; \
- do { \
- RB_AUGMENT(left); \
- } while ((left = RB_PARENT(left, field)) != NULL); \
- } \
- goto color; \
} \
parent = RB_PARENT(elm, field); \
color = RB_COLOR(elm, field); \
- if (child) \
+ if (child != NULL) \
RB_PARENT(child, field) = parent; \
- if (parent) { \
+ if (parent != NULL) { \
if (RB_LEFT(parent, field) == elm) \
RB_LEFT(parent, field) = child; \
else \
RB_RIGHT(parent, field) = child; \
- RB_AUGMENT(parent); \
} else \
RB_ROOT(head) = child; \
-color: \
+ if (elm != old) \
+ (elm)->field = (old)->field; \
if (color == RB_BLACK) \
name##_RB_REMOVE_COLOR(head, parent, child); \
+ while (parent != NULL) { \
+ RB_AUGMENT(parent); \
+ parent = RB_PARENT(parent, field); \
+ } \
return (old); \
-} \
+}
#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \
/* Inserts a node into the RB tree */ \
@@ -653,10 +638,13 @@ name##_RB_INSERT(struct name *head, struct type *elm) \
RB_LEFT(parent, field) = elm; \
else \
RB_RIGHT(parent, field) = elm; \
- RB_AUGMENT(parent); \
} else \
RB_ROOT(head) = elm; \
name##_RB_INSERT_COLOR(head, elm); \
+ while (elm != NULL) { \
+ RB_AUGMENT(elm); \
+ elm = RB_PARENT(elm, field); \
+ } \
return (NULL); \
}
--
2.26.2
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 03/11] For the case when RB_REMOVE requires a nontrivial
2020-10-19 16:05 [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Sebastian Huber
2020-10-19 16:05 ` [PATCH 01/11] Add RB_REINSERT(3), a low overhead alternative to Sebastian Huber
2020-10-19 16:05 ` [PATCH 02/11] Correct the use of RB_AUGMENT in the RB_TREE Sebastian Huber
@ 2020-10-19 16:05 ` Sebastian Huber
2020-10-19 16:05 ` [PATCH 04/11] RB_REMOVE invokes RB_REMOVE_COLOR either when Sebastian Huber
` (6 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Sebastian Huber @ 2020-10-19 16:05 UTC (permalink / raw)
To: newlib
From: dougm <dougm@FreeBSD.org>
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
---
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) { \
--
2.26.2
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 04/11] RB_REMOVE invokes RB_REMOVE_COLOR either when
2020-10-19 16:05 [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Sebastian Huber
` (2 preceding siblings ...)
2020-10-19 16:05 ` [PATCH 03/11] For the case when RB_REMOVE requires a nontrivial Sebastian Huber
@ 2020-10-19 16:05 ` Sebastian Huber
2020-10-19 16:05 ` [PATCH 05/11] Remove from RB_REMOVE_COLOR some null checks Sebastian Huber
` (5 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Sebastian Huber @ 2020-10-19 16:05 UTC (permalink / raw)
To: newlib
From: dougm <dougm@FreeBSD.org>
child is red or child is null. In the first case, RB_REMOVE_COLOR just changes
the child to black and returns. With this change, RB_REMOVE handles that case,
and drops the child argument to RB_REMOVE_COLOR, since that value is always
null.
RB_REMOVE_COLOR is changed to remove a couple of unneeded tests, and
to eliminate some deep indentation.
RB_ISRED is defined to combine a null check with a test for redness,
to replace that combination in several places.
Reviewed by: markj
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D25032
---
newlib/libc/include/sys/tree.h | 137 ++++++++++++++++-----------------
1 file changed, 65 insertions(+), 72 deletions(-)
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index b1e5e23a7..d5adfdd4e 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -321,6 +321,7 @@ struct { \
#define RB_RIGHT(elm, field) (elm)->field.rbe_right
#define RB_PARENT(elm, field) (elm)->field.rbe_parent
#define RB_COLOR(elm, field) (elm)->field.rbe_color
+#define RB_ISRED(elm, field) ((elm) != NULL && RB_COLOR(elm, field) == RB_RED)
#define RB_ROOT(head) (head)->rbh_root
#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
@@ -396,7 +397,7 @@ struct { \
#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
- attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *)
+ attr void name##_RB_REMOVE_COLOR(struct name *, struct type *)
#define RB_PROTOTYPE_REMOVE(name, type, attr) \
attr struct type *name##_RB_REMOVE(struct name *, struct type *)
#define RB_PROTOTYPE_INSERT(name, type, attr) \
@@ -439,12 +440,11 @@ attr void \
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
{ \
struct type *parent, *gparent, *tmp; \
- while ((parent = RB_PARENT(elm, field)) != NULL && \
- RB_COLOR(parent, field) == RB_RED) { \
+ while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) { \
gparent = RB_PARENT(parent, field); \
if (parent == RB_LEFT(gparent, field)) { \
tmp = RB_RIGHT(gparent, field); \
- if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ if (RB_ISRED(tmp, field)) { \
RB_COLOR(tmp, field) = RB_BLACK; \
RB_SET_BLACKRED(parent, gparent, field);\
elm = gparent; \
@@ -460,7 +460,7 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
RB_ROTATE_RIGHT(head, gparent, tmp, field); \
} else { \
tmp = RB_LEFT(gparent, field); \
- if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ if (RB_ISRED(tmp, field)) { \
RB_COLOR(tmp, field) = RB_BLACK; \
RB_SET_BLACKRED(parent, gparent, field);\
elm = gparent; \
@@ -481,11 +481,11 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
attr void \
-name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
+name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \
{ \
- struct type *tmp; \
- while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
- elm != RB_ROOT(head)) { \
+ struct type *elm, *tmp; \
+ elm = NULL; \
+ do { \
if (RB_LEFT(parent, field) == elm) { \
tmp = RB_RIGHT(parent, field); \
if (RB_COLOR(tmp, field) == RB_RED) { \
@@ -493,32 +493,29 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm)
RB_ROTATE_LEFT(head, parent, tmp, field);\
tmp = RB_RIGHT(parent, field); \
} \
- if ((RB_LEFT(tmp, field) == NULL || \
- RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
- (RB_RIGHT(tmp, field) == NULL || \
- RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+ if (!RB_ISRED(RB_LEFT(tmp, field), field) && \
+ !RB_ISRED(RB_RIGHT(tmp, field), field)) { \
RB_COLOR(tmp, field) = RB_RED; \
elm = parent; \
parent = RB_PARENT(elm, field); \
- } else { \
- if (RB_RIGHT(tmp, field) == NULL || \
- RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
- struct type *oleft; \
- if ((oleft = RB_LEFT(tmp, field)) \
- != NULL) \
- RB_COLOR(oleft, field) = RB_BLACK;\
- RB_COLOR(tmp, field) = RB_RED; \
- RB_ROTATE_RIGHT(head, tmp, oleft, field);\
- tmp = RB_RIGHT(parent, field); \
- } \
- RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
- RB_COLOR(parent, field) = RB_BLACK; \
- if (RB_RIGHT(tmp, field)) \
- RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
- RB_ROTATE_LEFT(head, parent, tmp, field);\
- elm = RB_ROOT(head); \
- break; \
+ continue; \
} \
+ if (!RB_ISRED(RB_RIGHT(tmp, field), field)) { \
+ struct type *oleft; \
+ if ((oleft = RB_LEFT(tmp, field)) \
+ != NULL) \
+ RB_COLOR(oleft, field) = RB_BLACK; \
+ RB_COLOR(tmp, field) = RB_RED; \
+ RB_ROTATE_RIGHT(head, tmp, oleft, field); \
+ tmp = RB_RIGHT(parent, field); \
+ } \
+ RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
+ RB_COLOR(parent, field) = RB_BLACK; \
+ if (RB_RIGHT(tmp, field)) \
+ RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \
+ RB_ROTATE_LEFT(head, parent, tmp, field); \
+ elm = RB_ROOT(head); \
+ break; \
} else { \
tmp = RB_LEFT(parent, field); \
if (RB_COLOR(tmp, field) == RB_RED) { \
@@ -526,59 +523,54 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm)
RB_ROTATE_RIGHT(head, parent, tmp, field);\
tmp = RB_LEFT(parent, field); \
} \
- if ((RB_LEFT(tmp, field) == NULL || \
- RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
- (RB_RIGHT(tmp, field) == NULL || \
- RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+ if (!RB_ISRED(RB_LEFT(tmp, field), field) && \
+ !RB_ISRED(RB_RIGHT(tmp, field), field)) { \
RB_COLOR(tmp, field) = RB_RED; \
elm = parent; \
parent = RB_PARENT(elm, field); \
- } else { \
- if (RB_LEFT(tmp, field) == NULL || \
- RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
- struct type *oright; \
- if ((oright = RB_RIGHT(tmp, field)) \
- != NULL) \
- 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(tmp, field) = RB_COLOR(parent, field);\
- RB_COLOR(parent, field) = RB_BLACK; \
- if (RB_LEFT(tmp, field)) \
- RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
- RB_ROTATE_RIGHT(head, parent, tmp, field);\
- elm = RB_ROOT(head); \
- break; \
+ continue; \
+ } \
+ if (!RB_ISRED(RB_LEFT(tmp, field), field)) { \
+ struct type *oright; \
+ if ((oright = RB_RIGHT(tmp, field)) \
+ != NULL) \
+ 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(tmp, field) = RB_COLOR(parent, field); \
+ RB_COLOR(parent, field) = RB_BLACK; \
+ if (RB_LEFT(tmp, field)) \
+ RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \
+ RB_ROTATE_RIGHT(head, parent, tmp, field); \
+ elm = RB_ROOT(head); \
+ break; \
} \
- } \
- if (elm) \
- RB_COLOR(elm, field) = RB_BLACK; \
+ } while (!RB_ISRED(elm, field) && parent != NULL); \
+ RB_COLOR(elm, field) = RB_BLACK; \
}
#define RB_GENERATE_REMOVE(name, type, field, attr) \
attr struct type * \
name##_RB_REMOVE(struct name *head, struct type *elm) \
{ \
- struct type *child, *parent, *parent_old, *old = elm; \
+ struct type *child, *old, *parent, *parent_old, *right; \
int color; \
+ \
+ old = elm; \
parent_old = parent = RB_PARENT(elm, field); \
+ right = RB_RIGHT(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) { \
+ if (RB_LEFT(elm, field) == NULL) \
+ elm = child = right; \
+ else if (right == 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); \
+ else { \
+ if ((child = RB_LEFT(right, field)) == NULL) { \
+ child = RB_RIGHT(right, field); \
RB_RIGHT(old, field) = child; \
- parent = elm; \
+ parent = elm = right; \
} else { \
do \
elm = child; \
@@ -586,8 +578,6 @@ name##_RB_REMOVE(struct name *head, struct type *elm) \
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; \
@@ -600,8 +590,11 @@ name##_RB_REMOVE(struct name *head, struct type *elm) \
RB_LEFT(parent_old, field) = elm; \
else \
RB_RIGHT(parent_old, field) = elm; \
- if (color == RB_BLACK) \
- name##_RB_REMOVE_COLOR(head, parent, child); \
+ if (child != NULL) { \
+ RB_PARENT(child, field) = parent; \
+ RB_COLOR(child, field) = RB_BLACK; \
+ } else if (color != RB_RED && parent != NULL) \
+ name##_RB_REMOVE_COLOR(head, parent); \
while (parent != NULL) { \
RB_AUGMENT(parent); \
parent = RB_PARENT(parent, field); \
--
2.26.2
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 05/11] Remove from RB_REMOVE_COLOR some null checks
2020-10-19 16:05 [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Sebastian Huber
` (3 preceding siblings ...)
2020-10-19 16:05 ` [PATCH 04/11] RB_REMOVE invokes RB_REMOVE_COLOR either when Sebastian Huber
@ 2020-10-19 16:05 ` Sebastian Huber
2020-10-19 16:05 ` [PATCH 06/11] To reduce the size of an rb_node, drop the color Sebastian Huber
` (4 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Sebastian Huber @ 2020-10-19 16:05 UTC (permalink / raw)
To: newlib
From: dougm <dougm@FreeBSD.org>
where the pointer checked is provably never null. Restructure the surrounding
code just enough to make the non-nullness obvious.
Reviewed by: markj
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D25089
---
newlib/libc/include/sys/tree.h | 46 +++++++++++++++-------------------
1 file changed, 20 insertions(+), 26 deletions(-)
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index d5adfdd4e..372c001b9 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -493,26 +493,23 @@ 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) && \
- !RB_ISRED(RB_RIGHT(tmp, field), field)) { \
- RB_COLOR(tmp, field) = RB_RED; \
- elm = parent; \
- parent = RB_PARENT(elm, field); \
- continue; \
- } \
- if (!RB_ISRED(RB_RIGHT(tmp, field), field)) { \
+ if (RB_ISRED(RB_LEFT(tmp, field), field)) { \
struct type *oleft; \
- if ((oleft = RB_LEFT(tmp, field)) \
- != NULL) \
- RB_COLOR(oleft, field) = RB_BLACK; \
+ 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(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; \
- if (RB_RIGHT(tmp, field)) \
- RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \
RB_ROTATE_LEFT(head, parent, tmp, field); \
elm = RB_ROOT(head); \
break; \
@@ -523,26 +520,23 @@ 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_LEFT(tmp, field), field) && \
- !RB_ISRED(RB_RIGHT(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)) { \
+ if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \
struct type *oright; \
- if ((oright = RB_RIGHT(tmp, field)) \
- != NULL) \
- RB_COLOR(oright, field) = RB_BLACK; \
+ 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); \
+ } 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; \
- if (RB_LEFT(tmp, field)) \
- RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \
RB_ROTATE_RIGHT(head, parent, tmp, field); \
elm = RB_ROOT(head); \
break; \
--
2.26.2
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 06/11] To reduce the size of an rb_node, drop the color
2020-10-19 16:05 [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Sebastian Huber
` (4 preceding siblings ...)
2020-10-19 16:05 ` [PATCH 05/11] Remove from RB_REMOVE_COLOR some null checks Sebastian Huber
@ 2020-10-19 16:05 ` Sebastian Huber
2020-10-19 16:05 ` [PATCH 07/11] Restore an RB_COLOR macro, for the benefit of Sebastian Huber
` (3 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Sebastian Huber @ 2020-10-19 16:05 UTC (permalink / raw)
To: newlib
From: dougm <dougm@FreeBSD.org>
field. Set the least significant bit in the pointer to the node from its parent
to indicate that the node is red. Have the tree rotation macros leave the
old-parent/new-child node red and the new-parent/old-child node black.
This change makes RB_LEFT and RB_RIGHT no longer assignable, and
RB_COLOR no longer defined. Any code that modifies the tree or
examines a node color would have to be modified after this change.
Reviewed by: markj
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D25105
---
newlib/libc/include/sys/tree.h | 281 +++++++++++++++++----------------
1 file changed, 143 insertions(+), 138 deletions(-)
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index 372c001b9..29b731822 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -307,34 +307,31 @@ struct name { \
(root)->rbh_root = NULL; \
} while (/*CONSTCOND*/ 0)
-#define RB_BLACK 0
-#define RB_RED 1
#define RB_ENTRY(type) \
struct { \
struct type *rbe_left; /* left element */ \
struct type *rbe_right; /* right element */ \
struct type *rbe_parent; /* parent element */ \
- int rbe_color; /* node color */ \
}
-#define RB_LEFT(elm, field) (elm)->field.rbe_left
-#define RB_RIGHT(elm, field) (elm)->field.rbe_right
+#define RB_LF(elm, field) (elm)->field.rbe_left
+#define RB_RT(elm, field) (elm)->field.rbe_right
+#define RB_FLIP(elm) (*(__uintptr_t *)&(elm) ^= 1)
+#define RB_FLIP_LF(elm, field) RB_FLIP(RB_LF(elm, field))
+#define RB_FLIP_RT(elm, field) RB_FLIP(RB_RT(elm, field))
+#define RB_ISRED(elm) ((*(__uintptr_t *)&(elm) & 1) != 0)
+#define RB_RED_LF(elm, field) RB_ISRED(RB_LF(elm, field))
+#define RB_RED_RT(elm, field) RB_ISRED(RB_RT(elm, field))
+#define RB_PTR(elm, field) ((__typeof(elm->field.rbe_parent)) \
+ ((__uintptr_t)(elm) & ~(__uintptr_t)1))
+#define RB_LEFT(elm, field) RB_PTR(RB_LF(elm, field), field)
+#define RB_RIGHT(elm, field) RB_PTR(RB_RT(elm, field), field)
#define RB_PARENT(elm, field) (elm)->field.rbe_parent
-#define RB_COLOR(elm, field) (elm)->field.rbe_color
-#define RB_ISRED(elm, field) ((elm) != NULL && RB_COLOR(elm, field) == RB_RED)
#define RB_ROOT(head) (head)->rbh_root
#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
-
-#define RB_SET(elm, parent, field) do { \
- RB_PARENT(elm, field) = parent; \
- RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
- RB_COLOR(elm, field) = RB_RED; \
-} while (/*CONSTCOND*/ 0)
-
-#define RB_SET_BLACKRED(black, red, field) do { \
- RB_COLOR(black, field) = RB_BLACK; \
- RB_COLOR(red, field) = RB_RED; \
-} while (/*CONSTCOND*/ 0)
+#define RB_BOOL int
+#define RB_TRUE 1
+#define RB_FALSE 0
/*
* Something to be invoked in a loop at the root of every modified subtree,
@@ -344,37 +341,42 @@ struct { \
#define RB_AUGMENT(x) break
#endif
+/*
+ * Fix pointers to a parent, and from a parent, as part of rotation.
+ */
+#define RB_ROTATE_PARENT(head, elm, tmp, field) do { \
+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) == NULL) \
+ RB_ROOT(head) = (tmp); \
+ else if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LF(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RT(RB_PARENT(elm, field), field) = (tmp); \
+ RB_PARENT(elm, field) = (tmp); \
+} while (/*CONSTCOND*/ 0)
+
+/*
+ * Rotation makes the descending node red, and the ascending
+ * node not-red.
+ */
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
(tmp) = RB_RIGHT(elm, field); \
- if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
+ if ((RB_RT(elm, field) = RB_LF(tmp, field)) != NULL) { \
RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
} \
- if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
- if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
- RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
- else \
- RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
- } else \
- (head)->rbh_root = (tmp); \
- RB_LEFT(tmp, field) = (elm); \
- RB_PARENT(elm, field) = (tmp); \
+ RB_ROTATE_PARENT(head, elm, tmp, field); \
+ RB_LF(tmp, field) = (elm); \
+ RB_FLIP_LF(tmp, field); \
RB_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
(tmp) = RB_LEFT(elm, field); \
- if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
+ if ((RB_LF(elm, field) = RB_RT(tmp, field)) != NULL) { \
RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
} \
- if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
- if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
- RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
- else \
- RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
- } else \
- (head)->rbh_root = (tmp); \
- RB_RIGHT(tmp, field) = (elm); \
- RB_PARENT(elm, field) = (tmp); \
+ RB_ROTATE_PARENT(head, elm, tmp, field); \
+ RB_RT(tmp, field) = (elm); \
+ RB_FLIP_RT(tmp, field); \
RB_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)
@@ -439,110 +441,105 @@ struct { \
attr void \
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
{ \
- struct type *parent, *gparent, *tmp; \
- while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) { \
- gparent = RB_PARENT(parent, field); \
- if (parent == RB_LEFT(gparent, field)) { \
- tmp = RB_RIGHT(gparent, field); \
- if (RB_ISRED(tmp, field)) { \
- RB_COLOR(tmp, field) = RB_BLACK; \
- RB_SET_BLACKRED(parent, gparent, field);\
- elm = gparent; \
- continue; \
- } \
+ struct type *gparent, *parent; \
+ while ((parent = RB_PARENT(elm, field)) != NULL) { \
+ if (RB_LEFT(parent, field) == elm) \
+ RB_FLIP_LF(parent, field); \
+ else \
+ RB_FLIP_RT(parent, field); \
+ if ((gparent = RB_PARENT(parent, field)) == NULL) \
+ break; \
+ if (RB_RED_LF(gparent, field) && \
+ RB_RED_RT(gparent, field)) { \
+ RB_FLIP_LF(gparent, field); \
+ RB_FLIP_RT(gparent, field); \
+ elm = gparent; \
+ continue; \
+ } \
+ if (RB_RED_LF(gparent, field) && \
+ parent == RB_LEFT(gparent, field)) { \
if (RB_RIGHT(parent, field) == elm) { \
- RB_ROTATE_LEFT(head, parent, tmp, field);\
- tmp = parent; \
+ RB_ROTATE_LEFT(head, parent, elm, field);\
parent = elm; \
- elm = tmp; \
- } \
- RB_SET_BLACKRED(parent, gparent, field); \
- RB_ROTATE_RIGHT(head, gparent, tmp, field); \
- } else { \
- tmp = RB_LEFT(gparent, field); \
- if (RB_ISRED(tmp, field)) { \
- RB_COLOR(tmp, field) = RB_BLACK; \
- RB_SET_BLACKRED(parent, gparent, field);\
- elm = gparent; \
- continue; \
} \
+ RB_ROTATE_RIGHT(head, gparent, parent, field); \
+ } else if (RB_RED_RT(gparent, field) && \
+ parent == RB_RIGHT(gparent, field)) { \
if (RB_LEFT(parent, field) == elm) { \
- RB_ROTATE_RIGHT(head, parent, tmp, field);\
- tmp = parent; \
+ RB_ROTATE_RIGHT(head, parent, elm, field);\
parent = elm; \
- elm = tmp; \
} \
- RB_SET_BLACKRED(parent, gparent, field); \
- RB_ROTATE_LEFT(head, gparent, tmp, field); \
+ RB_ROTATE_LEFT(head, gparent, parent, field); \
} \
+ break; \
} \
- RB_COLOR(head->rbh_root, field) = RB_BLACK; \
}
#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
attr void \
-name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \
+name##_RB_REMOVE_COLOR(struct name *head, struct type *elm) \
{ \
- struct type *elm, *tmp; \
- elm = NULL; \
+ struct type *par, *sib, *tmp; \
+ RB_BOOL go_left, left_child, red_par; \
+ left_child = (RB_LEFT(elm, field) == NULL); \
do { \
- if (RB_LEFT(parent, field) == elm) { \
- 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);\
- tmp = RB_RIGHT(parent, field); \
+ go_left = left_child; \
+ if (go_left ? \
+ !RB_RED_RT(elm, field) : \
+ !RB_RED_LF(elm, field)) { \
+ par = RB_PARENT(elm, field); \
+ left_child = par != NULL && \
+ RB_LEFT(par, field) == elm; \
+ red_par = left_child ? RB_RED_LF(par, field) : \
+ par == NULL ? RB_TRUE : \
+ RB_RED_RT(par, field); \
+ } \
+ if (go_left) { \
+ if (RB_RED_RT(elm, field)) { \
+ red_par = RB_TRUE; \
+ RB_ROTATE_LEFT(head, elm, par, field); \
} \
- 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(tmp, field) = RB_RED; \
- elm = parent; \
- parent = RB_PARENT(elm, field); \
+ sib = RB_RIGHT(elm, field); \
+ if (RB_RED_LF(sib, field)) { \
+ RB_ROTATE_RIGHT(head, sib, tmp, field); \
+ sib = tmp; \
+ } else if (!RB_RED_RT(sib, field)) { \
+ RB_FLIP_RT(elm, field); \
+ elm = par; \
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); \
- elm = RB_ROOT(head); \
+ if (RB_RED_RT(sib, field)) \
+ RB_FLIP_RT(sib, field); \
+ RB_ROTATE_LEFT(head, elm, sib, field); \
+ RB_FLIP_LF(sib, field); \
break; \
} else { \
- 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);\
- tmp = RB_LEFT(parent, field); \
+ if (RB_RED_LF(elm, field)) { \
+ red_par = RB_TRUE; \
+ RB_ROTATE_RIGHT(head, elm, par, field); \
} \
- 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); \
- } else if (!RB_ISRED(RB_LEFT(tmp, field), field)) { \
- RB_COLOR(tmp, field) = RB_RED; \
- elm = parent; \
- parent = RB_PARENT(elm, field); \
+ sib = RB_LEFT(elm, field); \
+ if (RB_RED_RT(sib, field)) { \
+ RB_ROTATE_LEFT(head, sib, tmp, field); \
+ sib = tmp; \
+ } else if (!RB_RED_LF(sib, field)) { \
+ RB_FLIP_LF(elm, field); \
+ elm = par; \
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); \
- elm = RB_ROOT(head); \
+ if (RB_RED_LF(sib, field)) \
+ RB_FLIP_LF(sib, field); \
+ RB_ROTATE_RIGHT(head, elm, sib, field); \
+ RB_FLIP_RT(sib, field); \
break; \
} \
- } while (!RB_ISRED(elm, field) && parent != NULL); \
- RB_COLOR(elm, field) = RB_BLACK; \
+ } while (!red_par); \
+ if (par != NULL && red_par) { \
+ if (left_child) \
+ RB_FLIP_LF(par, field); \
+ else \
+ RB_FLIP_RT(par, field); \
+ } \
}
#define RB_GENERATE_REMOVE(name, type, field, attr) \
@@ -550,12 +547,11 @@ attr struct type * \
name##_RB_REMOVE(struct name *head, struct type *elm) \
{ \
struct type *child, *old, *parent, *parent_old, *right; \
- int color; \
+ RB_BOOL old_red, red; \
\
old = elm; \
parent_old = parent = RB_PARENT(elm, field); \
right = RB_RIGHT(elm, field); \
- color = RB_COLOR(elm, field); \
if (RB_LEFT(elm, field) == NULL) \
elm = child = right; \
else if (right == NULL) \
@@ -563,7 +559,8 @@ name##_RB_REMOVE(struct name *head, struct type *elm) \
else { \
if ((child = RB_LEFT(right, field)) == NULL) { \
child = RB_RIGHT(right, field); \
- RB_RIGHT(old, field) = child; \
+ red = RB_RED_RT(old, field); \
+ RB_RT(old, field) = child; \
parent = elm = right; \
} else { \
do \
@@ -571,23 +568,31 @@ name##_RB_REMOVE(struct name *head, struct type *elm) \
while ((child = RB_LEFT(elm, field)) != NULL); \
child = RB_RIGHT(elm, field); \
parent = RB_PARENT(elm, field); \
- RB_LEFT(parent, field) = child; \
+ red = RB_RED_LF(parent, field); \
+ RB_LF(parent, field) = child; \
RB_PARENT(RB_RIGHT(old, field), field) = elm; \
} \
RB_PARENT(RB_LEFT(old, field), field) = elm; \
- color = RB_COLOR(elm, field); \
elm->field = old->field; \
} \
- if (parent_old == NULL) \
+ 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 (child != NULL) { \
+ old_red = RB_FALSE; \
+ } else if (RB_LEFT(parent_old, field) == old) { \
+ old_red = RB_RED_LF(parent_old, field); \
+ RB_LF(parent_old, field) = elm; \
+ if (old_red && parent != parent_old) \
+ RB_FLIP_LF(parent_old, field); \
+ } else { \
+ old_red = RB_RED_RT(parent_old, field); \
+ RB_RT(parent_old, field) = elm; \
+ if (old_red && parent != parent_old) \
+ RB_FLIP_RT(parent_old, field); \
+ } \
+ if (child != NULL) \
RB_PARENT(child, field) = parent; \
- RB_COLOR(child, field) = RB_BLACK; \
- } else if (color != RB_RED && parent != NULL) \
+ else if (parent != NULL && \
+ (parent != parent_old ? !red : !old_red)) \
name##_RB_REMOVE_COLOR(head, parent); \
while (parent != NULL) { \
RB_AUGMENT(parent); \
@@ -615,14 +620,14 @@ name##_RB_INSERT(struct name *head, struct type *elm) \
else \
return (tmp); \
} \
- RB_SET(elm, parent, field); \
- if (parent != NULL) { \
- if (comp < 0) \
- RB_LEFT(parent, field) = elm; \
- else \
- RB_RIGHT(parent, field) = elm; \
- } else \
+ RB_PARENT(elm, field) = parent; \
+ RB_LF(elm, field) = RB_RT(elm, field) = NULL; \
+ if (parent == NULL) \
RB_ROOT(head) = elm; \
+ else if (comp < 0) \
+ RB_LF(parent, field) = elm; \
+ else \
+ RB_RT(parent, field) = elm; \
name##_RB_INSERT_COLOR(head, elm); \
while (elm != NULL) { \
RB_AUGMENT(elm); \
--
2.26.2
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 07/11] Restore an RB_COLOR macro, for the benefit of
2020-10-19 16:05 [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Sebastian Huber
` (5 preceding siblings ...)
2020-10-19 16:05 ` [PATCH 06/11] To reduce the size of an rb_node, drop the color Sebastian Huber
@ 2020-10-19 16:05 ` Sebastian Huber
2020-10-19 16:05 ` [PATCH 08/11] Fixup r361997 by balancing parens. Duh Sebastian Huber
` (2 subsequent siblings)
9 siblings, 0 replies; 11+ messages in thread
From: Sebastian Huber @ 2020-10-19 16:05 UTC (permalink / raw)
To: newlib
From: dougm <dougm@FreeBSD.org>
a bit of DIAGNOSTIC code that depends on it.
Reported by: rpokala, mjguzik
Reviewed by: markj
Differential Revision: https://reviews.freebsd.org/D25204
---
newlib/libc/include/sys/tree.h | 6 ++++++
1 file changed, 6 insertions(+)
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index 29b731822..7c2053981 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -333,6 +333,12 @@ struct { \
#define RB_TRUE 1
#define RB_FALSE 0
+/* For debugging support */
+#define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? RB_FALSE : \
+ RB_LEFT(RB_PARENT(elm, field), field) == elm ? \
+ RB_RED_LF(RB_PARENT(elm, field), field) : \
+ RB_RED_RT(RB_PARENT(elm, field), field)
+
/*
* Something to be invoked in a loop at the root of every modified subtree,
* from the bottom up to the root, to update augmented node data.
--
2.26.2
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 08/11] Fixup r361997 by balancing parens. Duh.
2020-10-19 16:05 [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Sebastian Huber
` (6 preceding siblings ...)
2020-10-19 16:05 ` [PATCH 07/11] Restore an RB_COLOR macro, for the benefit of Sebastian Huber
@ 2020-10-19 16:05 ` Sebastian Huber
2020-10-19 16:05 ` [PATCH 09/11] Linuxkpi uses the rb-tree structures Sebastian Huber
2020-10-26 9:52 ` [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Corinna Vinschen
9 siblings, 0 replies; 11+ messages in thread
From: Sebastian Huber @ 2020-10-19 16:05 UTC (permalink / raw)
To: newlib
From: dougm <dougm@FreeBSD.org>
---
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 7c2053981..33efb9e11 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -337,7 +337,7 @@ struct { \
#define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? RB_FALSE : \
RB_LEFT(RB_PARENT(elm, field), field) == elm ? \
RB_RED_LF(RB_PARENT(elm, field), field) : \
- RB_RED_RT(RB_PARENT(elm, field), field)
+ RB_RED_RT(RB_PARENT(elm, field), field))
/*
* Something to be invoked in a loop at the root of every modified subtree,
--
2.26.2
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH 09/11] Linuxkpi uses the rb-tree structures
2020-10-19 16:05 [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Sebastian Huber
` (7 preceding siblings ...)
2020-10-19 16:05 ` [PATCH 08/11] Fixup r361997 by balancing parens. Duh Sebastian Huber
@ 2020-10-19 16:05 ` Sebastian Huber
2020-10-26 9:52 ` [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Corinna Vinschen
9 siblings, 0 replies; 11+ messages in thread
From: Sebastian Huber @ 2020-10-19 16:05 UTC (permalink / raw)
To: newlib
From: dougm <dougm@FreeBSD.org>
without using their interfaces, making them break when the representation
changes. Revert changes that eliminated the color field from rb-trees, leaving
everything as it was before.
Reviewed by: markj
Differential Revision: https://reviews.freebsd.org/D25250
---
newlib/libc/include/sys/tree.h | 285 ++++++++++++++++-----------------
1 file changed, 137 insertions(+), 148 deletions(-)
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h
index 33efb9e11..372c001b9 100644
--- a/newlib/libc/include/sys/tree.h
+++ b/newlib/libc/include/sys/tree.h
@@ -307,37 +307,34 @@ struct name { \
(root)->rbh_root = NULL; \
} while (/*CONSTCOND*/ 0)
+#define RB_BLACK 0
+#define RB_RED 1
#define RB_ENTRY(type) \
struct { \
struct type *rbe_left; /* left element */ \
struct type *rbe_right; /* right element */ \
struct type *rbe_parent; /* parent element */ \
+ int rbe_color; /* node color */ \
}
-#define RB_LF(elm, field) (elm)->field.rbe_left
-#define RB_RT(elm, field) (elm)->field.rbe_right
-#define RB_FLIP(elm) (*(__uintptr_t *)&(elm) ^= 1)
-#define RB_FLIP_LF(elm, field) RB_FLIP(RB_LF(elm, field))
-#define RB_FLIP_RT(elm, field) RB_FLIP(RB_RT(elm, field))
-#define RB_ISRED(elm) ((*(__uintptr_t *)&(elm) & 1) != 0)
-#define RB_RED_LF(elm, field) RB_ISRED(RB_LF(elm, field))
-#define RB_RED_RT(elm, field) RB_ISRED(RB_RT(elm, field))
-#define RB_PTR(elm, field) ((__typeof(elm->field.rbe_parent)) \
- ((__uintptr_t)(elm) & ~(__uintptr_t)1))
-#define RB_LEFT(elm, field) RB_PTR(RB_LF(elm, field), field)
-#define RB_RIGHT(elm, field) RB_PTR(RB_RT(elm, field), field)
+#define RB_LEFT(elm, field) (elm)->field.rbe_left
+#define RB_RIGHT(elm, field) (elm)->field.rbe_right
#define RB_PARENT(elm, field) (elm)->field.rbe_parent
+#define RB_COLOR(elm, field) (elm)->field.rbe_color
+#define RB_ISRED(elm, field) ((elm) != NULL && RB_COLOR(elm, field) == RB_RED)
#define RB_ROOT(head) (head)->rbh_root
#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
-#define RB_BOOL int
-#define RB_TRUE 1
-#define RB_FALSE 0
-/* For debugging support */
-#define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? RB_FALSE : \
- RB_LEFT(RB_PARENT(elm, field), field) == elm ? \
- RB_RED_LF(RB_PARENT(elm, field), field) : \
- RB_RED_RT(RB_PARENT(elm, field), field))
+#define RB_SET(elm, parent, field) do { \
+ RB_PARENT(elm, field) = parent; \
+ RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
+ RB_COLOR(elm, field) = RB_RED; \
+} while (/*CONSTCOND*/ 0)
+
+#define RB_SET_BLACKRED(black, red, field) do { \
+ RB_COLOR(black, field) = RB_BLACK; \
+ RB_COLOR(red, field) = RB_RED; \
+} while (/*CONSTCOND*/ 0)
/*
* Something to be invoked in a loop at the root of every modified subtree,
@@ -347,42 +344,37 @@ struct { \
#define RB_AUGMENT(x) break
#endif
-/*
- * Fix pointers to a parent, and from a parent, as part of rotation.
- */
-#define RB_ROTATE_PARENT(head, elm, tmp, field) do { \
- if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) == NULL) \
- RB_ROOT(head) = (tmp); \
- else if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
- RB_LF(RB_PARENT(elm, field), field) = (tmp); \
- else \
- RB_RT(RB_PARENT(elm, field), field) = (tmp); \
- RB_PARENT(elm, field) = (tmp); \
-} while (/*CONSTCOND*/ 0)
-
-/*
- * Rotation makes the descending node red, and the ascending
- * node not-red.
- */
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
(tmp) = RB_RIGHT(elm, field); \
- if ((RB_RT(elm, field) = RB_LF(tmp, field)) != NULL) { \
+ if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
} \
- RB_ROTATE_PARENT(head, elm, tmp, field); \
- RB_LF(tmp, field) = (elm); \
- RB_FLIP_LF(tmp, field); \
+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_LEFT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
RB_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
(tmp) = RB_LEFT(elm, field); \
- if ((RB_LF(elm, field) = RB_RT(tmp, field)) != NULL) { \
+ if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
} \
- RB_ROTATE_PARENT(head, elm, tmp, field); \
- RB_RT(tmp, field) = (elm); \
- RB_FLIP_RT(tmp, field); \
+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_RIGHT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
RB_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)
@@ -447,105 +439,110 @@ struct { \
attr void \
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
{ \
- struct type *gparent, *parent; \
- while ((parent = RB_PARENT(elm, field)) != NULL) { \
- if (RB_LEFT(parent, field) == elm) \
- RB_FLIP_LF(parent, field); \
- else \
- RB_FLIP_RT(parent, field); \
- if ((gparent = RB_PARENT(parent, field)) == NULL) \
- break; \
- if (RB_RED_LF(gparent, field) && \
- RB_RED_RT(gparent, field)) { \
- RB_FLIP_LF(gparent, field); \
- RB_FLIP_RT(gparent, field); \
- elm = gparent; \
- continue; \
- } \
- if (RB_RED_LF(gparent, field) && \
- parent == RB_LEFT(gparent, field)) { \
+ struct type *parent, *gparent, *tmp; \
+ while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) { \
+ gparent = RB_PARENT(parent, field); \
+ if (parent == RB_LEFT(gparent, field)) { \
+ tmp = RB_RIGHT(gparent, field); \
+ if (RB_ISRED(tmp, field)) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
+ } \
if (RB_RIGHT(parent, field) == elm) { \
- RB_ROTATE_LEFT(head, parent, elm, field);\
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ tmp = parent; \
parent = elm; \
+ elm = tmp; \
+ } \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_RIGHT(head, gparent, tmp, field); \
+ } else { \
+ tmp = RB_LEFT(gparent, field); \
+ if (RB_ISRED(tmp, field)) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
} \
- RB_ROTATE_RIGHT(head, gparent, parent, field); \
- } else if (RB_RED_RT(gparent, field) && \
- parent == RB_RIGHT(gparent, field)) { \
if (RB_LEFT(parent, field) == elm) { \
- RB_ROTATE_RIGHT(head, parent, elm, field);\
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ tmp = parent; \
parent = elm; \
+ elm = tmp; \
} \
- RB_ROTATE_LEFT(head, gparent, parent, field); \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_LEFT(head, gparent, tmp, field); \
} \
- break; \
} \
+ RB_COLOR(head->rbh_root, field) = RB_BLACK; \
}
#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
attr void \
-name##_RB_REMOVE_COLOR(struct name *head, struct type *elm) \
+name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \
{ \
- struct type *par, *sib, *tmp; \
- RB_BOOL go_left, left_child, red_par; \
- left_child = (RB_LEFT(elm, field) == NULL); \
+ struct type *elm, *tmp; \
+ elm = NULL; \
do { \
- go_left = left_child; \
- if (go_left ? \
- !RB_RED_RT(elm, field) : \
- !RB_RED_LF(elm, field)) { \
- par = RB_PARENT(elm, field); \
- left_child = par != NULL && \
- RB_LEFT(par, field) == elm; \
- red_par = left_child ? RB_RED_LF(par, field) : \
- par == NULL ? RB_TRUE : \
- RB_RED_RT(par, field); \
- } \
- if (go_left) { \
- if (RB_RED_RT(elm, field)) { \
- red_par = RB_TRUE; \
- RB_ROTATE_LEFT(head, elm, par, field); \
+ if (RB_LEFT(parent, field) == elm) { \
+ 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);\
+ tmp = RB_RIGHT(parent, field); \
} \
- sib = RB_RIGHT(elm, field); \
- if (RB_RED_LF(sib, field)) { \
- RB_ROTATE_RIGHT(head, sib, tmp, field); \
- sib = tmp; \
- } else if (!RB_RED_RT(sib, field)) { \
- RB_FLIP_RT(elm, field); \
- elm = par; \
+ 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(tmp, field) = RB_RED; \
+ elm = parent; \
+ parent = RB_PARENT(elm, field); \
continue; \
} \
- if (RB_RED_RT(sib, field)) \
- RB_FLIP_RT(sib, field); \
- RB_ROTATE_LEFT(head, elm, sib, field); \
- RB_FLIP_LF(sib, field); \
+ 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); \
+ elm = RB_ROOT(head); \
break; \
} else { \
- if (RB_RED_LF(elm, field)) { \
- red_par = RB_TRUE; \
- RB_ROTATE_RIGHT(head, elm, par, field); \
+ 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);\
+ tmp = RB_LEFT(parent, field); \
} \
- sib = RB_LEFT(elm, field); \
- if (RB_RED_RT(sib, field)) { \
- RB_ROTATE_LEFT(head, sib, tmp, field); \
- sib = tmp; \
- } else if (!RB_RED_LF(sib, field)) { \
- RB_FLIP_LF(elm, field); \
- elm = par; \
+ 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); \
+ } 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_RED_LF(sib, field)) \
- RB_FLIP_LF(sib, field); \
- RB_ROTATE_RIGHT(head, elm, sib, field); \
- RB_FLIP_RT(sib, field); \
+ 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); \
+ elm = RB_ROOT(head); \
break; \
} \
- } while (!red_par); \
- if (par != NULL && red_par) { \
- if (left_child) \
- RB_FLIP_LF(par, field); \
- else \
- RB_FLIP_RT(par, field); \
- } \
+ } while (!RB_ISRED(elm, field) && parent != NULL); \
+ RB_COLOR(elm, field) = RB_BLACK; \
}
#define RB_GENERATE_REMOVE(name, type, field, attr) \
@@ -553,11 +550,12 @@ attr struct type * \
name##_RB_REMOVE(struct name *head, struct type *elm) \
{ \
struct type *child, *old, *parent, *parent_old, *right; \
- RB_BOOL old_red, red; \
+ int color; \
\
old = elm; \
parent_old = parent = RB_PARENT(elm, field); \
right = RB_RIGHT(elm, field); \
+ color = RB_COLOR(elm, field); \
if (RB_LEFT(elm, field) == NULL) \
elm = child = right; \
else if (right == NULL) \
@@ -565,8 +563,7 @@ name##_RB_REMOVE(struct name *head, struct type *elm) \
else { \
if ((child = RB_LEFT(right, field)) == NULL) { \
child = RB_RIGHT(right, field); \
- red = RB_RED_RT(old, field); \
- RB_RT(old, field) = child; \
+ RB_RIGHT(old, field) = child; \
parent = elm = right; \
} else { \
do \
@@ -574,31 +571,23 @@ name##_RB_REMOVE(struct name *head, struct type *elm) \
while ((child = RB_LEFT(elm, field)) != NULL); \
child = RB_RIGHT(elm, field); \
parent = RB_PARENT(elm, field); \
- red = RB_RED_LF(parent, field); \
- RB_LF(parent, field) = child; \
+ RB_LEFT(parent, field) = child; \
RB_PARENT(RB_RIGHT(old, field), field) = elm; \
} \
RB_PARENT(RB_LEFT(old, field), field) = elm; \
+ color = RB_COLOR(elm, field); \
elm->field = old->field; \
} \
- if (parent_old == NULL) { \
+ if (parent_old == NULL) \
RB_ROOT(head) = elm; \
- old_red = RB_FALSE; \
- } else if (RB_LEFT(parent_old, field) == old) { \
- old_red = RB_RED_LF(parent_old, field); \
- RB_LF(parent_old, field) = elm; \
- if (old_red && parent != parent_old) \
- RB_FLIP_LF(parent_old, field); \
- } else { \
- old_red = RB_RED_RT(parent_old, field); \
- RB_RT(parent_old, field) = elm; \
- if (old_red && parent != parent_old) \
- RB_FLIP_RT(parent_old, field); \
- } \
- if (child != NULL) \
+ else if (RB_LEFT(parent_old, field) == old) \
+ RB_LEFT(parent_old, field) = elm; \
+ else \
+ RB_RIGHT(parent_old, field) = elm; \
+ if (child != NULL) { \
RB_PARENT(child, field) = parent; \
- else if (parent != NULL && \
- (parent != parent_old ? !red : !old_red)) \
+ RB_COLOR(child, field) = RB_BLACK; \
+ } else if (color != RB_RED && parent != NULL) \
name##_RB_REMOVE_COLOR(head, parent); \
while (parent != NULL) { \
RB_AUGMENT(parent); \
@@ -626,14 +615,14 @@ name##_RB_INSERT(struct name *head, struct type *elm) \
else \
return (tmp); \
} \
- RB_PARENT(elm, field) = parent; \
- RB_LF(elm, field) = RB_RT(elm, field) = NULL; \
- if (parent == NULL) \
+ RB_SET(elm, parent, field); \
+ if (parent != NULL) { \
+ if (comp < 0) \
+ RB_LEFT(parent, field) = elm; \
+ else \
+ RB_RIGHT(parent, field) = elm; \
+ } else \
RB_ROOT(head) = elm; \
- else if (comp < 0) \
- RB_LF(parent, field) = elm; \
- else \
- RB_RT(parent, field) = elm; \
name##_RB_INSERT_COLOR(head, elm); \
while (elm != NULL) { \
RB_AUGMENT(elm); \
--
2.26.2
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD
2020-10-19 16:05 [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Sebastian Huber
` (8 preceding siblings ...)
2020-10-19 16:05 ` [PATCH 09/11] Linuxkpi uses the rb-tree structures Sebastian Huber
@ 2020-10-26 9:52 ` Corinna Vinschen
9 siblings, 0 replies; 11+ messages in thread
From: Corinna Vinschen @ 2020-10-26 9:52 UTC (permalink / raw)
To: newlib
On Oct 19 18:05, Sebastian Huber wrote:
> This patch set adds some changes after the last synchronization point with
> FreeBSD to Newlib. In a simple benchmark, the node insert/extract performance
> improved.
>
> In an intermediate step of this patch set the node color member is removed.
> Later it is restored. I propose to keep the patch series as is to have the
> same change history as FreeBSD.
>
> FreeBSD also changed the implementation to so that the node color is stored in
> the parent pointer in follow up patches. In addition, they changed the
> algorithm from red-black to weak AVL. These changes are NOT INCLUDED, since
> they break the ABI/API. I did some rough benchmarking and was not immediately
> convinced that the new implementation in FreeBSD is better.
>
> dougm (10):
> Correct the use of RB_AUGMENT in the RB_TREE
> For the case when RB_REMOVE requires a nontrivial
> RB_REMOVE invokes RB_REMOVE_COLOR either when
> Remove from RB_REMOVE_COLOR some null checks
> To reduce the size of an rb_node, drop the color
> Restore an RB_COLOR macro, for the benefit of
> Fixup r361997 by balancing parens. Duh.
> Linuxkpi uses the rb-tree structures
> In concluding RB_REMOVE_COLOR, in the case when
> Define RB_SET_PARENT to do all assignments
>
> trasz (1):
> Add RB_REINSERT(3), a low overhead alternative to
>
> newlib/libc/include/sys/tree.h | 273 ++++++++++++++++-----------------
> 1 file changed, 130 insertions(+), 143 deletions(-)
>
> --
> 2.26.2
Please go ahead.
Thanks,
Corinna
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2020-10-26 9:52 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-10-19 16:05 [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Sebastian Huber
2020-10-19 16:05 ` [PATCH 01/11] Add RB_REINSERT(3), a low overhead alternative to Sebastian Huber
2020-10-19 16:05 ` [PATCH 02/11] Correct the use of RB_AUGMENT in the RB_TREE Sebastian Huber
2020-10-19 16:05 ` [PATCH 03/11] For the case when RB_REMOVE requires a nontrivial Sebastian Huber
2020-10-19 16:05 ` [PATCH 04/11] RB_REMOVE invokes RB_REMOVE_COLOR either when Sebastian Huber
2020-10-19 16:05 ` [PATCH 05/11] Remove from RB_REMOVE_COLOR some null checks Sebastian Huber
2020-10-19 16:05 ` [PATCH 06/11] To reduce the size of an rb_node, drop the color Sebastian Huber
2020-10-19 16:05 ` [PATCH 07/11] Restore an RB_COLOR macro, for the benefit of Sebastian Huber
2020-10-19 16:05 ` [PATCH 08/11] Fixup r361997 by balancing parens. Duh Sebastian Huber
2020-10-19 16:05 ` [PATCH 09/11] Linuxkpi uses the rb-tree structures Sebastian Huber
2020-10-26 9:52 ` [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Corinna Vinschen
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).