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