[apple/libc.git] / gen / NetBSD / rbtree.3

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