gen/NetBSD/rbtree.3

   1 .\"     $NetBSD: rbtree.3,v 1.12 2016/08/30 05:12:00 dholland 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 29, 2016
  33 .Dt RBTREE 3
  34 .Os
  35 .Sh NAME
  36 .Nm rbtree ,
  37 .Nm rb_tree_init ,
  38 .Nm rb_tree_insert_node ,
  39 .Nm rb_tree_remove_node ,
  40 .Nm rb_tree_find_node ,
  41 .Nm rb_tree_find_node_geq ,
  42 .Nm rb_tree_find_node_leq ,
  43 .Nm rb_tree_iterate ,
  44 .Nm rb_tree_count ,
  45 .Nm RB_TREE_MIN ,
  46 .Nm RB_TREE_MAX ,
  47 .Nm RB_TREE_FOREACH ,
  48 .Nm RB_TREE_FOREACH_SAFE ,
  49 .Nm RB_TREE_FOREACH_REVERSE ,
  50 .Nm RB_TREE_FOREACH_REVERSE_SAFE
  51 .Nd red-black tree
  52 .Sh LIBRARY
  53 .Lb libc
  54 .Sh SYNOPSIS
  55 .In sys/rbtree.h
  56 .Ft void
  57 .Fn rb_tree_init "rb_tree_t *rbt" "const rb_tree_ops_t *ops"
  58 .Ft void *
  59 .Fn rb_tree_insert_node "rb_tree_t *rbt" "void *rb"
  60 .Ft void
  61 .Fn rb_tree_remove_node "rb_tree_t *rbt" "void *rb"
  62 .Ft void *
  63 .Fn rb_tree_find_node "rb_tree_t *rbt" "const void *key"
  64 .Ft void *
  65 .Fn rb_tree_find_node_geq "rb_tree_t *rbt" "const void *key"
  66 .Ft void *
  67 .Fn rb_tree_find_node_leq "rb_tree_t *rbt" "const void *key"
  68 .Ft void *
  69 .Fn rb_tree_iterate "rb_tree_t *rbt" "void *rb" "const unsigned int direction"
  70 .Ft size_t
  71 .Fn rb_tree_count "rb_tree_t *rbt"
  72 .Ft void *
  73 .Fn RB_TREE_MIN "rb_tree_t *rbt"
  74 .Ft void *
  75 .Fn RB_TREE_MAX "rb_tree_t *rbt"
  76 .Fn RB_TREE_FOREACH "void *rb" "rb_tree_t *rbt"
  77 .Fn RB_TREE_FOREACH_SAFE "void *rb" "rb_tree_t *rbt" "void *tmp"
  78 .Fn RB_TREE_FOREACH_REVERSE "void *rb" "rb_tree_t *rbt"
  79 .Fn RB_TREE_FOREACH_REVERSE_SAFE "void *rb" "rb_tree_t *rbt" "void *tmp"
  80 .Sh DESCRIPTION
  81 .Nm
  82 provides red-black trees.
  83 A red-black tree is a binary search tree with the node color as an
  84 extra attribute.
  85 It fulfills a set of conditions:
  86 .Bl -enum -offset indent
  87 .It
  88 Every search path from the root to a leaf consists of the same number of
  89 black nodes.
  90 .It
  91 Each red node (except for the root) has a black parent.
  92 .It
  93 Each leaf node is black.
  94 .El
  95 .Pp
  96 Every operation on a red-black tree is bounded as O(lg n).
  97 The maximum height of a red-black tree is 2lg (n+1).
  98 .Sh TYPES
  99 .Bl -tag -width compact
 100 .It Vt rb_tree_t
 101 A red-black tree.
 102 .It Vt typedef signed int \
 103 (* rbto_compare_nodes_fn)(void *context, const void *node1, const void *node2);
 104 The node-comparison function.
 105 Defines an ordering on nodes.
 106 Returns a negative value if the first node
 107 .Ar node1
 108 precedes the second node
 109 .Ar node2 .
 110 Returns a positive value if the first node
 111 .Ar node1
 112 follows the second node
 113 .Ar node2 .
 114 Returns 0 if the first node
 115 .Ar node1
 116 and the second node
 117 .Ar node2
 118 are identical according to the ordering.
 119 .It Vt typedef signed int \
 120 (* rbto_compare_key_fn)(void *context, const void *node, const void *key);
 121 The node-key comparison function.
 122 Defines the order of nodes and keys.
 123 Returns a negative value if the node
 124 .Ar node
 125 precedes the key
 126 .Ar key .
 127 Returns a positive value if the node
 128 .Ar node
 129 follows the key
 130 .Ar key .
 131 Returns 0 if the node
 132 .Ar node
 133 is identical to the key
 134 .Ar key
 135 according to the ordering.
 136 .It Vt rb_tree_ops_t
 137 Defines the function for comparing two nodes in the same tree,
 138 the function for comparing a node in the tree with a key,
 139 the offset of member
 140 .Vt rb_node_t
 141 within the node type,
 142 and the opaque context pointer passed to the comparison functions.
 143 Members of
 144 .Vt rb_tree_ops_t
 145 are
 146 .Bd -literal
 147         rbto_compare_nodes_fn rbto_compare_nodes;
 148         rbto_compare_key_fn rbto_compare_key;
 149         size_t rbto_node_offset;
 150         void *rbto_context;
 151 .Ed
 152 .It Vt rb_node_t
 153 A node in a red-black tree has this structure as a member.
 154 The offset of the
 155 .Vt rb_node_t
 156 member in the caller's node structure should be provided as
 157 .Va rbto_node_offset .
 158 (None of the functions in the
 159 .Nm
 160 interface are meant to take pointers directly to the
 161 .Vt rb_node_t
 162 member.)
 163 .El
 164 .Sh FUNCTIONS
 165 .Bl -tag -width compact
 166 .It Fn rb_tree_init "rbt" "ops"
 167 Initialize the red-black tree
 168 .Fa rbt .
 169 Let the comparison functions given by
 170 .Fa ops
 171 define the order of nodes in the tree for
 172 the purposes of insertion, search, and iteration.
 173 .Fn rb_tree_init
 174 always succeeds.
 175 .It Fn rb_tree_insert_node "rbt" "rb"
 176 Insert the node
 177 .Fa rb
 178 into the tree
 179 .Fa rbt .
 180 Return inserted node on success,
 181 already existing node on failure.
 182 .It Fn rb_tree_remove_node "rbt" "rb"
 183 Remove the node
 184 .Fa rb
 185 from the tree
 186 .Fa rbt .
 187 .It Fn rb_tree_find_node "rbt" "key"
 188 Search the tree
 189 .Fa rbt
 190 for a node exactly matching
 191 .Fa key .
 192 If no such node is in the tree, return
 193 .Dv NULL .
 194 Otherwise, return the matching node.
 195 .It Fn rb_tree_find_node_geq "rbt" "key"
 196 Search the tree
 197 .Fa rbt
 198 for a node that exactly matches
 199 .Fa key
 200 and return it.
 201 If no such node is present, return the first node following
 202 .Fa key
 203 or, if no such node is in the tree, return
 204 .Dv NULL .
 205 .It Fn rb_tree_find_node_leq "rbt" "key"
 206 Search the tree
 207 .Fa rbt
 208 for a node that exactly matches
 209 .Fa key
 210 and return it.
 211 If no such node is present, return the first node preceding
 212 .Fa key
 213 or, if no such node is in the tree, return
 214 .Dv NULL .
 215 .It Fn rb_tree_iterate "rbt" "rb" "direction"
 216 If
 217 .Fa direction
 218 is
 219 .Dv RB_DIR_LEFT ,
 220 return the node in the tree
 221 .Fa rbt
 222 immediately preceding the node
 223 .Fa rb
 224 or, if
 225 .Fa rb
 226 is
 227 .Dv NULL ,
 228 return the first node in
 229 .Fa rbt
 230 or, if the tree is empty, return
 231 .Dv NULL .
 232 .Pp
 233 If
 234 .Fa direction
 235 is
 236 .Dv RB_DIR_RIGHT ,
 237 return the node in the tree
 238 .Fa rbt
 239 immediately following the node
 240 .Fa rb
 241 or, if
 242 .Fa rb
 243 is
 244 .Dv NULL ,
 245 return the last node in
 246 .Fa rbt
 247 or, if the tree is empty, return
 248 .Dv NULL .
 249 .It Fn rb_tree_count "rbt"
 250 Return the number of nodes in the tree
 251 .Fa rbt .
 252 If
 253 .Fa rbt
 254 is
 255 .Dv NULL ,
 256 0 is returned.
 257 .It Fn RB_TREE_MIN "rbt"
 258 Return the first node in
 259 .Fa rbt ,
 260 i.e. the node with the least key, or
 261 .Dv NULL
 262 if
 263 .Fa rbt
 264 is empty.
 265 .It Fn RB_TREE_MAX "rbt"
 266 Return the last node in
 267 .Fa rbt ,
 268 i.e. the node with the greatest key, or
 269 .Dv NULL
 270 if
 271 .Fa rbt
 272 is empty.
 273 .It Fn RB_TREE_FOREACH "rb" "rbt"
 274 .Nm RB_TREE_FOREACH
 275 is a macro to be used in the place of a
 276 .Dv for
 277 header preceding a statement to traverse the nodes in
 278 .Fa rbt
 279 from least to greatest, assigning
 280 .Fa rb
 281 to each node in turn and executing the statement.
 282 .It Fn RB_TREE_FOREACH_SAFE "rb" "rbt" "tmp"
 283 .Nm RB_TREE_FOREACH_SAFE
 284 is a macro to be used like
 285 .Nm RB_TREE_FOREACH
 286 but which uses a temporary variable to permit safe modification or deletion of
 287 .Fa rb
 288 in the body of the loop.
 289 .It Fn RB_TREE_FOREACH_REVERSE "rb" "rbt"
 290 .Nm RB_TREE_FOREACH_REVERSE
 291 is a macro to be used in the place of a
 292 .Dv for
 293 header preceding a statement to traverse the nodes in
 294 .Fa rbt
 295 from greatest to least, assigning
 296 .Fa rb
 297 to each node in turn and executing the statement.
 298 .It Fn RB_TREE_FOREACH_REVERSE_SAFE "rb" "rbt" "tmp"
 299 .Nm RB_TREE_FOREACH_REVERSE_SAFE
 300 is a macro to be used like
 301 .Nm RB_TREE_FOREACH_REVERSE
 302 but which uses a temporary variable to permit safe modification or deletion of
 303 .Fa rb
 304 in the body of the loop.
 305 .El
 306 .Sh SEE ALSO
 307 .Xr queue 3 ,
 308 .Xr tree 3
 309 .Sh HISTORY
 310 The
 311 .Nm
 312 interface first appeared in
 313 .Nx 6.0 .
 314 .Sh AUTHORS
 315 .An Matt Thomas Aq Mt matt@NetBSD.org
 316 wrote
 317 .Nm .
 318 .Pp
 319 .An Niels Provos Aq Mt provos@citi.umich.edu
 320 wrote the
 321 .Xr tree 3
 322 manual page.
 323 Portions of this page derive from that page.
 324 .\" .Sh CAVEATS
 325 .\" .Sh BUGS
 326 .\" .Sh SECURITY CONSIDERATIONS