share/man/man3/tree.3

   1 .\"     $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $
   2 .\"
   3 .\" Copyright 2002 Niels Provos <provos@citi.umich.edu>
   4 .\" All rights reserved.
   5 .\"
   6 .\" Redistribution and use in source and binary forms, with or without
   7 .\" modification, are permitted provided that the following conditions
   8 .\" are met:
   9 .\" 1. Redistributions of source code must retain the above copyright
  10 .\"    notice, this list of conditions and the following disclaimer.
  11 .\" 2. Redistributions in binary form must reproduce the above copyright
  12 .\"    notice, this list of conditions and the following disclaimer in the
  13 .\"    documentation and/or other materials provided with the distribution.
  14 .\" 3. All advertising materials mentioning features or use of this software
  15 .\"    must display the following acknowledgement:
  16 .\"      This product includes software developed by Niels Provos.
  17 .\" 4. The name of the author may not be used to endorse or promote products
  18 .\"    derived from this software without specific prior written permission.
  19 .\"
  20 .\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  21 .\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  22 .\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  23 .\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  24 .\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  25 .\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26 .\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27 .\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  29 .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30 .\"
  31 .\" $FreeBSD$
  32 .\"
  33 .Dd November 4, 2013
  34 .Dt TREE 3
  35 .Os
  36 .Sh NAME
  37 .Nm SPLAY_PROTOTYPE ,
  38 .Nm SPLAY_GENERATE ,
  39 .Nm SPLAY_ENTRY ,
  40 .Nm SPLAY_HEAD ,
  41 .Nm SPLAY_INITIALIZER ,
  42 .Nm SPLAY_ROOT ,
  43 .Nm SPLAY_EMPTY ,
  44 .Nm SPLAY_NEXT ,
  45 .Nm SPLAY_MIN ,
  46 .Nm SPLAY_MAX ,
  47 .Nm SPLAY_FIND ,
  48 .Nm SPLAY_LEFT ,
  49 .Nm SPLAY_RIGHT ,
  50 .Nm SPLAY_FOREACH ,
  51 .Nm SPLAY_INIT ,
  52 .Nm SPLAY_INSERT ,
  53 .Nm SPLAY_REMOVE ,
  54 .Nm RB_PROTOTYPE ,
  55 .Nm RB_PROTOTYPE_STATIC ,
  56 .Nm RB_GENERATE ,
  57 .Nm RB_GENERATE_STATIC ,
  58 .Nm RB_ENTRY ,
  59 .Nm RB_HEAD ,
  60 .Nm RB_INITIALIZER ,
  61 .Nm RB_ROOT ,
  62 .Nm RB_EMPTY ,
  63 .Nm RB_NEXT ,
  64 .Nm RB_PREV ,
  65 .Nm RB_MIN ,
  66 .Nm RB_MAX ,
  67 .Nm RB_FIND ,
  68 .Nm RB_NFIND ,
  69 .Nm RB_LEFT ,
  70 .Nm RB_RIGHT ,
  71 .Nm RB_PARENT ,
  72 .Nm RB_FOREACH ,
  73 .Nm RB_FOREACH_SAFE ,
  74 .Nm RB_FOREACH_REVERSE ,
  75 .Nm RB_FOREACH_REVERSE_SAFE ,
  76 .Nm RB_INIT ,
  77 .Nm RB_INSERT ,
  78 .Nm RB_REMOVE
  79 .Nd "implementations of splay and red-black trees"
  80 .Sh SYNOPSIS
  81 .In sys/tree.h
  82 .Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP
  83 .Fn SPLAY_GENERATE NAME TYPE FIELD CMP
  84 .Fn SPLAY_ENTRY TYPE
  85 .Fn SPLAY_HEAD HEADNAME TYPE
  86 .Ft "struct TYPE *"
  87 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
  88 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
  89 .Ft bool
  90 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
  91 .Ft "struct TYPE *"
  92 .Fn SPLAY_NEXT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
  93 .Ft "struct TYPE *"
  94 .Fn SPLAY_MIN NAME "SPLAY_HEAD *head"
  95 .Ft "struct TYPE *"
  96 .Fn SPLAY_MAX NAME "SPLAY_HEAD *head"
  97 .Ft "struct TYPE *"
  98 .Fn SPLAY_FIND NAME "SPLAY_HEAD *head" "struct TYPE *elm"
  99 .Ft "struct TYPE *"
 100 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
 101 .Ft "struct TYPE *"
 102 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
 103 .Fn SPLAY_FOREACH VARNAME NAME "SPLAY_HEAD *head"
 104 .Ft void
 105 .Fn SPLAY_INIT "SPLAY_HEAD *head"
 106 .Ft "struct TYPE *"
 107 .Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
 108 .Ft "struct TYPE *"
 109 .Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm"
 110 .Fn RB_PROTOTYPE NAME TYPE FIELD CMP
 111 .Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
 112 .Fn RB_GENERATE NAME TYPE FIELD CMP
 113 .Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP
 114 .Fn RB_ENTRY TYPE
 115 .Fn RB_HEAD HEADNAME TYPE
 116 .Fn RB_INITIALIZER "RB_HEAD *head"
 117 .Ft "struct TYPE *"
 118 .Fn RB_ROOT "RB_HEAD *head"
 119 .Ft "bool"
 120 .Fn RB_EMPTY "RB_HEAD *head"
 121 .Ft "struct TYPE *"
 122 .Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm"
 123 .Ft "struct TYPE *"
 124 .Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm"
 125 .Ft "struct TYPE *"
 126 .Fn RB_MIN NAME "RB_HEAD *head"
 127 .Ft "struct TYPE *"
 128 .Fn RB_MAX NAME "RB_HEAD *head"
 129 .Ft "struct TYPE *"
 130 .Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm"
 131 .Ft "struct TYPE *"
 132 .Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm"
 133 .Ft "struct TYPE *"
 134 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
 135 .Ft "struct TYPE *"
 136 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
 137 .Ft "struct TYPE *"
 138 .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
 139 .Fn RB_FOREACH VARNAME NAME "RB_HEAD *head"
 140 .Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
 141 .Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head"
 142 .Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
 143 .Ft void
 144 .Fn RB_INIT "RB_HEAD *head"
 145 .Ft "struct TYPE *"
 146 .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
 147 .Ft "struct TYPE *"
 148 .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
 149 .Sh DESCRIPTION
 150 These macros define data structures for different types of trees:
 151 splay trees and red-black trees.
 152 .Pp
 153 In the macro definitions,
 154 .Fa TYPE
 155 is the name tag of a user defined structure that must contain a field of type
 156 .Vt SPLAY_ENTRY ,
 157 or
 158 .Vt RB_ENTRY ,
 159 named
 160 .Fa ENTRYNAME .
 161 The argument
 162 .Fa HEADNAME
 163 is the name tag of a user defined structure that must be declared
 164 using the macros
 165 .Fn SPLAY_HEAD ,
 166 or
 167 .Fn RB_HEAD .
 168 The argument
 169 .Fa NAME
 170 has to be a unique name prefix for every tree that is defined.
 171 .Pp
 172 The function prototypes are declared with
 173 .Fn SPLAY_PROTOTYPE ,
 174 .Fn RB_PROTOTYPE ,
 175 or
 176 .Fn RB_PROTOTYPE_STATIC .
 177 The function bodies are generated with
 178 .Fn SPLAY_GENERATE ,
 179 .Fn RB_GENERATE ,
 180 or
 181 .Fn RB_GENERATE_STATIC .
 182 See the examples below for further explanation of how these macros are used.
 183 .Sh SPLAY TREES
 184 A splay tree is a self-organizing data structure.
 185 Every operation on the tree causes a splay to happen.
 186 The splay moves the requested
 187 node to the root of the tree and partly rebalances it.
 188 .Pp
 189 This has the benefit that request locality causes faster lookups as
 190 the requested nodes move to the top of the tree.
 191 On the other hand, every lookup causes memory writes.
 192 .Pp
 193 The Balance Theorem bounds the total access time for
 194 .Ar m
 195 operations and
 196 .Ar n
 197 inserts on an initially empty tree as
 198 .Fn O "\*[lp]m + n\*[rp]lg n" .
 199 The
 200 amortized cost for a sequence of
 201 .Ar m
 202 accesses to a splay tree is
 203 .Fn O "lg n" .
 204 .Pp
 205 A splay tree is headed by a structure defined by the
 206 .Fn SPLAY_HEAD
 207 macro.
 208 A
 209 structure is declared as follows:
 210 .Bd -ragged -offset indent
 211 .Fn SPLAY_HEAD HEADNAME TYPE
 212 .Va head ;
 213 .Ed
 214 .Pp
 215 where
 216 .Fa HEADNAME
 217 is the name of the structure to be defined, and struct
 218 .Fa TYPE
 219 is the type of the elements to be inserted into the tree.
 220 .Pp
 221 The
 222 .Fn SPLAY_ENTRY
 223 macro declares a structure that allows elements to be connected in the tree.
 224 .Pp
 225 In order to use the functions that manipulate the tree structure,
 226 their prototypes need to be declared with the
 227 .Fn SPLAY_PROTOTYPE
 228 macro,
 229 where
 230 .Fa NAME
 231 is a unique identifier for this particular tree.
 232 The
 233 .Fa TYPE
 234 argument is the type of the structure that is being managed
 235 by the tree.
 236 The
 237 .Fa FIELD
 238 argument is the name of the element defined by
 239 .Fn SPLAY_ENTRY .
 240 .Pp
 241 The function bodies are generated with the
 242 .Fn SPLAY_GENERATE
 243 macro.
 244 It takes the same arguments as the
 245 .Fn SPLAY_PROTOTYPE
 246 macro, but should be used only once.
 247 .Pp
 248 Finally,
 249 the
 250 .Fa CMP
 251 argument is the name of a function used to compare tree nodes
 252 with each other.
 253 The function takes two arguments of type
 254 .Vt "struct TYPE *" .
 255 If the first argument is smaller than the second, the function returns a
 256 value smaller than zero.
 257 If they are equal, the function returns zero.
 258 Otherwise, it should return a value greater than zero.
 259 The compare
 260 function defines the order of the tree elements.
 261 .Pp
 262 The
 263 .Fn SPLAY_INIT
 264 macro initializes the tree referenced by
 265 .Fa head .
 266 .Pp
 267 The splay tree can also be initialized statically by using the
 268 .Fn SPLAY_INITIALIZER
 269 macro like this:
 270 .Bd -ragged -offset indent
 271 .Fn SPLAY_HEAD HEADNAME TYPE
 272 .Va head
 273 =
 274 .Fn SPLAY_INITIALIZER &head ;
 275 .Ed
 276 .Pp
 277 The
 278 .Fn SPLAY_INSERT
 279 macro inserts the new element
 280 .Fa elm
 281 into the tree.
 282 .Pp
 283 The
 284 .Fn SPLAY_REMOVE
 285 macro removes the element
 286 .Fa elm
 287 from the tree pointed by
 288 .Fa head .
 289 .Pp
 290 The
 291 .Fn SPLAY_FIND
 292 macro can be used to find a particular element in the tree.
 293 .Bd -literal -offset indent
 294 struct TYPE find, *res;
 295 find.key = 30;
 296 res = SPLAY_FIND(NAME, head, &find);
 297 .Ed
 298 .Pp
 299 The
 300 .Fn SPLAY_ROOT ,
 301 .Fn SPLAY_MIN ,
 302 .Fn SPLAY_MAX ,
 303 and
 304 .Fn SPLAY_NEXT
 305 macros can be used to traverse the tree:
 306 .Bd -literal -offset indent
 307 for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np))
 308 .Ed
 309 .Pp
 310 Or, for simplicity, one can use the
 311 .Fn SPLAY_FOREACH
 312 macro:
 313 .Bd -ragged -offset indent
 314 .Fn SPLAY_FOREACH np NAME head
 315 .Ed
 316 .Pp
 317 The
 318 .Fn SPLAY_EMPTY
 319 macro should be used to check whether a splay tree is empty.
 320 .Sh RED-BLACK TREES
 321 A red-black tree is a binary search tree with the node color as an
 322 extra attribute.
 323 It fulfills a set of conditions:
 324 .Bl -enum -offset indent
 325 .It
 326 Every search path from the root to a leaf consists of the same number of
 327 black nodes.
 328 .It
 329 Each red node (except for the root) has a black parent.
 330 .It
 331 Each leaf node is black.
 332 .El
 333 .Pp
 334 Every operation on a red-black tree is bounded as
 335 .Fn O "lg n" .
 336 The maximum height of a red-black tree is
 337 .Fn 2lg "n + 1" .
 338 .Pp
 339 A red-black tree is headed by a structure defined by the
 340 .Fn RB_HEAD
 341 macro.
 342 A
 343 structure is declared as follows:
 344 .Bd -ragged -offset indent
 345 .Fn RB_HEAD HEADNAME TYPE
 346 .Va head ;
 347 .Ed
 348 .Pp
 349 where
 350 .Fa HEADNAME
 351 is the name of the structure to be defined, and struct
 352 .Fa TYPE
 353 is the type of the elements to be inserted into the tree.
 354 .Pp
 355 The
 356 .Fn RB_ENTRY
 357 macro declares a structure that allows elements to be connected in the tree.
 358 .Pp
 359 In order to use the functions that manipulate the tree structure,
 360 their prototypes need to be declared with the
 361 .Fn RB_PROTOTYPE
 362 or
 363 .Fn RB_PROTOTYPE_STATIC
 364 macro,
 365 where
 366 .Fa NAME
 367 is a unique identifier for this particular tree.
 368 The
 369 .Fa TYPE
 370 argument is the type of the structure that is being managed
 371 by the tree.
 372 The
 373 .Fa FIELD
 374 argument is the name of the element defined by
 375 .Fn RB_ENTRY .
 376 .Pp
 377 The function bodies are generated with the
 378 .Fn RB_GENERATE
 379 or
 380 .Fn RB_GENERATE_STATIC
 381 macro.
 382 These macros take the same arguments as the
 383 .Fn RB_PROTOTYPE
 384 and
 385 .Fn RB_PROTOTYPE_STATIC
 386 macros, but should be used only once.
 387 .Pp
 388 Finally,
 389 the
 390 .Fa CMP
 391 argument is the name of a function used to compare tree nodes
 392 with each other.
 393 The function takes two arguments of type
 394 .Vt "struct TYPE *" .
 395 If the first argument is smaller than the second, the function returns a
 396 value smaller than zero.
 397 If they are equal, the function returns zero.
 398 Otherwise, it should return a value greater than zero.
 399 The compare
 400 function defines the order of the tree elements.
 401 .Pp
 402 The
 403 .Fn RB_INIT
 404 macro initializes the tree referenced by
 405 .Fa head .
 406 .Pp
 407 The red-black tree can also be initialized statically by using the
 408 .Fn RB_INITIALIZER
 409 macro like this:
 410 .Bd -ragged -offset indent
 411 .Fn RB_HEAD HEADNAME TYPE
 412 .Va head
 413 =
 414 .Fn RB_INITIALIZER &head ;
 415 .Ed
 416 .Pp
 417 The
 418 .Fn RB_INSERT
 419 macro inserts the new element
 420 .Fa elm
 421 into the tree.
 422 .Pp
 423 The
 424 .Fn RB_REMOVE
 425 macro removes the element
 426 .Fa elm
 427 from the tree pointed by
 428 .Fa head .
 429 .Pp
 430 The
 431 .Fn RB_FIND
 432 and
 433 .Fn RB_NFIND
 434 macros can be used to find a particular element in the tree.
 435 .Bd -literal -offset indent
 436 struct TYPE find, *res;
 437 find.key = 30;
 438 res = RB_FIND(NAME, head, &find);
 439 .Ed
 440 .Pp
 441 The
 442 .Fn RB_ROOT ,
 443 .Fn RB_MIN ,
 444 .Fn RB_MAX ,
 445 .Fn RB_NEXT ,
 446 and
 447 .Fn RB_PREV
 448 macros can be used to traverse the tree:
 449 .Pp
 450 .Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"
 451 .Pp
 452 Or, for simplicity, one can use the
 453 .Fn RB_FOREACH
 454 or
 455 .Fn RB_FOREACH_REVERSE
 456 macro:
 457 .Bd -ragged -offset indent
 458 .Fn RB_FOREACH np NAME head
 459 .Ed
 460 .Pp
 461 The macros
 462 .Fn RB_FOREACH_SAFE
 463 and
 464 .Fn RB_FOREACH_REVERSE_SAFE
 465 traverse the tree referenced by head
 466 in a forward or reverse direction respectively,
 467 assigning each element in turn to np.
 468 However, unlike their unsafe counterparts,
 469 they permit both the removal of np
 470 as well as freeing it from within the loop safely
 471 without interfering with the traversal.
 472 .Pp
 473 The
 474 .Fn RB_EMPTY
 475 macro should be used to check whether a red-black tree is empty.
 476 .Sh NOTES
 477 Trying to free a tree in the following way is a common error:
 478 .Bd -literal -offset indent
 479 SPLAY_FOREACH(var, NAME, head) {
 480         SPLAY_REMOVE(NAME, head, var);
 481         free(var);
 482 }
 483 free(head);
 484 .Ed
 485 .Pp
 486 Since
 487 .Va var
 488 is freed, the
 489 .Fn FOREACH
 490 macro refers to a pointer that may have been reallocated already.
 491 Proper code needs a second variable.
 492 .Bd -literal -offset indent
 493 for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
 494         nxt = SPLAY_NEXT(NAME, head, var);
 495         SPLAY_REMOVE(NAME, head, var);
 496         free(var);
 497 }
 498 .Ed
 499 .Pp
 500 Both
 501 .Fn RB_INSERT
 502 and
 503 .Fn SPLAY_INSERT
 504 return
 505 .Dv NULL
 506 if the element was inserted in the tree successfully, otherwise they
 507 return a pointer to the element with the colliding key.
 508 .Pp
 509 Accordingly,
 510 .Fn RB_REMOVE
 511 and
 512 .Fn SPLAY_REMOVE
 513 return the pointer to the removed element otherwise they return
 514 .Dv NULL
 515 to indicate an error.
 516 .Sh SEE ALSO
 517 .Xr queue 3
 518 .Sh AUTHORS
 519 The author of the tree macros is
 520 .An Niels Provos .