1.\" $NetBSD: rbtree.3,v 1.5 2011/03/28 13:46:14 ahoka 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 17, 2011 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 *" "const rb_tree_ops_t *" 42.Ft void * 43.Fn rb_tree_insert_node "rb_tree_t *" "void *" 44.Ft void 45.Fn rb_tree_remove_node "rb_tree_t *" "void *" 46.Ft void * 47.Fn rb_tree_find_node "rb_tree_t *" "const void *" 48.Ft void * 49.Fn rb_tree_find_node_geq "rb_tree_t *" "const void *" 50.Ft void * 51.Fn rb_tree_find_node_leq "rb_tree_t *" "const void *" 52.Ft void * 53.Fn rb_tree_iterate "rb_tree_t *" "void *" "const unsigned int" 54.Sh DESCRIPTION 55.Nm 56provides red-black trees. 57A red-black tree is a binary search tree with the node color as an 58extra attribute. 59It fulfills a set of conditions: 60.Bl -enum -offset indent 61.It 62Every search path from the root to a leaf consists of the same number of 63black nodes. 64.It 65Each red node (except for the root) has a black parent. 66.It 67Each leaf node is black. 68.El 69.Pp 70Every operation on a red-black tree is bounded as O(lg n). 71The maximum height of a red-black tree is 2lg (n+1). 72.Sh TYPES 73.Bl -tag -width compact 74.It Vt rb_tree_t 75A red-black tree. 76.It Vt typedef signed int \ 77(*const rbto_compare_nodes_fn)(void *, const void *, const void *); 78The node-comparison operator. 79Defines an ordering on nodes. 80Returns a negative value if the first node precedes the second node. 81Returns a positive value if the first node follows the second node. 82Returns 0 if the first node and the second are identical according 83to the ordering. 84.It Vt typedef signed int \ 85(*const rbto_compare_key_fn)(void *, const void *, const void *); 86The node-key comparison operator. 87Defines the order of nodes and keys. 88Returns a negative value if the node precedes the key. 89Returns a positive value if the node follows the key. 90Returns 0 if the node is identical to the key according to the ordering. 91.It Vt rb_tree_ops_t 92Defines the operator for comparing two nodes in the same tree, 93the operator for comparing a node in the tree with a key, 94the offset of member 95.Vt rb_node_t 96within a node, 97and the opaque context passed to the operators. 98Members of 99.Vt rb_tree_ops_t 100are 101.Bd -literal 102 rbto_compare_nodes_fn rbto_compare_nodes; 103 rbto_compare_key_fn rbto_compare_key; 104 size_t rbto_node_offset; 105 void *rbto_context; 106.Ed 107.It Vt rb_node_t 108A node in a red-black tree has this structure as a member. 109.El 110.Sh FUNCTIONS 111.Bl -tag -width compact 112.It Fn rb_tree_init "rbt" "ops" 113Initialize the red-black tree 114.Fa rbt . 115Let the comparison operators given by 116.Fa ops 117define the order of nodes in the tree for 118the purposes of insertion, search, and iteration. 119.Fn rb_tree_init 120always succeeds. 121.It Fn rb_tree_insert_node "rbt" "rb" 122Insert the node 123.Fa rb 124into the tree 125.Fa rbt . 126Return inserted node on success, 127already existing node on failure. 128.It Fn rb_tree_remove_node "rbt" "rb" 129Remove the node 130.Fa rb 131from the tree 132.Fa rbt . 133.It Fn rb_tree_find_node "rbt" "key" 134Search the tree 135.Fa rbt 136for a node exactly matching 137.Fa key . 138If no such node is in the tree, return 139.Dv NULL . 140Otherwise, return the matching node. 141.It Fn rb_tree_find_node_geq "rbt" "key" 142Search the tree 143.Fa rbt 144for a node that exactly matches 145.Fa key 146and return it. 147If no such node is present, return the first node following 148.Fa key 149or, if no such node is in the tree, return 150.Dv NULL . 151.It Fn rb_tree_find_node_leq "rbt" "key" 152Search the tree 153.Fa rbt 154for a node that exactly matches 155.Fa key 156and return it. 157If no such node is present, return the first node preceding 158.Fa key 159or, if no such node is in the tree, return 160.Dv NULL . 161.It Fn rb_tree_iterate "rbt" "rb" "direction" 162If 163.Fa direction 164is 165.Dv RB_DIR_LEFT , 166return the node in the tree 167.Fa rbt 168immediately preceding the node 169.Fa rb 170or, if 171.Fa rb 172is 173.Dv NULL , 174return the last node in 175.Fa rbt 176or, if the tree is empty, return 177.Dv NULL . 178.Pp 179If 180.Fa direction 181is 182.Dv RB_DIR_RIGHT , 183return the node in the tree 184.Fa rbt 185immediately following the node 186.Fa rb 187or, if 188.Fa rb 189is 190.Dv NULL , 191return the first node in 192.Fa rbt 193or, if the tree is empty, return 194.Dv NULL . 195.El 196.Sh CODE REFERENCES 197The 198.Nm 199interface is implemented in 200.Pa common/lib/libc/gen/rb.c . 201.\" .Sh EXAMPLES 202.\" 203.\" XXX: Should contain some examples. 204.\" 205.Sh SEE ALSO 206.Xr queue 3 , 207.Xr tree 3 208.Sh HISTORY 209The 210.Nm 211interface first appeared in 212.Nx 6.0 . 213.Sh AUTHORS 214.An Matt Thomas Aq matt@NetBSD.org 215wrote 216.Nm . 217.Pp 218.An Niels Provos Aq provos@citi.umich.edu 219wrote the 220.Xr tree 3 221manual page. 222Portions of this page derive from that page. 223.\" .Sh CAVEATS 224.\" .Sh BUGS 225.\" .Sh SECURITY CONSIDERATIONS 226