Man page or keyword search:   man All Sections 1 - General Commands 2 - System Calls 3 - Subroutines, Functions 4 - Special Files 5 - File Formats 6 - Games and Screensavers 7 - Macros and Conventions 8 - Maintenence Commands 9 - Kernel Interface New Commands Server 4.4BSD AIX Alpinelinux Archlinux Aros BSDOS BSDi Bifrost CentOS Cygwin Darwin Debian DigitalUNIX DragonFly ElementaryOS Fedora FreeBSD Gentoo GhostBSD HP-UX Haiku Hurd IRIX Inferno JazzOS Kali Knoppix LinuxMint MacOSX Mageia Mandriva Manjaro Minix MirBSD NeXTSTEP NetBSD OPENSTEP OSF1 OpenBSD OpenDarwin OpenIndiana OpenMandriva OpenServer OpenSuSE OpenVMS Oracle PC-BSD Peanut Pidora Plan9 QNX Raspbian RedHat Scientific Slackware SmartOS Solaris SuSE SunOS Syllable Tru64 UNIXv7 Ubuntu Ultrix UnixWare Xenix YellowDog aLinux   9087 pages apropos Keyword Search (all sections) Output format html ascii pdf view pdf save postscript

RBTREE(3)		 BSD Library Functions Manual		     RBTREE(3)

NAME
     rbtree — red-black 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 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:

	   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 red-black tree is bounded as O(lg n).	 The maximum
     height of a red-black tree is 2lg (n+1).

TYPES
     rb_tree_t
	      A red-black tree.

     typedef signed int (*const rbto_compare_nodes_fn)(void *context, const
	      void *node1, const void *node2);
	      The node-comparison 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 node-key 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 red-black tree has this structure as a member.

FUNCTIONS
     rb_tree_init(rbt, ops)
	      Initialize the red-black tree rbt.  Let the comparison operators
	      given by ops define the order of nodes in the tree for the pur‐
	      poses 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 match‐
	      ing 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.  Por‐
     tions of this page derive from that page.

BSD				August 19, 2012				   BSD

                             _         _         _ 
                            | |       | |       | |     
                            | |       | |       | |     
                         __ | | __ __ | | __ __ | | __  
                         \ \| |/ / \ \| |/ / \ \| |/ /  
                          \ \ / /   \ \ / /   \ \ / /   
                           \   /     \   /     \   /    
                            \_/       \_/       \_/ 

Vote for polarhome