C++ bindings for cgul_rbtree More...

#include <cgul_rbtree_cxx.h>

Collaboration diagram for cgul_rbtree_cxx:

Public Types
typedef cgul_rbtree__compare_t	compare_t

typedef int(*	fold_key_t) (const void key, void data)

typedef int(*	fold_value_t) (void value, void data)

typedef int(*	fold_pair_t) (const void key, void value, void *data)

typedef int(*	traverse_t) (cgul_rbtree_cxx t, cgul_rbtree_node_cxx n, void *data)

Public Member Functions
	cgul_rbtree_cxx (compare_t compare, int with_indexing=0)

	cgul_rbtree_cxx (cgul_rbtree_t rhs)

virtual	~cgul_rbtree_cxx ()

virtual void	free_keys ()

virtual void	free_values ()

virtual unsigned long int	get_cache_size () const

virtual void	set_cache_size (unsigned long int size)

virtual unsigned long int	get_cache_reserve () const

virtual void	set_cache_reserve (unsigned long int reserve)

virtual int	is_empty () const

virtual int	insert (const void key, cgul_rbtree_node_cxx *n)

virtual cgul_rbtree_node_cxx *	find (const void *key)

virtual cgul_rbtree_node_cxx *	find_at (unsigned long int index)

virtual int	find_rank (const void key, unsigned long int rank)

virtual cgul_rbtree_node_cxx *	find_floor (const void *search_key)

virtual cgul_rbtree_node_cxx *	find_ceiling (const void *search_key)

virtual cgul_rbtree_node_cxx *	get_front () const

virtual cgul_rbtree_node_cxx *	get_back () const

virtual cgul_rbtree_node_cxx *	get_oldest () const

virtual void	set_oldest (cgul_rbtree_node_cxx *n)

virtual cgul_rbtree_node_cxx *	get_youngest () const

virtual void	set_youngest (cgul_rbtree_node_cxx *n)

virtual int	remove (const void key_in, void key_out, void *value_out)

virtual void	remove_node (cgul_rbtree_node_cxx n, void key_out, void *value_out)

virtual int	remove_at (unsigned long int index, void key_out, void value_out)

virtual int	remove_front (void key_out, void value_out)

virtual int	remove_back (void key_out, void value_out)

virtual int	remove_range (cgul_rbtree_node_cxx first, cgul_rbtree_node_cxx last, cgul_cache_cxx keys_cache=NULL, cgul_cache_cxx values_cache=NULL)

virtual void	clear (cgul_cache_cxx keys_cache, cgul_cache_cxx values_cache)

virtual unsigned long int	get_size () const

virtual int	is_ok () const

virtual void	swap (cgul_rbtree_cxx &rhs)

virtual void	foldl_keys (fold_key_t f, void *data)

virtual void	foldr_keys (fold_key_t f, void *data)

virtual void	foldl_values (fold_value_t f, void *data)

virtual void	foldr_values (fold_value_t f, void *data)

virtual void	foldl_pairs (fold_pair_t f, void *data)

virtual void	foldr_pairs (fold_pair_t f, void *data)

virtual void	traverse (traverse_t f, void *data)

virtual void	traverse_range (cgul_rbtree_node_cxx first, cgul_rbtree_node_cxx last, traverse_t f, void *data)

virtual cgul_rbtree_t	get_obj () const

virtual cgul_rbtree_t	take_obj ()

virtual void	set_obj (cgul_rbtree_t rhs)

Detailed Description

This class provides the C++ bindings for C cgul_rbtree objects. The main purpose of this class is to convert the C-style function calls and exception handling in cgul_rbtree into C++-style function calls and exception handling.

See also: cgul_rbtree_t

Member Typedef Documentation

§ compare_t

typedef cgul_rbtree__compare_t cgul_rbtree_cxx::compare_t

This typedef is the interface the client must define in order for cgul_rbtree_cxx to sort your keys as they are inserted.

§ fold_key_t

typedef int(* cgul_rbtree_cxx::fold_key_t) (const void *key, void *data)

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

    foldl_keys()
    foldr_keys()

Parameters

[in]	key	key
[in]	data	client data

Returns: whether to continue

§ fold_value_t

typedef int(* cgul_rbtree_cxx::fold_value_t) (void *value, void *data)

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

    foldl_values()
    foldr_values()

Parameters

[in]	value	value
[in]	data	client data

Returns: whether to continue

§ fold_pair_t

typedef int(* cgul_rbtree_cxx::fold_pair_t) (const void *key, void *value, void *data)

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

    foldl_pairs()
    foldr_pairs()

Parameters

[in]	key	key
[in]	value	value
[in]	data	client data

Returns: whether to continue

§ traverse_t

typedef int(* cgul_rbtree_cxx::traverse_t) (cgul_rbtree_cxx *t, cgul_rbtree_node_cxx *n, void *data)

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

    traverse()
    traverse_range()

Parameters

[in]	t	tree
[in]	n	node
[in]	data	client data

Returns: whether to continue

Constructor & Destructor Documentation

§ cgul_rbtree_cxx() [1/2]

cgul_rbtree_cxx::cgul_rbtree_cxx	(	compare_t	compare,
		int	with_indexing = `0`
	)

inline

Create a new cgul_rbtree_cxx object. compare is the comparison function that allows the tree to maintain its sorted order. The caller is responsible for arranging for delete to be called on the object. If memory cannot be allocated, an exception is thrown.

Be default with_indexing is false which means the ability to index into the tree as though it were an array will not be enabled. If with_indexing is set to true, each node will be larger containing two extra unsigned long values and will run about 15% slower.

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 traverse() method can be used to remove each node safely before calling delete on the object created.

Parameters

[in]	compare	comparison function
[in]	with_indexing	whether to enable indexing

References cgul_rbtree__new(), and cgul_rbtree__new_with_indexing().

§ cgul_rbtree_cxx() [2/2]

cgul_rbtree_cxx::cgul_rbtree_cxx ( cgul_rbtree_t rhs )

inline

Create a new cgul_rbtree_cxx object by wrapping an existing cgul_rbtree object.

Parameters

[in] rhs right-hand side

§ ~cgul_rbtree_cxx()

virtual cgul_rbtree_cxx::~cgul_rbtree_cxx ( )

inlinevirtual

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 clear() before calling this method in order to properly put the keys and values back on their respective cgul_cache_cxx objects (if cgul_cache_cxx objects are being used) before you delete the tree. If cgul_cache_cxx objects are not being used, the client needs to arrange some other mechanism to free the keys or values.

See also: free_keys(); free_values()

References cgul_rbtree__delete().

Member Function Documentation

§ free_keys()

virtual void cgul_rbtree_cxx::free_keys ( )

inlinevirtual

This method calls free() on all the keys in the tree. 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 delete because it otherwise invalidates the tree.

References cgul_rbtree__free_keys().

§ free_values()

virtual void cgul_rbtree_cxx::free_values ( )

inlinevirtual

This method calls free() on all the values in the tree. 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 delete because it otherwise invalidates the tree.

References cgul_rbtree__free_values().

§ get_cache_size()

virtual unsigned long int cgul_rbtree_cxx::get_cache_size ( ) const

inlinevirtual

Get the size of the cache of nodes.

Returns: size of the cache of nodes

References cgul_rbtree__get_cache_size().

§ set_cache_size()

virtual void cgul_rbtree_cxx::set_cache_size ( unsigned long int size )

inlinevirtual

Set the size of the cache of nodes.

For efficiency, the cgul_rbtree_cxx 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] size of the cache of nodes

References cgul_rbtree__set_cache_size().

§ get_cache_reserve()

virtual unsigned long int cgul_rbtree_cxx::get_cache_reserve ( ) const

inlinevirtual

Get the reserve limit of the cache of nodes.

Returns: reserve limit of the cache of nodes

References cgul_rbtree__get_cache_reserve().

§ set_cache_reserve()

virtual void cgul_rbtree_cxx::set_cache_reserve ( unsigned long int reserve )

inlinevirtual

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 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 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_cxx 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] reserve of the cache of nodes

See also: cgul_cache_cxx::set_reserve()

References cgul_rbtree__set_cache_reserve().

§ is_empty()

virtual int cgul_rbtree_cxx::is_empty ( ) const

inlinevirtual

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

Returns: whether the tree is empty

References cgul_rbtree__is_empty().

§ insert()

virtual int cgul_rbtree_cxx::insert	(	const void *	key,
		cgul_rbtree_node_cxx **	n
	)

inlinevirtual

Insert key into the tree. 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.

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_cxx::get_value() or cgul_rbtree_node_cxx::set_value() to get or set the value indexed by "key".

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

    cgul_string_cxx word;
    cgul_rbtree_node_cxx* n = NULL;

    if (t->insert(word.get_value(), &n)) {
        word.take_value();
        . . .
    } 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]	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

References cgul_rbtree__insert().

§ find()

virtual cgul_rbtree_node_cxx* cgul_rbtree_cxx::find ( const void * key )

inlinevirtual

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] key key

Returns: node associated with the key or NULL

References cgul_rbtree__find().

§ find_at()

virtual cgul_rbtree_node_cxx* cgul_rbtree_cxx::find_at ( unsigned long int index )

inlinevirtual

Find the node indexed by position. This lets you use a cgul_rbtree_cxx instances like you would an array. Indexing into cgul_rbtree_cxx 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 have ever feel the need to shift the elements of an array, this method is 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 the tree was not created with indexing enabled.

Parameters

[in] index index into sorted keys of node to return

Returns: node associated with index

See also: find_rank()

References cgul_rbtree__find_at().

§ find_rank()

virtual int cgul_rbtree_cxx::find_rank	(	const void *	key,
		unsigned long int *	rank
	)

inlinevirtual

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 find_at() in order to lookup key by index.

This method throws an exception if t was not created with indexing enabled.

Parameters

[in]	key	key
[out]	rank	rank of key

Returns: whether the key exists in the tree

See also: find_at()

References cgul_rbtree__find_rank().

§ find_floor()

virtual cgul_rbtree_node_cxx* cgul_rbtree_cxx::find_floor ( const void * search_key )

inlinevirtual

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] search_key search key

Returns: floor node or NULL

References cgul_rbtree__find_floor().

§ find_ceiling()

virtual cgul_rbtree_node_cxx* cgul_rbtree_cxx::find_ceiling ( const void * search_key )

inlinevirtual

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] search_key search key

Returns: ceiling node or NULL

References cgul_rbtree__find_ceiling().

§ get_front()

virtual cgul_rbtree_node_cxx* cgul_rbtree_cxx::get_front ( ) const

inlinevirtual

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_cxx* n = t->get_front();
    for ( ; n ; n = n->get_next()) {
        ...
    }

Returns: front node

References cgul_rbtree__get_front().

§ get_back()

virtual cgul_rbtree_node_cxx* cgul_rbtree_cxx::get_back ( ) const

inlinevirtual

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_cxx* n = t->get_back();
    for ( ; n ; n = n->get_prev()) {
        ...
    }

Returns: back node

References cgul_rbtree__get_back().

§ get_oldest()

virtual cgul_rbtree_node_cxx* cgul_rbtree_cxx::get_oldest ( ) const

inlinevirtual

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_cxx* n = t->get_oldest();
    for ( ; n ; n = n->get_younger()) {
        ...
    }

Returns: oldest node

See also: cgul_rbtree_node_cxx::get_younger()

References cgul_rbtree__get_oldest().

§ set_oldest()

virtual void cgul_rbtree_cxx::set_oldest ( cgul_rbtree_node_cxx * n )

inlinevirtual

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 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] n node

See also: set_youngest()

References cgul_rbtree__set_oldest().

§ get_youngest()

virtual cgul_rbtree_node_cxx* cgul_rbtree_cxx::get_youngest ( ) const

inlinevirtual

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_cxx* n = t->get_youngest();
    for ( ; n ; n = n->get_older()) {
        ...
    }

Returns: youngest node

See also: cgul_rbtree_node_cxx::get_older()

References cgul_rbtree__get_youngest().

§ set_youngest()

virtual void cgul_rbtree_cxx::set_youngest ( cgul_rbtree_node_cxx * n )

inlinevirtual

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

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

Parameters

[in] n node

See also: set_oldest()

References cgul_rbtree__set_youngest().

§ remove()

virtual int cgul_rbtree_cxx::remove	(	const void *	key_in,
		void **	key_out,
		void **	value_out
	)

inlinevirtual

Remove the node associated with key. 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 remove_node() for details.

Parameters

[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

References cgul_rbtree__remove().

§ remove_node()

virtual void cgul_rbtree_cxx::remove_node	(	cgul_rbtree_node_cxx *	n,
		void **	key_out,
		void **	value_out
	)

inlinevirtual

Remove node from the tree. 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 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 node->get_next() afterward. The solution is simple. Just call node->get_next() before calling this method:

    for (curr = t->find(key) ; curr ; curr = next) {
        next = curr->get_next();
        t->remove_node(curr, &key_out, &value_out);
        free(key_out);
        free(value_out);
    }

Alternatively, you can use remove_range(), traverse(), or 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_cxx* objects for both its keys and values, another way to remove nodes is as follows:

    static int
    remove_node_cb(cgul_rbtree_cxx* t,
                   cgul_rbtree_node_cxx* node,
                   void* data)
    {
        cgul_string_cxx* key = NULL;
        cgul_string_cxx* value = NULL;
        t->remove_node(node, (void**)&key, (void**)&value);
        delete key;
        delete value;
        return 1;
    }

    cgul_rbtree_node_cxx* first = t->find(key1);
    cgul_rbtree_node_cxx* last = t->find(key2);
    if (first && last) {
        t->traverse_range(first, last, &remove_node_cb, NULL);
    }

Parameters

[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

References cgul_rbtree__remove_node().

§ remove_at()

virtual int cgul_rbtree_cxx::remove_at	(	unsigned long int	index,
		void **	key_out,
		void **	value_out
	)

inlinevirtual

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 the tree was not created with indexing enabled.

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

Parameters

[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

References cgul_rbtree__remove_at().

§ remove_front()

virtual int cgul_rbtree_cxx::remove_front	(	void **	key_out,
		void **	value_out
	)

inlinevirtual

As with all remove operations, 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.

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.

Parameters

[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

References cgul_rbtree__remove_front().

§ remove_back()

virtual int cgul_rbtree_cxx::remove_back	(	void **	key_out,
		void **	value_out
	)

inlinevirtual

As with all remove operations, 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.

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.

Parameters

[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

References cgul_rbtree__remove_back().

§ remove_range()

virtual int cgul_rbtree_cxx::remove_range	(	cgul_rbtree_node_cxx *	first,
		cgul_rbtree_node_cxx *	last,
		cgul_cache_cxx *	keys_cache = `NULL`,
		cgul_cache_cxx *	values_cache = `NULL`
	)

inlinevirtual

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]	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_cxx::get_freer()

References cgul_rbtree__remove_range().

§ clear()

virtual void cgul_rbtree_cxx::clear	(	cgul_cache_cxx *	keys_cache,
		cgul_cache_cxx *	values_cache
	)

inlinevirtual

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.

Parameters

[in]	keys_cache	keys cache
[in]	values_cache	values cache

See also: remove_range(); cgul_cache_cxx::get_freer()

References cgul_rbtree__clear(), and cgul_cache_cxx::get_obj().

§ get_size()

virtual unsigned long int cgul_rbtree_cxx::get_size ( ) const

inlinevirtual

Return the total number of elements stored in the tree.

Returns: size of the tree

References cgul_rbtree__get_size().

§ is_ok()

virtual int cgul_rbtree_cxx::is_ok ( ) const

inlinevirtual

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.

Returns: 1 if passed basic sanity check; otherwise, 0

References cgul_rbtree__is_ok().

§ swap()

virtual void cgul_rbtree_cxx::swap ( cgul_rbtree_cxx & rhs )

inlinevirtual

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

Parameters

[in] rhs right-hand side

References cgul_rbtree__swap().

§ foldl_keys()

virtual void cgul_rbtree_cxx::foldl_keys	(	fold_key_t	f,
		void *	data
	)

inlinevirtual

This method performs a left fold of the tree 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 current key. The second 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_rbtree__get_front(), cgul_rbtree_node__get_key(), and cgul_rbtree_node__get_next().

§ foldr_keys()

virtual void cgul_rbtree_cxx::foldr_keys	(	fold_key_t	f,
		void *	data
	)

inlinevirtual

This method performs a right fold of the tree 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 current key. The second 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_rbtree__get_back(), cgul_rbtree_node__get_key(), and cgul_rbtree_node__get_prev().

§ foldl_values()

virtual void cgul_rbtree_cxx::foldl_values	(	fold_value_t	f,
		void *	data
	)

inlinevirtual

This method performs a left fold of the tree 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 current value. The second 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_rbtree__get_front(), cgul_rbtree_node__get_next(), and cgul_rbtree_node__get_value().

§ foldr_values()

virtual void cgul_rbtree_cxx::foldr_values	(	fold_value_t	f,
		void *	data
	)

inlinevirtual

This method performs a right fold of the tree 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 current value. The second 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_rbtree__get_back(), cgul_rbtree_node__get_prev(), and cgul_rbtree_node__get_value().

§ foldl_pairs()

virtual void cgul_rbtree_cxx::foldl_pairs	(	fold_pair_t	f,
		void *	data
	)

inlinevirtual

This method performs a left fold of the tree 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 current key. 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_rbtree__get_front(), cgul_rbtree_node__get_key(), cgul_rbtree_node__get_next(), and cgul_rbtree_node__get_value().

§ foldr_pairs()

virtual void cgul_rbtree_cxx::foldr_pairs	(	fold_pair_t	f,
		void *	data
	)

inlinevirtual

This method performs a right fold of the tree 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 current key. 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_rbtree__get_back(), cgul_rbtree_node__get_key(), cgul_rbtree_node__get_prev(), and cgul_rbtree_node__get_value().

§ traverse()

virtual void cgul_rbtree_cxx::traverse	(	traverse_t	f,
		void *	data
	)

inlinevirtual

Traverse all nodes passing each node to the function f.

The first parameter passed into f is the tree this. The second paramenter passed into f is the node for this iteration. The third 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 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 traverse() or traverse_range() in order to iterate over the tree elements. In fact, I would recommend that you use cgul_rbtree_node_cxx::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_cxx 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]	f	traversal callback function
[in]	data	client data passed to `f`

See also: traverse_range()

References traverse_range().

§ traverse_range()

virtual void cgul_rbtree_cxx::traverse_range	(	cgul_rbtree_node_cxx *	first,
		cgul_rbtree_node_cxx *	last,
		traverse_t	f,
		void *	data
	)

inlinevirtual

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 tree. 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 tree this. The second paramenter passed into f is the node for this iteration. The third 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 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 tree. If last is NULL, iteration stops at the end of the tree.

NOTE: It is not strictly necessary that you use traverse() or traverse_range() in order to iterate over the tree elements. In fact, I would recommend that you use cgul_rbtree_node_cxx::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_cxx class provides all the public methods you need to safely remove nodes while you are iterating over the tree, but you do have to be careful.

Parameters

[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: traverse()

References cgul_rbtree__get_back(), cgul_rbtree__get_front(), and cgul_rbtree_node__get_next().

Referenced by traverse().

§ get_obj()

virtual cgul_rbtree_t cgul_rbtree_cxx::get_obj ( ) const

inlinevirtual

Get the underlying cgul_rbtree object.

Returns: underlying object

Referenced by cgul_stanza_cxx::clear_tree(), cgul_stanza_cxx::lookup_tree(), cgul_stanza_cxx::set_allowed_keys(), and cgul_stanza_cxx::set_mandatory_keys().

§ take_obj()

virtual cgul_rbtree_t cgul_rbtree_cxx::take_obj ( )

inlinevirtual

Take the underlying cgul_rbtree object. This means the underlying object will not be deleted when the wrapper goes out of scope. Also, because you have taken the underlying object, no other methods should be called on this wrapper's instance. Lastly, after taking the underlying object, it is the caller's responsibility to delete the underlying object by calling cgul_rbtree__delete().

Returns: underlying object

§ set_obj()

virtual void cgul_rbtree_cxx::set_obj ( cgul_rbtree_t rhs )

inlinevirtual

Set the new underlying object to rhs. This causes the old underlying object to be deleted which invalidates any outstanding pointers to or iterators for the old underlying object.

This instance takes ownership of rhs which means rhs will be automatically deleted when the C++ wrapper is deleted. To prevent automatic deletion of rhs, call take_obj() when the C++ wrapper is no longer needed.

Parameters

[in] rhs right-hand side

References cgul_rbtree__delete().

The documentation for this class was generated from the following file:

cgul_rbtree_cxx.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

§ compare_t

§ fold_key_t

§ fold_value_t

§ fold_pair_t

§ traverse_t

Constructor & Destructor Documentation

§ cgul_rbtree_cxx() [1/2]

§ cgul_rbtree_cxx() [2/2]

§ ~cgul_rbtree_cxx()

Member Function Documentation

§ free_keys()

§ free_values()

§ get_cache_size()

§ set_cache_size()

§ get_cache_reserve()

§ set_cache_reserve()

§ is_empty()

§ insert()

§ find()

§ find_at()

§ find_rank()

§ find_floor()

§ find_ceiling()

§ get_front()

§ get_back()

§ get_oldest()

§ set_oldest()

§ get_youngest()

§ set_youngest()

§ remove()

§ remove_node()

§ remove_at()

§ remove_front()

§ remove_back()

§ remove_range()

§ clear()

§ get_size()

§ is_ok()

§ swap()

§ foldl_keys()

§ foldr_keys()

§ foldl_values()

§ foldr_values()

§ foldl_pairs()

§ foldr_pairs()

§ traverse()

§ traverse_range()

§ get_obj()

§ take_obj()

§ set_obj()