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.
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 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
#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.
Add or Insert Elements
#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.
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.
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
#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
#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.
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.