first cut at documenting new red-black tree code.

ok jmc@

2 files changed, 499 insertions, 1 deletions

diff --git a/share/man/man9/Makefile b/share/man/man9/Makefile
index aae1ad14808..a9a83b2f0e5 100644
--- a/share/man/man9/Makefile
+++ b/share/man/man9/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.279 2016/09/02 17:36:54 tedu Exp $
+#	$OpenBSD: Makefile,v 1.280 2016/09/05 07:22:29 dlg Exp $
 #	$NetBSD: Makefile,v 1.4 1996/01/09 03:23:01 thorpej Exp $
 
 #	Makefile for section 9 (kernel function and variable) manual pages.
@@ -26,6 +26,7 @@ MAN=	aml_evalnode.9 atomic_add_int.9 atomic_cas_uint.9 \
 	namei.9 \
 	panic.9 pci_conf_read.9 pci_intr_map.9 pfind.9 physio.9 pmap.9 \
 	pool.9 ppsratecheck.9 printf.9 psignal.9 \
+	RBT_INIT.9 \
 	radio.9 arc4random.9 rasops.9 ratecheck.9 refcnt_init.9 resettodr.9 \
 	rssadapt.9 route.9 rt_ifa_add.9 rt_timer_add.9 rtalloc.9 rtable_add.9 \
 	rtlabel_id2name.9 rtrequest.9 rwlock.9 SipHash24.9 sensor_attach.9 \
diff --git a/share/man/man9/RBT_INIT.9 b/share/man/man9/RBT_INIT.9
new file mode 100644
index 00000000000..01d0d3e6d99
--- /dev/null
+++ b/share/man/man9/RBT_INIT.9
@@ -0,0 +1,497 @@
+.\"	$OpenBSD: RBT_INIT.9,v 1.1 2016/09/05 07:22:29 dlg 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.
+.\" *
+.\" * 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.
+.\" */
+.\"
+.\" Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
+.\"
+.\" Permission to use, copy, modify, and distribute this software for any
+.\" purpose with or without fee is hereby granted, provided that the above
+.\" copyright notice and this permission notice appear in all copies.
+.\"
+.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+.\"
+.Dd $Mdocdate: September 5 2016 $
+.Dt RBT_INIT 9
+.Os
+.Sh NAME
+.Nm RBT_HEAD ,
+.Nm RBT_ENTRY ,
+.Nm RBT_PROTOTYPE ,
+.Nm RBT_GENERATE ,
+.Nm RBT_INITIALIZER ,
+.Nm RBT_INIT ,
+.Nm RBT_INSERT ,
+.Nm RBT_REMOVE ,
+.Nm RBT_FIND ,
+.Nm RBT_NFIND ,
+.Nm RBT_EMPTY ,
+.Nm RBT_ROOT ,
+.Nm RBT_MIN ,
+.Nm RBT_MAX ,
+.Nm RBT_NEXT ,
+.Nm RBT_PREV ,
+.Nm RBT_LEFT ,
+.Nm RBT_RIGHT ,
+.Nm RBT_PARENT ,
+.Nm RBT_FOREACH ,
+.Nm RBT_FOREACH_SAFE ,
+.Nm RBT_FOREACH_REVERSE ,
+.Nm RBT_FOREACH_REVERSE_SAFE
+.Nd Kernel red-black trees
+.Sh SYNOPSIS
+.In sys/tree.h
+.Fn RBT_HEAD "NAME" "TYPE"
+.Fn RBT_ENTRY "TYPE"
+.Fo RBT_PROTOTYPE
+.Fa "NAME"
+.Fa "TYPE"
+.Fa "ENTRY"
+.Fa "int (*compare)(const struct TYPE *, const struct TYPE *)"
+.Fc
+.Fo RBT_GENERATE
+.Fa "NAME"
+.Fa "TYPE"
+.Fa "ENTRY"
+.Fa "int (*compare)(const struct TYPE *, const struct TYPE *)"
+.Fc
+.Ft struct NAME
+.Fn RBT_INITIALIZER "struct NAME *self"
+.Ft void
+.Fn RBT_INIT "NAME" "struct NAME *rbt"
+.Ft struct TYPE *
+.Fn RBT_INSERT "NAME" "struct NAME *rbt" "struct TYPE *elm"
+.Ft struct TYPE *
+.Fn RBT_REMOVE "NAME" "struct NAME *rbt" "struct TYPE *elm"
+.Ft struct TYPE *
+.Fn RBT_FIND "NAME" "struct NAME *rbt" "const struct TYPE *key"
+.Ft struct TYPE *
+.Fn RBT_NFIND "NAME" "struct NAME *rbt" "const struct TYPE *key"
+.Ft int
+.Fn RBT_EMPTY "NAME" "struct NAME *rbt"
+.Ft struct TYPE *
+.Fn RBT_ROOT "NAME" "struct NAME *rbt"
+.Ft struct TYPE *
+.Fn RBT_MIN "NAME" "struct NAME *rbt"
+.Ft struct TYPE *
+.Fn RBT_MAX "NAME" "struct NAME *rbt"
+.Ft struct TYPE *
+.Fn RBT_NEXT "NAME" "struct NAME *rbt"
+.Ft struct TYPE *
+.Fn RBT_PREV "NAME" "struct NAME *rbt"
+.Ft struct TYPE *
+.Fn RBT_LEFT "NAME" "struct NAME *rbt"
+.Ft struct TYPE *
+.Fn RBT_RIGHT "NAME" "struct NAME *rbt"
+.Ft struct TYPE *
+.Fn RBT_PARENT "NAME" "struct NAME *rbt"
+.Fo RBT_FOREACH
+.Fa "VARNAME"
+.Fa "NAME"
+.Fa "struct NAME *rbt"
+.Fc
+.Fo RBT_FOREACH_REVERSE
+.Fa "VARNAME"
+.Fa "NAME"
+.Fa "struct NAME *rbt"
+.Fc
+.Fo RBT_FOREACH_SAFE
+.Fa "VARNAME"
+.Fa "NAME"
+.Fa "struct NAME *rbt"
+.Fa "NEXTVARNAME"
+.Fc
+.Fo RBT_FOREACH_REVERSE SAFE
+.Fa "VARNAME"
+.Fa "NAME"
+.Fa "struct NAME *rbt"
+.Fa "NEXTVARNAME"
+.Fc
+.Sh DESCRIPTION
+The red-black tree API provides data structures and operations for
+storing structures in red-black trees.
+.Pp
+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
+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
+This API is implemented as a set of functions that operate on generic
+pointers, but users of the API generate wrappers and macros that provide
+type safety when calling the functions.
+.Pp
+In the macro definitions,
+.Fa TYPE
+is the name of a structure that will be stored in a red-black tree.
+The
+.Fa TYPE
+structure must contain an
+.Fn RBT_ENTRY
+field
+that allows the element to be connected to a tree.
+The argument
+.Fa NAME
+is the name of a red-black tree type that can store a particular
+.Fa TYPE
+element.
+.Ss Creating a Red-Black Tree Type
+The
+.Fn RBT_HEAD
+macro creates a red-black tree type to store
+.Fa TYPE
+structures as elements in the tree.
+The argument
+.Fa NAME
+must uniquely identify every type of tree that is defined.
+.Pp
+.Fn RBT_PROTOTYPE
+produces the wrappers for a red-black tree type identified by
+.Fa NAME
+to operate on elements of type
+.Fa TYPE .
+.Fa ENTRY
+specifies which field in the
+.Fa TYPE
+structure is used to connect elements to
+.Fa NAME
+red-black trees.
+Elements in the red-black tree are ordered according to the result of comparing 
+them with the
+.Fa compare
+function.
+If the first argument to
+.Fa compare
+is to be ordered lower the second,
+the function returns a value smaller than zero.
+If the first argument is to be ordered higher than the second,
+the function returns a value greater than zero.
+If they are equal, the function returns zero.
+.Pp
+.Fn RBT_GENERATE
+produces the internal data structures used by the red-black tree
+type identified by
+.Fa NAME
+to operate on elements of type
+.Fa TYPE .
+The
+.Fa ENTRY
+and
+.Fa compare
+arguments are the same as the
+.Fn RBT_PROTOTYPE
+arguments of the same names.
+.Ss Initialising a Red-Black Tree
+.Fn RBT_INIT
+initialises the red-black tree
+.Fa rbt
+of type
+.Fa NAME
+to an empty state.
+.Pp
+.Fn RBT_INITIALIZER
+can be used to initialise a declaraion of the red-black tree
+.Fa self
+of type
+.Fa NAME
+to an empty state.
+.Ss Red-Black Tree Operations
+.Fn RBT_INSERT
+inserts the element
+.Fa elm
+into the red-black tree
+.Fa rbt
+of type
+.Fa NAME .
+Upon success,
+.Dv 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
+.Fn RBT_REMOVE
+removes the element
+.Fa elm
+from the red-black tree
+.Fa rbt
+of type
+.Fa NAME .
+.Fa elm
+must exist in the tree
+.Fa rbt
+before it is removed.
+.Pp
+.Fn RBT_FIND
+performs a binary search for an exact match of
+.Fa key
+in the red-black tree
+.Fa rbt
+of type
+.Fa NAME .
+.Pp
+.Fn RBT_NFIND
+performs a binary search for first node that is greater than or equal to
+.Fa key
+in the red-black tree
+.Fa rbt
+of type
+.Fa NAME .
+.Pp
+.Fn RBT_EMPTY
+returns if the red-black tree
+.Fa rbt
+of type
+.Fa NAME
+is empty.
+.Pp
+.Fn RBT_ROOT
+returns the root element in the red-black tree
+.Fa rbt
+of type
+.Fa NAME .
+.Pp
+.Fn RBT_MIN
+returns the lowest ordered element in the red-black tree
+.Fa rbt
+of type
+.Fa NAME .
+.Pp
+.Fn RBT_MAX
+returns the highest ordered element in the red-black tree
+.Fa rbt
+of type
+.Fa NAME .
+.Ss Red-Black Tree Element Operations
+.Fn RBT_NEXT
+returns a pointer to the next ordered element after
+.Fa elm
+in a red-black tree of type
+.Fa NAME .
+.Pp
+.Fn RBT_PREV
+returns a pointer to the previous ordered element after
+.Fa elm
+in a red-black tree of type
+.Fa NAME .
+.Pp
+.Fn RBT_LEFT
+returns a pointer to the left child element of
+.Fa elm
+in a red-black tree of type
+.Fa NAME .
+.Pp
+.Fn RBT_RIGHT
+returns a pointer to the right child element of
+.Fa elm
+in a red-black tree of type
+.Fa NAME .
+.Pp
+.Fn RBT_PARENT
+returns a pointer to the parent element of
+.Fa elm
+in a red-black tree of type
+.Fa NAME .
+.Ss Red-Black Tree Iterators
+The
+.Fn RBT_FOREACH
+macro iterates over the red-black tree
+.Fa rbt
+of type
+.Fa NAME
+from the lowest ordered element to the highest ordered element,
+setting
+.Fa VARNAME
+to each element in turn.
+.Pp
+The
+.Fn RBT_FOREACH_REVERSE
+macro iterates over the red-black tree
+.Fa rbt
+of type
+.Fa NAME
+from the highest ordered element to the lowest ordered element,
+setting
+.Fa VARNAME
+to each element in turn.
+.Pp
+The
+.Fn RBT_FOREACH_SAFE
+macro iterates over the red-black tree
+.Fa rbt
+of type
+.Fa NAME
+from the lowest ordered element to the highest ordered element,
+setting
+.Fa VARNAME
+to each element in turn.
+.Fa VARNAME
+may be removed from the tree during iteration because a reference to the next
+element is held in
+.Fa NEXTVARNAME .
+.Pp
+The
+.Fn RBT_FOREACH_REVERSE_SAFE
+macro iterates over the red-black tree
+.Fa rbt
+of type
+.Fa NAME
+from the highest ordered element to the lowest ordered element,
+setting
+.Fa VARNAME
+to each element in turn.
+.Fa VARNAME
+may be removed from the tree during iteration because a reference to the next
+element is held in
+.Fa NEXTVARNAME .
+.Sh CONTEXT
+.Fn RBT_INIT ,
+.Fn RBT_INSERT ,
+.Fn RBT_REMOVE ,
+.Fn RBT_FIND ,
+.Fn RBT_NFIND ,
+.Fn RBT_EMPTY ,
+.Fn RBT_ROOT ,
+.Fn RBT_MIN ,
+.Fn RBT_MAX ,
+.Fn RBT_NEXT ,
+.Fn RBT_PREV ,
+.Fn RBT_LEFT ,
+.Fn RBT_RIGHT ,
+.Fn RBT_PARENT ,
+.Fn RBT_FOREACH ,
+.Fn RBT_FOREACH_REVERSE ,
+.Fn RBT_FOREACH_SAFE ,
+and
+.Fn RBT_FOREACH_SAFE_REVERSE
+can be called during autoconf, from process context, or from interrupt
+context.
+.Pp
+It is up to the caller to provide appropriate locking around calls to
+these functions to prevent concurrent access to the relevent data structures.
+.Sh RETURN VALUES
+.Fn RBT_INSERT
+will return
+.Dv NULL
+on successful insertion of
+.Fa elm
+into the tree, otherwise it will return a reference to an existing
+element with the same key.
+.Pp
+.Fn RBT_FIND
+will return a reference to an element that compares as equal to
+.Fa key ,
+or
+.Dv NULL
+if no such element could be found.
+.Pp
+.Fn RBT_NFIND
+will return a reference to the nearest element that compares as equal or
+greater to 
+.Fa key ,
+or
+.Dv NULL
+if no such element could be found.
+.Pp
+.Fn RBT_EMPTY
+returns non-zero if the red-black tree
+.Fa rbt
+is empty, otherwise 0.
+.Pp
+.Fn RBT_ROOT
+returns a reference to the root node in the red-black tree
+.Fa rbt ,
+or
+.Dv NULL
+if it is empty.
+.Pp
+.Fn RBT_MIN
+returns a reference to the lowest ordered element in the red-black tree
+.Fa rbt ,
+or
+.Dv NULL
+if it is empty.
+.Pp
+.Fn RBT_MAX
+returns a reference to the lowest ordered element in the red-black tree
+.Fa rbt ,
+or
+.Dv NULL
+if it is empty.
+.Pp
+.Fn RBT_NEXT
+returns a reference to the next ordered element in the red-black tree after
+.Fa elm ,
+or
+.Dv NULL
+if it is the greatest element in the tree.
+.Pp
+.Fn RBT_PREV
+returns a reference to the previous ordered element in the red-black tree before
+.Fa elm ,
+or
+.Dv NULL
+if it is the lowest element in the tree.
+.Pp
+.Fn RBT_LEFT
+returns a reference to left child element of 
+.Fa elm ,
+or
+.Dv NULL
+if it is a leaf in the tree.
+.Pp
+.Fn RBT_RIGHT
+returns a reference to right child element of 
+.Fa elm ,
+or
+.Dv NULL
+if it is a leaf in the tree.
+.Pp
+.Fn RBT_PARENT
+returns a reference to parent element of 
+.Fa elm ,
+or
+.Dv NULL
+if it is the root of the tree.
+.Sh SEE ALSO
+.Xr RB_INIT 3
+.Sh HISTORY
+The red-black tree kernel API first appeared in
+.Ox 6.1 .