[src/trunk]: src sync with OpenBSD.

[christos <christos%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/386f4fa2821a
branches:  trunk
changeset: 785773:386f4fa2821a
user:      christos <christos%NetBSD.org@localhost>
date:      Fri Mar 29 21:16:31 2013 +0000

description:
sync with OpenBSD.

diffstat:

 share/man/man3/tree.3 |  249 ++++++++++++++++++++++++++++++++++++++-----------
 sys/sys/tree.h        |    6 +-
 2 files changed, 197 insertions(+), 58 deletions(-)

diffs (truncated from 491 to 300 lines):

diff -r 5714e433116d -r 386f4fa2821a share/man/man3/tree.3
--- a/share/man/man3/tree.3     Fri Mar 29 20:58:58 2013 +0000
+++ b/share/man/man3/tree.3     Fri Mar 29 21:16:31 2013 +0000
@@ -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 <provos%citi.umich.edu@localhost>
 .\" * 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 @@
 .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 @@
 .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 @@
 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 @@
 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 @@
 .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 @@
 .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 @@
 .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 @@
 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 @@
 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 @@
 .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 @@
 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 @@
 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 @@
 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