Doubly Linked Lists

Functions
cx_list_iterator	cx_list_begin (const cx_list *list)
	Get an iterator for the first list element. More...
cx_list_iterator	cx_list_end (const cx_list *list)
	Get an iterator for the position after the last list element. More...
cx_list_iterator	cx_list_next (const cx_list *list, cx_list_const_iterator position)
	Get an iterator for the next list element. More...
cx_list_iterator	cx_list_previous (const cx_list *list, cx_list_const_iterator position)
	Get an iterator for the previous list element. More...
void	cx_list_clear (cx_list *list)
	Remove all elements from a list. More...
cxbool	cx_list_empty (const cx_list *list)
	Check whether a list is empty. More...
cx_list *	cx_list_new (void)
	Create a new list without any elements. More...
void	cx_list_delete (cx_list *list)
	Destroy a list. More...
void	cx_list_destroy (cx_list *list, cx_free_func deallocate)
	Destroy a list and all its elements. More...
cxsize	cx_list_size (const cx_list *list)
	Get the actual number of list elements. More...
cxsize	cx_list_max_size (const cx_list *list)
	Get the maximum number of list elements possible. More...
void	cx_list_swap (cx_list *list1, cx_list *list2)
	Swap the data of two lists. More...
cxptr	cx_list_assign (cx_list *list, cx_list_iterator position, cxcptr data)
	Assign data to a list element. More...
cxptr	cx_list_front (const cx_list *list)
	Get the first element of a list. More...
cxptr	cx_list_back (const cx_list *list)
	Get the last element of a list. More...
cxptr	cx_list_get (const cx_list *list, cx_list_const_iterator position)
	Get the data at a given iterator position. More...
cx_list_iterator	cx_list_insert (cx_list *list, cx_list_iterator position, cxcptr data)
	Insert data into a list at a given iterator position. More...
void	cx_list_push_front (cx_list *list, cxcptr data)
	Insert data at the beginning of a list. More...
void	cx_list_push_back (cx_list *list, cxcptr data)
	Append data at the end of a list. More...
cx_list_iterator	cx_list_erase (cx_list *list, cx_list_iterator position, cx_free_func deallocate)
	Erase a list element. More...
cxptr	cx_list_extract (cx_list *list, cx_list_iterator position)
	Extract a list element. More...
cxptr	cx_list_pop_front (cx_list *list)
	Remove the first list element. More...
cxptr	cx_list_pop_back (cx_list *list)
	Remove the last element of a list. More...
void	cx_list_remove (cx_list *list, cxcptr data)
	Remove all elements with a given value from a list. More...
void	cx_list_unique (cx_list *list, cx_compare_func compare)
	Remove duplicates of consecutive elements. More...
void	cx_list_splice (cx_list *tlist, cx_list_iterator position, cx_list *slist, cx_list_iterator first, cx_list_iterator last)
	Move a range of list elements in front of a given position. More...
void	cx_list_merge (cx_list *list1, cx_list *list2, cx_compare_func compare)
	Merge two sorted lists. More...
void	cx_list_sort (cx_list *list, cx_compare_func compare)
	Sort all elements of a list using the given comparison function. More...
void	cx_list_reverse (cx_list *list)
	Reverse the order of all list elements. More...

Detailed Description

The module implements a doubly linked list object which can be traversed in both directions, forward and backward, and methods to create, destroy and manipulate it.

Synopsis:

#include <cxlist.h>

Function Documentation

cxptr cx_list_assign	(	cx_list *	list,
		cx_list_iterator	position,
		cxcptr	data
	)

Assign data to a list element.

Parameters

list	A list.
position	List position where the data will be stored
data	Data to store.

Returns

Handle to the previously stored data object.

The function assigns the data object reference data to the iterator position position of the list list.

cxptr cx_list_back

(

const cx_list *

list

)

Get the last element of a list.

Parameters

list	The list to query.

Returns

Handle to the data object stored in the last list element.

The function returns a reference to the last data item in the list list.

Calling this function with an empty list is an invalid operation, and the result is undefined.

References cx_list_empty().

cx_list_iterator cx_list_begin

(

const cx_list *

list

)

Get an iterator for the first list element.

Parameters

list

A list.

Returns

Iterator for the first element in the list or cx_list_end() if the list is empty.

The function returns a handle to the first element of list. The handle cannot be used directly to access the element data, but only through the appropriate functions.

Referenced by cx_list_pop_front(), and cx_list_remove().

void cx_list_clear

(

cx_list *

list

)

Remove all elements from a list.

Parameters

list	List to be cleared.

Returns

Nothing.

The list list is cleared, i.e. all elements are removed from the list. The removed data objects are left untouched, in particular they are not deallocated. It is the responsibility of the caller to ensure that there are still other references to the removed data objects. After calling cx_list_clear() the list list is empty.

void cx_list_delete

(

cx_list *

list

)

Destroy a list.

Parameters

list	The list to delete.

Returns

Nothing.

The function deallocates the list object, but not the data objects currently stored in the list.

References cx_free(), and cx_list_empty().

void cx_list_destroy	(	cx_list *	list,
		cx_free_func	deallocate
	)

Destroy a list and all its elements.

Parameters

list	List container to destroy.
deallocate	Data deallocator.

Returns

Nothing.

The function deallocates all data objects referenced by the list using the data deallocation function deallocate and finally deallocates the list itself.

References cx_free(), and cx_list_empty().

cxbool cx_list_empty

(

const cx_list *

list

)

Check whether a list is empty.

Parameters

list

A list.

Returns

The function returns TRUE if the list is empty, and FALSE otherwise.

The function tests if the list list contains data. A call to this function is equivalent to the statement:

return (cx_list_size(list) == 0);

Referenced by cx_list_back(), cx_list_delete(), cx_list_destroy(), cx_list_front(), cx_list_pop_back(), cx_list_pop_front(), and cx_list_unique().

cx_list_iterator cx_list_end

(

const cx_list *

list

)

Get an iterator for the position after the last list element.

Parameters

list

A list.

Returns

Iterator for the end of the list.

The function returns an iterator for the position one past the last element of the list list. The handle cannot be used to directly access the element data, but only through the appropriate functions.

Referenced by cx_list_pop_back().

cx_list_iterator cx_list_erase	(	cx_list *	list,
		cx_list_iterator	position,
		cx_free_func	deallocate
	)

Erase a list element.

Parameters

list	The list to update.
position	List iterator position.
deallocate	Data deallocator.

Returns

The iterator for the list position after position.

The function removes the data object stored at position position from the list list. The data object itself is deallocated by calling the data deallocator deallocate.

cxptr cx_list_extract	(	cx_list *	list,
		cx_list_iterator	position
	)

Extract a list element.

Parameters

list	A list.
position	List iterator position.

Returns

Handle to the previously stored data object.

The function removes a data object from the list list located at the iterator position position without destroying the data object.

See Also

cx_list_erase(), cx_list_remove()

cxptr cx_list_front

(

const cx_list *

list

)

Get the first element of a list.

Parameters

list	The list to query.

Returns

Handle to the data object stored in the first list element.

The function returns a reference to the first data item in the list list.

Calling this function with an empty list is an invalid operation, and the result is undefined.

References cx_list_empty().

cxptr cx_list_get	(	const cx_list *	list,
		cx_list_const_iterator	position
	)

Get the data at a given iterator position.

Parameters

list	A list.
position	List position the data is retrieved from.

Returns

Handle to the data object.

The function returns a reference to the data item stored in the list list at the iterator position position.

cx_list_iterator cx_list_insert	(	cx_list *	list,
		cx_list_iterator	position,
		cxcptr	data
	)

Insert data into a list at a given iterator position.

Parameters

list	The list to update.
position	List iterator position.
data	Data item to insert.

Returns

List iterator position of the inserted data item.

The function inserts the data object reference data into the list list at the list position given by the list iterator position.

References cx_list_max_size().

cxsize cx_list_max_size

(

const cx_list *

list

)

Get the maximum number of list elements possible.

Parameters

list

A list.

Returns

The maximum number of elements that can be stored in the list.

Retrieves the lists capacity, i.e. the maximum possible number of data items a list can hold.

Referenced by cx_list_insert().

void cx_list_merge	(	cx_list *	list1,
		cx_list *	list2,
		cx_compare_func	compare
	)

Merge two sorted lists.

Parameters

list1	First list to merge.
list2	Second list to merge.
compare	Function comparing the list elements.

Returns

Nothing.

The function combines the two lists list1 and list2 by moving all elements from list2 into list1, so that all elements are still sorted. The function requires that both input lists are already sorted. The sorting order in which the elements of list2 are inserted into list1 is determined by the comparison function compare. The comparison function compare must return an integer less than, equal or greater than zero if the first argument passed to it is found, respectively, to be less than, match, or be greater than the second argument.

The list list2 is consumed by this process, i.e. after the successful merging of the two lists, list list2 will be empty.

cx_list* cx_list_new

(

void

)

Create a new list without any elements.

Returns

Handle to the newly allocated list.

The function allocates memory for the list object and initializes it to a empty list.

References cx_malloc().

cx_list_iterator cx_list_next	(	const cx_list *	list,
		cx_list_const_iterator	position
	)

Get an iterator for the next list element.

Parameters

list	A list.
position	Current iterator position.

Returns

Iterator for the next list element.

The function returns an iterator for the next element in the list list with respect to the current iterator position position. If the list list is empty or position points to the list end the function returns cx_list_end().

cxptr cx_list_pop_back

(

cx_list *

list

)

Remove the last element of a list.

Parameters

list	The list to update.

Returns

Handle to the data object previously stored as the last list element.

The function removes the last element from the list list returning a handle to the previously stored data.

It is equivalent to the statement

cx_list_extract(list, cx_list_previous(list, cx_list_end(list)));

Calling this function with an empty list is an invalid operation, and the result is undefined.

References cx_list_empty(), and cx_list_end().

cxptr cx_list_pop_front

(

cx_list *

list

)

Remove the first list element.

Parameters

list	The list to update.

Returns

Handle to the data object previously stored as the first list element.

The function removes the first element from the list list returning a handle to the previously stored data.

It is equivalent to the statement

cx_list_extract(list, cx_list_begin(list));

Calling this function with an empty list is an invalid operation, and the result is undefined.

References cx_list_begin(), and cx_list_empty().

cx_list_iterator cx_list_previous	(	const cx_list *	list,
		cx_list_const_iterator	position
	)

Get an iterator for the previous list element.

Parameters

list	A list.
position	Current iterator position.

Returns

Iterator for the previous list element.

The function returns an iterator for the previous element in the list list with respect to the current iterator position position. If the list list is empty or position points to the beginning of the list the function returns cx_list_end().

void cx_list_push_back	(	cx_list *	list,
		cxcptr	data
	)

Append data at the end of a list.

Parameters

list	The list to update.
data	Data to append.

Returns

Nothing.

The data data is inserted into the list list after the last element, so that it becomes the new list tail.

It is equivalent to the statement

cx_list_insert(list, cx_list_end(list), data);

void cx_list_push_front	(	cx_list *	list,
		cxcptr	data
	)

Insert data at the beginning of a list.

Parameters

list	The list to update.
data	Data to add to the list.

Returns

Nothing.

The data data is inserted into the list list before the first element of the list, so that it becomes the new list head.

It is equivalent to the statement

cx_list_insert(list, cx_list_begin(list), data);

void cx_list_remove	(	cx_list *	list,
		cxcptr	data
	)

Remove all elements with a given value from a list.

Parameters

list	A list object.
data	Data to remove.

Returns

Nothing.

The value data is searched in the list list. If the data is found it is removed from the list. The data object itself is not deallocated.

References cx_list_begin().

void cx_list_reverse

(

cx_list *

list

)

Reverse the order of all list elements.

Parameters

list	The list to reverse.

Returns

Nothing.

The order of the elements of the list list is reversed.

cxsize cx_list_size

(

const cx_list *

list

)

Get the actual number of list elements.

Parameters

list

A list.

Returns

The current number of elements the list contains, or 0 if the list is empty.

Retrieves the number of elements currently stored in the list list.

void cx_list_sort	(	cx_list *	list,
		cx_compare_func	compare
	)

Sort all elements of a list using the given comparison function.

Parameters

list	The list to sort.
compare	Function comparing the list elements.

Returns

Nothing.

The input list list is sorted using the comparison function compare to determine the order of two list elements. The comparison function compare must return an integer less than, equal or greater than zero if the first argument passed to it is found, respectively, to be less than, match, or be greater than the second argument.

void cx_list_splice	(	cx_list *	tlist,
		cx_list_iterator	position,
		cx_list *	slist,
		cx_list_iterator	first,
		cx_list_iterator	last
	)

Move a range of list elements in front of a given position.

Parameters

tlist	Target list.
position	Target iterator position.
slist	Source list.
first	Position of the first element to move.
last	Position of the last element to move.

Returns

Nothing.

The range of list elements from the iterator position first to last, but not including last, is moved from the source list slist in front of the position position of the target list tlist. Target and source list may be identical, provided that the target position position does not fall within the range of list elements to move.

void cx_list_swap	(	cx_list *	list1,
		cx_list *	list2
	)

Swap the data of two lists.

Parameters

list1	First list.
list2	Second list.

Returns

Nothing.

The contents of the first list list1 will be moved to the second list list2, while the contents of list2 is moved to list1.

void cx_list_unique	(	cx_list *	list,
		cx_compare_func	compare
	)

Remove duplicates of consecutive elements.

Parameters

list	A list.
compare	Function comparing the list elements.

Returns

Nothing.

The function removes duplicates of consecutive list elements, i.e. list elements with the same value, from the list list. The equality of the list elements is checked using the comparison function compare. The comparison function compare must return an integer less than, equal or greater than zero if the first argument passed to it is found, respectively, to be less than, match, or be greater than the second argument.

References cx_list_empty().