From nobody Sun Jul 10 03:58:55 2022 X-Original-To: dev-commits-src-branches@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 415201CF96D6; Sun, 10 Jul 2022 03:58:56 +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 4LgYCz5hcvz40Yx; Sun, 10 Jul 2022 03:58:55 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1657425535; 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=a7UeHnVKIOkg72z4jKKzkAPfI7E3yadSRzdNWLMYNyo=; b=UDdjJZv4MJfy5NyCmlUFuG3sBXmwlivijVXyYCHgktWf2cLJ7/1nYsbmMIeZ7gD/MskriT uLLB6OQt4uqwUL8v1MOatt1gNsj3SQqQmtWhDB7C2+/GQFqU6HA/Gx5HWZtHbIytd/JMrc tSxhAaLgQISE8G0ED7yShyg1w9DXO03rGlo+VC7EpSm+uMXlQffKjF+QaF4vcJeB9I4DaQ 9QwzSZT7egDdUV9mDjnJrWHJaHR8o+ongXEV8V9qn1fpQvRJcmvjhggRYFxyCCmviffzEN Q0ljXlmgSZzR7OO41vSSfsmqKBR5QQg6Lys/LbqF0wcZfEctIE6Bfl3IoI+WIA== 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 4LgYCz3t8zz19rm; Sun, 10 Jul 2022 03:58:55 +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 26A3wtDS054393; Sun, 10 Jul 2022 03:58:55 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 26A3wt4m054392; Sun, 10 Jul 2022 03:58:55 GMT (envelope-from git) Date: Sun, 10 Jul 2022 03:58:55 GMT Message-Id: <202207100358.26A3wt4m054392@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: 689d65d736bb - stable/13 - tree.3: document RB_AUGMENT List-Id: Commits to the stable branches of the FreeBSD src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-branches List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-branches@freebsd.org X-BeenThere: dev-commits-src-branches@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: 689d65d736bbed1bf078b96cce5ccfc8b2dddae8 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1657425535; 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=a7UeHnVKIOkg72z4jKKzkAPfI7E3yadSRzdNWLMYNyo=; b=Qji69HsyBdw+qBtH+GnaeNS3kjxjEL+Vq0mMj3W+r4ZiA1DXCodNnAJ9yxhiaBAS0bQ15x YpIG/4beyMX90m0ilu/qnRabMzJjRlYVyf96ByrSrnCNYF6BXFgTpM4oCAiJTVyV1/R5A9 0rGSdUq5i0MEl9CXScLq+toX5SBBjVH6YkyEomwpsafrsdm6j0WmI0lz0oHUdlfzOAItYB oENTgh+VWxS3IQWDmG5kpqTrlh4+ERCw2qRczvrDn9tWhZEk+QrpMxdAsHhSd6DLNU5ZZM 3fwK/BdxsL3EzG/24Uk+ciwOrYGFXhwnzmoCNjyxtQS9uHmUMsNvBO9pSKLT5A== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1657425535; a=rsa-sha256; cv=none; b=Fn7X4F0Cj1CWpwQQoBdKLjtjPq59vj/kSE3YUlwsR9XDqs3mbKspPT3gzzJ3tFewK6Aq30 wg494MgOfxnvX/YJ6DZ80UtIjO9pjR5oWZQZVFkGHHgHX+V6J+dM4AE0GtZHvtAEMNgsH0 3In2TXikCf5hgfL1Eb10P/0ZXU4GDzj8nQup0L+TpLdQC3HbeN5PRbtTPxJcDJUm8hKUgS Wt2QAyTXxccnOGrekAWmb2JztyD4zKjFkDfAXHUjoYmNiElbKhiZi0HRJ6E2bLJIvyLZt4 MH8WVM6H6spNyxOrcr2zIO17FCUDgY/tW6ZQvr3nHFs6eBlg0Y7S9ogKFwCJlg== 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=689d65d736bbed1bf078b96cce5ccfc8b2dddae8 commit 689d65d736bbed1bf078b96cce5ccfc8b2dddae8 Author: Doug Moore AuthorDate: 2022-06-19 16:55:44 +0000 Commit: Doug Moore 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 @@ -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); }