|
| sp_tree * | sp_tree_new (dict_compare_func cmp_func) |
| | Create an empty tree that orders keys with |cmp_func| (must not be NULL).
|
| |
| dict * | sp_dict_new (dict_compare_func cmp_func) |
| | Like sp_tree_new(), but wrapped in a generic dict for use with the dict_* macros.
|
| |
| size_t | sp_tree_free (sp_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 | sp_tree_insert (sp_tree *tree, void *key) |
| | Insert |key| unless an equal key is present.
|
| |
| void ** | sp_tree_search (sp_tree *tree, const void *key) |
| | Return the address of the datum stored for |key|, or NULL if |key| is not present.
|
| |
| void ** | sp_tree_search_le (sp_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 ** | sp_tree_search_lt (sp_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 ** | sp_tree_search_ge (sp_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 ** | sp_tree_search_gt (sp_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 | sp_tree_remove (sp_tree *tree, const void *key) |
| | Remove the element with key |key|.
|
| |
| size_t | sp_tree_clear (sp_tree *tree, dict_delete_func delete_func) |
| | Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL.
|
| |
| size_t | sp_tree_traverse (sp_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 | sp_tree_select (sp_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 | sp_tree_count (const sp_tree *tree) |
| | Return the number of elements.
|
| |
| size_t | sp_tree_min_path_length (const sp_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 | sp_tree_max_path_length (const sp_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 | sp_tree_total_path_length (const sp_tree *tree) |
| | Return the sum of the depths of all nodes, the root being at depth 1, or 0 for an empty tree.
|
| |
| bool | sp_tree_verify (const sp_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.
|
| |
| sp_itor * | sp_itor_new (sp_tree *tree) |
| | Create an iterator over |tree| that is not positioned on any element yet.
|
| |
| dict_itor * | sp_dict_itor_new (sp_tree *tree) |
| | Like sp_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.
|
| |
| void | sp_itor_free (sp_itor *itor) |
| | Free an iterator.
|
| |
| bool | sp_itor_valid (const sp_itor *itor) |
| | Return whether |itor| is positioned on an element.
|
| |
| void | sp_itor_invalidate (sp_itor *itor) |
| | Unposition |itor|, so that it is not positioned on any element.
|
| |
| bool | sp_itor_next (sp_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 | sp_itor_prev (sp_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 | sp_itor_nextn (sp_itor *itor, size_t count) |
| | Move |itor| |count| elements forward and return whether it is still positioned.
|
| |
| bool | sp_itor_prevn (sp_itor *itor, size_t count) |
| | Move |itor| |count| elements back and return whether it is still positioned.
|
| |
| bool | sp_itor_first (sp_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 | sp_itor_last (sp_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 | sp_itor_search (sp_itor *itor, const void *key) |
| | Position |itor| on |key| and return true, or unposition it and return false if |key| is not present.
|
| |
| bool | sp_itor_search_le (sp_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 | sp_itor_search_lt (sp_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 | sp_itor_search_ge (sp_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 | sp_itor_search_gt (sp_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 * | sp_itor_key (const sp_itor *itor) |
| | Return the key |itor| is positioned on, or NULL if it is not positioned.
|
| |
| void ** | sp_itor_datum (sp_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 | sp_itor_compare (const sp_itor *i1, const sp_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 | sp_itor_remove (sp_itor *itor) |
| | Remove the element |itor| is positioned on and unposition |itor|; return false if it was not positioned.
|
| |
Splay tree.
Every access moves the key it finds to the root ("splaying"), so a sequence of m operations on n elements takes O((n + m) log(n + m)) time: amortized O(log n) per operation, though a single operation can take O(n). Recently used keys are cheap to find again. Because searches restructure the tree, a splay tree must not be read concurrently even without writers. Selecting the nth element takes O(n).
Definition in file sp_tree.h.
1.12.0