Mercurial > hg > ucx / file revision

# 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, const void *element);

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

int cx_array_insert(CxArray array, size_t index, const void *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, const void *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, const void *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.

> 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"}

## Insertion Sort

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

int cx_array_insert_sorted(CxArray array,
        cx_compare_func cmp_func, const void *element);

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

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

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

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,
        cx_compare_func cmp_func, const void *element);

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

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

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

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

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.

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