List Interface

The list.h header defines a common interface for all list implementations.

UCX already comes with two common list implementations (linked list and array list) that should cover most use cases. A more advanced use case is implemented as a key/value list. If you feel the need to implement your own list, you will find the instructions below.

#include <cx/linked_list.h>

CxList *cxLinkedListCreate(const CxAllocator *allocator,
        size_t elem_size);

#include <cx/array_list.h>

CxList *cxArrayListCreate(const CxAllocator *allocator,
        size_t elem_size, size_t initial_capacity);

#include <cx/kv_list.h>

CxList *cxKvListCreate(const CxAllocator *allocator,
        size_t elem_size);

CxMap *cxKvListCreateAsMap(const CxAllocator *allocator,
        size_t elem_size);

The function cxLinkedListCreate() creates a new linked list with the specified allocator which stores elements of size elem_size.

Array lists can be created with cxArrayListCreate() where the additional argument initial_capacity specifies for how many elements the underlying array shall be initially allocated.

The key/value list implements both the list and the map interfaces and allows access to the elements via a key. Depending on the perspective, you can see a key/value list as an associative list or as an ordered map.

If CX_STORE_POINTERS is used as elem_size, the actual element size will be sizeof(void*) and the list will behave slightly differently when accessing elements. Lists that are storing pointers will always return the stored pointer directly, instead of returning a pointer into the list's memory, thus saving you from unnecessary dereferencing. Conversely, when adding elements to the list, the pointers you specify (e.g., in cxListAdd() or cxListInsert()) are directly added to the list, instead of copying the contents pointed to by the argument.

Example

In the following example we create a linked-list of regular expressions for filtering data.

#include <cx/linked_list.h>
#include <regex.h>

CxList *create_pattern_list(void) {
    // create a linked list to store patterns
    // NULL means, the cxDefaultAllocator will be used
    CxList *list = cxLinkedListCreate(NULL, sizeof(regex_t));
    
    // automatically free the pattern when list gets destroyed
    cxSetDestructor(list, regfree);
    
    return list;
}

int add_pattern(CxList *list, const char *value) {
    // compile pattern and add it to the list, if successful
    regex_t regex;
    if (regcomp(&regex, value, REG_EXTENDED|REG_NOSUB)) {
        return 1;
    } else {
        // take address of local variable
        // since we are not storing pointers in this list,
        // we get a copy of the data directly in the list
        cxListAdd(list, &regex);
        return 0;
    }
}

bool matches_any(CxList *list, const char *text) {
    CxIterator iter = cxListIterator(list);
    cx_foreach(regex_t*, pat, iter) {
        if (regexec(pat, text, 0, NULL, 0) == 0) {
            return true;
        }
    }
    return false;
}

If in the above example the list was created with CX_STORE_POINTERS instead of sizeof(regex_t), the add_pattern() function would need to be changed as follows:

int add_pattern(CxList *list, const char *value) {
    // allocate memory here, because now we are storing pointers
    regex_t *regex = malloc(sizeof(regex_t));
    if (!regex || regcomp(regex, value, REG_EXTENDED|REG_NOSUB)) {
        return 1;
    } else {
        cxListAdd(list, regex);
        return 0;
    }
}

Also, just registering regfree() as a destructor is not enough anymore because the regex_t structure also needs to be freed. Therefore, we would need to wrap the calls to regfree() and free() into an own destructor, which we then register with the list. However, it should be clear by now that using CX_STORE_POINTERS is a bad choice for this use case to begin with.

As a rule of thumb: if you allocate memory for an element that you immediately put into the list, consider storing the element directly. And if you are getting pointers to already allocated memory from somewhere else, and you just want to organize those elements in a list, then consider using CX_STORE_POINTERS.

Insert

#include <cx/list.h>

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

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

void *cxListEmplace(CxList *list);

void *cxListEmplaceAt(CxList *list, size_t index);

CxIterator cxListEmplaceArray(CxList *list, size_t n);

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

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

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

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

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

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

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

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

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

The function cxListAdd() appends the element elem to the list and returns zero on success or non-zero when allocating the memory for the element fails. Similarly, cxListInsert() adds the element at the specified index.

The functions cxListEmplace() and cxListEmplaceAt() behave like cxListAdd() and cxListInsert(), except that they only allocate the memory and return a pointer to it, leaving it to the callee to copy the element data into it. The same is true for cxListEmplaceArray() and cxListEmplaceArrayAt(), which allocate memory for n elements and return an iterator to the first element. Be aware that when the list is storing pointers, the allocated memory will be for the pointer, not the actual element's data.

If the list is storing pointers (cf. cxCollectionStoresPointers()), the pointer elem is directly added to the list. Otherwise, the contents at the location pointed to by elem are copied to the list's memory with the element size specified during creation of the list.

When you are currently iterating through a list, you can insert elements before or after the current position of the iterator with cxListInsertBefore() or cxListInsertAfter(), respectively.

The function cxListInsertSorted() inserts the element at the correct position so that the list remains sorted according to the list's compare function. It is important that the list is already sorted before calling this function. On the other hand, cxListInsertUnique() inserts the element only if it is not already in the list. In this case it is strongly recommended that the list is already sorted but not required; the function will fall back to an inefficient algorithm when the list is not sorted.

The array argument for cxListAddArray(), cxListInsertArray(), cxListInsertSortedArray(), and cxListInsertUniqueArray() must always point to an array of elements to be added (i.e., either an array of pointers or an array of actual elements). Here, no auto-magic is implemented, depending on cxCollectionStoresPointers().

The return values of the array-inserting functions are the number of elements that have been successfully processed. Usually this is equivalent to the number of inserted elements, except for cxListInsertUniqueArray(), where the actual number of inserted elements may be lower than the number of successfully processed elements.

Access and Find

Functions for searching and accessing elements.

#include <cx/list.h>

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

void *cxListFirst(const CxList *list);

void *cxListLast(const CxList *list);

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

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

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

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

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

size_t cxListSize(const CxList *list);

The function cxListAt() accesses the element at the specified index. If the list is storing pointers (i.e. cxCollectionStoresPointers() returns true), the pointer at the specified index is directly returned. Otherwise, a pointer to the element at the specified index is returned. If the index is out-of-bounds, the function returns NULL. The functions cxListFirst() and cxListLast() behave like cxListAt(), accessing the first or the last valid index, respectively, and returning NULL when the list is empty.

The function cxListSet() allows you to modify elements at a specific index in the list. This function replaces the element at the specified index with the value pointed to by elem. If the list is storing values directly (not pointers), the contents at the memory location elem will be copied into the list. If the list is storing pointers, the pointer value itself will be stored. The function returns 0 on success and 1 if the index is out of bounds.

On the other hand, cxListFind() searches for the element pointed to by elem by comparing each element in the list with the list's compare function and returns the first index when the element was found. Otherwise, the function returns the list size.

The function cxListFindRemove() behaves like cxListFind(), except that it also removes the first occurrence of the element from the list. This will also call destructor functions, if specified, so take special care when you continue to use elem, or when the list is storing pointers and the element appears more than once in the list.

The function cxListContains() returns true if and only if cxListFind() returns a valid index.

With cxListIndexValid() you can check the index returned by cxListFind() or cxListFindRemove(), which is more convenient than comparing the return value with the return value of cxListSize().

Remove

#include <cx/list.h>

int cxListRemove(CxList *list, size_t index);

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

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

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

int cxListRemoveAndGetFirst(CxList *list, void *targetbuf);

int cxListPopFront(CxList *list, void *targetbuf);

int cxListRemoveAndLast(CxList *list, void *targetbuf);

int cxListPop(CxList *list, void *targetbuf);

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

void cxListClear(CxList *list);

The function cxListRemove() removes the element at the specified index and returns zero, or returns non-zero if the index is out-of-bounds. The function cxListRemoveArray() removes num elements starting at index and returns the number of elements that have been removed. For each removed element, the destructor functions are called.

The function cxListFindRemove() finds the first element within the list that is equivalent to the element pointed to by elem and removes it from the list. This will also call destructor functions, if specified, so take special care when you continue to use elem. This function needs a valid comparator function.

On the other hand, cxListRemoveAndGet() family of functions do not invoke the destructor functions and instead copy the elements into the targetbuf, which must be large enough to hold the removed elements.

The function cxListClear() simply removes all elements from the list, invoking the destructor functions. It behaves equivalently but is usually more efficient than calling cxListRemove() for every index.

Iterators

#include <cx/list.h>

CxIterator cxListIterator(const CxList *list);

CxIterator cxListBackwardsIterator(const CxList *list);

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

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

The functions cxListIterator() and cxListBackwardsIterator() create iterators that start and the first or the last element in the list and iterate through the entire list.

The functions cxListIteratorAt() and cxListBackwardsIteratorAt() start with the element at the specified index and iterate until the end, or the beginning of the list, respectively.

Removing elements via an iterator will cause an invocation of the destructor functions for the removed element.

It is safe to specify an out-of-bounds index, or a NULL pointer, in which cases the returned iterator will behave like an iterator over an empty list.

Reorder

#include <cx/list.h>

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

void cxListReverse(CxList *list);

void cxListSort(CxList *list);

The function cxListSwap() swaps two elements specified by the indices i and j. The return value is non-zero if one of the indices is out-of-bounds.

The function cxListReverse() reorders all elements so that they appear in exactly the opposite order after invoking this function.

The function cxListSort() sorts all elements with respect to the list's compare function, unless the list is already sorted (cf. cxCollectionSorted()), in which case the function immediately returns.

Default UCX implementations of the list interface make use of small buffer optimizations when swapping elements.

Compare

#include <cx/list.h>

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

Arbitrary lists can be compared element-wise with cxListCompare(), as long as the comparator functions of both lists are equivalent.

That means you can compare an UCX array list with a linked list, and you could even compare lists that are storing pointers with lists that are not storing pointers.

However, the optimized list-internal compare implementation is only used when they are identical for both lists. Otherwise, cxListCompare() will behave as if you were iterating through both lists and manually comparing the elements.

The return value of cxListCompare() is zero if the lists are element-wise equivalent. If they are not, the non-zero return value equals the return value of the used compare function for the first pair of elements that are not equal.

Clone

#include <cx/allocator.h>

typedef void*(cx_clone_func)(
        void *target, const void *source,
        const CxAllocator *allocator,
        void *data);

#include <cx/list.h>

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

int cxListCloneShallow(CxList *dst, const CxList *src);

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

int cxListDifferenceShallow(CxList *dst,
        const CxList *minuend, const CxList *subtrahend);

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

int cxListIntersectionShallow(CxList *dst,
        const CxList *src, const CxList *other);

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

int cxListUnionShallow(CxList *dst,
        const CxList *src,  const CxList *other);

With cxListClone() you can create deep copies of the elements in a list and insert them into another list. The destination list does not need to be empty, in which case the elements will be appended. Depending on the concrete list implementation, cxListClone() tries to allocate enough memory up-front before trying to insert anything.

The function cxListDifference() clones elements from the minuend that are not contained in the subtrahend, while cxListIntersection() only clones elements from the src that are also contained in the other list. And cxListUnion() clones elements from src first, and from other only when they are not contained in src.

All three functions, for union, difference, and intersection, are optimized for sorted lists. In that case they will take linear time instead of quadratic time for the operation. Also, cxListUnion() makes sure that the elements from src and other are cloned interleaving, so that the result of the union is still sorted.

However, when the dst list already contains elements, all functions will only append the result of the operation to that list. That means the dst list is only guaranteed to be sorted when it was empty and the input lists are all sorted.

Refer to the documentation of the clone-function callback to learn how to implement it.

The simple versions of the above functions use an internal shallow clone function which uses memcpy() to copy the elements. If the destination map is storing pointers, this internal clone function uses the current default allocator to allocate the memory.

The functions return zero if and only if all clone operations were successful.

Reserve and Shrink

#include <cx/list.h>

int cxListReserve(CxList *list, size_t count);

int cxListShrink(CxList *list);

If a list implementation allows overallocation, the function cxListReserve() can be used to reserve memory for a total of count elements. On the other hand, you can use cxListShrink() to dispose of any overallocated memory and reduce the capacity to the actual number of currently stored elements. Calling cxListReserve() with a count argument that is less than the current size of the list has no effect, and the function returns zero.

If allocating memory fails, cxListReserve() returns a non-zero value. Since shrinking should never fail, cxListShrink() will usually always return zero, but depending on the list (or allocator) implementation, the possibility for a non-zero return value is there.

List implementations that do not overallocate are advised to simply return zero. That means, using those functions never does any harm and calls to them can be added whenever it seems appropriate. Even if the currently used list implementation does not support overallocation, it may become extremely useful when the concrete implementation is exchanged later.

Dispose

#include <cx/list.h>

void cxListFree(CxList *list);

No matter with which function a CxList has been created, you can always deallocate the entire memory with a call to cxListFree().

The effect is equivalent to invoking cxListClear() plus deallocating the memory for the list structure. That means, for each element in the list, the destructor functions are called before deallocating the list.

When the list has been storing pointers, make sure that either another reference to the same memory exists in your program, or any of the destructor functions deallocates the memory. Otherwise, there is a risk of a memory leak.

Implement own List Structures

If you want to create your own list implementation, this is extremely easy.

You need to define a function for creating your list and assign a cx_list_class structure with the pointers to your implementation. Then you call the cx_list_init() helper function to initialize the collection structure. This also automatically adds support for CX_STORE_POINTERS to your list.

// define the class with pointers to your functions
static cx_list_class my_list_class = {
        my_list_deallocate,
        my_list_insert_element,
        my_list_insert_array,
        my_list_insert_sorted,
        my_list_insert_unique,
        my_list_insert_iter,
        my_list_remove,
        my_list_clear,
        my_list_swap,
        my_list_at,
        my_list_find_remove,
        my_list_sort,
        my_list_compare,
        my_list_reverse,
        my_list_change_capacity,
        my_list_iterator,
};

typedef struct {
    struct cx_list_s base;
    // your custom list data goes here
} my_list;

CxList *my_list_create(
        const CxAllocator *allocator,
        size_t elem_size
) {
    if (allocator == NULL) {
        allocator = cxDefaultAllocator;
    }

    my_list *list = cxCalloc(allocator, 1, sizeof(my_list));
    if (list == NULL) return NULL;
    cx_list_init((CxList*)list, &my_list_class,
            allocator, elem_size);
            
    // initialize your custom list data here

    return (CxList *) list;
}

The required behavior for the implementations is described in the following table. You can always look at the source code of the UCX implementations to get inspiration.

Function	Description
`clear`	Invoke destructor functions on all elements and remove them from the list.
`deallocate`	Invoke destructor functions on all elements and deallocate the entire list memory.
`insert_element`	Insert or allocate a single element at the specified index. Return a pointer to the allocated element or `NULL` on failure.
`insert_array`	Insert or allocate an array of elements starting at the specified index. Return the number of successfully inserted or allocated elements.
`insert_sorted`	Insert an array of sorted elements into a sorted list. Return the number of elements processed (equals the number of elements inserted in this case).
`insert_unique`	Insert an array of sorted unique elements into a sorted list. Return the number of elements processed (not the number of elements inserted, which might be lower).
`insert_iter`	Insert a single element depending on the iterator position. The third argument to this function is zero when the element shall be inserted after the iterator position and non-zero if it shall be inserted before the iterator position. The implementation is also responsible for adjusting the iterator, respectively.
`remove`	Remove multiple elements starting at the specified index. If a target buffer is specified, copy the elements to that buffer. Otherwise, invoke the destructor functions for the elements. Return the number of elements actually removed.
`swap`	Swap two elements by index. Return zero on success or non-zero when any index was out-of-bounds.
`at`	Return a pointer to the element at the specified index or `NULL` when the index is out-of-bounds.
`find_remove`	Search for the specified element with the list's compare function and return the index if found. If the `remove` argument is true, invoke the destructor functions and remove the element. Return the list size if the element is not found.
`sort`	Sort all elements in the list with respect to the list's compare function.
`compare`	This function pointer can be `NULL`, in which case an unoptimized fallback is used. You can implement an optimized compare function that compares the list of another list of the same class.
`reverse`	Reorder all elements in the list so that they appear in exactly the opposite order.
`change_capacity`	When your list supports overallocation, the capacity shall be changed to the specified value. Return non-zero on error and zero on success. When the list does not support overallocation, this function pointer can be `NULL`.
`iterator`	Create an iterator starting at the specified index. The Boolean argument indicates whether iteration is supposed to traverse backwards.

Default Class Function Implementations

If you are satisfied with some of the default implementations, you can use some pre-defined functions. Note, however, that those are not optimized for any specific list structure and just serve as a quick and convenient solution if performance does not matter for your use case.

Default Function	Description
`cx_list_default_insert_array`	Falls back to multiple calls of `insert_element`.
`cx_list_default_insert_sorted`	Uses linear search to find insertion points.
`cx_list_default_insert_unique`	Like `cx_default_insert_sorted` but skips elements that are already contained.
`cx_list_default_sort`	Copies all elements to an array, applies `qsort()`, and copies the elements back.
`cx_list_default_swap`	Uses a temporarily allocated buffer to perform a three-way-swap.

20 December 2025