1.\" $OpenBSD: RBT_INIT.9,v 1.6 2017/06/08 03:12:53 dlg 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.\" 27.\" Copyright (c) 2016 David Gwynne <dlg@openbsd.org> 28.\" 29.\" Permission to use, copy, modify, and distribute this software for any 30.\" purpose with or without fee is hereby granted, provided that the above 31.\" copyright notice and this permission notice appear in all copies. 32.\" 33.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 34.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 35.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 36.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 37.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 38.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 39.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 40.\" 41.Dd $Mdocdate: June 8 2017 $ 42.Dt RBT_INIT 9 43.Os 44.Sh NAME 45.Nm RBT_HEAD , 46.Nm RBT_ENTRY , 47.Nm RBT_PROTOTYPE , 48.Nm RBT_GENERATE , 49.Nm RBT_INITIALIZER , 50.Nm RBT_INIT , 51.Nm RBT_INSERT , 52.Nm RBT_REMOVE , 53.Nm RBT_FIND , 54.Nm RBT_NFIND , 55.Nm RBT_EMPTY , 56.Nm RBT_ROOT , 57.Nm RBT_MIN , 58.Nm RBT_MAX , 59.Nm RBT_NEXT , 60.Nm RBT_PREV , 61.Nm RBT_LEFT , 62.Nm RBT_RIGHT , 63.Nm RBT_PARENT , 64.Nm RBT_SET_LEFT , 65.Nm RBT_SET_RIGHT , 66.Nm RBT_SET_PARENT , 67.Nm RBT_FOREACH , 68.Nm RBT_FOREACH_SAFE , 69.Nm RBT_FOREACH_REVERSE , 70.Nm RBT_FOREACH_REVERSE_SAFE , 71.Nm RBT_POISON , 72.Nm RBT_CHECK 73.Nd Kernel red-black trees 74.Sh SYNOPSIS 75.In sys/tree.h 76.Fn RBT_HEAD "NAME" "TYPE" 77.Fn RBT_ENTRY "TYPE" 78.Fo RBT_PROTOTYPE 79.Fa "NAME" 80.Fa "TYPE" 81.Fa "ENTRY" 82.Fa "int (*compare)(const struct TYPE *, const struct TYPE *)" 83.Fc 84.Fo RBT_GENERATE 85.Fa "NAME" 86.Fa "TYPE" 87.Fa "ENTRY" 88.Fa "int (*compare)(const struct TYPE *, const struct TYPE *)" 89.Fc 90.Ft struct NAME 91.Fn RBT_INITIALIZER "struct NAME *self" 92.Ft void 93.Fn RBT_INIT "NAME" "struct NAME *rbt" 94.Ft struct TYPE * 95.Fn RBT_INSERT "NAME" "struct NAME *rbt" "struct TYPE *elm" 96.Ft struct TYPE * 97.Fn RBT_REMOVE "NAME" "struct NAME *rbt" "struct TYPE *elm" 98.Ft struct TYPE * 99.Fn RBT_FIND "NAME" "struct NAME *rbt" "const struct TYPE *key" 100.Ft struct TYPE * 101.Fn RBT_NFIND "NAME" "struct NAME *rbt" "const struct TYPE *key" 102.Ft int 103.Fn RBT_EMPTY "NAME" "struct NAME *rbt" 104.Ft struct TYPE * 105.Fn RBT_ROOT "NAME" "struct NAME *rbt" 106.Ft struct TYPE * 107.Fn RBT_MIN "NAME" "struct NAME *rbt" 108.Ft struct TYPE * 109.Fn RBT_MAX "NAME" "struct NAME *rbt" 110.Ft struct TYPE * 111.Fn RBT_NEXT "NAME" "struct TYPE *elm" 112.Ft struct TYPE * 113.Fn RBT_PREV "NAME" "struct TYPE *elm" 114.Ft struct TYPE * 115.Fn RBT_LEFT "NAME" "struct TYPE *elm" 116.Ft struct TYPE * 117.Fn RBT_RIGHT "NAME" "struct TYPE *elm" 118.Ft struct TYPE * 119.Fn RBT_PARENT "NAME" "struct TYPE *elm" 120.Ft void 121.Fn RBT_SET_LEFT "NAME" "struct TYPE *elm" "struct TYPE *left" 122.Ft void 123.Fn RBT_SET_RIGHT "NAME" "struct TYPE *elm" "struct TYPE *right" 124.Ft void 125.Fn RBT_SET_PARENT "NAME" "struct TYPE *elm" "struct TYPE *parent" 126.Fo RBT_FOREACH 127.Fa "VARNAME" 128.Fa "NAME" 129.Fa "struct NAME *rbt" 130.Fc 131.Fo RBT_FOREACH_REVERSE 132.Fa "VARNAME" 133.Fa "NAME" 134.Fa "struct NAME *rbt" 135.Fc 136.Fo RBT_FOREACH_SAFE 137.Fa "VARNAME" 138.Fa "NAME" 139.Fa "struct NAME *rbt" 140.Fa "NEXTVARNAME" 141.Fc 142.Fo RBT_FOREACH_REVERSE_SAFE 143.Fa "VARNAME" 144.Fa "NAME" 145.Fa "struct NAME *rbt" 146.Fa "NEXTVARNAME" 147.Fc 148.Ft void 149.Fn RBT_POISON "NAME" "struct TYPE *elm" "unsigned long poison" 150.Ft int 151.Fn RBT_CHECK "NAME" "struct TYPE *elm" "unsigned long poison" 152.Sh DESCRIPTION 153The red-black tree API provides data structures and operations for 154storing structures in red-black trees. 155.Pp 156A red-black tree is a binary search tree with the node color as an 157extra attribute. 158It fulfills a set of conditions: 159.Pp 160.Bl -enum -compact -offset indent 161.It 162every search path from the root to a leaf consists of the same number of 163black nodes, 164.It 165each red node (except for the root) has a black parent, 166.It 167each leaf node is black. 168.El 169.Pp 170Every operation on a red-black tree is bounded as O(lg n). 171The maximum height of a red-black tree is 2lg (n+1). 172.Pp 173This API is implemented as a set of functions that operate on generic 174pointers, but users of the API generate wrappers and macros that provide 175type safety when calling the functions. 176.Pp 177In the macro definitions, 178.Fa TYPE 179is the name of a structure that will be stored in a red-black tree. 180The 181.Fa TYPE 182structure must contain an 183.Fn RBT_ENTRY 184field 185that allows the element to be connected to a tree. 186The argument 187.Fa NAME 188is the name of a red-black tree type that can store a particular 189.Fa TYPE 190element. 191.Ss Creating a Red-Black Tree Type 192The 193.Fn RBT_HEAD 194macro creates a red-black tree type to store 195.Fa TYPE 196structures as elements in the tree. 197The argument 198.Fa NAME 199must uniquely identify every type of tree that is defined. 200.Pp 201.Fn RBT_PROTOTYPE 202produces the wrappers for a red-black tree type identified by 203.Fa NAME 204to operate on elements of type 205.Fa TYPE . 206.Fa ENTRY 207specifies which field in the 208.Fa TYPE 209structure is used to connect elements to 210.Fa NAME 211red-black trees. 212Elements in the red-black tree are ordered according to the result of comparing 213them with the 214.Fa compare 215function. 216If the first argument to 217.Fa compare 218is to be ordered lower than the second, 219the function returns a value smaller than zero. 220If the first argument is to be ordered higher than the second, 221the function returns a value greater than zero. 222If they are equal, the function returns zero. 223.Pp 224.Fn RBT_GENERATE 225produces the internal data structures used by the red-black tree 226type identified by 227.Fa NAME 228to operate on elements of type 229.Fa TYPE . 230The 231.Fa ENTRY 232and 233.Fa compare 234arguments are the same as the 235.Fn RBT_PROTOTYPE 236arguments of the same names. 237.Ss Initialising a Red-Black Tree 238.Fn RBT_INIT 239initialises the red-black tree 240.Fa rbt 241of type 242.Fa NAME 243to an empty state. 244.Pp 245.Fn RBT_INITIALIZER 246can be used to initialise a declaration of the red-black tree 247.Fa self 248of type 249.Fa NAME 250to an empty state. 251.Ss Red-Black Tree Operations 252.Fn RBT_INSERT 253inserts the element 254.Fa elm 255into the red-black tree 256.Fa rbt 257of type 258.Fa NAME . 259Upon success, 260.Dv NULL 261is returned. 262If a matching element already exists in the tree, the insertion is 263aborted and a pointer to the existing element is returned. 264.Pp 265.Fn RBT_REMOVE 266removes the element 267.Fa elm 268from the red-black tree 269.Fa rbt 270of type 271.Fa NAME . 272.Fa elm 273must exist in the tree 274.Fa rbt 275before it is removed. 276.Pp 277.Fn RBT_FIND 278performs a binary search for an exact match of 279.Fa key 280in the red-black tree 281.Fa rbt 282of type 283.Fa NAME . 284.Pp 285.Fn RBT_NFIND 286performs a binary search for the first node that is greater than or equal to 287.Fa key 288in the red-black tree 289.Fa rbt 290of type 291.Fa NAME . 292.Pp 293.Fn RBT_EMPTY 294returns if the red-black tree 295.Fa rbt 296of type 297.Fa NAME 298is empty. 299.Pp 300.Fn RBT_ROOT 301returns the root element in the red-black tree 302.Fa rbt 303of type 304.Fa NAME . 305.Pp 306.Fn RBT_MIN 307returns the lowest ordered element in the red-black tree 308.Fa rbt 309of type 310.Fa NAME . 311.Pp 312.Fn RBT_MAX 313returns the highest ordered element in the red-black tree 314.Fa rbt 315of type 316.Fa NAME . 317.Ss Red-Black Tree Element Operations 318.Fn RBT_NEXT 319returns a pointer to the next ordered element after 320.Fa elm 321in a red-black tree of type 322.Fa NAME . 323.Pp 324.Fn RBT_PREV 325returns a pointer to the previous ordered element before 326.Fa elm 327in a red-black tree of type 328.Fa NAME . 329.Pp 330.Fn RBT_LEFT 331returns a pointer to the left child element of 332.Fa elm 333in a red-black tree of type 334.Fa NAME . 335.Pp 336.Fn RBT_RIGHT 337returns a pointer to the right child element of 338.Fa elm 339in a red-black tree of type 340.Fa NAME . 341.Pp 342.Fn RBT_PARENT 343returns a pointer to the parent element of 344.Fa elm 345in a red-black tree of type 346.Fa NAME . 347.Pp 348.Fn RBT_SET_LEFT 349sets the left child pointer of element 350.Fa elm 351to 352.Fa left 353in a red-black tree of type 354.Fa NAME . 355.Pp 356.Fn RBT_SET_RIGHT 357sets the right child pointer of element 358.Fa elm 359to 360.Fa right 361in a red-black tree of type 362.Fa NAME . 363.Pp 364.Fn RBT_SET_PARENT 365sets the parent pointer of element 366.Fa elm 367to 368.Fa parent 369in a red-black tree of type 370.Fa NAME . 371.Ss Red-Black Tree Iterators 372The 373.Fn RBT_FOREACH 374macro iterates over the red-black tree 375.Fa rbt 376of type 377.Fa NAME 378from the lowest ordered element to the highest ordered element, 379setting 380.Fa VARNAME 381to each element in turn. 382.Pp 383The 384.Fn RBT_FOREACH_REVERSE 385macro iterates over the red-black tree 386.Fa rbt 387of type 388.Fa NAME 389from the highest ordered element to the lowest ordered element, 390setting 391.Fa VARNAME 392to each element in turn. 393.Pp 394The 395.Fn RBT_FOREACH_SAFE 396macro iterates over the red-black tree 397.Fa rbt 398of type 399.Fa NAME 400from the lowest ordered element to the highest ordered element, 401setting 402.Fa VARNAME 403to each element in turn. 404.Fa VARNAME 405may be removed from the tree during iteration because a reference to the next 406element is held in 407.Fa NEXTVARNAME . 408.Pp 409The 410.Fn RBT_FOREACH_REVERSE_SAFE 411macro iterates over the red-black tree 412.Fa rbt 413of type 414.Fa NAME 415from the highest ordered element to the lowest ordered element, 416setting 417.Fa VARNAME 418to each element in turn. 419.Fa VARNAME 420may be removed from the tree during iteration because a reference to the next 421element is held in 422.Fa NEXTVARNAME . 423.Ss Red-Black Tree Element Poisoning 424.Fn RBT_POISON 425is used to poison the pointers in the RBT_ENTRY structure inside 426.Fa elm 427which has been removed from a red-black tree of type 428.Fa NAME 429with the 430.Fa poison 431value. 432.Pp 433.Fn RBT_CHECK 434is used to verify that the pointers in the RBT_ENTRY structure inside 435.Fa elm 436are set to the 437.Fa poison 438value. 439.Sh CONTEXT 440.Fn RBT_INIT , 441.Fn RBT_INSERT , 442.Fn RBT_REMOVE , 443.Fn RBT_FIND , 444.Fn RBT_NFIND , 445.Fn RBT_EMPTY , 446.Fn RBT_ROOT , 447.Fn RBT_MIN , 448.Fn RBT_MAX , 449.Fn RBT_NEXT , 450.Fn RBT_PREV , 451.Fn RBT_LEFT , 452.Fn RBT_RIGHT , 453.Fn RBT_PARENT , 454.Fn RBT_SET_LEFT , 455.Fn RBT_SET_RIGHT , 456.Fn RBT_SET_PARENT , 457.Fn RBT_FOREACH , 458.Fn RBT_FOREACH_REVERSE , 459.Fn RBT_FOREACH_SAFE , 460.Fn RBT_FOREACH_SAFE_REVERSE , 461.Fn RBT_POISON , 462and 463.Fn RBT_CHECK 464can be called during autoconf, from process context, or from interrupt 465context. 466.Pp 467It is up to the caller to provide appropriate locking around calls to 468these functions to prevent concurrent access to the relevant data structures. 469.Sh RETURN VALUES 470.Fn RBT_INSERT 471will return 472.Dv NULL 473on successful insertion of 474.Fa elm 475into the tree, otherwise it will return a reference to an existing 476element with the same key. 477.Pp 478.Fn RBT_FIND 479will return a reference to an element that compares as equal to 480.Fa key , 481or 482.Dv NULL 483if no such element could be found. 484.Pp 485.Fn RBT_NFIND 486will return a reference to the nearest element that compares as equal or 487greater to 488.Fa key , 489or 490.Dv NULL 491if no such element could be found. 492.Pp 493.Fn RBT_EMPTY 494returns non-zero if the red-black tree 495.Fa rbt 496is empty, otherwise 0. 497.Pp 498.Fn RBT_ROOT 499returns a reference to the root node in the red-black tree 500.Fa rbt , 501or 502.Dv NULL 503if it is empty. 504.Pp 505.Fn RBT_MIN 506returns a reference to the lowest ordered element in the red-black tree 507.Fa rbt , 508or 509.Dv NULL 510if it is empty. 511.Pp 512.Fn RBT_MAX 513returns a reference to the lowest ordered element in the red-black tree 514.Fa rbt , 515or 516.Dv NULL 517if it is empty. 518.Pp 519.Fn RBT_NEXT 520returns a reference to the next ordered element in the red-black tree after 521.Fa elm , 522or 523.Dv NULL 524if it is the greatest element in the tree. 525.Pp 526.Fn RBT_PREV 527returns a reference to the previous ordered element in the red-black tree before 528.Fa elm , 529or 530.Dv NULL 531if it is the lowest element in the tree. 532.Pp 533.Fn RBT_LEFT 534returns a reference to the left child element of 535.Fa elm , 536or 537.Dv NULL 538if it is a leaf in the tree. 539.Pp 540.Fn RBT_RIGHT 541returns a reference to the right child element of 542.Fa elm , 543or 544.Dv NULL 545if it is a leaf in the tree. 546.Pp 547.Fn RBT_PARENT 548returns a reference to the parent element of 549.Fa elm , 550or 551.Dv NULL 552if it is the root of the tree. 553.Pp 554.Fn RBT_CHECK 555returns non-zero if the RBT_ENTRY in the red-black tree element contains the 556.Fa poison 557value, 558otherwise 0. 559.Sh SEE ALSO 560.Xr RB_INIT 3 561.Sh HISTORY 562The red-black tree kernel API first appeared in 563.Ox 6.1 . 564