1.\" $NetBSD: rbtree.3,v 1.13 2019/03/07 12:05:54 roy Exp $ 2.\" 3.\" Copyright (c) 2010 The NetBSD Foundation, Inc. 4.\" All rights reserved. 5.\" 6.\" This code is derived from software contributed to The NetBSD Foundation 7.\" by Matt Thomas, Niels Provos, and David Young. 8.\" 9.\" Redistribution and use in source and binary forms, with or without 10.\" modification, are permitted provided that the following conditions 11.\" are met: 12.\" 1. Redistributions of source code must retain the above copyright 13.\" notice, this list of conditions and the following disclaimer. 14.\" 2. Redistributions in binary form must reproduce the above copyright 15.\" notice, this list of conditions and the following disclaimer in the 16.\" documentation and/or other materials provided with the distribution. 17.\" 18.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 19.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 20.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 21.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 22.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 28.\" POSSIBILITY OF SUCH DAMAGE. 29.\" 30.Dd March 4, 2019 31.Dt RBTREE 3 32.Os 33.Sh NAME 34.Nm rbtree 35.Nd red-black tree 36.Sh LIBRARY 37.Lb libc 38.Sh SYNOPSIS 39.In sys/rbtree.h 40.Ft void 41.Fn rb_tree_init "rb_tree_t *rbt" "const rb_tree_ops_t *ops" 42.Ft void * 43.Fn rb_tree_insert_node "rb_tree_t *rbt" "void *rb" 44.Ft void 45.Fn rb_tree_remove_node "rb_tree_t *rbt" "void *rb" 46.Ft void * 47.Fn rb_tree_find_node "rb_tree_t *rbt" "const void *key" 48.Ft void * 49.Fn rb_tree_find_node_geq "rb_tree_t *rbt" "const void *key" 50.Ft void * 51.Fn rb_tree_find_node_leq "rb_tree_t *rbt" "const void *key" 52.Ft void * 53.Fn rb_tree_iterate "rb_tree_t *rbt" "void *rb" "unsigned int direction" 54.Ft void * 55.Fn RB_TREE_MIN "rb_tree_t *rbt" 56.Ft void * 57.Fn RB_TREE_MAX "rb_tree_t *rbt" 58.Fn RB_TREE_NEXT "rb_tree_t *rbt" "void *rb" 59.Fn RB_TREE_PREV "rb_tree_t *rbt" "void *rb" 60.Fn RB_TREE_FOREACH "void *rb" "rb_tree_t *rbt" 61.Fn RB_TREE_FOREACH_SAFE "void *rb" "rb_tree_t *rbt" "void *tmp" 62.Fn RB_TREE_FOREACH_REVERSE "void *rb" "rb_tree_t *rbt" 63.Fn RB_TREE_FOREACH_REVERSE_SAFE "void *rb" "rb_tree_t *rbt" "void *tmp" 64.Sh DESCRIPTION 65.Nm 66provides red-black trees. 67A red-black tree is a binary search tree with the node color as an 68extra attribute. 69It fulfills a set of conditions: 70.Bl -enum -offset indent 71.It 72Every search path from the root to a leaf consists of the same number of 73black nodes. 74.It 75Each red node (except for the root) has a black parent. 76.It 77Each leaf node is black. 78.El 79.Pp 80Every operation on a red-black tree is bounded as O(lg n). 81The maximum height of a red-black tree is 2lg (n+1). 82.Sh TYPES 83.Bl -tag -width compact 84.It Vt rb_tree_t 85A red-black tree. 86.It Vt typedef signed int \ 87(* rbto_compare_nodes_fn)(void *context, const void *node1, const void *node2); 88The node-comparison function. 89Defines an ordering on nodes. 90Returns a negative value if the first node 91.Ar node1 92precedes the second node 93.Ar node2 . 94Returns a positive value if the first node 95.Ar node1 96follows the second node 97.Ar node2 . 98Returns 0 if the first node 99.Ar node1 100and the second node 101.Ar node2 102are identical according to the ordering. 103.It Vt typedef signed int \ 104(* rbto_compare_key_fn)(void *context, const void *node, const void *key); 105The node-key comparison function. 106Defines the order of nodes and keys. 107Returns a negative value if the node 108.Ar node 109precedes the key 110.Ar key . 111Returns a positive value if the node 112.Ar node 113follows the key 114.Ar key . 115Returns 0 if the node 116.Ar node 117is identical to the key 118.Ar key 119according to the ordering. 120.It Vt rb_tree_ops_t 121Defines the function for comparing two nodes in the same tree, 122the function for comparing a node in the tree with a key, 123the offset of member 124.Vt rb_node_t 125within the node type, 126and the opaque context pointer passed to the comparison functions. 127Members of 128.Vt rb_tree_ops_t 129are 130.Bd -literal 131 rbto_compare_nodes_fn rbto_compare_nodes; 132 rbto_compare_key_fn rbto_compare_key; 133 size_t rbto_node_offset; 134 void *rbto_context; 135.Ed 136.It Vt rb_node_t 137A node in a red-black tree has this structure as a member. 138The offset of the 139.Vt rb_node_t 140member in the caller's node structure should be provided as 141.Va rbto_node_offset . 142(None of the functions in the 143.Nm 144interface are meant to take pointers directly to the 145.Vt rb_node_t 146member.) 147.El 148.Sh FUNCTIONS 149.Bl -tag -width compact 150.It Fn rb_tree_init "rbt" "ops" 151Initialize the red-black tree 152.Fa rbt . 153Let the comparison functions given by 154.Fa ops 155define the order of nodes in the tree for 156the purposes of insertion, search, and iteration. 157.Fn rb_tree_init 158always succeeds. 159.It Fn rb_tree_insert_node "rbt" "rb" 160Insert the node 161.Fa rb 162into the tree 163.Fa rbt . 164Return inserted node on success, 165already existing node on failure. 166.It Fn rb_tree_remove_node "rbt" "rb" 167Remove the node 168.Fa rb 169from the tree 170.Fa rbt . 171.It Fn rb_tree_find_node "rbt" "key" 172Search the tree 173.Fa rbt 174for a node exactly matching 175.Fa key . 176If no such node is in the tree, return 177.Dv NULL . 178Otherwise, return the matching node. 179.It Fn rb_tree_find_node_geq "rbt" "key" 180Search the tree 181.Fa rbt 182for a node that exactly matches 183.Fa key 184and return it. 185If no such node is present, return the first node following 186.Fa key 187or, if no such node is in the tree, return 188.Dv NULL . 189.It Fn rb_tree_find_node_leq "rbt" "key" 190Search the tree 191.Fa rbt 192for a node that exactly matches 193.Fa key 194and return it. 195If no such node is present, return the first node preceding 196.Fa key 197or, if no such node is in the tree, return 198.Dv NULL . 199.It Fn rb_tree_iterate "rbt" "rb" "direction" 200If 201.Fa direction 202is 203.Dv RB_DIR_LEFT , 204return the node in the tree 205.Fa rbt 206immediately preceding the node 207.Fa rb 208or, if 209.Fa rb 210is 211.Dv NULL , 212return the first node in 213.Fa rbt 214or, if the tree is empty, return 215.Dv NULL . 216.Pp 217If 218.Fa direction 219is 220.Dv RB_DIR_RIGHT , 221return the node in the tree 222.Fa rbt 223immediately following the node 224.Fa rb 225or, if 226.Fa rb 227is 228.Dv NULL , 229return the last node in 230.Fa rbt 231or, if the tree is empty, return 232.Dv NULL . 233.It Fn RB_TREE_MIN "rbt" 234Return the first node in 235.Fa rbt , 236i.e. the node with the least key, or 237.Dv NULL 238if 239.Fa rbt 240is empty. 241.It Fn RB_TREE_MAX "rbt" 242Return the last node in 243.Fa rbt , 244i.e. the node with the greatest key, or 245.Dv NULL 246if 247.Fa rbt 248is empty. 249.It Fn RB_TREE_NEXT "rbt" "rb" 250Return the next node in 251.Fa rbt , 252or 253.Dv NULL 254if there is none. 255.It Fn RB_TREE_PREV "rbt" "rb" 256Return the previous node in 257.Fa rbt , 258or 259.Dv NULL 260if there is none. 261.It Fn RB_TREE_FOREACH "rb" "rbt" 262.Nm RB_TREE_FOREACH 263is a macro to be used in the place of a 264.Dv for 265header preceding a statement to traverse the nodes in 266.Fa rbt 267from least to greatest, assigning 268.Fa rb 269to each node in turn and executing the statement. 270.It Fn RB_TREE_FOREACH_SAFE "rb" "rbt" "tmp" 271Allows both the removal of 272.Fa rb 273as well as freeing it from within the loop safely without interfering 274with the traversal. 275.It Fn RB_TREE_FOREACH_REVERSE "rb" "rbt" 276.Nm RB_TREE_FOREACH_REVERSE 277is a macro to be used in the place of a 278.Dv for 279header preceding a statement to traverse the nodes in 280.Fa rbt 281from greatest to least, assigning 282.Fa rb 283to each node in turn and executing the statement. 284.It Fn RB_TREE_FOREACH_REVERSE_SAFE "rb" "rbt" "tmp" 285Allows both the removal of 286.Fa rb 287as well as freeing it from within the loop safely without interfering 288with the traversal. 289.El 290.Sh CODE REFERENCES 291The 292.Nm 293interface is implemented in 294.Pa common/lib/libc/gen/rb.c . 295.\" .Sh EXAMPLES 296.\" 297.\" XXX: Should contain some examples. 298.\" 299.Sh SEE ALSO 300.Xr queue 3 , 301.Xr tree 3 302.Sh HISTORY 303The 304.Nm 305interface first appeared in 306.Nx 6.0 . 307.Sh AUTHORS 308.An Matt Thomas Aq Mt matt@NetBSD.org 309wrote 310.Nm . 311.Pp 312.An Niels Provos Aq Mt provos@citi.umich.edu 313wrote the 314.Xr tree 3 315manual page. 316Portions of this page derive from that page. 317.\" .Sh CAVEATS 318.\" .Sh BUGS 319.\" .Sh SECURITY CONSIDERATIONS 320