public inbox for newlib-cvs@sourceware.org
help / color / mirror / Atom feed
From: Sebastian Huber <sh@sourceware.org>
To: newlib-cvs@sourceware.org
Subject: [newlib-cygwin] Correct the use of RB_AUGMENT in the RB_TREE
Date: Mon, 26 Oct 2020 13:31:57 +0000 (GMT) [thread overview]
Message-ID: <20201026133157.CC6163894C34@sourceware.org> (raw)
https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;h=1256d090ad0de00ef143272d5174009893349520
commit 1256d090ad0de00ef143272d5174009893349520
Author: dougm <dougm@FreeBSD.org>
Date: Mon Jan 27 15:09:13 2020 +0000
Correct the use of RB_AUGMENT in the RB_TREE
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
Diff:
---
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); \
}
reply other threads:[~2020-10-26 13:31 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20201026133157.CC6163894C34@sourceware.org \
--to=sh@sourceware.org \
--cc=newlib-cvs@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).