libyarb(3) FreeBSD Library Functions Manual libyarb(3) NAME libyarb – Red-Black Trees SYNOPSIS #include -I/usr/local/include -L/usr/local/lib -lyarb DESCRIPTION LibYarb is Yet Another Red-Black Tree Libary. Red-Black Trees are binary search trees with O(log2 N) performance for insertions, deletions, and lookups. The longest path length is 2 log2(N) where N is the smallest power of 2 that is greater than the number of black nodes in the tree. All library functions are reentrant if concurrent invocations are applied to different structures. USAGE The library uses nodes defined in yarb.h: #define YARB_RED 0 #define YARB_BLACK 1 union yarb_keyval { void *ptr; float num; }; struct yarb { union yarb_keyval key, value; struct yarb *left, *right, *parent; unsigned char color; }; struct yarb_list { union yarb_keyval key, value; }; YARB_INSERT() Insert new keys or update values with yarb_insert(). struct yarb *yarb_insert( struct yarb *tree, int ( *comparator )( const union yarb_keyval first, const union yarb_keyval second ), void ( *func )( const union yarb_keyval value ), const union yarb_keyval key, const union yarb_keyval value ); On success, yarb_insert() returns a pointer to the root node of the tree. You must save this pointer because the root node can change when the tree is rebalanced. If memory allocation fails, yarb_insert() returns NULL. The first argument is the tree. Pass NULL to create a new tree. The second argument is a comparator function used to order the tree. The comparator function must accept 2 union yarb_keyvals. The comparator must return a value < 0 if the first key sorts before the second key. The comparator must return 0 if the first key is equivalent to the second key. The comparator must return a value greater > 0 if the first key sorts after the second key. The third argument is a function to be applied to the current value associated with the key if the key is already present in the tree. This function can be used to deallocate values. The third argument can be NULL. The fourth argument is the key. The fifth argument is the new value to associate with the key. YARB_DELETE() Remove keys with yarb_delete(). struct yarb *yarb_delete( struct yarb *tree, int ( *comparator )( const union yarb_keyval first, const union yarb_keyval second ), void ( *func )( const union yarb_keyval key, const union yarb_keyval value ), const union yarb_keyval key ); yarb_delete() returns a pointer to the root node. You must save this value because the root node can change when the tree is rebalanced. If the tree contains only one node, and you delete it, yarb_delete() returns NULL. The first argument is the tree. The second argument is the comparator function. The third argument is a function to be applied to the key and value of the node to be deleted before it is deleted. This function can be used to deallocate keys and values. The second argument can be NULL. The fourth argument is the key to delete. YARB_LOOKUP() Retrieve a node to examine or modify with yarb_lookup(). struct yarb *yarb_lookup( struct yarb *tree, int ( *comparator )( const union yarb_keyval first, const union yarb_keyval second ), const union yarb_keyval key ); yarb_lookup() returns NULL if the key is not in the tree or the tree is NULL. The first argument is the tree. The second argument is the comparator function. The third argument is the key of the desired node. YARB_FIRST() Use yarb_first() to retrieve the node that sorts first in a tree. struct yarb *yarb_first( struct yarb *tree ); yarb_first() returns NULL if tree is NULL. YARB_LAST() Use yarb_last() to retrieve the node that sorts last in a tree. struct yarb *yarb_last( struct yarb *tree ); yarb_last() returns NULL if tree is NULL. YARB_PREVIOUS() Use yarb_previous() to retrieve the node that sorts immediately before a specified node. struct yarb *yarb_previous( struct yarb *node ); yarb_previous() returns NULL if node is NULL or node is the first node in the tree. YARB_NEXT() Used yarb_next() to retrieve the node that sorts immediately after a specified node. struct yarb *yarb_next( struct yarb *node ); yarb_next() returns NULL if node is NULL or node is the last node in the tree. YARB_TRAVERSE() Use yarb_traverse() to apply a function to all the nodes in a tree. struct yarb *yarb_traverse( struct yarb *tree, void ( *func )( struct yarb *node, void *data ), void *data, int direction ); On success, yarb_traverse() returns a pointer to the root node of the tree. If memory cannot be allocated for temporary storage, yarb_traverse() returns NULL. In this case, the function may have been applied to some or to no nodes in the tree. The first argument is the tree. The second argument is a function to apply to nodes. The function is called with a pointer to a node and an opaque data pointer. The third argument is the opaque data pointer to be passed to the second argument. The fourth argument specifies the order in which the traversal is carried out. A fourth argument of < 0 causes the tree to be traversed in reverse sorted order. A fourth argument of >= 0 causes the tree to be traversed in sorted order. YARB_DESTROY() Use yarb_destroy() to deallocate a tree. int yarb_destroy( struct yarb *tree, void ( *func )( const union yarb_keyval key, const union yarb_keyval value )); On success, yarb_destroy() returns 0. If memory cannot be allocated for temporary storage, yarb_destroy() returns 1. In that case, the tree can be in an inconsistent state. Traversal may cause a crash. The first argument is the tree. The second argument is a function to be applied to the key and value unions of each node before it is deallocated. This function can be used to deallocate keys and values. The second argument can be NULL. YARB_MAKE_STACK() Use yarb_make_stack() to create an automatically resized stack of nodes. Stacks are useful for collecting nodes that match a selection criterion during a traversal of a tree. It is more efficient to iterate over the stack than to traverse a tree multiple times. struct yarb_stack *yarb_make_stack(); yarb_make_stack() returns NULL if memory allocation fails. Stacks are defined in yarb.h: struct yarb_stack { int free, used; struct yarb **top, **values; }; The free and used elements describe the number of free and used elements in the values list. The values list contains a contiguous array of node pointers of length followed by empty slots. The top element points to the node pointer in the values list of the node on the top of the stack. If the stack is empty, top points to the first slot in the values list. yarb_make_stack() creates stacks with 64 free slots in the values list. Pushing more than 64 nodes causes the values list to be resized to its current size plus 64 more slots. Stacks never shrink. You iterate over a stack like this: int i; struct yarb **z; for( i = 0, z = stack->values; i < stack->used; ++i, ++z ) do_something_with( *z ); YARB_STACK_FREE() Deallocte stacks with the YARB_STACK_FREE() macro. void YARB_STACK_FREE( struct yarb_stack *stack ); YARB_STACK_PUSH() Push a node onto the top of a stack with the YARB_STACK_PUSH() macro. struct yarb *YARB_STACK_PUSH( struct yarb_stack *, struct yarb * ) The macro returns the struct yarb pointer pushed or NULL if memory allocation fails. YARB_STACK_POP() Pop a node off the top of a stack with YARB_STACK_POP() macro. struct yarb *YARB_STACK_POP( struct yarb_stack * ); The macro returns NULL if the stack is empty. YARB_STACK_CLEAR() Empty a stack with the YARB_STACK_CLEAR() macro. void YARB_STACK_CLEAR( yarb_stack *stack ); Invoking yarb_stack_clear() on a stack is equivalent to but more efficient than: while( YARB_STACK_POP( stack ) != NULL ) ; AUTHORS James Bailie ⟨jimmy@mammothcheese.ca⟩ http://www.mammothcheese.ca Tue Dec 26, 2017