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