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.Dd February 24, 2002 32.Dt TREE 3 33.Os 34.Sh NAME 35.Nm SPLAY_PROTOTYPE, 36.Nm SPLAY_GENERATE, 37.Nm SPLAY_ENTRY , 38.Nm SPLAY_HEAD , 39.Nm SPLAY_INITIALIZER , 40.Nm SPLAY_ROOT , 41.Nm SPLAY_EMPTY , 42.Nm SPLAY_NEXT , 43.Nm SPLAY_MIN , 44.Nm SPLAY_MAX , 45.Nm SPLAY_FIND , 46.Nm SPLAY_LEFT , 47.Nm SPLAY_RIGHT , 48.Nm SPLAY_FOREACH , 49.Nm SPLAY_INIT , 50.Nm SPLAY_INSERT , 51.Nm SPLAY_REMOVE , 52.Nm RB_PROTOTYPE, 53.Nm RB_GENERATE, 54.Nm RB_ENTRY , 55.Nm RB_HEAD , 56.Nm RB_INITIALIZER , 57.Nm RB_ROOT , 58.Nm RB_EMPTY , 59.Nm RB_NEXT , 60.Nm RB_MIN , 61.Nm RB_MAX , 62.Nm RB_FIND , 63.Nm RB_LEFT , 64.Nm RB_RIGHT , 65.Nm RB_PARENT , 66.Nm RB_FOREACH , 67.Nm RB_INIT , 68.Nm RB_INSERT , 69.Nm RB_REMOVE 70.Nd "implementations of splay and red-black trees" 71.Sh SYNOPSIS 72.Fd #include <sys/tree.h> 73.Pp 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 134These macros defines data structures for different types of trees: 135splay trees and red-black trees. 136.Pp 137In the macro definitions, 138.Fa TYPE 139is the name tag of a user defined structure that must contain a field of type 140.Li SPLAY_ENTRY , 141or 142.Li RB_ENTRY , 143named 144.Fa ENTRYNAME . 145The argument 146.Fa HEADNAME 147is the name tag of a user defined structure that must be declared 148using the macros 149.Fn SPLAY_HEAD , 150or 151.Fn RB_HEAD . 152The argument 153.Fa NAME 154has to be a unique name prefix for every tree that is defined. 155.Pp 156The function prototypes are declared with either 157.Li SPLAY_PROTOTYPE, 158or 159.Li RB_PROTOTYPE . 160The function bodies are generated with either 161.Li SPLAY_GENERATE, 162or 163.Li RB_GENERATE . 164See the examples below for further explanation of how these macros are used. 165.Sh SPLAY TREES 166A splay tree is a self-organizing data structure. Every operation 167on the tree causes a splay to happen. The splay moves the requested 168node to the root of the tree and partly rebalances it. 169.Pp 170This has the benefit that request locality causes faster lookups as 171the requested nodes move to the top of the tree. On the other hand, 172every lookup causes memory writes. 173.Pp 174The Balance Theorem bounds the total access time for m operations 175and n inserts on an initially empty tree as O((m + n)lg n). The 176amortized cost for a sequence of m accesses to a splay tree is O(lg n); 177.Pp 178A splay tree is headed by a structure defined by the 179.Fn SPLAY_HEAD 180macro. 181A 182.Fa SPLAY_HEAD 183structure is declared as follows: 184.Bd -literal -offset indent 185SPLAY_HEAD(HEADNAME, TYPE) head; 186.Ed 187.Pp 188where 189.Fa HEADNAME 190is the name of the structure to be defined, and struct 191.Fa TYPE 192is the type of the elements to be inserted into the tree. 193.Pp 194The 195.Fn SPLAY_ENTRY 196macro declares a structure that allows elements to be connected in the tree. 197.Pp 198In order to use the functions that manipulate the tree structure, 199their prototypes need to be declared with the 200.Fn SPLAY_PROTOTYPE 201macro, 202where 203.Fa NAME 204is a unique identifier for this particular tree. 205The 206.Fa TYPE 207argument is the type of the structure that is being managed 208by the tree. 209The 210.Fa FIELD 211argument is the name of the element defined by 212.Fn SPLAY_ENTRY . 213.Pp 214The function bodies are generated with the 215.Fn SPLAY_GENERATE 216macro. It takes the same arguments as the 217.Fn SPLAY_PROTOTYPE 218macro, but should be used only once. 219.Pp 220Finally, 221the 222.Fa CMP 223argument is the name of a function used to compare tree noded 224with each other. The function takes two arguments of type 225.Fa "struct TYPE *" . 226If the first argument is smaller than the second, the function returns a 227value smaller than zero. If they are equal, the function returns zero. 228Otherwise, it should return a value greater than zero. The compare 229function defines the order of the tree elements. 230.Pp 231The 232.Fn SPLAY_INIT 233macro initializes the tree referenced by 234.Fa head . 235.Pp 236The splay tree can also be initialized statically by using the 237.Fn SPLAY_INITIALIZER 238macro like this: 239.Bd -literal -offset indent 240SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(&head); 241.Ed 242.Pp 243The 244.Fn SPLAY_INSERT 245macro inserts the new element 246.Fa elm 247into the tree. 248.Pp 249The 250.Fn SPLAY_REMOVE 251macro removes the element 252.Fa elm 253from the tree pointed by 254.Fa head . 255.Pp 256The 257.Fn SPLAY_FIND 258macro can be used to find a particular element in the tree. 259.Bd -literal -offset indent 260struct TYPE find, *res; 261find.key = 30; 262res = SPLAY_FIND(NAME, head, &find); 263.Ed 264.Pp 265The 266.Fn SPLAY_ROOT , 267.Fn SPLAY_MIN , 268.Fn SPLAY_MAX , 269and 270.Fn SPLAY_NEXT 271macros can be used to traverse the tree: 272.Bd -literal -offset indent 273for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np)) 274.Ed 275.Pp 276Or, for simplicity, one can use the 277.Fn SPLAY_FOREACH 278macro: 279.Bd -literal -offset indent 280SPLAY_FOREACH(np, NAME, head) 281.Ed 282.Pp 283The 284.Fn SPLAY_EMPTY 285macro should be used to check whether a splay tree is empty. 286.Pp 287.Sh RED-BLACK TREES 288A red-black tree is a binary search tree with the node color as an 289extra attribute. It fulfills a set of conditions: 290.Bl -enum -compact -offset indent 291.It 292every search path from the root to a leaf consists of the same number of 293black nodes, 294.It 295each red node (except for the root) has a black parent, 296.It 297each leaf node is black. 298.El 299.Pp 300Every operation on a red-black tree is bounded as O(lg n). 301The maximum height of a red-black tree is 2lg (n+1). 302.Pp 303A red-black tree is headed by a structure defined by the 304.Fn RB_HEAD 305macro. 306A 307.Fa RB_HEAD 308structure is declared as follows: 309.Bd -literal -offset indent 310RB_HEAD(HEADNAME, TYPE) head; 311.Ed 312.Pp 313where 314.Fa HEADNAME 315is the name of the structure to be defined, and struct 316.Fa TYPE 317is the type of the elements to be inserted into the tree. 318.Pp 319The 320.Fn RB_ENTRY 321macro declares a structure that allows elements to be connected in the tree. 322.Pp 323In order to use the functions that manipulate the tree structure, 324their prototypes need to be declared with the 325.Fn RB_PROTOTYPE 326macro, 327where 328.Fa NAME 329is a unique identifier for this particular tree. 330The 331.Fa TYPE 332argument is the type of the structure that is being managed 333by the tree. 334The 335.Fa FIELD 336argument is the name of the element defined by 337.Fn RB_ENTRY . 338.Pp 339The function bodies are generated with the 340.Fn RB_GENERATE 341macro. It takes the same arguments as the 342.Fn RB_PROTOTYPE 343macro, but should be used only once. 344.Pp 345Finally, 346the 347.Fa CMP 348argument is the name of a function used to compare tree noded 349with each other. The function takes two arguments of type 350.Fa "struct TYPE *" . 351If the first argument is smaller than the second, the function returns a 352value smaller than zero. If they are equal, the function returns zero. 353Otherwise, it should return a value greater than zero. The compare 354function defines the order of the tree elements. 355.Pp 356The 357.Fn RB_INIT 358macro initializes the tree referenced by 359.Fa head . 360.Pp 361The redblack tree can also be initialized statically by using the 362.Fn RB_INITIALIZER 363macro like this: 364.Bd -literal -offset indent 365RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(&head); 366.Ed 367.Pp 368The 369.Fn RB_INSERT 370macro inserts the new element 371.Fa elm 372into the tree. 373.Pp 374The 375.Fn RB_REMOVE 376macro removes the element 377.Fa elm 378from the tree pointed by 379.Fa head . 380.Pp 381The 382.Fn RB_FIND 383macro can be used to find a particular element in the tree. 384.Bd -literal -offset indent 385struct TYPE find, *res; 386find.key = 30; 387res = RB_FIND(NAME, head, &find); 388.Ed 389.Pp 390The 391.Fn RB_ROOT , 392.Fn RB_MIN , 393.Fn RB_MAX , 394and 395.Fn RB_NEXT 396macros can be used to traverse the tree: 397.Bd -literal -offset indent 398for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np)) 399.Ed 400.Pp 401Or, for simplicity, one can use the 402.Fn RB_FOREACH 403macro: 404.Bd -literal -offset indent 405RB_FOREACH(np, NAME, head) 406.Ed 407.Pp 408The 409.Fn RB_EMPTY 410macro should be used to check whether a splay tree is empty. 411.Pp 412.Sh NOTES 413Trying to free a tree in the following way is a common error: 414.Bd -literal -offset indent 415SPLAY_FOREACH(var, NAME, head) { 416 SPLAY_REMOVE(NAME, head, var); 417 free(var); 418} 419free(head); 420.Ed 421.Pp 422Since 423.Va var 424is free'd, the 425.Fn FOREACH 426macro refers to a pointer that may have been reallocated already. 427Proper code needs a second variable. 428.Bd -literal -offset indent 429for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) { 430 nxt = SPLAY_NEXT(NAME, head, var); 431 SPLAY_REMOVE(NAME, head, var); 432 free(var); 433} 434.Ed 435.Pp 436Both 437.Fn RB_INSERT 438and 439.Fn SPLAY_INSERT 440return 441.Va NULL 442if the element was inserted in the tree successfully, otherwise they 443return a pointer to the element with the colliding key. 444.Pp 445Accordingly, 446.Fn RB_REMOVE 447and 448.Fn SPLAY_REMOVE 449return the pointer to the removed element otherwise they return 450.Va NULL 451to indicate an error. 452.Sh AUTHORS 453The author of the tree macros is Niels Provos. 454