ucx: comparison docs/Writerside/topics/array

-:e30d38e06559
+:fc5e63b04281
 CxArrayReallocator cx_array_reallocator(
 const struct cx_allocator_s *allocator,
 const void *stackmem
 );
-```
+extern CxArrayReallocator* cx_array_default_reallocator;
-<warning>
+```
-TODO: document
-</warning>
+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 <cx/array_list.h>
+The default `cx_array_default_reallocator` simply defers to the standard library `realloc()`.
-int cx_array_add(void **target, void *size, void *capacity,
+A reallocator created with the `cx_array_reallocator()` function uses a more sophisticated approach.
-size_t elem_size, const void *elem,
+On the one hand, it can use an arbitrary UCX [allocator](allocator.h.md) for the reallocation,
-CxArrayReallocator *reallocator);
+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,
-#define cx_array_simple_add(ARRAY, elem)
+if the current location equals the `stackmem` address.
-#define cx_array_simple_add_a(reallocator, ARRAY, elem)
+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.
-<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,
+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)
 ```
-<warning>
+The function `cx_array_reserve()` guarantees that at least `count` _additional_ elements
-TODO: document
+can be stored in the array pointed to by `array`.
-</warning>
+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
 ```C
 #include <cx/array_list.h>
 #define cx_array_simple_copy(ARRAY, index, src, count)
 #define cx_array_simple_copy_a(reallocator, ARRAY, index, src, count)
 ```
-<warning>
+The function `cx_array_copy()` first [reserves](#reserve) enough memory to copy `elem_count` number of elements from the `src` array
-TODO: outdated - rewrite
+to the target array at the specified `index`, and then copies the data with one call to `memmove()`.
-</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` 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
+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 need to be within size and not even within the capacity of the current array
-* `index` does not even need to be within the capacity of the array
+* if `index` equals `*size`, this function effectively appends the data to the target 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)
+* 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 <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
 ```C
 int cx_array_insert_sorted(
 src, elem_count, cmp_func)
 #define cx_array_simple_insert_sorted_a(reallocator, ARRAY,
 src, elem_count, cmp_func)
-int cx_array_add_sorted(
+#define cx_array_add_sorted(target, size, capacity,
-void **target, size_t *size, size_t *capacity,
+elem_size, elem, cx_compare_func cmp_func, reallocator);
-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>
+The function `cx_array_insert_sorted()` inserts the `elem_count` number of already sorted elements from the `src` array
-TODO: document
+into the target array, comparing the elements with the given `cmp_func`.
-</warning>
+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
 ```C
 #include <cx/array_list.h>
 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>
+The function `cx_array_binary_search()` searches the array `arr` for the data pointed to by `elem` using the compare function `cmp_func`.
-TODO: document
-</warning>
+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
 ```C
 #include <cx/iterator.h>
 size_t idx1,
 size_t idx2
 );
 ```
-<warning>
+The function `cx_array_swap()` exchanges two items with a three-way swap.
-TODO: document
-</warning>
+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`.
 <seealso>
 <category ref="apidoc">
 <a href="https://ucx.sourceforge.io/api/array__list_8h.html">array_list.h</a>
 </category>

comparison: docs/Writerside/topics/array_list.h.md

docs/Writerside/topics/array_list.h.md

Mercurial > hg > ucx / file comparison

comparison: docs/Writerside/topics/array_list.h.md

docs/Writerside/topics/array_list.h.md