# 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 trees | 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() | 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

AVL tree.

### 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_cb | Value comparison callback.
gs_cb | Data 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

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

tree | AVL 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

tree | AVL 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

tree | AVL 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

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.

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

tree | AVL tree.
elem | Tree 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

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.

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

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.

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

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.

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

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.

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

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.

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

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.

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

dest | First AVL tree.
src | Second AVL tree.
cmp_opaque | Extra 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

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

value | The 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

elem | Tree 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

tree | AVL tree.
elem | Tree element.
cmp_opaque | Extra 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

tree | AVL tree.
elem | Tree 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

tree | AVL tree the element belongs to or NULL.
elem | Tree 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

tree | AVL tree the element belongs to or NULL.
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.

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

tree | AVL tree.
elem | Tree 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

tree | AVL tree.
elem | Tree element.

#### Returns

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

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