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