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

<warning>
TODO: document
</warning>

## 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>

cx_array_add(target, size, capacity, elem_size, elem, 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>