Data Structures | Typedefs | Functions
tommytree.h File Reference

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

Detailed Description

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.

tommy_tree_init(&tree, cmp);
Tree container type.
Definition: tommytree.h:146
void tommy_tree_init(tommy_tree *tree, tommy_compare_func *cmp)
Initializes the tree.
Definition: tommytree.h:157

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.

struct element {
int value;
// other fields
};
struct element* elem = malloc(sizeof(struct element)); // creates the element
elem->value = ...; // initializes the element
tommy_tree_insert(&tree, &elem->node, elem); // inserts the element
Data structure node.
Definition: tommytypes.h:242
TOMMY_API void tommy_tree_insert(tommy_tree *tree, tommy_tree_node *node, void *data)
Inserts an element in the tree, allowing duplicate keys.

To find the first element with a given key in tree order, call tommy_tree_search() providing the key to search.

struct element value_to_find = { 1 };
struct element* elem = tommy_tree_search(&tree, &value_to_find);
if (!elem) {
// not found
} else {
// found
}
void * tommy_tree_search(tommy_tree *tree, const void *data)
Searches an element in the tree.
Definition: tommytree.h:447

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

while (i) {
struct element* elem = i->data; // gets the element pointer
printf("%d\n", elem->value); // process the element
i = tommy_tree_next(i); // go to the next element
}
void * data
Pointer to the element containing the node.
Definition: tommytypes.h:260
tommy_tree_node * tommy_tree_head(tommy_tree *tree)
Gets the head (smallest) node in the tree.
Definition: tommytree.h:306
tommy_tree_node * tommy_tree_next(tommy_tree_node *node)
Gets the node following the specified one in tree order.
Definition: tommytree.h:257

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.

struct element value_to_remove = { 1 };
struct element* elem = tommy_tree_remove(&tree, &value_to_remove);
if (elem) {
free(elem); // frees the element allocated memory
}
void * tommy_tree_remove(tommy_tree *tree, const void *data)
Searches and removes an element from the tree.
Definition: tommytree.h:789

You can also remove an element from the tree if you already have the node address using tommy_tree_remove_existing().

struct element* elem = ...;
tommy_tree_remove_existing(&tree, &elem->node);
free(elem);
TOMMY_API void * tommy_tree_remove_existing(tommy_tree *tree, tommy_tree_node *node)
Removes an element from the tree.

To remove the smallest or greatest element you can use tommy_tree_remove_head() or tommy_tree_remove_tail().

struct element* elem = tommy_tree_remove_head(&tree);
if (elem) {
free(elem);
}
void * tommy_tree_remove_head(tommy_tree *tree)
Removes and returns the head (smallest) element.
Definition: tommytree.h:344

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.

// deallocates all the elements iterating the tree
tommy_tree_foreach(&tree, free);
TOMMY_API void tommy_tree_foreach(tommy_tree *tree, tommy_foreach_func *func)
Calls the specified function for each element in the tree.

Typedef Documentation

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

◆ tommy_tree

typedef struct tommy_tree_struct tommy_tree

Tree container type.

Note
Don't use internal fields directly, but access the container only using functions.

Function Documentation

◆ tommy_tree_init()

void tommy_tree_init ( tommy_tree *  tree,
tommy_compare_func *  cmp 
)

Initializes the tree.

Parameters
treeThe tree.
cmpThe comparison function that defines the order in the tree.

◆ tommy_tree_swap()

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.

Parameters
firstThe first tree.
secondThe second tree.
Note
This operation is O(1).

◆ tommy_tree_clear()

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.

Parameters
treeThe tree.
Note
This operation is O(1).

◆ tommy_tree_insert()

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.

Parameters
treeThe tree.
nodePointer to the node embedded into the element to insert.
dataPointer to the element to insert.

◆ tommy_tree_insert_unique()

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.

Parameters
treeThe tree.
nodeThe candidate node. It must not belong to any container.
dataPointer to the element to insert.
Returns
The first equal element, or data if the candidate was inserted.

◆ tommy_tree_to_list()

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.

Parameters
treeThe tree to drain.
listThe destination list.
Note
This operation is O(n), using O(log n) stack space.

◆ tommy_tree_remove_existing()

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.

Parameters
treeThe tree.
nodeThe node to remove.
Returns
The removed element.

◆ tommy_tree_parent()

tommy_tree_node * tommy_tree_parent ( tommy_tree_node *  node)

Gets the parent of the specified node.

Parameters
nodeNode contained in the tree.
Returns
The parent node. For the root node 0 is returned.

◆ tommy_tree_next()

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.

Parameters
nodeNode contained in the tree.
Returns
The following node, or 0 for the tail node.
Note
This operation is O(log n), and amortized O(1) during full traversal.

◆ tommy_tree_prev()

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.

Parameters
nodeNode contained in the tree.
Returns
The preceding node, or 0 for the head node.
Note
This operation is O(log n), and amortized O(1) during full traversal.

◆ tommy_tree_head()

tommy_tree_node * tommy_tree_head ( tommy_tree *  tree)

Gets the head (smallest) node in the tree.

Parameters
treeThe tree.
Returns
The head node, or 0 if the tree is empty.
Note
This operation is O(log n).

◆ tommy_tree_tail()

tommy_tree_node * tommy_tree_tail ( tommy_tree *  tree)

Gets the tail (greatest) node in the tree.

Parameters
treeThe tree.
Returns
The tail node, or 0 if the tree is empty.
Note
This operation is O(log n).

◆ tommy_tree_remove_head()

void * tommy_tree_remove_head ( tommy_tree *  tree)

Removes and returns the head (smallest) element.

If the tree is empty, 0 is returned.

Parameters
treeThe tree.
Returns
The removed element, or 0 if the tree is empty.

◆ tommy_tree_remove_tail()

void * tommy_tree_remove_tail ( tommy_tree *  tree)

Removes and returns the tail (greatest) element.

If the tree is empty, 0 is returned.

Parameters
treeThe tree.
Returns
The removed element, or 0 if the tree is empty.

◆ tommy_tree_find_compare()

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.

Parameters
treeThe tree.
cmpComparison function called with cmp_arg and the element in the tree.
cmp_argSearch key, which may have a different type from tree elements.
Returns
The first equal node in tree order, or 0 if none.

◆ tommy_tree_find()

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.

Parameters
treeThe tree.
dataElement used for comparison.
Returns
The first equal node in tree order, or 0 if none.

◆ tommy_tree_search_compare()

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.

Parameters
treeThe tree.
cmpComparison function called with cmp_arg and the element in the tree.
cmp_argSearch key, which may have a different type from tree elements.
Returns
The first equal element in tree order, or 0 if none.

◆ tommy_tree_search()

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.

Parameters
treeThe tree.
dataElement used for comparison.
Returns
The first equal element in tree order, or 0 if none.

◆ tommy_tree_find_greater_equal_compare()

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.

Parameters
treeThe tree.
cmpComparison function called with cmp_arg and the element in the tree.
cmp_argSearch key, which may have a different type from tree elements.
Returns
The first node in tree order with key greater or equal, or 0 if none.

◆ tommy_tree_find_greater_equal()

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.

Parameters
treeThe tree.
dataElement used for comparison.
Returns
The first node in tree order with key greater or equal, or 0 if none.

◆ tommy_tree_search_greater_equal_compare()

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.

Parameters
treeThe tree.
cmpComparison function called with cmp_arg and the element in the tree.
cmp_argSearch key, which may have a different type from tree elements.
Returns
The first element in tree order with key greater or equal, or 0 if none.

◆ tommy_tree_search_greater_equal()

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.

Parameters
treeThe tree.
dataElement used for comparison.
Returns
The first element in tree order with key greater or equal, or 0 if none.

◆ tommy_tree_find_greater_compare()

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.

Parameters
treeThe tree.
cmpComparison function called with cmp_arg and the element in the tree.
cmp_argSearch key, which may have a different type from tree elements.
Returns
The first strictly greater node, or 0 if none.

◆ tommy_tree_find_greater()

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.

Parameters
treeThe tree.
dataElement used for comparison.
Returns
The first strictly greater node, or 0 if none.

◆ tommy_tree_search_greater_compare()

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.

Parameters
treeThe tree.
cmpComparison function called with cmp_arg and the element in the tree.
cmp_argSearch key, which may have a different type from tree elements.
Returns
The first strictly greater element, or 0 if none.

◆ tommy_tree_search_greater()

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.

Parameters
treeThe tree.
dataElement used for comparison.
Returns
The first strictly greater element, or 0 if none.

◆ tommy_tree_find_less_equal_compare()

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.

Parameters
treeThe tree.
cmpComparison function called with cmp_arg and the element in the tree.
cmp_argSearch key, which may have a different type from tree elements.
Returns
The last node in tree order with key less or equal, or 0 if none.

◆ tommy_tree_find_less_equal()

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.

Parameters
treeThe tree.
dataElement used for comparison.
Returns
The last node in tree order with key less or equal, or 0 if none.

◆ tommy_tree_search_less_equal_compare()

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.

Parameters
treeThe tree.
cmpComparison function called with cmp_arg and the element in the tree.
cmp_argSearch key, which may have a different type from tree elements.
Returns
The last element in tree order with key less or equal, or 0 if none.

◆ tommy_tree_search_less_equal()

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.

Parameters
treeThe tree.
dataElement used for comparison.
Returns
The last element in tree order with key less or equal, or 0 if none.

◆ tommy_tree_find_less_compare()

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.

Parameters
treeThe tree.
cmpComparison function called with cmp_arg and the element in the tree.
cmp_argSearch key, which may have a different type from tree elements.
Returns
The last strictly less node, or 0 if none.

◆ tommy_tree_find_less()

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.

Parameters
treeThe tree.
dataElement used for comparison.
Returns
The last strictly less node, or 0 if none.

◆ tommy_tree_search_less_compare()

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.

Parameters
treeThe tree.
cmpComparison function called with cmp_arg and the element in the tree.
cmp_argSearch key, which may have a different type from tree elements.
Returns
The last strictly less element, or 0 if none.

◆ tommy_tree_search_less()

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.

Parameters
treeThe tree.
dataElement used for comparison.
Returns
The last strictly less element, or 0 if none.

◆ tommy_tree_remove_compare()

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.

Parameters
treeThe tree.
cmpComparison function called with cmp_arg and the element in the tree.
cmp_argSearch key, which may have a different type from tree elements.
Returns
The first equal element in tree order, or 0 if not found.

◆ tommy_tree_remove()

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.

Parameters
treeThe tree.
dataElement used for comparison.
Returns
The first equal element in tree order, or 0 if not found.

◆ tommy_tree_foreach()

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.

// initializes the tree
tommy_tree_init(&tree, cmp);
...
// creates an element
struct element* elem = malloc(sizeof(struct element));
...
// insert it in the tree
tommy_tree_insert(&tree, &elem->node, elem);
...
// deallocates all the elements iterating the tree
tommy_tree_foreach(&tree, free);
tommy_tree_clear(&tree); // resets the tree before reuse
void tommy_tree_clear(tommy_tree *tree)
Removes all elements, preserving the comparison function.
Definition: tommytree.h:189

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.

Parameters
treeThe tree.
funcFunction to call with each element.

◆ tommy_tree_foreach_arg()

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.

Parameters
treeThe tree.
funcFunction to call with each element.
argArgument to pass to the function.

◆ tommy_tree_empty()

tommy_bool_t tommy_tree_empty ( const tommy_tree *  tree)

Checks whether the tree is empty.

Parameters
treeThe tree.
Returns
Nonzero if the tree is empty, 0 otherwise.
Note
This operation is O(1).

◆ tommy_tree_count()

tommy_size_t tommy_tree_count ( const tommy_tree *  tree)

Gets the number of elements.

Parameters
treeThe tree.
Returns
The number of elements in the tree.
Note
This operation is O(1).

◆ tommy_tree_memory_usage()

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.

Parameters
treeThe tree.
Returns
Total memory allocated by the tree, in bytes.