From nobody Fri Jun 10 21:56:17 2022 X-Original-To: dev-commits-src-main@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 6E40F8375A0; Fri, 10 Jun 2022 21:56:17 +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 4LKZXx2cctz3QPd; Fri, 10 Jun 2022 21:56:17 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1654898177; 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=WABrvqTQdrwGGNrQmp8Qo9mtDUFaghpQ0pL9MShuMJA=; b=klmIT+cyAC7dTjX6AqNuCiTP236Q658/WlgG0aNgG4TnTdaC34bHYq4JZcBwyozLOEsECN kN0lDfOGkmC/P5Z+D2UQKchcY0b75VSrOngK6rT/NxXe1VlQX0gPBS/TBcOK0OVPsm6uju BrHX7TVCXOOolGPmKPQiJLWZZKVkhKVHlmNClRRTvjj+ajFKOrG4hn2SYBrmTYVfNdnfNS xIXfF7Zj6yTvUxjXsbU9qsZuxhZAH+TqqJue3pllA2m80CM3RC3DYwvUyaOvTvexdcvuXy IxLkMJB38p1UI9ehzvdaDNM6FiTugkVCTVnE7xwI/0VLfwpzKNRM9KfxGkR/fg== 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 398F520739; Fri, 10 Jun 2022 21:56:17 +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 25ALuHfS086034; Fri, 10 Jun 2022 21:56:17 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 25ALuHpj086033; Fri, 10 Jun 2022 21:56:17 GMT (envelope-from git) Date: Fri, 10 Jun 2022 21:56:17 GMT Message-Id: <202206102156.25ALuHpj086033@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Doug Moore Subject: git: 36447829aee5 - main - rb_tree: drop needless tests from rb_next, rb_prev List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@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/main X-Git-Reftype: branch X-Git-Commit: 36447829aee545ad9eafbfff3a783ee58cfb28fd Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1654898177; 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=WABrvqTQdrwGGNrQmp8Qo9mtDUFaghpQ0pL9MShuMJA=; b=cU9fQg1MJnz0gQZNdg3vIm5gRO6YtLteOj49jwgiyi6gfDAVVjPrJxqdqI4THwZCkju1K4 1xga9Jd/UkIC9X1VgtcG+hojuSpKyqc/VtN8FRDEaKP0p42SkTvFD62D7DY4xltri5MFki 9HpMbDhtr/EsTui7W7bqbpONO78I7V2cCbLMQi5k45EmB2ZIHx2gZL5x7ewzvlp9SRbV0q knakcKGNRCOfpXvZF66DSqVEY+Iuzok7A881/t+KyQ/37nvLwRZVa13xNPaCPCNBGjtvLM lDnZJcXbtz/Ln3SF+FIZZsaimSr8LTd0PPgeql4Wl7QyPvaQYeP15lVqCd6MRw== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1654898177; a=rsa-sha256; cv=none; b=b3wWpecxcEnjxCSkmj01WteZtjgCWReZDot6Mzqd9FP7CA3zHQvvchFbknXEzvPdtbeqb2 9Ut7xSiPWfzsM0dlxeFKPwh8mfMwMa9Iaj3AQ23LQn3Rc7vOAGZSwIHyuBUwRpua7lrSJE 8tntub2V1krcq+9nVs05238uap5pDzG/oYTwim5SiWxLfR2aIifapACsE4wxXtLprkJ17W MaUvKk26Fl4uU7hPsxFUO9b4S8Bc28PqP5HwilL8qo9NXCDj6puPUXMuoSR5wT+WtE0PBL 7EEDmLOk2ZBU/QzhODpD74EW3lGiVFifRYd+YS7+hq+2yiqlhYeOix/pJDIC6w== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=36447829aee545ad9eafbfff3a783ee58cfb28fd commit 36447829aee545ad9eafbfff3a783ee58cfb28fd Author: Doug Moore AuthorDate: 2022-06-10 21:53:16 +0000 Commit: Doug Moore CommitDate: 2022-06-10 21:53:16 +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 --- 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 bc01e4de910a..0403288d1d68 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); \ }