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