From nobody Mon Sep 26 17:41:00 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 4MbqmX5XSLz4YMbG; Mon, 26 Sep 2022 17:41:00 +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 4MbqmX54hqz3NDX; Mon, 26 Sep 2022 17:41:00 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1664214060; 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=EXdLR/tp33piP9lDEM5v55z4iOUze7tJYZrhxBCtG5k=; b=vug+mw2t6c6/c/owLxuacvtiO0299wtre0psbVLRO3n47VwizdfM3auu/y90tfBaGDOSsa YDrPKDDSv3KjI3jxoXT5drK/lwYtZs81959Gfw/hXuCBSWSwOjnw4Jr8KTplQz4c32Ec/g y81rVMQzlYti/tPj8vdBx+cvDN4Neg9dWM3C71fcjz+cfIelEtO/RBRCcg7kGFquxEB550 /PK2efINsAZKGDpkerEPWSAmzzuukQ2fVoGplzsAjm/mk0+vjaaDwCJwwrFSKFSl/cOp5W VF0w59MM5kseSWW5lgjq3qKNMeLS4tF23p2lETLR8CY3nW9VnoxypICFo3s3Fg== 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 4MbqmX48lvzqxv; Mon, 26 Sep 2022 17:41:00 +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 28QHf03g010802; Mon, 26 Sep 2022 17:41:00 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 28QHf04K010801; Mon, 26 Sep 2022 17:41:00 GMT (envelope-from git) Date: Mon, 26 Sep 2022 17:41:00 GMT Message-Id: <202209261741.28QHf04K010801@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: b5b07c71e836 - main - rb_tree: add augmentation comments 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: b5b07c71e83637af8a2507ef96c32bc7e2d226c6 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1664214060; 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=EXdLR/tp33piP9lDEM5v55z4iOUze7tJYZrhxBCtG5k=; b=bS1z6mEInosKJO2emZs+kmAE4Q4moH0Z/rour7Ql/DQl59muaUmOLk04rZ9muYf7dZvv9F IhfnIPTwE7s6CVErByJxK1nBLRZ5ENMldv/H6E1i28Baz4UjJAzh1VYM8vIoMdmjQR3ugn ybZdV5dbsM0kHJ1WmAWrYRjWj6R1IrvwBYhgKOFrJukZMExKHE34g5y6FZbnOxHcrHngRX F6zoosmv+V3IvfQDEajEOYDmulw8Y6iD8PIPsxyK/h7BbmFCdn9vfpRhUHdZoKycpaX2rn 01BfOcIOn3WYRwTNHIRRyvlvypPKKsMsXNaCUYAt+ZLYz9cFBqpN0uyk5rSGcA== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1664214060; a=rsa-sha256; cv=none; b=WZBGiZRLLcaz+0PA8e2e+g9z8pmSAaqexbql0VURFRgo2achlLdzenyqOZHwL5sEzVEu7R IsS+LuiRpn7kSzE7ePFY8KwfL5s2tmiU/hHq4AeeJDYipnSnaz/QQbAfiWs1dEML6Qt6kD X+mhKukoH22LRMwdzspBRGSG/iJV6Kad9xDlPJ9uuiQ49JKq0fn4XHLD9K51WpNHqhyIqP +LZaR92fA4F59O9qA5aTqA+G6MeLvSaNaNI0QCaVHlmVf8yTq4tcplXmwLSpzVgrt2Bqyj WIiR+gE/4gR7/4OAL/jpbaCWSiBot4LZMziDGTm7fhdpZmh0IIAMAqGxm1xeCg== 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=b5b07c71e83637af8a2507ef96c32bc7e2d226c6 commit b5b07c71e83637af8a2507ef96c32bc7e2d226c6 Author: Doug Moore AuthorDate: 2022-09-26 17:39:16 +0000 Commit: Doug Moore CommitDate: 2022-09-26 17:39:16 +0000 rb_tree: add augmentation comments Add comments to better explain why augmentation is done in several places. Reviewed by: alc MFC after: 2 weeks Differential Revision: https://reviews.freebsd.org/D36646 --- sys/sys/tree.h | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/sys/sys/tree.h b/sys/sys/tree.h index d37e5a338f8b..460af08407b8 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -598,6 +598,10 @@ name##_RB_INSERT_COLOR(struct name *head, \ RB_ROTATE(parent, child, sibdir, field); \ _RB_UP(child, field) = gpar; \ RB_SWAP_CHILD(head, gpar, parent, child, field); \ + /* \ + * Elements rotated down have new, smaller subtrees, \ + * so update augmentation for them. \ + */ \ if (elm != child) \ RB_AUGMENT_CHECK(elm); \ RB_AUGMENT_CHECK(parent); \ @@ -724,6 +728,11 @@ name##_RB_REMOVE_COLOR(struct name *head, \ RB_ROTATE(parent, elm, elmdir, field); \ RB_SET_PARENT(elm, gpar, field); \ RB_SWAP_CHILD(head, gpar, parent, elm, field); \ + /* \ + * An element rotated down, but not into the search \ + * path has a new, smaller subtree, so update \ + * augmentation for it. \ + */ \ if (sib != elm) \ RB_AUGMENT_CHECK(sib); \ return (parent); \ @@ -779,6 +788,11 @@ name##_RB_REMOVE(struct name *head, struct type *out) \ } \ _RB_AUGMENT_WALK(parent, opar, field); \ if (opar != NULL) { \ + /* \ + * Elements rotated into the search path have \ + * changed subtrees, so update augmentation for \ + * them if AUGMENT_WALK didn't. \ + */ \ RB_AUGMENT_CHECK(opar); \ RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \ } \ @@ -811,6 +825,11 @@ name##_RB_INSERT(struct name *head, struct type *elm) \ tmp = name##_RB_INSERT_COLOR(head, parent, elm); \ _RB_AUGMENT_WALK(elm, tmp, field); \ if (tmp != NULL) \ + /* \ + * An element rotated into the search path has a \ + * changed subtree, so update augmentation for it if \ + * AUGMENT_WALK didn't. \ + */ \ RB_AUGMENT_CHECK(tmp); \ return (NULL); \ }