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