From nobody Tue Aug 2 16:23:24 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 4Ly0fN6Zy3z4XXjN; Tue, 2 Aug 2022 16:23:24 +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 4Ly0fN5lc7z3pF8; Tue, 2 Aug 2022 16:23:24 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1659457404; 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=zKFuu3b2YjQOxR4RxZL3LiQbqCPBORuYEtNxPdKJQJ0=; b=rXLQrQEThdksA5PODRaTRF5t3BhygrA2jprgVOGy7J/it7epmMEOUPwWI6YRah3dAOl8qQ n7lWwgynIV0wOJAAiTAjqkrnhihCXOVgmSsZJajuhTl5lc15aoE9kSorVAsRQ2ZS+Dzt28 Zoz7XwJccBpeuyxDlu1HKmxjtrUudI+bK3x1A72ApqMnvVFKe+sqJTGhZDZZvalmapP44V 09nvfPoZq2k+PAJspC5ypfo3uldfSiPaup8y0t18pFAkY+5PH0RluBIVZYOwMqTj9zKuSe IU+kptzM4LjZxCPpZWnrHSQtwBimqIgiqwtTKVnk09ziMnh/7EUnvHV6o0t/eg== 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 4Ly0fN4SRvzKCQ; Tue, 2 Aug 2022 16:23:24 +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 272GNOf0051246; Tue, 2 Aug 2022 16:23:24 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 272GNO67051245; Tue, 2 Aug 2022 16:23:24 GMT (envelope-from git) Date: Tue, 2 Aug 2022 16:23:24 GMT Message-Id: <202208021623.272GNO67051245@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: 35557a0d9169 - main - rb_tree: update augmentation after element change 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: 35557a0d9169172b90df903b0daf389c2839b749 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1659457404; 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=zKFuu3b2YjQOxR4RxZL3LiQbqCPBORuYEtNxPdKJQJ0=; b=Hn03vso8ZMccjeeW8pAk5e4dPBSmIWILQvmmRItfn2CTnXbJbVg4tG7MV1IEQgry0WtD9u sv/PhDkYEOXcFh3qzoQjYricT2rnXnQUx1eRCEy53p2WWlikQNO7KSg9kqbNPTfWqjD5N+ wmWyjrjdKFqwrjmGfmYNMB2dzkxO1yfO4NahAMbt2vlXDw1He6blVFskGDJTSIxAN5HVCL fxAJJAVxQCmvYnA961hqHkzzaYaS0H7FbatEe0aewjT6AhN6h9vMkB1gXoMPR1+tXS/WPt zt0q246QS3977Z+WVikcVZ5p3A5CTKodMZWTMRWUYGkcQ0ZaYMS2i5GnMzJ+1g== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1659457404; a=rsa-sha256; cv=none; b=Qm8le856VnhnruhRMV7m8BnZc/MiQdfXo6sgCQSch3/fhTecRJWUnKqJaUWlDo/SaCO1xH jfmhQI7G3/dDCHf6yi9MzHZOfKY1LWX9v5lFgEf8lv9ggGw70gRNd6kN4LHWLYq/DitDlI 2FmiuWAP1XixogXwhgw0heBA9COqoIvqRlVxrMIwAA3/p5wZuGvsLfGNwkebiLRjpbu/bc +eZaAkUgtquBoABc++n0VU02/r/8Y3srwBANh3xT6g0YjU7kuMp5AFOEXdumi/eOZiNI20 YlSL1TVVADtwdG4zygObH61L+oC0SUecbvdrPx4Zflp+hKuE3d+7xuCbIhBqzQ== 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=35557a0d9169172b90df903b0daf389c2839b749 commit 35557a0d9169172b90df903b0daf389c2839b749 Author: Doug Moore AuthorDate: 2022-08-02 16:19:46 +0000 Commit: Doug Moore CommitDate: 2022-08-02 16:23:12 +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 --- 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 c68c71fff85b..cbc741fe642d 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. @@ -592,12 +595,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 1529b07dfcdb..c0d21b5f8b73 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); \ }