# HG changeset patch # User Mike Becker # Date 1726594721 -7200 # Node ID 3012e9b4214e8b94447c19b3c7f4364ae1dd45f5 # Parent f8ca6e6c0d48e1298fff00c37b01321a0b24a4f5 add low level cx_array_insert_sorted() and convenience macros relates to #416 diff -r f8ca6e6c0d48 -r 3012e9b4214e src/array_list.c --- a/src/array_list.c Tue Sep 17 19:08:22 2024 +0200 +++ b/src/array_list.c Tue Sep 17 19:38:41 2024 +0200 @@ -120,6 +120,122 @@ return CX_ARRAY_SUCCESS; } +enum cx_array_result cx_array_insert_sorted( + void **target, + size_t *size, + size_t *capacity, + cx_compare_func cmp_func, + void const *sorted_data, + size_t elem_size, + size_t elem_count, + struct cx_array_reallocator_s *reallocator +) { + // assert pointers + assert(target != NULL); + assert(size != NULL); + assert(capacity != NULL); + assert(cmp_func != NULL); + assert(sorted_data != NULL); + assert(reallocator != NULL); + + // corner case + if (elem_count == 0) return 0; + + // store some counts + size_t old_size = *size; + size_t needed_capacity = old_size + elem_count; + + // if we need more than we have, try a reallocation + if (needed_capacity > *capacity) { + size_t new_capacity = needed_capacity - (needed_capacity % 16) + 16; + void *new_mem = reallocator->realloc( + *target, new_capacity, elem_size, reallocator + ); + if (new_mem == NULL) { + // give it up right away, there is no contract + // that requires us to insert as much as we can + return CX_ARRAY_REALLOC_FAILED; + } + *target = new_mem; + *capacity = new_capacity; + } + + // now we have guaranteed that we can insert everything + size_t new_size = old_size + elem_count; + *size = new_size; + + // declare the source and destination indices/pointers + size_t si = 0, di = 0; + char const *src = sorted_data; + char *dest = *target; + + // find the first insertion point + while (di < old_size) { + if (cmp_func(src, dest) < 0) { + break; + } + di++; + dest += elem_size; + } + + // move the remaining elements in the array completely to the right + // we will call it the "buffer" for parked elements + size_t buf_size = old_size - di; + size_t bi = new_size - buf_size; + char *bptr = ((char *) *target) + bi * elem_size; + memmove(bptr, dest, buf_size * elem_size); + + // while there are both source and buffered elements left, + // copy them interleaving + while (si < elem_count && bi < new_size) { + // determine how many source elements can be inserted + size_t copy_len = 1; + si++; + char const *next_src = src + elem_size; + while (si < elem_count) { + if (cmp_func(bptr, next_src) < 0) { + break; + } + copy_len++; + si++; + next_src += elem_size; + } + + // copy the source elements + memcpy(dest, src, copy_len * elem_size); + dest += copy_len * elem_size; + src = next_src; + + // determine how many buffered elements need to be restored + copy_len = 1; + bi++; + char *next_bptr = bptr + elem_size; + while (bi < new_size) { + if (cmp_func(src, next_bptr) < 0) { + break; + } + copy_len++; + bi++; + next_bptr += elem_size; + } + + // restore the buffered elements + memmove(dest, bptr, copy_len * elem_size); + dest += copy_len * elem_size; + bptr = next_bptr; + } + + // still source elements left? simply append them + if (si < elem_count) { + memcpy(dest, src, elem_size * (elem_count - si)); + } + + // still buffer elements left? + // don't worry, we already moved them to the correct place + + return CX_ARRAY_SUCCESS; +} + #ifndef CX_ARRAY_SWAP_SBO_SIZE #define CX_ARRAY_SWAP_SBO_SIZE 128 #endif @@ -269,106 +385,24 @@ void const *sorted_data, size_t n ) { - // corner case - if (n == 0) return 0; - - // define some handy pointers + // get a correctly typed pointer to the list cx_array_list *arl = (cx_array_list *) list; - cx_compare_func cmp = list->collection.cmpfunc; - - // store some counts - size_t old_size = list->collection.size; - size_t capacity = arl->capacity; - size_t needed_capacity = old_size + n; - size_t elem_size = list->collection.elem_size; - - // if we need more than we have, try a reallocation - if (needed_capacity > capacity) { - capacity = needed_capacity - (needed_capacity % 16) + 16; - if (0 != cxReallocate(list->collection.allocator, - &(arl->data), - capacity * elem_size)) { - // give it up right away, there is no contract - // that requires us to insert as much as we can - return 0; - } - arl->capacity = capacity; - } - - // now we have guaranteed that we can insert everything - size_t new_size = list->collection.size + n; - list->collection.size = new_size; - - // declare the source and destination indices/pointers - size_t si = 0, di = 0; - char const *src = sorted_data; - char *dest = arl->data; - - // find the first insertion point - while (di < old_size) { - if (cmp(src, dest) < 0) { - break; - } - di++; - dest += elem_size; - } - // move the remaining elements in the array completely to the right - // we will call it the "buffer" for parked elements - size_t buf_size = old_size - di; - size_t bi = new_size - buf_size; - char *bptr = ((char *) arl->data) + bi * elem_size; - memmove(bptr, dest, buf_size * elem_size); - - // while there are both source and buffered elements left, - // copy them interleaving - while (si < n && bi < new_size) { - // determine how many source elements can be inserted - size_t copy_len = 1; - si++; - char const *next_src = src + elem_size; - while (si < n) { - if (cmp(bptr, next_src) < 0) { - break; - } - copy_len++; - si++; - next_src += elem_size; - } - - // copy the source elements - memcpy(dest, src, copy_len * elem_size); - dest += copy_len * elem_size; - src = next_src; - - // determine how many buffered elements need to be restored - copy_len = 1; - bi++; - char *next_bptr = bptr + elem_size; - while (bi < new_size) { - if (cmp(src, next_bptr) < 0) { - break; - } - copy_len++; - bi++; - next_bptr += elem_size; - } - - // restore the buffered elements - memmove(dest, bptr, copy_len * elem_size); - dest += copy_len * elem_size; - bptr = next_bptr; + if (CX_ARRAY_SUCCESS == cx_array_insert_sorted( + &arl->data, + &list->collection.size, + &arl->capacity, + list->collection.cmpfunc, + sorted_data, + list->collection.elem_size, + n, + &arl->reallocator + )) { + return n; + } else { + // array list implementation is "all or nothing" + return 0; } - - // still source elements left? simply append them - if (si < n) { - memcpy(dest, src, elem_size * (n - si)); - } - - // still buffer elements left? - // don't worry, we already moved them to the correct place - - return n; } static int cx_arl_insert_element( diff -r f8ca6e6c0d48 -r 3012e9b4214e src/cx/array_list.h --- a/src/cx/array_list.h Tue Sep 17 19:08:22 2024 +0200 +++ b/src/cx/array_list.h Tue Sep 17 19:38:41 2024 +0200 @@ -55,6 +55,8 @@ * @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) \ type * name; \ @@ -147,7 +149,8 @@ * @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 target array's capacity - - * \c NULL if only the size shall be used to bound the array + * \c NULL if only the size shall be used to bound the array (reallocations + * will NOT be supported in that case) * @param index the index where the copied elements shall be placed * @param src the source array * @param elem_size the size of one element @@ -174,6 +177,7 @@ * @param index the index where the copied elements shall be placed * @param src the source array * @param count the number of elements to copy + * @see CX_ARRAY_DECLARE() */ #define cx_array_simple_copy(array, index, src, count) \ cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ @@ -202,14 +206,94 @@ cx_array_copy((void**)(target), size, capacity, *(size), elem, elem_size, 1, reallocator) /** - * Convenience macro that uses cx_array_add() with a default layout and the default reallocator. + * 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) + * @see CX_ARRAY_DECLARE() */ #define cx_array_simple_add(array, elem) \ cx_array_simple_copy(array, array##_size, &(elem), 1) + +/** + * Inserts a sorted array into another sorted array. + * + * If either the target or the source array is not already sorted with respect + * to the specified \p cmp_func, the behavior is undefined. + * + * If the capacity is insufficient to hold the new data, a reallocation + * attempt is made. + * + * @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 target array's capacity + * @param cmp_func the compare function for the elements + * @param src the source array + * @param elem_size the size of one element + * @param elem_count the number of elements to insert + * @param reallocator the array reallocator to use + * @return zero on success, non-zero error code on failure + */ +enum cx_array_result cx_array_insert_sorted( + void **target, + size_t *size, + size_t *capacity, + cx_compare_func cmp_func, + void const *src, + size_t elem_size, + size_t elem_count, + struct cx_array_reallocator_s *reallocator +) __attribute__((__nonnull__)); + +/** + * Inserts an element into a sorted array. + * + * If the target array is not already sorted with respect + * to the specified \p cmp_func, the behavior is undefined. + * + * If the capacity is insufficient to hold the new data, a reallocation + * attempt is made. + * + * @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 target array's capacity + * @param elem_size the size of one element + * @param elem a pointer to the element to add + * @param reallocator the array reallocator to use + * @return zero on success, non-zero error code on failure + */ +#define cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator) \ + cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator) + +/** + * Convenience macro for cx_array_add_sorted() 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) + * @param cmp_func the compare function for the elements + * @see CX_ARRAY_DECLARE() + */ +#define cx_array_simple_add_sorted(array, elem, cmp_func) \ + cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \ + sizeof((array)[0]), &(elem), cmp_func, cx_array_default_reallocator) + +/** + * Convenience macro for cx_array_insert_sorted() with a default + * layout and the default reallocator. + * + * @param array the name of the array (NOT a pointer to the array) + * @param src pointer to the source array + * @param n number of elements in the source array + * @param cmp_func the compare function for the elements + * @see CX_ARRAY_DECLARE() + */ +#define cx_array_simple_insert_sorted(array, src, n, cmp_func) \ + cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \ + cmp_func, src, sizeof((array)[0]), n, cx_array_default_reallocator) + /** * Swaps two array elements. * diff -r f8ca6e6c0d48 -r 3012e9b4214e tests/test_list.c --- a/tests/test_list.c Tue Sep 17 19:08:22 2024 +0200 +++ b/tests/test_list.c Tue Sep 17 19:38:41 2024 +0200 @@ -99,6 +99,53 @@ free(heaparray); } +CX_TEST(test_array_insert_sorted) { + int d1 = 50; + int d2 = 80; + int d3 = 60; + int d4 = 40; + int d5 = 70; + int d6a[6] = {52, 54, 56, 62, 64, 75}; + int d7a[6] = {51, 57, 58, 65, 77, 78}; + int d8 = 90; + int expected[18] = { + 40, 50, 51, 52, 54, 56, 57, 58, 60, + 62, 64, 65, 70, 75, 77, 78, 80, 90 + }; + + CX_ARRAY_DECLARE(int, array); + cx_array_initialize(array, 4); + + CX_TEST_DO { + CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d1, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 1); + CX_TEST_ASSERT(array_capacity == 4); + CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d2, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 2); + CX_TEST_ASSERT(array_capacity == 4); + CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d3, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 3); + CX_TEST_ASSERT(array_capacity == 4); + CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d4, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 4); + CX_TEST_ASSERT(array_capacity == 4); + CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d5, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 5); + CX_TEST_ASSERT(array_capacity >= 5); + CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d6a, 6, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 11); + CX_TEST_ASSERT(array_capacity >= 11); + CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d7a, 6, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 17); + CX_TEST_ASSERT(array_capacity >= 17); + CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d8, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 18); + CX_TEST_ASSERT(array_capacity >= 18); + + CX_TEST_ASSERT(0 == memcmp(array, expected, 18 * sizeof(int))); + } +} + typedef struct node { struct node *next; struct node *prev; @@ -1534,6 +1581,7 @@ CxTestSuite *suite = cx_test_suite_new("array_list"); cx_test_register(suite, test_array_add); + cx_test_register(suite, test_array_insert_sorted); cx_test_register(suite, test_list_arl_create); cx_test_register(suite, test_list_arl_create_simple);