From nobody Sun Jun 19 16:58:26 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 618768546C0; Sun, 19 Jun 2022 16:58: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 4LQzW71mX6z3Myw; Sun, 19 Jun 2022 16:58:27 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1655657907; 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=1yUawX19Y3LWeqz9HHlGPRsOjsEvQy+XLxZk/TQ8nUo=; b=A00JXoh08JK18oY2T7nKBd1845ZLPbKylt7lbvbIZIY8M/cYxjDW2Umah9a0RT/oOLWY9H eykgStiTD1CELc4g4qnHuU434clfJ1qbOA4vHPpFBW/B2Uciot9lrQEjX/1RfRMXGYivBZ 3CxGsD36i5f7ikLKr1GQFG1hL6tr+Pt7yLEmu+UdqPKFmFFSuCTs/MmU9gWB4lP9wqIBZ7 K4k0p057Z7leRckApNGU613q2Kuo3Uoo0cIFZNV8aAskSD3Yf77BbXauKMYjpYOe7v48xA SoRn2YHbmrRgM1usnLFCf8GQZtk0EJv8L4EQyUJBE2IPqdGF4OwgYTka1zspig== 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 18E38491F; Sun, 19 Jun 2022 16:58: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 25JGwQfp094655; Sun, 19 Jun 2022 16:58:26 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 25JGwQnv094654; Sun, 19 Jun 2022 16:58:26 GMT (envelope-from git) Date: Sun, 19 Jun 2022 16:58:26 GMT Message-Id: <202206191658.25JGwQnv094654@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: a8380d272ae7 - main - tree.3: document RB_AUGMENT 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/main X-Git-Reftype: branch X-Git-Commit: a8380d272ae791e5de1bc56c761d15ba9b00899f Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1655657907; 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=1yUawX19Y3LWeqz9HHlGPRsOjsEvQy+XLxZk/TQ8nUo=; b=AMb/vcndY30wbGhhyhd5hUImDSAED8/AwNl1I/PYGuhP4DJEd47D+FOfM1qHWJlv6lZg8n GAQJIhFvqi7kFnD1PRbb+m6v/TGvwtuAdqz4Ie9Gk4zo7LOCXEDLr31UxvOOWHO5YaEz1i vCZ2O0mr6WcEcS/tV88CFTpD0E0FQhhsFce5vEktzDNVKDd1QyTzp0V4hzHDKvdxBXcsGm lugdtN3BFVHRAOS2K9V8IvO0Cvj5vLGQ6CmH6Rb3LHXmy7JbSmlwVqbwQP0c0feDXcbb2d ul62nO2vQfdQjcNw2yit0xI0cERTPx6MVJdMINT0nu9UrAORv2gHxBbP9jZUQQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1655657907; a=rsa-sha256; cv=none; b=UcaBB5zbz6zxpjz/7YA557fslH24YrZ0DDfft+qKZrqO3gklQCSCbx8toCQj/gV1cHpTq/ XVqr+ZOddzkYqUGzDlhPT7ga6Fjjs8fmj3sJpgxw+jPjl+QEmLbOY/0H58arUriTSVcpeD 4IQwToEuE4gtuaYOVW7kjCuUSnltvy2RWDZyj4n6cB/oeVmhKpja4sOQx4KHLySPgK9JmE BpqnsJuLdYtsUzFPVImCbCyl3jzjGuDzMWZKhz6zes3S3IK5B2ZHAleagHC6ddWs3TSHQz N66bmRx23Uy3rbb+70E2+BU1Px8H9up+d4hSvbf0GRyPT49EtSx/HAH/JFLeCw== 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=a8380d272ae791e5de1bc56c761d15ba9b00899f commit a8380d272ae791e5de1bc56c761d15ba9b00899f Author: Doug Moore AuthorDate: 2022-06-19 16:55:44 +0000 Commit: Doug Moore CommitDate: 2022-06-19 16:55:44 +0000 tree.3: document RB_AUGMENT Document the RB_AUGMENT macro, and provide an example of its use. Reviewed by: alc, kib MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D35518 --- share/man/man3/Makefile | 3 ++- share/man/man3/tree.3 | 35 +++++++++++++++++++++++++++++++++-- 2 files changed, 35 insertions(+), 3 deletions(-) diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile index 33101026c01a..fa4f751ce553 100644 --- a/share/man/man3/Makefile +++ b/share/man/man3/Makefile @@ -319,7 +319,8 @@ MLINKS+= timeradd.3 timerclear.3 \ timeradd.3 timespecclear.3 \ timeradd.3 timespecisset.3 \ timeradd.3 timespeccmp.3 -MLINKS+= tree.3 RB_EMPTY.3 \ +MLINKS+= tree.3 RB_AUGMENT.3 \ + tree.3 RB_EMPTY.3 \ tree.3 RB_ENTRY.3 \ tree.3 RB_FIND.3 \ tree.3 RB_FOREACH.3 \ diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 index a29f06d3c21e..c68c71fff85b 100644 --- a/share/man/man3/tree.3 +++ b/share/man/man3/tree.3 @@ -98,7 +98,8 @@ .Nm RB_INIT , .Nm RB_INSERT , .Nm RB_REMOVE , -.Nm RB_REINSERT +.Nm RB_REINSERT , +.Nm RB_AUGMENT .Nd "implementations of splay and rank-balanced (wavl) trees" .Sh SYNOPSIS .In sys/tree.h @@ -193,6 +194,8 @@ .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm" +.Ft "void" +.Fn RB_AUGMENT NAME "struct TYPE *elm" .Sh DESCRIPTION These macros define data structures for different types of trees: splay trees and rank-balanced (wavl) trees. @@ -581,11 +584,27 @@ is modified in a way that affects comparison, such as by modifying a node's key. This is a lower overhead alternative to removing the element and reinserting it again. +.Pp +The +.Fn RB_AUGMENT +macro updates augmentation data of the element +.Fa elm +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. +It is typically used to maintain some associative accumulation of tree +elements, such as sums, minima, maxima, and the like. .Sh EXAMPLES The following example demonstrates how to declare a rank-balanced tree holding integers. Values are inserted into it and the contents of the tree are printed in order. +To maintain the sum of the values in the tree, each element maintains +the sum of its value and the sums from its left and right subtrees. Lastly, the internal structure of the tree is printed. .Bd -literal -offset 3n #include @@ -595,7 +614,7 @@ Lastly, the internal structure of the tree is printed. struct node { RB_ENTRY(node) entry; - int i; + int i, sum; }; int @@ -604,6 +623,17 @@ intcmp(struct node *e1, struct node *e2) return (e1->i < e2->i ? -1 : e1->i > e2->i); } +int +sumaug(struct node *e) +{ + e->sum = e->i; + if (RB_LEFT(e, entry) != NULL) + e->sum += RB_LEFT(e, entry)->sum; + if (RB_RIGHT(e, entry) != NULL) + e->sum += RB_RIGHT(e, entry)->sum; +} +#define RB_AUGMENT(entry) sumaug(entry) + RB_HEAD(inttree, node) head = RB_INITIALIZER(&head); RB_GENERATE(inttree, node, entry, intcmp) @@ -651,6 +681,7 @@ main(void) printf("%d\en", n->i); } print_tree(RB_ROOT(&head)); + printf("Sum of values = %d\n", RB_ROOT(&head)->sum); printf("\en"); return (0); }