share/man/man3/tree.3

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