diff -r 6691e007cef7 -r 473d8cb58a6c ucx/array_list.c --- a/ucx/array_list.c Wed Dec 31 12:37:09 2025 +0100 +++ b/ucx/array_list.c Wed Dec 31 16:40:12 2025 +0100 @@ -26,6 +26,10 @@ * POSSIBILITY OF SUCH DAMAGE. */ +#ifdef WITH_MEMRCHR +#define _GNU_SOURCE +#endif + #include "cx/array_list.h" #include "cx/compare.h" #include @@ -97,11 +101,18 @@ if (index > array->size) return -1; if (n == 0) return 0; + // calculate required capacity + size_t req_capacity = array->size + n; + if (req_capacity <= array->size) { + errno = EOVERFLOW; + return -1; + } + // guarantee enough capacity - if (array->capacity < array->size + n) { - const size_t new_capacity = cx_array_grow_capacity(array->capacity,array->size + n); + if (array->capacity < req_capacity) { + const size_t new_capacity = cx_array_grow_capacity(array->capacity,req_capacity); if (cxReallocateArray(allocator, &array->data, new_capacity, elem_size)) { - return -1; // LCOV_EXCL_LINE + return -1; } array->capacity = new_capacity; } @@ -111,8 +122,8 @@ dst += index * elem_size; // do we need to move some elements? - if (index < array->size) { - size_t elems_to_move = array->size - index; + size_t elems_to_move = array->size - index; + if (elems_to_move > 0) { char *target = dst + n * elem_size; memmove(target, dst, elems_to_move * elem_size); } @@ -127,15 +138,15 @@ return 0; } -int cx_array_insert_sorted_s_( +int cx_array_insert_sorted_c_( const CxAllocator *allocator, CxArray *array, size_t elem_size, const void *sorted_data, size_t n, - bool allow_duplicates, cx_compare_func2 cmp_func, - void *context + void *context, + bool allow_duplicates ) { // assert pointers assert(allocator != NULL); @@ -310,7 +321,9 @@ left_src += elem_size; skip_len++; } else { - break; + // should be unreachable because the requirement is + // that the source array is sorted + break; // LCOV_EXCL_LINE } } } @@ -339,14 +352,63 @@ const CxAllocator *allocator, CxArray *array, size_t elem_size, - cx_compare_func cmp_func, const void *sorted_data, size_t n, + cx_compare_func cmp_func, bool allow_duplicates ) { cx_compare_func_wrapper wrapper = {cmp_func}; - return cx_array_insert_sorted_s_(allocator, array, elem_size, sorted_data, - n, allow_duplicates, cx_acmp_wrap, &wrapper); + return cx_array_insert_sorted_c_(allocator, array, elem_size, sorted_data, + n, cx_cmp_wrap, &wrapper, allow_duplicates); +} + +#ifndef WITH_QSORT_R +static cx_thread_local cx_compare_func2 cx_array_fn_for_qsort; +static cx_thread_local void *cx_array_context_for_qsort; +static int cx_array_qsort_wrapper(const void *l, const void *r) { + return cx_array_fn_for_qsort(l, r, cx_array_context_for_qsort); +} +#endif + +#if defined(WITH_QSORT_R) && defined(__APPLE__) +// macOS uses a different comparefunc signature for qsort_r +typedef struct QsortCmpFuncWrapper { + cx_compare_func2 fn; + void *context; +} QsortCmpFuncWrapper; + +static int sort_comparefunc(void *context, const void *left, const void *right){ + QsortCmpFuncWrapper *w = context; + return w->fn(left, right, w->context); +} +#endif + +void cx_array_qsort_c(void *array, size_t nmemb, size_t size, + cx_compare_func2 fn, void *context) { +#ifdef WITH_QSORT_R +#ifndef __APPLE__ + qsort_r(array, nmemb, size, fn, context); +#else + QsortCmpFuncWrapper wrapper; + wrapper.fn = fn; + wrapper.context = context; + qsort_r(array, nmemb, size, &wrapper, sort_comparefunc); +#endif +#else + cx_array_fn_for_qsort = fn; + cx_array_context_for_qsort = context; + qsort(array, nmemb, size, cx_array_qsort_wrapper); +#endif +} + +void cx_array_sort_(CxArray *array, size_t elem_size, + cx_compare_func fn) { + qsort(array->data, array->size, elem_size, fn); +} + +void cx_array_sort_c_(CxArray *array, size_t elem_size, + cx_compare_func2 fn, void *context) { + cx_array_qsort_c(array->data, array->size, elem_size, fn, context); } CxIterator cx_array_iterator_(CxArray *array, size_t elem_size) { @@ -357,6 +419,50 @@ return cxIteratorPtr(array->data, array->size); } +void cx_array_remove_(CxArray *array, size_t elem_size, size_t index, size_t n, bool fast) { + if (n == 0) return; + if (index >= array->size) return; + if (index + n >= array->size) { + // only tail elements are removed + array->size = index; + return; + } + array->size -= n; + size_t remaining = array->size - index; + char *dest = ((char*)array->data) + index * elem_size; + if (fast) { + char *src = dest + remaining * elem_size; + if (n == 1 && elem_size <= CX_WORDSIZE/8) { + // try to optimize int-sized values + // (from likely to unlikely) + if (elem_size == sizeof(int32_t)) { + *(int32_t*)dest = *(int32_t*)src; + return; + } +#if CX_WORDSIZE == 64 + if (elem_size == sizeof(int64_t)) { + *(int64_t*)dest = *(int64_t*)src; + return; + } +#endif + if (elem_size == sizeof(int8_t)) { + *(int8_t*)dest = *(int8_t*)src; + return; + } + if (elem_size == sizeof(int16_t)) { + *(int16_t*)dest = *(int16_t*)src; + return; + } + // note we cannot optimize the last branch, because + // the elem_size could be crazily misaligned + } + memcpy(dest, src, n * elem_size); + } else { + char *src = dest + n * elem_size; + memmove(dest, src, remaining * elem_size); + } +} + void cx_array_free_(const CxAllocator *allocator, CxArray *array) { cxFree(allocator, array->data); array->data = NULL; @@ -501,7 +607,7 @@ cx_compare_func cmp_func ) { cx_compare_func_wrapper wrapper = {cmp_func}; - return cx_array_binary_search_inf_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper); + return cx_array_binary_search_inf_c(arr, size, elem_size, elem, cx_cmp_wrap, &wrapper); } size_t cx_array_binary_search( @@ -512,7 +618,7 @@ cx_compare_func cmp_func ) { cx_compare_func_wrapper wrapper = {cmp_func}; - return cx_array_binary_search_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper); + return cx_array_binary_search_c(arr, size, elem_size, elem, cx_cmp_wrap, &wrapper); } size_t cx_array_binary_search_sup( @@ -523,7 +629,7 @@ cx_compare_func cmp_func ) { cx_compare_func_wrapper wrapper = {cmp_func}; - return cx_array_binary_search_sup_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper); + return cx_array_binary_search_sup_c(arr, size, elem_size, elem, cx_cmp_wrap, &wrapper); } #ifndef CX_ARRAY_SWAP_SBO_SIZE @@ -631,15 +737,15 @@ arl->data, list->collection.size, arl->capacity }; - if (cx_array_insert_sorted_s_( + if (cx_array_insert_sorted_c_( list->collection.allocator, &wrap, list->collection.elem_size, sorted_data, n, - allow_duplicates, cx_list_compare_wrapper, - list + list, + allow_duplicates )) { // array list implementation is "all or nothing" return 0; // LCOV_EXCL_LINE @@ -752,10 +858,9 @@ } // just move the elements to the left - char *first_remaining = arl->data; - first_remaining += (index + remove) * list->collection.elem_size; char *dst_move = arl->data; dst_move += index * list->collection.elem_size; + char *first_remaining = dst_move + remove * list->collection.elem_size; memmove(dst_move, first_remaining, remaining * list->collection.elem_size); // decrease the size @@ -849,19 +954,12 @@ return list->collection.size; } -// TODO: remove this hack once we have a solution for qsort() / qsort_s() -static _Thread_local CxList *cx_hack_for_qsort_list; -static int cx_hack_cmp_for_qsort(const void *l, const void *r) { - return cx_list_compare_wrapper(l, r, cx_hack_for_qsort_list); -} - static void cx_arl_sort(struct cx_list_s *list) { - // TODO: think about if we can somehow use qsort()_s - cx_hack_for_qsort_list = list; - qsort(((cx_array_list *) list)->data, + cx_array_qsort_c(((cx_array_list *) list)->data, list->collection.size, list->collection.elem_size, - cx_hack_cmp_for_qsort + cx_list_compare_wrapper, + list ); } @@ -995,8 +1093,7 @@ cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list)); if (list == NULL) return NULL; - cx_list_init((CxList*)list, &cx_array_list_class, - allocator, elem_size); + cx_list_init((CxList*)list, &cx_array_list_class, allocator, elem_size); list->capacity = initial_capacity; // allocate the array after the real elem_size is known