# HG changeset patch # User Mike Becker # Date 1765906208 -3600 # Node ID 1e0e7f08ccd6e0961ac7af71daa7bed1efaeae76 # Parent 75a8c63db7c7eacbc310a48ed447f49b115c8753 update the online docs with the new array API - resolves #619 diff -r 75a8c63db7c7 -r 1e0e7f08ccd6 docs/Writerside/topics/array_list.h.md --- a/docs/Writerside/topics/array_list.h.md Tue Dec 16 16:01:37 2025 +0100 +++ b/docs/Writerside/topics/array_list.h.md Tue Dec 16 18:30:08 2025 +0100 @@ -15,268 +15,149 @@ The remaining documentation on this page concentrates on dealing with plain C arrays. -## Declare Array with Size and Capacity +## Declaring and Initializing ```C #include -#define CX_ARRAY_DECLARE_SIZED(type, name, size_type) +#define CX_ARRAY(type, name) -#define CX_ARRAY_DECLARE(type, name) +int cx_array_init(CxArray array, size_t capacity); -#define cx_array_initialize(ARRAY, capacity) +int cx_array_init_a(const CxAllocator *allocator, + CxArray array, size_t capacity); -#define cx_array_initialize_a(allocator, ARRAY, 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 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`. +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`. -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); -} -``` +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. -> 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 the [default allocator](allocator.h.md#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); +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. -struct my_data data; -cx_array_initialize_a(mpool->allocator, data.my_array, 16); -``` +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()`. -> The aforementioned macros simplify your life, 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 +## Reallocation ```C #include -typedef struct { - void *(*realloc)(void *array, - size_t old_capacity, size_t new_capacity, - size_t elem_size, CxArrayReallocator *alloc); - const CxAllocator *allocator; - const void *stack_ptr; -} CxArrayReallocator; +int cx_array_reserve(CxArray array, size_t capacity); + +int cx_array_copy_to_new(CxArray array, size_t capacity); -CxArrayReallocator cx_array_reallocator( - const struct cx_allocator_s *allocator, - const void *stack_ptr -); +int cx_array_reserve_a(const CxAllocator *allocator, + CxArray array, size_t capacity); -extern CxArrayReallocator* cx_array_default_reallocator; +int cx_array_copy_to_new_a(const CxAllocator *allocator, + CxArray array, size_t capacity); ``` -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 necessary reallocation. +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`. -This is realized by passing a reallocator to the various functions that specify how an array shall be reallocated when needed. - -The default `cx_array_default_reallocator` simply defers to the [default allocator](allocator.h.md#default-allocator). +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. -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](allocator.h.md) 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 `stack_ptr`, the reallocator will _always_ allocate _new_ memory for the array, -if the current location equals the `stack_ptr` address. +> 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"} -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](mempool.h.md) this can be a powerful tool. -For example, you can add small arrays to your structs plus a memory pool and then use that memory pool to reallocate the arrays on the heap when needed. -When you are done with the arrays, you can then use the memory pool to free the memory for those arrays that needed to be moved to the heap. - -## Reserve +## Add or Insert Elements ```C #include -int cx_array_reserve( - void **array, void *size, void *capacity, unsigned width, - size_t elem_size, size_t count, - CxArrayReallocator *reallocator); +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); -#define cx_array_simple_reserve(ARRAY, count) -#define cx_array_simple_reserve_a(reallocator, ARRAY, count) +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 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 a width of 8 is also 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`. - -> While the actual integer type for `size` and `capacity` can be chosen freely, it must be _the same_ for both variables. -> For example, it is not allowed, and it does not make any sense either, to use a 16-bit integer for the size, but a 32-bit integer for the capacity. - -## Copy - -```C -#include - -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); +The above functions insert one or more elements into the array at the specified `index` +or add them to the end of the array. -#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](#reserve) 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 +When the array capacity is not sufficient, a re-allocation is attempted. +If the allocation fails, the function returns non-zero. -> If you are using `cx_array_reserve()` already in your program, there is no need to call `cx_array_copy()` or any of the convenience macros anymore. -> In other words: if you already guarantee, by any means that no reallocation is necessary when writing to your array, -> it is strongly recommended to use standard library functions or direct index-based access instead of the UCX functions, -> which only purpose is to make it easier for you to guarantee that your array's capacity is large enough to hold new elements. - -## Add Elements - -```C -#include - -#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. +> 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 -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); +int cx_array_insert_sorted(CxArray array, + cx_compare_func cmp_func, const void *element); -#define cx_array_simple_insert_sorted(ARRAY, - src, elem_count, cmp_func) +int cx_array_insert_sorted_array(CxArray array, + cx_compare_func cmp_func, const void *sorted_data, size_t n); -#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); +int cx_array_insert_sorted_a(const CxAllocator *allocator, + CxArray array, cx_compare_func cmp_func, const void *element); -#define cx_array_simple_add_sorted(ARRAY, - elem, cmp_func) - -#define cx_array_simple_add_sorted_a(reallocator, ARRAY, - elem, cmp_func) +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 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()`](#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](#binary-search). +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. -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. - -## Sets of Unique Elements +## Insert Unique Elements ```C #include -int cx_array_insert_unique( - 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); +int cx_array_insert_unique(CxArray array, + cx_compare_func cmp_func, const void *element); -#define cx_array_simple_insert_unique(ARRAY, - src, elem_count, cmp_func) +int cx_array_insert_unique_array(CxArray array, + cx_compare_func cmp_func, const void *sorted_data, size_t n); -#define cx_array_simple_insert_unique_a(reallocator, ARRAY, - src, elem_count, cmp_func) - -#define cx_array_add_unique(target, size, capacity, - elem_size, elem, cx_compare_func cmp_func, reallocator); +int cx_array_insert_unique_a(const CxAllocator *allocator, + CxArray array, cx_compare_func cmp_func, const void *element); -#define cx_array_simple_add_unique(ARRAY, - elem, cmp_func) - -#define cx_array_simple_add_unique_a(reallocator, ARRAY, - elem, cmp_func) +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 `cx_array_insert_sorted()` and its [relatives](#insertion-sort), -except that they skip insertion of elements that are already present in the target array. +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 @@ -297,7 +178,9 @@ ``` 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`.