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

NAME
     libindex - Static Balanced Binary Search Trees

SYNOPSIS
     #include <index.h>
     -I/usr/local/include -L/usr/local/lib -lindex

DESCRIPTION
     Index Trees are static binary search trees.  You can change the values
     associated with keys, but you cannot remove keys or insert new keys.

     Trees are bulk-loaded to be as close to perfectly balanced as they can be
     in weight and height, resulting in longest path lengths of log2(N) where
     N is the smallest power of 2 larger than the number of nodes in a tree.

     All library functions are reentrant if concurrent invocations are applied
     to different structures.

USAGE
     The library uses nodes defined in index.h:

     union index_keyval
     {
        void *ptr;
        int num;
     };

     struct index
     {
        union index_keyval key, value;
        struct index *left, *right, *parent;
     };

     struct index_list
     {
        union index_keyval key, value;
     };

   INDEX_INIT()
     Bulk load a tree with index_init().

     struct index *index_init( int nkeys,
                               struct index_list *list,
                               int ( comparator )( const union index_keyval *first,
                                                   const union index_keyval *second ));

     On success, index_init() returns a pointer to the root node of the tree.
     If memory allocation fails, index_init() returns NULL.

     The first argument is a positive value specifying the number of keys.

     The second argument is a pointer to a list of index_list structures of
     <nkeys> length.  Each item in the list contains a key and its initial
     value.  As a side-effect, the list will be sorted by key when
     index_init() returns.  The list can be deallocated after index_init()
     returns.

     The third argument is a comparator function used to order the tree.  The
     comparator function must accept 2 pointers to union index_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.

   INDEX_LOOKUP()
     Retrieve a node to examine or modify with index_lookup().

     struct index *index_lookup( struct index *tree,
                                 int ( *comparator )( const union index_keyval first,
                                                      const union index_keyval second ),
                                 const union index_keyval key );

     The first argument is the tree.

     The second argument is the comparator function.  Note that this
     comparator accepts 2 union index_keyvals and not 2 pointers to union
     index_keyvals.

     The third argument is the key of the desired node.

     index_lookup() returns NULL if the key is not in the tree.  Because the
     key set is static, you can save the values returned from index_lookup()
     for frequently accessed keys.

   INDEX_FIRST()
     Use index_first() to retrieve the node that sorts first in a tree.

     struct index *index_first( struct index *tree );

     index_first() returns NULL if tree is NULL.

   INDEX_LAST()
     Use index_last() to retrieve the node that sorts last in a tree.

     struct index *index_last( struct index *tree );

     index_last() returns NULL if tree is NULL.

   INDEX_PREVIOUS()
     Use index_previous() to retrieve the node that sorts immediately before a
     specified node.

     struct index *index_previous( struct index *node );

     index_previous() returns NULL if node is NULL or node is the first node
     in the tree.

   INDEX_NEXT()
     Used index_next() to retrieve the node that sorts immediately after a
     specified node.

     struct index *index_next( struct index *node );

     index_next() returns NULL if node is NULL or node is the last node in the
     tree.

   INDEX_TRAVERSE()
     Use index_traverse() to apply a function to all the nodes in a tree.

     struct index *index_traverse( struct index *tree,
                                   void ( *func )( struct index *node, void *data ),
                                   void *data,
                                   int direction );

     On success, index_traverse() returns a pointer to the root node of the
     tree.  If memory cannot be allocated for temporary storage,
     index_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 caller-supplied function to apply to nodes.  The
     function is called with a pointer to a node and a caller specified 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.

   INDEX_DESTROY()
     Use index_destroy() to deallocate a tree.

     int index_destroy( struct index *tree,
                        void ( *func )( const union index_keyval key,
                                        const union index_keyval value ));

     On success, index_destroy() returns 0.  If memory cannot be allocated for
     temporary storage, index_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 caller-supplied 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.

   INDEX_MAKE_STACK()
     Use index_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 index_stack *index_make_stack();

     index_make_stack() returns NULL if memory allocation fails.

     Stacks are defined in index.h:

     struct index_stack
     {
        int free, used;
        struct index **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.

     index_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 index **z;

     for( i = 0, z = stack->values; i < stack->used; ++i, ++z )
        do_something_with( *z );

   INDEX_STACK_FREE()
     Deallocte stacks with the INDEX_STACK_FREE() macro.

     void INDEX_STACK_FREE( struct index_stack *stack );

   INDEX_STACK_PUSH()
     Push a node onto the top of a stack with the INDEX_STACK_PUSH() macro.

     struct index *INDEX_STACK_PUSH( struct index_stack *, struct index * )

     The macro returns the struct index pointer pushed or NULL if memory
     allocation fails.

   INDEX_STACK_POP()
     Pop a node off the top of a stack with INDEX_STACK_POP() macro.

     struct index *INDEX_STACK_POP( struct index_stack * );

     The macro returns NULL if the stack is empty.

   INDEX_STACK_CLEAR()
     Empty a stack with the INDEX_STACK_CLEAR() macro.

     void INDEX_STACK_CLEAR( index_stack *stack );

     Invoking index_stack_clear() on a stack is equivalent to but more
     efficient than:

     while( INDEX_STACK_POP( stack ) != NULL )
        ;

AUTHORS
     James Bailie <jimmy@mammothcheese.ca>
     http://www.mammothcheese.ca

                              June 23, 2017