diff options
Diffstat (limited to 'static/freebsd/man3/tree.3')
| -rw-r--r-- | static/freebsd/man3/tree.3 | 816 |
1 files changed, 816 insertions, 0 deletions
diff --git a/static/freebsd/man3/tree.3 b/static/freebsd/man3/tree.3 new file mode 100644 index 00000000..83d005a5 --- /dev/null +++ b/static/freebsd/man3/tree.3 @@ -0,0 +1,816 @@ +.\" $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $ +.\" +.\" Copyright 2002 Niels Provos <provos@citi.umich.edu> +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by Niels Provos. +.\" 4. The name of the author may not be used to endorse or promote products +.\" derived from this software without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR +.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +.\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, +.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF +.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +.\" +.Dd August 2, 2024 +.Dt TREE 3 +.Os +.Sh NAME +.Nm SPLAY_PROTOTYPE , +.Nm SPLAY_GENERATE , +.Nm SPLAY_ENTRY , +.Nm SPLAY_HEAD , +.Nm SPLAY_INITIALIZER , +.Nm SPLAY_ROOT , +.Nm SPLAY_EMPTY , +.Nm SPLAY_NEXT , +.Nm SPLAY_MIN , +.Nm SPLAY_MAX , +.Nm SPLAY_FIND , +.Nm SPLAY_LEFT , +.Nm SPLAY_RIGHT , +.Nm SPLAY_FOREACH , +.Nm SPLAY_INIT , +.Nm SPLAY_INSERT , +.Nm SPLAY_REMOVE , +.Nm RB_PROTOTYPE , +.Nm RB_PROTOTYPE_STATIC , +.Nm RB_PROTOTYPE_INSERT , +.Nm RB_PROTOTYPE_INSERT_COLOR , +.Nm RB_PROTOTYPE_REMOVE , +.Nm RB_PROTOTYPE_REMOVE_COLOR , +.Nm RB_PROTOTYPE_FIND , +.Nm RB_PROTOTYPE_NFIND , +.Nm RB_PROTOTYPE_NEXT , +.Nm RB_PROTOTYPE_PREV , +.Nm RB_PROTOTYPE_MINMAX , +.Nm RB_PROTOTYPE_REINSERT , +.Nm RB_GENERATE , +.Nm RB_GENERATE_STATIC , +.Nm RB_GENERATE_INSERT , +.Nm RB_GENERATE_INSERT_COLOR , +.Nm RB_GENERATE_REMOVE , +.Nm RB_GENERATE_REMOVE_COLOR , +.Nm RB_GENERATE_FIND , +.Nm RB_GENERATE_NFIND , +.Nm RB_GENERATE_NEXT , +.Nm RB_GENERATE_PREV , +.Nm RB_GENERATE_MINMAX , +.Nm RB_GENERATE_REINSERT , +.Nm RB_ENTRY , +.Nm RB_HEAD , +.Nm RB_INITIALIZER , +.Nm RB_ROOT , +.Nm RB_EMPTY , +.Nm RB_NEXT , +.Nm RB_PREV , +.Nm RB_MIN , +.Nm RB_MAX , +.Nm RB_FIND , +.Nm RB_NFIND , +.Nm RB_LEFT , +.Nm RB_RIGHT , +.Nm RB_PARENT , +.Nm RB_FOREACH , +.Nm RB_FOREACH_FROM , +.Nm RB_FOREACH_SAFE , +.Nm RB_FOREACH_REVERSE , +.Nm RB_FOREACH_REVERSE_FROM , +.Nm RB_FOREACH_REVERSE_SAFE , +.Nm RB_INIT , +.Nm RB_INSERT , +.Nm RB_INSERT_NEXT , +.Nm RB_INSERT_PREV , +.Nm RB_REMOVE , +.Nm RB_REINSERT , +.Nm RB_AUGMENT +.Nm RB_AUGMENT_CHECK, +.Nm RB_UPDATE_AUGMENT +.Nd "implementations of splay and rank-balanced (wavl) trees" +.Sh SYNOPSIS +.In sys/tree.h +.Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP +.Fn SPLAY_GENERATE NAME TYPE FIELD CMP +.Fn SPLAY_ENTRY TYPE +.Fn SPLAY_HEAD HEADNAME TYPE +.Ft "struct TYPE *" +.Fn SPLAY_INITIALIZER "SPLAY_HEAD *head" +.Fn SPLAY_ROOT "SPLAY_HEAD *head" +.Ft bool +.Fn SPLAY_EMPTY "SPLAY_HEAD *head" +.Ft "struct TYPE *" +.Fn SPLAY_NEXT NAME "SPLAY_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn SPLAY_MIN NAME "SPLAY_HEAD *head" +.Ft "struct TYPE *" +.Fn SPLAY_MAX NAME "SPLAY_HEAD *head" +.Ft "struct TYPE *" +.Fn SPLAY_FIND NAME "SPLAY_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME" +.Ft "struct TYPE *" +.Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME" +.Fn SPLAY_FOREACH VARNAME NAME "SPLAY_HEAD *head" +.Ft void +.Fn SPLAY_INIT "SPLAY_HEAD *head" +.Ft "struct TYPE *" +.Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm" +.Fn RB_PROTOTYPE NAME TYPE FIELD CMP +.Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP +.Fn RB_PROTOTYPE_INSERT NAME TYPE ATTR +.Fn RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR +.Fn RB_PROTOTYPE_REMOVE NAME TYPE ATTR +.Fn RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR +.Fn RB_PROTOTYPE_FIND NAME TYPE ATTR +.Fn RB_PROTOTYPE_NFIND NAME TYPE ATTR +.Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR +.Fn RB_PROTOTYPE_PREV NAME TYPE ATTR +.Fn RB_PROTOTYPE_MINMAX NAME TYPE ATTR +.Fn RB_PROTOTYPE_REINSERT NAME TYPE ATTR +.Fn RB_GENERATE NAME TYPE FIELD CMP +.Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP +.Fn RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR +.Fn RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR +.Fn RB_GENERATE_REMOVE NAME TYPE FIELD ATTR +.Fn RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR +.Fn RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR +.Fn RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR +.Fn RB_GENERATE_NEXT NAME TYPE FIELD ATTR +.Fn RB_GENERATE_PREV NAME TYPE FIELD ATTR +.Fn RB_GENERATE_MINMAX NAME TYPE FIELD ATTR +.Fn RB_GENERATE_REINSERT NAME TYPE FIELD CMP ATTR +.Fn RB_ENTRY TYPE +.Fn RB_HEAD HEADNAME TYPE +.Fn RB_INITIALIZER "RB_HEAD *head" +.Ft "struct TYPE *" +.Fn RB_ROOT "RB_HEAD *head" +.Ft "bool" +.Fn RB_EMPTY "RB_HEAD *head" +.Ft "struct TYPE *" +.Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_MIN NAME "RB_HEAD *head" +.Ft "struct TYPE *" +.Fn RB_MAX NAME "RB_HEAD *head" +.Ft "struct TYPE *" +.Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME" +.Ft "struct TYPE *" +.Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME" +.Ft "struct TYPE *" +.Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME" +.Fn RB_FOREACH VARNAME NAME "RB_HEAD *head" +.Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME" +.Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" +.Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head" +.Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME" +.Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" +.Ft void +.Fn RB_INIT "RB_HEAD *head" +.Ft "struct TYPE *" +.Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_INSERT_NEXT NAME "RB_HEAD *head" "struct TYPE *elm" "struct TYPE *next" +.Ft "struct TYPE *" +.Fn RB_INSERT_PREV NAME "RB_HEAD *head" "struct TYPE *elm" "struct TYPE *prev" +.Ft "struct TYPE *" +.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" +.Ft "bool" +.Fn RB_AUGMENT_CHECK 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. +.Pp +In the macro definitions, +.Fa TYPE +is the name tag of a user defined structure that must contain a field of type +.Vt SPLAY_ENTRY , +or +.Vt RB_ENTRY , +named +.Fa ENTRYNAME . +The argument +.Fa HEADNAME +is the name tag of a user defined structure that must be declared +using the macros +.Fn SPLAY_HEAD , +or +.Fn RB_HEAD . +The argument +.Fa NAME +has to be a unique name prefix for every tree that is defined. +.Pp +The function prototypes are declared with +.Fn SPLAY_PROTOTYPE , +.Fn RB_PROTOTYPE , +or +.Fn RB_PROTOTYPE_STATIC . +The function bodies are generated with +.Fn SPLAY_GENERATE , +.Fn RB_GENERATE , +or +.Fn RB_GENERATE_STATIC . +See the examples below for further explanation of how these macros are used. +.Sh SPLAY TREES +A splay tree is a self-organizing data structure. +Every operation on the tree causes a splay to happen. +The splay moves the requested +node to the root of the tree and partly rebalances it. +.Pp +This has the benefit that request locality causes faster lookups as +the requested nodes move to the top of the tree. +On the other hand, every lookup causes memory writes. +.Pp +The Balance Theorem bounds the total access time for +.Ar m +operations and +.Ar n +inserts on an initially empty tree as +.Fn O "\*[lp]m + n\*[rp]lg n" . +The +amortized cost for a sequence of +.Ar m +accesses to a splay tree is +.Fn O "lg n" . +.Pp +A splay tree is headed by a structure defined by the +.Fn SPLAY_HEAD +macro. +A +structure is declared as follows: +.Bd -ragged -offset indent +.Fn SPLAY_HEAD HEADNAME TYPE +.Va head ; +.Ed +.Pp +where +.Fa HEADNAME +is the name of the structure to be defined, and struct +.Fa TYPE +is the type of the elements to be inserted into the tree. +.Pp +The +.Fn SPLAY_ENTRY +macro declares a structure that allows elements to be connected in the tree. +.Pp +In order to use the functions that manipulate the tree structure, +their prototypes need to be declared with the +.Fn SPLAY_PROTOTYPE +macro, +where +.Fa NAME +is a unique identifier for this particular tree. +The +.Fa TYPE +argument is the type of the structure that is being managed +by the tree. +The +.Fa FIELD +argument is the name of the element defined by +.Fn SPLAY_ENTRY . +.Pp +The function bodies are generated with the +.Fn SPLAY_GENERATE +macro. +It takes the same arguments as the +.Fn SPLAY_PROTOTYPE +macro, but should be used only once. +.Pp +Finally, +the +.Fa CMP +argument is the name of a function used to compare tree nodes +with each other. +The function takes two arguments of type +.Vt "struct TYPE *" . +If the first argument is smaller than the second, the function returns a +value smaller than zero. +If they are equal, the function returns zero. +Otherwise, it should return a value greater than zero. +The compare +function defines the order of the tree elements. +.Pp +The +.Fn SPLAY_INIT +macro initializes the tree referenced by +.Fa head . +.Pp +The splay tree can also be initialized statically by using the +.Fn SPLAY_INITIALIZER +macro like this: +.Bd -ragged -offset indent +.Fn SPLAY_HEAD HEADNAME TYPE +.Va head += +.Fn SPLAY_INITIALIZER &head ; +.Ed +.Pp +The +.Fn SPLAY_INSERT +macro inserts the new element +.Fa elm +into the tree. +.Pp +The +.Fn SPLAY_REMOVE +macro removes the element +.Fa elm +from the tree pointed by +.Fa head . +.Pp +The +.Fn SPLAY_FIND +macro can be used to find a particular element in the tree. +.Bd -literal -offset indent +struct TYPE find, *res; +find.key = 30; +res = SPLAY_FIND(NAME, head, &find); +.Ed +.Pp +The +.Fn SPLAY_ROOT , +.Fn SPLAY_MIN , +.Fn SPLAY_MAX , +and +.Fn SPLAY_NEXT +macros can be used to traverse the tree: +.Bd -literal -offset indent +for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np)) +.Ed +.Pp +Or, for simplicity, one can use the +.Fn SPLAY_FOREACH +macro: +.Bd -ragged -offset indent +.Fn SPLAY_FOREACH np NAME head +.Ed +.Pp +The +.Fn SPLAY_EMPTY +macro should be used to check whether a splay tree is empty. +.Sh RANK-BALANCED TREES +Rank-balanced (RB) trees are a framework for defining height-balanced +binary search trees, including AVL and red-black trees. +Each tree node has an associated rank. +Balance conditions are expressed by conditions on the differences in +rank between any node and its children. +Rank differences are stored in each tree node. +.Pp +The balance conditions implemented by the RB macros lead to weak AVL +(wavl) trees, which combine the best aspects of AVL and red-black +trees. +Wavl trees rebalance after an insertion in the same way AVL trees do, +with the same worst-case time as red-black trees offer, and with +better balance in the resulting tree. +Wavl trees rebalance after a removal in a way that requires less +restructuring, in the worst case, than either AVL or red-black trees +do. +Removals can lead to a tree almost as unbalanced as a red-black +tree; insertions lead to a tree becoming as balanced as an AVL tree. +.Pp +A rank-balanced tree is headed by a structure defined by the +.Fn RB_HEAD +macro. +A +structure is declared as follows: +.Bd -ragged -offset indent +.Fn RB_HEAD HEADNAME TYPE +.Va head ; +.Ed +.Pp +where +.Fa HEADNAME +is the name of the structure to be defined, and struct +.Fa TYPE +is the type of the elements to be inserted into the tree. +.Pp +The +.Fn RB_ENTRY +macro declares a structure that allows elements to be connected in the tree. +.Pp +In order to use the functions that manipulate the tree structure, +their prototypes need to be declared with the +.Fn RB_PROTOTYPE +or +.Fn RB_PROTOTYPE_STATIC +macro, +where +.Fa NAME +is a unique identifier for this particular tree. +The +.Fa TYPE +argument is the type of the structure that is being managed +by the tree. +The +.Fa FIELD +argument is the name of the element defined by +.Fn RB_ENTRY . +Individual prototypes can be declared with +.Fn RB_PROTOTYPE_INSERT , +.Fn RB_PROTOTYPE_INSERT_COLOR , +.Fn RB_PROTOTYPE_REMOVE , +.Fn RB_PROTOTYPE_REMOVE_COLOR , +.Fn RB_PROTOTYPE_FIND , +.Fn RB_PROTOTYPE_NFIND , +.Fn RB_PROTOTYPE_NEXT , +.Fn RB_PROTOTYPE_PREV , +.Fn RB_PROTOTYPE_MINMAX , +and +.Fn RB_PROTOTYPE_REINSERT +in case not all functions are required. +The individual prototype macros expect +.Fa NAME , +.Fa TYPE , +and +.Fa ATTR +arguments. +The +.Fa ATTR +argument must be empty for global functions or +.Fa static +for static functions. +.Pp +The function bodies are generated with the +.Fn RB_GENERATE +or +.Fn RB_GENERATE_STATIC +macro. +These macros take the same arguments as the +.Fn RB_PROTOTYPE +and +.Fn RB_PROTOTYPE_STATIC +macros, but should be used only once. +As an alternative individual function bodies are generated with the +.Fn RB_GENERATE_INSERT , +.Fn RB_GENERATE_INSERT_COLOR , +.Fn RB_GENERATE_REMOVE , +.Fn RB_GENERATE_REMOVE_COLOR , +.Fn RB_GENERATE_FIND , +.Fn RB_GENERATE_NFIND , +.Fn RB_GENERATE_NEXT , +.Fn RB_GENERATE_PREV , +.Fn RB_GENERATE_MINMAX , +and +.Fn RB_GENERATE_REINSERT +macros. +.Pp +Finally, +the +.Fa CMP +argument is the name of a function used to compare tree nodes +with each other. +The function takes two arguments of type +.Vt "struct TYPE *" . +If the first argument is smaller than the second, the function returns a +value smaller than zero. +If they are equal, the function returns zero. +Otherwise, it should return a value greater than zero. +The compare +function defines the order of the tree elements. +.Pp +The +.Fn RB_INIT +macro initializes the tree referenced by +.Fa head . +.Pp +The rank-balanced tree can also be initialized statically by using the +.Fn RB_INITIALIZER +macro like this: +.Bd -ragged -offset indent +.Fn RB_HEAD HEADNAME TYPE +.Va head += +.Fn RB_INITIALIZER &head ; +.Ed +.Pp +The +.Fn RB_INSERT +macro inserts the new element +.Fa elm +into the tree. +.Pp +The +.Fn RB_INSERT_NEXT +macro inserts the new element +.Fa elm +into the tree immediately after a given element. +.Pp +The +.Fn RB_INSERT_PREV +macro inserts the new element +.Fa elm +into the tree immediately before a given element. +.Pp +The +.Fn RB_REMOVE +macro removes the element +.Fa elm +from the tree pointed by +.Fa head . +.Pp +The +.Fn RB_FIND +and +.Fn RB_NFIND +macros can be used to find a particular element in the tree. +.Pp +The +.Fn RB_FIND +macro returns the element in the tree equal to the provided +key, or +.Dv NULL +if there is no such element. +.Pp +The +.Fn RB_NFIND +macro returns the least element greater than or equal to the provided +key, or +.Dv NULL +if there is no such element. +.Bd -literal -offset indent +struct TYPE find, *res, *resn; +find.key = 30; +res = RB_FIND(NAME, head, &find); +resn = RB_NFIND(NAME, head, &find); +.Ed +.Pp +The +.Fn RB_ROOT , +.Fn RB_MIN , +.Fn RB_MAX , +.Fn RB_NEXT , +and +.Fn RB_PREV +macros can be used to traverse the tree: +.Pp +.Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))" +.Pp +Or, for simplicity, one can use the +.Fn RB_FOREACH +or +.Fn RB_FOREACH_REVERSE +macro: +.Bd -ragged -offset indent +.Fn RB_FOREACH np NAME head +.Ed +.Pp +The macros +.Fn RB_FOREACH_SAFE +and +.Fn RB_FOREACH_REVERSE_SAFE +traverse the tree referenced by head +in a forward or reverse direction respectively, +assigning each element in turn to np. +However, unlike their unsafe counterparts, +they permit both the removal of np +as well as freeing it from within the loop safely +without interfering with the traversal. +.Pp +Both +.Fn RB_FOREACH_FROM +and +.Fn RB_FOREACH_REVERSE_FROM +may be used to continue an interrupted traversal +in a forward or reverse direction respectively. +The head pointer is not required. +The pointer to the node from where to resume the traversal +should be passed as their last argument, +and will be overwritten to provide safe traversal. +.Pp +The +.Fn RB_EMPTY +macro should be used to check whether a rank-balanced tree is empty. +.Pp +The +.Fn RB_REINSERT +macro updates the position of the element +.Fa elm +in the tree. +This must be called if a member of a +.Nm tree +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 +.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_AUGMENT_CHECK +macro updates augmentation data of the element +.Fa elm +in the tree. +By default, it does nothing and returns false. +If +.Fn RB_AUGMENT_CHECK +is defined, 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 toward the +top, until it returns false to indicate that it did not change the +element and so working further up the tree would change nothing. +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 +.Fn 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. +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 +#define RB_AUGMENT(entry) sumaug(entry) + +#include <sys/tree.h> +#include <err.h> +#include <stdio.h> +#include <stdlib.h> + +struct node { + RB_ENTRY(node) entry; + int i, sum; +}; + +int +intcmp(struct node *e1, struct node *e2) +{ + return (e1->i < e2->i ? -1 : e1->i > e2->i); +} + +void +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; +} + +RB_HEAD(inttree, node) head = RB_INITIALIZER(&head); +RB_GENERATE(inttree, node, entry, intcmp) + +int testdata[] = { + 20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18, + 7, 11, 14 +}; + +void +print_tree(struct node *n) +{ + struct node *left, *right; + + if (n == NULL) { + printf("nil"); + return; + } + left = RB_LEFT(n, entry); + right = RB_RIGHT(n, entry); + if (left == NULL && right == NULL) + printf("%d", n->i); + else { + printf("%d(", n->i); + print_tree(left); + printf(","); + print_tree(right); + printf(")"); + } +} + +int +main(void) +{ + int i; + struct node *n; + + for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) { + if ((n = malloc(sizeof(struct node))) == NULL) + err(1, NULL); + n->i = testdata[i]; + RB_INSERT(inttree, &head, n); + } + + RB_FOREACH(n, inttree, &head) { + printf("%d\en", n->i); + } + print_tree(RB_ROOT(&head)); + printf("\enSum of values = %d\en", RB_ROOT(&head)->sum); + return (0); +} +.Ed +.Sh NOTES +Trying to free a tree in the following way is a common error: +.Bd -literal -offset indent +SPLAY_FOREACH(var, NAME, head) { + SPLAY_REMOVE(NAME, head, var); + free(var); +} +free(head); +.Ed +.Pp +Since +.Va var +is freed, the +.Fn FOREACH +macro refers to a pointer that may have been reallocated already. +Proper code needs a second variable. +.Bd -literal -offset indent +for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) { + nxt = SPLAY_NEXT(NAME, head, var); + SPLAY_REMOVE(NAME, head, var); + free(var); +} +.Ed +.Pp +Both +.Fn RB_INSERT +and +.Fn SPLAY_INSERT +return +.Dv NULL +if the element was inserted in the tree successfully, otherwise they +return a pointer to the element with the colliding key. +.Pp +Accordingly, +.Fn RB_REMOVE +and +.Fn SPLAY_REMOVE +return the pointer to the removed element otherwise they return +.Dv NULL +to indicate an error. +.Sh SEE ALSO +.Xr arb 3 , +.Xr queue 3 +.Rs +.%A "Bernhard Haeupler" +.%A "Siddhartha Sen" +.%A "Robert E. Tarjan" +.%T "Rank-Balanced Trees" +.%U "http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf" +.%J "ACM Transactions on Algorithms" +.%V "11" +.%N "4" +.%D "June 2015" +.Re +.Sh HISTORY +The tree macros first appeared in +.Fx 4.6 . +.Sh AUTHORS +The author of the tree macros is +.An Niels Provos . |