diff -r e30d38e06559 -r fc5e63b04281 docs/Writerside/topics/array_list.h.md --- a/docs/Writerside/topics/array_list.h.md Sat Mar 15 22:58:51 2025 +0100 +++ b/docs/Writerside/topics/array_list.h.md Sun Mar 16 15:23:45 2025 +0100 @@ -105,29 +105,26 @@ const struct cx_allocator_s *allocator, const void *stackmem ); + +extern CxArrayReallocator* cx_array_default_reallocator; ``` - -TODO: document - +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. -## Add Elements +This is realized by passing a reallocator to the various functions which specifies how an array shall be reallocated when needed. -```C -#include +The default `cx_array_default_reallocator` simply defers to the standard library `realloc()`. -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) +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 `stackmem`, the reallocator will _always_ allocate _new_ memory for the array, +if the current location equals the `stackmem` address. -#define cx_array_simple_add_a(reallocator, ARRAY, elem) -``` - - -TODO: document - +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 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 @@ -136,16 +133,37 @@ int cx_array_reserve( void **array, void *size, void *capacity, unsigned width, - size_t elem_size, size_t elem_count, + 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) ``` - -TODO: document - +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`. + +> 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 @@ -163,27 +181,37 @@ #define cx_array_simple_copy_a(reallocator, ARRAY, index, src, count) ``` - -TODO: outdated - rewrite - - -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. +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, effectively copying elements within the array with `memmove` +* `*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 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) + 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 + +> 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. ## Insertion Sort @@ -200,11 +228,8 @@ #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_add_sorted(target, size, capacity, + elem_size, elem, cx_compare_func cmp_func, reallocator); #define cx_array_simple_add_sorted(ARRAY, elem, cmp_func) @@ -213,9 +238,17 @@ elem, cmp_func) ``` - -TODO: document - +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). + +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. ## Binary Search @@ -235,9 +268,25 @@ const void *elem, cx_compare_func cmp_func); ``` - -TODO: document - +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. + +> Note, that all of the above functions are only well-defined on arrays which are sorted with respect to the given compare function. +> +> This can, for example, easily be achieved by calling the standard library's `qsort()` function. +>{style="note"} + +> Despite the name, neither C nor POSIX standards require the standard library's `bsearch()` function to be implemented using binary search. +> But observations show that it usually is. +> This makes `cx_array_binary_search()` likely to be equivalent to `bsearch()`, except that it returns an index rather than a pointer. ## Iterators @@ -271,9 +320,11 @@ ); ``` - -TODO: document - +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. [](install.md#small-buffer-optimizations)). + +You have to make sure that both indices are within bounds of the array `arr`.