docs/Writerside/topics/array_list.h.md

# Array List

Next to an array list implementation of the list interface,
UCX offers several functions to work with plain C arrays equipped with a size and a capacity.

The high-level [list interface](list.h.md) is documented on a separate page and explains how lists are used
that are created by one of the following functions.

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

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

The remaining documentation on this page concentrates on dealing with plain C arrays.

## Declaring and Initializing

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

#define CX_ARRAY(type, name)

int cx_array_init(CxArray array, size_t capacity);

int cx_array_init_a(const CxAllocator *allocator,
        CxArray array, size_t capacity);

void cx_array_init_fixed(CxArray array,
        void *fixed_size_array, size_t num_initialized);
```

The purpose of the UCX array functions is to keep track of the size and capacity of a plain C array.

The `CX_ARRAY()` macro declares a variable over an anonymous struct which is compatible to `CxArray`.
The thus created struct contains the three members `data`, `size`, and `capacity`.
You can then pass a pseudo-reference to this variable to any of the UCX array functions.
This is realized by macros which will automatically take the address of your variable and cast it to a pointer of `CxArray`.

Once the array is declared, you can use one of `cx_array_init()`, `cx_array_init_a()`, or `cx_array_init_fixed()` to initialize it.

The former two functions allocate memory for the array using the [default allocator](allocator.h.md#default-allocator) or the allocator passed to the function.
They return zero on success and non-zero on allocation failure.

The latter function initializes the array with a fixed-sized array.
The `num_initialized` argument specifies the number of elements that are already initialized in the array.
This is useful, for example, if you want to initialize the array with stack memory and only want to
allocate memory if the capacity you reserved on the stack is not sufficient.
More on this in the following section, when discussing `cx_array_copy_to_new()`.

## Reallocation

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

int cx_array_reserve(CxArray array, size_t capacity);

int cx_array_copy_to_new(CxArray array, size_t capacity);

int cx_array_reserve_a(const CxAllocator *allocator,
        CxArray array, size_t capacity);

int cx_array_copy_to_new_a(const CxAllocator *allocator,
        CxArray array, size_t capacity);
```

The functions `cx_array_reserve()` and `cx_array_reserve_a()` change the capacity of the array to exactly `capacity` elements.
If the current `size` is larger than `capacity`, the array is truncated to `capacity`.

The functions `cx_array_copy_to_new()` and `cx_array_copy_to_new_a()` allocate a new memory block with the specified capacity
and copy the elements of the old memory to the new memory.

> The functions `cx_array_copy_to_new()` and `cx_array_copy_to_new_a()` do **not** free the old memory.
> If the old memory is not located on the stack, or you don't have another reference to it, it will be leaked.
> The functions are particularly useful when the array was initialized with a fixed-sized array.
>{style="note"}

## Add or Insert Elements

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

int cx_array_add(CxArray array, Any element);

int cx_array_add_array(CxArray array, const void *other, size_t n);

int cx_array_insert(CxArray array, size_t index, Any element);

int cx_array_insert_array(CxArray array,
        size_t index, const void *other, size_t n);

int cx_array_add_a(const CxAllocator* allocator,
        CxArray array, Any element);

int cx_array_add_array(const CxAllocator* allocator,
        CxArray array, const void *other, size_t n);

int cx_array_insert_a(const CxAllocator* allocator,
        CxArray array, size_t index, Any element);

int cx_array_insert_array_a(const CxAllocator* allocator,
        CxArray array, size_t index, const void *other, size_t n);
```

The above functions insert one or more elements into the array at the specified `index`
or add them to the end of the array.

When the array capacity is not sufficient, a re-allocation is attempted.
If the allocation fails, the function returns non-zero.

> Since the "functions" are actually macros, the variants which add or insert one single element
> also conveniently take the address of the passed argument, so you don't have to do it.
> This is why the type is specified as `Any` instead of `const void*` here.

> Be careful when using these functions on an array that was initialized with fixed-sized memory.
> In this case, you MUST make sure that the capacity is sufficient or reallocate the array
> with `cx_array_copy_to_new()` or `cx_array_copy_to_new_a()` before adding or inserting more elements.
>{style="note"}

## Remove Elements

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

void cx_array_remove(CxArray array, size_t index);

void cx_array_remove_fast(CxArray array, size_t index);

void cx_array_remove_array(CxArray array, size_t index, size_t n);

void cx_array_remove_array_fast(CxArray array, size_t index, size_t n);
```

The functions `cx_array_remove()` and `cx_array_remove_array()` remove one or more elements from the array by shifting the remaining elements by the number of removed elements.
The functions `cx_array_remove_fast()` and `cx_array_remove_array_fast()` on the other hand copy elements from the end of the array into the gap to fill the removed elements.
Therefore, if the order of the elements does not matter, you can use the fast versions of these functions for better performance.

> When you specify an `index` that is out-of-bounds or choose a number `n` of elements that would overflow the array,
> the above functions only remove as many elements as possible.
> So it's safe to use them without any bounds checking.

## Sorting

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

void cx_array_qsort_c(void *array, size_t nmemb, size_t size,
        cx_compare_func2 fn, void *context);

void cx_array_sort(CxArray array, cx_compare_func fn);
        
void cx_array_sort_c(CxArray array,
        cx_compare_func2 fn, void *context);
```

With simple `cx_compare_func` functions, arrays can always be sorted with standard `qsort()`.
Sorting arrays with `cx_compare_func2` functions, however, need special support by either `qsort_r()` (GNU) or `qsort_s()` (ISO).
However, both functions come with their own challenges.
On the one hand, `qsort_r()` is not ISO standard, and on the other hand `qsort_s()` is only optional and has an incorrect parameter order in the Microsoft C library.

To provide a platform independent solution, UCX detects if `qsort_r()` is available and implements a fallback when it is not.
You can safely use `cx_array_qsort_c()` everywhere wehere you would use `qsort_r()`.

The functions `cx_array_sort()` and `cx_array_sort_c()` are for convenient work with arrays declared with `CX_ARRAY()`.

## Insertion Sort

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

int cx_array_insert_sorted(CxArray array, Any element,
        cx_compare_func cmp_func);

int cx_array_insert_sorted_array(CxArray array,
        const void *sorted_data, size_t n,
        cx_compare_func cmp_func);

int cx_array_insert_sorted_a(const CxAllocator *allocator,
        CxArray array, Any element,
        cx_compare_func cmp_func);

int cx_array_insert_sorted_array_a(const CxAllocator *allocator,
        CxArray array, const void *sorted_data, size_t n,
        cx_compare_func cmp_func);

int cx_array_insert_sorted_c(CxArray array, Any element,
        cx_compare_func2 cmp_func, void *context);

int cx_array_insert_sorted_array_c(CxArray array,
        const void *sorted_data, size_t n,
        cx_compare_func2 cmp_func, void *context);

int cx_array_insert_sorted_ca(const CxAllocator *allocator,
        CxArray array, Any element,
        cx_compare_func2 cmp_func, void *context);

int cx_array_insert_sorted_array_ca(const CxAllocator *allocator,
        CxArray array, const void *sorted_data, size_t n,
        cx_compare_func2 cmp_func, void *context);
```

The above functions are equivalent to `cx_array_insert()` and `cx_array_insert_array()`,
except that they only work on sorted arrays and insert the element at the correct position with respect to the sort order.
If either the array or the `sorted_data` is not sorted according to the given `cmp_func`, the behavior is undefined.

## Insert Unique Elements

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

int cx_array_insert_unique(CxArray array, Any element,
        cx_compare_func cmp_func);

int cx_array_insert_unique_array(CxArray array,
        const void *sorted_data, size_t n,
        cx_compare_func cmp_func);

int cx_array_insert_unique_a(const CxAllocator *allocator,
        CxArray array, Any element,
        cx_compare_func cmp_func);

int cx_array_insert_unique_array_a(const CxAllocator *allocator,
        CxArray array, const void *sorted_data, size_t n,
        cx_compare_func cmp_func);

int cx_array_insert_unique_c(CxArray array, Any element,
        cx_compare_func2 cmp_func, void *context);

int cx_array_insert_unique_array_c(CxArray array,
        const void *sorted_data, size_t n,
        cx_compare_func2 cmp_func, void *context);

int cx_array_insert_unique_ca(const CxAllocator *allocator,
        CxArray array, Any element,
        cx_compare_func2 cmp_func, void *context);

int cx_array_insert_unique_array_ca(const CxAllocator *allocator,
        CxArray array, const void *sorted_data, size_t n,
        cx_compare_func2 cmp_func, void *context);
```

The above functions are similar to the functions for insertion sort,
except that they only insert elements that are not already present in the array.

## Binary Search

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

size_t cx_array_binary_search(
        const void *arr, size_t size, size_t elem_size,
        const void *elem, cx_compare_func cmp_func);

size_t cx_array_binary_search_inf(
        const void *arr, size_t size, size_t elem_size,
        const void *elem, cx_compare_func cmp_func);

size_t cx_array_binary_search_sup(
        const void *arr, size_t size, size_t elem_size,
        const void *elem, cx_compare_func cmp_func);

size_t cx_array_binary_search_c(
        const void *arr, size_t size, size_t elem_size,
        const void *elem, cx_compare_func2 cmp_func, void *context);

size_t cx_array_binary_search_inf_c(
        const void *arr, size_t size, size_t elem_size,
        const void *elem, cx_compare_func2 cmp_func, void *context);

size_t cx_array_binary_search_sup_c(
        const void *arr, size_t size, size_t elem_size,
        const void *elem, cx_compare_func2 cmp_func, void *context);
```

The function `cx_array_binary_search()` searches the array `arr` for the data pointed to by `elem` using the compare function `cmp_func`.

Note that these functions do not operate on `CxArray` and are instead more general and also useful on plain C arrays.

If the element is found (i.e. `cmp_func` returns zero), the function returns the index of the element.
Otherwise, the function returns `size`.

The functions `cx_array_binary_search_inf()` and `cx_array_binary_search_sup()` are equivalent,
except that they return the index of the closest element if the searched element is not found.
The former function returns the closest element that is less or equal (the greatest lower bound / infimum),
and the latter function returns the closest element that is larger or equal (the least upper bound / supremum)
than the searched element.

When the found element appears more than once in the array,
the binary search and the infimum report the largest index
and the supremum reports the smallest index of the identical items, respectively.

The function variants with the `_c` suffix allow additional `context` for the compare function.

> Note that all the above functions are only well-defined on arrays which are sorted with respect to the given compare function.
> 
> This can, for example, easily be achieved by calling the standard library's `qsort()` or `qsort_s()` function.
>{style="note"}

> Despite the name, neither C nor POSIX standards require the standard library's `bsearch()` function to be implemented using binary search.
> But observations show that it usually is.
> This makes `cx_array_binary_search()` likely to be equivalent to `bsearch()`, except that it returns an index rather than a pointer.

## Iterators

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

CxIterator cxIterator(const void *array,
        size_t elem_size, size_t elem_count,
        bool remove_keeps_order);
       
CxIterator cxIteratorPtr(const void *array,
        size_t elem_count,
        bool remove_keeps_order);
```

Iterators over plain C arrays are defined in [iterator.h](iterator.h.md#creating-an-iterator).

## Other

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

void cx_array_swap(
        void *arr,
        size_t elem_size,
        size_t idx1,
        size_t idx2
);
```

The function `cx_array_swap()` exchanges two items with a three-way swap.

No memory is allocated if the element size `elem_size` is not larger than `CX_ARRAY_SWAP_SBO_SIZE` (cf. [](install.md#small-buffer-optimizations)).

You have to make sure that both indices are within bounds of the array `arr`. 

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