1.\" $NetBSD: rbtree.3,v 1.12 2016/08/30 05:12:00 dholland 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 August 29, 2016 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_FOREACH "void *rb" "rb_tree_t *rbt" 59.Fn RB_TREE_FOREACH_REVERSE "void *rb" "rb_tree_t *rbt" 60.Sh DESCRIPTION 61.Nm 62provides red-black trees. 63A red-black tree is a binary search tree with the node color as an 64extra attribute. 65It fulfills a set of conditions: 66.Bl -enum -offset indent 67.It 68Every search path from the root to a leaf consists of the same number of 69black nodes. 70.It 71Each red node (except for the root) has a black parent. 72.It 73Each leaf node is black. 74.El 75.Pp 76Every operation on a red-black tree is bounded as O(lg n). 77The maximum height of a red-black tree is 2lg (n+1). 78.Sh TYPES 79.Bl -tag -width compact 80.It Vt rb_tree_t 81A red-black tree. 82.It Vt typedef signed int \ 83(* rbto_compare_nodes_fn)(void *context, const void *node1, const void *node2); 84The node-comparison function. 85Defines an ordering on nodes. 86Returns a negative value if the first node 87.Ar node1 88precedes the second node 89.Ar node2 . 90Returns a positive value if the first node 91.Ar node1 92follows the second node 93.Ar node2 . 94Returns 0 if the first node 95.Ar node1 96and the second node 97.Ar node2 98are identical according to the ordering. 99.It Vt typedef signed int \ 100(* rbto_compare_key_fn)(void *context, const void *node, const void *key); 101The node-key comparison function. 102Defines the order of nodes and keys. 103Returns a negative value if the node 104.Ar node 105precedes the key 106.Ar key . 107Returns a positive value if the node 108.Ar node 109follows the key 110.Ar key . 111Returns 0 if the node 112.Ar node 113is identical to the key 114.Ar key 115according to the ordering. 116.It Vt rb_tree_ops_t 117Defines the function for comparing two nodes in the same tree, 118the function for comparing a node in the tree with a key, 119the offset of member 120.Vt rb_node_t 121within the node type, 122and the opaque context pointer passed to the comparison functions. 123Members of 124.Vt rb_tree_ops_t 125are 126.Bd -literal 127 rbto_compare_nodes_fn rbto_compare_nodes; 128 rbto_compare_key_fn rbto_compare_key; 129 size_t rbto_node_offset; 130 void *rbto_context; 131.Ed 132.It Vt rb_node_t 133A node in a red-black tree has this structure as a member. 134The offset of the 135.Vt rb_node_t 136member in the caller's node structure should be provided as 137.Va rbto_node_offset . 138(None of the functions in the 139.Nm 140interface are meant to take pointers directly to the 141.Vt rb_node_t 142member.) 143.El 144.Sh FUNCTIONS 145.Bl -tag -width compact 146.It Fn rb_tree_init "rbt" "ops" 147Initialize the red-black tree 148.Fa rbt . 149Let the comparison functions given by 150.Fa ops 151define the order of nodes in the tree for 152the purposes of insertion, search, and iteration. 153.Fn rb_tree_init 154always succeeds. 155.It Fn rb_tree_insert_node "rbt" "rb" 156Insert the node 157.Fa rb 158into the tree 159.Fa rbt . 160Return inserted node on success, 161already existing node on failure. 162.It Fn rb_tree_remove_node "rbt" "rb" 163Remove the node 164.Fa rb 165from the tree 166.Fa rbt . 167.It Fn rb_tree_find_node "rbt" "key" 168Search the tree 169.Fa rbt 170for a node exactly matching 171.Fa key . 172If no such node is in the tree, return 173.Dv NULL . 174Otherwise, return the matching node. 175.It Fn rb_tree_find_node_geq "rbt" "key" 176Search the tree 177.Fa rbt 178for a node that exactly matches 179.Fa key 180and return it. 181If no such node is present, return the first node following 182.Fa key 183or, if no such node is in the tree, return 184.Dv NULL . 185.It Fn rb_tree_find_node_leq "rbt" "key" 186Search the tree 187.Fa rbt 188for a node that exactly matches 189.Fa key 190and return it. 191If no such node is present, return the first node preceding 192.Fa key 193or, if no such node is in the tree, return 194.Dv NULL . 195.It Fn rb_tree_iterate "rbt" "rb" "direction" 196If 197.Fa direction 198is 199.Dv RB_DIR_LEFT , 200return the node in the tree 201.Fa rbt 202immediately preceding the node 203.Fa rb 204or, if 205.Fa rb 206is 207.Dv NULL , 208return the first node in 209.Fa rbt 210or, if the tree is empty, return 211.Dv NULL . 212.Pp 213If 214.Fa direction 215is 216.Dv RB_DIR_RIGHT , 217return the node in the tree 218.Fa rbt 219immediately following the node 220.Fa rb 221or, if 222.Fa rb 223is 224.Dv NULL , 225return the last node in 226.Fa rbt 227or, if the tree is empty, return 228.Dv NULL . 229.It Fn RB_TREE_MIN "rbt" 230Return the first node in 231.Fa rbt , 232i.e. the node with the least key, or 233.Dv NULL 234if 235.Fa rbt 236is empty. 237.It Fn RB_TREE_MAX "rbt" 238Return the last node in 239.Fa rbt , 240i.e. the node with the greatest key, or 241.Dv NULL 242if 243.Fa rbt 244is empty. 245.It Fn RB_TREE_FOREACH "rb" "rbt" 246.Nm RB_TREE_FOREACH 247is a macro to be used in the place of a 248.Dv for 249header preceding a statement to traverse the nodes in 250.Fa rbt 251from least to greatest, assigning 252.Fa rb 253to each node in turn and executing the statement. 254.It Fn RB_TREE_FOREACH_REVERSE "rb" "rbt" 255.Nm RB_TREE_FOREACH_REVERSE 256is a macro to be used in the place of a 257.Dv for 258header preceding a statement to traverse the nodes in 259.Fa rbt 260from greatest to least, assigning 261.Fa rb 262to each node in turn and executing the statement. 263.El 264.Sh CODE REFERENCES 265The 266.Nm 267interface is implemented in 268.Pa common/lib/libc/gen/rb.c . 269.\" .Sh EXAMPLES 270.\" 271.\" XXX: Should contain some examples. 272.\" 273.Sh SEE ALSO 274.Xr queue 3 , 275.Xr tree 3 276.Sh HISTORY 277The 278.Nm 279interface first appeared in 280.Nx 6.0 . 281.Sh AUTHORS 282.An Matt Thomas Aq Mt matt@NetBSD.org 283wrote 284.Nm . 285.Pp 286.An Niels Provos Aq Mt provos@citi.umich.edu 287wrote the 288.Xr tree 3 289manual page. 290Portions of this page derive from that page. 291.\" .Sh CAVEATS 292.\" .Sh BUGS 293.\" .Sh SECURITY CONSIDERATIONS 294