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 May 8, 2019
  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_PROTOTYPE_INSERT ,
  57 .Nm RB_PROTOTYPE_INSERT_COLOR ,
  58 .Nm RB_PROTOTYPE_REMOVE ,
  59 .Nm RB_PROTOTYPE_REMOVE_COLOR ,
  60 .Nm RB_PROTOTYPE_FIND ,
  61 .Nm RB_PROTOTYPE_NFIND ,
  62 .Nm RB_PROTOTYPE_NEXT ,
  63 .Nm RB_PROTOTYPE_PREV ,
  64 .Nm RB_PROTOTYPE_MINMAX ,
  65 .Nm RB_GENERATE ,
  66 .Nm RB_GENERATE_STATIC ,
  67 .Nm RB_GENERATE_INSERT ,
  68 .Nm RB_GENERATE_INSERT_COLOR ,
  69 .Nm RB_GENERATE_REMOVE ,
  70 .Nm RB_GENERATE_REMOVE_COLOR ,
  71 .Nm RB_GENERATE_FIND ,
  72 .Nm RB_GENERATE_NFIND ,
  73 .Nm RB_GENERATE_NEXT ,
  74 .Nm RB_GENERATE_PREV ,
  75 .Nm RB_GENERATE_MINMAX ,
  76 .Nm RB_ENTRY ,
  77 .Nm RB_HEAD ,
  78 .Nm RB_INITIALIZER ,
  79 .Nm RB_ROOT ,
  80 .Nm RB_EMPTY ,
  81 .Nm RB_NEXT ,
  82 .Nm RB_PREV ,
  83 .Nm RB_MIN ,
  84 .Nm RB_MAX ,
  85 .Nm RB_FIND ,
  86 .Nm RB_NFIND ,
  87 .Nm RB_LEFT ,
  88 .Nm RB_RIGHT ,
  89 .Nm RB_PARENT ,
  90 .Nm RB_FOREACH ,
  91 .Nm RB_FOREACH_FROM ,
  92 .Nm RB_FOREACH_SAFE ,
  93 .Nm RB_FOREACH_REVERSE ,
  94 .Nm RB_FOREACH_REVERSE_FROM ,
  95 .Nm RB_FOREACH_REVERSE_SAFE ,
  96 .Nm RB_INIT ,
  97 .Nm RB_INSERT ,
  98 .Nm RB_REMOVE
  99 .Nd "implementations of splay and red-black trees"
 100 .Sh SYNOPSIS
 101 .In sys/tree.h
 102 .Fn SPLAY_PROTOTYPE NAME TYPE FIELD CMP
 103 .Fn SPLAY_GENERATE NAME TYPE FIELD CMP
 104 .Fn SPLAY_ENTRY TYPE
 105 .Fn SPLAY_HEAD HEADNAME TYPE
 106 .Ft "struct TYPE *"
 107 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
 108 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
 109 .Ft bool
 110 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
 111 .Ft "struct TYPE *"
 112 .Fn SPLAY_NEXT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
 113 .Ft "struct TYPE *"
 114 .Fn SPLAY_MIN NAME "SPLAY_HEAD *head"
 115 .Ft "struct TYPE *"
 116 .Fn SPLAY_MAX NAME "SPLAY_HEAD *head"
 117 .Ft "struct TYPE *"
 118 .Fn SPLAY_FIND NAME "SPLAY_HEAD *head" "struct TYPE *elm"
 119 .Ft "struct TYPE *"
 120 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
 121 .Ft "struct TYPE *"
 122 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
 123 .Fn SPLAY_FOREACH VARNAME NAME "SPLAY_HEAD *head"
 124 .Ft void
 125 .Fn SPLAY_INIT "SPLAY_HEAD *head"
 126 .Ft "struct TYPE *"
 127 .Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
 128 .Ft "struct TYPE *"
 129 .Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm"
 130 .Fn RB_PROTOTYPE NAME TYPE FIELD CMP
 131 .Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
 132 .Fn RB_PROTOTYPE_INSERT NAME TYPE ATTR
 133 .Fn RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
 134 .Fn RB_PROTOTYPE_REMOVE NAME TYPE ATTR
 135 .Fn RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
 136 .Fn RB_PROTOTYPE_FIND NAME TYPE ATTR
 137 .Fn RB_PROTOTYPE_NFIND NAME TYPE ATTR
 138 .Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR
 139 .Fn RB_PROTOTYPE_PREV NAME TYPE ATTR
 140 .Fn RB_PROTOTYPE_MINMAX NAME TYPE ATTR
 141 .Fn RB_GENERATE NAME TYPE FIELD CMP
 142 .Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP
 143 .Fn RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
 144 .Fn RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
 145 .Fn RB_GENERATE_REMOVE NAME TYPE FIELD ATTR
 146 .Fn RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
 147 .Fn RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
 148 .Fn RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
 149 .Fn RB_GENERATE_NEXT NAME TYPE FIELD ATTR
 150 .Fn RB_GENERATE_PREV NAME TYPE FIELD ATTR
 151 .Fn RB_GENERATE_MINMAX NAME TYPE FIELD ATTR
 152 .Fn RB_ENTRY TYPE
 153 .Fn RB_HEAD HEADNAME TYPE
 154 .Fn RB_INITIALIZER "RB_HEAD *head"
 155 .Ft "struct TYPE *"
 156 .Fn RB_ROOT "RB_HEAD *head"
 157 .Ft "bool"
 158 .Fn RB_EMPTY "RB_HEAD *head"
 159 .Ft "struct TYPE *"
 160 .Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm"
 161 .Ft "struct TYPE *"
 162 .Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm"
 163 .Ft "struct TYPE *"
 164 .Fn RB_MIN NAME "RB_HEAD *head"
 165 .Ft "struct TYPE *"
 166 .Fn RB_MAX NAME "RB_HEAD *head"
 167 .Ft "struct TYPE *"
 168 .Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm"
 169 .Ft "struct TYPE *"
 170 .Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm"
 171 .Ft "struct TYPE *"
 172 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
 173 .Ft "struct TYPE *"
 174 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
 175 .Ft "struct TYPE *"
 176 .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
 177 .Fn RB_FOREACH VARNAME NAME "RB_HEAD *head"
 178 .Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
 179 .Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
 180 .Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head"
 181 .Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
 182 .Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
 183 .Ft void
 184 .Fn RB_INIT "RB_HEAD *head"
 185 .Ft "struct TYPE *"
 186 .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
 187 .Ft "struct TYPE *"
 188 .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
 189 .Sh DESCRIPTION
 190 These macros define data structures for different types of trees:
 191 splay trees and red-black trees.
 192 .Pp
 193 In the macro definitions,
 194 .Fa TYPE
 195 is the name tag of a user defined structure that must contain a field of type
 196 .Vt SPLAY_ENTRY ,
 197 or
 198 .Vt RB_ENTRY ,
 199 named
 200 .Fa ENTRYNAME .
 201 The argument
 202 .Fa HEADNAME
 203 is the name tag of a user defined structure that must be declared
 204 using the macros
 205 .Fn SPLAY_HEAD ,
 206 or
 207 .Fn RB_HEAD .
 208 The argument
 209 .Fa NAME
 210 has to be a unique name prefix for every tree that is defined.
 211 .Pp
 212 The function prototypes are declared with
 213 .Fn SPLAY_PROTOTYPE ,
 214 .Fn RB_PROTOTYPE ,
 215 or
 216 .Fn RB_PROTOTYPE_STATIC .
 217 The function bodies are generated with
 218 .Fn SPLAY_GENERATE ,
 219 .Fn RB_GENERATE ,
 220 or
 221 .Fn RB_GENERATE_STATIC .
 222 See the examples below for further explanation of how these macros are used.
 223 .Sh SPLAY TREES
 224 A splay tree is a self-organizing data structure.
 225 Every operation on the tree causes a splay to happen.
 226 The splay moves the requested
 227 node to the root of the tree and partly rebalances it.
 228 .Pp
 229 This has the benefit that request locality causes faster lookups as
 230 the requested nodes move to the top of the tree.
 231 On the other hand, every lookup causes memory writes.
 232 .Pp
 233 The Balance Theorem bounds the total access time for
 234 .Ar m
 235 operations and
 236 .Ar n
 237 inserts on an initially empty tree as
 238 .Fn O "\*[lp]m + n\*[rp]lg n" .
 239 The
 240 amortized cost for a sequence of
 241 .Ar m
 242 accesses to a splay tree is
 243 .Fn O "lg n" .
 244 .Pp
 245 A splay tree is headed by a structure defined by the
 246 .Fn SPLAY_HEAD
 247 macro.
 248 A
 249 structure is declared as follows:
 250 .Bd -ragged -offset indent
 251 .Fn SPLAY_HEAD HEADNAME TYPE
 252 .Va head ;
 253 .Ed
 254 .Pp
 255 where
 256 .Fa HEADNAME
 257 is the name of the structure to be defined, and struct
 258 .Fa TYPE
 259 is the type of the elements to be inserted into the tree.
 260 .Pp
 261 The
 262 .Fn SPLAY_ENTRY
 263 macro declares a structure that allows elements to be connected in the tree.
 264 .Pp
 265 In order to use the functions that manipulate the tree structure,
 266 their prototypes need to be declared with the
 267 .Fn SPLAY_PROTOTYPE
 268 macro,
 269 where
 270 .Fa NAME
 271 is a unique identifier for this particular tree.
 272 The
 273 .Fa TYPE
 274 argument is the type of the structure that is being managed
 275 by the tree.
 276 The
 277 .Fa FIELD
 278 argument is the name of the element defined by
 279 .Fn SPLAY_ENTRY .
 280 .Pp
 281 The function bodies are generated with the
 282 .Fn SPLAY_GENERATE
 283 macro.
 284 It takes the same arguments as the
 285 .Fn SPLAY_PROTOTYPE
 286 macro, but should be used only once.
 287 .Pp
 288 Finally,
 289 the
 290 .Fa CMP
 291 argument is the name of a function used to compare tree nodes
 292 with each other.
 293 The function takes two arguments of type
 294 .Vt "struct TYPE *" .
 295 If the first argument is smaller than the second, the function returns a
 296 value smaller than zero.
 297 If they are equal, the function returns zero.
 298 Otherwise, it should return a value greater than zero.
 299 The compare
 300 function defines the order of the tree elements.
 301 .Pp
 302 The
 303 .Fn SPLAY_INIT
 304 macro initializes the tree referenced by
 305 .Fa head .
 306 .Pp
 307 The splay tree can also be initialized statically by using the
 308 .Fn SPLAY_INITIALIZER
 309 macro like this:
 310 .Bd -ragged -offset indent
 311 .Fn SPLAY_HEAD HEADNAME TYPE
 312 .Va head
 313 =
 314 .Fn SPLAY_INITIALIZER &head ;
 315 .Ed
 316 .Pp
 317 The
 318 .Fn SPLAY_INSERT
 319 macro inserts the new element
 320 .Fa elm
 321 into the tree.
 322 .Pp
 323 The
 324 .Fn SPLAY_REMOVE
 325 macro removes the element
 326 .Fa elm
 327 from the tree pointed by
 328 .Fa head .
 329 .Pp
 330 The
 331 .Fn SPLAY_FIND
 332 macro can be used to find a particular element in the tree.
 333 .Bd -literal -offset indent
 334 struct TYPE find, *res;
 335 find.key = 30;
 336 res = SPLAY_FIND(NAME, head, &find);
 337 .Ed
 338 .Pp
 339 The
 340 .Fn SPLAY_ROOT ,
 341 .Fn SPLAY_MIN ,
 342 .Fn SPLAY_MAX ,
 343 and
 344 .Fn SPLAY_NEXT
 345 macros can be used to traverse the tree:
 346 .Bd -literal -offset indent
 347 for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np))
 348 .Ed
 349 .Pp
 350 Or, for simplicity, one can use the
 351 .Fn SPLAY_FOREACH
 352 macro:
 353 .Bd -ragged -offset indent
 354 .Fn SPLAY_FOREACH np NAME head
 355 .Ed
 356 .Pp
 357 The
 358 .Fn SPLAY_EMPTY
 359 macro should be used to check whether a splay tree is empty.
 360 .Sh RED-BLACK TREES
 361 A red-black tree is a binary search tree with the node color as an
 362 extra attribute.
 363 It fulfills a set of conditions:
 364 .Bl -enum -offset indent
 365 .It
 366 Every search path from the root to a leaf consists of the same number of
 367 black nodes.
 368 .It
 369 Each red node (except for the root) has a black parent.
 370 .It
 371 Each leaf node is black.
 372 .El
 373 .Pp
 374 Every operation on a red-black tree is bounded as
 375 .Fn O "lg n" .
 376 The maximum height of a red-black tree is
 377 .Fn 2lg "n + 1" .
 378 .Pp
 379 A red-black tree is headed by a structure defined by the
 380 .Fn RB_HEAD
 381 macro.
 382 A
 383 structure is declared as follows:
 384 .Bd -ragged -offset indent
 385 .Fn RB_HEAD HEADNAME TYPE
 386 .Va head ;
 387 .Ed
 388 .Pp
 389 where
 390 .Fa HEADNAME
 391 is the name of the structure to be defined, and struct
 392 .Fa TYPE
 393 is the type of the elements to be inserted into the tree.
 394 .Pp
 395 The
 396 .Fn RB_ENTRY
 397 macro declares a structure that allows elements to be connected in the tree.
 398 .Pp
 399 In order to use the functions that manipulate the tree structure,
 400 their prototypes need to be declared with the
 401 .Fn RB_PROTOTYPE
 402 or
 403 .Fn RB_PROTOTYPE_STATIC
 404 macro,
 405 where
 406 .Fa NAME
 407 is a unique identifier for this particular tree.
 408 The
 409 .Fa TYPE
 410 argument is the type of the structure that is being managed
 411 by the tree.
 412 The
 413 .Fa FIELD
 414 argument is the name of the element defined by
 415 .Fn RB_ENTRY .
 416 Individual prototypes can be declared with
 417 .Fn RB_PROTOTYPE_INSERT ,
 418 .Fn RB_PROTOTYPE_INSERT_COLOR ,
 419 .Fn RB_PROTOTYPE_REMOVE ,
 420 .Fn RB_PROTOTYPE_REMOVE_COLOR ,
 421 .Fn RB_PROTOTYPE_FIND ,
 422 .Fn RB_PROTOTYPE_NFIND ,
 423 .Fn RB_PROTOTYPE_NEXT ,
 424 .Fn RB_PROTOTYPE_PREV ,
 425 and
 426 .Fn RB_PROTOTYPE_MINMAX
 427 in case not all functions are required.
 428 The individual prototype macros expect
 429 .Fa NAME ,
 430 .Fa TYPE ,
 431 and
 432 .Fa ATTR
 433 arguments.
 434 The
 435 .Fa ATTR
 436 argument must be empty for global functions or
 437 .Fa static
 438 for static functions.
 439 .Pp
 440 The function bodies are generated with the
 441 .Fn RB_GENERATE
 442 or
 443 .Fn RB_GENERATE_STATIC
 444 macro.
 445 These macros take the same arguments as the
 446 .Fn RB_PROTOTYPE
 447 and
 448 .Fn RB_PROTOTYPE_STATIC
 449 macros, but should be used only once.
 450 As an alternative individual function bodies are generated with the
 451 .Fn RB_GENERATE_INSERT ,
 452 .Fn RB_GENERATE_INSERT_COLOR ,
 453 .Fn RB_GENERATE_REMOVE ,
 454 .Fn RB_GENERATE_REMOVE_COLOR ,
 455 .Fn RB_GENERATE_FIND ,
 456 .Fn RB_GENERATE_NFIND ,
 457 .Fn RB_GENERATE_NEXT ,
 458 .Fn RB_GENERATE_PREV ,
 459 and
 460 .Fn RB_GENERATE_MINMAX
 461 macros.
 462 .Pp
 463 Finally,
 464 the
 465 .Fa CMP
 466 argument is the name of a function used to compare tree nodes
 467 with each other.
 468 The function takes two arguments of type
 469 .Vt "struct TYPE *" .
 470 If the first argument is smaller than the second, the function returns a
 471 value smaller than zero.
 472 If they are equal, the function returns zero.
 473 Otherwise, it should return a value greater than zero.
 474 The compare
 475 function defines the order of the tree elements.
 476 .Pp
 477 The
 478 .Fn RB_INIT
 479 macro initializes the tree referenced by
 480 .Fa head .
 481 .Pp
 482 The red-black tree can also be initialized statically by using the
 483 .Fn RB_INITIALIZER
 484 macro like this:
 485 .Bd -ragged -offset indent
 486 .Fn RB_HEAD HEADNAME TYPE
 487 .Va head
 488 =
 489 .Fn RB_INITIALIZER &head ;
 490 .Ed
 491 .Pp
 492 The
 493 .Fn RB_INSERT
 494 macro inserts the new element
 495 .Fa elm
 496 into the tree.
 497 .Pp
 498 The
 499 .Fn RB_REMOVE
 500 macro removes the element
 501 .Fa elm
 502 from the tree pointed by
 503 .Fa head .
 504 .Pp
 505 The
 506 .Fn RB_FIND
 507 and
 508 .Fn RB_NFIND
 509 macros can be used to find a particular element in the tree.
 510 .Bd -literal -offset indent
 511 struct TYPE find, *res;
 512 find.key = 30;
 513 res = RB_FIND(NAME, head, &find);
 514 .Ed
 515 .Pp
 516 The
 517 .Fn RB_ROOT ,
 518 .Fn RB_MIN ,
 519 .Fn RB_MAX ,
 520 .Fn RB_NEXT ,
 521 and
 522 .Fn RB_PREV
 523 macros can be used to traverse the tree:
 524 .Pp
 525 .Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"
 526 .Pp
 527 Or, for simplicity, one can use the
 528 .Fn RB_FOREACH
 529 or
 530 .Fn RB_FOREACH_REVERSE
 531 macro:
 532 .Bd -ragged -offset indent
 533 .Fn RB_FOREACH np NAME head
 534 .Ed
 535 .Pp
 536 The macros
 537 .Fn RB_FOREACH_SAFE
 538 and
 539 .Fn RB_FOREACH_REVERSE_SAFE
 540 traverse the tree referenced by head
 541 in a forward or reverse direction respectively,
 542 assigning each element in turn to np.
 543 However, unlike their unsafe counterparts,
 544 they permit both the removal of np
 545 as well as freeing it from within the loop safely
 546 without interfering with the traversal.
 547 .Pp
 548 Both
 549 .Fn RB_FOREACH_FROM
 550 and
 551 .Fn RB_FOREACH_REVERSE_FROM
 552 may be used to continue an interrupted traversal
 553 in a forward or reverse direction respectively.
 554 The head pointer is not required.
 555 The pointer to the node from where to resume the traversal
 556 should be passed as their last argument,
 557 and will be overwritten to provide safe traversal.
 558 .Pp
 559 The
 560 .Fn RB_EMPTY
 561 macro should be used to check whether a red-black tree is empty.
 562 .Sh EXAMPLES
 563 The following example demonstrates how to declare a red-black tree
 564 holding integers.
 565 Values are inserted into it and the contents of the tree are printed
 566 in order.
 567 Lastly, the internal structure of the tree is printed.
 568 .Bd -literal -offset 3n
 569 #include <sys/tree.h>
 570 #include <err.h>
 571 #include <stdio.h>
 572 #include <stdlib.h>
 573
 574 struct node {
 575         RB_ENTRY(node) entry;
 576         int i;
 577 };
 578
 579 int
 580 intcmp(struct node *e1, struct node *e2)
 581 {
 582         return (e1->i < e2->i ? -1 : e1->i > e2->i);
 583 }
 584
 585 RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);
 586 RB_GENERATE(inttree, node, entry, intcmp)
 587
 588 int testdata[] = {
 589         20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18,
 590         7, 11, 14
 591 };
 592
 593 void
 594 print_tree(struct node *n)
 595 {
 596         struct node *left, *right;
 597
 598         if (n == NULL) {
 599                 printf("nil");
 600                 return;
 601         }
 602         left = RB_LEFT(n, entry);
 603         right = RB_RIGHT(n, entry);
 604         if (left == NULL && right == NULL)
 605                 printf("%d", n->i);
 606         else {
 607                 printf("%d(", n->i);
 608                 print_tree(left);
 609                 printf(",");
 610                 print_tree(right);
 611                 printf(")");
 612         }
 613 }
 614
 615 int
 616 main(void)
 617 {
 618         int i;
 619         struct node *n;
 620
 621         for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) {
 622                 if ((n = malloc(sizeof(struct node))) == NULL)
 623                         err(1, NULL);
 624                 n->i = testdata[i];
 625                 RB_INSERT(inttree, &head, n);
 626         }
 627
 628         RB_FOREACH(n, inttree, &head) {
 629                 printf("%d\en", n->i);
 630         }
 631         print_tree(RB_ROOT(&head));
 632         printf("\en");
 633         return (0);
 634 }
 635 .Ed
 636 .Sh NOTES
 637 Trying to free a tree in the following way is a common error:
 638 .Bd -literal -offset indent
 639 SPLAY_FOREACH(var, NAME, head) {
 640         SPLAY_REMOVE(NAME, head, var);
 641         free(var);
 642 }
 643 free(head);
 644 .Ed
 645 .Pp
 646 Since
 647 .Va var
 648 is freed, the
 649 .Fn FOREACH
 650 macro refers to a pointer that may have been reallocated already.
 651 Proper code needs a second variable.
 652 .Bd -literal -offset indent
 653 for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
 654         nxt = SPLAY_NEXT(NAME, head, var);
 655         SPLAY_REMOVE(NAME, head, var);
 656         free(var);
 657 }
 658 .Ed
 659 .Pp
 660 Both
 661 .Fn RB_INSERT
 662 and
 663 .Fn SPLAY_INSERT
 664 return
 665 .Dv NULL
 666 if the element was inserted in the tree successfully, otherwise they
 667 return a pointer to the element with the colliding key.
 668 .Pp
 669 Accordingly,
 670 .Fn RB_REMOVE
 671 and
 672 .Fn SPLAY_REMOVE
 673 return the pointer to the removed element otherwise they return
 674 .Dv NULL
 675 to indicate an error.
 676 .Sh SEE ALSO
 677 .Xr queue 3
 678 .Sh AUTHORS
 679 The author of the tree macros is
 680 .An Niels Provos .