AVL trees

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.

No thread synchronization is performed by this API, i.e., it is not thread-safe to concurrently operate on a tree unless you implement some external synchronization mechanism.

Summary
AVL treesAVL trees.
Types
nacore_avl_treeAVL tree.
nacore_avl_tree_elemAVL tree element.
Functions
nacore_avl_tree_new()Creates a new tree.
nacore_avl_tree_free()Destroys 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()Creates a new tree element and inserts it into a tree.
nacore_avl_tree_pop()Removes an element from a tree, destroys it 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_dump()Dumps the structure and content of a tree on stderr.
nacore_avl_tree_elem_new()Creates a new tree element without adding it to a tree.
nacore_avl_tree_elem_free()Destroys a tree element.
nacore_avl_tree_elem_insert()Inserts a tree element into a tree.
nacore_avl_tree_elem_pop()Removes an element from a tree without destroying it.
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.

Types

nacore_avl_tree

typedef struct _nacore_avl_tree * nacore_avl_tree

AVL tree.

nacore_avl_tree_elem

typedef struct _nacore_avl_tree_elem * nacore_avl_tree_elem

AVL tree element.

Functions

nacore_avl_tree_new()

_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.

Parameters

cmp_cbValue comparison callback.
gs_cbData size callback or NULL.

Returns

AVL tree or NULL if there was not enough memory.

nacore_avl_tree_free()

_NACORE_DEF void nacore_avl_tree_free(nacore_avl_tree tree,
nacore_op_cb free_cb,
void *free_opaque)

Destroys 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.

Parameters

treeAVL tree.
free_cbCallback called for each tree element or NULL.
free_opaqueExtra opaque data to be passed to free_cb or NULL.

nacore_avl_tree_get_n_elems()

_NACORE_DEF size_t nacore_avl_tree_get_n_elems(nacore_avl_tree tree)

Gets the number of elements in a tree.

Parameters

treeAVL tree.

Returns

Number of elements in the tree or 0 if the tree is empty.

nacore_avl_tree_get_first()

_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_get_first(nacore_avl_tree tree)

Gets the leftmost (i.e., the first/smallest by value) element in a tree.

Parameters

treeAVL tree.

Returns

Leftmost tree element in the tree or NULL if the tree is empty.

nacore_avl_tree_get_last()

_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_get_last(nacore_avl_tree tree)

Gets the rightmost (i.e., the last/biggest by value) element in a tree.

Parameters

treeAVL tree.

Returns

Rightmost tree element in the tree or NULL if the tree is empty.

nacore_avl_tree_insert()

_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_insert(nacore_avl_tree tree,
void *cmp_opaque,
void *gs_opaque,
void *value)

Creates a new tree element and inserts it into a tree.

Parameters

treeAVL tree.
cmp_opaqueExtra opaque data to be passed to the value comparison callback or NULL.
gs_opaqueExtra opaque data to be passed to the data size callback or NULL.
valueThe value to be contained in the element.

Returns

New tree element containing value or NULL if there was not enough memory.

See also

nacore_avl_tree_elem_insert().

nacore_avl_tree_pop()

_NACORE_DEF void * nacore_avl_tree_pop(nacore_avl_tree tree,
nacore_avl_tree_elem elem)

Removes an element from a tree, destroys it and returns the value it contains.

Once this function is called, referring to elem will cause undefined behavior.

Parameters

treeAVL tree.
elemTree element to be removed.

Returns

The value contained in the element being removed.  If the tree is auto-allocating the caller is in charge of free()ing the value.

See also

nacore_avl_tree_elem_pop().

nacore_avl_tree_find()

_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.

Parameters

treeAVL tree.
cmp_opaqueExtra opaque data to be passed to the value comparison callback or NULL.
filter_cbValue filtering callback or NULL.
filter_opaqueExtra opaque data to be passed to filter_cb or NULL.
valueThe value to look for.

Returns

Tree element containing the desired value or NULL if no such element was found.

nacore_avl_tree_find_first()

_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.

Parameters

treeAVL tree.
cmp_opaqueExtra opaque data to be passed to the value comparison callback or NULL.
filter_cbValue filtering callback or NULL.
filter_opaqueExtra opaque data to be passed to filter_cb or NULL.
valueThe value to look for.

Returns

Tree element containing the desired value or NULL if no such element was found.

nacore_avl_tree_find_last()

_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.

Parameters

treeAVL tree.
cmp_opaqueExtra opaque data to be passed to the value comparison callback or NULL.
filter_cbValue filtering callback or NULL.
filter_opaqueExtra opaque data to be passed to filter_cb or NULL.
valueThe value to look for.

Returns

Tree element containing the desired value or NULL if no such element was found.

nacore_avl_tree_find_prev()

_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.

Parameters

treeAVL tree.
elemThe element to the left of which the search happens.
cmp_opaqueExtra opaque data to be passed to the value comparison callback or NULL.
filter_cbValue filtering callback or NULL.
filter_opaqueExtra opaque data to be passed to filter_cb or NULL.

Returns

Tree element containing the desired value or NULL if no such element was found.

nacore_avl_tree_find_next()

_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.

Parameters

treeAVL tree.
elemThe element before which the search happens.
cmp_opaqueExtra opaque data to be passed to the value comparison callback or NULL.
filter_cbValue filtering callback or NULL.
filter_opaqueExtra opaque data to be passed to filter_cb or NULL.

Returns

Tree element containing the desired value or NULL if no such element was found.

nacore_avl_tree_dup()

_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.

Parameters

treeAVL tree.
cmp_opaqueExtra opaque data to be passed to the value comparison callback or NULL.
gs_cbData size callback or NULL.
gs_opaqueExtra opaque data to be passed to gs_cb or NULL.
filter_cbValue filtering callback or NULL.
filter_opaqueExtra opaque data to be passed to filter_cb or NULL.
dup_cbCallback called for each new tree element or NULL.
dup_opaqueExtra opaque data to be passed to dup_cb or NULL.

Returns

AVL tree or NULL if there was not enough memory.

nacore_avl_tree_merge()

_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.

Parameters

destFirst AVL tree.
srcSecond AVL tree.
cmp_opaqueExtra opaque data to be passed to the value comparison callback or NULL.

Returns

The AVL tree containing elements from both trees.

nacore_avl_tree_dump()

_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.

Parameters

treeAVL tree.
to_string_cbCallback returning a textual description of a value or NULL.
to_string_opaqueExtra opaque data to be passed to to_string_cb or NULL.

nacore_avl_tree_elem_new()

_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_elem_new(void *value)

Creates a new tree element without adding it to a tree.

Parameters

valueThe value to be contained in the element.

Returns

New tree element containing value or NULL if there was not enough memory.

nacore_avl_tree_elem_free()

_NACORE_DEF void nacore_avl_tree_elem_free(nacore_avl_tree_elem elem)

Destroys a tree element.

Once this function is called, referring to elem will cause undefined behavior.

Only to be used when the element is not part of a tree.

Parameters

elemTree element.

nacore_avl_tree_elem_insert()

_NACORE_DEF void nacore_avl_tree_elem_insert(nacore_avl_tree tree,
nacore_avl_tree_elem elem,
void *cmp_opaque)

Inserts a tree element into a tree.

Only to be used when the element to be insterted is not part of a tree.

Beware of auto-allocating trees...

Parameters

treeAVL tree.
elemTree element.
cmp_opaqueExtra opaque data to be passed to the value comparison callback or NULL.

See also

nacore_avl_tree_insert().

nacore_avl_tree_elem_pop()

_NACORE_DEF void nacore_avl_tree_elem_pop(nacore_avl_tree tree,
nacore_avl_tree_elem elem)

Removes an element from a tree without destroying it.

Parameters

treeAVL tree.
elemTree element.

See also

nacore_avl_tree_pop().

nacore_avl_tree_elem_get_value()

_NACORE_DEF void * nacore_avl_tree_elem_get_value(nacore_avl_tree tree,
nacore_avl_tree_elem elem)

Gets the value contained in a tree element.

The tree parameter is currently unused.  It is however good if you set it to NULL only when elem is not part of a tree.

Parameters

treeAVL tree the element belongs to or NULL.
elemTree element.

Returns

The value contained in elem.

nacore_avl_tree_elem_set_value()

_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 element is not part of a tree set tree as NULL, in which case the function shall behave as if the element is part of a normal tree.

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.  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.

Parameters

treeAVL tree the element belongs to or NULL.
elemTree element.
free_cbCallback called to destroy element value or NULL.
free_opaqueExtra opaque data to be passed to free_cb or NULL.
cmp_opaqueExtra opaque data to be passed to the value comparison callback or NULL.
gs_opaqueExtra opaque data to be passed to the data size callback or NULL.
valueThe value.

Returns

0 on success or ENOMEM if there was not enough memory (auto-allocating trees only).

nacore_avl_tree_elem_get_prev()

_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.

Parameters

treeAVL tree.
elemTree element.

Returns

Next element on the left w.r.t. the given element or NULL if there is none.

nacore_avl_tree_elem_get_next()

_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.

Parameters

treeAVL tree.
elemTree element.

Returns

Next element on the right w.r.t. the given element or NULL if there is none.

typedef struct _nacore_avl_tree * nacore_avl_tree
AVL tree.
typedef struct _nacore_avl_tree_elem * nacore_avl_tree_elem
AVL tree element.
_NACORE_DEF nacore_avl_tree nacore_avl_tree_new(nacore_cmp_cb cmp_cb,
nacore_get_size_cb gs_cb)
Creates a new tree.
_NACORE_DEF void nacore_avl_tree_free(nacore_avl_tree tree,
nacore_op_cb free_cb,
void *free_opaque)
Destroys a tree and all its elements.
_NACORE_DEF size_t nacore_avl_tree_get_n_elems(nacore_avl_tree tree)
Gets the number of elements in a tree.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_get_first(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_last(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_insert(nacore_avl_tree tree,
void *cmp_opaque,
void *gs_opaque,
void *value)
Creates a new tree element and inserts it into a tree.
_NACORE_DEF void * nacore_avl_tree_pop(nacore_avl_tree tree,
nacore_avl_tree_elem elem)
Removes an element from a tree, destroys it and returns the value it contains.
_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.
_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.
_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.
_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.
_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.
_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.
_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.
_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.
_NACORE_DEF nacore_avl_tree_elem nacore_avl_tree_elem_new(void *value)
Creates a new tree element without adding it to a tree.
_NACORE_DEF void nacore_avl_tree_elem_free(nacore_avl_tree_elem elem)
Destroys a tree element.
_NACORE_DEF void nacore_avl_tree_elem_insert(nacore_avl_tree tree,
nacore_avl_tree_elem elem,
void *cmp_opaque)
Inserts a tree element into a tree.
_NACORE_DEF void nacore_avl_tree_elem_pop(nacore_avl_tree tree,
nacore_avl_tree_elem elem)
Removes an element from a tree without destroying it.
_NACORE_DEF void * nacore_avl_tree_elem_get_value(nacore_avl_tree tree,
nacore_avl_tree_elem elem)
Gets the value contained in a tree element.
_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.
_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.
_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.
Close