Date: Sun, 10 Jul 2022 03:58:55 GMT From: Doug Moore <dougm@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org Subject: git: 689d65d736bb - stable/13 - tree.3: document RB_AUGMENT Message-ID: <202207100358.26A3wt4m054392@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=689d65d736bbed1bf078b96cce5ccfc8b2dddae8 commit 689d65d736bbed1bf078b96cce5ccfc8b2dddae8 Author: Doug Moore <dougm@FreeBSD.org> AuthorDate: 2022-06-19 16:55:44 +0000 Commit: Doug Moore <dougm@FreeBSD.org> CommitDate: 2022-07-10 03:57: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 (cherry picked from commit a8380d272ae791e5de1bc56c761d15ba9b00899f) --- 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 <sys/tree.h> @@ -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); }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202207100358.26A3wt4m054392>