# HG changeset patch # User Mike Becker # Date 1733359907 -3600 # Node ID 84fc42b04d3b30bc3fa38d07861a98a41aacad48 # Parent bb196054f3fd87f684979b04c66687fac311bd04 add cx_array_reserve() and several more array convenience functions diff -r bb196054f3fd -r 84fc42b04d3b src/array_list.c --- a/src/array_list.c Mon Dec 02 20:58:17 2024 +0100 +++ b/src/array_list.c Thu Dec 05 01:51:47 2024 +0100 @@ -89,6 +89,96 @@ // LOW LEVEL ARRAY LIST FUNCTIONS +int cx_array_reserve( + void **array, + void *size, + void *capacity, + unsigned width, + size_t elem_size, + size_t elem_count, + CxArrayReallocator *reallocator +) { + // assert pointers + assert(array != NULL); + assert(size != NULL); + assert(capacity != NULL); + assert(reallocator != NULL); + + // 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(*array != NULL || oldcap == 0); + + // determine new capacity + size_t newcap = oldsize + elem_count; + + // check for overflow + if (newcap > max_size) { + errno = EOVERFLOW; + return 1; + } + + // reallocate if possible + if (newcap > oldcap) { + // calculate new capacity (next number divisible by 16) + newcap = newcap - (newcap % 16) + 16; + + // perform reallocation + void *newmem = reallocator->realloc( + *array, newcap, elem_size, reallocator + ); + if (newmem == NULL) { + return 1; + } + + // store new pointer + *array = newmem; + + // store new capacity + if (width == 0 || width == __WORDSIZE) { + *(size_t*) capacity = newcap; + } else if (width == 16) { + *(uint16_t*) capacity = newcap; + } else if (width == 8) { + *(uint8_t*) capacity = newcap; + } +#if __WORDSIZE == 64 + else if (width == 32) { + *(uint32_t*) capacity = newcap; + } +#endif + } + + return 0; +} + int cx_array_copy( void **target, void *size, diff -r bb196054f3fd -r 84fc42b04d3b src/cx/array_list.h --- a/src/cx/array_list.h Mon Dec 02 20:58:17 2024 +0100 +++ b/src/cx/array_list.h Thu Dec 05 01:51:47 2024 +0100 @@ -97,6 +97,19 @@ array = malloc(sizeof(array[0]) * capacity) /** + * Initializes an array declared with CX_ARRAY_DECLARE(). + * + * The memory for the array is allocated with the specified allocator. + * @param allocator the allocator + * @param array the array + * @param capacity the initial capacity + */ +#define cx_array_initialize_a(allocator, array, capacity) \ + array##_capacity = capacity; \ + array##_size = 0; \ + array = cxMalloc(allocator, sizeof(array[0]) * capacity) + +/** * Defines a reallocation mechanism for arrays. */ struct cx_array_reallocator_s { @@ -174,6 +187,41 @@ ); /** + * Reserves memory for additional elements. + * + * This function checks if the \p capacity of the array is sufficient to hold + * at least \p size plus \p elem_count elements. If not, a reallocation is + * performed with the specified \p reallocator. + * + * This function can be useful to replace subsequent calls to cx_array_copy() + * with one single cx_array_reserve() and then - after guaranteeing a + * sufficient capacity - use simple memmove() or memcpy(). + * + * 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 array a pointer to the target array + * @param size a pointer to the size of the array + * @param capacity a pointer to the capacity of the array + * @param width the width in bytes for the \p size and \p capacity or zero for default + * @param elem_size the size of one element + * @param elem_count the number of expected additional elements + * @param reallocator the array reallocator to use + * @return zero on success, non-zero on failure + */ +cx_attr_nonnull +int cx_array_reserve( + void **array, + void *size, + void *capacity, + unsigned width, + size_t elem_size, + size_t elem_count, + struct cx_array_reallocator_s *reallocator +); + +/** * Copies elements from one array to another. * * The elements are copied to the \p target array at the specified \p index, @@ -214,6 +262,24 @@ /** * Convenience macro that uses cx_array_copy() with a default layout and + * the specified reallocator. + * + * @param reallocator the array reallocator to use + * @param array the name of the array (NOT a pointer to the array) + * @param index the index where the copied elements shall be placed + * @param src the source array + * @param count the number of elements to copy + * @return zero on success, non-zero on failure + * @see CX_ARRAY_DECLARE() + * @see cx_array_simple_copy() + */ +#define cx_array_simple_copy_a(reallocator, array, index, src, count) \ + cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ + 8*sizeof(array##_size), index, src, sizeof((array)[0]), count, \ + reallocator) + +/** + * Convenience macro that uses cx_array_copy() with a default layout and * the default reallocator. * * @param array the name of the array (NOT a pointer to the array) @@ -222,11 +288,41 @@ * @param count the number of elements to copy * @return zero on success, non-zero on failure * @see CX_ARRAY_DECLARE() + * @see cx_array_simple_copy_a() */ #define cx_array_simple_copy(array, index, src, count) \ - cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ - 8*sizeof(array##_size), index, src, sizeof((array)[0]), count, \ - cx_array_default_reallocator) + cx_array_simple_copy_a(cx_array_default_reallocator, \ + array, index, src, count) + +/** + * Convenience macro that uses cx_array_reserve() with a default layout and + * the specified reallocator. + * + * @param reallocator the array reallocator to use + * @param array the name of the array (NOT a pointer to the array) + * @param count the number of expected additional elements + * @return zero on success, non-zero on failure + * @see CX_ARRAY_DECLARE() + * @see cx_array_simple_reserve() + */ +#define cx_array_simple_reserve_a(reallocator, array, count) \ + cx_array_reserve((void**)&(array), &(array##_size), &(array##_capacity), \ + 8*sizeof(array##_size), sizeof((array)[0]), count, \ + reallocator) + +/** + * Convenience macro that uses cx_array_reserve() with a default layout and + * the default reallocator. + * + * @param array the name of the array (NOT a pointer to the array) + * @param count the number of expected additional elements + * @return zero on success, non-zero on failure + * @see CX_ARRAY_DECLARE() + * @see cx_array_simple_reserve_a() + */ +#define cx_array_simple_reserve(array, count) \ + cx_array_simple_reserve_a(cx_array_default_reallocator, \ + array, count) /** * Adds an element to an array with the possibility of allocating more space. @@ -252,16 +348,30 @@ /** * Convenience macro that uses cx_array_add() with a default layout and + * the specified reallocator. + * + * @param reallocator the array reallocator to use + * @param array the name of the array (NOT a pointer to the array) + * @param elem the element to add (NOT a pointer, address is automatically taken) + * @return zero on success, non-zero on failure + * @see CX_ARRAY_DECLARE() + * @see cx_array_simple_add() + */ +#define cx_array_simple_add_a(reallocator, array, elem) \ + cx_array_simple_copy_a(reallocator, array, array##_size, &(elem), 1) + +/** + * Convenience macro that uses cx_array_add() with a default layout and * the default reallocator. * * @param array the name of the array (NOT a pointer to the array) * @param elem the element to add (NOT a pointer, address is automatically taken) * @return zero on success, non-zero on failure * @see CX_ARRAY_DECLARE() + * @see cx_array_simple_add_a() */ #define cx_array_simple_add(array, elem) \ - cx_array_simple_copy(array, array##_size, &(elem), 1) - + cx_array_simple_add_a(cx_array_default_reallocator, array, elem) /** * Inserts a sorted array into another sorted array. diff -r bb196054f3fd -r 84fc42b04d3b tests/test_list.c --- a/tests/test_list.c Mon Dec 02 20:58:17 2024 +0100 +++ b/tests/test_list.c Thu Dec 05 01:51:47 2024 +0100 @@ -142,6 +142,25 @@ free(arr); } +CX_TEST(test_array_reserve) { + CX_ARRAY_DECLARE_SIZED(int, arr, uint16_t); + cx_array_initialize(arr, 16); + arr_size = 5; + int result; + CX_TEST_DO { + result = cx_array_simple_reserve(arr, 3); + CX_TEST_ASSERT(result == 0); + CX_TEST_ASSERT(arr_size == 5); + CX_TEST_ASSERT(arr_capacity == 16); + + result = cx_array_simple_reserve(arr, 20); + CX_TEST_ASSERT(result == 0); + CX_TEST_ASSERT(arr_size == 5); + CX_TEST_ASSERT(arr_capacity >= 25); + } + free(arr); +} + CX_TEST(test_array_insert_sorted) { int d1 = 50; int d2 = 80; @@ -1879,6 +1898,7 @@ 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_reserve); cx_test_register(suite, test_array_insert_sorted); cx_test_register(suite, test_array_binary_search);