libyarb(8)              FreeBSD System Manager's Manual             libyarb(8)

NAME
     libyarb - Red-Black Trees

SYNOPSIS
     #include <yarb.h>
     -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;
        int 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 <used>
     length followed by <free> 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

                                 June 27, 2017