[PATCH 02/11] Correct the use of RB_AUGMENT in the RB_TREE
Sebastian Huber
sebastian.huber@embedded-brains.de
Mon Oct 19 16:05:15 GMT 2020
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
More information about the Newlib
mailing list