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...

Macros
#define	cxListPopFront(list, targetbuf)
	Removes and returns the first element of the list.

#define	cxListPop(list, targetbuf)
	Removes and returns the last element of the list.

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.

size_t	cx_list_default_insert_unique (struct cx_list_s list, const void sorted_data, size_t n)
	Default implementation of an array insert where only elements are inserted when they don't exist in the list.

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.

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

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

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

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

void *	cxListEmplaceAt (CxList *list, size_t index)
	Allocates memory for an element at the specified index and returns a pointer to that memory.

void *	cxListEmplace (CxList *list)
	Allocates memory for an element at the end of the list and returns a pointer to that memory.

CxIterator	cxListEmplaceArrayAt (CxList *list, size_t index, size_t n)
	Allocates memory for multiple elements and returns an iterator.

CxIterator	cxListEmplaceArray (CxList *list, size_t n)
	Allocates memory for multiple elements and returns an iterator.

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

int	cxListInsertUnique (CxList list, const void elem)
	Inserts an item into a list if it does not exist.

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

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

size_t	cxListInsertUniqueArray (CxList list, const void array, size_t n)
	Inserts an array into a list, skipping duplicates.

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

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

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

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

int	cxListRemoveAndGetFirst (CxList list, void targetbuf)
	Removes and returns the first element of the list.

int	cxListRemoveAndGetLast (CxList list, void targetbuf)
	Removes and returns the last element of the list.

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

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

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

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

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

void *	cxListFirst (const CxList *list)
	Returns a pointer to the first element.

void *	cxListLast (const CxList *list)
	Returns a pointer to the last element.

int	cxListSet (CxList list, size_t index, const void elem)
	Sets the element at the specified index in the list.

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

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

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

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

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

bool	cxListContains (const CxList list, const void elem)
	Checks if the list contains the specified element.

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

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

void	cxListSort (CxList *list)
	Sorts the list.

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.

int	cxListClone (CxList dst, const CxList src, cx_clone_func clone_func, const CxAllocator clone_allocator, void data)
	Performs a deep clone of one list into another.

int	cxListDifference (CxList dst, const CxList minuend, const CxList subtrahend, cx_clone_func clone_func, const CxAllocator clone_allocator, void *data)
	Clones elements from a list only if they are not present in another list.

int	cxListIntersection (CxList dst, const CxList src, const CxList other, cx_clone_func clone_func, const CxAllocator clone_allocator, void *data)
	Clones elements from a list only if they are also present in another list.

int	cxListUnion (CxList dst, const CxList src, const CxList other, cx_clone_func clone_func, const CxAllocator clone_allocator, void *data)
	Performs a deep clone of one list into another, skipping duplicates.

int	cxListCloneSimple (CxList dst, const CxList src)
	Performs a shallow clone of one list into another.

int	cxListDifferenceSimple (CxList dst, const CxList minuend, const CxList *subtrahend)
	Clones elements from a list only if they are not present in another list.

int	cxListIntersectionSimple (CxList dst, const CxList src, const CxList *other)
	Clones elements from a list only if they are also present in another list.

int	cxListUnionSimple (CxList dst, const CxList src, const CxList *other)
	Performs a deep clone of one list into another, skipping duplicates.

int	cxListReserve (CxList *list, size_t capacity)
	Asks the list to reserve enough memory for a given total number of elements.

int	cxListShrink (CxList *list)
	Advises the list to free any overallocated memory.

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

Macro Definition Documentation

◆ cxListPop

#define cxListPop	(		list,
			targetbuf )

Value:

cxListRemoveAndGetLast((list), (targetbuf))

cxListRemoveAndGetLast

int cxListRemoveAndGetLast(CxList *list, void *targetbuf)

Removes and returns the last element of the list.

Alias for cxListRemoveAndGetLast().

No destructor is called, and instead the element is copied to the targetbuf which MUST be large enough to hold the removed element. If the list is storing pointers, only the pointer is copied to targetbuf.

Parameters

list	(`CxList*`) the list
targetbuf	(`void*`) a buffer where to copy the element

Return values

zero	success
non-zero	the list is empty

See also: cxListRemoveAndGetLast(); cxListPopFront()

◆ cxListPopFront

#define cxListPopFront	(		list,
			targetbuf )

Value:

cxListRemoveAndGetFirst((list), (targetbuf))

cxListRemoveAndGetFirst

int cxListRemoveAndGetFirst(CxList *list, void *targetbuf)

Removes and returns the first element of the list.

Alias for cxListRemoveAndGetFirst().

No destructor is called, and instead the element is copied to the targetbuf which MUST be large enough to hold the removed element. If the list is storing pointers, only the pointer is copied to targetbuf.

Parameters

list	(`CxList*`) the list
targetbuf	(`void*`) a buffer where to copy the element

Return values

zero	success
non-zero	the list is empty

See also: cxListRemoveAndGetFirst(); cxListPop()

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_insert_unique()

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

Default implementation of an array insert where only elements are inserted when they don't exist in the list.

This function is similar to cx_list_default_insert_sorted(), except it skips elements that are already in the list.

Note: The return value of this function denotes the number of elements from the sorted_data that are definitely contained in the list after completing the call. It is not the number of elements that were newly inserted. That means, when no error occurred, the return value should be n.

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 from the sorted_data that are definitely present in the list after this call

◆ 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()

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

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(); cxListEmplace()

◆ cxListAddArray()

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

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

See also: cxListEmplaceArray()

◆ cxListAt()

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

Returns a pointer to the element at the specified index.

If the list is storing pointers, returns the pointer stored 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()

CxIterator cxListBackwardsIterator ( const CxList * list )

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

The returned iterator is position-aware.

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

Parameters

list the list

Returns: a new iterator

◆ cxListBackwardsIteratorAt()

CxIterator cxListBackwardsIteratorAt	(	const CxList *	list,
		size_t	index )

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 or list is NULL, 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()

void cxListClear ( CxList * list )

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

◆ cxListClone()

int cxListClone	(	CxList *	dst,
		const CxList *	src,
		cx_clone_func	clone_func,
		const CxAllocator *	clone_allocator,
		void *	data )

Performs a deep clone of one list into another.

If the destination list already contains elements, the cloned elements are appended to that list.

Attention: If the cloned elements need to be destroyed by a destructor function, you must make sure that the destination list also uses this destructor function.

Parameters

dst	the destination list
src	the source list
clone_func	the clone function for the elements
clone_allocator	the allocator that is passed to the clone function
data	optional additional data that is passed to the clone function

Return values

zero	when all elements were successfully cloned
non-zero	when an allocation error occurred

See also: cxListCloneSimple()

◆ cxListCloneSimple()

int cxListCloneSimple	(	CxList *	dst,
		const CxList *	src )

Performs a shallow clone of one list into another.

This function uses the default allocator, if needed, and performs shallow clones with memcpy().

If the destination list already contains elements, the cloned elements are appended to that list.

Attention: If the cloned elements need to be destroyed by a destructor function, you must make sure that the destination list also uses this destructor function.

Parameters

dst	the destination list
src	the source list

Return values

zero	when all elements were successfully cloned
non-zero	when an allocation error occurred

See also: cxListClone()

◆ 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

◆ cxListContains()

bool cxListContains	(	const CxList *	list,
		const void *	elem )

Checks if the list contains the specified element.

The elements are compared with the list's comparator function.

Parameters

list	the list
elem	the element to find

Return values

true	if the element is contained
false	if the element is not contained

See also: cxListFind()

◆ cxListDifference()

int cxListDifference	(	CxList *	dst,
		const CxList *	minuend,
		const CxList *	subtrahend,
		cx_clone_func	clone_func,
		const CxAllocator *	clone_allocator,
		void *	data )

Clones elements from a list only if they are not present in another list.

If the minuend does not contain duplicates, this is equivalent to adding the set difference to the destination list.

This function is optimized for the case when both the minuend and the subtrahend are sorted.

Parameters

dst	the destination list
minuend	the list to subtract elements from
subtrahend	the elements that shall be subtracted
clone_func	the clone function for the elements
clone_allocator	the allocator that is passed to the clone function
data	optional additional data that is passed to the clone function

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

See also: cxListDifferenceSimple()

◆ cxListDifferenceSimple()

int cxListDifferenceSimple	(	CxList *	dst,
		const CxList *	minuend,
		const CxList *	subtrahend )

Clones elements from a list only if they are not present in another list.

This function uses the default allocator, if needed, and performs shallow clones with memcpy().

If the minuend does not contain duplicates, this is equivalent to adding the set difference to the destination list.

This function is optimized for the case when both the minuend and the subtrahend are sorted.

Parameters

dst	the destination list
minuend	the list to subtract elements from
subtrahend	the elements that shall be subtracted

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

See also: cxListDifference()

◆ cxListEmplace()

void * cxListEmplace ( CxList * list )

Allocates memory for an element at the end of the list and returns a pointer to that memory.

Remarks: When the list is storing pointers, this will return a void**.

Parameters

list the list

Returns: a pointer to the allocated memory; NULL when the operation fails, or the index is out-of-bounds

See also: cxListEmplaceAt(); cxListAdd()

◆ cxListEmplaceArray()

CxIterator cxListEmplaceArray	(	CxList *	list,
		size_t	n )

Allocates memory for multiple elements and returns an iterator.

The iterator will only iterate over the successfully allocated elements. The elem_count attribute is set to that number, and the index attribute will range from zero to elem_count minus one.

Remarks: When the list is storing pointers, the iterator will iterate over the void** elements.

Parameters

list	the list
n	the number of elements for which to allocate the memory

Returns: an iterator, iterating over the new memory

See also: cxListEmplace(); cxListAddArray()

◆ cxListEmplaceArrayAt()

CxIterator cxListEmplaceArrayAt	(	CxList *	list,
		size_t	index,
		size_t	n )

Allocates memory for multiple elements and returns an iterator.

The iterator will only iterate over the successfully allocated elements. The elem_count attribute is set to that number, and the index attribute will range from zero to elem_count minus one.

Remarks: When the list is storing pointers, the iterator will iterate over the void** elements.

Parameters

list	the list
index	the index where to insert the new data
n	the number of elements for which to allocate the memory

Returns: an iterator, iterating over the new memory

See also: cxListEmplaceAt(); cxListInsertArray()

◆ cxListEmplaceAt()

void * cxListEmplaceAt	(	CxList *	list,
		size_t	index )

Allocates memory for an element at the specified index and returns a pointer to that memory.

Remarks: When the list is storing pointers, this will return a void**.

Parameters

list	the list
index	the index where to emplace the element

Returns: a pointer to the allocated memory; NULL when the operation fails, or the index is out-of-bounds

See also: cxListEmplace(); cxListEmplaceArrayAt(); cxListInsert()

◆ cxListFind()

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

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(); cxListContains()

◆ cxListFindRemove()

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

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

◆ cxListFirst()

void * cxListFirst ( const CxList * list )

Returns a pointer to the first element.

If the list is storing pointers, returns the first pointer stored in the list.

Parameters

list the list

Returns: a pointer to the first element or NULL if the list is empty

◆ 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 that shall be freed

◆ cxListIndexValid()

bool cxListIndexValid	(	const CxList *	list,
		size_t	index )

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

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

Inserts an item at the specified index.

If the 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(); cxListEmplaceAt()

◆ cxListInsertAfter()

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

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

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

Inserts multiple items to the list at the specified index.

If the 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

See also: cxListEmplaceArrayAt()

◆ cxListInsertBefore()

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

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

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

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

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

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

◆ cxListInsertUnique()

int cxListInsertUnique	(	CxList *	list,
		const void *	elem )

Inserts an item into a list if it does not exist.

If the list is not sorted already, this function will check all elements and append the new element when it was not found. It is strongly recommended to use this function only on sorted lists, where the element, if it is not contained, is inserted at the correct position.

Parameters

list	the list
elem	a pointer to the element to add

Return values

zero	success (also when the element was already in the list)
non-zero	memory allocation failure

◆ cxListInsertUniqueArray()

size_t cxListInsertUniqueArray	(	CxList *	list,
		const void *	array,
		size_t	n )

Inserts an array into a list, skipping duplicates.

The list does not need to be sorted (in contrast to cxListInsertSortedArray()). But it is strongly recommended to use this function only on sorted lists, because otherwise it will fall back to an inefficient algorithm which inserts all elements one by one. If the list is not sorted, the array also does not need to be sorted. But when the list is sorted, the array must also be sorted.

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.

Note: The return value of this function denotes the number of elements from the sorted_data that are definitely contained in the list after completing the call. It is not the number of elements that were newly inserted. That means, when no error occurred, the return value should be 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; the number of elements from the sorted_data that are definitely present in the list after this call

◆ cxListIntersection()

int cxListIntersection	(	CxList *	dst,
		const CxList *	src,
		const CxList *	other,
		cx_clone_func	clone_func,
		const CxAllocator *	clone_allocator,
		void *	data )

Clones elements from a list only if they are also present in another list.

This function is optimized for the case when both the src and the other list are sorted.

If the destination list already contains elements, the intersection is appended to that list.

Parameters

dst	the destination list
src	the list to clone the elements from
other	the list to check the elements for existence
clone_func	the clone function for the elements
clone_allocator	the allocator that is passed to the clone function
data	optional additional data that is passed to the clone function

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

See also: cxListIntersectionSimple()

◆ cxListIntersectionSimple()

int cxListIntersectionSimple	(	CxList *	dst,
		const CxList *	src,
		const CxList *	other )

Clones elements from a list only if they are also present in another list.

This function uses the default allocator, if needed, and performs shallow clones with memcpy().

This function is optimized for the case when both the src and the other list are sorted.

If the destination list already contains elements, the intersection is appended to that list.

Parameters

dst	the destination list
src	the list to clone the elements from
other	the list to check the elements for existence

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

See also: cxListIntersection()

◆ cxListIterator()

CxIterator cxListIterator ( const CxList * list )

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

The returned iterator is position-aware.

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

Parameters

list the list

Returns: a new iterator

◆ cxListIteratorAt()

CxIterator cxListIteratorAt	(	const CxList *	list,
		size_t	index )

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

The returned iterator is position-aware.

If the index is out of range or list is NULL, 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

◆ cxListLast()

void * cxListLast ( const CxList * list )

Returns a pointer to the last element.

If the list is storing pointers, returns the last pointer stored in the list.

Parameters

list the list

Returns: a pointer to the last element or NULL if the list is empty

◆ cxListRemove()

int cxListRemove	(	CxList *	list,
		size_t	index )

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

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

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. If the list is storing pointers, only the pointer is copied to targetbuf.

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

◆ cxListRemoveAndGetFirst()

int cxListRemoveAndGetFirst	(	CxList *	list,
		void *	targetbuf )

Removes and returns the first element of the list.

No destructor is called, and instead the element is copied to the targetbuf which MUST be large enough to hold the removed element. If the list is storing pointers, only the pointer is copied to targetbuf.

Parameters

list	the list
targetbuf	a buffer where to copy the element

Return values

zero	success
non-zero	the list is empty

See also: cxListPopFront(); cxListRemoveAndGetLast()

◆ cxListRemoveAndGetLast()

int cxListRemoveAndGetLast	(	CxList *	list,
		void *	targetbuf )

Removes and returns the last element of the list.

No destructor is called, and instead the element is copied to the targetbuf which MUST be large enough to hold the removed element. If the list is storing pointers, only the pointer is copied to targetbuf.

Parameters

list	the list
targetbuf	a buffer where to copy the element

Return values

zero	success
non-zero	the list is empty

◆ cxListRemoveArray()

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

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

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

Removes and returns multiple elements 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. If the list is storing pointers, targetbuf is expected to be an array of pointers.

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

◆ cxListReserve()

int cxListReserve	(	CxList *	list,
		size_t	capacity )

Asks the list to reserve enough memory for a given total number of elements.

List implementations are free to choose if reserving memory upfront makes sense. For example, array-based implementations usually do support reserving memory for additional elements while linked lists usually don't.

Note: When the requested capacity is smaller than the current size, this function returns zero without performing any action.

Parameters

list	the list
capacity	the expected total number of elements

Return values

zero	on success or when overallocation is not supported
non-zero	when an allocation error occurred

See also: cxListShrink()

◆ cxListReverse()

void cxListReverse ( CxList * list )

Reverses the order of the items.

Parameters

list the list

◆ cxListSet()

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

Sets the element at the specified index in the list.

This overwrites the element in-place without calling any destructor on the overwritten element.

Parameters

list	the list to set the element in
index	the index to set the element at
elem	element to set

Return values

zero	on success
non-zero	when index is out of bounds

◆ cxListShrink()

int cxListShrink ( CxList * list )

Advises the list to free any overallocated memory.

Lists that do not support overallocation simply return zero.

This function usually returns zero, except for very special and custom list and/or allocator implementations where freeing memory can fail.

Parameters

list the list

Returns: usually zero

◆ cxListSize()

size_t cxListSize ( const CxList * list )

Returns the number of elements currently stored in the list.

Parameters

list the list

Returns: the number of currently stored elements

◆ cxListSort()

void cxListSort ( CxList * list )

Sorts the list.

Remarks: The underlying sort algorithm is implementation defined.

Parameters

list the list

◆ cxListSwap()

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

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

◆ cxListUnion()

int cxListUnion	(	CxList *	dst,
		const CxList *	src,
		const CxList *	other,
		cx_clone_func	clone_func,
		const CxAllocator *	clone_allocator,
		void *	data )

Performs a deep clone of one list into another, skipping duplicates.

This function is optimized for the case when both the src and the other list are sorted. In that case, the union will also be sorted.

If the destination list already contains elements, the union is appended to that list. In that case the destination is not necessarily sorted.

Parameters

dst	the destination list
src	the primary source list
other	the other list, where elements are only cloned from when they are not in `src`
clone_func	the clone function for the elements
clone_allocator	the allocator that is passed to the clone function
data	optional additional data that is passed to the clone function

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

See also: cxListUnionSimple()

◆ cxListUnionSimple()

int cxListUnionSimple	(	CxList *	dst,
		const CxList *	src,
		const CxList *	other )

Performs a deep clone of one list into another, skipping duplicates.

This function uses the default allocator, if needed, and performs shallow clones with memcpy().

This function is optimized for the case when both the src and the other list are sorted. In that case, the union will also be sorted.

If the destination list already contains elements, the union is appended to that list. In that case the destination is not necessarily sorted.

Parameters

dst	the destination list
src	the primary source list
other	the other list, where elements are only cloned from when they are not in `src`

Return values

zero	when the elements were successfully cloned
non-zero	when an allocation error occurred

See also: cxListUnion()

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 as a placeholder for initializing CxList pointers for which you do not want to reserve memory right from the beginning.

Data Structures

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ cxListPop

◆ cxListPopFront

Function Documentation

◆ cx_list_default_insert_array()

◆ cx_list_default_insert_sorted()

◆ cx_list_default_insert_unique()

◆ cx_list_default_sort()

◆ cx_list_default_swap()

◆ cx_list_init()

◆ cxListAdd()

◆ cxListAddArray()

◆ cxListAt()

◆ cxListBackwardsIterator()

◆ cxListBackwardsIteratorAt()

◆ cxListClear()

◆ cxListClone()

◆ cxListCloneSimple()

◆ cxListCompare()

◆ cxListContains()

◆ cxListDifference()

◆ cxListDifferenceSimple()

◆ cxListEmplace()

◆ cxListEmplaceArray()

◆ cxListEmplaceArrayAt()

◆ cxListEmplaceAt()

◆ cxListFind()

◆ cxListFindRemove()

◆ cxListFirst()

◆ cxListFree()

◆ cxListIndexValid()

◆ cxListInsert()

◆ cxListInsertAfter()

◆ cxListInsertArray()

◆ cxListInsertBefore()

◆ cxListInsertSorted()

◆ cxListInsertSortedArray()

◆ cxListInsertUnique()

◆ cxListInsertUniqueArray()

◆ cxListIntersection()

◆ cxListIntersectionSimple()

◆ cxListIterator()

◆ cxListIteratorAt()

◆ cxListLast()

◆ cxListRemove()

◆ cxListRemoveAndGet()

◆ cxListRemoveAndGetFirst()

◆ cxListRemoveAndGetLast()

◆ cxListRemoveArray()

◆ cxListRemoveArrayAndGet()

◆ cxListReserve()

◆ cxListReverse()

◆ cxListSet()

◆ cxListShrink()

◆ cxListSize()

◆ cxListSort()

◆ cxListSwap()

◆ cxListUnion()

◆ cxListUnionSimple()

Variable Documentation

◆ cxEmptyList