From nobody Mon Aug 22 09:22:20 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 4MB6MK15TJz4Z6c7; Mon, 22 Aug 2022 09:22:21 +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 4MB6MK0XJVz3hGT; Mon, 22 Aug 2022 09:22:21 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1661160141; 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=vH8MlWDTRjTWLUAVe6N9dPuWEFnQ2ti5+FZm3sBprRc=; b=k7f63B5GlnBu2Cvi4KTwaRzTJ+g67LL/3kEw6JsvOHkXb1zjCh8CrU5JcY56RsniH1p1M5 lEPKYpBdKgZzt8Iq2CLYga5WfNrUZ6gEcCkxO68zXL0yIFMI3kR1TJPe4DiS/J3GZul8ke Ov4j20Y1QGcsYaUWQmJKYUwz+5NwAGKv82rGElz2jHpWIoUhlxog2aQxELg/hydCpvk6kV DnOCbLVAySPrpIU2IJDQ4RpwDl8IK2dS5aq3GQhU7z1NLUpg5v0MQsz1ITj/CutoiCTwA+ MaC3uOn4p23celUiaML/a18PLbTlLOGdrwehn+AHHKch6qGimQgSIQgcbpUHyA== 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 4MB6MJ6jlQzlJZ; Mon, 22 Aug 2022 09:22:20 +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 27M9MKhJ061467; Mon, 22 Aug 2022 09:22:20 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 27M9MK6p061466; Mon, 22 Aug 2022 09:22:20 GMT (envelope-from git) Date: Mon, 22 Aug 2022 09:22:20 GMT Message-Id: <202208220922.27M9MK6p061466@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: 7ba58de6b6d0 - stable/13 - rb_tree: update augmentation after element change 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: 7ba58de6b6d015094f4153030dabcc441a179c54 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1661160141; 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=vH8MlWDTRjTWLUAVe6N9dPuWEFnQ2ti5+FZm3sBprRc=; b=GUk2lgH9wnsGo18zEEROPf51GxNz0c563Hk9s0CaZUBhNLr9MbplUlcG69FnuwNoDjiuV9 CeFAB4yaln5Xx6t9DAVTqBmmL/kW17aelOuXUo3CelY5zWNSbkgxO3eDOm/riS83yEiYz+ rEhMd37C4ga8kyznGzPpg8TOUZwvrYJUoNHh1Q94tvZKQhd4OSXPeB8L3zfConkPPMCFpH xs2bVd97cJeYo8tLHxH+BA8unTq6ktpiT8PeeVmfxd9ZKAIbe22F9D/EYcFR5KDjMGqSQe yf30kex8IhSgPdgG1YVig81gM8hIM82EEYRPH4tU4e4qjZWEViQCoRyOnXSAKQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1661160141; a=rsa-sha256; cv=none; b=pASAtvTzXlsiS27UGIjiR+O3OkLUXvHph5c3fgWeOTkaRb67tODWgEJVBzBzB4e4N0NCti LPKf0lBO8F65fy6kKQ/BHzf+VpBhqy5oYEsxeMB3JBRd6H/PNELADtDoLiZ76FnDBcJJUl JmDK3HWeZ9fx6WvFvnRRoNkDHVKBZZju3eQrdiDSnuB6dPmPY7EG+JTF+pAAgLaMptoS3Q DtcCgrfbaxsmT6fNeMWlGQnr+LsOQVL7TVdOvkdZjo9mL/w/Lkk1AzqBPYUjZgEQqNwWKy xSFqp8XdNpqU1kwMaMXdEAFP2W+DtPh9zciuJQny5ygd/qpFhtnvpIqJKbflEw== 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=7ba58de6b6d015094f4153030dabcc441a179c54 commit 7ba58de6b6d015094f4153030dabcc441a179c54 Author: Doug Moore AuthorDate: 2022-08-02 16:19:46 +0000 Commit: Doug Moore CommitDate: 2022-08-22 09:21:37 +0000 rb_tree: update augmentation after element change For an augmented rb_tree, allow a faster alternative to removing an element from the tree, tweaking it slightly, and inserting it back into the tree, knowing that its relative position in the tree is unchanged. Instead, just change the element and invoke RB_UPDATE_AUGMENT to fix the augmentation data for all the nodes in the tree. Reviewed by: kib MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D36010 (cherry picked from commit 35557a0d9169172b90df903b0daf389c2839b749) --- share/man/man3/tree.3 | 24 ++++++++++++++++++++---- sys/sys/tree.h | 18 ++++++++++-------- 2 files changed, 30 insertions(+), 12 deletions(-) diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 index c45ce3d3ceb6..86d6569d1955 100644 --- a/share/man/man3/tree.3 +++ b/share/man/man3/tree.3 @@ -100,6 +100,7 @@ .Nm RB_REMOVE , .Nm RB_REINSERT , .Nm RB_AUGMENT +.Nm RB_UPDATE_AUGMENT .Nd "implementations of splay and rank-balanced (wavl) trees" .Sh SYNOPSIS .In sys/tree.h @@ -196,6 +197,8 @@ .Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "void" .Fn RB_AUGMENT NAME "struct TYPE *elm" +.Ft "void" +.Fn RB_UPDATE_AUGMENT NAME "struct TYPE *elm" .Sh DESCRIPTION These macros define data structures for different types of trees: splay trees and rank-balanced (wavl) trees. @@ -607,12 +610,25 @@ macro updates augmentation data of the element in the tree. By default, it has no effect. It is not meant to be invoked by the RB user. -If RB_AUGMENT is defined by the RB user, then when an element is -inserted or removed from the tree, it is invoked for every element in -the tree that is the root of an altered subtree, working from the -bottom of the tree up to the top. +If +.Fn RB_AUGMENT +is defined by the RB user, then when an element is inserted or removed +from the tree, it is invoked for every element in the tree that is the +root of an altered subtree, working from the bottom of the tree up to +the top. It is typically used to maintain some associative accumulation of tree elements, such as sums, minima, maxima, and the like. +.Pp +The +.Fn RB_UPDATE_AUGMENT +macro updates augmentation data of the element +.Fa elm +and its ancestors in the tree. +If RB_AUGMENT is defined by the RB user, then when an element in the +tree is changed, without changing the order of items in the tree, +invoking this function on that element restores consistency of the +augmentation state of the tree as if the element had been removed and +inserted again. .Sh EXAMPLES The following example demonstrates how to declare a rank-balanced tree holding integers. diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 5d215d0babe9..b66fa88829b2 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -371,6 +371,13 @@ struct { \ #define RB_AUGMENT(x) break #endif +#define RB_UPDATE_AUGMENT(elm, field) do { \ + __typeof(elm) tmp = (elm); \ + do { \ + RB_AUGMENT(tmp); \ + } while ((tmp = RB_PARENT(tmp, field)) != NULL); \ +} while (0) + #define RB_SWAP_CHILD(head, out, in, field) do { \ if (RB_PARENT(out, field) == NULL) \ RB_ROOT(head) = (in); \ @@ -678,11 +685,9 @@ name##_RB_REMOVE(struct name *head, struct type *elm) \ RB_SWAP_CHILD(head, old, elm, field); \ if (child != NULL) \ RB_SET_PARENT(child, parent, field); \ - if (parent != NULL) \ + if (parent != NULL) { \ name##_RB_REMOVE_COLOR(head, parent, child); \ - while (parent != NULL) { \ - RB_AUGMENT(parent); \ - parent = RB_PARENT(parent, field); \ + RB_UPDATE_AUGMENT(parent, field); \ } \ return (old); \ } @@ -714,10 +719,7 @@ name##_RB_INSERT(struct name *head, struct type *elm) \ else \ RB_RIGHT(parent, field) = elm; \ name##_RB_INSERT_COLOR(head, elm); \ - while (elm != NULL) { \ - RB_AUGMENT(elm); \ - elm = RB_PARENT(elm, field); \ - } \ + RB_UPDATE_AUGMENT(elm, field); \ return (NULL); \ }