Fri Mar 19 19:36:28 2010 UTC ()
Some cosmetic modifications, including removal of white space.


(jruoho)
diff -r1.1 -r1.2 src/share/man/man3/rb.3
cvs diff -r1.1 -r1.2 src/share/man/man3/Attic/rb.3 (expand / switch to unified diff)

--- src/share/man/man3/Attic/rb.3 2010/03/19 18:02:22 1.1
+++ src/share/man/man3/Attic/rb.3 2010/03/19 19:36:27 1.2
@@ -1,14 +1,14 @@ @@ -1,14 +1,14 @@
1.\" $NetBSD: rb.3,v 1.1 2010/03/19 18:02:22 dyoung Exp $ 1.\" $NetBSD: rb.3,v 1.2 2010/03/19 19:36:27 jruoho Exp $
2.\" 2.\"
3.\" Copyright (c) 2010 The NetBSD Foundation, Inc. 3.\" Copyright (c) 2010 The NetBSD Foundation, Inc.
4.\" All rights reserved. 4.\" All rights reserved.
5.\" 5.\"
6.\" This code is derived from software contributed to The NetBSD Foundation 6.\" This code is derived from software contributed to The NetBSD Foundation
7.\" by Matt Thomas, Niels Provos, and David Young. 7.\" by Matt Thomas, Niels Provos, and David Young.
8.\" 8.\"
9.\" Redistribution and use in source and binary forms, with or without 9.\" Redistribution and use in source and binary forms, with or without
10.\" modification, are permitted provided that the following conditions 10.\" modification, are permitted provided that the following conditions
11.\" are met: 11.\" are met:
12.\" 1. Redistributions of source code must retain the above copyright 12.\" 1. Redistributions of source code must retain the above copyright
13.\" notice, this list of conditions and the following disclaimer. 13.\" notice, this list of conditions and the following disclaimer.
14.\" 2. Redistributions in binary form must reproduce the above copyright 14.\" 2. Redistributions in binary form must reproduce the above copyright
@@ -43,60 +43,62 @@ @@ -43,60 +43,62 @@
43.Fn rb_tree_find_node "struct rb_tree *" "const void *" 43.Fn rb_tree_find_node "struct rb_tree *" "const void *"
44.Ft struct rb_node * 44.Ft struct rb_node *
45.Fn rb_tree_find_node_geq "struct rb_tree *" "const void *" 45.Fn rb_tree_find_node_geq "struct rb_tree *" "const void *"
46.Ft struct rb_node * 46.Ft struct rb_node *
47.Fn rb_tree_find_node_leq "struct rb_tree *" "const void *" 47.Fn rb_tree_find_node_leq "struct rb_tree *" "const void *"
48.Ft struct rb_node * 48.Ft struct rb_node *
49.Fn rb_tree_iterate "struct rb_tree *" "struct rb_node *" "const unsigned int" 49.Fn rb_tree_iterate "struct rb_tree *" "struct rb_node *" "const unsigned int"
50.Sh DESCRIPTION 50.Sh DESCRIPTION
51.Nm 51.Nm
52provides red-black trees. 52provides red-black trees.
53A red-black tree is a binary search tree with the node color as an 53A red-black tree is a binary search tree with the node color as an
54extra attribute. 54extra attribute.
55It fulfills a set of conditions: 55It fulfills a set of conditions:
56.Bl -enum -compact -offset indent 56.Bl -enum -offset indent
57.It  57.It
58every search path from the root to a leaf consists of the same number of 58Every search path from the root to a leaf consists of the same number of
59black nodes, 59black nodes.
60.It  60.It
61each red node (except for the root) has a black parent, 61Each red node (except for the root) has a black parent.
62.It  62.It
63each leaf node is black. 63Each leaf node is black.
64.El  64.El
65.Pp 65.Pp
66Every operation on a red-black tree is bounded as O(lg n). 66Every operation on a red-black tree is bounded as O(lg n).
67The maximum height of a red-black tree is 2lg (n+1). 67The maximum height of a red-black tree is 2lg (n+1).
68.Sh TYPES 68.Sh TYPES
69.Bl -tag -width compact 69.Bl -tag -width compact
70.It Vt struct rb_tree 70.It Vt struct rb_tree
71A red-black tree. 71A red-black tree.
72.It Vt typedef signed int (*const rbto_compare_nodes_fn)(const struct rb_node *, const struct rb_node *); 72.It Vt typedef signed int \
 73(*const rbto_compare_nodes_fn)(const struct rb_node *, const struct rb_node *);
73The node-comparison operator. 74The node-comparison operator.
74Defines an ordering on nodes. 75Defines an ordering on nodes.
75Returns a positive value if the first node precedes the second node. 76Returns a positive value if the first node precedes the second node.
76Returns a negative value if the first node follows the second node. 77Returns a negative value if the first node follows the second node.
77Returns 0 if the first node and the second are identical according 78Returns 0 if the first node and the second are identical according
78to the ordering. 79to the ordering.
79.It Vt typedef signed int (*const rbto_compare_key_fn)(const struct rb_node *, const void *); 80.It Vt typedef signed int \
 81(*const rbto_compare_key_fn)(const struct rb_node *, const void *);
80The node-key comparison operator. 82The node-key comparison operator.
81Defines the order of nodes and keys. 83Defines the order of nodes and keys.
82Returns a positive value if the node precedes the key. 84Returns a positive value if the node precedes the key.
83Returns a negative value if the node follows the key. 85Returns a negative value if the node follows the key.
84Returns 0 if the node is identical to the ey according to the ordering. 86Returns 0 if the node is identical to the key according to the ordering.
85.It Vt struct rb_tree_ops 87.It Vt struct rb_tree_ops
86Defines the operators for comparing two nodes in the same tree, 88Defines the operators for comparing two nodes in the same tree,
87and for comparing a node in the tree with a key. 89and for comparing a node in the tree with a key.
88Members of 90Members of
89.Vt rb_tree_ops  91.Vt rb_tree_ops
90are 92are
91.Bd -literal 93.Bd -literal
92 rbto_compare_nodes_fn rbto_compare_nodes; 94 rbto_compare_nodes_fn rbto_compare_nodes;
93 rbto_compare_key_fn rbto_compare_key; 95 rbto_compare_key_fn rbto_compare_key;
94.Ed 96.Ed
95.It Vt struct rb_node 97.It Vt struct rb_node
96A node in a red-black tree. 98A node in a red-black tree.
97.Sh FUNCTIONS 99.Sh FUNCTIONS
98.Bl -tag -width compact 100.Bl -tag -width compact
99.It Fn rb_tree_init "rbt" "ops" 101.It Fn rb_tree_init "rbt" "ops"
100Initialize the red-black tree 102Initialize the red-black tree
101.Fa rbt . 103.Fa rbt .
102Let the comparison operators given by 104Let the comparison operators given by
@@ -111,80 +113,80 @@ Insert the node @@ -111,80 +113,80 @@ Insert the node
111into the tree 113into the tree
112.Fa rbt . 114.Fa rbt .
113Return 115Return
114.Dv true 116.Dv true
115on success, 117on success,
116.Dv false 118.Dv false
117on failure. 119on failure.
118.It Fn rb_tree_find_node "rbt" "key" 120.It Fn rb_tree_find_node "rbt" "key"
119Search the tree 121Search the tree
120.Fa rbt 122.Fa rbt
121for a node exactly matching 123for a node exactly matching
122.Fa key . 124.Fa key .
123If no such node is in the tree, return 125If no such node is in the tree, return
124.Dv NULL .  126.Dv NULL .
125Otherwise, return the matching node. 127Otherwise, return the matching node.
126.It Fn rb_tree_find_node_geq "rbt" "key" 128.It Fn rb_tree_find_node_geq "rbt" "key"
127Search the tree 129Search the tree
128.Fa rbt 130.Fa rbt
129for a node that exactly matches 131for a node that exactly matches
130.Fa key 132.Fa key
131and return it. 133and return it.
132If no such node is present, return the first node following 134If no such node is present, return the first node following
133.Fa key 135.Fa key
134or, if no such node is in the tree, return 136or, if no such node is in the tree, return
135.Dv NULL .  137.Dv NULL .
136.It Fn rb_tree_find_node_leq "rbt" "key" 138.It Fn rb_tree_find_node_leq "rbt" "key"
137Search the tree 139Search the tree
138.Fa rbt 140.Fa rbt
139for a node that exactly matches 141for a node that exactly matches
140.Fa key 142.Fa key
141and return it. 143and return it.
142If no such node is present, return the first node preceding 144If no such node is present, return the first node preceding
143.Fa key 145.Fa key
144or, if no such node is in the tree, return 146or, if no such node is in the tree, return
145.Dv NULL . 147.Dv NULL .
146.It Fn rb_tree_iterate "rbt" "rb" "direction" 148.It Fn rb_tree_iterate "rbt" "rb" "direction"
147If 149If
148.Fa direction 150.Fa direction
149is 151is
150.Dv RB_DIR_LEFT , 152.Dv RB_DIR_LEFT ,
151return the node in the tree 153return the node in the tree
152.Fa rbt 154.Fa rbt
153immediately preceding the node 155immediately preceding the node
154.Fa rb 156.Fa rb
155or, if 157or, if
156.Fa rb 158.Fa rb
157is 159is
158.Dv NULL , 160.Dv NULL ,
159return the last node in 161return the last node in
160.Fa rbt  162.Fa rbt
161or, if the tree is empty, return 163or, if the tree is empty, return
162.Dv NULL . 164.Dv NULL .
163.Pp 165.Pp
164If 166If
165.Fa direction 167.Fa direction
166is 168is
167.Dv RB_DIR_RIGHT , 169.Dv RB_DIR_RIGHT ,
168return the node in the tree 170return the node in the tree
169.Fa rbt 171.Fa rbt
170immediately following the node 172immediately following the node
171.Fa rb 173.Fa rb
172or, if 174or, if
173.Fa rb 175.Fa rb
174is 176is
175.Dv NULL , 177.Dv NULL ,
176return the first node in 178return the first node in
177.Fa rbt  179.Fa rbt
178or, if the tree is empty, return 180or, if the tree is empty, return
179.Dv NULL . 181.Dv NULL .
180.El 182.El
181.Sh CODE REFERENCES 183.Sh CODE REFERENCES
182This section describes places within the 184This section describes places within the
183.Nx 185.Nx
184source tree where actual code implementing 186source tree where actual code implementing
185.Nm 187.Nm
186can be found. 188can be found.
187All pathnames are relative to 189All pathnames are relative to
188.Pa /usr/src . 190.Pa /usr/src .
189.Pp 191.Pp
190.Nm 192.Nm
@@ -197,17 +199,17 @@ is implemented within the file @@ -197,17 +199,17 @@ is implemented within the file
197.Sh HISTORY 199.Sh HISTORY
198The 200The
199.Nm 201.Nm
200interface first appeared in 202interface first appeared in
201.Nx 6.0 . 203.Nx 6.0 .
202.Sh AUTHORS 204.Sh AUTHORS
203.An Matt Thomas Aq matt@NetBSD.org 205.An Matt Thomas Aq matt@NetBSD.org
204wrote 206wrote
205.Nm . 207.Nm .
206.Pp 208.Pp
207.An Niels Provos Aq provos@citi.umich.edu 209.An Niels Provos Aq provos@citi.umich.edu
208wrote the 210wrote the
209.Xr tree 3 211.Xr tree 3
210manual page. Portions of this page derive from that page.  212manual page. Portions of this page derive from that page.
211.\" .Sh CAVEATS 213.\" .Sh CAVEATS
212.\" .Sh BUGS 214.\" .Sh BUGS
213.\" .Sh SECURITY CONSIDERATIONS 215.\" .Sh SECURITY CONSIDERATIONS