gen/NetBSD/rbtree.3

   1 .\"     $NetBSD: rbtree.3,v 1.7 2012/08/19 19:31:13 wiz Exp $
   2 .\"
   3 .\" Copyright (c) 2010 The NetBSD Foundation, Inc.
   4 .\" All rights reserved.
   5 .\"
   6 .\" Portions Copyright (c) 2012 Apple Inc. All rights reserved.
   7 .\"
   8 .\" This code is derived from software contributed to The NetBSD Foundation
   9 .\" by Matt Thomas, Niels Provos, and David Young.
  10 .\"
  11 .\" Redistribution and use in source and binary forms, with or without
  12 .\" modification, are permitted provided that the following conditions
  13 .\" are met:
  14 .\" 1. Redistributions of source code must retain the above copyright
  15 .\"    notice, this list of conditions and the following disclaimer.
  16 .\" 2. Redistributions in binary form must reproduce the above copyright
  17 .\"    notice, this list of conditions and the following disclaimer in the
  18 .\"    documentation and/or other materials provided with the distribution.
  19 .\"
  20 .\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  21 .\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  22 .\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  23 .\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  24 .\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  25 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  26 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  27 .\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  28 .\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  29 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  30 .\" POSSIBILITY OF SUCH DAMAGE.
  31 .\"
  32 .Dd August 19, 2012
  33 .Dt RBTREE 3
  34 .Os
  35 .Sh NAME
  36 .Nm rbtree
  37 .Nd red-black tree
  38 .Sh LIBRARY
  39 .Lb libc
  40 .Sh SYNOPSIS
  41 .In sys/rbtree.h
  42 .Ft void
  43 .Fn rb_tree_init "rb_tree_t *rbt" "const rb_tree_ops_t *ops"
  44 .Ft void *
  45 .Fn rb_tree_insert_node "rb_tree_t *rbt" "void *rb"
  46 .Ft void
  47 .Fn rb_tree_remove_node "rb_tree_t *rbt" "void *rb"
  48 .Ft void *
  49 .Fn rb_tree_find_node "rb_tree_t *rbt" "const void *key"
  50 .Ft void *
  51 .Fn rb_tree_find_node_geq "rb_tree_t *rbt" "const void *key"
  52 .Ft void *
  53 .Fn rb_tree_find_node_leq "rb_tree_t *rbt" "const void *key"
  54 .Ft void *
  55 .Fn rb_tree_iterate "rb_tree_t *rbt" "void *rb" "const unsigned int direction"
  56 .Ft size_t
  57 .Fn rb_tree_count "rb_tree_t *rbt"
  58 .Sh DESCRIPTION
  59 .Nm
  60 provides red-black trees.
  61 A red-black tree is a binary search tree with the node color as an
  62 extra attribute.
  63 It fulfills a set of conditions:
  64 .Bl -enum -offset indent
  65 .It
  66 Every search path from the root to a leaf consists of the same number of
  67 black nodes.
  68 .It
  69 Each red node (except for the root) has a black parent.
  70 .It
  71 Each leaf node is black.
  72 .El
  73 .Pp
  74 Every operation on a red-black tree is bounded as O(lg n).
  75 The maximum height of a red-black tree is 2lg (n+1).
  76 .Sh TYPES
  77 .Bl -tag -width compact
  78 .It Vt rb_tree_t
  79 A red-black tree.
  80 .It Vt typedef signed int \
  81 (* rbto_compare_nodes_fn)(void *context, const void *node1, const void *node2);
  82 The node-comparison operator.
  83 Defines an ordering on nodes.
  84 Returns a negative value if the first node
  85 .Ar node1
  86 precedes the second node
  87 .Ar node2 .
  88 Returns a positive value if the first node
  89 .Ar node1
  90 follows the second node
  91 .Ar node2 .
  92 Returns 0 if the first node
  93 .Ar node1
  94 and the second node
  95 .Ar node2
  96 are identical according to the ordering.
  97 .It Vt typedef signed int \
  98 (* rbto_compare_key_fn)(void *context, const void *node, const void *key);
  99 The node-key comparison operator.
 100 Defines the order of nodes and keys.
 101 Returns a negative value if the node
 102 .Ar node
 103 precedes the key
 104 .Ar key .
 105 Returns a positive value if the node
 106 .Ar node
 107 follows the key
 108 .Ar key .
 109 Returns 0 if the node
 110 .Ar node
 111 is identical to the key
 112 .Ar key
 113 according to the ordering.
 114 .It Vt rb_tree_ops_t
 115 Defines the operator for comparing two nodes in the same tree,
 116 the operator for comparing a node in the tree with a key,
 117 the offset of member
 118 .Vt rb_node_t
 119 within a node,
 120 and the opaque context passed to the operators.
 121 Members of
 122 .Vt rb_tree_ops_t
 123 are
 124 .Bd -literal
 125         rbto_compare_nodes_fn rbto_compare_nodes;
 126         rbto_compare_key_fn rbto_compare_key;
 127         size_t rbto_node_offset;
 128         void *rbto_context;
 129 .Ed
 130 .It Vt rb_node_t
 131 A node in a red-black tree has this structure as a member.
 132 .El
 133 .Sh FUNCTIONS
 134 .Bl -tag -width compact
 135 .It Fn rb_tree_init "rbt" "ops"
 136 Initialize the red-black tree
 137 .Fa rbt .
 138 Let the comparison operators given by
 139 .Fa ops
 140 define the order of nodes in the tree for
 141 the purposes of insertion, search, and iteration.
 142 .Fn rb_tree_init
 143 always succeeds.
 144 .It Fn rb_tree_insert_node "rbt" "rb"
 145 Insert the node
 146 .Fa rb
 147 into the tree
 148 .Fa rbt .
 149 Return inserted node on success,
 150 already existing node on failure.
 151 .It Fn rb_tree_remove_node "rbt" "rb"
 152 Remove the node
 153 .Fa rb
 154 from the tree
 155 .Fa rbt .
 156 .It Fn rb_tree_find_node "rbt" "key"
 157 Search the tree
 158 .Fa rbt
 159 for a node exactly matching
 160 .Fa key .
 161 If no such node is in the tree, return
 162 .Dv NULL .
 163 Otherwise, return the matching node.
 164 .It Fn rb_tree_find_node_geq "rbt" "key"
 165 Search the tree
 166 .Fa rbt
 167 for a node that exactly matches
 168 .Fa key
 169 and return it.
 170 If no such node is present, return the first node following
 171 .Fa key
 172 or, if no such node is in the tree, return
 173 .Dv NULL .
 174 .It Fn rb_tree_find_node_leq "rbt" "key"
 175 Search the tree
 176 .Fa rbt
 177 for a node that exactly matches
 178 .Fa key
 179 and return it.
 180 If no such node is present, return the first node preceding
 181 .Fa key
 182 or, if no such node is in the tree, return
 183 .Dv NULL .
 184 .It Fn rb_tree_iterate "rbt" "rb" "direction"
 185 If
 186 .Fa direction
 187 is
 188 .Dv RB_DIR_LEFT ,
 189 return the node in the tree
 190 .Fa rbt
 191 immediately preceding the node
 192 .Fa rb
 193 or, if
 194 .Fa rb
 195 is
 196 .Dv NULL ,
 197 return the last node in
 198 .Fa rbt
 199 or, if the tree is empty, return
 200 .Dv NULL .
 201 .Pp
 202 If
 203 .Fa direction
 204 is
 205 .Dv RB_DIR_RIGHT ,
 206 return the node in the tree
 207 .Fa rbt
 208 immediately following the node
 209 .Fa rb
 210 or, if
 211 .Fa rb
 212 is
 213 .Dv NULL ,
 214 return the first node in
 215 .Fa rbt
 216 or, if the tree is empty, return
 217 .Dv NULL .
 218 .It Fn rb_tree_count "rbt"
 219 Return the number of nodes in the tree
 220 .Fa rbt .
 221 If
 222 .Fa rbt
 223 is
 224 .Dv NULL ,
 225 0 is returned.
 226 .El
 227 .Sh IMPLEMENTATION DETAILS
 228 .Nx 6.0
 229 included a version of this API that returned the wrong result when using
 230 .Fn rb_tree_iterate
 231 to find the first or last node.
 232 This implementation does not have this bug.
 233 If you wish to maintain portability with
 234 .Nx 6.0 ,
 235 it is recomended that you use the
 236 .Fn RB_TREE_MIN
 237 and
 238 .Fn RB_TREE_MAX
 239 macros rather than using
 240 .Fn rb_tree_iterate
 241 directly.
 242 .Sh SEE ALSO
 243 .Xr queue 3
 244 .Sh HISTORY
 245 The
 246 .Nm
 247 interface first appeared in
 248 .Nx 6.0 .
 249 .Sh AUTHORS
 250 .An Matt Thomas Aq matt@NetBSD.org
 251 wrote
 252 .Nm .
 253 .Pp
 254 .An Niels Provos Aq provos@citi.umich.edu
 255 wrote the
 256 .Xr tree 3
 257 manual page.
 258 Portions of this page derive from that page.
 259 .\" .Sh CAVEATS
 260 .\" .Sh BUGS
 261 .\" .Sh SECURITY CONSIDERATIONS