Module Name: src
Committed By: jruoho
Date: Sun Oct 24 06:57:05 UTC 2010
Modified Files:
src/distrib/sets/lists/comp: mi
src/share/man/man3: Makefile
Added Files:
src/share/man/man3: rbtree.3
Removed Files:
src/share/man/man3: rb.3
Log Message:
Catch-up with code changes.
To generate a diff of this commit:
cvs rdiff -u -r1.1514 -r1.1515 src/distrib/sets/lists/comp/mi
cvs rdiff -u -r1.56 -r1.57 src/share/man/man3/Makefile
cvs rdiff -u -r1.4 -r0 src/share/man/man3/rb.3
cvs rdiff -u -r0 -r1.1 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/distrib/sets/lists/comp/mi
diff -u src/distrib/sets/lists/comp/mi:1.1514 src/distrib/sets/lists/comp/mi:1.1515
--- src/distrib/sets/lists/comp/mi:1.1514 Wed Oct 20 09:22:33 2010
+++ src/distrib/sets/lists/comp/mi Sun Oct 24 06:57:04 2010
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.1514 2010/10/20 09:22:33 jmmv Exp $
+# $NetBSD: mi,v 1.1515 2010/10/24 06:57:04 jruoho Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -7773,7 +7773,8 @@
./usr/share/man/cat3/randomid_delete.0 comp-c-catman .cat
./usr/share/man/cat3/randomid_new.0 comp-c-catman .cat
./usr/share/man/cat3/raw.0 comp-c-catman .cat
-./usr/share/man/cat3/rb.0 comp-c-catman .cat
+./usr/share/man/cat3/rb.0 comp-obsolete obsolete
+./usr/share/man/cat3/rbtree.0 comp-c-catman .cat
./usr/share/man/cat3/rb_tree_find_node.0 comp-c-catman .cat
./usr/share/man/cat3/rb_tree_find_node_geq.0 comp-c-catman .cat
./usr/share/man/cat3/rb_tree_find_node_leq.0 comp-c-catman .cat
@@ -13677,7 +13678,8 @@
./usr/share/man/html3/randomid_delete.html comp-c-htmlman html
./usr/share/man/html3/randomid_new.html comp-c-htmlman html
./usr/share/man/html3/raw.html comp-c-htmlman html
-./usr/share/man/html3/rb.html comp-c-htmlman html
+./usr/share/man/html3/rb.html comp-obsolete obsolete
+./usr/share/man/html3/rbtree.html comp-c-htmlman html
./usr/share/man/html3/rb_tree_find_node.html comp-c-htmlman html
./usr/share/man/html3/rb_tree_find_node_geq.html comp-c-htmlman html
./usr/share/man/html3/rb_tree_find_node_leq.html comp-c-htmlman html
@@ -19581,7 +19583,8 @@
./usr/share/man/man3/randomid_delete.3 comp-c-man .man
./usr/share/man/man3/randomid_new.3 comp-c-man .man
./usr/share/man/man3/raw.3 comp-c-man .man
-./usr/share/man/man3/rb.3 comp-c-man .man
+./usr/share/man/man3/rb.3 comp-obsolete obsolete
+./usr/share/man/man3/rbtree.3 comp-c-man .man
./usr/share/man/man3/rb_tree_find_node.3 comp-c-man .man
./usr/share/man/man3/rb_tree_find_node_geq.3 comp-c-man .man
./usr/share/man/man3/rb_tree_find_node_leq.3 comp-c-man .man
Index: src/share/man/man3/Makefile
diff -u src/share/man/man3/Makefile:1.56 src/share/man/man3/Makefile:1.57
--- src/share/man/man3/Makefile:1.56 Sat Oct 16 10:27:08 2010
+++ src/share/man/man3/Makefile Sun Oct 24 06:57:04 2010
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.56 2010/10/16 10:27:08 skrll Exp $
+# $NetBSD: Makefile,v 1.57 2010/10/24 06:57:04 jruoho Exp $
# @(#)Makefile 8.2 (Berkeley) 12/13/93
MAN= _DIAGASSERT.3 __CONCAT.3 __UNCONST.3 CMSG_DATA.3 \
@@ -6,7 +6,7 @@
dlfcn.3 dl_iterate_phdr.3 end.3 \
fast_divide32.3 ffs32.3 gcq.3 \
ilog2.3 intro.3 inttypes.3 iso646.3 \
- offsetof.3 queue.3 rb.3 sigevent.3 \
+ offsetof.3 queue.3 rbtree.3 sigevent.3 \
stdarg.3 stdbool.3 stddef.3 stdint.3 stdlib.3 sysexits.3 \
tgmath.3 timeradd.3 timeval.3 tree.3 types.3 varargs.3
@@ -195,12 +195,12 @@
queue.3 CIRCLEQ_PREV.3 \
queue.3 CIRCLEQ_LOOP_NEXT.3 \
queue.3 CIRCLEQ_LOOP_PREV.3
-MLINKS+=rb.3 rb_tree_init.3 \
- rb.3 rb_tree_insert_node.3 \
- rb.3 rb_tree_find_node.3 \
- rb.3 rb_tree_find_node_geq.3 \
- rb.3 rb_tree_find_node_leq.3 \
- rb.3 rb_tree_iterate.3
+MLINKS+=rbtree.3 rb_tree_init.3 \
+ rbtree.3 rb_tree_insert_node.3 \
+ rbtree.3 rb_tree_find_node.3 \
+ rbtree.3 rb_tree_find_node_geq.3 \
+ rbtree.3 rb_tree_find_node_leq.3 \
+ rbtree.3 rb_tree_iterate.3
MLINKS+=stdarg.3 va_arg.3 stdarg.3 va_copy.3 \
stdarg.3 va_end.3 stdarg.3 va_start.3
MLINKS+=dirent.3 dir.3 \
Added files:
Index: src/share/man/man3/rbtree.3
diff -u /dev/null src/share/man/man3/rbtree.3:1.1
--- /dev/null Sun Oct 24 06:57:05 2010
+++ src/share/man/man3/rbtree.3 Sun Oct 24 06:57:04 2010
@@ -0,0 +1,217 @@
+.\" $NetBSD: rbtree.3,v 1.1 2010/10/24 06:57:04 jruoho Exp $
+.\"
+.\" Copyright (c) 2010 The NetBSD Foundation, 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 October 24, 2010
+.Dt RBTREE 3
+.Os
+.Sh NAME
+.Nm rbtree
+.Nd red-black tree
+.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"
+.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 struct rb_tree
+A red-black tree.
+.It Vt typedef signed int \
+(*const rbto_compare_nodes_fn)(const struct rb_node *, const struct rb_node *);
+The node-comparison operator.
+Defines an ordering on nodes.
+Returns a positive value if the first node precedes the second node.
+Returns a negative value if the first node follows the second node.
+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 *);
+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.
+Members of
+.Vt rb_tree_ops
+are
+.Bd -literal
+ rbto_compare_nodes_fn rbto_compare_nodes;
+ rbto_compare_key_fn rbto_compare_key;
+.Ed
+.It Vt struct rb_node
+A node in a red-black tree.
+.El
+.Sh FUNCTIONS
+.Bl -tag -width compact
+.It Fn rb_tree_init "rbt" "ops"
+Initialize the red-black tree
+.Fa rbt .
+Let the comparison operators 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
+.Dv true
+on success,
+.Dv false
+on failure.
+.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 last 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 first node in
+.Fa rbt
+or, if the tree is empty, return
+.Dv NULL .
+.El
+.Sh CODE REFERENCES
+This section describes places within the
+.Nx
+source tree where actual code implementing
+.Nm
+can be found.
+All pathnames are relative to
+.Pa /usr/src .
+.Pp
+.Nm
+is implemented within the file
+.Pa common/lib/libc/gen/rb.c .
+.\" .Sh EXAMPLES
+.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 m...@netbsd.org
+wrote
+.Nm .
+.Pp
+.An Niels Provos Aq pro...@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
