
RBTREE(3) BSD Library Functions Manual RBTREE(3)
NAME
rbtree  redblack tree
LIBRARY
Standard C Library (libc, lc)
SYNOPSIS
#include <sys/rbtree.h>
void
rb_tree_init(rb_tree_t *rbt, const rb_tree_ops_t *ops);
void *
rb_tree_insert_node(rb_tree_t *rbt, void *rb);
void
rb_tree_remove_node(rb_tree_t *rbt, void *rb);
void *
rb_tree_find_node(rb_tree_t *rbt, const void *key);
void *
rb_tree_find_node_geq(rb_tree_t *rbt, const void *key);
void *
rb_tree_find_node_leq(rb_tree_t *rbt, const void *key);
void *
rb_tree_iterate(rb_tree_t *rbt, void *rb, const unsigned int direction);
DESCRIPTION
rbtree provides redblack trees. A redblack tree is a binary search tree with the node
color as an extra attribute. It fulfills a set of conditions:
1. Every search path from the root to a leaf consists of the same number of black
nodes.
2. Each red node (except for the root) has a black parent.
3. Each leaf node is black.
Every operation on a redblack tree is bounded as O(lg n). The maximum height of a red
black tree is 2lg (n+1).
TYPES
rb_tree_t
A redblack tree.
typedef signed int (*const rbto_compare_nodes_fn)(void *context, const void *node1, const
void *node2);
The nodecomparison operator. Defines an ordering on nodes. Returns a negative
value if the first node node1 precedes the second node node2. Returns a positive
value if the first node node1 follows the second node node2. Returns 0 if the
first node node1 and the second node node2 are identical according to the ordering.
typedef signed int (*const rbto_compare_key_fn)(void *context, const void *node, const void
*key);
The nodekey comparison operator. Defines the order of nodes and keys. Returns a
negative value if the node node precedes the key key. Returns a positive value if
the node node follows the key key. Returns 0 if the node node is identical to the
key key according to the ordering.
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 rb_node_t within a
node, and the opaque context passed to the operators. Members of rb_tree_ops_t are
rbto_compare_nodes_fn rbto_compare_nodes;
rbto_compare_key_fn rbto_compare_key;
size_t rbto_node_offset;
void *rbto_context;
rb_node_t
A node in a redblack tree has this structure as a member.
FUNCTIONS
rb_tree_init(rbt, ops)
Initialize the redblack tree rbt. Let the comparison operators given by ops
define the order of nodes in the tree for the purposes of insertion, search, and
iteration. rb_tree_init() always succeeds.
rb_tree_insert_node(rbt, rb)
Insert the node rb into the tree rbt. Return inserted node on success, already
existing node on failure.
rb_tree_remove_node(rbt, rb)
Remove the node rb from the tree rbt.
rb_tree_find_node(rbt, key)
Search the tree rbt for a node exactly matching key. If no such node is in the
tree, return NULL. Otherwise, return the matching node.
rb_tree_find_node_geq(rbt, key)
Search the tree rbt for a node that exactly matches key and return it. If no such
node is present, return the first node following key or, if no such node is in the
tree, return NULL.
rb_tree_find_node_leq(rbt, key)
Search the tree rbt for a node that exactly matches key and return it. If no such
node is present, return the first node preceding key or, if no such node is in the
tree, return NULL.
rb_tree_iterate(rbt, rb, direction)
If direction is RB_DIR_LEFT, return the node in the tree rbt immediately preceding
the node rb or, if rb is NULL, return the last node in rbt or, if the tree is
empty, return NULL.
If direction is RB_DIR_RIGHT, return the node in the tree rbt immediately following
the node rb or, if rb is NULL, return the first node in rbt or, if the tree is
empty, return NULL.
CODE REFERENCES
The rbtree interface is implemented in common/lib/libc/gen/rb.c.
SEE ALSO
queue(3), tree(3)
HISTORY
The rbtree interface first appeared in NetBSD 6.0.
AUTHORS
Matt Thomas <matt@NetBSD.org> wrote rbtree.
Niels Provos <provos@citi.umich.edu> wrote the tree(3) manual page. Portions of this page
derive from that page.
BSD August 19, 2012 BSD 
