cgul_rbtree.h File Reference

red-black tree implementation More...

#include "cgul_common.h"
#include "cgul_cache.h"
#include "cgul_exception.h"
#include "cgul_rbtree_node.h"

Include dependency graph for cgul_rbtree.h:

This graph shows which files directly or indirectly include this file:

Typedefs
typedef typedefCGUL_BEGIN_C struct cgul_rbtree *	cgul_rbtree_t
typedef int(*	cgul_rbtree__compare_t) (const void *key1, const void *key2)
typedef int(*	cgul_rbtree__fold_key_t) (cgul_exception_t *cex, const void *key, void *data)
typedef int(*	cgul_rbtree__fold_value_t) (cgul_exception_t *cex, void *value, void *data)
typedef int(*	cgul_rbtree__fold_pair_t) (cgul_exception_t *cex, const void *key, void *value, void *data)
typedef int(*	cgul_rbtree__traverse_t) (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree_node_t n, void *data)

Functions
CGUL_EXPORT cgul_rbtree_t	cgul_rbtree__new (cgul_exception_t *cex, cgul_rbtree__compare_t compare)
CGUL_EXPORT cgul_rbtree_t	cgul_rbtree__new_with_indexing (cgul_exception_t *cex, cgul_rbtree__compare_t compare)
CGUL_EXPORT void	cgul_rbtree__delete (cgul_rbtree_t t)
CGUL_EXPORT void	cgul_rbtree__free_keys (cgul_rbtree_t t)
CGUL_EXPORT void	cgul_rbtree__free_values (cgul_rbtree_t t)
CGUL_EXPORT unsigned long int	cgul_rbtree__get_cache_size (cgul_exception_t *cex, cgul_rbtree_t t)
CGUL_EXPORT void	cgul_rbtree__set_cache_size (cgul_exception_t *cex, cgul_rbtree_t t, unsigned long int size)
CGUL_EXPORT unsigned long int	cgul_rbtree__get_cache_reserve (cgul_exception_t *cex, cgul_rbtree_t t)
CGUL_EXPORT void	cgul_rbtree__set_cache_reserve (cgul_exception_t *cex, cgul_rbtree_t t, unsigned long int reserve)
CGUL_EXPORT int	cgul_rbtree__is_empty (cgul_exception_t *cex, cgul_rbtree_t t)
CGUL_EXPORT int	cgul_rbtree__insert (cgul_exception_t *cex, cgul_rbtree_t t, const void *key, cgul_rbtree_node_t *n)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree__find (cgul_exception_t *cex, cgul_rbtree_t t, const void *key)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree__find_at (cgul_exception_t *cex, cgul_rbtree_t t, unsigned long int index)
CGUL_EXPORT int	cgul_rbtree__find_rank (cgul_exception_t *cex, cgul_rbtree_t t, const void *key, unsigned long int *rank)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree__find_floor (cgul_exception_t *cex, cgul_rbtree_t t, const void *search_key)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree__find_ceiling (cgul_exception_t *cex, cgul_rbtree_t rbtree, const void *search_key)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree__find_special (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree__compare_t compare, const void *data)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree__get_front (cgul_exception_t *cex, cgul_rbtree_t t)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree__get_back (cgul_exception_t *cex, cgul_rbtree_t t)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree__get_oldest (cgul_exception_t *cex, cgul_rbtree_t t)
CGUL_EXPORT void	cgul_rbtree__set_oldest (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree_node_t n)
CGUL_EXPORT cgul_rbtree_node_t	cgul_rbtree__get_youngest (cgul_exception_t *cex, cgul_rbtree_t t)
CGUL_EXPORT void	cgul_rbtree__set_youngest (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree_node_t n)
CGUL_EXPORT int	cgul_rbtree__remove (cgul_exception_t *cex, cgul_rbtree_t t, const void *key_in, void **key_out, void **value_out)
CGUL_EXPORT void	cgul_rbtree__remove_node (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree_node_t n, void **key_out, void **value_out)
CGUL_EXPORT int	cgul_rbtree__remove_at (cgul_exception_t *cex, cgul_rbtree_t t, unsigned long int index, void **key_out, void **value_out)
CGUL_EXPORT int	cgul_rbtree__remove_front (cgul_exception_t *cex, cgul_rbtree_t t, void **key_out, void **value_out)
CGUL_EXPORT int	cgul_rbtree__remove_back (cgul_exception_t *cex, cgul_rbtree_t t, void **key_out, void **value_out)
CGUL_EXPORT int	cgul_rbtree__remove_range (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree_node_t first, cgul_rbtree_node_t last, cgul_cache_t keys_cache, cgul_cache_t values_cache)
CGUL_EXPORT void	cgul_rbtree__clear (cgul_exception_t *cex, cgul_rbtree_t t, cgul_cache_t keys_cache, cgul_cache_t values_cache)
CGUL_EXPORT unsigned long int	cgul_rbtree__get_size (cgul_exception_t *cex, cgul_rbtree_t t)
CGUL_EXPORT int	cgul_rbtree__is_ok (cgul_exception_t *cex, cgul_rbtree_t t)
CGUL_EXPORT void	cgul_rbtree__swap (cgul_exception_t *cex, cgul_rbtree_t t1, cgul_rbtree_t t2)
CGUL_EXPORT void	cgul_rbtree__foldl_keys (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree__fold_key_t f, void *data)
CGUL_EXPORT void	cgul_rbtree__foldr_keys (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree__fold_key_t f, void *data)
CGUL_EXPORT void	cgul_rbtree__foldl_values (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree__fold_value_t f, void *data)
CGUL_EXPORT void	cgul_rbtree__foldr_values (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree__fold_value_t f, void *data)
CGUL_EXPORT void	cgul_rbtree__foldl_pairs (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree__fold_pair_t f, void *data)
CGUL_EXPORT void	cgul_rbtree__foldr_pairs (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree__fold_pair_t f, void *data)
CGUL_EXPORT void	cgul_rbtree__traverse (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree__traverse_t f, void *data)
CGUL_EXPORT void	cgul_rbtree__traverse_range (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree_node_t first, cgul_rbtree_node_t last, cgul_rbtree__traverse_t f, void *data)

Detailed Description

Red-black tree implementation.

Author

Paul Serice

Typedef Documentation

cgul_rbtree_t

typedef typedefCGUL_BEGIN_C struct cgul_rbtree* cgul_rbtree_t

Opaque pointer to a cgul_rbtree instance.

cgul_rbtree__compare_t

typedef int(* cgul_rbtree__compare_t) (const void *key1, const void *key2)

This typedef is the interface the client must define in order for cgul_rbtree to sort your keys as they are inserted. When you define your comparison function, you should compare key1 to key2 and return less than zero, zero, or greater than zero if key1 is less than, equal to, or greater than key2.

Parameters

[in]	key1	first key
[in]	key2	second key

Returns

result of comparison

cgul_rbtree__fold_key_t

typedef int(* cgul_rbtree__fold_key_t) (cgul_exception_t *cex, const void *key, void *data)

This typedef is the interface for the combining function used by the following methods:

    cgul_rbtree__foldl_keys()
    cgul_rbtree__foldr_keys()

The client must not alter key.

Parameters

[in,out]	cex	c-style exception
[in]	key	key
[in]	data	client data

Returns

whether to continue

cgul_rbtree__fold_value_t

typedef int(* cgul_rbtree__fold_value_t) (cgul_exception_t *cex, void *value, void *data)

This typedef is the interface for the combining function used by the following methods:

    cgul_rbtree__foldl_values()
    cgul_rbtree__foldr_values()

Parameters

[in,out]	cex	c-style exception
[in]	value	value
[in]	data	client data

Returns

whether to continue

cgul_rbtree__fold_pair_t

typedef int(* cgul_rbtree__fold_pair_t) (cgul_exception_t *cex, const void *key, void *value, void *data)

This typedef is the interface for the combining function used by the following methods:

    cgul_rbtree__foldl_pairs()
    cgul_rbtree__foldr_pairs()

The client must not alter key.

Parameters

[in,out]	cex	c-style exception
[in]	key	key
[in]	value	value
[in]	data	client data

Returns

whether to continue

cgul_rbtree__traverse_t

typedef int(* cgul_rbtree__traverse_t) (cgul_exception_t *cex, cgul_rbtree_t t, cgul_rbtree_node_t n, void *data)

This typedef is the interface for the callback function used by the following methods:

    cgul_rbtree__traverse()
    cgul_rbtree__traverse_range()

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	n	node
[in]	data	client data

Returns

whether to continue

Function Documentation

cgul_rbtree__new()

CGUL_EXPORT cgul_rbtree_t cgul_rbtree__new	(	cgul_exception_t *	cex,
		cgul_rbtree__compare_t	compare
	)

Create a new cgul_rbtree object. compare is the comparison function that allows the tree to maintain its sorted order. The caller is responsible for freeing the object by calling cgul_rbtree__delete(). If memory cannot be allocated, NULL is returned, and an exception is thrown.

The cgul_rbtree object that is returned does not allow you to index into it as though it were an array. This saves you two unsigned long values for each node in the tree. It also saves you about 15% for inserts and deletes. If in doubt, use this constructor.

This class does not take ownership of the inserted keys/value pairs. Instead, the client is responsible for freeing the key/value pairs only after their nodes have been permanently removed from the cgul_rbtree. The cgul_rbtree__traverse() method can be used to remove each node safely before calling cgul_rbtree__delete().

Parameters

[in,out]	cex	c-style exception
[in]	compare	comparison function

Returns

new cgul_rbtree instance

See also

cgul_rbtree__compare_t

Referenced by cgul_rbtree_cxx::cgul_rbtree_cxx().

cgul_rbtree__new_with_indexing()

CGUL_EXPORT cgul_rbtree_t cgul_rbtree__new_with_indexing	(	cgul_exception_t *	cex,
		cgul_rbtree__compare_t	compare
	)

Create a new cgul_rbtree object. compare is the comparison function that allows the tree to maintain its sorted order. The caller is responsible for freeing the object by calling cgul_rbtree__delete(). If memory cannot be allocated, NULL is returned, and an exception is thrown.

The cgul_rbtree object that is returned allows you to index into it as though it were an array. This costs you two unsigned long values for each node in the tree. It also costs you about 15% for inserts and deletes. You should only use this constructor if you know you want to be able to call cgul_rbtree__find_at() or cgul_rbtree__remove_at().

This class does not take ownership of the inserted keys/value pairs. Instead, the client is responsible for freeing the key/value pairs only after their nodes have been permanently removed from the cgul_rbtree. The cgul_rbtree__traverse() method can be used to remove each node safely before calling cgul_rbtree__delete().

Parameters

[in,out]	cex	c-style exception
[in]	compare	comparison function

Returns

new cgul_rbtree instance

See also

cgul_rbtree__compare_t

Referenced by cgul_rbtree_cxx::cgul_rbtree_cxx().

cgul_rbtree__delete()

CGUL_EXPORT void cgul_rbtree__delete

(

cgul_rbtree_t

t

)

This method frees all internally allocated memory. This does not include the key/value pairs stored in the tree. The client is responsible for freeing the key/value pairs when the client thinks it is convenient and safe to do so; however, the client must understand that freeing a key before removing its node invalidates the data structure.

As a convenience, you may want to call cgul_rbtree__clear() before calling this method in order to properly put the keys and values back on their respective cgul_cache objects (if cgul_cache objects are being used) before you delete the tree. If cgul_cache objects are not being used, the client needs to arrange some other mechanism to free the keys or values.

Do not try to access t after calling this method.

Parameters

[in]

t

cgul_rbtree instance

See also

cgul_rbtree__free_keys()

cgul_rbtree__free_values()

Referenced by cgul_rbtree_cxx::set_obj(), and cgul_rbtree_cxx::~cgul_rbtree_cxx().

cgul_rbtree__free_keys()

CGUL_EXPORT void cgul_rbtree__free_keys

(

cgul_rbtree_t

t

)

This method calls free() on all the keys in the tree t. Because this is such a common operation, it is an exception to the rule that cgul containers never free keys. This method should only ever be called immediately before calling cgul_rbtree__delete() because it otherwise invalidates the tree. Because this function is basically an extension of cgul_rbtree__delete(), it does not accept a cgul_exception object as an input parameter.

Parameters

[in]

t

cgul_rbtree instance

Referenced by cgul_rbtree_cxx::free_keys().

cgul_rbtree__free_values()

CGUL_EXPORT void cgul_rbtree__free_values

(

cgul_rbtree_t

t

)

This method calls free() on all the values in the tree t. Because this is such a common operation, it is an exception to the rule that cgul containers never free values. This method should only ever be called immediately before calling cgul_rbtree__delete() because it otherwise invalidates the tree. Because this function is basically an extension of cgul_rbtree__delete(), it does not accept a cgul_exception object as an input parameter.

Parameters

[in]

t

cgul_rbtree instance

Referenced by cgul_rbtree_cxx::free_values().

cgul_rbtree__get_cache_size()

CGUL_EXPORT unsigned long int cgul_rbtree__get_cache_size	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t
	)

Get the size of the cache of nodes.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance

Returns

size of the cache of nodes

Referenced by cgul_rbtree_cxx::get_cache_size().

cgul_rbtree__set_cache_size()

CGUL_EXPORT void cgul_rbtree__set_cache_size	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		unsigned long int	size
	)

Set the size of the cache of nodes.

For efficiency, the cgul_rbtree object can keep a cache of nodes that can be reused. In many situations, this can greatly reduce the number of calls to malloc() which can greatly improve performance and reduce memory fragmentation.

You can release all the cached nodes and disable caching of nodes by setting the cache reserve to 0 and the cache size to 0 (in that order). This is the default.

If an error occurs (while enlarging the cache), an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	size	of the cache of nodes

Referenced by cgul_rbtree_cxx::set_cache_size().

cgul_rbtree__get_cache_reserve()

CGUL_EXPORT unsigned long int cgul_rbtree__get_cache_reserve	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t
	)

Get the reserve limit of the cache of nodes.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance

Returns

reserve limit of the cache of nodes

Referenced by cgul_rbtree_cxx::get_cache_reserve().

cgul_rbtree__set_cache_reserve()

CGUL_EXPORT void cgul_rbtree__set_cache_reserve	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		unsigned long int	reserve
	)

Set the reserve limit of the cache of nodes and guarantee that at least that many nodes are allocated and waiting in reserve.

When you use this method to increase the reserve, you are guaranteed that at least reserve count of nodes will be allocated and reserved for future use.

This is useful because cgul_rbtree__insert() can throw an exception if it cannot allocate a node to hold the key/value pair. Thus, by allocating and reserving a node now, we know that cgul_rbtree__insert() will be able to run without error later when the node is "unreserved". Normally, this is not an issue because you can almost always just insert at the moment when it is requested, but if the cgul_rbtree is busy at that moment (perhaps it is iterating over its nodes), you'll have to queue insert (and remove) requests for later execution.

To "unreserve" a node so that it can be used, you simply call this method again with a value for reserve that is less than the current reserve limit.

If an error occurs while allocating the reserved nodes, an exception is thrown.

WARNING: If you reserve nodes without "unreserving" them, you will introduce a memory leak that is difficult to track down because this class is careful to free all of the cached nodes (including the reserved nodes) when it is deleted, but the reserved nodes will just sit around in memory until that time. Thus, after reserving nodes by calling this method, you must remember to timely set the reserve level back to zero in order to make those nodes available.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	reserve	of the cache of nodes

See also

cgul_cache__set_reserve

Referenced by cgul_rbtree_cxx::set_cache_reserve().

cgul_rbtree__is_empty()

CGUL_EXPORT int cgul_rbtree__is_empty	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t
	)

Return 1 if the tree is empty; otherwise, return 0.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance

Returns

whether the tree is empty

Referenced by cgul_rbtree_cxx::is_empty().

cgul_rbtree__insert()

CGUL_EXPORT int cgul_rbtree__insert	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		const void *	key,
		cgul_rbtree_node_t *	n
	)

Insert key into the tree t. If key already exists, another node with the same key is not created. The new or pre-existing node is returned in *n if n is not NULL.

If a matching node is not found, 1 is returned because a new node can and will be inserted. If a matching node is found, 0 is returned because the insertion failed because the key already exists.

If an error occurs, 0 is returned, *n is set to NULL (if n is not NULL), and an exception is thrown.

It is important to understand that the cgul_rbtree class (like all containers in the cgul library) does not take ownership of key. It also does not attempt to make a copy of the thing pointed to by key. This gives the user complete control over the lifetime of the key and gives a real performance boost in many cases; however, this means that key must not be invalidated while it is still being used by this class.

This method operates as it does so that you only have to search the tree once when doing an insert. Logically, you would usually like to do a find to see if the tree holds your key. If it does, you use the value associated with that key in some way. If it does not, you then want to insert a new key/value pair into the tree. The problem with divorcing the find from the insert is that it then requires you to search the tree twice. Once to see if the key exists and once to do the insertion.

To prevent having to search the tree twice, you can just call this method to handle both inserting and updating nodes. It will search the tree once, and it will always return a pointer to the correct node. You can then use cgul_rbtree_node__get_value() or cgul_rbtree_node__set_value() to get or set the value indexed by "key".

TIP: You might find it convenient to use cgul_string to build up a string that you use as a key. You can then use cgul_string__get_value() [yes, get_value()] and pass the string to cgul_rbtree__insert(). If the insert succeeds, you can inform the cgul_string object that it is no longer the owner of the underlying C-style string by calling cgul_string__take_value() [yes, take_value()]. An example is as follows:

    int insert_rv = 0;
    cgul_rbtree_node_t n = NULL;

    char* w = cgul_string__get_value(word);
    insert_rv = cgul_rbtree__insert(t, w, &n);
    if (*cex) {
        goto out;
    }
    if (insert_rv) {
        cgul_string__take_value(word);
        . . .
    } else {
        . . .
    }

NOTE: Inserting a key/value pair does not cause this class to take ownership of key or value. The client must make sure the values pointed to by key and value are not invalidated during the life of the newly created node. If the client needs to delete the key or the value or both, the client needs to manually arrange for this.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	key	key
[out]	n	node that already existed or was newly created

Returns

1 if a new node was inserted; 0 if a node with the same key already exists

Referenced by cgul_rbtree_cxx::insert().

cgul_rbtree__find()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree__find	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		const void *	key
	)

Find the node indexed by key. If the key does not exist, NULL is returned; otherwise, the node associated with the key is returned.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	key	key

Returns

node associated with the key or NULL

Referenced by cgul_rbtree_cxx::find().

cgul_rbtree__find_at()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree__find_at	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		unsigned long int	index
	)

Find the node indexed by position. This lets you use a cgul_rbtree instances like you would an array. Indexing into cgul_rbtree is a logarithmic function which will be slower than an array, but you get all the advantages of a balanced binary tree including fast insertion and deletion. So, if you ever feel the need to shift the elements of an array, this method might be for you.

If index is out of range, NULL is returned; otherwise, the node returned is the same node that would be returned if you had an array t that held all the nodes in the tree in sorted order, and you asked for t[index].

This method throws an exception if t was not created with cguil_rbtree__new_with_indexing().

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	index	index into sorted keys of node to return

Returns

node associated with index

See also

cgul_rbtree__find_rank()

Referenced by cgul_rbtree_cxx::find_at().

cgul_rbtree__find_rank()

CGUL_EXPORT int cgul_rbtree__find_rank	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		const void *	key,
		unsigned long int *	rank
	)

Return whether the rank of the key key could be determined. If the rank could be determined it is returned in *rank (if rank is not NULL).

The rank is the number of keys less than key. It can be used as the index parameter to cgul_rbtree__find_at() in order to lookup key by index.

This method throws an exception if t was not created with cguil_rbtree__new_with_indexing().

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	key	key
[out]	rank	rank of key

Returns

whether the key exists in the tree

See also

cgul_rbtree__find_at()

Referenced by cgul_rbtree_cxx::find_rank().

cgul_rbtree__find_floor()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree__find_floor	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		const void *	search_key
	)

Find the node having the largest key less than or equal to the search key search_key and return it. If such a key does not exist, NULL is returned instead.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	search_key	search key

Returns

floor or NULL

Referenced by cgul_rbtree_cxx::find_floor().

cgul_rbtree__find_ceiling()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree__find_ceiling	(	cgul_exception_t *	cex,
		cgul_rbtree_t	rbtree,
		const void *	search_key
	)

Find the node having the smallest key greater than or equal to the search key search_key and return it. If such a key does not exist, NULL is returned instead.

Parameters

[in]	cex	c-style exception
[in]	rbtree	cgul_rbtree instance
[in]	search_key	search key

Returns

ceiling or NULL

Referenced by cgul_rbtree_cxx::find_ceiling().

cgul_rbtree__find_special()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree__find_special	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree__compare_t	compare,
		const void *	data
	)

This function lets you search the tree using arbitrary client data rather than a specific key. The comparison function compare will be called with key1 set to the current node which is of type cgul_rbtree_node_t and key2 set to data. The comparison function should return less than one if you want to move to the current node's left child. It should return greater than one if you want to move to the current node's right child. It should return zero, if you have found what you are looking for. If your comparison function returns zero, that is the node that will be returned; otherwise, NULL is returned.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	compare	comparison function
[in]	data	data passed to compare in lieu of a second key

Returns

node that was found or NULL if no node could be found

cgul_rbtree__get_front()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree__get_front	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t
	)

Return the first node according to sort order. This operation is O(1). If the tree is empty, NULL is returned. This class does not have to search the tree in order to find the front node because it efficiently keeps a direct pointer to the front node up to date.

The following example shows how to iterate over the entire tree in sort order:

    cgul_rbtree_node_t n = cgul_rbtree__get_front(cex, t);
    for ( ; n ; n = cgul_rbtree_node__get_next(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance

Returns

front node

Referenced by cgul_multimap_cxx::foldl_keys(), cgul_rbtree_cxx::foldl_keys(), cgul_rbtree_cxx::foldl_pairs(), cgul_rbtree_cxx::foldl_values(), cgul_rbtree_cxx::get_front(), and cgul_rbtree_cxx::traverse_range().

cgul_rbtree__get_back()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree__get_back	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t
	)

Return the last node according to sort order. This operation is O(1). If the tree is empty, NULL is returned. This class does not have to search the tree in order to find the back node because it efficiently keeps a direct pointer to the back node up to date.

The following example shows how to iterate over the entire tree in reverse sort order:

    cgul_rbtree_node_t n = cgul_rbtree__get_back(cex, t);
    for ( ; n ; n = cgul_rbtree_node__get_prev(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance

Returns

back node

Referenced by cgul_multimap_cxx::foldr_keys(), cgul_rbtree_cxx::foldr_keys(), cgul_rbtree_cxx::foldr_pairs(), cgul_rbtree_cxx::foldr_values(), cgul_rbtree_cxx::get_back(), and cgul_rbtree_cxx::traverse_range().

cgul_rbtree__get_oldest()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree__get_oldest	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t
	)

Return the oldest node according to chronological order (i.e., the order in which the nodes are inserted). This operation is O(1). If the tree is empty, NULL is returned. This class does not have to search the tree in order to find the oldest node because it efficiently keeps a direct pointer to the oldest node up to date.

The following example shows how to iterate over the entire tree in chronological order:

    cgul_rbtree_node_t n = cgul_rbtree__get_oldest(cex, t);
    for ( ; n ; n = cgul_rbtree_node__get_younger(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance

Returns

oldest node

See also

cgul_rbtree_node__get_younger()

Referenced by cgul_rbtree_cxx::get_oldest().

cgul_rbtree__set_oldest()

CGUL_EXPORT void cgul_rbtree__set_oldest	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree_node_t	n
	)

Set the oldest node in the tree to be n. Calling this method has the potential to confuse iterators and should be handled with roughly the same level of caution as calling cgul_rbtree__remove_node().

This method could be used, for example, if your code expires the oldest node in the tree, and you want to force n to be the next node to expire.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	n	node

See also

cgul_rbtree__set_youngest()

Referenced by cgul_rbtree_cxx::set_oldest().

cgul_rbtree__get_youngest()

CGUL_EXPORT cgul_rbtree_node_t cgul_rbtree__get_youngest	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t
	)

Return the youngest node according to chronological order (i.e., the order in which the nodes are inserted). This operation is O(1). If the tree is empty, NULL is returned. This class does not have to search the tree in order to find the youngest node because it efficiently keeps a direct pointer to the youngest node up to date.

The following example shows how to iterate over the entire tree in reverse chronological order:

    cgul_rbtree_node_t n = cgul_rbtree__get_youngest(cex, t);
    for ( ; n ; n = cgul_rbtree_node__get_older(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance

Returns

youngest node

See also

cgul_rbtree_node__get_older()

Referenced by cgul_rbtree_cxx::get_youngest().

cgul_rbtree__set_youngest()

CGUL_EXPORT void cgul_rbtree__set_youngest	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree_node_t	n
	)

Set the youngest node in the tree to be n. Calling this method has the potential to confuse iterators and should be handled with roughly the same level of caution as calling cgul_rbtree__remove_node().

This method could be used, for example, if your code expires the least-recently used (LRU) node. By calling cgul_rbtree__set_youngest() each time a node is used, the least-recently used node will be the oldest node in the tree.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	n	node

See also

cgul_rbtree__set_oldest()

Referenced by cgul_rbtree_cxx::set_youngest().

cgul_rbtree__remove()

CGUL_EXPORT int cgul_rbtree__remove	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		const void *	key_in,
		void **	key_out,
		void **	value_out
	)

Remove the node in t associated with key_in. The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL. This method returns 1 if the node was removed; it returns 0 otherwise.

It is almost always a mistake to naively call this method while iterating over the tree. See cgul_rbtree__remove_node() for details.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	key_in	key associated with the node to be removed
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns

whether the node was removed

Referenced by cgul_rbtree_cxx::remove().

cgul_rbtree__remove_node()

CGUL_EXPORT void cgul_rbtree__remove_node	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree_node_t	n,
		void **	key_out,
		void **	value_out
	)

Remove node from the tree t. The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL.

There is no speed advantage to using this method instead of cgul_rbtree__remove(). The reason is that removing a node has the potential to unbalance the tree requiring the code to descend the tree even though we already have the node in hand.

It is almost always a mistake to naively call this method while iterating over the tree. The problem is that calling this method invalidates the node making it impossible to call cgul_rbtree_node__get_next() afterward. The solution is simple. Just call cgul_rbtree_node__get_next() before calling this method:

    curr = cgul_rbtree__find(&local, t, key);
    for ( ; curr ; curr = next) {
        next = cgul_rbtree_node__get_next(&local, curr);
        cgul_rbtree__remove_node(&local,
                                 t,
                                 curr,
                                 &key_out,
                                 &value_out);
        free(key_out);
        free(value_out);
    }

Alternatively, you can use cgul_rbtree__remove_range(), cgul_rbtree__traverse(), or cgul_rbtree__traverse_range().

If you use one of the traversal methods, it is safe to call this method naively. For example, if your tree stores cgul_string objects for both its keys and values, another way to remove nodes is as follows:

    static int
    remove_node_cb(cgul_rbtree_t t,
                   cgul_rbtree_node_t node,
                   void* data)
    {
        cgul_string_t key = NULL;
        cgul_string_t value = NULL;
        cgul_exception_t local = NULL;
        cgul_rbtree__remove_node(&local,
                                 t,
                                 node,
                                 (void**)&key,
                                 (void**)&value);
        cgul_string__delete(key);
        cgul_string__delete(value);
        return 1;
    }

    first = cgul_rbtree__find(&local, t, key1);
    last = cgul_rbtree__find(&local, t, key2);
    if (first && last) {
        cgul_rbtree__traverse_range(&local,
                                    t,
                                    first,
                                    last,
                                    &remove_node_cb,
                                    NULL);
    }

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	n	node to be removed
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Referenced by cgul_rbtree_cxx::remove_node().

cgul_rbtree__remove_at()

CGUL_EXPORT int cgul_rbtree__remove_at	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		unsigned long int	index,
		void **	key_out,
		void **	value_out
	)

This method lets you remove a node based on its sorted order index. If the index is out of bounds, 0 is returned; otherwise 1 is returned. If you are interested in getting your hands on the key and value pointers stored in the node that is to be removed, they will be returned in key_out and value_out if you pass in pointers that are not NULL. index is zero-based.

This method throws an exception if t was not created with cguil_rbtree__new_with_indexing().

It is almost always a mistake to naively call this method while iterating over the tree. See cgul_rbtree__remove_node() for details.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	index	index of the sorted key associated with the node to be removed
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns

whether the node was removed

Referenced by cgul_rbtree_cxx::remove_at().

cgul_rbtree__remove_front()

CGUL_EXPORT int cgul_rbtree__remove_front	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		void **	key_out,
		void **	value_out
	)

As with all remove operations, cgul_rbtree__remove_front() has to descend the tree making sure the tree is balanced for the removal. The performance advantage to using this method is that it does not have to call the comparison function to decide whether it should take the right or left child of each node. It knows to always take the left child.

The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns

whether the node was removed

Referenced by cgul_rbtree_cxx::remove_front().

cgul_rbtree__remove_back()

CGUL_EXPORT int cgul_rbtree__remove_back	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		void **	key_out,
		void **	value_out
	)

As with all remove operations, cgul_rbtree__remove_back() has to descend the tree making sure the tree is balanced for the removal. The performance advantage to using this method is that it does not have to call the comparison function to decide whether it should take the right or left child of each node. It knows to always take the right child.

The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns

whether the node was removed

Referenced by cgul_rbtree_cxx::remove_back().

cgul_rbtree__remove_range()

CGUL_EXPORT int cgul_rbtree__remove_range	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree_node_t	first,
		cgul_rbtree_node_t	last,
		cgul_cache_t	keys_cache,
		cgul_cache_t	values_cache
	)

This method removes nodes in the range first (inclusive) to last (inclusive). Strictly as a convenience, this method is an exception to the rule that cgul containers never free keys or values. If you pass in keys_cache or values_cache instances that are not NULL, the keys or values will be put back on their respective caches.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	first	first node in range
[in]	last	last node in range
[in]	keys_cache	keys cache
[in]	values_cache	values cache

Returns

whether any nodes were removed.

See also

cgul_cache__get_freer()

Referenced by cgul_rbtree_cxx::remove_range().

cgul_rbtree__clear()

CGUL_EXPORT void cgul_rbtree__clear	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_cache_t	keys_cache,
		cgul_cache_t	values_cache
	)

This method clears the tree by removing each node individually. Strictly as a convenience, this method is an exception to the rule that cgul containers never free keys or values. If you pass in keys_cache or values_cache instances that are not NULL, the keys or values will be put back on their respective caches.

Another easy way to clear your tree is to just keep removing nodes from the front of the tree freeing the key/value pairs as you go:

    void* key = NULL;
    void* value = NULL;
    while (cgul_rbtree__remove_front(&local, tree, &key, &value)) {
        free(key);
        free(value);
    }

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	keys_cache	keys cache
[in]	values_cache	values cache

See also

cgul_rbtree__remove_range

cgul_cache__get_freer()

Referenced by cgul_rbtree_cxx::clear().

cgul_rbtree__get_size()

CGUL_EXPORT unsigned long int cgul_rbtree__get_size	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t
	)

Return the total number of elements stored in t.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance

Returns

size of the tree

Referenced by cgul_rbtree_cxx::get_size().

cgul_rbtree__is_ok()

CGUL_EXPORT int cgul_rbtree__is_ok	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t
	)

This function performs a basic sanity check on the tree and returns 1 if the tree passes and 0 if the tree fails. For now, it checks to see that there are never two red nodes without at least one intervening black node. It also checks to make sure that the black depth of all nodes are within one level of each other. There are many unbalanced trees that satisfy this criteria however.

Parameters

[in]	cex	c-style exception
[in]	t	cgul_rbtree instance

Returns

1 if passed basic sanity check; otherwise, 0

Referenced by cgul_rbtree_cxx::is_ok().

cgul_rbtree__swap()

CGUL_EXPORT void cgul_rbtree__swap	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t1,
		cgul_rbtree_t	t2
	)

Swap the underlying data for t1 and t2. For large trees, this should be much faster than trying to do the same thing using removes and inserts.

Parameters

[in]	cex	c-style exception
[in]	t1	first cgul_rbtree instance
[in]	t2	second cgul_rbtree instance

Referenced by cgul_rbtree_cxx::swap().

cgul_rbtree__foldl_keys()

CGUL_EXPORT void cgul_rbtree__foldl_keys	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree__fold_key_t	f,
		void *	data
	)

This method performs a left fold of the tree t with the combining function f. f is called once for each key in the tree starting at the front of the tree and iterating forward to the end of the tree.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_rbtree__foldr_keys()

CGUL_EXPORT void cgul_rbtree__foldr_keys	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree__fold_key_t	f,
		void *	data
	)

This method performs a right fold of the tree t with the combining function f. f is called once for each key in the tree starting at the back of the tree and iterating backward to the front of the tree.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_rbtree__foldl_values()

CGUL_EXPORT void cgul_rbtree__foldl_values	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree__fold_value_t	f,
		void *	data
	)

This method performs a left fold of the tree t with the combining function f. f is called once for each value in the tree starting at the front of the tree and iterating forward to the end of the tree.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current value. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_rbtree__foldr_values()

CGUL_EXPORT void cgul_rbtree__foldr_values	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree__fold_value_t	f,
		void *	data
	)

This method performs a right fold of the tree t with the combining function f. f is called once for each value in the tree starting at the back of the tree and iterating backward to the front of the tree.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current value. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_rbtree__foldl_pairs()

CGUL_EXPORT void cgul_rbtree__foldl_pairs	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree__fold_pair_t	f,
		void *	data
	)

This method performs a left fold of the tree t with the combining function f. f is called once for each key/value pair in the tree starting at the front of the tree and iterating forward to the end of the tree.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the current value. The fourth parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_rbtree__foldr_pairs()

CGUL_EXPORT void cgul_rbtree__foldr_pairs	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree__fold_pair_t	f,
		void *	data
	)

This method performs a right fold of the tree t with the combining function f. f is called once for each key/value pair in the tree starting at the back of the tree and iterating backward to the front of the tree.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the current value. The fourth parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	f	combining function
[in]	data	client data passed to f

cgul_rbtree__traverse()

CGUL_EXPORT void cgul_rbtree__traverse	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree__traverse_t	f,
		void *	data
	)

Traverse all nodes passing each node to the function f.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the rbtree t. The third paramenter passed into f is the node for this iteration. The fourth parameter passed into f is the client data data.

f is provided with a safe context in which it can remove the node that is passed into f by calling cgul_rbtree__remove_node().

f must return true after each iteration in order for the traversal to continue.

NOTE: It is not strictly necessary that you use cgul_rbtree__traverse() or cgul_rbtree__traverse_range() in order to iterate over the rbtree elements. In fact, I would recommend that you use cgul_rbtree_node__get_next() for most of your iteration needs. If you need to remove nodes though, you should probably use this method. If you look at this method's source however, you will see that the cgul_rbtree_node class provides all the public methods you need to safely remove nodes while you are iterating over the rbtree, but you do have to be careful.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	f	traversal callback function
[in]	data	passed to f

cgul_rbtree__traverse_range()

CGUL_EXPORT void cgul_rbtree__traverse_range	(	cgul_exception_t *	cex,
		cgul_rbtree_t	t,
		cgul_rbtree_node_t	first,
		cgul_rbtree_node_t	last,
		cgul_rbtree__traverse_t	f,
		void *	data
	)

Traverse all nodes starting with first (inclusive) and ending with last (inclusive) passing each node to the function f. If you know the first node, but are not sure of the last node, just use NULL as the last node. This will cause this method to iterate until it reaches the end of the rbtree. You can than have f return 0 when it determines that the last node has been reached.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the rbtree t. The third paramenter passed into f is the node for this iteration. The fourth parameter passed into f is the client data data.

f is provided with a safe context in which it can remove the node that is passed into f by calling cgul_rbtree__remove_node().

f must return true after each iteration in order for the traversal to continue.

If first is NULL, iteration starts at the beginning of the rbtree. If last is NULL, iteration stops at the end of the rbtree.

NOTE: It is not strictly necessary that you use cgul_rbtree__traverse() or cgul_rbtree__traverse_range() in order to iterate over the rbtree elements. In fact, I would recommend that you use cgul_rbtree_node__get_next() for most of your iteration needs. If you need to remove nodes though, you should probably use this method. If you look at this method's source however, you will see that the cgul_rbtree_node class provides all the public methods you need to safely remove nodes while you are iterating over the rbtree, but you do have to be careful.

Parameters

[in,out]	cex	c-style exception
[in]	t	cgul_rbtree instance
[in]	first	first node in range
[in]	last	last node in range
[in]	f	traversal callback function
[in]	data	client data passed to f

See also

cgul_rbtree__traverse