From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1921) id D43213894C34; Mon, 26 Oct 2020 13:32:02 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D43213894C34 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] For the case when RB_REMOVE requires a nontrivial X-Act-Checkin: newlib-cygwin X-Git-Author: dougm X-Git-Refname: refs/heads/master X-Git-Oldrev: 1256d090ad0de00ef143272d5174009893349520 X-Git-Newrev: 9db2b545710ad398a9012094d33b7e8884013227 Message-Id: <20201026133202.D43213894C34@sourceware.org> Date: Mon, 26 Oct 2020 13:32:02 +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:02 -0000 https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;h=9db2b545710ad398a9012094d33b7e8884013227 commit 9db2b545710ad398a9012094d33b7e8884013227 Author: dougm Date: Thu May 21 05:34:02 2020 +0000 For the case when RB_REMOVE requires a nontrivial search to find the node to replace the one being removed, restructure to first remove the replacement node and correct the parent pointers around it, and then let the all-cases code at the end deal with the parent of the deleted node, making it point to the replacement node. This removes one or two conditional branches. Reviewed by: markj Tested by: pho Differential Revision: https://reviews.freebsd.org/D24845 Diff: --- newlib/libc/include/sys/tree.h | 52 +++++++++++++++++++----------------------- 1 file changed, 24 insertions(+), 28 deletions(-) diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h index 5c31ff2ea..b1e5e23a7 100644 --- a/newlib/libc/include/sys/tree.h +++ b/newlib/libc/include/sys/tree.h @@ -562,48 +562,44 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) attr struct type * \ name##_RB_REMOVE(struct name *head, struct type *elm) \ { \ - struct type *child, *parent, *old = elm; \ + struct type *child, *parent, *parent_old, *old = elm; \ int color; \ - if (RB_LEFT(elm, field) == NULL) \ - child = RB_RIGHT(elm, field); \ - else if (RB_RIGHT(elm, field) == NULL) \ - child = RB_LEFT(elm, field); \ - else { \ + parent_old = parent = RB_PARENT(elm, field); \ + color = RB_COLOR(elm, field); \ + if (RB_LEFT(elm, field) == NULL) { \ + elm = child = RB_RIGHT(elm, field); \ + if (elm != NULL) \ + RB_PARENT(elm, field) = parent; \ + } else if (RB_RIGHT(elm, field) == NULL) { \ + elm = child = RB_LEFT(elm, field); \ + RB_PARENT(elm, field) = parent; \ + } else { \ 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; \ + parent = elm; \ } else { \ do \ elm = child; \ while ((child = RB_LEFT(elm, field)) != NULL); \ child = RB_RIGHT(elm, field); \ + parent = RB_PARENT(elm, field); \ + RB_LEFT(parent, field) = child; \ + if (child != NULL) \ + RB_PARENT(child, field) = parent; \ 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(parent, field) = elm; \ - } else \ - RB_ROOT(head) = elm; \ + color = RB_COLOR(elm, field); \ + elm->field = old->field; \ } \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child != NULL) \ - RB_PARENT(child, field) = parent; \ - if (parent != NULL) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - } else \ - RB_ROOT(head) = child; \ - if (elm != old) \ - (elm)->field = (old)->field; \ + if (parent_old == NULL) \ + RB_ROOT(head) = elm; \ + else if (RB_LEFT(parent_old, field) == old) \ + RB_LEFT(parent_old, field) = elm; \ + else \ + RB_RIGHT(parent_old, field) = elm; \ if (color == RB_BLACK) \ name##_RB_REMOVE_COLOR(head, parent, child); \ while (parent != NULL) { \