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