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 10, 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_FROM ,
  74 .Nm RB_FOREACH_SAFE ,
  75 .Nm RB_FOREACH_REVERSE ,
  76 .Nm RB_FOREACH_REVERSE_FROM ,
  77 .Nm RB_FOREACH_REVERSE_SAFE ,
  78 .Nm RB_INIT ,
  79 .Nm RB_INSERT ,
  80 .Nm RB_REMOVE
  81 .Nd "implementations of splay and red-black trees"
  82 .Sh SYNOPSIS
  83 .In sys/tree.h
  84 .Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP
  85 .Fn SPLAY_GENERATE NAME TYPE FIELD CMP
  86 .Fn SPLAY_ENTRY TYPE
  87 .Fn SPLAY_HEAD HEADNAME TYPE
  88 .Ft "struct TYPE *"
  89 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
  90 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
  91 .Ft bool
  92 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
  93 .Ft "struct TYPE *"
  94 .Fn SPLAY_NEXT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
  95 .Ft "struct TYPE *"
  96 .Fn SPLAY_MIN NAME "SPLAY_HEAD *head"
  97 .Ft "struct TYPE *"
  98 .Fn SPLAY_MAX NAME "SPLAY_HEAD *head"
  99 .Ft "struct TYPE *"
 100 .Fn SPLAY_FIND NAME "SPLAY_HEAD *head" "struct TYPE *elm"
 101 .Ft "struct TYPE *"
 102 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
 103 .Ft "struct TYPE *"
 104 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
 105 .Fn SPLAY_FOREACH VARNAME NAME "SPLAY_HEAD *head"
 106 .Ft void
 107 .Fn SPLAY_INIT "SPLAY_HEAD *head"
 108 .Ft "struct TYPE *"
 109 .Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
 110 .Ft "struct TYPE *"
 111 .Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm"
 112 .Fn RB_PROTOTYPE NAME TYPE FIELD CMP
 113 .Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
 114 .Fn RB_GENERATE NAME TYPE FIELD CMP
 115 .Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP
 116 .Fn RB_ENTRY TYPE
 117 .Fn RB_HEAD HEADNAME TYPE
 118 .Fn RB_INITIALIZER "RB_HEAD *head"
 119 .Ft "struct TYPE *"
 120 .Fn RB_ROOT "RB_HEAD *head"
 121 .Ft "bool"
 122 .Fn RB_EMPTY "RB_HEAD *head"
 123 .Ft "struct TYPE *"
 124 .Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm"
 125 .Ft "struct TYPE *"
 126 .Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm"
 127 .Ft "struct TYPE *"
 128 .Fn RB_MIN NAME "RB_HEAD *head"
 129 .Ft "struct TYPE *"
 130 .Fn RB_MAX NAME "RB_HEAD *head"
 131 .Ft "struct TYPE *"
 132 .Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm"
 133 .Ft "struct TYPE *"
 134 .Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm"
 135 .Ft "struct TYPE *"
 136 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
 137 .Ft "struct TYPE *"
 138 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
 139 .Ft "struct TYPE *"
 140 .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
 141 .Fn RB_FOREACH VARNAME NAME "RB_HEAD *head"
 142 .Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
 143 .Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
 144 .Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head"
 145 .Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
 146 .Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
 147 .Ft void
 148 .Fn RB_INIT "RB_HEAD *head"
 149 .Ft "struct TYPE *"
 150 .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
 151 .Ft "struct TYPE *"
 152 .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
 153 .Sh DESCRIPTION
 154 These macros define data structures for different types of trees:
 155 splay trees and red-black trees.
 156 .Pp
 157 In the macro definitions,
 158 .Fa TYPE
 159 is the name tag of a user defined structure that must contain a field of type
 160 .Vt SPLAY_ENTRY ,
 161 or
 162 .Vt RB_ENTRY ,
 163 named
 164 .Fa ENTRYNAME .
 165 The argument
 166 .Fa HEADNAME
 167 is the name tag of a user defined structure that must be declared
 168 using the macros
 169 .Fn SPLAY_HEAD ,
 170 or
 171 .Fn RB_HEAD .
 172 The argument
 173 .Fa NAME
 174 has to be a unique name prefix for every tree that is defined.
 175 .Pp
 176 The function prototypes are declared with
 177 .Fn SPLAY_PROTOTYPE ,
 178 .Fn RB_PROTOTYPE ,
 179 or
 180 .Fn RB_PROTOTYPE_STATIC .
 181 The function bodies are generated with
 182 .Fn SPLAY_GENERATE ,
 183 .Fn RB_GENERATE ,
 184 or
 185 .Fn RB_GENERATE_STATIC .
 186 See the examples below for further explanation of how these macros are used.
 187 .Sh SPLAY TREES
 188 A splay tree is a self-organizing data structure.
 189 Every operation on the tree causes a splay to happen.
 190 The splay moves the requested
 191 node to the root of the tree and partly rebalances it.
 192 .Pp
 193 This has the benefit that request locality causes faster lookups as
 194 the requested nodes move to the top of the tree.
 195 On the other hand, every lookup causes memory writes.
 196 .Pp
 197 The Balance Theorem bounds the total access time for
 198 .Ar m
 199 operations and
 200 .Ar n
 201 inserts on an initially empty tree as
 202 .Fn O "\*[lp]m + n\*[rp]lg n" .
 203 The
 204 amortized cost for a sequence of
 205 .Ar m
 206 accesses to a splay tree is
 207 .Fn O "lg n" .
 208 .Pp
 209 A splay tree is headed by a structure defined by the
 210 .Fn SPLAY_HEAD
 211 macro.
 212 A
 213 structure is declared as follows:
 214 .Bd -ragged -offset indent
 215 .Fn SPLAY_HEAD HEADNAME TYPE
 216 .Va head ;
 217 .Ed
 218 .Pp
 219 where
 220 .Fa HEADNAME
 221 is the name of the structure to be defined, and struct
 222 .Fa TYPE
 223 is the type of the elements to be inserted into the tree.
 224 .Pp
 225 The
 226 .Fn SPLAY_ENTRY
 227 macro declares a structure that allows elements to be connected in the tree.
 228 .Pp
 229 In order to use the functions that manipulate the tree structure,
 230 their prototypes need to be declared with the
 231 .Fn SPLAY_PROTOTYPE
 232 macro,
 233 where
 234 .Fa NAME
 235 is a unique identifier for this particular tree.
 236 The
 237 .Fa TYPE
 238 argument is the type of the structure that is being managed
 239 by the tree.
 240 The
 241 .Fa FIELD
 242 argument is the name of the element defined by
 243 .Fn SPLAY_ENTRY .
 244 .Pp
 245 The function bodies are generated with the
 246 .Fn SPLAY_GENERATE
 247 macro.
 248 It takes the same arguments as the
 249 .Fn SPLAY_PROTOTYPE
 250 macro, but should be used only once.
 251 .Pp
 252 Finally,
 253 the
 254 .Fa CMP
 255 argument is the name of a function used to compare tree nodes
 256 with each other.
 257 The function takes two arguments of type
 258 .Vt "struct TYPE *" .
 259 If the first argument is smaller than the second, the function returns a
 260 value smaller than zero.
 261 If they are equal, the function returns zero.
 262 Otherwise, it should return a value greater than zero.
 263 The compare
 264 function defines the order of the tree elements.
 265 .Pp
 266 The
 267 .Fn SPLAY_INIT
 268 macro initializes the tree referenced by
 269 .Fa head .
 270 .Pp
 271 The splay tree can also be initialized statically by using the
 272 .Fn SPLAY_INITIALIZER
 273 macro like this:
 274 .Bd -ragged -offset indent
 275 .Fn SPLAY_HEAD HEADNAME TYPE
 276 .Va head
 277 =
 278 .Fn SPLAY_INITIALIZER &head ;
 279 .Ed
 280 .Pp
 281 The
 282 .Fn SPLAY_INSERT
 283 macro inserts the new element
 284 .Fa elm
 285 into the tree.
 286 .Pp
 287 The
 288 .Fn SPLAY_REMOVE
 289 macro removes the element
 290 .Fa elm
 291 from the tree pointed by
 292 .Fa head .
 293 .Pp
 294 The
 295 .Fn SPLAY_FIND
 296 macro can be used to find a particular element in the tree.
 297 .Bd -literal -offset indent
 298 struct TYPE find, *res;
 299 find.key = 30;
 300 res = SPLAY_FIND(NAME, head, &find);
 301 .Ed
 302 .Pp
 303 The
 304 .Fn SPLAY_ROOT ,
 305 .Fn SPLAY_MIN ,
 306 .Fn SPLAY_MAX ,
 307 and
 308 .Fn SPLAY_NEXT
 309 macros can be used to traverse the tree:
 310 .Bd -literal -offset indent
 311 for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np))
 312 .Ed
 313 .Pp
 314 Or, for simplicity, one can use the
 315 .Fn SPLAY_FOREACH
 316 macro:
 317 .Bd -ragged -offset indent
 318 .Fn SPLAY_FOREACH np NAME head
 319 .Ed
 320 .Pp
 321 The
 322 .Fn SPLAY_EMPTY
 323 macro should be used to check whether a splay tree is empty.
 324 .Sh RED-BLACK TREES
 325 A red-black tree is a binary search tree with the node color as an
 326 extra attribute.
 327 It fulfills a set of conditions:
 328 .Bl -enum -offset indent
 329 .It
 330 Every search path from the root to a leaf consists of the same number of
 331 black nodes.
 332 .It
 333 Each red node (except for the root) has a black parent.
 334 .It
 335 Each leaf node is black.
 336 .El
 337 .Pp
 338 Every operation on a red-black tree is bounded as
 339 .Fn O "lg n" .
 340 The maximum height of a red-black tree is
 341 .Fn 2lg "n + 1" .
 342 .Pp
 343 A red-black tree is headed by a structure defined by the
 344 .Fn RB_HEAD
 345 macro.
 346 A
 347 structure is declared as follows:
 348 .Bd -ragged -offset indent
 349 .Fn RB_HEAD HEADNAME TYPE
 350 .Va head ;
 351 .Ed
 352 .Pp
 353 where
 354 .Fa HEADNAME
 355 is the name of the structure to be defined, and struct
 356 .Fa TYPE
 357 is the type of the elements to be inserted into the tree.
 358 .Pp
 359 The
 360 .Fn RB_ENTRY
 361 macro declares a structure that allows elements to be connected in the tree.
 362 .Pp
 363 In order to use the functions that manipulate the tree structure,
 364 their prototypes need to be declared with the
 365 .Fn RB_PROTOTYPE
 366 or
 367 .Fn RB_PROTOTYPE_STATIC
 368 macro,
 369 where
 370 .Fa NAME
 371 is a unique identifier for this particular tree.
 372 The
 373 .Fa TYPE
 374 argument is the type of the structure that is being managed
 375 by the tree.
 376 The
 377 .Fa FIELD
 378 argument is the name of the element defined by
 379 .Fn RB_ENTRY .
 380 .Pp
 381 The function bodies are generated with the
 382 .Fn RB_GENERATE
 383 or
 384 .Fn RB_GENERATE_STATIC
 385 macro.
 386 These macros take the same arguments as the
 387 .Fn RB_PROTOTYPE
 388 and
 389 .Fn RB_PROTOTYPE_STATIC
 390 macros, but should be used only once.
 391 .Pp
 392 Finally,
 393 the
 394 .Fa CMP
 395 argument is the name of a function used to compare tree nodes
 396 with each other.
 397 The function takes two arguments of type
 398 .Vt "struct TYPE *" .
 399 If the first argument is smaller than the second, the function returns a
 400 value smaller than zero.
 401 If they are equal, the function returns zero.
 402 Otherwise, it should return a value greater than zero.
 403 The compare
 404 function defines the order of the tree elements.
 405 .Pp
 406 The
 407 .Fn RB_INIT
 408 macro initializes the tree referenced by
 409 .Fa head .
 410 .Pp
 411 The red-black tree can also be initialized statically by using the
 412 .Fn RB_INITIALIZER
 413 macro like this:
 414 .Bd -ragged -offset indent
 415 .Fn RB_HEAD HEADNAME TYPE
 416 .Va head
 417 =
 418 .Fn RB_INITIALIZER &head ;
 419 .Ed
 420 .Pp
 421 The
 422 .Fn RB_INSERT
 423 macro inserts the new element
 424 .Fa elm
 425 into the tree.
 426 .Pp
 427 The
 428 .Fn RB_REMOVE
 429 macro removes the element
 430 .Fa elm
 431 from the tree pointed by
 432 .Fa head .
 433 .Pp
 434 The
 435 .Fn RB_FIND
 436 and
 437 .Fn RB_NFIND
 438 macros can be used to find a particular element in the tree.
 439 .Bd -literal -offset indent
 440 struct TYPE find, *res;
 441 find.key = 30;
 442 res = RB_FIND(NAME, head, &find);
 443 .Ed
 444 .Pp
 445 The
 446 .Fn RB_ROOT ,
 447 .Fn RB_MIN ,
 448 .Fn RB_MAX ,
 449 .Fn RB_NEXT ,
 450 and
 451 .Fn RB_PREV
 452 macros can be used to traverse the tree:
 453 .Pp
 454 .Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"
 455 .Pp
 456 Or, for simplicity, one can use the
 457 .Fn RB_FOREACH
 458 or
 459 .Fn RB_FOREACH_REVERSE
 460 macro:
 461 .Bd -ragged -offset indent
 462 .Fn RB_FOREACH np NAME head
 463 .Ed
 464 .Pp
 465 The macros
 466 .Fn RB_FOREACH_SAFE
 467 and
 468 .Fn RB_FOREACH_REVERSE_SAFE
 469 traverse the tree referenced by head
 470 in a forward or reverse direction respectively,
 471 assigning each element in turn to np.
 472 However, unlike their unsafe counterparts,
 473 they permit both the removal of np
 474 as well as freeing it from within the loop safely
 475 without interfering with the traversal.
 476 .Pp
 477 Both
 478 .Fn RB_FOREACH_FROM
 479 and
 480 .Fn RB_FOREACH_REVERSE_FROM
 481 may be used to continue an interrupted traversal
 482 in a forward or reverse direction respectively.
 483 The head pointer is not required.
 484 The pointer to the node from where to resume the traversal
 485 should be passed as their last argument,
 486 and will be overwritten to provide safe traversal.
 487 .Pp
 488 The
 489 .Fn RB_EMPTY
 490 macro should be used to check whether a red-black tree is empty.
 491 .Sh NOTES
 492 Trying to free a tree in the following way is a common error:
 493 .Bd -literal -offset indent
 494 SPLAY_FOREACH(var, NAME, head) {
 495         SPLAY_REMOVE(NAME, head, var);
 496         free(var);
 497 }
 498 free(head);
 499 .Ed
 500 .Pp
 501 Since
 502 .Va var
 503 is freed, the
 504 .Fn FOREACH
 505 macro refers to a pointer that may have been reallocated already.
 506 Proper code needs a second variable.
 507 .Bd -literal -offset indent
 508 for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
 509         nxt = SPLAY_NEXT(NAME, head, var);
 510         SPLAY_REMOVE(NAME, head, var);
 511         free(var);
 512 }
 513 .Ed
 514 .Pp
 515 Both
 516 .Fn RB_INSERT
 517 and
 518 .Fn SPLAY_INSERT
 519 return
 520 .Dv NULL
 521 if the element was inserted in the tree successfully, otherwise they
 522 return a pointer to the element with the colliding key.
 523 .Pp
 524 Accordingly,
 525 .Fn RB_REMOVE
 526 and
 527 .Fn SPLAY_REMOVE
 528 return the pointer to the removed element otherwise they return
 529 .Dv NULL
 530 to indicate an error.
 531 .Sh SEE ALSO
 532 .Xr queue 3
 533 .Sh AUTHORS
 534 The author of the tree macros is
 535 .An Niels Provos .