Add RB_PROTOTYPE_STATIC, RB_GENERATE_STATIC, RB_PREV, RB_NFIND,

and RB_FOREACH_REVERSE from FreeBSD.  OK deraadt@

2 files changed, 47 insertions, 22 deletions

diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile
index 2fd1dfb15d3..d4bfafcc210 100644
--- a/share/man/man3/Makefile
+++ b/share/man/man3/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.19 2008/03/31 13:15:53 jmc Exp $
+#	$OpenBSD: Makefile,v 1.20 2008/05/11 22:19:09 millert Exp $
 #	@(#)Makefile	8.2 (Berkeley) 12/13/93
 
 MAN=	assert.3 bitstring.3 CMSG_DATA.3 dlfcn.3 dl_iterate_phdr.3 end.3 \
@@ -64,13 +64,13 @@ MLINKS+=tree.3 SPLAY_PROTOTYPE.3 tree.3 SPLAY_GENERATE.3 \
 	tree.3 SPLAY_LEFT.3 tree.3 SPLAY_RIGHT.3 tree.3 SPLAY_INIT.3 \
 	tree.3 SPLAY_INSERT.3 tree.3 SPLAY_REMOVE.3 \
 	tree.3 SPLAY_FOREACH.3
-MLINKS+=tree.3 RB_PROTOTYPE.3 tree.3 RB_GENERATE.3 \
-	tree.3 RB_ENTRY.3 tree.3 RB_HEAD.3 \
-	tree.3 RB_INITIALIZER.3 tree.3 RB_ROOT.3 \
-	tree.3 RB_EMPTY.3 tree.3 RB_NEXT.3 \
-	tree.3 RB_MIN.3 tree.3 RB_MAX.3 tree.3 RB_FIND.3 \
+MLINKS+=tree.3 RB_PROTOTYPE.3 tree.3 RB_PROTOTYPE_STATIC.3 \
+	tree.3 RB_GENERATE.3 tree.3 RB_GENERATE_STATIC.3 tree.3 RB_ENTRY.3 \
+	tree.3 RB_HEAD.3 tree.3 RB_INITIALIZER.3 tree.3 RB_ROOT.3 \
+	tree.3 RB_EMPTY.3 tree.3 RB_NEXT.3 tree.3 RB_PREV.3 \
+	tree.3 RB_MIN.3 tree.3 RB_MAX.3 tree.3 RB_FIND.3 tree.3 RB_NFIND.3 \
 	tree.3 RB_LEFT.3 tree.3 RB_RIGHT.3 tree.3 RB_PARENT.3 \
 	tree.3 RB_INIT.3 tree.3 RB_INSERT.3 tree.3 RB_REMOVE.3 \
-	tree.3 RB_FOREACH.3
+	tree.3 RB_FOREACH.3 tree.3 RB_FOREACH_REVERSE.3
 
 .include <bsd.prog.mk>
diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3
index e4a5cede6a6..05d71f60b9c 100644
--- a/share/man/man3/tree.3
+++ b/share/man/man3/tree.3
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: tree.3,v 1.14 2007/12/24 12:04:13 otto Exp $
+.\"	$OpenBSD: tree.3,v 1.15 2008/05/11 22:19:09 millert Exp $
 .\"/*
 .\" * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 .\" * All rights reserved.
@@ -28,7 +28,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 $Mdocdate: December 24 2007 $
+.Dd $Mdocdate: May 11 2008 $
 .Dt TREE 3
 .Os
 .Sh NAME
@@ -50,20 +50,25 @@
 .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_REVERSE ,
 .Nm RB_INIT ,
 .Nm RB_INSERT ,
 .Nm RB_REMOVE
@@ -101,7 +106,9 @@
 .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"
@@ -112,18 +119,23 @@
 .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_REVERSE "VARNAME" "NAME" "RB_HEAD *head"
 .Ft void
 .Fn RB_INIT "RB_HEAD *head"
 .Ft "struct TYPE *"
@@ -153,14 +165,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.
@@ -328,7 +342,9 @@ macro declares a structure that allows elements to be connected in the tree.
 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.
@@ -343,10 +359,14 @@ argument is the name of the element defined by
 .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
@@ -388,7 +408,9 @@ from the tree pointed by
 .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.
 .Bd -literal -offset indent
 struct TYPE find, *res;
 find.key = 30;
@@ -399,8 +421,9 @@ 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, &head); np != NULL; np = RB_NEXT(NAME, &head, np))
@@ -408,7 +431,9 @@ 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
-macro:
+or
+.Fn RB_FOREACH_REVERSE
+macros:
 .Bd -literal -offset indent
 RB_FOREACH(np, NAME, &head)
 .Ed