--- Libc/Libc-1725.40.4/gen/NetBSD/rbtree.3
+++ /dev/null
@@ -1,326 +0,0 @@
-.\"     $NetBSD: rbtree.3,v 1.12 2016/08/30 05:12:00 dholland Exp $
-.\"
-.\" Copyright (c) 2010 The NetBSD Foundation, Inc.
-.\" All rights reserved.
-.\"
-.\" Portions Copyright (c) 2012 Apple Inc. All rights reserved.
-.\"
-.\" This code is derived from software contributed to The NetBSD Foundation
-.\" by Matt Thomas, Niels Provos, and David Young.
-.\"
-.\" 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 NETBSD FOUNDATION, INC. AND CONTRIBUTORS
-.\" ``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 FOUNDATION OR CONTRIBUTORS
-.\" 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 August 29, 2016
-.Dt RBTREE 3
-.Os
-.Sh NAME
-.Nm rbtree ,
-.Nm rb_tree_init ,
-.Nm rb_tree_insert_node ,
-.Nm rb_tree_remove_node ,
-.Nm rb_tree_find_node ,
-.Nm rb_tree_find_node_geq ,
-.Nm rb_tree_find_node_leq ,
-.Nm rb_tree_iterate ,
-.Nm rb_tree_count ,
-.Nm RB_TREE_MIN ,
-.Nm RB_TREE_MAX ,
-.Nm RB_TREE_FOREACH ,
-.Nm RB_TREE_FOREACH_SAFE ,
-.Nm RB_TREE_FOREACH_REVERSE ,
-.Nm RB_TREE_FOREACH_REVERSE_SAFE
-.Nd red-black tree
-.Sh LIBRARY
-.Lb libc
-.Sh SYNOPSIS
-.In sys/rbtree.h
-.Ft void
-.Fn rb_tree_init "rb_tree_t *rbt" "const rb_tree_ops_t *ops"
-.Ft void *
-.Fn rb_tree_insert_node "rb_tree_t *rbt" "void *rb"
-.Ft void
-.Fn rb_tree_remove_node "rb_tree_t *rbt" "void *rb"
-.Ft void *
-.Fn rb_tree_find_node "rb_tree_t *rbt" "const void *key"
-.Ft void *
-.Fn rb_tree_find_node_geq "rb_tree_t *rbt" "const void *key"
-.Ft void *
-.Fn rb_tree_find_node_leq "rb_tree_t *rbt" "const void *key"
-.Ft void *
-.Fn rb_tree_iterate "rb_tree_t *rbt" "void *rb" "const unsigned int direction"
-.Ft size_t
-.Fn rb_tree_count "rb_tree_t *rbt"
-.Ft void *
-.Fn RB_TREE_MIN "rb_tree_t *rbt"
-.Ft void *
-.Fn RB_TREE_MAX "rb_tree_t *rbt"
-.Fn RB_TREE_FOREACH "void *rb" "rb_tree_t *rbt"
-.Fn RB_TREE_FOREACH_SAFE "void *rb" "rb_tree_t *rbt" "void *tmp"
-.Fn RB_TREE_FOREACH_REVERSE "void *rb" "rb_tree_t *rbt"
-.Fn RB_TREE_FOREACH_REVERSE_SAFE "void *rb" "rb_tree_t *rbt" "void *tmp"
-.Sh DESCRIPTION
-.Nm
-provides 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 -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).
-.Sh TYPES
-.Bl -tag -width compact
-.It Vt rb_tree_t
-A red-black tree.
-.It Vt typedef signed int \
-(* rbto_compare_nodes_fn)(void *context, const void *node1, const void *node2);
-The node-comparison function.
-Defines an ordering on nodes.
-Returns a negative value if the first node
-.Ar node1
-precedes the second node
-.Ar node2 .
-Returns a positive value if the first node
-.Ar node1
-follows the second node
-.Ar node2 .
-Returns 0 if the first node
-.Ar node1
-and the second node
-.Ar node2
-are identical according to the ordering.
-.It Vt typedef signed int \
-(* rbto_compare_key_fn)(void *context, const void *node, const void *key);
-The node-key comparison function.
-Defines the order of nodes and keys.
-Returns a negative value if the node
-.Ar node
-precedes the key
-.Ar key .
-Returns a positive value if the node
-.Ar node
-follows the key
-.Ar key .
-Returns 0 if the node
-.Ar node
-is identical to the key
-.Ar key
-according to the ordering.
-.It Vt rb_tree_ops_t
-Defines the function for comparing two nodes in the same tree,
-the function for comparing a node in the tree with a key,
-the offset of member
-.Vt rb_node_t
-within the node type,
-and the opaque context pointer passed to the comparison functions.
-Members of
-.Vt rb_tree_ops_t
-are
-.Bd -literal
-        rbto_compare_nodes_fn rbto_compare_nodes;
-        rbto_compare_key_fn rbto_compare_key;
-        size_t rbto_node_offset;
-        void *rbto_context;
-.Ed
-.It Vt rb_node_t
-A node in a red-black tree has this structure as a member.
-The offset of the
-.Vt rb_node_t
-member in the caller's node structure should be provided as
-.Va rbto_node_offset .
-(None of the functions in the
-.Nm
-interface are meant to take pointers directly to the
-.Vt rb_node_t
-member.)
-.El
-.Sh FUNCTIONS
-.Bl -tag -width compact
-.It Fn rb_tree_init "rbt" "ops"
-Initialize the red-black tree
-.Fa rbt .
-Let the comparison functions given by
-.Fa ops
-define the order of nodes in the tree for
-the purposes of insertion, search, and iteration.
-.Fn rb_tree_init
-always succeeds.
-.It Fn rb_tree_insert_node "rbt" "rb"
-Insert the node
-.Fa rb
-into the tree
-.Fa rbt .
-Return inserted node on success,
-already existing node on failure.
-.It Fn rb_tree_remove_node "rbt" "rb"
-Remove the node
-.Fa rb
-from the tree
-.Fa rbt .
-.It Fn rb_tree_find_node "rbt" "key"
-Search the tree
-.Fa rbt
-for a node exactly matching
-.Fa key .
-If no such node is in the tree, return
-.Dv NULL .
-Otherwise, return the matching node.
-.It Fn rb_tree_find_node_geq "rbt" "key"
-Search the tree
-.Fa rbt
-for a node that exactly matches
-.Fa key
-and return it.
-If no such node is present, return the first node following
-.Fa key
-or, if no such node is in the tree, return
-.Dv NULL .
-.It Fn rb_tree_find_node_leq "rbt" "key"
-Search the tree
-.Fa rbt
-for a node that exactly matches
-.Fa key
-and return it.
-If no such node is present, return the first node preceding
-.Fa key
-or, if no such node is in the tree, return
-.Dv NULL .
-.It Fn rb_tree_iterate "rbt" "rb" "direction"
-If
-.Fa direction
-is
-.Dv RB_DIR_LEFT ,
-return the node in the tree
-.Fa rbt
-immediately preceding the node
-.Fa rb
-or, if
-.Fa rb
-is
-.Dv NULL ,
-return the first node in
-.Fa rbt
-or, if the tree is empty, return
-.Dv NULL .
-.Pp
-If
-.Fa direction
-is
-.Dv RB_DIR_RIGHT ,
-return the node in the tree
-.Fa rbt
-immediately following the node
-.Fa rb
-or, if
-.Fa rb
-is
-.Dv NULL ,
-return the last node in
-.Fa rbt
-or, if the tree is empty, return
-.Dv NULL .
-.It Fn rb_tree_count "rbt"
-Return the number of nodes in the tree
-.Fa rbt .
-If
-.Fa rbt
-is
-.Dv NULL ,
-0 is returned.
-.It Fn RB_TREE_MIN "rbt"
-Return the first node in
-.Fa rbt ,
-i.e. the node with the least key, or
-.Dv NULL
-if
-.Fa rbt
-is empty.
-.It Fn RB_TREE_MAX "rbt"
-Return the last node in
-.Fa rbt ,
-i.e. the node with the greatest key, or
-.Dv NULL
-if
-.Fa rbt
-is empty.
-.It Fn RB_TREE_FOREACH "rb" "rbt"
-.Nm RB_TREE_FOREACH
-is a macro to be used in the place of a
-.Dv for
-header preceding a statement to traverse the nodes in
-.Fa rbt
-from least to greatest, assigning
-.Fa rb
-to each node in turn and executing the statement.
-.It Fn RB_TREE_FOREACH_SAFE "rb" "rbt" "tmp"
-.Nm RB_TREE_FOREACH_SAFE
-is a macro to be used like
-.Nm RB_TREE_FOREACH
-but which uses a temporary variable to permit safe modification or deletion of
-.Fa rb
-in the body of the loop.
-.It Fn RB_TREE_FOREACH_REVERSE "rb" "rbt"
-.Nm RB_TREE_FOREACH_REVERSE
-is a macro to be used in the place of a
-.Dv for
-header preceding a statement to traverse the nodes in
-.Fa rbt
-from greatest to least, assigning
-.Fa rb
-to each node in turn and executing the statement.
-.It Fn RB_TREE_FOREACH_REVERSE_SAFE "rb" "rbt" "tmp"
-.Nm RB_TREE_FOREACH_REVERSE_SAFE
-is a macro to be used like
-.Nm RB_TREE_FOREACH_REVERSE
-but which uses a temporary variable to permit safe modification or deletion of
-.Fa rb
-in the body of the loop.
-.El
-.Sh SEE ALSO
-.Xr queue 3 ,
-.Xr tree 3
-.Sh HISTORY
-The
-.Nm
-interface first appeared in
-.Nx 6.0 .
-.Sh AUTHORS
-.An Matt Thomas Aq Mt matt@NetBSD.org
-wrote
-.Nm .
-.Pp
-.An Niels Provos Aq Mt provos@citi.umich.edu
-wrote the
-.Xr tree 3
-manual page.
-Portions of this page derive from that page.
-.\" .Sh CAVEATS
-.\" .Sh BUGS
-.\" .Sh SECURITY CONSIDERATIONS