linked list implementation More...

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

Include dependency graph for cgul_list.h:

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

Typedefs
typedef typedefCGUL_BEGIN_C struct cgul_list *	cgul_list_t

typedef int(*	cgul_list__compare_t) (const void value1, const void value2)

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

typedef int(*	cgul_list__traverse_t) (cgul_exception_t cex, cgul_list_t l, cgul_list_node_t n, void data)

Functions
CGUL_EXPORT cgul_list_t	cgul_list__new (cgul_exception_t *cex)

CGUL_EXPORT void	cgul_list__delete (cgul_list_t l)

CGUL_EXPORT void	cgul_list__free_values (cgul_list_t l)

CGUL_EXPORT unsigned long int	cgul_list__get_cache_size (cgul_exception_t *cex, cgul_list_t l)

CGUL_EXPORT void	cgul_list__set_cache_size (cgul_exception_t *cex, cgul_list_t l, unsigned long int size)

CGUL_EXPORT int	cgul_list__is_empty (cgul_exception_t *cex, cgul_list_t l)

CGUL_EXPORT cgul_list_node_t	cgul_list__get_front (cgul_exception_t *cex, cgul_list_t l)

CGUL_EXPORT cgul_list_node_t	cgul_list__get_back (cgul_exception_t *cex, cgul_list_t l)

CGUL_EXPORT cgul_list_node_t	cgul_list__push_front (cgul_exception_t cex, cgul_list_t l, const void value)

CGUL_EXPORT void *	cgul_list__pop_front (cgul_exception_t *cex, cgul_list_t l)

CGUL_EXPORT cgul_list_node_t	cgul_list__push_back (cgul_exception_t cex, cgul_list_t l, const void value)

CGUL_EXPORT void *	cgul_list__pop_back (cgul_exception_t *cex, cgul_list_t l)

CGUL_EXPORT void	cgul_list__move_before_node (cgul_exception_t *cex, cgul_list_t l, cgul_list_node_t n1, cgul_list_node_t n2)

CGUL_EXPORT void	cgul_list__move_after_node (cgul_exception_t *cex, cgul_list_t l, cgul_list_node_t n1, cgul_list_node_t n2)

CGUL_EXPORT cgul_list_node_t	cgul_list__insert_before_node (cgul_exception_t cex, cgul_list_t l, cgul_list_node_t n, const void value)

CGUL_EXPORT cgul_list_node_t	cgul_list__insert_after_node (cgul_exception_t cex, cgul_list_t l, cgul_list_node_t n, const void value)

CGUL_EXPORT cgul_list_node_t	cgul_list__insert_sorted (cgul_exception_t cex, cgul_list_t l, const void value, cgul_list__compare_t f)

CGUL_EXPORT void	cgul_list__sort (cgul_exception_t *cex, cgul_list_t l, cgul_list__compare_t f)

CGUL_EXPORT void	cgul_list__merge (cgul_exception_t *cex, cgul_list_t l1, cgul_list_t l2, cgul_list__compare_t f)

CGUL_EXPORT void	cgul_list__reverse (cgul_exception_t *cex, cgul_list_t l)

CGUL_EXPORT void	cgul_list__clear (cgul_exception_t *cex, cgul_list_t l, cgul_cache_t values_cache)

CGUL_EXPORT void	cgul_list__remove_node (cgul_exception_t cex, cgul_list_t l, cgul_list_node_t n, void *value_out)

CGUL_EXPORT void	cgul_list__remove_range (cgul_exception_t *cex, cgul_list_t l, cgul_list_node_t n_begin, cgul_list_node_t n_end, cgul_cache_t values_cache)

CGUL_EXPORT int	cgul_list__remove_value (cgul_exception_t cex, cgul_list_t l, const void value, cgul_cache_t values_cache)

CGUL_EXPORT unsigned long int	cgul_list__get_size (cgul_exception_t *cex, cgul_list_t l)

CGUL_EXPORT void	cgul_list__swap (cgul_exception_t *cex, cgul_list_t l1, cgul_list_t l2)

CGUL_EXPORT void	cgul_list__foldl (cgul_exception_t cex, cgul_list_t l, cgul_list__fold_t f, void data)

CGUL_EXPORT void	cgul_list__foldr (cgul_exception_t cex, cgul_list_t l, cgul_list__fold_t f, void data)

CGUL_EXPORT void	cgul_list__traverse (cgul_exception_t cex, cgul_list_t l, cgul_list__traverse_t f, void data)

CGUL_EXPORT void	cgul_list__traverse_range (cgul_exception_t cex, cgul_list_t l, cgul_list_node_t first, cgul_list_node_t last, cgul_list__traverse_t f, void data)

Detailed Description

Linked list implementation.

Author: Paul Serice

Typedef Documentation

§ cgul_list_t

typedef typedefCGUL_BEGIN_C struct cgul_list* cgul_list_t

Opaque pointer to a cgul_list instance.

§ cgul_list__compare_t

typedef int(* cgul_list__compare_t) (const void *value1, const void *value2)

This typedef is the interface for the comparison function used by cgul_list__sort() and cgul_list__insert_sorted(). When you define your comparison function, you should compare value1 to value2 and return less than zero, zero, or greater than zero if value1 is less than, equal to, or greater than value2.

Parameters

[in]	value1	first value
[in]	value2	second value

Returns: result of comparison

§ cgul_list__fold_t

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

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

    cgul_list__foldl()
    cgul_list__foldr()

Parameters

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

Returns: whether to continue

§ cgul_list__traverse_t

typedef int(* cgul_list__traverse_t) (cgul_exception_t *cex, cgul_list_t l, cgul_list_node_t n, void *data)

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

    cgul_list__traverse()
    cgul_list__traverse_range()

Parameters

[in,out]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	n	node
[in]	data	client data

Returns: whether to continue

Function Documentation

§ cgul_list__new()

CGUL_EXPORT cgul_list_t cgul_list__new ( cgul_exception_t * cex )

Create a new cgul_list object. The caller is responsible for freeing the object by calling cgul_list__delete(). If memory cannot be allocated, NULL is returned and an exception is thrown.

Parameters

[in,out] cex c-style exception

Returns: new cgul_list instance

Referenced by cgul_list_cxx::cgul_list_cxx().

§ cgul_list__delete()

CGUL_EXPORT void cgul_list__delete ( cgul_list_t l )

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

Parameters

[in] l cgul_list instance

See also: cgul_list__free_values()

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

§ cgul_list__free_values()

CGUL_EXPORT void cgul_list__free_values ( cgul_list_t l )

This method calls free() on all the values in the list l. 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_list__delete() because it otherwise invalidates the list. Because this function is basically an extension of cgul_list__delete(), it does not accept a cgul_exception object as an input parameter.

Parameters

[in] l cgul_list instance

Referenced by cgul_list_cxx::free_values().

§ cgul_list__get_cache_size()

CGUL_EXPORT unsigned long int cgul_list__get_cache_size	(	cgul_exception_t *	cex,
		cgul_list_t	l
	)

Get the size of the cache of nodes.

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance

Returns: size of the cache of nodes

Referenced by cgul_list_cxx::get_cache_size().

§ cgul_list__set_cache_size()

CGUL_EXPORT void cgul_list__set_cache_size	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		unsigned long int	size
	)

Set the size of the cache of nodes.

For efficiency, the cgul_list 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,out]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	size	of the cache of nodes

Referenced by cgul_list_cxx::set_cache_size().

§ cgul_list__is_empty()

CGUL_EXPORT int cgul_list__is_empty	(	cgul_exception_t *	cex,
		cgul_list_t	l
	)

Return true if the list l is empty.

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance

Returns: whether the list is empty

Referenced by cgul_list_cxx::is_empty().

§ cgul_list__get_front()

CGUL_EXPORT cgul_list_node_t cgul_list__get_front	(	cgul_exception_t *	cex,
		cgul_list_t	l
	)

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

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance

Returns: first element

Referenced by cgul_list_cxx::foldl(), cgul_list_cxx::get_front(), and cgul_list_cxx::traverse_range().

§ cgul_list__get_back()

CGUL_EXPORT cgul_list_node_t cgul_list__get_back	(	cgul_exception_t *	cex,
		cgul_list_t	l
	)

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

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance

Returns: last element

Referenced by cgul_list_cxx::foldr(), cgul_list_cxx::get_back(), and cgul_list_cxx::traverse_range().

§ cgul_list__push_front()

CGUL_EXPORT cgul_list_node_t cgul_list__push_front	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		const void *	value
	)

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

Parameters

[in,out]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	value	value to add at the front of the list

Returns: node that holds value

Referenced by cgul_list_cxx::push_front().

§ cgul_list__pop_front()

CGUL_EXPORT void* cgul_list__pop_front	(	cgul_exception_t *	cex,
		cgul_list_t	l
	)

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

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance

Returns: value that was stored in the front node

Referenced by cgul_list_cxx::pop_front().

§ cgul_list__push_back()

CGUL_EXPORT cgul_list_node_t cgul_list__push_back	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		const void *	value
	)

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

Parameters

[in,out]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	value	value to add at the back of the list

Returns: node that holds value

Referenced by cgul_list_cxx::push_back().

§ cgul_list__pop_back()

CGUL_EXPORT void* cgul_list__pop_back	(	cgul_exception_t *	cex,
		cgul_list_t	l
	)

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

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance

Returns: value that was stored in the back node

Referenced by cgul_list_cxx::pop_back().

§ cgul_list__move_before_node()

CGUL_EXPORT void cgul_list__move_before_node	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_list_node_t	n1,
		cgul_list_node_t	n2
	)

Move n2 before n1 in list l. 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:

    cgul_list__move_before_node(&local,
                                lst,
                                NULL,
                                cgul_list__get_front(&local, lst));

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	n1	insert before this node
[in]	n2	node to insert

Referenced by cgul_list_cxx::move_before_node().

§ cgul_list__move_after_node()

CGUL_EXPORT void cgul_list__move_after_node	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_list_node_t	n1,
		cgul_list_node_t	n2
	)

Move n2 after n1 in list l. 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:

    cgul_list__move_after_node(&local,
                               lst,
                               NULL,
                               cgul_list__get_back(&local, lst));

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	n1	insert after this node
[in]	n2	node to insert

Referenced by cgul_list_cxx::move_after_node().

§ cgul_list__insert_before_node()

CGUL_EXPORT cgul_list_node_t cgul_list__insert_before_node	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_list_node_t	n,
		const void *	value
	)

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

Parameters

[in,out]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	n	insert before this node
[in]	value	value to insert

Returns: node that holds value

Referenced by cgul_list_cxx::insert_before_node().

§ cgul_list__insert_after_node()

CGUL_EXPORT cgul_list_node_t cgul_list__insert_after_node	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_list_node_t	n,
		const void *	value
	)

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

Parameters

[in,out]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	n	insert after this node
[in]	value	value to insert

Returns: node that holds value

Referenced by cgul_list_cxx::insert_after_node().

§ cgul_list__insert_sorted()

CGUL_EXPORT cgul_list_node_t cgul_list__insert_sorted	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		const void *	value,
		cgul_list__compare_t	f
	)

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

This method assumes l is already sorted. If not, call cgul_list__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 cgul_list__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 cgul_list__push_back() followed by a single call to cgul_list__sort().

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

Parameters

[in,out]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	value	value to insert
[in]	f	comparison function

Returns: node that holds value

Referenced by cgul_list_cxx::insert_sorted().

§ cgul_list__sort()

CGUL_EXPORT void cgul_list__sort	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_list__compare_t	f
	)

Sort the list l using 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 cgul_list__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 or cgul_multimap are usually better solutions.

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

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	f	comparison function

See also: cgul_merge_sort; cgul_list__merge

Referenced by cgul_list_cxx::sort().

§ cgul_list__merge()

CGUL_EXPORT void cgul_list__merge	(	cgul_exception_t *	cex,
		cgul_list_t	l1,
		cgul_list_t	l2,
		cgul_list__compare_t	f
	)

Merge the sorted lists l1 and l2 producing one large sorted list. The sort order is determined by the comparison function f. When this method returns, all the nodes will be in l1 and l2 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]	cex	c-style exception
[in]	l1	first list
[in]	l2	second list
[in]	f	comparison function

Referenced by cgul_list_cxx::merge().

§ cgul_list__reverse()

CGUL_EXPORT void cgul_list__reverse	(	cgul_exception_t *	cex,
		cgul_list_t	l
	)

Reverse the order of the list. It is usually more efficient, however, to use either cgul_list_node__get_prev() to iterate in reverse order or cgul_list__push_front() to insert in reverse order.

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance

§ cgul_list__clear()

CGUL_EXPORT void cgul_list__clear	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_cache_t	values_cache
	)

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 instance that is not NULL, the values will be put back on their cache.

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	values_cache	values cache

See also: cgul_cache__get_freer()

Referenced by cgul_list_cxx::clear().

§ cgul_list__remove_node()

CGUL_EXPORT void cgul_list__remove_node	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_list_node_t	n,
		void **	value_out
	)

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

    curr = cgul_list__get_front(&local, l);
    for ( ; curr ; curr = next) {
        next = cgul_list_node__get_next(&local, curr);
        cgul_list__remove_node(&local, l, curr, &value_out);
        free(value_out);
    }

Alternatively, you can use cgul_list__remove_range(), cgul_list__traverse(), or cgul_list__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 its values, another way to remove nodes is as follows:

    static int
    remove_node_cb(cgul_list_t l,
                   cgul_list_node_t n,
                   void* data)
    {
        cgul_exception_t local = NULL;
        cgul_string_t value_out = NULL;
        cgul_list__remove_node(&local, l, n, (void**)&value_out);
        cgul_string__delete(value_out);
        return 1;
    }

    cgul_list__traverse(&local, l, &remove_node_cb, NULL);

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	n	node to remove
[out]	value_out	value

Referenced by cgul_list_cxx::remove_node().

§ cgul_list__remove_range()

CGUL_EXPORT void cgul_list__remove_range	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_list_node_t	n_begin,
		cgul_list_node_t	n_end,
		cgul_cache_t	values_cache
	)

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 instance that is not NULL, the values will be put back on their cache.

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance
[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__get_freer()

Referenced by cgul_list_cxx::remove_range().

§ cgul_list__remove_value()

CGUL_EXPORT int cgul_list__remove_value	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		const void *	value,
		cgul_cache_t	values_cache
	)

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 instance that is not NULL, the values will be put back on their cache.

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	value	values to remove from the list
[in]	values_cache	values cache

See also: cgul_cache__get_freer()

Referenced by cgul_list_cxx::remove_value().

§ cgul_list__get_size()

CGUL_EXPORT unsigned long int cgul_list__get_size	(	cgul_exception_t *	cex,
		cgul_list_t	l
	)

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

Parameters

[in]	cex	c-style exception
[in]	l	`cgul_list` instance

Returns: size of the list

Referenced by cgul_list_cxx::get_size().

§ cgul_list__swap()

CGUL_EXPORT void cgul_list__swap	(	cgul_exception_t *	cex,
		cgul_list_t	l1,
		cgul_list_t	l2
	)

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

Parameters

[in]	cex	c-style exception
[in]	l1	first `cgul_list` instance
[in]	l2	second `cgul_list` instance

Referenced by cgul_list_cxx::swap().

§ cgul_list__foldl()

CGUL_EXPORT void cgul_list__foldl	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_list__fold_t	f,
		void *	data
	)

This method performs a left fold of the list l 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 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]	l	`cgul_list` instance
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_list__foldr()

CGUL_EXPORT void cgul_list__foldr	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_list__fold_t	f,
		void *	data
	)

This method performs a right fold of the list l 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 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]	l	`cgul_list` instance
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_list__traverse()

CGUL_EXPORT void cgul_list__traverse	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_list__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 list l. 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_list__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_list__traverse() or cgul_list__traverse_range() in order to iterate over the list elements. In fact, I would recommend that you use cgul_list_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_list_node 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,out]	cex	c-style exception
[in]	l	`cgul_list` instance
[in]	f	traversal callback function
[in]	data	passed to `f`

§ cgul_list__traverse_range()

CGUL_EXPORT void cgul_list__traverse_range	(	cgul_exception_t *	cex,
		cgul_list_t	l,
		cgul_list_node_t	first,
		cgul_list_node_t	last,
		cgul_list__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 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 standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the list l. 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_list__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 cgul_list__traverse() or cgul_list__traverse_range() in order to iterate over the list elements. In fact, I would recommend that you use cgul_list_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_list_node 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,out]	cex	c-style exception
[in]	l	`cgul_list` 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_list__traverse

Typedefs

Functions

Detailed Description

Typedef Documentation

§ cgul_list_t

§ cgul_list__compare_t

§ cgul_list__fold_t

§ cgul_list__traverse_t

Function Documentation

§ cgul_list__new()

§ cgul_list__delete()

§ cgul_list__free_values()

§ cgul_list__get_cache_size()

§ cgul_list__set_cache_size()

§ cgul_list__is_empty()

§ cgul_list__get_front()

§ cgul_list__get_back()

§ cgul_list__push_front()

§ cgul_list__pop_front()

§ cgul_list__push_back()

§ cgul_list__pop_back()

§ cgul_list__move_before_node()

§ cgul_list__move_after_node()

§ cgul_list__insert_before_node()

§ cgul_list__insert_after_node()

§ cgul_list__insert_sorted()

§ cgul_list__sort()

§ cgul_list__merge()

§ cgul_list__reverse()

§ cgul_list__clear()

§ cgul_list__remove_node()

§ cgul_list__remove_range()

§ cgul_list__remove_value()

§ cgul_list__get_size()

§ cgul_list__swap()

§ cgul_list__foldl()

§ cgul_list__foldr()

§ cgul_list__traverse()

§ cgul_list__traverse_range()