diff options
Diffstat (limited to 'share/man/man3/tree.3')
-rw-r--r-- | share/man/man3/tree.3 | 453 |
1 files changed, 0 insertions, 453 deletions
diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 deleted file mode 100644 index 2d43ac1f09b04..0000000000000 --- a/share/man/man3/tree.3 +++ /dev/null @@ -1,453 +0,0 @@ -.\" $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 February 24, 2002 -.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_GENERATE, -.Nm RB_ENTRY , -.Nm RB_HEAD , -.Nm RB_INITIALIZER , -.Nm RB_ROOT , -.Nm RB_EMPTY , -.Nm RB_NEXT , -.Nm RB_MIN , -.Nm RB_MAX , -.Nm RB_FIND , -.Nm RB_LEFT , -.Nm RB_RIGHT , -.Nm RB_PARENT , -.Nm RB_FOREACH , -.Nm RB_INIT , -.Nm RB_INSERT , -.Nm RB_REMOVE -.Nd "implementations of splay and red-black trees" -.Sh SYNOPSIS -.Fd #include <sys/tree.h> -.Pp -.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" -.Pp -.Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP" -.Fn RB_GENERATE "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_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_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" -.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 defines 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 -.Li SPLAY_ENTRY , -or -.Li 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 either -.Li SPLAY_PROTOTYPE, -or -.Li RB_PROTOTYPE . -The function bodies are generated with either -.Li SPLAY_GENERATE, -or -.Li RB_GENERATE . -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 m operations -and n inserts on an initially empty tree as O((m + n)lg n). The -amortized cost for a sequence of m accesses to a splay tree is O(lg n); -.Pp -A splay tree is headed by a structure defined by the -.Fn SPLAY_HEAD -macro. -A -.Fa SPLAY_HEAD -structure is declared as follows: -.Bd -literal -offset indent -SPLAY_HEAD(HEADNAME, TYPE) 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 noded -with each other. The function takes two arguments of type -.Fa "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 -literal -offset indent -SPLAY_HEAD(HEADNAME, TYPE) head = 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 -literal -offset indent -SPLAY_FOREACH(np, NAME, head) -.Ed -.Pp -The -.Fn SPLAY_EMPTY -macro should be used to check whether a splay tree is empty. -.Pp -.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 -compact -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 O(lg n). -The maximum height of a red-black tree is 2lg (n+1). -.Pp -A red-black tree is headed by a structure defined by the -.Fn RB_HEAD -macro. -A -.Fa RB_HEAD -structure is declared as follows: -.Bd -literal -offset indent -RB_HEAD(HEADNAME, TYPE) 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 -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 -macro. It takes the same arguments as the -.Fn RB_PROTOTYPE -macro, but should be used only once. -.Pp -Finally, -the -.Fa CMP -argument is the name of a function used to compare tree noded -with each other. The function takes two arguments of type -.Fa "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 redblack tree can also be initialized statically by using the -.Fn RB_INITIALIZER -macro like this: -.Bd -literal -offset indent -RB_HEAD(HEADNAME, TYPE) head = 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 -macro 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 , -and -.Fn RB_NEXT -macros can be used to traverse the tree: -.Bd -literal -offset indent -for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np)) -.Ed -.Pp -Or, for simplicity, one can use the -.Fn RB_FOREACH -macro: -.Bd -literal -offset indent -RB_FOREACH(np, NAME, head) -.Ed -.Pp -The -.Fn RB_EMPTY -macro should be used to check whether a splay tree is empty. -.Pp -.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 free'd, 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 -.Va 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 -.Va NULL -to indicate an error. -.Sh AUTHORS -The author of the tree macros is Niels Provos. |