functions implement a generic balanced tree data structure.
A balanced tree stores a sorted set of items of type
and guarantees O(log n) search time.
The user code supplies callback routines for:
- Comparing two items
- Housekeeping associated with adding and removing an item
creates a new tree.
parameter can be retrieved at any time via
and is otherwise ignored.
is a typed memory type string (see
used when allocating memory for the tree.
parameters are pointers to user-supplied callback functions having
the following types:
typedef int gtree_cmp_t(struct gtree *g,
const void *item1, const void *item2);
typedef void gtree_add_t(struct gtree *g, void *item);
typedef void gtree_del_t(struct gtree *g, void *item);
typedef const char *gtree_print_t(struct gtree *g, const void *item);
function should return an integer that is negative, zero, or positive
if the first item is less than, equal to, or greater than the second.
This function must return values consistent with a total ordering
of the items.
If not specified,
item1 - item2
is used, i.e., the sorting is based on the pointers themselves.
routines, if not
will be called whenever an item is added to, or removed from, the tree.
For example, if
causes a new item to replace an old item, there will be a call to the
function for the old item, followed by a call to the
function for the new item.
These callbacks are typically used to increase and decrease reference counts.
callback (also optional) is used by
to print an item when dumping the contents of the tree for debugging.
destroys a tree and frees all associated memory.
If any items remain in the tree, the
callback will be invoked once for each item.
Note that this function takes a pointer to a pointer to a tree.
Upon return, the pointer to the tree will be set to
If it is already equal to
retrieves an item previously stored in the tree, or else returns
if the item is not found.
adds an item to the tree, replacing any item that is equal to it
(as determined by the
is an invalid item and may not be stored in a tree.
is equivalent to
except that the caller pre-allocates the memory necessary to add
the item to the tree, which guarantees a successful operation.
must point to memory allocated with the same
memory type as was passed to
and the size of this memory block must be at least as large as the
size of an internal node, which is returned by
removes an item from the tree.
If the item does not exist, nothing happens.
returns the number of items in the tree.
return the first and last items in the tree, respectively, or
if the tree is empty.
return the next and previous item in the tree to
if there are no more items in the tree.
Traversing the entire tree via
takes O(n log n) time, where n is the number of items in the tree.
traverses the items in the tree in order, invoking
with each item.
returns -1, the traversal stops and
immediately returns -1 to the caller.
returns 0 after all items have been traversed.
Any attempt to modify the tree before
returns will return an error.
generates a sorted array of all the items in the tree.
A pointer to the array is stored in
The array is allocated with memory type
The caller must eventually free the array, also using
prints out the tree for debugging purposes.