Module Name: src
Committed By: christos
Date: Fri Mar 29 21:16:31 UTC 2013
Modified Files:
src/share/man/man3: tree.3
Log Message:
sync with OpenBSD.
To generate a diff of this commit:
cvs rdiff -u -r1.8 -r1.9 src/share/man/man3/tree.3
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/share/man/man3/tree.3
diff -u src/share/man/man3/tree.3:1.8 src/share/man/man3/tree.3:1.9
--- src/share/man/man3/tree.3:1.8 Fri Mar 29 16:58:58 2013
+++ src/share/man/man3/tree.3 Fri Mar 29 17:16:31 2013
@@ -1,5 +1,5 @@
-.\" $NetBSD: tree.3,v 1.8 2013/03/29 20:58:58 pgoyette Exp $
-.\" $OpenBSD: tree.3,v 1.9 2003/05/20 09:13:38 jmc Exp $
+.\" $NetBSD: tree.3,v 1.9 2013/03/29 21:16:31 christos Exp $
+.\" $OpenBSD: tree.3,v 1.23 2011/07/09 08:43:01 jmc Exp $
.\"/*
.\" * Copyright 2002 Niels Provos <[email protected]>
.\" * All rights reserved.
@@ -12,11 +12,6 @@
.\" * 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
@@ -29,7 +24,7 @@
.\" * (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 May 5, 2010
+.Dd July 9 2011
.Dt TREE 3
.Os
.Sh NAME
@@ -51,20 +46,27 @@
.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_SAFE ,
+.Nm RB_FOREACH_REVERSE ,
+.Nm RB_FOREACH_REVERSE_SAFE ,
.Nm RB_INIT ,
.Nm RB_INSERT ,
.Nm RB_REMOVE
@@ -78,7 +80,7 @@
.Ft "struct TYPE *"
.Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
.Fn SPLAY_ROOT "SPLAY_HEAD *head"
-.Ft "bool"
+.Ft "int"
.Fn SPLAY_EMPTY "SPLAY_HEAD *head"
.Ft "struct TYPE *"
.Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
@@ -101,29 +103,38 @@
.Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
.Pp
.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"
+.Ft "int"
.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_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
+.Fn RB_FOREACH_REVERSE "VARNAME" "NAME" "RB_HEAD *head"
+.Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
.Ft void
.Fn RB_INIT "RB_HEAD *head"
.Ft "struct TYPE *"
@@ -142,12 +153,12 @@ 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 ,
+is the name tag of a user defined structure that must contain a field named
+.Fa FIELD ,
+of type
+.Li SPLAY_ENTRY
or
-.Li RB_ENTRY ,
-named
-.Fa ENTRYNAME .
+.Li RB_ENTRY .
The argument
.Fa HEADNAME
is the name tag of a user defined structure that must be declared
@@ -159,14 +170,16 @@ 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
+The function prototypes are declared with
+.Li SPLAY_PROTOTYPE ,
+.Li RB_PROTOTYPE ,
or
-.Li RB_PROTOTYPE .
-The function bodies are generated with either
-.Li SPLAY_GENERATE
+.Li RB_PROTOTYPE_STATIC .
+The function bodies are generated with
+.Li SPLAY_GENERATE ,
+.Li RB_GENERATE ,
or
-.Li RB_GENERATE .
+.Li 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.
@@ -228,7 +241,11 @@ macro, but should be used only once.
Finally,
the
.Fa CMP
+<<<<<<< tree.3
+argument is the name of a function used to compare trees' nodes
+=======
argument is the name of a function used to compare tree nodes
+>>>>>>> 1.8
with each other.
The function takes two arguments of type
.Fa "struct TYPE *" .
@@ -255,6 +272,11 @@ The
macro inserts the new element
.Fa elm
into the tree.
+Upon success,
+.Va NULL
+is returned.
+If a matching element already exists in the tree, the insertion is
+aborted, and a pointer to the existing element is returned.
.Pp
The
.Fn SPLAY_REMOVE
@@ -262,6 +284,11 @@ macro removes the element
.Fa elm
from the tree pointed by
.Fa head .
+Upon success, a pointer to the removed element is returned.
+.Va NULL
+is returned if
+.Fa elm
+is not present in the tree.
.Pp
The
.Fn SPLAY_FIND
@@ -269,7 +296,7 @@ macro can be used to find a particular e
.Bd -literal -offset indent
struct TYPE find, *res;
find.key = 30;
-res = SPLAY_FIND(NAME, head, \*[Am]find);
+res = SPLAY_FIND(NAME, \*[Am]head, \*[Am]find);
.Ed
.Pp
The
@@ -287,7 +314,7 @@ Or, for simplicity, one can use the
.Fn SPLAY_FOREACH
macro:
.Bd -literal -offset indent
-SPLAY_FOREACH(np, NAME, head)
+SPLAY_FOREACH(np, NAME, &head)
.Ed
.Pp
The
@@ -297,6 +324,7 @@ macro should be used to check whether a
A red-black tree is a binary search tree with the node color as an
extra attribute.
It fulfills a set of conditions:
+.Pp
.Bl -enum -compact -offset indent
.It
every search path from the root to a leaf consists of the same number of
@@ -333,7 +361,9 @@ macro declares a structure that allows e
In order to use the functions that manipulate the tree structure,
their prototypes need to be declared with the
.Fn RB_PROTOTYPE
-macro,
+or
+.Fn RB_PROTOTYPE_STATIC
+macros,
where
.Fa NAME
is a unique identifier for this particular tree.
@@ -348,15 +378,19 @@ argument is the name of the element defi
.Pp
The function bodies are generated with the
.Fn RB_GENERATE
-macro.
-It takes the same arguments as the
+or
+.Fn RB_GENERATE_STATIC
+macros.
+These macros take the same arguments as the
.Fn RB_PROTOTYPE
-macro, but should be used only once.
+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 trees noded
+argument is the name of a function used to compare trees' nodes
with each other.
The function takes two arguments of type
.Fa "struct TYPE *" .
@@ -371,7 +405,7 @@ The
macro initializes the tree referenced by
.Fa head .
.Pp
-The redblack tree can also be initialized statically by using the
+The red-black tree can also be initialized statically by using the
.Fn RB_INITIALIZER
macro like this:
.Bd -literal -offset indent
@@ -383,6 +417,11 @@ The
macro inserts the new element
.Fa elm
into the tree.
+Upon success,
+.Va NULL
+is returned.
+If a matching element already exists in the tree, the insertion is
+aborted, and a pointer to the existing element is returned.
.Pp
The
.Fn RB_REMOVE
@@ -391,22 +430,34 @@ macro removes the element
from the tree pointed to by
.Fa head .
The element must be present in that tree.
+.Fn RB_REMOVE
+returns
+.Fa elm .
.Pp
The
.Fn RB_FIND
macro can be used to find a particular element in the tree.
+and
+.Fn RB_NFIND
+macros can be used to find a particular element in the tree.
+.Fn RB_FIND
+finds the node with the same key as
+.Fa elm .
+.Fn RB_NFIND
+finds the first node greater than or equal to the search key.
.Bd -literal -offset indent
struct TYPE find, *res;
find.key = 30;
-res = RB_FIND(NAME, head, \*[Am]find);
+res = RB_FIND(NAME, \*[Am]head, \*[Am]find);
.Ed
.Pp
The
.Fn RB_ROOT ,
.Fn RB_MIN ,
.Fn RB_MAX ,
+.Fn RB_NEXT,
and
-.Fn RB_NEXT
+.Fn RB_PREV
macros can be used to traverse the tree:
.Bd -literal -offset indent
for (np = RB_MIN(NAME, \*[Am]head); np != NULL; np = RB_NEXT(NAME, \*[Am]head, np))
@@ -414,14 +465,102 @@ for (np = RB_MIN(NAME, \*[Am]head); np !
.Pp
Or, for simplicity, one can use the
.Fn RB_FOREACH
-macro:
+or
+.Fn RB_FOREACH_REVERSE
+macros:
.Bd -literal -offset indent
-RB_FOREACH(np, NAME, head)
+RB_FOREACH(np, NAME, \*[Am]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
The
.Fn RB_EMPTY
macro should be used to check whether a red-black tree is empty.
+.Sh EXAMPLES
+The following example demonstrates how to declare a red-black tree
+holding integers.
+Values are inserted into it and the contents of the tree are printed
+in order.
+Lastly, the internal structure of the tree is printed.
+.Bd -literal -offset 3n
+#include <sys/tree.h>
+#include <err.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+struct node {
+ RB_ENTRY(node) entry;
+ int i;
+};
+
+int
+intcmp(struct node *e1, struct node *e2)
+{
+ return (e1->i < e2->i ? -1 : e1->i > e2->i);
+}
+
+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()
+{
+ 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("\en");
+ return (0);
+}
+.Ed
.Sh NOTES
Some of these macros or functions perform no error checking,
and invalid usage leads to undefined behaviour.
@@ -431,8 +570,8 @@ that is not present in the tree is inval
.Pp
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);
+SPLAY_FOREACH(var, NAME, &head) {
+ SPLAY_REMOVE(NAME, &head, var);
free(var);
}
free(head);
@@ -445,29 +584,29 @@ is free'd, the
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);
+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.
+.\".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 AUTHORS
The author of the tree macros is
.An Niels Provos .
