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