diff options
Diffstat (limited to 'share/man/man3/tree.3')
| -rw-r--r-- | share/man/man3/tree.3 | 535 |
1 files changed, 535 insertions, 0 deletions
diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 new file mode 100644 index 0000000..2e9c63c --- /dev/null +++ b/share/man/man3/tree.3 @@ -0,0 +1,535 @@ +.\" $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. +.\" +.\" $FreeBSD$ +.\" +.Dd November 10, 2013 +.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_GENERATE , +.Nm RB_GENERATE_STATIC , +.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_REMOVE +.Nd "implementations of splay and red-black 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_GENERATE NAME TYPE FIELD CMP +.Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP +.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_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm" +.Sh DESCRIPTION +These macros define data structures for different types of trees: +splay trees and red-black 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 RED-BLACK TREES +A red-black tree is a binary search tree with the node color as an +extra attribute. +It fulfills a set of conditions: +.Bl -enum -offset indent +.It +Every search path from the root to a leaf consists of the same number of +black nodes. +.It +Each red node (except for the root) has a black parent. +.It +Each leaf node is black. +.El +.Pp +Every operation on a red-black tree is bounded as +.Fn O "lg n" . +The maximum height of a red-black tree is +.Fn 2lg "n + 1" . +.Pp +A red-black 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 . +.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. +.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 red-black 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_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. +.Bd -literal -offset indent +struct TYPE find, *res; +find.key = 30; +res = RB_FIND(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 red-black tree is empty. +.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 queue 3 +.Sh AUTHORS +The author of the tree macros is +.An Niels Provos . |
