\"     $NetBSD: rbtree.3,v 1.13 2019/03/07 12:05:54 roy 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 March 4, 2019
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 "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" "unsigned int direction"
Ft void *
Fn RB_TREE_MIN "rb_tree_t *rbt"
Ft void *
Fn RB_TREE_MAX "rb_tree_t *rbt"
Fn RB_TREE_NEXT "rb_tree_t *rbt" "void *rb"
Fn RB_TREE_PREV "rb_tree_t *rbt" "void *rb"
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_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_NEXT "rbt" "rb"
Return the next node in
Fa rbt ,
or
Dv NULL
if there is none.
It Fn RB_TREE_PREV "rbt" "rb"
Return the previous node in
Fa rbt ,
or
Dv NULL
if there is none.
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"
Allows both the removal of
Fa rb
as well as freeing it from within the loop safely without interfering
with the traversal.
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"
Allows both the removal of
Fa rb
as well as freeing it from within the loop safely without interfering
with the traversal.
El
Sh CODE REFERENCES
The
Nm
interface is implemented in
Pa common/lib/libc/gen/rb.c .
\" .Sh EXAMPLES
\"
\" XXX: Should contain some 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 Mt [email protected]
wrote
Nm .
Pp
An Niels Provos Aq Mt [email protected]
wrote the
Xr tree 3
manual page.
Portions of this page derive from that page.
\" .Sh CAVEATS
\" .Sh BUGS
\" .Sh SECURITY CONSIDERATIONS

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.