From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1921) id 1A8473858002; Thu, 7 Oct 2021 16:02:30 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1A8473858002 Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Sebastian Huber To: newlib-cvs@sourceware.org Subject: [newlib-cygwin] sys/tree.h: Add parent rotations X-Act-Checkin: newlib-cygwin X-Git-Author: Sebastian Huber X-Git-Refname: refs/heads/master X-Git-Oldrev: ee30f991c38851f1bfbbf72d19c5c6ee1b97f32a X-Git-Newrev: 5f7f27c81736c11c35c119cc5f18231eb8aaecec Message-Id: <20211007160230.1A8473858002@sourceware.org> Date: Thu, 7 Oct 2021 16:02:30 +0000 (GMT) X-BeenThere: newlib-cvs@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Newlib GIT logs List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 07 Oct 2021 16:02:30 -0000 https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;h=5f7f27c81736c11c35c119cc5f18231eb8aaecec commit 5f7f27c81736c11c35c119cc5f18231eb8aaecec Author: Sebastian Huber 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 { \