RBTREE(3) NetBSD Library Functions Manual RBTREE(3)NAMErbtree-- red-black treeLIBRARYStandard C Library (libc, -lc)SYNOPSIS#include <sys/rbtree.h>voidrb_tree_init(rb_tree_t *rbt,const rb_tree_ops_t *ops);void *rb_tree_insert_node(rb_tree_t *rbt,void *rb);voidrb_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,unsigned int direction);void *RB_TREE_MIN(rb_tree_t *rbt);void *RB_TREE_MAX(rb_tree_t *rbt);RB_TREE_FOREACH(void *rb,rb_tree_t *rbt);RB_TREE_FOREACH_REVERSE(void *rb,rb_tree_t *rbt);DESCRIPTIONrbtreeprovides 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).TYPESrb_tree_tA red-black tree.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 nodenode1precedes the second nodenode2. Returns a positive value if the first nodenode1follows the second nodenode2. Returns 0 if the first nodenode1and the second nodenode2are identical according to the ordering.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 nodenodeprecedes the keykey. Returns a positive value if the nodenodefollows the keykey. Returns 0 if the nodenodeis identical to the keykeyaccording to the ordering.rb_tree_ops_tDefines 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 memberrb_node_twithin the node type, and the opaque context pointer passed to the comparison functions. Members ofrb_tree_ops_tare rbto_compare_nodes_fn rbto_compare_nodes; rbto_compare_key_fn rbto_compare_key; size_t rbto_node_offset; void *rbto_context;rb_node_tA node in a red-black tree has this structure as a member. The offset of therb_node_tmember in the caller's node structure should be provided asrbto_node_offset. (None of the functions in therbtreeinterface are meant to take pointers directly to therb_node_tmember.)FUNCTIONSrb_tree_init(rbt,ops) Initialize the red-black treerbt. Let the comparison functions given byopsdefine 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 noderbinto the treerbt. Return inserted node on success, already existing node on failure.rb_tree_remove_node(rbt,rb) Remove the noderbfrom the treerbt.rb_tree_find_node(rbt,key) Search the treerbtfor a node exactly matchingkey. 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 treerbtfor a node that exactly matcheskeyand return it. If no such node is present, return the first node followingkeyor, if no such node is in the tree, return NULL.rb_tree_find_node_leq(rbt,key) Search the treerbtfor a node that exactly matcheskeyand return it. If no such node is present, return the first node precedingkeyor, if no such node is in the tree, return NULL.rb_tree_iterate(rbt,rb,direction) Ifdirectionis RB_DIR_LEFT, return the node in the treerbtimmediately preceding the noderbor, ifrbis NULL, return the first node inrbtor, if the tree is empty, return NULL. Ifdirectionis RB_DIR_RIGHT, return the node in the treerbtimmediately following the noderbor, ifrbis NULL, return the last node inrbtor, if the tree is empty, return NULL.RB_TREE_MIN(rbt) Return the first node inrbt, i.e. the node with the least key, or NULL ifrbtis empty.RB_TREE_MAX(rbt) Return the last node inrbt, i.e. the node with the greatest key, or NULL ifrbtis empty.RB_TREE_FOREACH(rb,rbt)RB_TREE_FOREACHis a macro to be used in the place of a for header preceding a statement to traverse the nodes inrbtfrom least to greatest, assigningrbto each node in turn and execut- ing the statement.RB_TREE_FOREACH_REVERSE(rb,rbt)RB_TREE_FOREACH_REVERSEis a macro to be used in the place of a for header preceding a statement to traverse the nodes inrbtfrom greatest to least, assigningrbto each node in turn and executing the statement.CODE REFERENCESTherbtreeinterface is implemented incommon/lib/libc/gen/rb.c.SEE ALSOqueue(3), tree(3)HISTORYTherbtreeinterface first appeared in NetBSD 6.0.AUTHORSMatt Thomas <matt@NetBSD.org> wroterbtree. Niels Provos <provos@citi.umich.edu> wrote the tree(3) manual page. Por- tions of this page derive from that page. NetBSD 8.0 August 29, 2016 NetBSD 8.0

You can also request any man page by name and (optionally) by section: |

©1996-2017 Modified for NetBSD by Kimmo Suominen