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