From owner-svn-src-all@freebsd.org Thu May 21 05:34:02 2020 Return-Path: Delivered-To: svn-src-all@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id BD0F7329F53; Thu, 21 May 2020 05:34:02 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 49SJFk4dl7z4QFv; Thu, 21 May 2020 05:34:02 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 9A0A38355; Thu, 21 May 2020 05:34:02 +0000 (UTC) (envelope-from dougm@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id 04L5Y2l2001035; Thu, 21 May 2020 05:34:02 GMT (envelope-from dougm@FreeBSD.org) Received: (from dougm@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id 04L5Y2VB001034; Thu, 21 May 2020 05:34:02 GMT (envelope-from dougm@FreeBSD.org) Message-Id: <202005210534.04L5Y2VB001034@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: dougm set sender to dougm@FreeBSD.org using -f From: Doug Moore Date: Thu, 21 May 2020 05:34:02 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r361324 - head/sys/sys X-SVN-Group: head X-SVN-Commit-Author: dougm X-SVN-Commit-Paths: head/sys/sys X-SVN-Commit-Revision: 361324 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.33 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 21 May 2020 05:34:02 -0000 Author: dougm Date: Thu May 21 05:34:02 2020 New Revision: 361324 URL: https://svnweb.freebsd.org/changeset/base/361324 Log: 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 Modified: head/sys/sys/tree.h Modified: head/sys/sys/tree.h ============================================================================== --- head/sys/sys/tree.h Thu May 21 05:02:58 2020 (r361323) +++ head/sys/sys/tree.h Thu May 21 05:34:02 2020 (r361324) @@ -562,48 +562,44 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type 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) { \