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