UAP Common Extensions 3.1 Help

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 is documented on a separate page and explains how lists are used that are created by one of the following functions.

#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

#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

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

struct my_data { int other_int; float other_float; CX_ARRAY_DECLARE(int, my_array); }

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, this could look like this:

CxMempool *mpool = cxMempoolCreateSimple(128); struct my_data data; cx_array_initialize_a(mpool->allocator, data.my_array, 16);

Array Reallocator

#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 ); extern CxArrayReallocator* cx_array_default_reallocator;

The main purpose of the functions defined in the array list header, is to make it easier to write to an array without caring too much about a possibly needed reallocation.

This is realized by passing a reallocator to the various functions which specifies how an array shall be reallocated when needed.

The default cx_array_default_reallocator simply defers to the standard library realloc().

A reallocator created with the cx_array_reallocator() function uses a more sophisticated approach. On the one hand, it can use an arbitrary UCX allocator for the reallocation, and on the other hand, it can optionally keep track of a stack memory pointer. If you pass a non-NULL pointer to stackmem, the reallocator will always allocate new memory for the array, if the current location equals the stackmem address.

This allows you to allocate an array on the stack and instruct UCX to automatically move it to heap memory when the capacity is exceeded. Combined with a UCX memory pool this can be a powerful tool for local arrays which are expected to stay within the bounds of the stack memory most of the time, but are also allowed to sometimes grow their capacity when needed.

Reserve

#include <cx/array_list.h> int cx_array_reserve( void **array, void *size, void *capacity, unsigned width, size_t elem_size, size_t count, CxArrayReallocator *reallocator); #define cx_array_simple_reserve(ARRAY, count) #define cx_array_simple_reserve_a(reallocator, ARRAY, count)

The function cx_array_reserve() guarantees that at least count additional elements can be stored in the array pointed to by array.

The array argument is a pointer to the location of the target array pointer. The reason for this additional indirection is that this function writes a new pointer back to that variable, if the array needed to be reallocated.

If reallocation fails, this function returns non-zero leaving the array as it was. Otherwise, the function returns zero.

If *size + elem_count does not exceed the current *capacity, this function does nothing and simply returns zero. Otherwise, the specified reallocator is used to reserve the necessary space. If reallocation was necessary but failed, this function returns non-zero.

The actual data type of size and capacity can be a pointer to an arbitrary integer whose byte-width is determined by the width argument. On 32-bit platforms the widths 1, 2, and 4 are supported and on 64-bit platforms, additionally a width of 8 is supported. Passing zero as argument makes the function assume the native width for size arguments sizeof(size_t).

The convenience macros take the name of an array variable and invoke the function by deducing the other arguments (including the width of the size and capacity). The reallocator used by the cx_array_simple_reserve() macro is the cx_array_default_reallocator.

Copy

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

The function cx_array_copy() first reserves enough memory to copy elem_count number of elements from the src array to the target array at the specified index, and then copies the data with one call to memmove().

A few things to note:

  • *target and src can point to the same memory region, since the underlying copy operation is a 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 and not even within the capacity of the current array

  • if index equals *size, this function effectively appends the data to the target array

  • the data in the target array is overwritten - if you want to insert data, you first need to copy the existing data to the end of the array and then copy the new data in a separate call

Add Elements

#include <cx/array_list.h> #define 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)

The macros for adding an element are all convenience macros that invoke cx_array_copy() interpreting the elem as an array of size one, copied to the past-by-one index of the target array.

Insertion Sort

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) #define cx_array_add_sorted(target, size, capacity, elem_size, elem, cx_compare_func cmp_func, reallocator); #define cx_array_simple_add_sorted(ARRAY, elem, cmp_func) #define cx_array_simple_add_sorted_a(reallocator, ARRAY, elem, cmp_func)

The function cx_array_insert_sorted() inserts the elem_count number of already sorted elements from the src array into the target array, comparing the elements with the given cmp_func.

The arguments of this function are used similar to cx_array_copy() with two notable exceptions: first, this function actually inserts the items, moving existing items when necessary, and second, no particular index is required because this function determines the insertion points automatically using binary search.

If either the target or the source array is not already sorted with respect to the given compare function, the behavior is undefined.

The convenience macros are all calling cx_array_insert_sorted() by deducing the missing arguments. The cx_array_add_sorted() family of macros are interpreting the elem as a src array with an elem_count of one.

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

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 (greatest lower bound / infimum), and the latter function returns the closest element that is larger or equal (least upper bound / supremum) than the searched element.

Iterators

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

Other

#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. Small Buffer Optimizations).

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

Last modified: 06 April 2025
List InterfaceLinked List