Module Name: src Committed By: enami Date: Mon Nov 8 03:20:59 UTC 2010
Modified Files: src/share/man/man3: rbtree.3 Log Message: - Add library section. - Fix function signatures. - Describe added member to an ops structure. - Describe rb_tree_remove_node. To generate a diff of this commit: cvs rdiff -u -r1.1 -r1.2 src/share/man/man3/rbtree.3 Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files.
Modified files: Index: src/share/man/man3/rbtree.3 diff -u src/share/man/man3/rbtree.3:1.1 src/share/man/man3/rbtree.3:1.2 --- src/share/man/man3/rbtree.3:1.1 Sun Oct 24 06:57:04 2010 +++ src/share/man/man3/rbtree.3 Mon Nov 8 03:20:59 2010 @@ -1,4 +1,4 @@ -.\" $NetBSD: rbtree.3,v 1.1 2010/10/24 06:57:04 jruoho Exp $ +.\" $NetBSD: rbtree.3,v 1.2 2010/11/08 03:20:59 enami Exp $ .\" .\" Copyright (c) 2010 The NetBSD Foundation, Inc. .\" All rights reserved. @@ -27,26 +27,30 @@ .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE .\" POSSIBILITY OF SUCH DAMAGE. .\" -.Dd October 24, 2010 +.Dd November 8, 2010 .Dt RBTREE 3 .Os .Sh NAME .Nm rbtree .Nd red-black tree +.Sh LIBRARY +.Lb libc .Sh SYNOPSIS .In sys/rbtree.h .Ft void -.Fn rb_tree_init "struct rb_tree *" "const struct rb_tree_ops *" -.Ft bool -.Fn rb_tree_insert_node "struct rb_tree *" "struct rb_node *" -.Ft struct rb_node * -.Fn rb_tree_find_node "struct rb_tree *" "const void *" -.Ft struct rb_node * -.Fn rb_tree_find_node_geq "struct rb_tree *" "const void *" -.Ft struct rb_node * -.Fn rb_tree_find_node_leq "struct rb_tree *" "const void *" -.Ft struct rb_node * -.Fn rb_tree_iterate "struct rb_tree *" "struct rb_node *" "const unsigned int" +.Fn rb_tree_init "rb_tree_t *" "const rb_tree_ops_t *" +.Ft void * +.Fn rb_tree_insert_node "rb_tree_t *" "void *" +.Ft void +.Fn rb_tree_remove_node "rb_tree_t *" "void *" +.Ft void * +.Fn rb_tree_find_node "rb_tree_t *" "const void *" +.Ft void * +.Fn rb_tree_find_node_geq "rb_tree_t *" "const void *" +.Ft void * +.Fn rb_tree_find_node_leq "rb_tree_t *" "const void *" +.Ft void * +.Fn rb_tree_iterate "rb_tree_t *" "void *" "const unsigned int" .Sh DESCRIPTION .Nm provides red-black trees. @@ -67,10 +71,10 @@ The maximum height of a red-black tree is 2lg (n+1). .Sh TYPES .Bl -tag -width compact -.It Vt struct rb_tree +.It Vt rb_tree_t A red-black tree. .It Vt typedef signed int \ -(*const rbto_compare_nodes_fn)(const struct rb_node *, const struct rb_node *); +(*const rbto_compare_nodes_fn)(void *, const void *, const void *); The node-comparison operator. Defines an ordering on nodes. Returns a positive value if the first node precedes the second node. @@ -78,24 +82,30 @@ Returns 0 if the first node and the second are identical according to the ordering. .It Vt typedef signed int \ -(*const rbto_compare_key_fn)(const struct rb_node *, const void *); +(*const rbto_compare_key_fn)(void *, const void *, const void *); The node-key comparison operator. Defines the order of nodes and keys. Returns a positive value if the node precedes the key. Returns a negative value if the node follows the key. Returns 0 if the node is identical to the key according to the ordering. -.It Vt struct rb_tree_ops -Defines the operators for comparing two nodes in the same tree, -and for comparing a node in the tree with a key. +.It Vt rb_tree_ops_t +Defines the operator for comparing two nodes in the same tree, +the operator for comparing a node in the tree with a key, +the offset of member +.Vt rb_node_t +within a node, +and the opaque context passed to the operators. Members of -.Vt rb_tree_ops +.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 struct rb_node -A node in a red-black tree. +.It Vt rb_node_t +A node in a red-black tree has this structure as a member. .El .Sh FUNCTIONS .Bl -tag -width compact @@ -113,11 +123,13 @@ .Fa rb into the tree .Fa rbt . -Return -.Dv true -on success, -.Dv false -on failure. +Return inserted node on success, +already existing node on failure. +.It Fn rb_tree_remove_node "rbt" "rb" +Remove the node +.Fa node +from the tree +.Fa rbt . .It Fn rb_tree_find_node "rbt" "key" Search the tree .Fa rbt