AVL tree. More...
Go to the source code of this file.
Data Structures | |
| struct | tommy_tree_struct |
| Tree container type. More... | |
Typedefs | |
| typedef tommy_node | tommy_tree_node |
| Tree node. More... | |
| typedef struct tommy_tree_struct | tommy_tree |
| Tree container type. More... | |
Functions | |
| void | tommy_tree_init (tommy_tree *tree, tommy_compare_func *cmp) |
| Initializes the tree. More... | |
| void | tommy_tree_swap (tommy_tree *first, tommy_tree *second) |
| Exchanges the contents of two initialized trees, including their comparison functions. More... | |
| void | tommy_tree_clear (tommy_tree *tree) |
| Removes all elements, preserving the comparison function. More... | |
| TOMMY_API void | tommy_tree_insert (tommy_tree *tree, tommy_tree_node *node, void *data) |
| Inserts an element in the tree, allowing duplicate keys. More... | |
| TOMMY_API void * | tommy_tree_insert_unique (tommy_tree *tree, tommy_tree_node *node, void *data) |
| Inserts an element only if no equal element is already contained. More... | |
| TOMMY_API void | tommy_tree_to_list (tommy_tree *tree, tommy_list *list) |
| Transfers all elements from the tree to the tail of a list in tree order. More... | |
| TOMMY_API void * | tommy_tree_remove_existing (tommy_tree *tree, tommy_tree_node *node) |
| Removes an element from the tree. More... | |
| tommy_tree_node * | tommy_tree_parent (tommy_tree_node *node) |
| Gets the parent of the specified node. More... | |
| tommy_tree_node * | tommy_tree_next (tommy_tree_node *node) |
| Gets the node following the specified one in tree order. More... | |
| tommy_tree_node * | tommy_tree_prev (tommy_tree_node *node) |
| Gets the node preceding the specified one in tree order. More... | |
| tommy_tree_node * | tommy_tree_head (tommy_tree *tree) |
| Gets the head (smallest) node in the tree. More... | |
| tommy_tree_node * | tommy_tree_tail (tommy_tree *tree) |
| Gets the tail (greatest) node in the tree. More... | |
| void * | tommy_tree_remove_head (tommy_tree *tree) |
| Removes and returns the head (smallest) element. More... | |
| void * | tommy_tree_remove_tail (tommy_tree *tree) |
| Removes and returns the tail (greatest) element. More... | |
| tommy_tree_node * | tommy_tree_find_compare (tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg) |
| Finds the first equal node in the tree with a specific comparison function. More... | |
| tommy_tree_node * | tommy_tree_find (tommy_tree *tree, const void *data) |
| Finds the first equal node in the tree. More... | |
| void * | tommy_tree_search_compare (tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg) |
| Searches an element in the tree with a specific comparison function. More... | |
| void * | tommy_tree_search (tommy_tree *tree, const void *data) |
| Searches an element in the tree. More... | |
| tommy_tree_node * | tommy_tree_find_greater_equal_compare (tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg) |
| Finds a node in the tree with key greater or equal than the specified one with a specific comparison function. More... | |
| tommy_tree_node * | tommy_tree_find_greater_equal (tommy_tree *tree, const void *data) |
| Finds a node in the tree with key greater or equal than the specified one. More... | |
| void * | tommy_tree_search_greater_equal_compare (tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg) |
| Searches an element in the tree with key greater or equal than the specified one with a specific comparison function. More... | |
| void * | tommy_tree_search_greater_equal (tommy_tree *tree, const void *data) |
| Searches an element in the tree with key greater or equal than the specified one. More... | |
| tommy_tree_node * | tommy_tree_find_greater_compare (tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg) |
| Finds the first node in tree order with key strictly greater than the specified one using a specific comparison function. More... | |
| tommy_tree_node * | tommy_tree_find_greater (tommy_tree *tree, const void *data) |
| Finds the first node in tree order with key strictly greater than the specified one. More... | |
| void * | tommy_tree_search_greater_compare (tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg) |
| Searches the first element in tree order with key strictly greater than the specified one using a specific comparison function. More... | |
| void * | tommy_tree_search_greater (tommy_tree *tree, const void *data) |
| Searches the first element in tree order with key strictly greater than the specified one. More... | |
| tommy_tree_node * | tommy_tree_find_less_equal_compare (tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg) |
| Finds a node in the tree with key less or equal than the specified one with a specific comparison function. More... | |
| tommy_tree_node * | tommy_tree_find_less_equal (tommy_tree *tree, const void *data) |
| Finds a node in the tree with key less or equal than the specified one. More... | |
| void * | tommy_tree_search_less_equal_compare (tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg) |
| Searches an element in the tree with key less or equal than the specified one with a specific comparison function. More... | |
| void * | tommy_tree_search_less_equal (tommy_tree *tree, const void *data) |
| Searches an element in the tree with key less or equal than the specified one. More... | |
| tommy_tree_node * | tommy_tree_find_less_compare (tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg) |
| Finds the last node in tree order with key strictly less than the specified one using a specific comparison function. More... | |
| tommy_tree_node * | tommy_tree_find_less (tommy_tree *tree, const void *data) |
| Finds the last node in tree order with key strictly less than the specified one. More... | |
| void * | tommy_tree_search_less_compare (tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg) |
| Searches the last element in tree order with key strictly less than the specified one using a specific comparison function. More... | |
| void * | tommy_tree_search_less (tommy_tree *tree, const void *data) |
| Searches the last element in tree order with key strictly less than the specified one. More... | |
| void * | tommy_tree_remove_compare (tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg) |
| Searches and removes an element from the tree with a specific comparison function. More... | |
| void * | tommy_tree_remove (tommy_tree *tree, const void *data) |
| Searches and removes an element from the tree. More... | |
| TOMMY_API void | tommy_tree_foreach (tommy_tree *tree, tommy_foreach_func *func) |
| Calls the specified function for each element in the tree. More... | |
| TOMMY_API void | tommy_tree_foreach_arg (tommy_tree *tree, tommy_foreach_arg_func *func, void *arg) |
| Calls the specified function with an argument for each element in the tree. More... | |
| tommy_bool_t | tommy_tree_empty (const tommy_tree *tree) |
| Checks whether the tree is empty. More... | |
| tommy_size_t | tommy_tree_count (const tommy_tree *tree) |
| Gets the number of elements. More... | |
| TOMMY_API tommy_size_t | tommy_tree_memory_usage (const tommy_tree *tree) |
| Gets the size of allocated memory. More... | |
AVL tree.
This tree is a standard AVL tree implementation that stores elements in the order defined by the comparison function.
Duplicate elements are allowed. They are visited in insertion order. Use tommy_tree_insert_unique() to reject duplicate keys.
To initialize a tree you have to call tommy_tree_init() specifying a comparison function that will define the order in the tree.
To insert elements in the tree you have to call tommy_tree_insert() for each element. In the insertion call you have to specify the address of the node and the address of the element. The address of the element is used to initialize the tommy_node::data field of the node.
To find the first element with a given key in tree order, call tommy_tree_search() providing the key to search.
To iterate over all the elements in the tree you can call tommy_tree_head() to get the head of the tree and follow the next elements with tommy_tree_next().
Iterators are pointers to nodes contained in the tree. Inserting elements or removing other nodes between iterator calls does not invalidate pointers to nodes that remain in the tree. Subsequent next/prev calls use the current contents and ordering; inserted elements may become visible and removed elements are skipped.
Removing the pointed node invalidates its use as an iterator, even if its storage has not been freed. To continue traversal after removing the current node, obtain the next or previous node before removal.
Keys and fields used for ordering must not be modified while contained. Concurrent traversal and modification require external synchronization.
To remove the first element with a given key in tree order, call tommy_tree_remove() providing the key to search and remove.
You can also remove an element from the tree if you already have the node address using tommy_tree_remove_existing().
To remove the smallest or greatest element you can use tommy_tree_remove_head() or tommy_tree_remove_tail().
To destroy the tree you have to remove or destroy all the contained elements. The tree itself doesn't have or need a deallocation function. This can be done with the tommy_tree_foreach() function.
| typedef tommy_node tommy_tree_node |
Tree node.
This is the node that you have to include inside your elements. The node must preserve its natural alignment because the tree stores the balance factor in the two least significant bits of the parent pointer.
| typedef struct tommy_tree_struct tommy_tree |
Tree container type.
| void tommy_tree_init | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp | ||
| ) |
Initializes the tree.
| tree | The tree. |
| cmp | The comparison function that defines the order in the tree. |
| void tommy_tree_swap | ( | tommy_tree * | first, |
| tommy_tree * | second | ||
| ) |
Exchanges the contents of two initialized trees, including their comparison functions.
Each comparison function moves with its root to preserve the tree order. The trees must not share nodes. Nodes are not accessed or modified. Passing the same tree twice has no effect.
| first | The first tree. |
| second | The second tree. |
| void tommy_tree_clear | ( | tommy_tree * | tree | ) |
Removes all elements, preserving the comparison function.
The tree remains initialized and can be reused immediately. Elements are not freed and nodes are not accessed or modified. Their links must not be used to traverse the previous contents. You can call this function after tommy_tree_foreach() has freed the elements.
| tree | The tree. |
| TOMMY_API void tommy_tree_insert | ( | tommy_tree * | tree, |
| tommy_tree_node * | node, | ||
| void * | data | ||
| ) |
Inserts an element in the tree, allowing duplicate keys.
Equal elements are visited in insertion order. You have to provide the pointer of the node embedded into the element and the pointer to the element.
| tree | The tree. |
| node | Pointer to the node embedded into the element to insert. |
| data | Pointer to the element to insert. |
| TOMMY_API void * tommy_tree_insert_unique | ( | tommy_tree * | tree, |
| tommy_tree_node * | node, | ||
| void * | data | ||
| ) |
Inserts an element only if no equal element is already contained.
If found, the first equal element in tree order is returned and the candidate node is left unchanged. Otherwise the candidate is inserted and data is returned.
| tree | The tree. |
| node | The candidate node. It must not belong to any container. |
| data | Pointer to the element to insert. |
| TOMMY_API void tommy_tree_to_list | ( | tommy_tree * | tree, |
| tommy_list * | list | ||
| ) |
Transfers all elements from the tree to the tail of a list in tree order.
Existing list elements remain before the transferred elements. The tree is left empty and initialized with its original comparison function. The list must be initialized and must not share nodes with the tree. Elements are not freed, and the node data and index fields are left unchanged. The index field no longer represents a valid tree parent after the transfer.
| tree | The tree to drain. |
| list | The destination list. |
| TOMMY_API void * tommy_tree_remove_existing | ( | tommy_tree * | tree, |
| tommy_tree_node * | node | ||
| ) |
Removes an element from the tree.
You must already have the address of the node to remove.
| tree | The tree. |
| node | The node to remove. |
| tommy_tree_node * tommy_tree_parent | ( | tommy_tree_node * | node | ) |
Gets the parent of the specified node.
| node | Node contained in the tree. |
| tommy_tree_node * tommy_tree_next | ( | tommy_tree_node * | node | ) |
Gets the node following the specified one in tree order.
See tommy_tree_iterator_validity for iterator validity across insertions and removals.
| node | Node contained in the tree. |
| tommy_tree_node * tommy_tree_prev | ( | tommy_tree_node * | node | ) |
Gets the node preceding the specified one in tree order.
See tommy_tree_iterator_validity for iterator validity across insertions and removals.
| node | Node contained in the tree. |
| tommy_tree_node * tommy_tree_head | ( | tommy_tree * | tree | ) |
Gets the head (smallest) node in the tree.
| tree | The tree. |
| tommy_tree_node * tommy_tree_tail | ( | tommy_tree * | tree | ) |
Gets the tail (greatest) node in the tree.
| tree | The tree. |
| void * tommy_tree_remove_head | ( | tommy_tree * | tree | ) |
Removes and returns the head (smallest) element.
If the tree is empty, 0 is returned.
| tree | The tree. |
| void * tommy_tree_remove_tail | ( | tommy_tree * | tree | ) |
Removes and returns the tail (greatest) element.
If the tree is empty, 0 is returned.
| tree | The tree. |
| tommy_tree_node * tommy_tree_find_compare | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp, | ||
| const void * | cmp_arg | ||
| ) |
Finds the first equal node in the tree with a specific comparison function.
Like tommy_tree_find() but you can specify a different comparison function. Note that this function must define a suborder of the original one. The first equal node in tree order is returned.
The cmp_arg argument will be the first argument of the comparison function, and it can be of a different type than the elements in the tree.
| tree | The tree. |
| cmp | Comparison function called with cmp_arg and the element in the tree. |
| cmp_arg | Search key, which may have a different type from tree elements. |
| tommy_tree_node * tommy_tree_find | ( | tommy_tree * | tree, |
| const void * | data | ||
| ) |
Finds the first equal node in the tree.
If the element is not found, 0 is returned.
| tree | The tree. |
| data | Element used for comparison. |
| void * tommy_tree_search_compare | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp, | ||
| const void * | cmp_arg | ||
| ) |
Searches an element in the tree with a specific comparison function.
Like tommy_tree_search() but you can specify a different comparison function. Note that this function must define a suborder of the original one. The first equal element in tree order is returned.
The cmp_arg argument will be the first argument of the comparison function, and it can be of a different type than the elements in the tree.
| tree | The tree. |
| cmp | Comparison function called with cmp_arg and the element in the tree. |
| cmp_arg | Search key, which may have a different type from tree elements. |
| void * tommy_tree_search | ( | tommy_tree * | tree, |
| const void * | data | ||
| ) |
Searches an element in the tree.
If the element is not found, 0 is returned.
| tree | The tree. |
| data | Element used for comparison. |
| tommy_tree_node * tommy_tree_find_greater_equal_compare | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp, | ||
| const void * | cmp_arg | ||
| ) |
Finds a node in the tree with key greater or equal than the specified one with a specific comparison function.
Like tommy_tree_find_greater_equal() but you can specify a different comparison function. Note that this function must define a suborder of the original one. The first qualifying node in tree order is returned.
The cmp_arg argument will be the first argument of the comparison function, and it can be of a different type than the elements in the tree.
| tree | The tree. |
| cmp | Comparison function called with cmp_arg and the element in the tree. |
| cmp_arg | Search key, which may have a different type from tree elements. |
| tommy_tree_node * tommy_tree_find_greater_equal | ( | tommy_tree * | tree, |
| const void * | data | ||
| ) |
Finds a node in the tree with key greater or equal than the specified one.
If no such element exists, 0 is returned.
| tree | The tree. |
| data | Element used for comparison. |
| void * tommy_tree_search_greater_equal_compare | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp, | ||
| const void * | cmp_arg | ||
| ) |
Searches an element in the tree with key greater or equal than the specified one with a specific comparison function.
Like tommy_tree_search_greater_equal() but you can specify a different comparison function. Note that this function must define a suborder of the original one. The first qualifying element in tree order is returned.
The cmp_arg argument will be the first argument of the comparison function, and it can be of a different type than the elements in the tree.
| tree | The tree. |
| cmp | Comparison function called with cmp_arg and the element in the tree. |
| cmp_arg | Search key, which may have a different type from tree elements. |
| void * tommy_tree_search_greater_equal | ( | tommy_tree * | tree, |
| const void * | data | ||
| ) |
Searches an element in the tree with key greater or equal than the specified one.
If no such element exists, 0 is returned.
| tree | The tree. |
| data | Element used for comparison. |
| tommy_tree_node * tommy_tree_find_greater_compare | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp, | ||
| const void * | cmp_arg | ||
| ) |
Finds the first node in tree order with key strictly greater than the specified one using a specific comparison function.
The function must define a suborder of the tree comparison function. Equivalent elements are excluded from the result.
| tree | The tree. |
| cmp | Comparison function called with cmp_arg and the element in the tree. |
| cmp_arg | Search key, which may have a different type from tree elements. |
| tommy_tree_node * tommy_tree_find_greater | ( | tommy_tree * | tree, |
| const void * | data | ||
| ) |
Finds the first node in tree order with key strictly greater than the specified one.
If no such element exists, 0 is returned.
| tree | The tree. |
| data | Element used for comparison. |
| void * tommy_tree_search_greater_compare | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp, | ||
| const void * | cmp_arg | ||
| ) |
Searches the first element in tree order with key strictly greater than the specified one using a specific comparison function.
The function must define a suborder of the tree comparison function. Equivalent elements are excluded from the result.
| tree | The tree. |
| cmp | Comparison function called with cmp_arg and the element in the tree. |
| cmp_arg | Search key, which may have a different type from tree elements. |
| void * tommy_tree_search_greater | ( | tommy_tree * | tree, |
| const void * | data | ||
| ) |
Searches the first element in tree order with key strictly greater than the specified one.
If no such element exists, 0 is returned.
| tree | The tree. |
| data | Element used for comparison. |
| tommy_tree_node * tommy_tree_find_less_equal_compare | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp, | ||
| const void * | cmp_arg | ||
| ) |
Finds a node in the tree with key less or equal than the specified one with a specific comparison function.
Like tommy_tree_find_less_equal() but you can specify a different comparison function. Note that this function must define a suborder of the original one. The last qualifying node in tree order is returned.
The cmp_arg argument will be the first argument of the comparison function, and it can be of a different type than the elements in the tree.
| tree | The tree. |
| cmp | Comparison function called with cmp_arg and the element in the tree. |
| cmp_arg | Search key, which may have a different type from tree elements. |
| tommy_tree_node * tommy_tree_find_less_equal | ( | tommy_tree * | tree, |
| const void * | data | ||
| ) |
Finds a node in the tree with key less or equal than the specified one.
If no such element exists, 0 is returned.
| tree | The tree. |
| data | Element used for comparison. |
| void * tommy_tree_search_less_equal_compare | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp, | ||
| const void * | cmp_arg | ||
| ) |
Searches an element in the tree with key less or equal than the specified one with a specific comparison function.
Like tommy_tree_search_less_equal() but you can specify a different comparison function. Note that this function must define a suborder of the original one. The last qualifying element in tree order is returned.
The cmp_arg argument will be the first argument of the comparison function, and it can be of a different type than the elements in the tree.
| tree | The tree. |
| cmp | Comparison function called with cmp_arg and the element in the tree. |
| cmp_arg | Search key, which may have a different type from tree elements. |
| void * tommy_tree_search_less_equal | ( | tommy_tree * | tree, |
| const void * | data | ||
| ) |
Searches an element in the tree with key less or equal than the specified one.
If no such element exists, 0 is returned.
| tree | The tree. |
| data | Element used for comparison. |
| tommy_tree_node * tommy_tree_find_less_compare | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp, | ||
| const void * | cmp_arg | ||
| ) |
Finds the last node in tree order with key strictly less than the specified one using a specific comparison function.
The function must define a suborder of the tree comparison function. Equivalent elements are excluded from the result.
| tree | The tree. |
| cmp | Comparison function called with cmp_arg and the element in the tree. |
| cmp_arg | Search key, which may have a different type from tree elements. |
| tommy_tree_node * tommy_tree_find_less | ( | tommy_tree * | tree, |
| const void * | data | ||
| ) |
Finds the last node in tree order with key strictly less than the specified one.
If no such element exists, 0 is returned.
| tree | The tree. |
| data | Element used for comparison. |
| void * tommy_tree_search_less_compare | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp, | ||
| const void * | cmp_arg | ||
| ) |
Searches the last element in tree order with key strictly less than the specified one using a specific comparison function.
The function must define a suborder of the tree comparison function. Equivalent elements are excluded from the result.
| tree | The tree. |
| cmp | Comparison function called with cmp_arg and the element in the tree. |
| cmp_arg | Search key, which may have a different type from tree elements. |
| void * tommy_tree_search_less | ( | tommy_tree * | tree, |
| const void * | data | ||
| ) |
Searches the last element in tree order with key strictly less than the specified one.
If no such element exists, 0 is returned.
| tree | The tree. |
| data | Element used for comparison. |
| void * tommy_tree_remove_compare | ( | tommy_tree * | tree, |
| tommy_compare_func * | cmp, | ||
| const void * | cmp_arg | ||
| ) |
Searches and removes an element from the tree with a specific comparison function.
The comparison function must define a suborder of the original one. The cmp_arg argument is passed as the first argument of the comparison function and may have a different type than the elements in the tree.
| tree | The tree. |
| cmp | Comparison function called with cmp_arg and the element in the tree. |
| cmp_arg | Search key, which may have a different type from tree elements. |
| void * tommy_tree_remove | ( | tommy_tree * | tree, |
| const void * | data | ||
| ) |
Searches and removes an element from the tree.
If the element is not found, 0 is returned.
| tree | The tree. |
| data | Element used for comparison. |
| TOMMY_API void tommy_tree_foreach | ( | tommy_tree * | tree, |
| tommy_foreach_func * | func | ||
| ) |
Calls the specified function for each element in the tree.
The elements are processed in order.
You cannot add or remove elements from the inside of the callback, but can use it to deallocate them.
If the callback frees the elements, the tree retains dangling node pointers. Call tommy_tree_clear() or tommy_tree_init() before reusing it. The tree has no storage to release.
| tree | The tree. |
| func | Function to call with each element. |
| TOMMY_API void tommy_tree_foreach_arg | ( | tommy_tree * | tree, |
| tommy_foreach_arg_func * | func, | ||
| void * | arg | ||
| ) |
Calls the specified function with an argument for each element in the tree.
The iteration order and callback rules are the same as tommy_tree_foreach(). The callback may deallocate the current element. Adding or removing elements from inside the callback is not allowed.
| tree | The tree. |
| func | Function to call with each element. |
| arg | Argument to pass to the function. |
| tommy_bool_t tommy_tree_empty | ( | const tommy_tree * | tree | ) |
Checks whether the tree is empty.
| tree | The tree. |
| tommy_size_t tommy_tree_count | ( | const tommy_tree * | tree | ) |
Gets the number of elements.
| tree | The tree. |
| TOMMY_API tommy_size_t tommy_tree_memory_usage | ( | const tommy_tree * | tree | ) |
Gets the size of allocated memory.
It includes the size of the tommy_tree_node of the stored elements.
| tree | The tree. |