|
| wb_tree * | wb_tree_new (dict_compare_func cmp_func) |
| | Create an empty tree that orders keys with |cmp_func| (must not be NULL).
|
| |
| dict * | wb_dict_new (dict_compare_func cmp_func) |
| | Like wb_tree_new(), but wrapped in a generic dict for use with the dict_* macros.
|
| |
| size_t | wb_tree_free (wb_tree *tree, dict_delete_func delete_func) |
| | Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL, and free the tree.
|
| |
| dict_insert_result | wb_tree_insert (wb_tree *tree, void *key) |
| | Insert |key| unless an equal key is present.
|
| |
| void ** | wb_tree_search (wb_tree *tree, const void *key) |
| | Return the address of the datum stored for |key|, or NULL if |key| is not present.
|
| |
| void ** | wb_tree_search_le (wb_tree *tree, const void *key) |
| | Return the address of the datum of the greatest key less than or equal to |key|, or NULL if there is none.
|
| |
| void ** | wb_tree_search_lt (wb_tree *tree, const void *key) |
| | Return the address of the datum of the greatest key less than |key|, or NULL if there is none.
|
| |
| void ** | wb_tree_search_ge (wb_tree *tree, const void *key) |
| | Return the address of the datum of the least key greater than or equal to |key|, or NULL if there is none.
|
| |
| void ** | wb_tree_search_gt (wb_tree *tree, const void *key) |
| | Return the address of the datum of the least key greater than |key|, or NULL if there is none.
|
| |
| dict_remove_result | wb_tree_remove (wb_tree *tree, const void *key) |
| | Remove the element with key |key|.
|
| |
| size_t | wb_tree_clear (wb_tree *tree, dict_delete_func delete_func) |
| | Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL.
|
| |
| size_t | wb_tree_traverse (wb_tree *tree, dict_visit_func visit, void *user_data) |
| | Call |visit|(key, datum, |user_data|) for each element in key order, stopping early if |visit| returns false.
|
| |
| bool | wb_tree_select (wb_tree *tree, size_t n, const void **key, void **datum) |
| | Store the key and datum of the |n|th element in key order (0-based) through |key| and |datum| and return true, or store NULL through them and return false if |n| is out of range.
|
| |
| size_t | wb_tree_count (const wb_tree *tree) |
| | Return the number of elements.
|
| |
| size_t | wb_tree_min_path_length (const wb_tree *tree) |
| | Return the shallowest depth at which a child link is absent, the root being at depth 1, or 0 for an empty tree.
|
| |
| size_t | wb_tree_max_path_length (const wb_tree *tree) |
| | Return the greatest depth of any node, the root being at depth 1, or 0 for an empty tree: the height of the tree.
|
| |
| size_t | wb_tree_total_path_length (const wb_tree *tree) |
| | Return the sum of the depths of all nodes, the root being at depth 1, or 0 for an empty tree.
|
| |
| bool | wb_tree_verify (const wb_tree *tree) |
| | Check the internal invariants of the tree and return true if they hold, or print the first failed check to stderr and return false.
|
| |
| wb_itor * | wb_itor_new (wb_tree *tree) |
| | Create an iterator over |tree| that is not positioned on any element yet.
|
| |
| dict_itor * | wb_dict_itor_new (wb_tree *tree) |
| | Like wb_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.
|
| |
| void | wb_itor_free (wb_itor *itor) |
| | Free an iterator.
|
| |
| bool | wb_itor_valid (const wb_itor *itor) |
| | Return whether |itor| is positioned on an element.
|
| |
| void | wb_itor_invalidate (wb_itor *itor) |
| | Unposition |itor|, so that it is not positioned on any element.
|
| |
| bool | wb_itor_next (wb_itor *itor) |
| | Move |itor| to the next element in key order and return true, or unposition it and return false if there is none.
|
| |
| bool | wb_itor_prev (wb_itor *itor) |
| | Move |itor| to the previous element in key order and return true, or unposition it and return false if there is none.
|
| |
| bool | wb_itor_nextn (wb_itor *itor, size_t count) |
| | Move |itor| |count| elements forward and return whether it is still positioned.
|
| |
| bool | wb_itor_prevn (wb_itor *itor, size_t count) |
| | Move |itor| |count| elements back and return whether it is still positioned.
|
| |
| bool | wb_itor_first (wb_itor *itor) |
| | Position |itor| on the first element in key order and return true, or unposition it and return false if the tree is empty.
|
| |
| bool | wb_itor_last (wb_itor *itor) |
| | Position |itor| on the last element in key order and return true, or unposition it and return false if the tree is empty.
|
| |
| bool | wb_itor_search (wb_itor *itor, const void *key) |
| | Position |itor| on |key| and return true, or unposition it and return false if |key| is not present.
|
| |
| bool | wb_itor_search_le (wb_itor *itor, const void *key) |
| | Position |itor| on the greatest key less than or equal to |key| and return true, or unposition it and return false if there is none.
|
| |
| bool | wb_itor_search_lt (wb_itor *itor, const void *key) |
| | Position |itor| on the greatest key less than |key| and return true, or unposition it and return false if there is none.
|
| |
| bool | wb_itor_search_ge (wb_itor *itor, const void *key) |
| | Position |itor| on the least key greater than or equal to |key| and return true, or unposition it and return false if there is none.
|
| |
| bool | wb_itor_search_gt (wb_itor *itor, const void *key) |
| | Position |itor| on the least key greater than |key| and return true, or unposition it and return false if there is none.
|
| |
| const void * | wb_itor_key (const wb_itor *itor) |
| | Return the key |itor| is positioned on, or NULL if it is not positioned.
|
| |
| void ** | wb_itor_datum (wb_itor *itor) |
| | Return the address of the datum |itor| is positioned on, through which it can be read or replaced, or NULL if it is not positioned.
|
| |
| int | wb_itor_compare (const wb_itor *i1, const wb_itor *i2) |
| | Compare the positions of two iterators over the same tree: return a negative value, zero, or a positive value as |i1| is before, at, or after |i2| in key order.
|
| |
| bool | wb_itor_remove (wb_itor *itor) |
| | Remove the element |itor| is positioned on and unposition |itor|; return false if it was not positioned.
|
| |
Weight-balanced tree, BB[alpha] with alpha = 1 - sqrt(2)/2.
Each node stores the size of its subtree, and the subtrees of every node are kept within a fixed ratio of each other, so insert, search and remove take O(log n) time in the worst case, and selecting the nth element also takes only O(log n).
Definition in file wb_tree.h.
1.12.0