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,
        cx_compare_func comparator, size_t elem_size,
        size_t initial_capacity);
        
CxList *cxArrayListCreateSimple(size_t elem_size,
        size_t initial_capacity);
```

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

## Declare Array with Size and Capacity

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

#define CX_ARRAY_DECLARE_SIZED(type, name, size_type)

#define CX_ARRAY_DECLARE(type, name)

#define cx_array_initialize(ARRAY, capacity)

#define cx_array_initialize_a(allocator, ARRAY, capacity)
```

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

The raw functions do not need this information packed into a structure, but working with independent variables is quite cumbersome.
Therefore, UCX defines several macros that call the raw functions assuming certain variable names.

This is what the `CX_ARRAY_DECLARE_SIZED()` and `CX_ARRAY_DECLARE()` macros are for.
They take a `type` for the array members, a `name` for the array variable, and a `size_type` for the type of the size and capacity variables (`size_t` by default when you use `CX_ARRAY_DECLARE()`),
and generate three variables named `name`, `name_size`, and `name_capacity`.

For example, you can abbreviate the following code
```C
struct my_data {
    int other_int;
    float other_float;
    int *my_array;
    size_t my_array_size;
    size_t my_array_capacity;
}
```
by substituting the three members for the array with `CX_ARRAY_DECLARE()`.
```C
struct my_data {
    int other_int;
    float other_float;
    CX_ARRAY_DECLARE(int, my_array);
}
```

> Using `CX_ARRAY_DECLARE_SIZED()` can save some space when you are using a size type that is _half_ as wide as `sizeof(void*)`.
> On 64-bit architectures, having the possibility to store more than four billion items is rarely necessary, hence using 32-bit integers for size and capacity
> saves eight bytes (assuming proper alignment in your struct).

Once the array is declared, you can use one of the macros `cx_array_initialize()` or `cx_array_initialize_a()` to allocate memory.
The former uses a stdlib default allocator and the latter allows you to use a specific allocator.
Important to note is, that the `ARRAY` argument expects the variable's _name_.
The macros set `ARRAY_size` to zero, `ARRAY_capacity` to the specified initial capacity, and invoke the allocator's `malloc()` function to allocate the memory.

Using the example from above, and the UCX [memory pool](mempool.h.md), this could look like this:

```C
CxMempool *mpool = cxMempoolCreateSimple(128);

struct my_data data;
cx_array_initialize_a(mpool->allocator, data.my_array, 16);
```

> The aforementioned macros make your life simpler, but keep in mind that using them is not mandatory.
> All other macros continue to work perfectly, if you declare and initialize your array manually, as long as you use
> the naming convention to suffix the size variable with `_size` and the capacity variable with `_capacity`.
> Also you can freely decide in which order you want to declare the variables.
> 
> For example, when you have multiple arrays in your struct with 8-bit `size_type` (because in your use case you don't expect more than 255 elements),
> it is favorable to group all pointers and then declare the size and capacity variables to avoid padding between the array declarations. 

## Array Reallocator

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

typedef struct {
    void *(*realloc)(void *array, size_t capacity, size_t elem_size,
            CxArrayReallocator *alloc);
    void *ptr1;
    void *ptr2;
    size_t int1;
    size_t int2;
} CxArrayReallocator;

CxArrayReallocator cx_array_reallocator(
        const struct cx_allocator_s *allocator,
        const void *stackmem
);
```

<warning>
TODO: document
</warning>

## Add Elements

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

int cx_array_add(void **target, void *size, void *capacity,
        size_t elem_size, const void *elem,
        CxArrayReallocator *reallocator);

#define cx_array_simple_add(ARRAY, elem)

#define cx_array_simple_add_a(reallocator, ARRAY, elem)
```

<warning>
TODO: document
</warning>

## Reserve

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

int cx_array_reserve(
        void **array, void *size, void *capacity, unsigned width,
        size_t elem_size, size_t elem_count,
        CxArrayReallocator *reallocator);

#define cx_array_simple_reserve(ARRAY, count)
#define cx_array_simple_reserve_a(reallocator, ARRAY, count)
```

<warning>
TODO: document
</warning>

## Copy

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

int cx_array_copy(
        void **target, void *size, void *capacity, unsigned width,
        size_t index, const void *src,
        size_t elem_size, size_t elem_count,
        CxArrayReallocator *reallocator);

#define cx_array_simple_copy(ARRAY, index, src, count)

#define cx_array_simple_copy_a(reallocator, ARRAY, index, src, count)
```

<warning>
TODO: outdated - rewrite
</warning>

The `target` argument is a pointer to the target array pointer.
The reason for this additional indirection is that this function writes
back the pointer to the possibly reallocated array.
The next two arguments are pointers to the `size` and `capacity` of the target array for which the width
(in bits) is specified in the `width` argument.

On a successful invocation, the function copies `elem_count` number of elements, each of size `elem_size` from
`src` to `*target` and uses the `reallocator` to extend the array when necessary.
Finally, the size, capacity, and the pointer to the array are all updated and the function returns zero.

A few things to note:
* `*target` and `src` can point to the same memory region, effectively copying elements within the array with `memmove`
* `*target` does not need to point to the start of the array, but `size` and `capacity` always start counting from the
  position, `*target` points to - in this scenario, the need for reallocation must be avoided for obvious reasons
* `index` does not need to be within size of the current array
* `index` does not even need to be within the capacity of the array
* `width` must be one of 8, 16, 32, 64 (only on 64-bit systems), or zero (in which case the native word width is used)

## Insertion Sort

```C
int cx_array_insert_sorted(
        void **target, size_t *size, size_t *capacity,
        cx_compare_func cmp_func,
        const void *src, size_t elem_size, size_t elem_count,
        CxArrayReallocator *reallocator);

#define cx_array_simple_insert_sorted(ARRAY,
        src, elem_count, cmp_func)

#define cx_array_simple_insert_sorted_a(reallocator, ARRAY,
        src, elem_count, cmp_func)

int cx_array_add_sorted(
        void **target, size_t *size, size_t *capacity,
        size_t elem_size, const void *elem,
        cx_compare_func cmp_func,
        CxArrayReallocator *reallocator);

#define cx_array_simple_add_sorted(ARRAY,
        elem, cmp_func)

#define cx_array_simple_add_sorted_a(reallocator, ARRAY,
        elem, cmp_func)
```

<warning>
TODO: document
</warning>

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

<warning>
TODO: document
</warning>

## Iterators

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

CxIterator cxIterator(const void *array,
        size_t elem_size, size_t elem_count);
        
CxIterator cxMutIterator(void *array,
        size_t elem_size, size_t elem_count, bool remove_keeps_order);
        
CxIterator cxIteratorPtr(const void *array, size_t elem_count);
        
CxIterator cxMutIteratorPtr(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
);
```

<warning>
TODO: document
</warning>

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