C++ bindings for cgul_list More...

#include <cgul_list_cxx.h>

Collaboration diagram for cgul_list_cxx:

Public Types
typedef cgul_list__compare_t	compare_t

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

typedef int(*	traverse_t) (cgul_list_cxx l, cgul_list_node_cxx n, void *data)

Public Member Functions
	cgul_list_cxx ()

	cgul_list_cxx (cgul_list_t rhs)

virtual	~cgul_list_cxx ()

virtual void	free_values ()

virtual unsigned long int	get_cache_size () const

virtual void	set_cache_size (unsigned long int size)

virtual int	is_empty () const

virtual cgul_list_node_cxx *	get_front () const

virtual cgul_list_node_cxx *	get_back () const

virtual cgul_list_node_cxx *	push_front (const void *value)

virtual void *	pop_front ()

virtual cgul_list_node_cxx *	push_back (const void *value)

virtual void *	pop_back ()

virtual void	move_before_node (cgul_list_node_cxx n1, cgul_list_node_cxx n2)

virtual void	move_after_node (cgul_list_node_cxx n1, cgul_list_node_cxx n2)

virtual cgul_list_node_cxx *	insert_before_node (cgul_list_node_cxx n, const void value)

virtual cgul_list_node_cxx *	insert_after_node (cgul_list_node_cxx n, const void value)

virtual cgul_list_node_cxx *	insert_sorted (const void *value, compare_t f)

virtual void	sort (compare_t f)

virtual void	merge (cgul_list_cxx &l, compare_t f)

virtual void	clear (cgul_cache_cxx *values_cache)

virtual void	remove_node (cgul_list_node_cxx n, void *value_out)

virtual void	remove_range (cgul_list_node_cxx n_begin, cgul_list_node_cxx n_end, cgul_cache_cxx *values_cache)

virtual int	remove_value (const void value, cgul_cache_cxx values_cache)

virtual unsigned long int	get_size () const

virtual void	swap (cgul_list_cxx &rhs)

virtual void	foldl (fold_t f, void *data)

virtual void	foldr (fold_t f, void *data)

virtual void	traverse (traverse_t f, void *data)

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

virtual cgul_list_t	get_obj () const

virtual cgul_list_t	take_obj ()

virtual void	set_obj (cgul_list_t rhs)

Detailed Description

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

Member Typedef Documentation

§ compare_t

typedef cgul_list__compare_t cgul_list_cxx::compare_t

This typedef is the interface for the comparison function used by sort() and insert_sorted().

§ fold_t

typedef int(* cgul_list_cxx::fold_t) (void *value, void *data)

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

    foldl()
    foldr()

Parameters

[in]	value	value
[in]	data	client data

Returns: whether to continue

§ traverse_t

typedef int(* cgul_list_cxx::traverse_t) (cgul_list_cxx *l, cgul_list_node_cxx *n, void *data)

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

    traverse()
    traverse_range()

Parameters

[in]	l	list
[in]	n	node
[in]	data	client data

Returns: whether to continue

Constructor & Destructor Documentation

§ cgul_list_cxx() [1/2]

cgul_list_cxx::cgul_list_cxx ( )

inline

Create a new cgul_list_cxx object. If memory cannot be allocated, an exception is thrown.

Returns: new cgul_list_cxx instance

References cgul_list__new().

Referenced by set_obj().

§ cgul_list_cxx() [2/2]

cgul_list_cxx::cgul_list_cxx ( cgul_list_t rhs )

inline

Create a new cgul_list_cxx object by wrapping an existing cgul_list object.

Parameters

[in] rhs right-hand side

§ ~cgul_list_cxx()

virtual cgul_list_cxx::~cgul_list_cxx ( )

inlinevirtual

This method frees all internally allocated memory. Do not try to access this instance after calling this method.

See also: free_values()

References cgul_list__delete().

Member Function Documentation

§ free_values()

virtual void cgul_list_cxx::free_values ( )

inlinevirtual

This method calls free() on all the values in the list. 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 list.

References cgul_list__free_values().

§ get_cache_size()

virtual unsigned long int cgul_list_cxx::get_cache_size ( ) const

inlinevirtual

Get the size of the cache of nodes.

Returns: size of the cache of nodes

References cgul_list__get_cache_size().

§ set_cache_size()

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

inlinevirtual

Set the size of the cache of nodes.

For efficiency, the cgul_list_cxx 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 size to 0. 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_list__set_cache_size().

§ is_empty()

virtual int cgul_list_cxx::is_empty ( ) const

inlinevirtual

Return true if the list is empty.

Returns: whether the list is empty

References cgul_list__is_empty().

§ get_front()

virtual cgul_list_node_cxx* cgul_list_cxx::get_front ( ) const

inlinevirtual

Return the first element on the list. You can use cgul_list_node_cxx::get_next() to iterate over the list by starting with the value returned by this method. If the list is empty, NULL is returned.

Returns: first element

References cgul_list__get_front().

§ get_back()

virtual cgul_list_node_cxx* cgul_list_cxx::get_back ( ) const

inlinevirtual

Return the last element on the list. You can use cgul_list_node_cxx::get_prev() to iterate over the list by starting with the value returned by this method. If the list is empty, NULL is returned.

Returns: last element

References cgul_list__get_back().

§ push_front()

virtual cgul_list_node_cxx* cgul_list_cxx::push_front ( const void * value )

inlinevirtual

Insert value at the front of the list. If successful, the inserted node is returned; otherwise, an exception is thrown.

Parameters

[in] value value to add at the front of the list

Returns: node that holds value

References cgul_list__push_front().

§ pop_front()

virtual void* cgul_list_cxx::pop_front ( )

inlinevirtual

Remove the first node from the list. Return the value that was stored in node. If the list is empty, NULL is returned.

Returns: value that was stored in the front node

References cgul_list__pop_front().

§ push_back()

virtual cgul_list_node_cxx* cgul_list_cxx::push_back ( const void * value )

inlinevirtual

Insert value at the back of the list. If successful, the return value is the inserted node; otherwise, an exception is thrown.

Parameters

[in] value value to add at the back of the list

Returns: node that holds value

References cgul_list__push_back().

§ pop_back()

virtual void* cgul_list_cxx::pop_back ( )

inlinevirtual

Remove the last value from the list. Return the value that was stored in node. If the list is empty, NULL is returned.

Returns: value that was stored in the back node

References cgul_list__pop_back().

§ move_before_node()

virtual void cgul_list_cxx::move_before_node	(	cgul_list_node_cxx *	n1,
		cgul_list_node_cxx *	n2
	)

inlinevirtual

Move n2 before n1 in the list. If n1 == NULL, move n2 to before the NULL at the end of the list. n1 and n2 must both already exist on the same list.

For example, to rotate the list wrapping the first element around to the back of the list, do the following:

    lst.move_before_node(NULL, lst.get_front());

Parameters

[in]	n1	insert before this node
[in]	n2	node to insert

References cgul_list__move_before_node().

§ move_after_node()

virtual void cgul_list_cxx::move_after_node	(	cgul_list_node_cxx *	n1,
		cgul_list_node_cxx *	n2
	)

inlinevirtual

Move n2 after n1 in the list. If n1 == NULL, move n2 to after the NULL at the beginning of the list. n1 and n2 must both already exist on the same list.

For example, to rotate the list wrapping the last element around to the front of the list, do the following:

    lst.move_after_node(NULL, lst.get_back());

Parameters

[in]	n1	insert after this node
[in]	n2	node to insert

References cgul_list__move_after_node().

§ insert_before_node()

virtual cgul_list_node_cxx* cgul_list_cxx::insert_before_node	(	cgul_list_node_cxx *	n,
		const void *	value
	)

inlinevirtual

Insert value before node n in the list. If n == NULL, then insert before the NULL at the end of the list. If successful, the return value is the inserted node; otherwise, an exception is thrown.

Parameters

[in]	n	inserting before this node
[in]	value	value to insert

Returns: node that holds value

References cgul_list__insert_before_node().

§ insert_after_node()

virtual cgul_list_node_cxx* cgul_list_cxx::insert_after_node	(	cgul_list_node_cxx *	n,
		const void *	value
	)

inlinevirtual

Insert value after node n in the list. If n == NULL, then insert after the NULL at the beginning of the list. If successful, the return value is the inserted node; otherwise, an exception is thrown.

Parameters

[in]	n	inserting after this node
[in]	value	value to insert

Returns: node that holds value

References cgul_list__insert_after_node().

§ insert_sorted()

virtual cgul_list_node_cxx* cgul_list_cxx::insert_sorted	(	const void *	value,
		compare_t	f
	)

inlinevirtual

Insert value into the list in sort order as determined by the comparison function f. If successful, the return value is the inserted node; otherwise, an exception is thrown.

This method assumes the list is already sorted. If not, call sort() before calling this method.

This method is O(N). Thus, this method is more efficient for a single insert on an already sorted list than sort() which is O(N log N), but calling this method to perform N inserts is O(N^2) which is not as efficient as N calls to push_back() followed by a single call to sort().

If you need to constantly maintain a sorted list, cgul_rbtree_cxx or cgul_multimap_cxx are usually better solutions.

Parameters

[in]	value	value to insert
[in]	f	comparison function

Returns: node that holds value

References cgul_list__insert_sorted().

§ sort()

virtual void cgul_list_cxx::sort ( compare_t f )

inlinevirtual

Sort the listusing the comparison function f.

This method uses merge sort. The main advantage of this method over cgul_merge_sort() is that it can sort the list in-line whereas cgul_merge_sort needs an extra copy of the list.

This method is O(N log N). Thus, this method is more efficient when sorting a large number of items, but insert_sorted() is O(N) so it is faster when inserting just one item into an already sorted list.

If you need to constantly maintain a sorted list, cgul_rbtree_cxx or cgul_multimap_cxx are usually better solutions.

If you need to merge two sorted lists, merge() is usually a better solution.

Parameters

[in] f comparison function

See also: cgul_merge_sort; cgul_list_cxx::merge

References cgul_list__sort().

§ merge()

virtual void cgul_list_cxx::merge	(	cgul_list_cxx &	l,
		compare_t	f
	)

inlinevirtual

Merge the sorted list l with this list. The sort order is determined by the comparison function f. When this method returns, all the nodes will be in this list and l will be empty.

This method is extremely efficient doing its job in a single pass, i.e., O(N). This method should be the first thing that comes to mind when you need to add a small, unsorted list to a large, sorted list. In this case, sort the small list using cgul_list__sort() before calling this method to merge the small list with the large list.

Parameters

[in,out]	l	list to merge into this list
[in]	f	comparison function

References cgul_list__merge(), and get_obj().

§ clear()

virtual void cgul_list_cxx::clear ( cgul_cache_cxx * values_cache )

inlinevirtual

Remove all elements from the list.

Strictly as a convenience, this method is an exception to the rule that cgul containers never free values. If you pass in a values_cache_cxx instance that is not NULL, the values will be put back on their cache.

Parameters

[in] values_cache values cache

See also: cgul_cache_cxx::get_freer()

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

§ remove_node()

virtual void cgul_list_cxx::remove_node	(	cgul_list_node_cxx *	n,
		void **	value_out
	)

inlinevirtual

Remove the node n from the list. If value_out is not NULL, the value held by n is returned in *value_out.

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:

    curr = l->get_front();
    for ( ; curr ; curr = next) {
        next = curr->get_next();
        l->remove_node(curr, &value_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 its values, another way to remove nodes is as follows:

    static int
    remove_node_cb(cgul_list_cxx* l,
                   cgul_list_node_cxx* n,
                   void* data)
    {
        cgul_string_cxx* value_out = NULL;
        l->remove_node(n, (void**)&value_out);
        delete value_out;
        return 1;
    }

    l->traverse(&remove_node_cb, NULL);

Parameters

[in]	n	node to remove
[out]	value_out	value

References cgul_list__remove_node().

§ remove_range()

virtual void cgul_list_cxx::remove_range	(	cgul_list_node_cxx *	n_begin,
		cgul_list_node_cxx *	n_end,
		cgul_cache_cxx *	values_cache
	)

inlinevirtual

Remove the nodes between n_begin (inclusive) and n_end (inclusive). If n_begin is NULL, start at the front of the list. If n_end is NULL or is not found, continue removing until the end of the list.

Strictly as a convenience, this method is an exception to the rule that cgul containers never free values. If you pass in a values_cache_cxx instance that is not NULL, the values will be put back on their cache.

Parameters

[in]	n_begin	begin removing with and including this node
[in]	n_end	end removing with and including this node
[in]	values_cache	values cache

See also: cgul_cache_cxx::get_freer()

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

§ remove_value()

virtual int cgul_list_cxx::remove_value	(	const void *	value,
		cgul_cache_cxx *	values_cache
	)

inlinevirtual

Remove all the nodes that have value for their value. If at least one node was removed, this method returns 1; otherwise, it returns 0.

Strictly as a convenience, this method is an exception to the rule that cgul containers never free values. If you pass in a values_cache_cxx instance that is not NULL, the values will be put back on their cache.

Parameters

[in]	value	values to remove from the list
[in]	values_cache	values cache

See also: cgul_cache_cxx::get_freer()

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

§ get_size()

virtual unsigned long int cgul_list_cxx::get_size ( ) const

inlinevirtual

Return the size of the list, i.e., the number of elements in the list.

Returns: size of the list

References cgul_list__get_size().

§ swap()

virtual void cgul_list_cxx::swap ( cgul_list_cxx & rhs )

inlinevirtual

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

Parameters

[in] rhs right-hand side

References cgul_list__swap().

§ foldl()

virtual void cgul_list_cxx::foldl	(	fold_t	f,
		void *	data
	)

inlinevirtual

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

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_list__get_front(), cgul_list_node__get_next(), and cgul_list_node__get_value().

§ foldr()

virtual void cgul_list_cxx::foldr	(	fold_t	f,
		void *	data
	)

inlinevirtual

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

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_list__get_back(), cgul_list_node__get_prev(), and cgul_list_node__get_value().

§ traverse()

virtual void cgul_list_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 list 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 list elements. In fact, I would recommend that you use cgul_list_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_list_node_cxx class provides all the public methods you need to safely remove nodes while you are iterating over the list, 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_list_cxx::traverse_range	(	cgul_list_node_cxx *	first,
		cgul_list_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 list. 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 list 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 list. If last is NULL, iteration stops at the end of the list.

NOTE: It is not strictly necessary that you use traverse() or traverse_range() in order to iterate over the list elements. In fact, I would recommend that you use cgul_list_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_list_node_cxx class provides all the public methods you need to safely remove nodes while you are iterating over the list, 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_list__get_back(), cgul_list__get_front(), and cgul_list_node__get_next().

Referenced by traverse().

§ get_obj()

virtual cgul_list_t cgul_list_cxx::get_obj ( ) const

inlinevirtual

Get the underlying cgul_list object.

Returns: underlying object

Referenced by merge().

§ take_obj()

virtual cgul_list_t cgul_list_cxx::take_obj ( )

inlinevirtual

Take the underlying cgul_list 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_list__delete().

Returns: underlying object

§ set_obj()

virtual void cgul_list_cxx::set_obj ( cgul_list_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_list__delete(), and cgul_list_cxx().

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

cgul_list_cxx.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

§ compare_t

§ fold_t

§ traverse_t

Constructor & Destructor Documentation

§ cgul_list_cxx() [1/2]

§ cgul_list_cxx() [2/2]

§ ~cgul_list_cxx()

Member Function Documentation

§ free_values()

§ get_cache_size()

§ set_cache_size()

§ is_empty()

§ get_front()

§ get_back()

§ push_front()

§ pop_front()

§ push_back()

§ pop_back()

§ move_before_node()

§ move_after_node()

§ insert_before_node()

§ insert_after_node()

§ insert_sorted()

§ sort()

§ merge()

§ clear()

§ remove_node()

§ remove_range()

§ remove_value()

§ get_size()

§ swap()

§ foldl()

§ foldr()

§ traverse()

§ traverse_range()

§ get_obj()

§ take_obj()

§ set_obj()