From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1921) id 1F27C3850412; Mon, 26 Oct 2020 13:32:38 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 1F27C3850412 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] In concluding RB_REMOVE_COLOR, in the case when X-Act-Checkin: newlib-cygwin X-Git-Author: dougm X-Git-Refname: refs/heads/master X-Git-Oldrev: 977a827d2908df223666641a890a5833df3f796c X-Git-Newrev: d03eaf36dc30bf41fc57f8de100c105f49063429 Message-Id: <20201026133238.1F27C3850412@sourceware.org> Date: Mon, 26 Oct 2020 13:32:38 +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: Mon, 26 Oct 2020 13:32:38 -0000 https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;h=d03eaf36dc30bf41fc57f8de100c105f49063429 commit d03eaf36dc30bf41fc57f8de100c105f49063429 Author: dougm Date: Sat Jun 20 20:25:39 2020 +0000 In concluding RB_REMOVE_COLOR, in the case when the sibling of the root of the too-short tree is black and at least one of the children of that sibling is red, either one or two rotations finish the rebalancing. In the case when both of the children are red, the current implementation uses two rotations where only one is necessary. This change removes that extra rotation, and in that case also removes a needless black-to-red-to-black recoloring. Reviewed by: markj Differential Revision: https://reviews.freebsd.org/D25335 Diff: --- newlib/libc/include/sys/tree.h | 26 +++++++++++--------------- 1 file changed, 11 insertions(+), 15 deletions(-) diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h index 372c001b9..2e1cc1eda 100644 --- a/newlib/libc/include/sys/tree.h +++ b/newlib/libc/include/sys/tree.h @@ -493,21 +493,19 @@ 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)) { \ + if (RB_ISRED(RB_RIGHT(tmp, field), field)) \ + RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ + else 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(oleft, field) = RB_BLACK; \ + tmp = oleft; \ + } else { \ 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; \ RB_ROTATE_LEFT(head, parent, tmp, field); \ @@ -520,21 +518,19 @@ 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_RIGHT(tmp, field), field)) { \ + if (RB_ISRED(RB_LEFT(tmp, field), field)) \ + RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ + else 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); \ + RB_COLOR(oright, field) = RB_BLACK; \ + tmp = oright; \ } 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; \ RB_ROTATE_RIGHT(head, parent, tmp, field); \