1.\" $NetBSD: rbtree.3,v 1.10 2014/03/18 18:20:39 riastradh 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 13, 2013 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 operator. 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 operator. 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 operator for comparing two nodes in the same tree, 118the operator for comparing a node in the tree with a key, 119the offset of member 120.Vt rb_node_t 121within a node, 122and the opaque context passed to the operators. 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. 134.El 135.Sh FUNCTIONS 136.Bl -tag -width compact 137.It Fn rb_tree_init "rbt" "ops" 138Initialize the red-black tree 139.Fa rbt . 140Let the comparison operators given by 141.Fa ops 142define the order of nodes in the tree for 143the purposes of insertion, search, and iteration. 144.Fn rb_tree_init 145always succeeds. 146.It Fn rb_tree_insert_node "rbt" "rb" 147Insert the node 148.Fa rb 149into the tree 150.Fa rbt . 151Return inserted node on success, 152already existing node on failure. 153.It Fn rb_tree_remove_node "rbt" "rb" 154Remove the node 155.Fa rb 156from the tree 157.Fa rbt . 158.It Fn rb_tree_find_node "rbt" "key" 159Search the tree 160.Fa rbt 161for a node exactly matching 162.Fa key . 163If no such node is in the tree, return 164.Dv NULL . 165Otherwise, return the matching node. 166.It Fn rb_tree_find_node_geq "rbt" "key" 167Search the tree 168.Fa rbt 169for a node that exactly matches 170.Fa key 171and return it. 172If no such node is present, return the first node following 173.Fa key 174or, if no such node is in the tree, return 175.Dv NULL . 176.It Fn rb_tree_find_node_leq "rbt" "key" 177Search the tree 178.Fa rbt 179for a node that exactly matches 180.Fa key 181and return it. 182If no such node is present, return the first node preceding 183.Fa key 184or, if no such node is in the tree, return 185.Dv NULL . 186.It Fn rb_tree_iterate "rbt" "rb" "direction" 187If 188.Fa direction 189is 190.Dv RB_DIR_LEFT , 191return the node in the tree 192.Fa rbt 193immediately preceding the node 194.Fa rb 195or, if 196.Fa rb 197is 198.Dv NULL , 199return the first node in 200.Fa rbt 201or, if the tree is empty, return 202.Dv NULL . 203.Pp 204If 205.Fa direction 206is 207.Dv RB_DIR_RIGHT , 208return the node in the tree 209.Fa rbt 210immediately following the node 211.Fa rb 212or, if 213.Fa rb 214is 215.Dv NULL , 216return the last node in 217.Fa rbt 218or, if the tree is empty, return 219.Dv NULL . 220.It Fn RB_TREE_MIN "rbt" 221Return the first node in 222.Fa rbt , 223i.e. the node with the least key, or 224.Dv NULL 225if 226.Fa rbt 227is empty. 228.It Fn RB_TREE_MAX "rbt" 229Return the last node in 230.Fa rbt , 231i.e. the node with the greatest key, or 232.Dv NULL 233if 234.Fa rbt 235is empty. 236.It Fn RB_TREE_FOREACH "rb" "rbt" 237.Nm RB_TREE_FOREACH 238is a macro to be used in the place of a 239.Dv for 240header preceding a statement to traverse the nodes in 241.Fa rbt 242from least to greatest, assigning 243.Fa rb 244to each node in turn and executing the statement. 245.It Fn RB_TREE_FOREACH_REVERSE "rb" "rbt" 246.Nm RB_TREE_FOREACH_REVERSE 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 greatest to least, assigning 252.Fa rb 253to each node in turn and executing the statement. 254.El 255.Sh CODE REFERENCES 256The 257.Nm 258interface is implemented in 259.Pa common/lib/libc/gen/rb.c . 260.\" .Sh EXAMPLES 261.\" 262.\" XXX: Should contain some examples. 263.\" 264.Sh SEE ALSO 265.Xr queue 3 , 266.Xr tree 3 267.Sh HISTORY 268The 269.Nm 270interface first appeared in 271.Nx 6.0 . 272.Sh AUTHORS 273.An Matt Thomas Aq Mt matt@NetBSD.org 274wrote 275.Nm . 276.Pp 277.An Niels Provos Aq Mt provos@citi.umich.edu 278wrote the 279.Xr tree 3 280manual page. 281Portions of this page derive from that page. 282.\" .Sh CAVEATS 283.\" .Sh BUGS 284.\" .Sh SECURITY CONSIDERATIONS 285