libindex(3) FreeBSD Library Functions Manual libindex(3) NAME libindex – Static Balanced Binary Search Trees SYNOPSIS #include -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; float 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 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 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. 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 December 26, 2017