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] sys/tree.h: Add parent rotations Date: Thu, 7 Oct 2021 16:02:30 +0000 (GMT) [thread overview] Message-ID: <20211007160230.1A8473858002@sourceware.org> (raw) 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 { \
reply other threads:[~2021-10-07 16:02 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=20211007160230.1A8473858002@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: linkBe 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).