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 190These macros define data structures for different types of trees: 191splay trees and red-black trees. 192.Pp 193In the macro definitions, 194.Fa TYPE 195is the name tag of a user defined structure that must contain a field of type 196.Vt SPLAY_ENTRY , 197or 198.Vt RB_ENTRY , 199named 200.Fa ENTRYNAME . 201The argument 202.Fa HEADNAME 203is the name tag of a user defined structure that must be declared 204using the macros 205.Fn SPLAY_HEAD , 206or 207.Fn RB_HEAD . 208The argument 209.Fa NAME 210has to be a unique name prefix for every tree that is defined. 211.Pp 212The function prototypes are declared with 213.Fn SPLAY_PROTOTYPE , 214.Fn RB_PROTOTYPE , 215or 216.Fn RB_PROTOTYPE_STATIC . 217The function bodies are generated with 218.Fn SPLAY_GENERATE , 219.Fn RB_GENERATE , 220or 221.Fn RB_GENERATE_STATIC . 222See the examples below for further explanation of how these macros are used. 223.Sh SPLAY TREES 224A splay tree is a self-organizing data structure. 225Every operation on the tree causes a splay to happen. 226The splay moves the requested 227node to the root of the tree and partly rebalances it. 228.Pp 229This has the benefit that request locality causes faster lookups as 230the requested nodes move to the top of the tree. 231On the other hand, every lookup causes memory writes. 232.Pp 233The Balance Theorem bounds the total access time for 234.Ar m 235operations and 236.Ar n 237inserts on an initially empty tree as 238.Fn O "\*[lp]m + n\*[rp]lg n" . 239The 240amortized cost for a sequence of 241.Ar m 242accesses to a splay tree is 243.Fn O "lg n" . 244.Pp 245A splay tree is headed by a structure defined by the 246.Fn SPLAY_HEAD 247macro. 248A 249structure is declared as follows: 250.Bd -ragged -offset indent 251.Fn SPLAY_HEAD HEADNAME TYPE 252.Va head ; 253.Ed 254.Pp 255where 256.Fa HEADNAME 257is the name of the structure to be defined, and struct 258.Fa TYPE 259is the type of the elements to be inserted into the tree. 260.Pp 261The 262.Fn SPLAY_ENTRY 263macro declares a structure that allows elements to be connected in the tree. 264.Pp 265In order to use the functions that manipulate the tree structure, 266their prototypes need to be declared with the 267.Fn SPLAY_PROTOTYPE 268macro, 269where 270.Fa NAME 271is a unique identifier for this particular tree. 272The 273.Fa TYPE 274argument is the type of the structure that is being managed 275by the tree. 276The 277.Fa FIELD 278argument is the name of the element defined by 279.Fn SPLAY_ENTRY . 280.Pp 281The function bodies are generated with the 282.Fn SPLAY_GENERATE 283macro. 284It takes the same arguments as the 285.Fn SPLAY_PROTOTYPE 286macro, but should be used only once. 287.Pp 288Finally, 289the 290.Fa CMP 291argument is the name of a function used to compare tree nodes 292with each other. 293The function takes two arguments of type 294.Vt "struct TYPE *" . 295If the first argument is smaller than the second, the function returns a 296value smaller than zero. 297If they are equal, the function returns zero. 298Otherwise, it should return a value greater than zero. 299The compare 300function defines the order of the tree elements. 301.Pp 302The 303.Fn SPLAY_INIT 304macro initializes the tree referenced by 305.Fa head . 306.Pp 307The splay tree can also be initialized statically by using the 308.Fn SPLAY_INITIALIZER 309macro 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 317The 318.Fn SPLAY_INSERT 319macro inserts the new element 320.Fa elm 321into the tree. 322.Pp 323The 324.Fn SPLAY_REMOVE 325macro removes the element 326.Fa elm 327from the tree pointed by 328.Fa head . 329.Pp 330The 331.Fn SPLAY_FIND 332macro can be used to find a particular element in the tree. 333.Bd -literal -offset indent 334struct TYPE find, *res; 335find.key = 30; 336res = SPLAY_FIND(NAME, head, &find); 337.Ed 338.Pp 339The 340.Fn SPLAY_ROOT , 341.Fn SPLAY_MIN , 342.Fn SPLAY_MAX , 343and 344.Fn SPLAY_NEXT 345macros can be used to traverse the tree: 346.Bd -literal -offset indent 347for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np)) 348.Ed 349.Pp 350Or, for simplicity, one can use the 351.Fn SPLAY_FOREACH 352macro: 353.Bd -ragged -offset indent 354.Fn SPLAY_FOREACH np NAME head 355.Ed 356.Pp 357The 358.Fn SPLAY_EMPTY 359macro should be used to check whether a splay tree is empty. 360.Sh RED-BLACK TREES 361A red-black tree is a binary search tree with the node color as an 362extra attribute. 363It fulfills a set of conditions: 364.Bl -enum -offset indent 365.It 366Every search path from the root to a leaf consists of the same number of 367black nodes. 368.It 369Each red node (except for the root) has a black parent. 370.It 371Each leaf node is black. 372.El 373.Pp 374Every operation on a red-black tree is bounded as 375.Fn O "lg n" . 376The maximum height of a red-black tree is 377.Fn 2lg "n + 1" . 378.Pp 379A red-black tree is headed by a structure defined by the 380.Fn RB_HEAD 381macro. 382A 383structure is declared as follows: 384.Bd -ragged -offset indent 385.Fn RB_HEAD HEADNAME TYPE 386.Va head ; 387.Ed 388.Pp 389where 390.Fa HEADNAME 391is the name of the structure to be defined, and struct 392.Fa TYPE 393is the type of the elements to be inserted into the tree. 394.Pp 395The 396.Fn RB_ENTRY 397macro declares a structure that allows elements to be connected in the tree. 398.Pp 399In order to use the functions that manipulate the tree structure, 400their prototypes need to be declared with the 401.Fn RB_PROTOTYPE 402or 403.Fn RB_PROTOTYPE_STATIC 404macro, 405where 406.Fa NAME 407is a unique identifier for this particular tree. 408The 409.Fa TYPE 410argument is the type of the structure that is being managed 411by the tree. 412The 413.Fa FIELD 414argument is the name of the element defined by 415.Fn RB_ENTRY . 416Individual 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 , 425and 426.Fn RB_PROTOTYPE_MINMAX 427in case not all functions are required. 428The individual prototype macros expect 429.Fa NAME , 430.Fa TYPE , 431and 432.Fa ATTR 433arguments. 434The 435.Fa ATTR 436argument must be empty for global functions or 437.Fa static 438for static functions. 439.Pp 440The function bodies are generated with the 441.Fn RB_GENERATE 442or 443.Fn RB_GENERATE_STATIC 444macro. 445These macros take the same arguments as the 446.Fn RB_PROTOTYPE 447and 448.Fn RB_PROTOTYPE_STATIC 449macros, but should be used only once. 450As 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 , 459and 460.Fn RB_GENERATE_MINMAX 461macros. 462.Pp 463Finally, 464the 465.Fa CMP 466argument is the name of a function used to compare tree nodes 467with each other. 468The function takes two arguments of type 469.Vt "struct TYPE *" . 470If the first argument is smaller than the second, the function returns a 471value smaller than zero. 472If they are equal, the function returns zero. 473Otherwise, it should return a value greater than zero. 474The compare 475function defines the order of the tree elements. 476.Pp 477The 478.Fn RB_INIT 479macro initializes the tree referenced by 480.Fa head . 481.Pp 482The red-black tree can also be initialized statically by using the 483.Fn RB_INITIALIZER 484macro 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 492The 493.Fn RB_INSERT 494macro inserts the new element 495.Fa elm 496into the tree. 497.Pp 498The 499.Fn RB_REMOVE 500macro removes the element 501.Fa elm 502from the tree pointed by 503.Fa head . 504.Pp 505The 506.Fn RB_FIND 507and 508.Fn RB_NFIND 509macros can be used to find a particular element in the tree. 510.Bd -literal -offset indent 511struct TYPE find, *res; 512find.key = 30; 513res = RB_FIND(NAME, head, &find); 514.Ed 515.Pp 516The 517.Fn RB_ROOT , 518.Fn RB_MIN , 519.Fn RB_MAX , 520.Fn RB_NEXT , 521and 522.Fn RB_PREV 523macros 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 527Or, for simplicity, one can use the 528.Fn RB_FOREACH 529or 530.Fn RB_FOREACH_REVERSE 531macro: 532.Bd -ragged -offset indent 533.Fn RB_FOREACH np NAME head 534.Ed 535.Pp 536The macros 537.Fn RB_FOREACH_SAFE 538and 539.Fn RB_FOREACH_REVERSE_SAFE 540traverse the tree referenced by head 541in a forward or reverse direction respectively, 542assigning each element in turn to np. 543However, unlike their unsafe counterparts, 544they permit both the removal of np 545as well as freeing it from within the loop safely 546without interfering with the traversal. 547.Pp 548Both 549.Fn RB_FOREACH_FROM 550and 551.Fn RB_FOREACH_REVERSE_FROM 552may be used to continue an interrupted traversal 553in a forward or reverse direction respectively. 554The head pointer is not required. 555The pointer to the node from where to resume the traversal 556should be passed as their last argument, 557and will be overwritten to provide safe traversal. 558.Pp 559The 560.Fn RB_EMPTY 561macro should be used to check whether a red-black tree is empty. 562.Sh EXAMPLES 563The following example demonstrates how to declare a red-black tree 564holding integers. 565Values are inserted into it and the contents of the tree are printed 566in order. 567Lastly, 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 574struct node { 575 RB_ENTRY(node) entry; 576 int i; 577}; 578 579int 580intcmp(struct node *e1, struct node *e2) 581{ 582 return (e1->i < e2->i ? -1 : e1->i > e2->i); 583} 584 585RB_HEAD(inttree, node) head = RB_INITIALIZER(&head); 586RB_GENERATE(inttree, node, entry, intcmp) 587 588int 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 593void 594print_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 615int 616main(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 637Trying to free a tree in the following way is a common error: 638.Bd -literal -offset indent 639SPLAY_FOREACH(var, NAME, head) { 640 SPLAY_REMOVE(NAME, head, var); 641 free(var); 642} 643free(head); 644.Ed 645.Pp 646Since 647.Va var 648is freed, the 649.Fn FOREACH 650macro refers to a pointer that may have been reallocated already. 651Proper code needs a second variable. 652.Bd -literal -offset indent 653for (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 660Both 661.Fn RB_INSERT 662and 663.Fn SPLAY_INSERT 664return 665.Dv NULL 666if the element was inserted in the tree successfully, otherwise they 667return a pointer to the element with the colliding key. 668.Pp 669Accordingly, 670.Fn RB_REMOVE 671and 672.Fn SPLAY_REMOVE 673return the pointer to the removed element otherwise they return 674.Dv NULL 675to indicate an error. 676.Sh SEE ALSO 677.Xr queue 3 678.Sh AUTHORS 679The author of the tree macros is 680.An Niels Provos . 681