1.\" $NetBSD: tree.3,v 1.3 2004/04/14 11:05:19 pooka Exp $ 2.\" $OpenBSD: tree.3,v 1.9 2003/05/20 09:13:38 jmc Exp $ 3.\"/* 4.\" * Copyright 2002 Niels Provos <provos@citi.umich.edu> 5.\" * All rights reserved. 6.\" * 7.\" * Redistribution and use in source and binary forms, with or without 8.\" * modification, are permitted provided that the following conditions 9.\" * are met: 10.\" * 1. Redistributions of source code must retain the above copyright 11.\" * notice, this list of conditions and the following disclaimer. 12.\" * 2. Redistributions in binary form must reproduce the above copyright 13.\" * notice, this list of conditions and the following disclaimer in the 14.\" * documentation and/or other materials provided with the distribution. 15.\" * 3. All advertising materials mentioning features or use of this software 16.\" * must display the following acknowledgement: 17.\" * This product includes software developed by Niels Provos. 18.\" * 4. The name of the author may not be used to endorse or promote products 19.\" * derived from this software without specific prior written permission. 20.\" * 21.\" * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22.\" * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23.\" * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24.\" * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25.\" * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26.\" * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27.\" * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28.\" * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29.\" * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30.\" * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31.\" */ 32.Dd August 9, 2015 33.Dt TREE 3 34.Os 35.Sh NAME 36.Nm SPLAY_PROTOTYPE , 37.Nm SPLAY_GENERATE , 38.Nm SPLAY_ENTRY , 39.Nm SPLAY_HEAD , 40.Nm SPLAY_INITIALIZER , 41.Nm SPLAY_ROOT , 42.Nm SPLAY_EMPTY , 43.Nm SPLAY_NEXT , 44.Nm SPLAY_MIN , 45.Nm SPLAY_MAX , 46.Nm SPLAY_FIND , 47.Nm SPLAY_LEFT , 48.Nm SPLAY_RIGHT , 49.Nm SPLAY_FOREACH , 50.Nm SPLAY_INIT , 51.Nm SPLAY_INSERT , 52.Nm SPLAY_REMOVE , 53.Nm RB_PROTOTYPE , 54.Nm RB_GENERATE , 55.Nm RB_ENTRY , 56.Nm RB_HEAD , 57.Nm RB_INITIALIZER , 58.Nm RB_ROOT , 59.Nm RB_EMPTY , 60.Nm RB_NEXT , 61.Nm RB_MIN , 62.Nm RB_MAX , 63.Nm RB_FIND , 64.Nm RB_LEFT , 65.Nm RB_RIGHT , 66.Nm RB_PARENT , 67.Nm RB_FOREACH , 68.Nm RB_FOREACH_FROM , 69.Nm RB_FOREACH_SAFE , 70.Nm RB_FOREACH_REVERSE , 71.Nm RB_FOREACH_REVERSE_FROM , 72.Nm RB_FOREACH_REVERSE_SAFE , 73.Nm RB_INIT , 74.Nm RB_INSERT , 75.Nm RB_REMOVE 76.Nd implementations of splay and red-black trees 77.Sh SYNOPSIS 78.In sys/tree.h 79.Fn SPLAY_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP" 80.Fn SPLAY_GENERATE "NAME" "TYPE" "FIELD" "CMP" 81.Fn SPLAY_ENTRY "TYPE" 82.Fn SPLAY_HEAD "HEADNAME" "TYPE" 83.Ft "struct TYPE *" 84.Fn SPLAY_INITIALIZER "SPLAY_HEAD *head" 85.Fn SPLAY_ROOT "SPLAY_HEAD *head" 86.Ft "bool" 87.Fn SPLAY_EMPTY "SPLAY_HEAD *head" 88.Ft "struct TYPE *" 89.Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" 90.Ft "struct TYPE *" 91.Fn SPLAY_MIN "NAME" "SPLAY_HEAD *head" 92.Ft "struct TYPE *" 93.Fn SPLAY_MAX "NAME" "SPLAY_HEAD *head" 94.Ft "struct TYPE *" 95.Fn SPLAY_FIND "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" 96.Ft "struct TYPE *" 97.Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME" 98.Ft "struct TYPE *" 99.Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME" 100.Fn SPLAY_FOREACH "VARNAME" "NAME" "SPLAY_HEAD *head" 101.Ft void 102.Fn SPLAY_INIT "SPLAY_HEAD *head" 103.Ft "struct TYPE *" 104.Fn SPLAY_INSERT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" 105.Ft "struct TYPE *" 106.Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" 107.Pp 108.Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP" 109.Fn RB_GENERATE "NAME" "TYPE" "FIELD" "CMP" 110.Fn RB_ENTRY "TYPE" 111.Fn RB_HEAD "HEADNAME" "TYPE" 112.Fn RB_INITIALIZER "RB_HEAD *head" 113.Ft "struct TYPE *" 114.Fn RB_ROOT "RB_HEAD *head" 115.Ft "bool" 116.Fn RB_EMPTY "RB_HEAD *head" 117.Ft "struct TYPE *" 118.Fn RB_NEXT "NAME" "RB_HEAD *head" "struct TYPE *elm" 119.Ft "struct TYPE *" 120.Fn RB_MIN "NAME" "RB_HEAD *head" 121.Ft "struct TYPE *" 122.Fn RB_MAX "NAME" "RB_HEAD *head" 123.Ft "struct TYPE *" 124.Fn RB_FIND "NAME" "RB_HEAD *head" "struct TYPE *elm" 125.Ft "struct TYPE *" 126.Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME" 127.Ft "struct TYPE *" 128.Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME" 129.Ft "struct TYPE *" 130.Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME" 131.Fn RB_FOREACH "VARNAME" "NAME" "RB_HEAD *head" 132.Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME" 133.Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" 134.Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head" 135.Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME" 136.Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" 137.Ft void 138.Fn RB_INIT "RB_HEAD *head" 139.Ft "struct TYPE *" 140.Fn RB_INSERT "NAME" "RB_HEAD *head" "struct TYPE *elm" 141.Ft "struct TYPE *" 142.Fn RB_REMOVE "NAME" "RB_HEAD *head" "struct TYPE *elm" 143.Sh DESCRIPTION 144These macros define data structures for different types of trees: 145splay trees and red-black trees. 146.Pp 147In the macro definitions, 148.Fa TYPE 149is the name tag of a user defined structure that must contain a field of type 150.Li SPLAY_ENTRY , 151or 152.Li RB_ENTRY , 153named 154.Fa ENTRYNAME . 155The argument 156.Fa HEADNAME 157is the name tag of a user defined structure that must be declared 158using the macros 159.Fn SPLAY_HEAD 160or 161.Fn RB_HEAD . 162The argument 163.Fa NAME 164has to be a unique name prefix for every tree that is defined. 165.Pp 166The function prototypes are declared with either 167.Li SPLAY_PROTOTYPE 168or 169.Li RB_PROTOTYPE . 170The function bodies are generated with either 171.Li SPLAY_GENERATE 172or 173.Li RB_GENERATE . 174See the examples below for further explanation of how these macros are used. 175.Sh SPLAY TREES 176A splay tree is a self-organizing data structure. 177Every operation on the tree causes a splay to happen. 178The splay moves the requested node to the root of the tree and partly 179rebalances it. 180.Pp 181This has the benefit that request locality causes faster lookups as 182the requested nodes move to the top of the tree. 183On the other hand, every lookup causes memory writes. 184.Pp 185The Balance Theorem bounds the total access time for m operations 186and n inserts on an initially empty tree as O((m + n)lg n). 187The amortized cost for a sequence of m accesses to a splay tree is O(lg n). 188.Pp 189A splay tree is headed by a structure defined by the 190.Fn SPLAY_HEAD 191macro. 192A 193.Fa SPLAY_HEAD 194structure is declared as follows: 195.Bd -literal -offset indent 196SPLAY_HEAD(HEADNAME, TYPE) head; 197.Ed 198.Pp 199where 200.Fa HEADNAME 201is the name of the structure to be defined, and struct 202.Fa TYPE 203is the type of the elements to be inserted into the tree. 204.Pp 205The 206.Fn SPLAY_ENTRY 207macro declares a structure that allows elements to be connected in the tree. 208.Pp 209In order to use the functions that manipulate the tree structure, 210their prototypes need to be declared with the 211.Fn SPLAY_PROTOTYPE 212macro, 213where 214.Fa NAME 215is a unique identifier for this particular tree. 216The 217.Fa TYPE 218argument is the type of the structure that is being managed 219by the tree. 220The 221.Fa FIELD 222argument is the name of the element defined by 223.Fn SPLAY_ENTRY . 224.Pp 225The function bodies are generated with the 226.Fn SPLAY_GENERATE 227macro. 228It takes the same arguments as the 229.Fn SPLAY_PROTOTYPE 230macro, but should be used only once. 231.Pp 232Finally, 233the 234.Fa CMP 235argument is the name of a function used to compare trees noded 236with each other. 237The function takes two arguments of type 238.Fa "struct TYPE *" . 239If the first argument is smaller than the second, the function returns a 240value smaller than zero. 241If they are equal, the function returns zero. 242Otherwise, it should return a value greater than zero. 243The compare function defines the order of the tree elements. 244.Pp 245The 246.Fn SPLAY_INIT 247macro initializes the tree referenced by 248.Fa head . 249.Pp 250The splay tree can also be initialized statically by using the 251.Fn SPLAY_INITIALIZER 252macro like this: 253.Bd -literal -offset indent 254SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(\*[Am]head); 255.Ed 256.Pp 257The 258.Fn SPLAY_INSERT 259macro inserts the new element 260.Fa elm 261into the tree. 262.Pp 263The 264.Fn SPLAY_REMOVE 265macro removes the element 266.Fa elm 267from the tree pointed by 268.Fa head . 269.Pp 270The 271.Fn SPLAY_FIND 272macro can be used to find a particular element in the tree. 273.Bd -literal -offset indent 274struct TYPE find, *res; 275find.key = 30; 276res = SPLAY_FIND(NAME, head, \*[Am]find); 277.Ed 278.Pp 279The 280.Fn SPLAY_ROOT , 281.Fn SPLAY_MIN , 282.Fn SPLAY_MAX , 283and 284.Fn SPLAY_NEXT 285macros can be used to traverse the tree: 286.Bd -literal -offset indent 287for (np = SPLAY_MIN(NAME, \*[Am]head); np != NULL; np = SPLAY_NEXT(NAME, \*[Am]head, np)) 288.Ed 289.Pp 290Or, for simplicity, one can use the 291.Fn SPLAY_FOREACH 292macro: 293.Bd -literal -offset indent 294SPLAY_FOREACH(np, NAME, head) 295.Ed 296.Pp 297The 298.Fn SPLAY_EMPTY 299macro should be used to check whether a splay tree is empty. 300.Sh RED-BLACK TREES 301A red-black tree is a binary search tree with the node color as an 302extra attribute. 303It fulfills a set of conditions: 304.Bl -enum -compact -offset indent 305.It 306every search path from the root to a leaf consists of the same number of 307black nodes, 308.It 309each red node (except for the root) has a black parent, 310.It 311each leaf node is black. 312.El 313.Pp 314Every operation on a red-black tree is bounded as O(lg n). 315The maximum height of a red-black tree is 2lg (n+1). 316.Pp 317A red-black tree is headed by a structure defined by the 318.Fn RB_HEAD 319macro. 320A 321.Fa RB_HEAD 322structure is declared as follows: 323.Bd -literal -offset indent 324RB_HEAD(HEADNAME, TYPE) head; 325.Ed 326.Pp 327where 328.Fa HEADNAME 329is the name of the structure to be defined, and struct 330.Fa TYPE 331is the type of the elements to be inserted into the tree. 332.Pp 333The 334.Fn RB_ENTRY 335macro declares a structure that allows elements to be connected in the tree. 336.Pp 337In order to use the functions that manipulate the tree structure, 338their prototypes need to be declared with the 339.Fn RB_PROTOTYPE 340macro, 341where 342.Fa NAME 343is a unique identifier for this particular tree. 344The 345.Fa TYPE 346argument is the type of the structure that is being managed 347by the tree. 348The 349.Fa FIELD 350argument is the name of the element defined by 351.Fn RB_ENTRY . 352.Pp 353The function bodies are generated with the 354.Fn RB_GENERATE 355macro. 356It takes the same arguments as the 357.Fn RB_PROTOTYPE 358macro, but should be used only once. 359.Pp 360Finally, 361the 362.Fa CMP 363argument is the name of a function used to compare trees noded 364with each other. 365The function takes two arguments of type 366.Fa "struct TYPE *" . 367If the first argument is smaller than the second, the function returns a 368value smaller than zero. 369If they are equal, the function returns zero. 370Otherwise, it should return a value greater than zero. 371The compare function defines the order of the tree elements. 372.Pp 373The 374.Fn RB_INIT 375macro initializes the tree referenced by 376.Fa head . 377.Pp 378The redblack tree can also be initialized statically by using the 379.Fn RB_INITIALIZER 380macro like this: 381.Bd -literal -offset indent 382RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(\*[Am]head); 383.Ed 384.Pp 385The 386.Fn RB_INSERT 387macro inserts the new element 388.Fa elm 389into the tree. 390.Pp 391The 392.Fn RB_REMOVE 393macro removes the element 394.Fa elm 395from the tree pointed by 396.Fa head . 397.Pp 398The 399.Fn RB_FIND 400macro can be used to find a particular element in the tree. 401.Bd -literal -offset indent 402struct TYPE find, *res; 403find.key = 30; 404res = RB_FIND(NAME, head, \*[Am]find); 405.Ed 406.Pp 407The 408.Fn RB_ROOT , 409.Fn RB_MIN , 410.Fn RB_MAX , 411and 412.Fn RB_NEXT 413macros can be used to traverse the tree: 414.Bd -literal -offset indent 415for (np = RB_MIN(NAME, \*[Am]head); np != NULL; np = RB_NEXT(NAME, \*[Am]head, np)) 416.Ed 417.Pp 418Or, for simplicity, one can use the 419.Fn RB_FOREACH 420or 421.Fn RB_FOREACH_REVERSE 422macro: 423.Bd -literal -offset indent 424RB_FOREACH(np, NAME, head) 425.Ed 426.Pp 427The macros 428.Fn RB_FOREACH_SAFE 429and 430.Fn RB_FOREACH_REVERSE_SAFE 431traverse the tree referenced by head 432in a forward or reverse direction respectively, 433assigning each element in turn to np. 434However, unlike their unsafe counterparts, 435they permit both the removal of np 436as well as freeing it from within the loop safely 437without interfering with the traversal. 438.Pp 439Both 440.Fn RB_FOREACH_FROM 441and 442.Fn RB_FOREACH_REVERSE_FROM 443may be used to continue an interrupted traversal 444in a forward or reverse direction respectively. 445The head pointer is not required. 446The pointer to the node from where to resume the traversal 447should be passed as their last argument, 448and will be overwritten to provide safe traversal. 449.Pp 450The 451.Fn RB_EMPTY 452macro should be used to check whether a red-black tree is empty. 453.Sh NOTES 454Trying to free a tree in the following way is a common error: 455.Bd -literal -offset indent 456SPLAY_FOREACH(var, NAME, head) { 457 SPLAY_REMOVE(NAME, head, var); 458 free(var); 459} 460free(head); 461.Ed 462.Pp 463Since 464.Va var 465is free'd, the 466.Fn SPLAY_FOREACH 467macro refers to a pointer that may have been reallocated already. 468Proper code needs a second variable. 469.Bd -literal -offset indent 470for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) { 471 nxt = SPLAY_NEXT(NAME, head, var); 472 SPLAY_REMOVE(NAME, head, var); 473 free(var); 474} 475.Ed 476.Pp 477Both 478.Fn RB_INSERT 479and 480.Fn SPLAY_INSERT 481return 482.Dv NULL 483if the element was inserted in the tree successfully, otherwise they 484return a pointer to the element with the colliding key. 485.Pp 486Accordingly, 487.Fn RB_REMOVE 488and 489.Fn SPLAY_REMOVE 490return the pointer to the removed element, otherwise they return 491.Dv NULL 492to indicate an error. 493.Sh AUTHORS 494The author of the tree macros is 495.An Niels Provos . 496