1.\" $OpenBSD: tree.3,v 1.12 2005/04/16 06:11:35 otto 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 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(&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, &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, &head); np != NULL; np = SPLAY_NEXT(NAME, &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.Pp 295.Bl -enum -compact -offset indent 296.It 297every search path from the root to a leaf consists of the same number of 298black nodes, 299.It 300each red node (except for the root) has a black parent, 301.It 302each leaf node is black. 303.El 304.Pp 305Every operation on a red-black tree is bounded as O(lg n). 306The maximum height of a red-black tree is 2lg (n+1). 307.Pp 308A red-black tree is headed by a structure defined by the 309.Fn RB_HEAD 310macro. 311A 312.Fa RB_HEAD 313structure is declared as follows: 314.Bd -literal -offset indent 315RB_HEAD(HEADNAME, TYPE) head; 316.Ed 317.Pp 318where 319.Fa HEADNAME 320is the name of the structure to be defined, and struct 321.Fa TYPE 322is the type of the elements to be inserted into the tree. 323.Pp 324The 325.Fn RB_ENTRY 326macro declares a structure that allows elements to be connected in the tree. 327.Pp 328In order to use the functions that manipulate the tree structure, 329their prototypes need to be declared with the 330.Fn RB_PROTOTYPE 331macro, 332where 333.Fa NAME 334is a unique identifier for this particular tree. 335The 336.Fa TYPE 337argument is the type of the structure that is being managed 338by the tree. 339The 340.Fa FIELD 341argument is the name of the element defined by 342.Fn RB_ENTRY . 343.Pp 344The function bodies are generated with the 345.Fn RB_GENERATE 346macro. 347It takes the same arguments as the 348.Fn RB_PROTOTYPE 349macro, but should be used only once. 350.Pp 351Finally, 352the 353.Fa CMP 354argument is the name of a function used to compare trees noded 355with each other. 356The function takes two arguments of type 357.Fa "struct TYPE *" . 358If the first argument is smaller than the second, the function returns a 359value smaller than zero. 360If they are equal, the function returns zero. 361Otherwise, it should return a value greater than zero. 362The compare function defines the order of the tree elements. 363.Pp 364The 365.Fn RB_INIT 366macro initializes the tree referenced by 367.Fa head . 368.Pp 369The red-black tree can also be initialized statically by using the 370.Fn RB_INITIALIZER 371macro like this: 372.Bd -literal -offset indent 373RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(&head); 374.Ed 375.Pp 376The 377.Fn RB_INSERT 378macro inserts the new element 379.Fa elm 380into the tree. 381.Pp 382The 383.Fn RB_REMOVE 384macro removes the element 385.Fa elm 386from the tree pointed by 387.Fa head . 388.Pp 389The 390.Fn RB_FIND 391macro can be used to find a particular element in the tree. 392.Bd -literal -offset indent 393struct TYPE find, *res; 394find.key = 30; 395res = RB_FIND(NAME, &head, &find); 396.Ed 397.Pp 398The 399.Fn RB_ROOT , 400.Fn RB_MIN , 401.Fn RB_MAX , 402and 403.Fn RB_NEXT 404macros can be used to traverse the tree: 405.Bd -literal -offset indent 406for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np)) 407.Ed 408.Pp 409Or, for simplicity, one can use the 410.Fn RB_FOREACH 411macro: 412.Bd -literal -offset indent 413RB_FOREACH(np, NAME, &head) 414.Ed 415.Pp 416The 417.Fn RB_EMPTY 418macro should be used to check whether a red-black tree is empty. 419.Sh EXAMPLES 420The following example demonstrates how to declare a red-black tree 421holding integers. 422Values are inserted into it and the contents of the tree are printed 423in order. 424Lastly, the internal structure of the tree is printed. 425.Bd -literal -offset 3n 426#include <sys/tree.h> 427#include <err.h> 428#include <stdio.h> 429#include <stdlib.h> 430 431struct node { 432 RB_ENTRY(node) entry; 433 int i; 434}; 435 436int 437intcmp(struct node *e1, struct node *e2) 438{ 439 return (e1->i - e2->i); 440} 441 442RB_HEAD(inttree, node) head = RB_INITIALIZER(&head); 443RB_GENERATE(inttree, node, entry, intcmp) 444 445int testdata[] = { 446 20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18, 447 7, 11, 14 448}; 449 450void 451print_tree(struct node *n) 452{ 453 struct node *left, *right; 454 455 if (n == NULL) { 456 printf("nil"); 457 return; 458 } 459 left = RB_LEFT(n, entry); 460 right = RB_RIGHT(n, entry); 461 if (left == NULL && right == NULL) 462 printf("%d", n->i); 463 else { 464 printf("%d(", n->i); 465 print_tree(left); 466 printf(","); 467 print_tree(right); 468 printf(")"); 469 } 470} 471 472int 473main() 474{ 475 int i; 476 struct node *n; 477 478 for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) { 479 if ((n = malloc(sizeof(struct node))) == NULL) 480 err(1, NULL); 481 n->i = testdata[i]; 482 RB_INSERT(inttree, &head, n); 483 } 484 485 RB_FOREACH(n, inttree, &head) { 486 printf("%d\en", n->i); 487 } 488 print_tree(RB_ROOT(&head)); 489 printf("\en"); 490 return (0); 491} 492.Ed 493.Sh NOTES 494Trying to free a tree in the following way is a common error: 495.Bd -literal -offset indent 496SPLAY_FOREACH(var, NAME, &head) { 497 SPLAY_REMOVE(NAME, &head, var); 498 free(var); 499} 500free(head); 501.Ed 502.Pp 503Since 504.Va var 505is free'd, the 506.Fn FOREACH 507macro refers to a pointer that may have been reallocated already. 508Proper code needs a second variable. 509.Bd -literal -offset indent 510for (var = SPLAY_MIN(NAME, &head); var != NULL; var = nxt) { 511 nxt = SPLAY_NEXT(NAME, &head, var); 512 SPLAY_REMOVE(NAME, &head, var); 513 free(var); 514} 515.Ed 516.Pp 517Both 518.Fn RB_INSERT 519and 520.Fn SPLAY_INSERT 521return 522.Va NULL 523if the element was inserted in the tree successfully, otherwise they 524return a pointer to the element with the colliding key. 525.Pp 526Accordingly, 527.Fn RB_REMOVE 528and 529.Fn SPLAY_REMOVE 530return the pointer to the removed element, otherwise they return 531.Va NULL 532to indicate an error. 533.Sh AUTHORS 534The author of the tree macros is Niels Provos. 535