Balanced Binary Trees

## Typedefs

typedef cxbool(* | cx_tree_compare_func) (cxcptr, cxcptr)
| The tree's key comparison operator function.

## Functions

cx_tree_iterator | cx_tree_begin (const cx_tree *tree)
| Get an iterator to the first pair in the tree.
cx_tree_iterator | cx_tree_end (const cx_tree *tree)
| Get an iterator for the position after the last pair in the tree.
cx_tree_iterator | cx_tree_next (const cx_tree *tree, cx_tree_const_iterator position)
| Get an iterator for the next pair in the tree.
cx_tree_iterator | cx_tree_previous (const cx_tree *tree, cx_tree_const_iterator position)
| Get an iterator for the previous pair in the tree.
void | cx_tree_clear (cx_tree *tree)
| Remove all pairs from a tree.
cxbool | cx_tree_empty (const cx_tree *tree)
| Check whether a tree is empty.
cx_tree * | cx_tree_new (cx_tree_compare_func compare, cx_free_func key_destroy, cx_free_func value_destroy)
| Create a new tree without any elements.
void | cx_tree_delete (cx_tree *tree)
| Destroy a tree and all its elements.
cxsize | cx_tree_size (const cx_tree *tree)
| Get the actual number of pairs in the tree.
cxsize | cx_tree_max_size (const cx_tree *tree)
| Get the maximum number of pairs possible.
cx_tree_compare_func | cx_tree_key_comp (const cx_tree *tree)
| Get the key comparison function.
void | cx_tree_swap (cx_tree *tree1, cx_tree *tree2)
| Swap the contents of two trees.
cxptr | cx_tree_assign (cx_tree *tree, cx_tree_iterator position, cxcptr data)
| Assign data to an iterator position.
cxptr | cx_tree_get_key (const cx_tree *tree, cx_tree_const_iterator position)
| Get the key from a given iterator position.
cxptr | cx_tree_get_value (const cx_tree *tree, cx_tree_const_iterator position)
| Get the data from a given iterator position.
cx_tree_iterator | cx_tree_find (const cx_tree *tree, cxcptr key)
| Locate an element in the tree.
cx_tree_iterator | cx_tree_lower_bound (const cx_tree *tree, cxcptr key)
| Find the beginning of a subsequence.
cx_tree_iterator | cx_tree_upper_bound (const cx_tree *tree, cxcptr key)
| Find the end of a subsequence.
void | cx_tree_equal_range (const cx_tree *tree, cxcptr key, cx_tree_iterator *begin, cx_tree_iterator *end)
| Find a subsequence matching a given key.
cxsize | cx_tree_count (const cx_tree *tree, cxcptr key)
| Get the number of elements matching a key.
cx_tree_iterator | cx_tree_insert_unique (cx_tree *tree, cxcptr key, cxcptr data)
| Attempt to insert data into a tree.
cx_tree_iterator | cx_tree_insert_equal (cx_tree *tree, cxcptr key, cxcptr data)
| Insert data into a tree.
void | cx_tree_erase_position (cx_tree *tree, cx_tree_iterator position)
| Erase an element from a tree.
void | cx_tree_erase_range (cx_tree *tree, cx_tree_iterator begin, cx_tree_iterator end)
| Erase a range of elements from a tree.
cxsize | cx_tree_erase (cx_tree *tree, cxcptr key)
| Erase all elements from a tree matching the provided key.
cxbool | cx_tree_verify (const cx_tree *tree)
| Validate a tree.

## Detailed Description

The module implements a balanced binary tree type, i.e. a container managing key/value pairs as elements. The container is optimized for lookup operations.

Synopsis:
  #include "cxtree.h"

## Typedef Documentation

## cx_tree_compare_func

typedef cxbool(* cx_tree_compare_func) (cxcptr, cxcptr)

The tree's key comparison operator function.

This type of function is used by a tree internally to compare the keys of its elements. A key comparison operator returns `TRUE` if the comparison of its first argument with the second argument succeeds, and `FALSE` otherwise, as, for instance, the logical operators <, >, ==, and != do.

Examples:

- A less than operator for integer values
  #include "cxtree.h"
  cxbool less_int(cxcptr i1, cxcptr i2)
  {
  return *i1 < *i2;
  }
- A less than and an equal operator for strings
  #include <string.h>
  #include "cxtree.h"
  cxbool less_string(cxcptr s1, cxcptr s2)
  {
  return strcmp(s1, s2) < 0;
  }
  cxbool equal_string(cxptr s1, cxptr s2)
  {
  return strcmp(s1, s2) == 0;
  }

## Function Documentation

## cx_tree_assign()

cxptr cx_tree_assign | ( | cx_tree * | tree,
|  | cx_tree_iterator | position,
|  | cxcptr | data )

Assign data to an iterator position.

Parameters

  tree | A tree.
  position | Iterator positions where the data will be stored.
  data | Data to store.

Returns
  Handle to the previously stored data object.

The function assigns a data object reference data to the iterator position position of the tree tree.

Referenced by cx_map_assign(), cx_map_put(), and cx_multimap_assign().

## cx_tree_begin()

cx_tree_iterator cx_tree_begin | ( | const cx_tree * | tree | ) |

Get an iterator to the first pair in the tree.

Parameters

  tree | The tree to query.

Returns
  Iterator for the first pair or cx_tree_end() if the tree is empty.

The function returns a handle for the first pair in the tree tree. The returned iterator cannot be used directly to access the value field of the key/value pair, but only through the appropriate methods.

Referenced by cx_map_begin(), and cx_multimap_begin().

## cx_tree_clear()

void cx_tree_clear | ( | cx_tree * | tree | ) |

Remove all pairs from a tree.

Parameters

  tree | Tree to be cleared.

Returns
  Nothing.

The tree tree is cleared, i.e. all pairs are removed from the tree. Keys and values are destroyed using the key and value destructors set up during tree creation. After calling this function the tree is empty.

Referenced by cx_map_clear(), and cx_multimap_clear().

## cx_tree_count()

cxsize cx_tree_count | ( | const cx_tree * | tree,
|  | cxcptr | key )

Get the number of elements matching a key.

Parameters

  tree | A tree.
  key | Key of the (key, value) pair(s) to locate.

Returns
  The number of elements with the specified key.

Counts all elements of the tree tree matching the key key.

Referenced by cx_multimap_count().

## cx_tree_delete()

void cx_tree_delete | ( | cx_tree * | tree | ) |

Destroy a tree and all its elements.

Parameters

  tree | The tree to destroy.

Returns
  Nothing.

The tree tree is deallocated. All data values and keys are deallocated using the tree's key and value destructor. If no key and/or value destructor was set when the tree was created the keys and the stored data values are left untouched. In this case the key and value deallocation is the responsibility of the user.

See also
  cx_tree_new()

References cx_free().

Referenced by cx_map_delete(), and cx_multimap_delete().

## cx_tree_empty()

cxbool cx_tree_empty | ( | const cx_tree * | tree | ) |

Check whether a tree is empty.

Parameters

  tree | A tree.

Returns
  The function returns `TRUE` if the tree is empty, and `FALSE` otherwise.

The function checks if the tree contains any pairs. Calling this function is equivalent to the statement:

return (cx_tree_size(tree) == 0);
cx_tree_size
cxsize cx_tree_size(const cx_tree *tree)
Get the actual number of pairs in the tree.
Definition cxtree.c:1213

Referenced by cx_map_empty(), and cx_multimap_empty().

## cx_tree_end()

cx_tree_iterator cx_tree_end | ( | const cx_tree * | tree | ) |

Get an iterator for the position after the last pair in the tree.

Parameters

  tree | The tree to query.

Returns
  Iterator for the end of the tree.

The function returns an iterator for the position one past the last pair in the tree tree. The iteration is done in ascending order according to the keys. The returned iterator cannot be used directly to access the value field of the key/value pair, but only through the appropriate methods.

Referenced by cx_map_count(), cx_map_end(), cx_map_get(), cx_map_put(), and cx_multimap_end().

## cx_tree_equal_range()

void cx_tree_equal_range | ( | const cx_tree * | tree,
|  | cxcptr | key,
|  | cx_tree_iterator * | begin,
|  | cx_tree_iterator * | end )

Find a subsequence matching a given key.

Parameters

  tree | A tree.
  key | The key of the (key, value) pair(s) to be located.
  begin | First element with key key.
  end | Last element with key key.

Returns
  Nothing.

The function returns the beginning and the end of a subsequence of tree elements with the key key through through the begin and end arguments. After calling this function begin possibly points to the first element of tree matching the key key and end possibly points to the last element of the sequence. If key is not present in the tree begin points to the next greater element or, if no such element exists, to cx_tree_end().

Referenced by cx_map_equal_range(), and cx_multimap_equal_range().

## cx_tree_erase()

cxsize cx_tree_erase | ( | cx_tree * | tree,
|  | cxcptr | key )

Erase all elements from a tree matching the provided key.

Parameters

  tree | A tree.
  key | Key of the element to be erased.

Returns
  The number of removed elements.

This function erases all elements with the specified key key, from tree. Key and value associated with the erased pairs are deallocated using the tree's key and value destructors, provided they have been set.

Referenced by cx_map_erase(), and cx_multimap_erase().

## cx_tree_erase_position()

void cx_tree_erase_position | ( | cx_tree * | tree,
|  | cx_tree_iterator | position )

Erase an element from a tree.

Parameters

  tree | A tree.
  position | Iterator position of the element to be erased.

Returns
  Nothing.

This function erases an element, specified by the iterator position, from tree. Key and value associated with the erased pair are deallocated using the tree's key and value destructors, provided they have been set.

Referenced by cx_map_erase_position(), and cx_multimap_erase_position().

## cx_tree_erase_range()

void cx_tree_erase_range | ( | cx_tree * | tree,
|  | cx_tree_iterator | begin,
|  | cx_tree_iterator | end )

Erase a range of elements from a tree.

Parameters

  tree | A tree.
  begin | Iterator pointing to the start of the range to erase.
  end | Iterator pointing to the end of the range to erase.

Returns
  Nothing.

This function erases all elements in the range [begin, end) from the tree tree. Key and value associated with the erased pair(s) are deallocated using the tree's key and value destructors, provided they have been set.

Referenced by cx_map_erase_range(), and cx_multimap_erase_range().

## cx_tree_find()

cx_tree_iterator cx_tree_find | ( | const cx_tree * | tree,
|  | cxcptr | key )

Locate an element in the tree.

Parameters

  tree | A tree.
  key | Key of the (key, value) pair to locate.

Returns
  Iterator pointing to the sought-after element, or cx_tree_end() if it was not found.

The function searches the tree tree for an element with a key matching key. If the search was successful an iterator to the sought-after pair is returned. If the search did not succeed, i.e. key is not present in the tree, a one past the end iterator is returned.

Referenced by cx_map_count(), cx_map_find(), and cx_multimap_find().

## cx_tree_get_key()

cxptr cx_tree_get_key | ( | const cx_tree * | tree,
|  | cx_tree_const_iterator | position )

Get the key from a given iterator position.

Parameters

  tree | A tree.
  position | Iterator position the data is retrieved from.

Returns
  Reference for the key.

The function returns a reference to the key associated with the iterator position position in the tree tree.

Note
  One must not modify the key of position through the returned reference, since this might corrupt the tree!

Referenced by cx_map_get(), cx_map_get_key(), and cx_multimap_get_key().

## cx_tree_get_value()

cxptr cx_tree_get_value | ( | const cx_tree * | tree,
|  | cx_tree_const_iterator | position )

Get the data from a given iterator position.

Parameters

  tree | A tree.
  position | Iterator position the data is retrieved from.

Returns
  Handle for the data object.

The function returns a reference to the data stored at iterator position position in the tree tree.

Referenced by cx_map_get(), cx_map_get_value(), and cx_multimap_get_value().

## cx_tree_insert_equal()

cx_tree_iterator cx_tree_insert_equal | ( | cx_tree * | tree,
|  | cxcptr | key,
|  | cxcptr | data )

Insert data into a tree.

Parameters

  tree | A tree.
  key | Key used to store the data.
  data | Data to insert.

Returns
  An iterator that points to the inserted pair.

This function inserts a (key, value) pair into the tree tree. Contrary to cx_tree_insert_unique() the key key used for inserting data may already be present in the tree.

Referenced by cx_multimap_insert().

## cx_tree_insert_unique()

cx_tree_iterator cx_tree_insert_unique | ( | cx_tree * | tree,
|  | cxcptr | key,
|  | cxcptr | data )

Attempt to insert data into a tree.

Parameters

  tree | A tree.
  key | Key used to store the data.
  data | Data to insert.

Returns
  An iterator that points to the inserted pair, or `NULL` if the pair could not be inserted.

This function attempts to insert a (key, value) pair into the tree tree. The insertion fails if the key already present in the tree, i.e. if the key is not unique.

Referenced by cx_map_get(), cx_map_insert(), and cx_map_put().

## cx_tree_key_comp()

cx_tree_compare_func cx_tree_key_comp | ( | const cx_tree * | tree | ) |

Get the key comparison function.

Parameters

  tree | The tree to query.

Returns
  Handle for the tree's key comparison function.

The function retrieves the function used by the tree methods for comparing keys. The key comparison function is set during tree creation.

See also
  cx_tree_new()

Referenced by cx_map_get(), cx_map_key_comp(), and cx_multimap_key_comp().

## cx_tree_lower_bound()

cx_tree_iterator cx_tree_lower_bound | ( | const cx_tree * | tree,
|  | cxcptr | key )

Find the beginning of a subsequence.

Parameters

  tree | A tree.
  key | Key of the (key, value) pair(s) to locate.

Returns
  Iterator pointing to the first position where an element with key key would get inserted, i.e. the first element with a key greater or equal than key.

The function returns the first element of a subsequence of elements in the tree that match the given key key. If key is not present in the tree tree an iterator pointing to the first element that has a greater key than key or cx_tree_end() if no such element exists.

Referenced by cx_map_get(), cx_map_lower_bound(), cx_map_put(), and cx_multimap_lower_bound().

## cx_tree_max_size()

cxsize cx_tree_max_size | ( | const cx_tree * | tree | ) |

Get the maximum number of pairs possible.

Parameters

  tree | A tree.

Returns
  The maximum number of pairs that can be stored in the tree.

Retrieves the tree's capacity, i.e. the maximum possible number of pairs a tree can manage.

Referenced by cx_map_max_size(), and cx_multimap_max_size().

## cx_tree_new()

cx_tree * cx_tree_new | ( | cx_tree_compare_func | compare,
|  | cx_free_func | key_destroy,
|  | cx_free_func | value_destroy )

Create a new tree without any elements.

Parameters

  compare | Function used to compare keys.
  key_destroy | Destructor for the keys.
  value_destroy | Destructor for the value field.

Returns
  Handle for the newly allocated tree.

Memory for a new tree is allocated and the tree is initialized to be a valid empty tree.

The tree's key comparison function is set to compare. It must return `TRUE` or `FALSE` if the comparison of the first argument passed to it with the second argument is found to be true or false respectively.

The destructors for a tree node's key and value field are set to key_destroy and value_destroy. Whenever a tree node is destroyed these functions are used to deallocate the memory used by the key and the value. Each of the destructors might be `NULL`, i.e. keys and values are not deallocated during destroy operations.

See also
  cx_tree_compare_func()

References cx_malloc().

Referenced by cx_map_new(), and cx_multimap_new().

## cx_tree_next()

cx_tree_iterator cx_tree_next | ( | const cx_tree * | tree,
|  | cx_tree_const_iterator | position )

Get an iterator for the next pair in the tree.

Parameters

  tree | A tree.
  position | Current iterator position.

Returns
  Iterator for the pair immediately following position.

The function returns an iterator for the next pair in the tree tree with respect to the current iterator position position. Iteration is done in ascending order according to the keys. If the tree is empty or position points to the end of the tree the function returns cx_tree_end().

Referenced by cx_map_next(), and cx_multimap_next().

## cx_tree_previous()

cx_tree_iterator cx_tree_previous | ( | const cx_tree * | tree,
|  | cx_tree_const_iterator | position )

Get an iterator for the previous pair in the tree.

Parameters

  tree | A tree.
  position | Current iterator position.

Returns
  Iterator for the pair immediately preceding position.

The function returns an iterator for the previous pair in the tree tree with respect to the current iterator position position. Iteration is done in ascending order according to the keys. If the tree is empty or position points to the beginning of the tree the function returns cx_tree_end().

Referenced by cx_map_previous(), and cx_multimap_previous().

## cx_tree_size()

cxsize cx_tree_size | ( | const cx_tree * | tree | ) |

Get the actual number of pairs in the tree.

Parameters

  tree | A tree.

Returns
  The current number of pairs, or 0 if the tree is empty.

Retrieves the current number of pairs stored in the tree.

Referenced by cx_map_size(), and cx_multimap_size().

## cx_tree_swap()

void cx_tree_swap | ( | cx_tree * | tree1,
|  | cx_tree * | tree2 )

Swap the contents of two trees.

Parameters

  tree1 | First tree.
  tree2 | Second tree.

Returns
  Nothing.

All pairs stored in the first tree tree1 are moved to the second tree tree2, while the pairs from tree2 are moved to tree1. Also the key comparison function, the key and the value destructor are exchanged.

Referenced by cx_map_swap(), and cx_multimap_swap().

## cx_tree_upper_bound()

cx_tree_iterator cx_tree_upper_bound | ( | const cx_tree * | tree,
|  | cxcptr | key )

Find the end of a subsequence.

Parameters

  tree | A tree.
  key | Key of the (key, value) pair(s) to locate.

Returns
  Iterator pointing to the last position where an element with key key would get inserted, i.e. the first element with a key greater than key.

The function returns the last element of a subsequence of elements in the tree that match the given key key. If key is not present in the tree tree an iterator pointing to the first element that has a greater key than key or cx_tree_end() if no such element exists.

Referenced by cx_map_upper_bound(), and cx_multimap_upper_bound().

## cx_tree_verify()

cxbool cx_tree_verify | ( | const cx_tree * | tree | ) |

Validate a tree.

Parameters

  tree | The tree to verify.

Returns
  Returns `TRUE` if the tree is valid, or `FALSE` otherwise.

The function is provided for debugging purposes. It verifies that the internal tree structure of tree is valid.