# HG changeset patch # User Mike Becker # Date 1733169497 -3600 # Node ID bb196054f3fd87f684979b04c66687fac311bd04 # Parent d14f3d5f47d1814f6262fad1bb58032597e54b91 make cx_array_copy() support different types for size/capacity - fixes #492 diff -r d14f3d5f47d1 -r bb196054f3fd docs/src/features.md --- a/docs/src/features.md Thu Nov 28 20:59:11 2024 +0100 +++ b/docs/src/features.md Mon Dec 02 20:58:17 2024 +0100 @@ -273,45 +273,40 @@ However, there is one extremely powerful function that can be used for several complex tasks: `cx_array_copy`. The full signature is shown below: ```c -enum cx_array_result cx_array_copy( +int cx_array_copy( void **target, - size_t *size, - size_t *capacity, // optional + void *size, + void *capacity, + unsigned width, size_t index, const void *src, size_t elem_size, size_t elem_count, - struct cx_array_reallocator_s *reallocator // optional + struct cx_array_reallocator_s *reallocator ); ``` The `target` argument is a pointer to the target array pointer. -The reason for this additional indirection is that - given that you provide a `reallocator` - this function writes +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. -Tracking the capacity is optional. -If you do not specify a pointer for the capacity, automatic reallocation of the array is entirely disabled (i.e. it -does not make sense to specify a `reallocator` then). -In this case, the function cannot copy more than `size-index` elements and if you try, it will return -`CX_ARRAY_REALLOC_NOT_SUPPORTED` and do nothing. +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 -`CX_ARRAY_SUCCESS`. - -The third, but extremely rare, return code is `CX_ARRAY_REALLOC_FAILED` and speaks for itself. +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` 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, specifying a `reallocator` is forbidden for obvious reasons -* `index` does not need to be within size of the current array, if `capacity` is specified -* `index` does not even need to be within the capacity of the array, if `reallocator` is specified + 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) If you just want to add one single element to an existing array, you can use the macro `cx_array_add()`. -In that case, since the element is added to the end of the array, the `capacity` argument is mandatory. You can use `CX_ARRAY_DECLARE()` to declare the necessary fields within a structure and then use the `cx_array_simple_*()` convenience macros to reduce code overhead. +The convenience macros automatically determine the width of the size/capacity variables. ## Map diff -r d14f3d5f47d1 -r bb196054f3fd src/array_list.c --- a/src/array_list.c Thu Nov 28 20:59:11 2024 +0100 +++ b/src/array_list.c Mon Dec 02 20:58:17 2024 +0100 @@ -30,6 +30,7 @@ #include "cx/compare.h" #include #include +#include // Default array reallocator @@ -90,8 +91,9 @@ int cx_array_copy( void **target, - size_t *size, - size_t *capacity, + void *size, + void *capacity, + unsigned width, size_t index, const void *src, size_t elem_size, @@ -105,29 +107,64 @@ assert(src != NULL); assert(reallocator != NULL); - // determine capacity - size_t cap = *capacity; - assert(*target != NULL || cap == 0); + // determine size and capacity + size_t oldcap; + size_t oldsize; + size_t max_size; + if (width == 0 || width == __WORDSIZE) { + oldcap = *(size_t*) capacity; + oldsize = *(size_t*) size; + max_size = SIZE_MAX; + } else if (width == 16) { + oldcap = *(uint16_t*) capacity; + oldsize = *(uint16_t*) size; + max_size = UINT16_MAX; + } else if (width == 8) { + oldcap = *(uint8_t*) capacity; + oldsize = *(uint8_t*) size; + max_size = UINT8_MAX; + } +#if __WORDSIZE == 64 + else if (width == 32) { + oldcap = *(uint32_t*) capacity; + oldsize = *(uint32_t*) size; + max_size = UINT32_MAX; + } +#endif + else { + errno = EINVAL; + return 1; + } + + // assert that the array is allocated when it has capacity + assert(*target != NULL || oldcap == 0); // check if resize is required size_t minsize = index + elem_count; - size_t newsize = *size < minsize ? minsize : *size; + size_t newsize = oldsize < minsize ? minsize : oldsize; + + // check for overflow + if (newsize > max_size) { + errno = EOVERFLOW; + return 1; + } // reallocate if possible - if (newsize > cap) { + size_t newcap = oldcap; + if (newsize > oldcap) { // check, if we need to repair the src pointer uintptr_t targetaddr = (uintptr_t) *target; uintptr_t srcaddr = (uintptr_t) src; bool repairsrc = targetaddr <= srcaddr - && srcaddr < targetaddr + cap * elem_size; + && srcaddr < targetaddr + oldcap * elem_size; // calculate new capacity (next number divisible by 16) - cap = newsize - (newsize % 16) + 16; - assert(cap > newsize); + newcap = newsize - (newsize % 16) + 16; + assert(newcap > newsize); // perform reallocation void *newmem = reallocator->realloc( - *target, cap, elem_size, reallocator + *target, newcap, elem_size, reallocator ); if (newmem == NULL) { return 1; @@ -138,9 +175,8 @@ src = ((char *) newmem) + (srcaddr - targetaddr); } - // store new pointer and capacity + // store new pointer *target = newmem; - *capacity = cap; } // determine target pointer @@ -149,7 +185,26 @@ // copy elements and set new size memmove(start, src, elem_count * elem_size); - *size = newsize; + + // if any of size or capacity changed, store them back + if (newsize != oldsize || newcap != oldcap) { + if (width == 0 || width == __WORDSIZE) { + *(size_t*) capacity = newcap; + *(size_t*) size = newsize; + } else if (width == 16) { + *(uint16_t*) capacity = newcap; + *(uint16_t*) size = newsize; + } else if (width == 8) { + *(uint8_t*) capacity = newcap; + *(uint8_t*) size = newsize; + } +#if __WORDSIZE == 64 + else if (width == 32) { + *(uint32_t*) capacity = newcap; + *(uint32_t*) size = newsize; + } +#endif + } // return successfully return 0; @@ -458,6 +513,7 @@ &arl->data, &list->collection.size, &arl->capacity, + 0, start_of_moved, first_to_move, list->collection.elem_size, @@ -478,6 +534,7 @@ &arl->data, &list->collection.size, &arl->capacity, + 0, index, array, list->collection.elem_size, @@ -602,6 +659,7 @@ &arl->data, &list->collection.size, &arl->capacity, + 0, index, ((char *) arl->data) + (index + remove) * list->collection.elem_size, list->collection.elem_size, diff -r d14f3d5f47d1 -r bb196054f3fd src/cx/array_list.h --- a/src/cx/array_list.h Thu Nov 28 20:59:11 2024 +0100 +++ b/src/cx/array_list.h Mon Dec 02 20:58:17 2024 +0100 @@ -52,16 +52,37 @@ /** * Declares variables for an array that can be used with the convenience macros. * + * @param type the type of the data + * @param name the name of the array + * @param size_type the type of the size (should be uint8_t, uint16_t, uint32_t, or size_t) + * * @see cx_array_simple_add() * @see cx_array_simple_copy() * @see cx_array_initialize() * @see cx_array_simple_add_sorted() * @see cx_array_simple_insert_sorted() */ -#define CX_ARRAY_DECLARE(type, name) \ +#define CX_ARRAY_DECLARE_SIZED(type, name, size_type) \ type * name; \ - size_t name##_size; \ - size_t name##_capacity + size_type name##_size; \ + size_type name##_capacity + +/** + * Declares variables for an array that can be used with the convenience macros. + * + * The size and capacity variables will have `size_t` type. + * Use #CX_ARRAY_DECLARE_SIZED() to specify a different type. + * + * @param type the type of the data + * @param name the name of the array + * + * @see cx_array_simple_add() + * @see cx_array_simple_copy() + * @see cx_array_initialize() + * @see cx_array_simple_add_sorted() + * @see cx_array_simple_insert_sorted() + */ +#define CX_ARRAY_DECLARE(type, name) CX_ARRAY_DECLARE_SIZED(type, name, size_t) /** * Initializes an array declared with CX_ARRAY_DECLARE(). @@ -163,9 +184,14 @@ * If the \p capacity is also insufficient to hold the new data, a reallocation * attempt is made with the specified \p reallocator. * + * The \p width refers to the size and capacity. Both must have the same width. + * Supported are 0, 8, 16, and 32, as well as 64 if running on a 64 bit + * architecture. If set to zero, the native word width is used. + * * @param target a pointer to the target array * @param size a pointer to the size of the target array * @param capacity a pointer to the capacity of the target array + * @param width the width in bytes for the \p size and \p capacity or zero for default * @param index the index where the copied elements shall be placed * @param src the source array * @param elem_size the size of one element @@ -176,8 +202,9 @@ cx_attr_nonnull int cx_array_copy( void **target, - size_t *size, - size_t *capacity, + void *size, + void *capacity, + unsigned width, size_t index, const void *src, size_t elem_size, @@ -198,7 +225,8 @@ */ #define cx_array_simple_copy(array, index, src, count) \ cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ - index, src, sizeof((array)[0]), count, cx_array_default_reallocator) + 8*sizeof(array##_size), index, src, sizeof((array)[0]), count, \ + cx_array_default_reallocator) /** * Adds an element to an array with the possibility of allocating more space. @@ -219,7 +247,8 @@ * @return zero on success, non-zero on failure */ #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \ - cx_array_copy((void**)(target), size, capacity, *(size), elem, elem_size, 1, reallocator) + cx_array_copy((void**)(target), size, capacity, 8*sizeof(*(size)), \ + *(size), elem, elem_size, 1, reallocator) /** * Convenience macro that uses cx_array_add() with a default layout and diff -r d14f3d5f47d1 -r bb196054f3fd tests/test_list.c --- a/tests/test_list.c Thu Nov 28 20:59:11 2024 +0100 +++ b/tests/test_list.c Mon Dec 02 20:58:17 2024 +0100 @@ -34,6 +34,7 @@ #include "cx/linked_list.h" #include +#include CX_TEST(test_array_add) { CX_ARRAY_DECLARE(int, arr); @@ -73,6 +74,74 @@ free(arr); } +CX_TEST(test_array_add8) { + CX_ARRAY_DECLARE_SIZED(int, arr, uint8_t); + arr = calloc(5, sizeof(int)); + arr[0] = 2; + arr[1] = 3; + arr[2] = 5; + arr[3] = 7; + arr[4] = 11; + arr_size = 3; + arr_capacity = 5; + int elem = 8, elem2 = 47; + int result; + CX_TEST_DO { + result = cx_array_simple_add(arr, elem); + CX_TEST_ASSERT(result == 0); + CX_TEST_ASSERT(arr[0] == 2); + CX_TEST_ASSERT(arr[1] == 3); + CX_TEST_ASSERT(arr[2] == 5); + CX_TEST_ASSERT(arr[3] == 8); + CX_TEST_ASSERT(arr[4] == 11); + CX_TEST_ASSERT(arr_size == 4); + CX_TEST_ASSERT(arr_capacity == 5); + + arr_size = 5; + result = cx_array_simple_add(arr, elem2); + CX_TEST_ASSERT(result == 0); + CX_TEST_ASSERT(arr[0] == 2); + CX_TEST_ASSERT(arr[1] == 3); + CX_TEST_ASSERT(arr[2] == 5); + CX_TEST_ASSERT(arr[3] == 8); + CX_TEST_ASSERT(arr[4] == 11); + CX_TEST_ASSERT(arr[5] == 47); + CX_TEST_ASSERT(arr_size == 6); + CX_TEST_ASSERT(arr_capacity >= 6); + + result = cx_array_simple_copy(arr, 260, &elem, 1); + CX_TEST_ASSERT(result != 0); + CX_TEST_ASSERT(errno == EOVERFLOW); + CX_TEST_ASSERT(arr_size == 6); + CX_TEST_ASSERT(arr_capacity < 128); + } + free(arr); +} + +CX_TEST(test_array_copy_unsupported_width) { + CX_ARRAY_DECLARE_SIZED(int, arr, uint16_t); + cx_array_initialize(arr, 16); + int result; + CX_TEST_DO { + int elem = 5; + result = cx_array_copy( + (void **) &(arr), + &(arr_size), + &(arr_capacity), + 12, // unsupported width + 5, + &elem, sizeof(int), + 1, + cx_array_default_reallocator + ); + CX_TEST_ASSERT(result != 0); + CX_TEST_ASSERT(errno == EINVAL); + CX_TEST_ASSERT(arr_size == 0); + CX_TEST_ASSERT(arr_capacity == 16); + } + free(arr); +} + CX_TEST(test_array_insert_sorted) { int d1 = 50; int d2 = 80; @@ -1808,6 +1877,8 @@ CxTestSuite *suite = cx_test_suite_new("array_list"); cx_test_register(suite, test_array_add); + cx_test_register(suite, test_array_add8); + cx_test_register(suite, test_array_copy_unsupported_width); cx_test_register(suite, test_array_insert_sorted); cx_test_register(suite, test_array_binary_search);