|
| hb_tree * | hb_tree_new (dict_compare_func cmp_func) |
| | Create an empty tree that orders keys with |cmp_func| (must not be NULL).
|
| |
| dict * | hb_dict_new (dict_compare_func cmp_func) |
| | Like hb_tree_new(), but wrapped in a generic dict for use with the dict_* macros.
|
| |
| size_t | hb_tree_free (hb_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 | hb_tree_insert (hb_tree *tree, void *key) |
| | Insert |key| unless an equal key is present.
|
| |
| void ** | hb_tree_search (hb_tree *tree, const void *key) |
| | Return the address of the datum stored for |key|, or NULL if |key| is not present.
|
| |
| void ** | hb_tree_search_le (hb_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 ** | hb_tree_search_lt (hb_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 ** | hb_tree_search_ge (hb_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 ** | hb_tree_search_gt (hb_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 | hb_tree_remove (hb_tree *tree, const void *key) |
| | Remove the element with key |key|.
|
| |
| size_t | hb_tree_clear (hb_tree *tree, dict_delete_func delete_func) |
| | Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL.
|
| |
| size_t | hb_tree_traverse (hb_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 | hb_tree_select (hb_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 | hb_tree_count (const hb_tree *tree) |
| | Return the number of elements.
|
| |
| size_t | hb_tree_min_path_length (const hb_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 | hb_tree_max_path_length (const hb_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 | hb_tree_total_path_length (const hb_tree *tree) |
| | Return the sum of the depths of all nodes, the root being at depth 1, or 0 for an empty tree.
|
| |
| bool | hb_tree_verify (const hb_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.
|
| |
| hb_itor * | hb_itor_new (hb_tree *tree) |
| | Create an iterator over |tree| that is not positioned on any element yet.
|
| |
| dict_itor * | hb_dict_itor_new (hb_tree *tree) |
| | Like hb_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.
|
| |
| void | hb_itor_free (hb_itor *itor) |
| | Free an iterator.
|
| |
| bool | hb_itor_valid (const hb_itor *itor) |
| | Return whether |itor| is positioned on an element.
|
| |
| void | hb_itor_invalidate (hb_itor *itor) |
| | Unposition |itor|, so that it is not positioned on any element.
|
| |
| bool | hb_itor_next (hb_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 | hb_itor_prev (hb_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 | hb_itor_nextn (hb_itor *itor, size_t count) |
| | Move |itor| |count| elements forward and return whether it is still positioned.
|
| |
| bool | hb_itor_prevn (hb_itor *itor, size_t count) |
| | Move |itor| |count| elements back and return whether it is still positioned.
|
| |
| bool | hb_itor_first (hb_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 | hb_itor_last (hb_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 | hb_itor_search (hb_itor *itor, const void *key) |
| | Position |itor| on |key| and return true, or unposition it and return false if |key| is not present.
|
| |
| bool | hb_itor_search_le (hb_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 | hb_itor_search_lt (hb_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 | hb_itor_search_ge (hb_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 | hb_itor_search_gt (hb_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 * | hb_itor_key (const hb_itor *itor) |
| | Return the key |itor| is positioned on, or NULL if it is not positioned.
|
| |
| void ** | hb_itor_datum (hb_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 | hb_itor_compare (const hb_itor *i1, const hb_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 | hb_itor_remove (hb_itor *itor) |
| | Remove the element |itor| is positioned on and unposition |itor|; return false if it was not positioned.
|
| |
Height-balanced (AVL) tree.
The heights of the two subtrees of every node differ by at most one, so insert, search and remove take O(log n) time in the worst case. Selecting the nth element takes O(n). The balance factor is stored in the low bits of each node's parent pointer, so the allocator must return 4-byte aligned memory.
Definition in file hb_tree.h.
1.12.0