1.\" $NetBSD: tree.3,v 1.14 2019/05/24 21:32:05 wiz Exp $ 2.\" $OpenBSD: tree.3,v 1.23 2011/07/09 08:43:01 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.\" * 16.\" * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17.\" * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18.\" * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19.\" * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20.\" * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21.\" * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22.\" * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23.\" * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24.\" * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25.\" * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26.\" */ 27.Dd May 25, 2019 28.Dt TREE 3 29.Os 30.Sh NAME 31.Nm SPLAY_PROTOTYPE , 32.Nm SPLAY_GENERATE , 33.Nm SPLAY_ENTRY , 34.Nm SPLAY_HEAD , 35.Nm SPLAY_INITIALIZER , 36.Nm SPLAY_ROOT , 37.Nm SPLAY_EMPTY , 38.Nm SPLAY_NEXT , 39.Nm SPLAY_MIN , 40.Nm SPLAY_MAX , 41.Nm SPLAY_FIND , 42.Nm SPLAY_LEFT , 43.Nm SPLAY_RIGHT , 44.Nm SPLAY_FOREACH , 45.Nm SPLAY_INIT , 46.Nm SPLAY_INSERT , 47.Nm SPLAY_REMOVE , 48.Nm RB_PROTOTYPE , 49.Nm RB_PROTOTYPE_STATIC , 50.Nm RB_GENERATE , 51.Nm RB_GENERATE_STATIC , 52.Nm RB_ENTRY , 53.Nm RB_HEAD , 54.Nm RB_INITIALIZER , 55.Nm RB_ROOT , 56.Nm RB_EMPTY , 57.Nm RB_NEXT , 58.Nm RB_PREV , 59.Nm RB_MIN , 60.Nm RB_MAX , 61.Nm RB_FIND , 62.Nm RB_NFIND , 63.Nm RB_LEFT , 64.Nm RB_RIGHT , 65.Nm RB_PARENT , 66.Nm RB_FOREACH , 67.Nm RB_FOREACH_SAFE , 68.Nm RB_FOREACH_REVERSE , 69.Nm RB_FOREACH_REVERSE_SAFE , 70.Nm RB_INIT , 71.Nm RB_INSERT , 72.Nm RB_REMOVE 73.Nd implementations of splay and red-black trees 74.Sh SYNOPSIS 75.In sys/tree.h 76.Fn SPLAY_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP" 77.Fn SPLAY_GENERATE "NAME" "TYPE" "FIELD" "CMP" 78.Fn SPLAY_ENTRY "TYPE" 79.Fn SPLAY_HEAD "HEADNAME" "TYPE" 80.Ft "struct TYPE *" 81.Fn SPLAY_INITIALIZER "SPLAY_HEAD *head" 82.Fn SPLAY_ROOT "SPLAY_HEAD *head" 83.Ft "int" 84.Fn SPLAY_EMPTY "SPLAY_HEAD *head" 85.Ft "struct TYPE *" 86.Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" 87.Ft "struct TYPE *" 88.Fn SPLAY_MIN "NAME" "SPLAY_HEAD *head" 89.Ft "struct TYPE *" 90.Fn SPLAY_MAX "NAME" "SPLAY_HEAD *head" 91.Ft "struct TYPE *" 92.Fn SPLAY_FIND "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" 93.Ft "struct TYPE *" 94.Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME" 95.Ft "struct TYPE *" 96.Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME" 97.Fn SPLAY_FOREACH "VARNAME" "NAME" "SPLAY_HEAD *head" 98.Ft void 99.Fn SPLAY_INIT "SPLAY_HEAD *head" 100.Ft "struct TYPE *" 101.Fn SPLAY_INSERT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" 102.Ft "struct TYPE *" 103.Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" 104.Pp 105.Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP" 106.Fn RB_PROTOTYPE_STATIC "NAME" "TYPE" "FIELD" "CMP" 107.Fn RB_GENERATE "NAME" "TYPE" "FIELD" "CMP" 108.Fn RB_GENERATE_STATIC "NAME" "TYPE" "FIELD" "CMP" 109.Fn RB_ENTRY "TYPE" 110.Fn RB_HEAD "HEADNAME" "TYPE" 111.Fn RB_INITIALIZER "RB_HEAD *head" 112.Ft "struct TYPE *" 113.Fn RB_ROOT "RB_HEAD *head" 114.Ft "int" 115.Fn RB_EMPTY "RB_HEAD *head" 116.Ft "struct TYPE *" 117.Fn RB_NEXT "NAME" "RB_HEAD *head" "struct TYPE *elm" 118.Ft "struct TYPE *" 119.Fn RB_PREV "NAME" "RB_HEAD *head" "struct TYPE *elm" 120.Ft "struct TYPE *" 121.Fn RB_MIN "NAME" "RB_HEAD *head" 122.Ft "struct TYPE *" 123.Fn RB_MAX "NAME" "RB_HEAD *head" 124.Ft "struct TYPE *" 125.Fn RB_FIND "NAME" "RB_HEAD *head" "struct TYPE *elm" 126.Ft "struct TYPE *" 127.Fn RB_NFIND "NAME" "RB_HEAD *head" "struct TYPE *elm" 128.Ft "struct TYPE *" 129.Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME" 130.Ft "struct TYPE *" 131.Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME" 132.Ft "struct TYPE *" 133.Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME" 134.Fn RB_FOREACH "VARNAME" "NAME" "RB_HEAD *head" 135.Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" 136.Fn RB_FOREACH_REVERSE "VARNAME" "NAME" "RB_HEAD *head" 137.Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" 138.Ft void 139.Fn RB_INIT "RB_HEAD *head" 140.Ft "struct TYPE *" 141.Fn RB_INSERT "NAME" "RB_HEAD *head" "struct TYPE *elm" 142.Ft "struct TYPE *" 143.Fn RB_REMOVE "NAME" "RB_HEAD *head" "struct TYPE *elm" 144.Sh DESCRIPTION 145.Bf -symbolic 146This is a legacy interface; for new code, 147.Xr rbtree 3 148is preferred. 149.Ef 150.Pp 151These macros define data structures for different types of trees: 152splay trees and red-black trees. 153.Pp 154In the macro definitions, 155.Fa TYPE 156is the name tag of a user defined structure that must contain a field named 157.Fa FIELD , 158of type 159.Li SPLAY_ENTRY 160or 161.Li RB_ENTRY . 162The argument 163.Fa HEADNAME 164is the name tag of a user defined structure that must be declared 165using the macros 166.Fn SPLAY_HEAD 167or 168.Fn RB_HEAD . 169The argument 170.Fa NAME 171has to be a unique name prefix for every tree that is defined. 172.Pp 173The function prototypes are declared with 174.Li SPLAY_PROTOTYPE , 175.Li RB_PROTOTYPE , 176or 177.Li RB_PROTOTYPE_STATIC . 178The function bodies are generated with 179.Li SPLAY_GENERATE , 180.Li RB_GENERATE , 181or 182.Li RB_GENERATE_STATIC . 183See the examples below for further explanation of how these macros are used. 184.Sh SPLAY TREES 185A splay tree is a self-organizing data structure. 186Every operation on the tree causes a splay to happen. 187The splay moves the requested node to the root of the tree and partly 188rebalances it. 189.Pp 190This has the benefit that request locality causes faster lookups as 191the requested nodes move to the top of the tree. 192On the other hand, every lookup causes memory writes. 193.Pp 194The Balance Theorem bounds the total access time for m operations 195and n inserts on an initially empty tree as O((m + n)lg n). 196The amortized cost for a sequence of m accesses to a splay tree is O(lg n). 197.Pp 198A splay tree is headed by a structure defined by the 199.Fn SPLAY_HEAD 200macro. 201A 202.Fa SPLAY_HEAD 203structure is declared as follows: 204.Bd -literal -offset indent 205SPLAY_HEAD(HEADNAME, TYPE) head; 206.Ed 207.Pp 208where 209.Fa HEADNAME 210is the name of the structure to be defined, and struct 211.Fa TYPE 212is the type of the elements to be inserted into the tree. 213.Pp 214The 215.Fn SPLAY_ENTRY 216macro declares a structure that allows elements to be connected in the tree. 217.Pp 218In order to use the functions that manipulate the tree structure, 219their prototypes need to be declared with the 220.Fn SPLAY_PROTOTYPE 221macro, 222where 223.Fa NAME 224is a unique identifier for this particular tree. 225The 226.Fa TYPE 227argument is the type of the structure that is being managed 228by the tree. 229The 230.Fa FIELD 231argument is the name of the element defined by 232.Fn SPLAY_ENTRY . 233.Pp 234The function bodies are generated with the 235.Fn SPLAY_GENERATE 236macro. 237It takes the same arguments as the 238.Fn SPLAY_PROTOTYPE 239macro, but should be used only once. 240.Pp 241Finally, 242the 243.Fa CMP 244argument is the name of a function used to compare tree nodes 245with each other. 246The function takes two arguments of type 247.Fa "struct TYPE *" . 248If the first argument is smaller than the second, the function returns a 249value smaller than zero. 250If they are equal, the function returns zero. 251Otherwise, it should return a value greater than zero. 252The compare function defines the order of the tree elements. 253.Pp 254The 255.Fn SPLAY_INIT 256macro initializes the tree referenced by 257.Fa head . 258.Pp 259The splay tree can also be initialized statically by using the 260.Fn SPLAY_INITIALIZER 261macro like this: 262.Bd -literal -offset indent 263SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(&head); 264.Ed 265.Pp 266The 267.Fn SPLAY_INSERT 268macro inserts the new element 269.Fa elm 270into the tree. 271Upon success, 272.Dv NULL 273is returned. 274If a matching element already exists in the tree, the insertion is 275aborted, and a pointer to the existing element is returned. 276.Pp 277The 278.Fn SPLAY_REMOVE 279macro removes the element 280.Fa elm 281from the tree pointed by 282.Fa head . 283Upon success, a pointer to the removed element is returned. 284.Dv NULL 285is returned if 286.Fa elm 287is not present in the tree. 288.Pp 289The 290.Fn SPLAY_FIND 291macro can be used to find a particular element in the tree. 292.Bd -literal -offset indent 293struct TYPE find, *res; 294find.key = 30; 295res = SPLAY_FIND(NAME, &head, &find); 296.Ed 297.Pp 298The 299.Fn SPLAY_ROOT , 300.Fn SPLAY_MIN , 301.Fn SPLAY_MAX , 302and 303.Fn SPLAY_NEXT 304macros can be used to traverse the tree: 305.Bd -literal -offset indent 306for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np)) 307.Ed 308.Pp 309Or, for simplicity, one can use the 310.Fn SPLAY_FOREACH 311macro: 312.Bd -literal -offset indent 313SPLAY_FOREACH(np, NAME, &head) 314.Ed 315.Pp 316The 317.Fn SPLAY_EMPTY 318macro should be used to check whether a splay tree is empty. 319.Sh RED-BLACK TREES 320A red-black tree is a binary search tree with the node color as an 321extra attribute. 322It fulfills a set of conditions: 323.Pp 324.Bl -enum -compact -offset indent 325.It 326every search path from the root to a leaf consists of the same number of 327black nodes, 328.It 329each red node (except for the root) has a black parent, 330.It 331each leaf node is black. 332.El 333.Pp 334Every operation on a red-black tree is bounded as O(lg n). 335The maximum height of a red-black tree is 2lg (n+1). 336.Pp 337A red-black tree is headed by a structure defined by the 338.Fn RB_HEAD 339macro. 340A 341.Fa RB_HEAD 342structure is declared as follows: 343.Bd -literal -offset indent 344RB_HEAD(HEADNAME, TYPE) head; 345.Ed 346.Pp 347where 348.Fa HEADNAME 349is the name of the structure to be defined, and struct 350.Fa TYPE 351is the type of the elements to be inserted into the tree. 352.Pp 353The 354.Fn RB_ENTRY 355macro declares a structure that allows elements to be connected in the tree. 356.Pp 357In order to use the functions that manipulate the tree structure, 358their prototypes need to be declared with the 359.Fn RB_PROTOTYPE 360or 361.Fn RB_PROTOTYPE_STATIC 362macros, 363where 364.Fa NAME 365is a unique identifier for this particular tree. 366The 367.Fa TYPE 368argument is the type of the structure that is being managed 369by the tree. 370The 371.Fa FIELD 372argument is the name of the element defined by 373.Fn RB_ENTRY . 374.Pp 375The function bodies are generated with the 376.Fn RB_GENERATE 377or 378.Fn RB_GENERATE_STATIC 379macros. 380These macros take the same arguments as the 381.Fn RB_PROTOTYPE 382and 383.Fn RB_PROTOTYPE_STATIC 384macros, but should be used only once. 385.Pp 386Finally, 387the 388.Fa CMP 389argument is the name of a function used to compare trees' nodes 390with each other. 391The function takes two arguments of type 392.Fa "struct TYPE *" . 393If the first argument is smaller than the second, the function returns a 394value smaller than zero. 395If they are equal, the function returns zero. 396Otherwise, it should return a value greater than zero. 397The compare function defines the order of the tree elements. 398.Pp 399The 400.Fn RB_INIT 401macro initializes the tree referenced by 402.Fa head . 403.Pp 404The red-black tree can also be initialized statically by using the 405.Fn RB_INITIALIZER 406macro like this: 407.Bd -literal -offset indent 408RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(&head); 409.Ed 410.Pp 411The 412.Fn RB_INSERT 413macro inserts the new element 414.Fa elm 415into the tree. 416Upon success, 417.Dv NULL 418is returned. 419If a matching element already exists in the tree, the insertion is 420aborted, and a pointer to the existing element is returned. 421.Pp 422The 423.Fn RB_REMOVE 424macro removes the element 425.Fa elm 426from the tree pointed to by 427.Fa head . 428The element must be present in that tree. 429.Fn RB_REMOVE 430returns 431.Fa elm . 432.Pp 433The 434.Fn RB_FIND 435macro can be used to find a particular element in the tree. 436and 437.Fn RB_NFIND 438macros can be used to find a particular element in the tree. 439.Fn RB_FIND 440finds the node with the same key as 441.Fa elm . 442.Fn RB_NFIND 443finds the first node greater than or equal to the search key. 444.Bd -literal -offset indent 445struct TYPE find, *res; 446find.key = 30; 447res = RB_FIND(NAME, &head, &find); 448.Ed 449.Pp 450The 451.Fn RB_ROOT , 452.Fn RB_MIN , 453.Fn RB_MAX , 454.Fn RB_NEXT , 455and 456.Fn RB_PREV 457macros can be used to traverse the tree: 458.Bd -literal -offset indent 459for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np)) 460.Ed 461.Pp 462Or, for simplicity, one can use the 463.Fn RB_FOREACH 464or 465.Fn RB_FOREACH_REVERSE 466macros: 467.Bd -literal -offset indent 468RB_FOREACH(np, NAME, &head) 469.Ed 470.Pp 471The macros 472.Fn RB_FOREACH_SAFE 473and 474.Fn RB_FOREACH_REVERSE_SAFE 475traverse the tree referenced by head 476in a forward or reverse direction respectively, 477assigning each element in turn to np. 478However, unlike their unsafe counterparts, 479they permit both the removal of np 480as well as freeing it from within the loop safely 481without interfering with the traversal. 482.Pp 483The 484.Fn RB_EMPTY 485macro should be used to check whether a red-black tree is empty. 486.Sh EXAMPLES 487The following example demonstrates how to declare a red-black tree 488holding integers. 489Values are inserted into it and the contents of the tree are printed 490in order. 491Lastly, the internal structure of the tree is printed. 492.Bd -literal -offset 3n 493#include <sys/tree.h> 494#include <err.h> 495#include <stdio.h> 496#include <stdlib.h> 497 498struct node { 499 RB_ENTRY(node) entry; 500 int i; 501}; 502 503int 504intcmp(struct node *e1, struct node *e2) 505{ 506 return (e1->i < e2->i ? -1 : e1->i > e2->i); 507} 508 509RB_HEAD(inttree, node) head = RB_INITIALIZER(&head); 510RB_GENERATE(inttree, node, entry, intcmp) 511 512int testdata[] = { 513 20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18, 514 7, 11, 14 515}; 516 517void 518print_tree(struct node *n) 519{ 520 struct node *left, *right; 521 522 if (n == NULL) { 523 printf("nil"); 524 return; 525 } 526 left = RB_LEFT(n, entry); 527 right = RB_RIGHT(n, entry); 528 if (left == NULL && right == NULL) 529 printf("%d", n->i); 530 else { 531 printf("%d(", n->i); 532 print_tree(left); 533 printf(","); 534 print_tree(right); 535 printf(")"); 536 } 537} 538 539int 540main() 541{ 542 int i; 543 struct node *n; 544 545 for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) { 546 if ((n = malloc(sizeof(struct node))) == NULL) 547 err(1, NULL); 548 n->i = testdata[i]; 549 RB_INSERT(inttree, &head, n); 550 } 551 552 RB_FOREACH(n, inttree, &head) { 553 printf("%d\en", n->i); 554 } 555 print_tree(RB_ROOT(&head)); 556 printf("\en"); 557 return (0); 558} 559.Ed 560.Sh NOTES 561Some of these macros or functions perform no error checking, 562and invalid usage leads to undefined behaviour. 563In the case of macros or functions that expect their arguments 564to be elements that are present in the tree, passing an element 565that is not present in the tree is invalid. 566.Pp 567Trying to free a tree in the following way is a common error: 568.Bd -literal -offset indent 569SPLAY_FOREACH(var, NAME, &head) { 570 SPLAY_REMOVE(NAME, &head, var); 571 free(var); 572} 573free(head); 574.Ed 575.Pp 576Since 577.Va var 578is free'd, the 579.Fn FOREACH 580macro refers to a pointer that may have been reallocated already. 581Proper code needs a second variable. 582.Bd -literal -offset indent 583for (var = SPLAY_MIN(NAME, &head); var != NULL; var = nxt) { 584 nxt = SPLAY_NEXT(NAME, &head, var); 585 SPLAY_REMOVE(NAME, &head, var); 586 free(var); 587} 588.Ed 589.\".Pp 590.\"Both 591.\".Fn RB_INSERT 592.\"and 593.\".Fn SPLAY_INSERT 594.\"return 595.\".Dv NULL 596.\"if the element was inserted in the tree successfully, otherwise they 597.\"return a pointer to the element with the colliding key. 598.\".Pp 599.\"Accordingly, 600.\".Fn RB_REMOVE 601.\"and 602.\".Fn SPLAY_REMOVE 603.\"return the pointer to the removed element, otherwise they return 604.\".Dv NULL 605.\"to indicate an error. 606.Sh SEE ALSO 607.Xr rbtree 3 608.Sh AUTHORS 609The author of the tree macros is 610.An Niels Provos . 611