From nobody Wed Oct 12 03:00:27 2022 X-Original-To: dev-commits-src-all@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 4MnHT74crVz4f7fB; Wed, 12 Oct 2022 03:00:27 +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 4MnHT71yypz4HYx; Wed, 12 Oct 2022 03:00:27 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1665543627; 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=Nq5BL2zYu7zPNJ3Ylw1HSPWc6lqD4Bu9GwcDabYtsFQ=; b=kfU7SPpq19Kx/t2Bzw1X9i7phEKGXacrNXYm8EeviE3Ryv7xsHTMXVT7eEy3d8640rT9nU KdKWzucfSoTipOIgQ5NZCgZjzJrtjahQsZZuCq2OXaxliUA0aljK9XpdBCG6DGNq/yIckZ /usZU4cXFekLku7oKa+LQLPKiWxrpWbYZ02fJ7H8MpELwS17vRmeI71QXEs9m8pPpiV3aw HefmLMg7A7obWLxCTLl7kmGUM+EDhamYQ6uNn9ML/SjIPse/KyAiW8xGymy2xWHStcH8Vk QVyMZJq7u/A4m8V8TBq1OMRVc/LFiaVVjaoO4/AVohYM4sA/XHzlJneIutPTXQ== 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 4MnHT70sB0z19pq; Wed, 12 Oct 2022 03:00:27 +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 29C30R2Z079544; Wed, 12 Oct 2022 03:00:27 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 29C30Rru079543; Wed, 12 Oct 2022 03:00:27 GMT (envelope-from git) Date: Wed, 12 Oct 2022 03:00:27 GMT Message-Id: <202210120300.29C30Rru079543@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: 871847f65312 - stable/13 - rb_tree: add augmentation comments List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@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: 871847f653127d37626eebbc6f6d0980f540cf85 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1665543627; 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=Nq5BL2zYu7zPNJ3Ylw1HSPWc6lqD4Bu9GwcDabYtsFQ=; b=FpWIf/Z181sEMg0BGsSSkByD1uHfZI4wGgUl4DfxRPSoHcOgyGOKq5vxlIS7CmTM3Odbic BE//EmdKco0MXbiZtvpaAD4CX6EoGm66XFhCLECK3t2DlY/Y7SurQuhIW7DK8v7qgGVtBd wbhzzOURnmDf/1Zn59V5KJCPYAtPRYpDpOUD/9uvf1sKz3SPQ+gUfKo/dUfZGlKi/Q8WO7 M3fVhLt8HYFLfC5unYp3oyXQPLwM3qohG+vpvg0qwNh7aBJtZsAwcpHBx40JmCYR6NbN9e e+V1LuLJIxv1BlSp81dTDmHrV/sKyCF59J/6iZjl5Hum2MT0lqhkZU3ZW+8zxQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1665543627; a=rsa-sha256; cv=none; b=N9ptMExip67ETFcIgZgjUvtdioWr5KV2OndIl2q0BUPTTqVqIyDSYXZU/4XR98AFEW4zEp /buGqqb7toPJ4R9TGSYXLtvd18bjSruS6vqUiLA5NbzhZv3skyCxUuGv6cGNE6YeS1PcaE s8lVcowZ7RBgX707cVm6rSTAJRmLkUtRRYQTE27tKl9HU73UJSCh+t7J5enJBo6BtlIZs1 g4XAookmXusXWhR3GtCj7JjeTOq/btovau7hZoRtIb+dGghs5CGSE6W4W9Kc4ndp5wQij4 sVZjKnsNsL4Nq/wE0rfTN+zPgtFcJgySBg29TL17dc7LQ/7nKtqjqJf8oZdgHw== 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=871847f653127d37626eebbc6f6d0980f540cf85 commit 871847f653127d37626eebbc6f6d0980f540cf85 Author: Doug Moore AuthorDate: 2022-09-26 17:39:16 +0000 Commit: Doug Moore CommitDate: 2022-10-12 02:47:06 +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 (cherry picked from commit b5b07c71e83637af8a2507ef96c32bc7e2d226c6) --- sys/sys/tree.h | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 51bf4211fea4..10f559f516d2 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); \ }