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