Interface for list implementations. More...

#include "common.h"
#include "collection.h"

Data Structures
struct	cx_list_s
	Structure for holding the base data of a list. More...

struct	cx_list_class_s
	The class definition for arbitrary lists. More...

Typedefs
typedef struct cx_list_class_s	cx_list_class
	List class type.

typedef struct cx_list_s	CxList
	Common type for all list implementations.

Functions
size_t	cx_list_default_insert_array (struct cx_list_s list, size_t index, const void data, size_t n)
	Default implementation of an array insert.

size_t	cx_list_default_insert_sorted (struct cx_list_s list, const void sorted_data, size_t n)
	Default implementation of a sorted insert.

void	cx_list_default_sort (struct cx_list_s *list)
	Default unoptimized sort implementation.

int	cx_list_default_swap (struct cx_list_s *list, size_t i, size_t j)
	Default unoptimized swap implementation.

void	cx_list_init (struct cx_list_s list, struct cx_list_class_s cl, const struct cx_allocator_s *allocator, cx_compare_func comparator, size_t elem_size)
	Initializes a list struct.

static size_t	cxListSize (const CxList *list)
	Returns the number of elements currently stored in the list.

static int	cxListAdd (CxList list, const void elem)
	Adds an item to the end of the list.

static size_t	cxListAddArray (CxList list, const void array, size_t n)
	Adds multiple items to the end of the list.

static int	cxListInsert (CxList list, size_t index, const void elem)
	Inserts an item at the specified index.

static int	cxListInsertSorted (CxList list, const void elem)
	Inserts an item into a sorted list.

static size_t	cxListInsertArray (CxList list, size_t index, const void array, size_t n)
	Inserts multiple items to the list at the specified index.

static size_t	cxListInsertSortedArray (CxList list, const void array, size_t n)
	Inserts a sorted array into a sorted list.

static int	cxListInsertAfter (CxIterator iter, const void elem)
	Inserts an element after the current location of the specified iterator.

static int	cxListInsertBefore (CxIterator iter, const void elem)
	Inserts an element before the current location of the specified iterator.

static int	cxListRemove (CxList *list, size_t index)
	Removes the element at the specified index.

static int	cxListRemoveAndGet (CxList list, size_t index, void targetbuf)
	Removes and returns the element at the specified index.

static size_t	cxListRemoveArray (CxList *list, size_t index, size_t num)
	Removes multiple element starting at the specified index.

static size_t	cxListRemoveArrayAndGet (CxList list, size_t index, size_t num, void targetbuf)
	Removes and returns multiple element starting at the specified index.

static void	cxListClear (CxList *list)
	Removes all elements from this list.

static int	cxListSwap (CxList *list, size_t i, size_t j)
	Swaps two items in the list.

static void *	cxListAt (const CxList *list, size_t index)
	Returns a pointer to the element at the specified index.

static CxIterator	cxListIteratorAt (const CxList *list, size_t index)
	Returns an iterator pointing to the item at the specified index.

static CxIterator	cxListBackwardsIteratorAt (const CxList *list, size_t index)
	Returns a backwards iterator pointing to the item at the specified index.

CxIterator	cxListMutIteratorAt (CxList *list, size_t index)
	Returns a mutating iterator pointing to the item at the specified index.

CxIterator	cxListMutBackwardsIteratorAt (CxList *list, size_t index)
	Returns a mutating backwards iterator pointing to the item at the specified index.

static CxIterator	cxListIterator (const CxList *list)
	Returns an iterator pointing to the first item of the list.

static CxIterator	cxListMutIterator (CxList *list)
	Returns a mutating iterator pointing to the first item of the list.

static CxIterator	cxListBackwardsIterator (const CxList *list)
	Returns a backwards iterator pointing to the last item of the list.

static CxIterator	cxListMutBackwardsIterator (CxList *list)
	Returns a mutating backwards iterator pointing to the last item of the list.

static size_t	cxListFind (const CxList list, const void elem)
	Returns the index of the first element that equals `elem`.

static bool	cxListIndexValid (const CxList *list, size_t index)
	Checks if the specified index is within bounds.

static size_t	cxListFindRemove (CxList list, const void elem)
	Removes and returns the index of the first element that equals `elem`.

static void	cxListSort (CxList *list)
	Sorts the list.

static void	cxListReverse (CxList *list)
	Reverses the order of the items.

int	cxListCompare (const CxList list, const CxList other)
	Compares a list to another list of the same type.

void	cxListFree (CxList *list)
	Deallocates the memory of the specified list structure.

Variables
CxList *const	cxEmptyList
	A shared instance of an empty list.

Detailed Description

Interface for list implementations.

Author: Mike Becker; Olaf Wintermann

Copyright: 2-Clause BSD License

Function Documentation

◆ cx_list_default_insert_array()

size_t cx_list_default_insert_array	(	struct cx_list_s *	list,
		size_t	index,
		const void *	data,
		size_t	n )

Default implementation of an array insert.

This function uses the element insert function for each element of the array.

Use this in your own list class if you do not want to implement an optimized version for your list.

Parameters

list	the list
index	the index where to insert the data
data	a pointer to the array of data to insert
n	the number of elements to insert

Returns: the number of elements actually inserted

◆ cx_list_default_insert_sorted()

size_t cx_list_default_insert_sorted	(	struct cx_list_s *	list,
		const void *	sorted_data,
		size_t	n )

Default implementation of a sorted insert.

This function uses the array insert function to insert consecutive groups of sorted data.

The source data must already be sorted wrt. the list's compare function.

Use this in your own list class if you do not want to implement an optimized version for your list.

Parameters

list	the list
sorted_data	a pointer to the array of pre-sorted data to insert
n	the number of elements to insert

Returns: the number of elements actually inserted

◆ cx_list_default_sort()

void cx_list_default_sort ( struct cx_list_s * list )

Default unoptimized sort implementation.

This function will copy all data to an array, sort the array with standard qsort, and then copy the data back to the list memory.

Use this in your own list class if you do not want to implement an optimized version for your list.

Parameters

list	the list that shall be sorted

◆ cx_list_default_swap()

int cx_list_default_swap	(	struct cx_list_s *	list,
		size_t	i,
		size_t	j )

Default unoptimized swap implementation.

Use this in your own list class if you do not want to implement an optimized version for your list.

Parameters

list	the list in which to swap
i	index of one element
j	index of the other element

Return values

zero	success
non-zero	when indices are out of bounds or memory allocation for the temporary buffer fails

◆ cx_list_init()

void cx_list_init	(	struct cx_list_s *	list,
		struct cx_list_class_s *	cl,
		const struct cx_allocator_s *	allocator,
		cx_compare_func	comparator,
		size_t	elem_size )

Initializes a list struct.

Only use this function if you are creating your own list implementation. The purpose of this function is to be called in the initialization code of your list, to set certain members correctly.

This is particularly important when you want your list to support CX_STORE_POINTERS as elem_size. This function will wrap the list class accordingly and make sure that you can implement your list as if it was only storing objects and the wrapper will automatically enable the feature of storing pointers.

Example

CxList *myCustomListCreate(
        const CxAllocator *allocator,
        cx_compare_func comparator,
        size_t elem_size
) {
    if (allocator == NULL) {
        allocator = cxDefaultAllocator;
    }
 
    MyCustomList *list = cxCalloc(allocator, 1, sizeof(MyCustomList));
    if (list == NULL) return NULL;
 
    // initialize
    cx_list_init((CxList*)list, &my_custom_list_class,
            allocator, comparator, elem_size);
 
    // ... some more custom stuff ...
 
    return (CxList *) list;
}

Parameters

list	the list to initialize
cl	the list class
allocator	the allocator for the elements
comparator	a compare function for the elements
elem_size	the size of one element

◆ cxListAdd()

static int cxListAdd	(	CxList *	list,
		const void *	elem )

inlinestatic

Adds an item to the end of the list.

Parameters

list	the list
elem	a pointer to the element to add

Return values

zero	success
non-zero	memory allocation failure

See also: cxListAddArray()

◆ cxListAddArray()

static size_t cxListAddArray	(	CxList *	list,
		const void *	array,
		size_t	n )

inlinestatic

Adds multiple items to the end of the list.

This method is more efficient than invoking cxListAdd() multiple times.

If there is not enough memory to add all elements, the returned value is less than n.

If this list is storing pointers instead of objects array is expected to be an array of pointers.

Parameters

list	the list
array	a pointer to the elements to add
n	the number of elements to add

Returns: the number of added elements

◆ cxListAt()

static void * cxListAt	(	const CxList *	list,
		size_t	index )

inlinestatic

Returns a pointer to the element at the specified index.

Parameters

list	the list
index	the index of the element

Returns: a pointer to the element or NULL if the index is out of bounds

◆ cxListBackwardsIterator()

static CxIterator cxListBackwardsIterator ( const CxList * list )

inlinestatic

Returns a backwards iterator pointing to the last item of the list.

The returned iterator is position-aware.

If the list is empty, a past-the-end iterator will be returned.

Parameters

list the list

Returns: a new iterator

◆ cxListBackwardsIteratorAt()

static CxIterator cxListBackwardsIteratorAt	(	const CxList *	list,
		size_t	index )

inlinestatic

Returns a backwards iterator pointing to the item at the specified index.

The returned iterator is position-aware.

If the index is out of range, a past-the-end iterator will be returned.

Parameters

list	the list
index	the index where the iterator shall point at

Returns: a new iterator

◆ cxListClear()

static void cxListClear ( CxList * list )

inlinestatic

Removes all elements from this list.

If element destructor functions are specified, they are called for each element before removing them.

Parameters

list the list

◆ cxListCompare()

int cxListCompare	(	const CxList *	list,
		const CxList *	other )

Compares a list to another list of the same type.

First, the list sizes are compared. If they match, the lists are compared element-wise.

Parameters

list	the list
other	the list to compare to

Return values

zero	both lists are equal element wise
negative	the first list is smaller or the first non-equal element in the first list is smaller
positive	the first list is larger or the first non-equal element in the first list is larger

◆ cxListFind()

static size_t cxListFind	(	const CxList *	list,
		const void *	elem )

inlinestatic

Returns the index of the first element that equals elem.

Determining equality is performed by the list's comparator function.

Parameters

list	the list
elem	the element to find

Returns: the index of the element or the size of the list when the element is not found

See also: cxListIndexValid()

◆ cxListFindRemove()

static size_t cxListFindRemove	(	CxList *	list,
		const void *	elem )

inlinestatic

Removes and returns the index of the first element that equals elem.

Determining equality is performed by the list's comparator function.

Parameters

list	the list
elem	the element to find and remove

Returns: the index of the now removed element or the list size when the element is not found or could not be removed

See also: cxListIndexValid()

◆ cxListFree()

void cxListFree ( CxList * list )

Deallocates the memory of the specified list structure.

Also calls the content destructor functions for each element, if specified.

Parameters

list	the list which shall be freed

◆ cxListIndexValid()

static bool cxListIndexValid	(	const CxList *	list,
		size_t	index )

inlinestatic

Checks if the specified index is within bounds.

Parameters

list	the list
index	the index

Return values

true	if the index is within bounds
false	if the index is out of bounds

◆ cxListInsert()

static int cxListInsert	(	CxList *	list,
		size_t	index,
		const void *	elem )

inlinestatic

Inserts an item at the specified index.

If index equals the list size, this is effectively cxListAdd().

Parameters

list	the list
index	the index the element shall have
elem	a pointer to the element to add

Return values

zero	success
non-zero	memory allocation failure or the index is out of bounds

See also: cxListInsertAfter(); cxListInsertBefore()

◆ cxListInsertAfter()

static int cxListInsertAfter	(	CxIterator *	iter,
		const void *	elem )

inlinestatic

Inserts an element after the current location of the specified iterator.

The used iterator remains operational, but all other active iterators should be considered invalidated.

If iter is not a list iterator, the behavior is undefined. If iter is a past-the-end iterator, the new element gets appended to the list.

Parameters

iter	an iterator
elem	the element to insert

Return values

zero	success
non-zero	memory allocation failure

See also: cxListInsert(); cxListInsertBefore()

◆ cxListInsertArray()

static size_t cxListInsertArray	(	CxList *	list,
		size_t	index,
		const void *	array,
		size_t	n )

inlinestatic

Inserts multiple items to the list at the specified index.

If index equals the list size, this is effectively cxListAddArray().

This method is usually more efficient than invoking cxListInsert() multiple times.

If there is not enough memory to add all elements, the returned value is less than n.

If this list is storing pointers instead of objects array is expected to be an array of pointers.

Parameters

list	the list
index	the index where to add the elements
array	a pointer to the elements to add
n	the number of elements to add

Returns: the number of added elements

◆ cxListInsertBefore()

static int cxListInsertBefore	(	CxIterator *	iter,
		const void *	elem )

inlinestatic

Inserts an element before the current location of the specified iterator.

The used iterator remains operational, but all other active iterators should be considered invalidated.

If iter is not a list iterator, the behavior is undefined. If iter is a past-the-end iterator, the new element gets appended to the list.

Parameters

iter	an iterator
elem	the element to insert

Return values

zero	success
non-zero	memory allocation failure

See also: cxListInsert(); cxListInsertAfter()

◆ cxListInsertSorted()

static int cxListInsertSorted	(	CxList *	list,
		const void *	elem )

inlinestatic

Inserts an item into a sorted list.

If the list is not sorted already, the behavior is undefined.

Parameters

list	the list
elem	a pointer to the element to add

Return values

zero	success
non-zero	memory allocation failure

◆ cxListInsertSortedArray()

static size_t cxListInsertSortedArray	(	CxList *	list,
		const void *	array,
		size_t	n )

inlinestatic

Inserts a sorted array into a sorted list.

This method is usually more efficient than inserting each element separately, because consecutive chunks of sorted data are inserted in one pass.

If there is not enough memory to add all elements, the returned value is less than n.

If this list is storing pointers instead of objects array is expected to be an array of pointers.

If the list is not sorted already, the behavior is undefined.

Parameters

list	the list
array	a pointer to the elements to add
n	the number of elements to add

Returns: the number of added elements

◆ cxListIterator()

static CxIterator cxListIterator ( const CxList * list )

inlinestatic

Returns an iterator pointing to the first item of the list.

The returned iterator is position-aware.

If the list is empty, a past-the-end iterator will be returned.

Parameters

list the list

Returns: a new iterator

◆ cxListIteratorAt()

static CxIterator cxListIteratorAt	(	const CxList *	list,
		size_t	index )

inlinestatic

Returns an iterator pointing to the item at the specified index.

The returned iterator is position-aware.

If the index is out of range, a past-the-end iterator will be returned.

Parameters

list	the list
index	the index where the iterator shall point at

Returns: a new iterator

◆ cxListMutBackwardsIterator()

static CxIterator cxListMutBackwardsIterator ( CxList * list )

inlinestatic

Returns a mutating backwards iterator pointing to the last item of the list.

The returned iterator is position-aware.

If the list is empty, a past-the-end iterator will be returned.

Parameters

list the list

Returns: a new iterator

◆ cxListMutBackwardsIteratorAt()

CxIterator cxListMutBackwardsIteratorAt	(	CxList *	list,
		size_t	index )

Returns a mutating backwards iterator pointing to the item at the specified index.

The returned iterator is position-aware.

If the index is out of range, a past-the-end iterator will be returned.

Parameters

list	the list
index	the index where the iterator shall point at

Returns: a new iterator

◆ cxListMutIterator()

static CxIterator cxListMutIterator ( CxList * list )

inlinestatic

Returns a mutating iterator pointing to the first item of the list.

The returned iterator is position-aware.

If the list is empty, a past-the-end iterator will be returned.

Parameters

list the list

Returns: a new iterator

◆ cxListMutIteratorAt()

CxIterator cxListMutIteratorAt	(	CxList *	list,
		size_t	index )

Returns a mutating iterator pointing to the item at the specified index.

The returned iterator is position-aware.

If the index is out of range, a past-the-end iterator will be returned.

Parameters

list	the list
index	the index where the iterator shall point at

Returns: a new iterator

◆ cxListRemove()

static int cxListRemove	(	CxList *	list,
		size_t	index )

inlinestatic

Removes the element at the specified index.

If an element destructor function is specified, it is called before removing the element.

Parameters

list	the list
index	the index of the element

Return values

zero	success
non-zero	index out of bounds

◆ cxListRemoveAndGet()

static int cxListRemoveAndGet	(	CxList *	list,
		size_t	index,
		void *	targetbuf )

inlinestatic

Removes and returns the element at the specified index.

No destructor is called and instead the element is copied to the targetbuf which MUST be large enough to hold the removed element.

Parameters

list	the list
index	the index of the element
targetbuf	a buffer where to copy the element

Return values

zero	success
non-zero	index out of bounds

◆ cxListRemoveArray()

static size_t cxListRemoveArray	(	CxList *	list,
		size_t	index,
		size_t	num )

inlinestatic

Removes multiple element starting at the specified index.

If an element destructor function is specified, it is called for each element. It is guaranteed that the destructor is called before removing the element, however, due to possible optimizations it is neither guaranteed that the destructors are invoked for all elements before starting to remove them, nor that the element is removed immediately after the destructor call before proceeding to the next element.

Parameters

list	the list
index	the index of the element
num	the number of elements to remove

Returns: the actual number of removed elements

◆ cxListRemoveArrayAndGet()

static size_t cxListRemoveArrayAndGet	(	CxList *	list,
		size_t	index,
		size_t	num,
		void *	targetbuf )

inlinestatic

Removes and returns multiple element starting at the specified index.

No destructor is called and instead the elements are copied to the targetbuf which MUST be large enough to hold all removed elements.

Parameters

list	the list
index	the index of the element
num	the number of elements to remove
targetbuf	a buffer where to copy the elements

Returns: the actual number of removed elements

◆ cxListReverse()

static void cxListReverse ( CxList * list )

inlinestatic

Reverses the order of the items.

Parameters

list the list

◆ cxListSize()

static size_t cxListSize ( const CxList * list )

inlinestatic

Returns the number of elements currently stored in the list.

Parameters

list the list

Returns: the number of currently stored elements

◆ cxListSort()

static void cxListSort ( CxList * list )

inlinestatic

Sorts the list.

Remarks: The underlying sort algorithm is implementation defined.

Parameters

list the list

◆ cxListSwap()

static int cxListSwap	(	CxList *	list,
		size_t	i,
		size_t	j )

inlinestatic

Swaps two items in the list.

Implementations should only allocate temporary memory for the swap, if it is necessary.

Parameters

list	the list
i	the index of the first element
j	the index of the second element

Return values

zero	success
non-zero	one of the indices is out of bounds or the swap needed extra memory but allocation failed

Variable Documentation

◆ cxEmptyList

CxList* const cxEmptyList

extern

A shared instance of an empty list.

Writing to that list is not allowed.

You can use this is a placeholder for initializing CxList pointers for which you do not want to reserve memory right from the beginning.

Data Structures

Typedefs

Functions

Variables

Detailed Description

Function Documentation

◆ cx_list_default_insert_array()

◆ cx_list_default_insert_sorted()

◆ cx_list_default_sort()

◆ cx_list_default_swap()

◆ cx_list_init()

◆ cxListAdd()

◆ cxListAddArray()

◆ cxListAt()

◆ cxListBackwardsIterator()

◆ cxListBackwardsIteratorAt()

◆ cxListClear()

◆ cxListCompare()

◆ cxListFind()

◆ cxListFindRemove()

◆ cxListFree()

◆ cxListIndexValid()

◆ cxListInsert()

◆ cxListInsertAfter()

◆ cxListInsertArray()

◆ cxListInsertBefore()

◆ cxListInsertSorted()

◆ cxListInsertSortedArray()

◆ cxListIterator()

◆ cxListIteratorAt()

◆ cxListMutBackwardsIterator()

◆ cxListMutBackwardsIteratorAt()

◆ cxListMutIterator()

◆ cxListMutIteratorAt()

◆ cxListRemove()

◆ cxListRemoveAndGet()

◆ cxListRemoveArray()

◆ cxListRemoveArrayAndGet()

◆ cxListReverse()

◆ cxListSize()

◆ cxListSort()

◆ cxListSwap()

Variable Documentation

◆ cxEmptyList