|
| pr_tree * | pr_tree_new (dict_compare_func cmp_func) |
| | Create an empty tree that orders keys with |cmp_func| (must not be NULL).
|
| |
| dict * | pr_dict_new (dict_compare_func cmp_func) |
| | Like pr_tree_new(), but wrapped in a generic dict for use with the dict_* macros.
|
| |
| size_t | pr_tree_free (pr_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 | pr_tree_insert (pr_tree *tree, void *key) |
| | Insert |key| unless an equal key is present.
|
| |
| void ** | pr_tree_search (pr_tree *tree, const void *key) |
| | Return the address of the datum stored for |key|, or NULL if |key| is not present.
|
| |
| void ** | pr_tree_search_le (pr_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 ** | pr_tree_search_lt (pr_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 ** | pr_tree_search_ge (pr_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 ** | pr_tree_search_gt (pr_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 | pr_tree_remove (pr_tree *tree, const void *key) |
| | Remove the element with key |key|.
|
| |
| size_t | pr_tree_clear (pr_tree *tree, dict_delete_func delete_func) |
| | Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL.
|
| |
| size_t | pr_tree_traverse (pr_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 | pr_tree_select (pr_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 | pr_tree_count (const pr_tree *tree) |
| | Return the number of elements.
|
| |
| size_t | pr_tree_min_path_length (const pr_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 | pr_tree_max_path_length (const pr_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 | pr_tree_total_path_length (const pr_tree *tree) |
| | Return the sum of the depths of all nodes, the root being at depth 1, or 0 for an empty tree.
|
| |
| bool | pr_tree_verify (const pr_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.
|
| |
| pr_itor * | pr_itor_new (pr_tree *tree) |
| | Create an iterator over |tree| that is not positioned on any element yet.
|
| |
| dict_itor * | pr_dict_itor_new (pr_tree *tree) |
| | Like pr_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.
|
| |
| void | pr_itor_free (pr_itor *itor) |
| | Free an iterator.
|
| |
| bool | pr_itor_valid (const pr_itor *itor) |
| | Return whether |itor| is positioned on an element.
|
| |
| void | pr_itor_invalidate (pr_itor *itor) |
| | Unposition |itor|, so that it is not positioned on any element.
|
| |
| bool | pr_itor_next (pr_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 | pr_itor_prev (pr_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 | pr_itor_nextn (pr_itor *itor, size_t count) |
| | Move |itor| |count| elements forward and return whether it is still positioned.
|
| |
| bool | pr_itor_prevn (pr_itor *itor, size_t count) |
| | Move |itor| |count| elements back and return whether it is still positioned.
|
| |
| bool | pr_itor_first (pr_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 | pr_itor_last (pr_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 | pr_itor_search (pr_itor *itor, const void *key) |
| | Position |itor| on |key| and return true, or unposition it and return false if |key| is not present.
|
| |
| bool | pr_itor_search_le (pr_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 | pr_itor_search_lt (pr_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 | pr_itor_search_ge (pr_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 | pr_itor_search_gt (pr_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 * | pr_itor_key (const pr_itor *itor) |
| | Return the key |itor| is positioned on, or NULL if it is not positioned.
|
| |
| void ** | pr_itor_datum (pr_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 | pr_itor_compare (const pr_itor *i1, const pr_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 | pr_itor_remove (pr_itor *itor) |
| | Remove the element |itor| is positioned on and unposition |itor|; return false if it was not positioned.
|
| |
Path-reduction tree [Gonnet 1983].
Each node stores the size of its subtree, and the tree rotates whenever a rotation reduces the total path length, which keeps it balanced: insert, search and remove take O(log n) time, and selecting the nth element also takes only O(log n).
Definition in file pr_tree.h.
1.12.0