--- 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 <assert.h>
@@ -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