From owner-svn-src-all@freebsd.org Sat Jun 20 20:25:40 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 68E32333C6A; Sat, 20 Jun 2020 20:25:40 +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 49q6ch28HHz3XRS; Sat, 20 Jun 2020 20:25:40 +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 4511211BED; Sat, 20 Jun 2020 20:25:40 +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 05KKPeGL029119; Sat, 20 Jun 2020 20:25:40 GMT (envelope-from dougm@FreeBSD.org) Received: (from dougm@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id 05KKPe1t029118; Sat, 20 Jun 2020 20:25:40 GMT (envelope-from dougm@FreeBSD.org) Message-Id: <202006202025.05KKPe1t029118@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: dougm set sender to dougm@FreeBSD.org using -f From: Doug Moore Date: Sat, 20 Jun 2020 20:25:40 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r362450 - head/sys/sys X-SVN-Group: head X-SVN-Commit-Author: dougm X-SVN-Commit-Paths: head/sys/sys X-SVN-Commit-Revision: 362450 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: Sat, 20 Jun 2020 20:25:40 -0000 Author: dougm Date: Sat Jun 20 20:25:39 2020 New Revision: 362450 URL: https://svnweb.freebsd.org/changeset/base/362450 Log: 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 Modified: head/sys/sys/tree.h Modified: head/sys/sys/tree.h ============================================================================== --- head/sys/sys/tree.h Sat Jun 20 20:21:04 2020 (r362449) +++ head/sys/sys/tree.h Sat Jun 20 20:25:39 2020 (r362450) @@ -493,21 +493,19 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type 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_ROTATE_RIGHT(head, tmp, oleft, field); \ RB_COLOR(oleft, field) = RB_BLACK; \ + tmp = oleft; \ + } else { \ 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(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 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); \