Mercurial > hg > ucx / file revision

# List Interface

<warning>
Outdated Section - will be updated soon!
</warning>

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

UCX already comes with two common list implementations ([linked list](linked_list.h.md) and [array list](array_list.h.md))
that should cover most use cases.
But if you feel the need to implement an own list, you will find instructions [below](#implement-own-list-structures).

```C
#include <cx/linked_list.h>

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

#include <cx/array_list.h>

CxList *cxArrayListCreate(const CxAllocator *allocator,
        cx_compare_func comparator, size_t elem_size,
        size_t initial_capacity);
        
CxList *cxArrayListCreateSimple(size_t elem_size,
        size_t initial_capacity);
```

The function `cxLinkedListCreate()` creates a new linked list with the specified `allocator` which stores elements of size `elem_size`.
The elements are supposed to be compared with the specified `comparator` (cf. [](#access-and-find)). 
The function `cxLinkedListCreateSimple()` will use the stdlib default allocator and does not specify a compare function. 

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.

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.

> When you create a list which is storing pointers and do not specify a compare function, `cx_cmp_ptr` will be used by default.

## Example

<warning>
TODO: add example how to work with lists
</warning>

> If you want to lazy-initialize lists, you can use the global `cxEmptyList` symbol as a placeholder instead of using a `NULL`-pointer.
> While you *must not* insert elements into that list, you can safely access this list or create iterators.
> This allows you to write clean code without checking for `NULL`-pointer everywhere.
> You still need to make sure that the placeholder is replaced with an actual list before inserting elements.

## Insert

```C
#include <cx/list.h>

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

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

int cxListInsertSorted(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);

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`,
and `cxListInsertSorted()` adds the element at the correct position so that the list remains sorted according to the list's compare function.

When you are currently iterating through a list, you can insert items before or after the current position of the iterator
with `cxListInsertBefore()` or `cxListInsertAfter()`, respectively.
This _should_ be done with [mutating iterators](iterator.h.md#mutating-iterators) only, but is also defined for normal iterators.

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.

On the other hand the `array` argument for `cxListAddArray()`, `cxListInsertArray()`, and `cxListInsertSortedArray()`
must always point to an array of elements to be added (i.e. either an array of pointers, or an array of actual elements).

A special requirement for `cxListInsertSortedArray()` is, that the `array` must already be sorted.

> Implementations are required to optimize the insertion of a sorted array into a sorted list in linear time,
> while inserting each element separately via `cxListInsertSorted()` may take quadratic time.

> The functions `cxListInsertSorted()` and `cxListInsertSortedArray()` do neither check if the list is already sorted, nor do they actively sort the list.
> {style="note"}

## Access and Find

<link-summary>Functions for searching and accessing elements.</link-summary>

```C
#include <cx/list.h>

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

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

size_t cxListFindRemove(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 element at the specified index is returned.
If the index is out-of-bounds, the function returns `NULL`.

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.

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

## Remove

```C
#include <cx/list.h>

int cxListRemove(CxList *list, size_t index);

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

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

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

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](collection.h.md#destructor-functions) are called.

On the other hand, `cxListRemoveAndGet()` and `cxListRemoveArrayAndGet()` 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 `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`.

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

```C
#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);

CxIterator cxListMutIterator(CxList *list);

CxIterator cxListMutBackwardsIterator(CxList *list);

CxIterator cxListMutIteratorAt(CxList *list, size_t index);

CxIterator cxListMutBackwardsIteratorAt(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.

The functions with `Mut` in are equivalently, except that they create a [mutating iterator](iterator.h.md#mutating-iterators).
Removing elements via a mutating iterator will cause an invocation of the [destructor functions](collection.h.md#destructor-functions) for the removed element. 

If is safe to specify an out-of-bounds index in which case an iterator is returned for which `cxIteratorValid()` returns `false`, immediately.

## Reorder

```C
#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](install.md#small-buffer-optimizations) when swapping elements.

> An invocation of `cxListSort` sets the `sorted` flag of the [collection](collection.h.md).
> Implementations usually make use of this flag to optimize search operations, if possible.
> For example the [array list](array_list.h.md) implementation will use binary search
> for `cxListFind()` and similar operations, when the list is sorted.

## Compare

```C
#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 compare functions of both lists are equivalent.

That means, you can compare an UCX [array list](array_list.h.md) with a [linked list](linked_list.h.md),
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 both the compare functions and the list classes are identical.
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. 

## Dispose

```C
#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](collection.h.md#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 exist 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

<warning>
TODO: add documentation
</warning>

<seealso>
<category ref="apidoc">
<a href="https://ucx.sourceforge.io/api/list_8h.html">list.h</a>
</category>
</seealso>