Thread-safe AVL trees.
Through this single API two flavours of trees are offered: normal trees and auto-allocating trees.
The most evident difference between them is that the latter’s elements will contain automatically allocated copies of the inserted values (the pointed data is copied) while the former’s elements will contain copies of the references to the given data (the pointer value is copied).
Other differences that the user of this API should be aware of are specified in the documention of functions.
AVL trees | Thread-safe AVL trees. |
Types | |
nacore_avl_tree | AVL tree. |
nacore_avl_tree_elem | AVL tree element. |
Functions | |
nacore_avl_tree_new() | Creates a new tree. |
nacore_avl_tree_free() | Destroies a tree and all its elements. |
nacore_avl_tree_get_n_elems() | Gets the number of elements in a tree. |
nacore_avl_tree_get_first() | Gets the leftmost (i.e., the first/smallest by value) element in a tree. |
nacore_avl_tree_get_last() | Gets the rightmost (i.e., the last/biggest by value) element in a tree. |
nacore_avl_tree_insert() | Inserts a new element into a tree. |
nacore_avl_tree_pop() | Removes an element from a tree and returns the value it contains. |
nacore_avl_tree_find() | Finds a matching element inside a tree by comparing values. |
nacore_avl_tree_find_first() | Finds the leftmost matching element inside a tree by comparing values. |
nacore_avl_tree_find_last() | Finds the rightmost matching element inside a tree by comparing values. |
nacore_avl_tree_find_prev() | Finds the next element on the left in a tree holding a value that compares identical to that of the given element. |
nacore_avl_tree_find_next() | Finds the next element on the right in a tree holding a value that compares identical to that of the given element. |
nacore_avl_tree_dup() | Duplicates a tree. |
nacore_avl_tree_merge() | Merges two trees by inserting the elements of one tree into the other. |
nacore_avl_tree_begin_op() | Starts a section of code in which the tree is guaranteed not to be modified by other threads. |
nacore_avl_tree_end_op() | Ends a section of code in which the tree is guaranteed not to be modified by other threads. |
nacore_avl_tree_dump() | Dumps the structure and content of a tree on stderr. |
nacore_avl_tree_elem_get_value() | Gets the value contained in a tree element. |
nacore_avl_tree_elem_set_value() | Sets the value contained in a tree element and rearranges the tree to keep the sorting if needed. |
nacore_avl_tree_elem_get_prev() | Gets the next element on the left with regard to the given element in a tree. |
nacore_avl_tree_elem_get_next() | Gets the next element on the right with regard to the given element in a tree. |
_NACORE_DEF nacore_avl_tree nacore_avl_tree_new( nacore_cmp_cb cmp_cb, nacore_get_size_cb gs_cb )
Creates a new tree.
Use NULL as gs_cb to create a normal tree, otherwise (auto-allocating tree) the gs_cb will be called to determine the quantity of memory to allocate and copy for each insertion and value modification.
cmp_cb | Value comparison callback. |
gs_cb | Data size callback or NULL. |
AVL tree or NULL if some error occurred, in which case errno is set to EAGAIN if the system lacked the necessary resources (other than memory), ENOMEM if there was not enough memory, EPERM if the caller does not have the priviledge to perform the operation or NACORE_EUNKNOWN if another kind of error happened.
_NACORE_DEF void nacore_avl_tree_free( nacore_avl_tree tree, nacore_op_cb free_cb, void * free_opaque )
Destroies a tree and all its elements.
If the tree is auto-allocating, value copies inside each element are destroied too.
In any case, before potentially being destroyed, each element is passed to the free_cb callback, if one is given, as well as the specified extra data.
Once this function is called, referring to tree or any element it contains will cause undefined behavior. If the tree is auto-allocating, the same is true for element values outside of the free_cb callback, if one is supplied.
tree | AVL tree. |
free_cb | Callback called for each tree element or NULL. |
free_opaque | Extra opaque data to be passed to free_cb or NULL. |
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_insert( nacore_avl_tree tree, void * cmp_opaque, void * gs_opaque, void * value )
Inserts a new element into a tree.
tree | AVL tree. |
cmp_opaque | Extra opaque data to be passed to the value comparison callback or NULL. |
gs_opaque | Extra opaque data to be passed to the data size callback or NULL. |
value | The value to be contained in the element. |
New tree element containing value or NULL if there was not enough memory.
_NACORE_DEF void * nacore_avl_tree_pop( nacore_avl_tree tree, nacore_avl_tree_elem elem )
Removes an element from a tree and returns the value it contains.
Once this function is called, referring to elem will cause undefined behavior.
tree | AVL tree. |
elem | Tree element to be removed. |
The value contained in the element being removed. If the tree is auto-allocating the caller is in charge of free()ing the value.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_find( nacore_avl_tree tree, void * cmp_opaque, nacore_filter_cb filter_cb, void * filter_opaque, void * value )
Finds a matching element inside a tree by comparing values.
In case there are multiple matches, the returned element can be any of the matching elements.
If filter_cb is not NULL, it will be called along with filter_opaque when a matching element is found; if it is to be filtered out (i.e., filter_cb returns 0) the search will continue, etc.
tree | AVL tree. |
cmp_opaque | Extra opaque data to be passed to the value comparison callback or NULL. |
filter_cb | Value filtering callback or NULL. |
filter_opaque | Extra opaque data to be passed to filter_cb or NULL. |
value | The value to look for. |
Tree element containing the desired value or NULL if no such element was found.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_find_first( nacore_avl_tree tree, void * cmp_opaque, nacore_filter_cb filter_cb, void * filter_opaque, void * value )
Finds the leftmost matching element inside a tree by comparing values.
If filter_cb is not NULL, it will be called along with filter_opaque when a matching element is found; if it is to be filtered out (i.e., filter_cb returns 0) the search will continue, etc.
tree | AVL tree. |
cmp_opaque | Extra opaque data to be passed to the value comparison callback or NULL. |
filter_cb | Value filtering callback or NULL. |
filter_opaque | Extra opaque data to be passed to filter_cb or NULL. |
value | The value to look for. |
Tree element containing the desired value or NULL if no such element was found.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_find_last( nacore_avl_tree tree, void * cmp_opaque, nacore_filter_cb filter_cb, void * filter_opaque, void * value )
Finds the rightmost matching element inside a tree by comparing values.
If filter_cb is not NULL, it will be called along with filter_opaque when a matching element is found; if it is to be filtered out (i.e., filter_cb returns 0) the search will continue, etc.
tree | AVL tree. |
cmp_opaque | Extra opaque data to be passed to the value comparison callback or NULL. |
filter_cb | Value filtering callback or NULL. |
filter_opaque | Extra opaque data to be passed to filter_cb or NULL. |
value | The value to look for. |
Tree element containing the desired value or NULL if no such element was found.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_find_prev( nacore_avl_tree tree, nacore_avl_tree_elem elem, void * cmp_opaque, nacore_filter_cb filter_cb, void * filter_opaque )
Finds the next element on the left in a tree holding a value that compares identical to that of the given element.
If filter_cb is not NULL, it will be called along with filter_opaque when a matching element is found; if it is to be filtered out (i.e., filter_cb returns 0) the search will continue, etc.
tree | AVL tree. |
elem | The element to the left of which the search happens. |
cmp_opaque | Extra opaque data to be passed to the value comparison callback or NULL. |
filter_cb | Value filtering callback or NULL. |
filter_opaque | Extra opaque data to be passed to filter_cb or NULL. |
Tree element containing the desired value or NULL if no such element was found.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_find_next( nacore_avl_tree tree, nacore_avl_tree_elem elem, void * cmp_opaque, nacore_filter_cb filter_cb, void * filter_opaque )
Finds the next element on the right in a tree holding a value that compares identical to that of the given element.
If filter_cb is not NULL, it will be called along with filter_opaque when a matching element is found; if it is to be filtered out (i.e., filter_cb returns 0) the search will continue, etc.
tree | AVL tree. |
elem | The element before which the search happens. |
cmp_opaque | Extra opaque data to be passed to the value comparison callback or NULL. |
filter_cb | Value filtering callback or NULL. |
filter_opaque | Extra opaque data to be passed to filter_cb or NULL. |
Tree element containing the desired value or NULL if no such element was found.
_NACORE_DEF nacore_avl_tree nacore_avl_tree_dup( nacore_avl_tree tree, void * cmp_opaque, nacore_get_size_cb gs_cb, void * gs_opaque, nacore_filter_cb filter_cb, void * filter_opaque, nacore_op_cb dup_cb, void * dup_opaque )
Duplicates a tree.
gs_cb is used as in nacore_avl_tree_new(), hence if it is not NULL the new tree will be auto-allocating.
If filter_cb is not NULL, it will be called along with filter_opaque for each element; if it is to be filtered out (i.e., filter_cb returns 0) the element will not be included in the resulting tree.
After the creation of each new element dup_cb is called, if such a callback is given, passing it the value (its copy if the new list is auto-allocating) and the specified extra data.
tree | AVL tree. |
cmp_opaque | Extra opaque data to be passed to the value comparison callback or NULL. |
gs_cb | Data size callback or NULL. |
gs_opaque | Extra opaque data to be passed to gs_cb or NULL. |
filter_cb | Value filtering callback or NULL. |
filter_opaque | Extra opaque data to be passed to filter_cb or NULL. |
dup_cb | Callback called for each new tree element or NULL. |
dup_opaque | Extra opaque data to be passed to dup_cb or NULL. |
AVL tree or NULL if some error occurred, in which case errno is set to EAGAIN if the system lacked the necessary resources (other than memory), ENOMEM if there was not enough memory, EPERM if the caller does not have the priviledge to perform the operation or NACORE_EUNKNOWN if another kind of error happened.
_NACORE_DEF nacore_avl_tree nacore_avl_tree_merge( nacore_avl_tree dest, nacore_avl_tree src, void * cmp_opaque )
Merges two trees by inserting the elements of one tree into the other.
The two trees must have been created with the same data size callback (or NULL in both cases) and same value comparison callback.
Once this function is called, referring to src or dest will cause undefined behavior.
dest | First AVL tree. |
src | Second AVL tree. |
cmp_opaque | Extra opaque data to be passed to the value comparison callback or NULL. |
The AVL tree containing elements from both trees.
_NACORE_DEF int nacore_avl_tree_begin_op( nacore_avl_tree tree )
Starts a section of code in which the tree is guaranteed not to be modified by other threads.
Each successful call has to be matched by a following call to nacore_avl_tree_end_op().
tree | AVL tree. |
0 on success or EDEADLK if the current thread is already in such a section.
_NACORE_DEF void nacore_avl_tree_dump( nacore_avl_tree tree, nacore_to_string_cb to_string_cb, void * to_string_opaque )
Dumps the structure and content of a tree on stderr.
Never rely on the exact output of this function, it is intended to be used solely for debugging purposes.
tree | AVL tree. |
to_string_cb | Callback returning a textual description of a value or NULL. |
to_string_opaque | Extra opaque data to be passed to to_string_cb or NULL. |
_NACORE_DEF int nacore_avl_tree_elem_set_value( nacore_avl_tree tree, nacore_avl_tree_elem elem, nacore_op_cb free_cb, void * free_opaque, void * cmp_opaque, void * gs_opaque, void * value )
Sets the value contained in a tree element and rearranges the tree to keep the sorting if needed.
If the tree is auto-allocating, first the old value is free()d, then a copy of the new value is put into the element.
In any case, before potentially being destroyed, the element value is passed to the free_cb callback, if one is given, as well as the specified extra data.
tree | AVL tree the element belongs to. |
elem | Tree element. |
free_cb | Callback called to destroy element value or NULL. |
free_opaque | Extra opaque data to be passed to free_cb or NULL. |
cmp_opaque | Extra opaque data to be passed to the value comparison callback or NULL. |
gs_opaque | Extra opaque data to be passed to the data size callback or NULL. |
value | The value. |
0 on success or ENOMEM if there was not enough memory (auto-allocating trees only).
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_elem_get_prev( nacore_avl_tree tree, nacore_avl_tree_elem elem )
Gets the next element on the left with regard to the given element in a tree.
tree | AVL tree. |
elem | Tree element. |
Next element on the left w.r.t. the given element or NULL if there is none.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_elem_get_next( nacore_avl_tree tree, nacore_avl_tree_elem elem )
Gets the next element on the right with regard to the given element in a tree.
tree | AVL tree. |
elem | Tree element. |
Next element on the right w.r.t. the given element or NULL if there is none.
AVL tree.
typedef struct _nacore_avl_tree * nacore_avl_tree
AVL tree element.
typedef struct _nacore_avl_tree_elem * nacore_avl_tree_elem
Creates a new tree.
_NACORE_DEF nacore_avl_tree nacore_avl_tree_new( nacore_cmp_cb cmp_cb, nacore_get_size_cb gs_cb )
Destroies a tree and all its elements.
_NACORE_DEF void nacore_avl_tree_free( nacore_avl_tree tree, nacore_op_cb free_cb, void * free_opaque )
Gets the number of elements in a tree.
_NACORE_DEF size_t nacore_avl_tree_get_n_elems( nacore_avl_tree tree )
Gets the leftmost (i.e., the first/smallest by value) element in a tree.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_get_first( nacore_avl_tree tree )
Gets the rightmost (i.e., the last/biggest by value) element in a tree.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_get_last( nacore_avl_tree tree )
Inserts a new element into a tree.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_insert( nacore_avl_tree tree, void * cmp_opaque, void * gs_opaque, void * value )
Removes an element from a tree and returns the value it contains.
_NACORE_DEF void * nacore_avl_tree_pop( nacore_avl_tree tree, nacore_avl_tree_elem elem )
Finds a matching element inside a tree by comparing values.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_find( nacore_avl_tree tree, void * cmp_opaque, nacore_filter_cb filter_cb, void * filter_opaque, void * value )
Finds the leftmost matching element inside a tree by comparing values.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_find_first( nacore_avl_tree tree, void * cmp_opaque, nacore_filter_cb filter_cb, void * filter_opaque, void * value )
Finds the rightmost matching element inside a tree by comparing values.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_find_last( nacore_avl_tree tree, void * cmp_opaque, nacore_filter_cb filter_cb, void * filter_opaque, void * value )
Finds the next element on the left in a tree holding a value that compares identical to that of the given element.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_find_prev( nacore_avl_tree tree, nacore_avl_tree_elem elem, void * cmp_opaque, nacore_filter_cb filter_cb, void * filter_opaque )
Finds the next element on the right in a tree holding a value that compares identical to that of the given element.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_find_next( nacore_avl_tree tree, nacore_avl_tree_elem elem, void * cmp_opaque, nacore_filter_cb filter_cb, void * filter_opaque )
Duplicates a tree.
_NACORE_DEF nacore_avl_tree nacore_avl_tree_dup( nacore_avl_tree tree, void * cmp_opaque, nacore_get_size_cb gs_cb, void * gs_opaque, nacore_filter_cb filter_cb, void * filter_opaque, nacore_op_cb dup_cb, void * dup_opaque )
Merges two trees by inserting the elements of one tree into the other.
_NACORE_DEF nacore_avl_tree nacore_avl_tree_merge( nacore_avl_tree dest, nacore_avl_tree src, void * cmp_opaque )
Starts a section of code in which the tree is guaranteed not to be modified by other threads.
_NACORE_DEF int nacore_avl_tree_begin_op( nacore_avl_tree tree )
Ends a section of code in which the tree is guaranteed not to be modified by other threads.
_NACORE_DEF void nacore_avl_tree_end_op( nacore_avl_tree tree )
Dumps the structure and content of a tree on stderr.
_NACORE_DEF void nacore_avl_tree_dump( nacore_avl_tree tree, nacore_to_string_cb to_string_cb, void * to_string_opaque )
Gets the value contained in a tree element.
_NACORE_DEF void * nacore_avl_tree_elem_get_value( nacore_avl_tree tree, nacore_avl_tree_elem elem )
Sets the value contained in a tree element and rearranges the tree to keep the sorting if needed.
_NACORE_DEF int nacore_avl_tree_elem_set_value( nacore_avl_tree tree, nacore_avl_tree_elem elem, nacore_op_cb free_cb, void * free_opaque, void * cmp_opaque, void * gs_opaque, void * value )
Gets the next element on the left with regard to the given element in a tree.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_elem_get_prev( nacore_avl_tree tree, nacore_avl_tree_elem elem )
Gets the next element on the right with regard to the given element in a tree.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_elem_get_next( nacore_avl_tree tree, nacore_avl_tree_elem elem )