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