From nobody Sun Jun 19 06:28:36 2022 X-Original-To: dev-commits-src-branches@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 6494286099C; Sun, 19 Jun 2022 06:28:37 +0000 (UTC) (envelope-from git@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 "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4LQjXP2Lh2z4vFv; Sun, 19 Jun 2022 06:28:37 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1655620117; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=WOwz/mzywMM78ez+jgEY3NmuzdqMJN3QcWseAzRlrm8=; b=nACLgNHgLWClbMsop6xpxQZt1icqTQCf/RDQtB5FTXSuC+ZBf9fuR5zMZTyJSpLuf/Rk/2 GdWY2P5xQuYaE1xhGfCUenDewdYjjqXUl/QDPse/5rUaEYULFfZepqQcpD8TEsDBm8is23 PXDQqJQM+Xx3dusnEwDOouMjCPo5jLAfQuyF4bpecGy0xPcEaSqXlTfjMZHycXZsA2WzPc ds4OFkRlbLlNU+EPqg6zCGyEfzAGEkG60+KlfTElxx6B7SUMqguUZkhmDy0AvfHs35Od0Z neVt1xVtOx3TJNLv3zaXh0dnaCBTIypg8JYawqo43yHaGMYSP6RfxMD0HhVCnQ== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (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 did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 1EE7F236BF; Sun, 19 Jun 2022 06:28:37 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 25J6Sa5N041246; Sun, 19 Jun 2022 06:28:36 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 25J6Sa2S041245; Sun, 19 Jun 2022 06:28:36 GMT (envelope-from git) Date: Sun, 19 Jun 2022 06:28:36 GMT Message-Id: <202206190628.25J6Sa2S041245@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Doug Moore Subject: git: 0ee295149ae0 - stable/13 - rb_tree: drop needless tests from rb_next, rb_prev List-Id: Commits to the stable branches of the FreeBSD src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-branches List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-branches@freebsd.org X-BeenThere: dev-commits-src-branches@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: dougm X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: 0ee295149ae09a2e486c50dc4d91b433b139c616 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1655620117; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=WOwz/mzywMM78ez+jgEY3NmuzdqMJN3QcWseAzRlrm8=; b=LOUtVL1r8SC/o0ZpEBW02OPEf8wAnIIsGMxXXJPR97ye9Fo0IMdHZOAr4k1IrRcnv33AdY sUqI4prnIXsQiU3K8SaPMkQgs/OWH4awe0M2UxMKzRxBpFuacg7lcpHD5GMC3kXoMloYfD WR1s4ycdG8Tj4SQ5na5UraNBj0qRuc1Ltkla4XPbdLzph8jzySNzuJiL1xuDRsUtLKLNSq J/i3l94gWP4gi0P0dLCOt3qzkts/TPHXyDpN1hVJmTErr56zazMlRLLznEJtVKot/MEw3/ C1PmhzM75nJ2QJTh7YQzI+R/vnTaf83fYLGn9cDeaer9z7B5Xnylpzt3J4KPbw== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1655620117; a=rsa-sha256; cv=none; b=iFD+PZbDqwSZYXBHgG3iW/NRIZdrZn52dEgJlz1sD7MHISBYASzW1SSXdsXvYu1YO/rA0e 9cC2ul6lo0PEo8KWSnnVCuQAUpI67IWKo9XnyjZKQL7JdqKzNDxa0zKuw+2HQdGryXo6hu TQZXYt2zdjH6PWVn4S6F1fxXEe+sVQ/LBIDLNKuurAsw3cuYj8H05F9nVfw1BYCcpRNFxn Nbbo24eZu5vfpnUogTbSwxziT+OdAGeugdVT/zNmZHb/igRFW6nsOaeySW8bABoC3uTl7c 73l2MQy5tnnZ0mcZSpuV/SPqkEp2lrPd32ATfyOPifHt7UiRbak+iL/FTYxKGg== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=0ee295149ae09a2e486c50dc4d91b433b139c616 commit 0ee295149ae09a2e486c50dc4d91b433b139c616 Author: Doug Moore AuthorDate: 2022-06-10 21:53:16 +0000 Commit: Doug Moore CommitDate: 2022-06-19 06:25:00 +0000 rb_tree: drop needless tests from rb_next, rb_prev In RB_NEXT, when there is no RB_RIGHT node, the search must proceed through the parent node. There is code written to handle the case when the parent is non-NULL and the current element is the left child of that parent. If you assume that the current element is either the left child of its parent, or the right child of its parent, but not both, then this test is not necessary. Instead of assigning RB_PARENT(elm, field) to elm when elm == RB_LEFT, removing the test has the code assign RB_PARENT(elm, field) to elm when elm != RB_RIGHT. There's no need to examine the RB_LEFT field at all. This change removes that needless RB_LEFT test, and makes a similar change to the RB_PREV implementation. Reviewed by: alc MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D35450 (cherry picked from commit 36447829aee545ad9eafbfff3a783ee58cfb28fd) --- sys/sys/tree.h | 22 ++++++---------------- 1 file changed, 6 insertions(+), 16 deletions(-) diff --git a/sys/sys/tree.h b/sys/sys/tree.h index eb5f244d8a12..4cdd9548ba62 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -719,15 +719,10 @@ name##_RB_NEXT(struct type *elm) \ while (RB_LEFT(elm, field)) \ elm = RB_LEFT(elm, field); \ } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ + while (RB_PARENT(elm, field) && \ + (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ elm = RB_PARENT(elm, field); \ - } \ + elm = RB_PARENT(elm, field); \ } \ return (elm); \ } @@ -742,15 +737,10 @@ name##_RB_PREV(struct type *elm) \ while (RB_RIGHT(elm, field)) \ elm = RB_RIGHT(elm, field); \ } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ + while (RB_PARENT(elm, field) && \ + (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ elm = RB_PARENT(elm, field); \ - } \ + elm = RB_PARENT(elm, field); \ } \ return (elm); \ }