--- a/src/array_list.c Tue Dec 16 21:33:58 2025 +0100
+++ b/src/array_list.c Wed Dec 17 19:05:50 2025 +0100
@@ -127,14 +127,15 @@
return 0;
}
-int cx_array_insert_sorted_(
+int cx_array_insert_sorted_s_(
const CxAllocator *allocator,
CxArray *array,
size_t elem_size,
- cx_compare_func cmp_func,
const void *sorted_data,
size_t n,
- bool allow_duplicates
+ bool allow_duplicates,
+ cx_compare_func2 cmp_func,
+ void *context
) {
// assert pointers
assert(allocator != NULL);
@@ -177,7 +178,7 @@
char *dest = array->data;
// find the first insertion point
- di = cx_array_binary_search_sup(dest, old_size, elem_size, src, cmp_func);
+ di = cx_array_binary_search_sup_c(dest, old_size, elem_size, src, cmp_func, context);
dest += di * elem_size;
// move the remaining elements in the array completely to the right
@@ -203,8 +204,8 @@
// Therefore, the buffer can never contain an element that is smaller
// than any element in the source and the infimum exists.
size_t copy_len, bytes_copied;
- copy_len = cx_array_binary_search_inf(
- src, n - si, elem_size, bptr, cmp_func
+ copy_len = cx_array_binary_search_inf_c(
+ src, n - si, elem_size, bptr, cmp_func, context
);
copy_len++;
@@ -223,7 +224,7 @@
// for being a duplicate of the bptr
const char *end_of_src = src + (copy_len - 1) * elem_size;
size_t skip_len = 0;
- while (copy_len > 0 && cmp_func(bptr, end_of_src) == 0) {
+ while (copy_len > 0 && cmp_func(bptr, end_of_src, context) == 0) {
end_of_src -= elem_size;
skip_len++;
copy_len--;
@@ -233,7 +234,7 @@
// and skip all duplicates with the last element in the array
size_t more_skipped = 0;
for (unsigned j = 0; j < copy_len; j++) {
- if (last != NULL && cmp_func(last, src) == 0) {
+ if (last != NULL && cmp_func(last, src, context) == 0) {
// duplicate - skip
src += elem_size;
si++;
@@ -260,12 +261,13 @@
if (si >= n) break;
// determine how many buffered elements need to be restored
- copy_len = cx_array_binary_search_sup(
+ copy_len = cx_array_binary_search_sup_c(
bptr,
new_size - bi,
elem_size,
src,
- cmp_func
+ cmp_func,
+ context
);
// restore the buffered elements
@@ -295,7 +297,7 @@
const char *left_src = src;
while (si + copy_len + skip_len < n) {
const char *right_src = left_src + elem_size;
- int d = cmp_func(left_src, right_src);
+ int d = cmp_func(left_src, right_src, context);
if (d < 0) {
if (skip_len > 0) {
// new larger element found;
@@ -333,6 +335,20 @@
return 0;
}
+int cx_array_insert_sorted_(
+ const CxAllocator *allocator,
+ CxArray *array,
+ size_t elem_size,
+ cx_compare_func cmp_func,
+ const void *sorted_data,
+ size_t n,
+ 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);
+}
+
CxIterator cx_array_iterator_(CxArray *array, size_t elem_size) {
return cxIterator(array->data, elem_size, array->size);
}
@@ -354,7 +370,8 @@
size_t size,
size_t elem_size,
const void *elem,
- cx_compare_func cmp_func
+ cx_compare_func2 cmp_func,
+ void *context
) {
// special case: empty array
if (size == 0) return 0;
@@ -366,7 +383,7 @@
const char *array = arr;
// check the first array element
- result = cmp_func(elem, array);
+ result = cmp_func(elem, array, context);
if (result < 0) {
return size;
} else if (result == 0) {
@@ -377,7 +394,7 @@
if (size == 1) return 0;
// check the last array element
- result = cmp_func(elem, array + elem_size * (size - 1));
+ result = cmp_func(elem, array + elem_size * (size - 1), context);
if (result >= 0) {
return size - 1;
}
@@ -386,12 +403,12 @@
// so start the binary search
size_t left_index = 1;
size_t right_index = size - 1;
- size_t pivot_index;
+ size_t pivot_index = 0;
while (left_index <= right_index) {
pivot_index = left_index + (right_index - left_index) / 2;
const char *arr_elem = array + pivot_index * elem_size;
- result = cmp_func(elem, arr_elem);
+ result = cmp_func(elem, arr_elem, context);
if (result == 0) {
// found it!
return pivot_index;
@@ -408,6 +425,74 @@
return result < 0 ? (pivot_index - 1) : pivot_index;
}
+size_t cx_array_binary_search_inf_c(
+ const void *arr,
+ size_t size,
+ size_t elem_size,
+ const void *elem,
+ cx_compare_func2 cmp_func,
+ void *context
+) {
+ size_t index = cx_array_binary_search_inf_impl(
+ arr, size, elem_size, elem, cmp_func, context);
+ // in case of equality, report the largest index
+ const char *e = ((const char *) arr) + (index + 1) * elem_size;
+ while (index + 1 < size && cmp_func(e, elem, context) == 0) {
+ e += elem_size;
+ index++;
+ }
+ return index;
+}
+
+size_t cx_array_binary_search_c(
+ const void *arr,
+ size_t size,
+ size_t elem_size,
+ const void *elem,
+ cx_compare_func2 cmp_func,
+ void *context
+) {
+ size_t index = cx_array_binary_search_inf_c(
+ arr, size, elem_size, elem, cmp_func, context
+ );
+ if (index < size && cmp_func(((const char *) arr) + index * elem_size,
+ elem, context) == 0) {
+ return index;
+ } else {
+ return size;
+ }
+}
+
+size_t cx_array_binary_search_sup_c(
+ const void *arr,
+ size_t size,
+ size_t elem_size,
+ const void *elem,
+ cx_compare_func2 cmp_func,
+ void *context
+) {
+ size_t index = cx_array_binary_search_inf_impl(
+ arr, size, elem_size, elem, cmp_func, context
+ );
+ const char *e = ((const char *) arr) + index * elem_size;
+ if (index == size) {
+ // no infimum means the first element is supremum
+ return 0;
+ } else if (cmp_func(e, elem, context) == 0) {
+ // found an equal element, search the smallest index
+ e -= elem_size; // e now contains the element at index-1
+ while (index > 0 && cmp_func(e, elem, context) == 0) {
+ e -= elem_size;
+ index--;
+ }
+ return index;
+ } else {
+ // we already have the largest index of the infimum (by design)
+ // the next element is the supremum (or there is no supremum)
+ return index + 1;
+ }
+}
+
size_t cx_array_binary_search_inf(
const void *arr,
size_t size,
@@ -415,15 +500,8 @@
const void *elem,
cx_compare_func cmp_func
) {
- size_t index = cx_array_binary_search_inf_impl(
- arr, size, elem_size, elem, cmp_func);
- // in case of equality, report the largest index
- const char *e = ((const char *) arr) + (index + 1) * elem_size;
- while (index + 1 < size && cmp_func(e, elem) == 0) {
- e += elem_size;
- index++;
- }
- return index;
+ cx_compare_func_wrapper wrapper = {cmp_func};
+ return cx_array_binary_search_inf_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper);
}
size_t cx_array_binary_search(
@@ -433,15 +511,8 @@
const void *elem,
cx_compare_func cmp_func
) {
- size_t index = cx_array_binary_search_inf(
- arr, size, elem_size, elem, cmp_func
- );
- if (index < size &&
- cmp_func(((const char *) arr) + index * elem_size, elem) == 0) {
- return index;
- } else {
- return size;
- }
+ cx_compare_func_wrapper wrapper = {cmp_func};
+ return cx_array_binary_search_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper);
}
size_t cx_array_binary_search_sup(
@@ -451,26 +522,8 @@
const void *elem,
cx_compare_func cmp_func
) {
- size_t index = cx_array_binary_search_inf_impl(
- arr, size, elem_size, elem, cmp_func
- );
- const char *e = ((const char *) arr) + index * elem_size;
- if (index == size) {
- // no infimum means the first element is supremum
- return 0;
- } else if (cmp_func(e, elem) == 0) {
- // found an equal element, search the smallest index
- e -= elem_size; // e now contains the element at index-1
- while (index > 0 && cmp_func(e, elem) == 0) {
- e -= elem_size;
- index--;
- }
- return index;
- } else {
- // we already have the largest index of the infimum (by design)
- // the next element is the supremum (or there is no supremum)
- return index + 1;
- }
+ cx_compare_func_wrapper wrapper = {cmp_func};
+ return cx_array_binary_search_sup_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper);
}
#ifndef CX_ARRAY_SWAP_SBO_SIZE
@@ -578,14 +631,15 @@
arl->data, list->collection.size, arl->capacity
};
- if (cx_array_insert_sorted_(
+ if (cx_array_insert_sorted_s_(
list->collection.allocator,
&wrap,
list->collection.elem_size,
- list->collection.cmpfunc,
sorted_data,
n,
- allow_duplicates
+ allow_duplicates,
+ cx_list_compare_wrapper,
+ list
)) {
// array list implementation is "all or nothing"
return 0; // LCOV_EXCL_LINE
@@ -763,18 +817,18 @@
bool remove
) {
assert(list != NULL);
- assert(list->collection.cmpfunc != NULL);
if (list->collection.size == 0) return 0;
char *cur = ((const cx_array_list *) list)->data;
// optimize with binary search, when sorted
if (list->collection.sorted) {
- size_t i = cx_array_binary_search(
+ size_t i = cx_array_binary_search_c(
cur,
list->collection.size,
list->collection.elem_size,
elem,
- list->collection.cmpfunc
+ cx_list_compare_wrapper,
+ list
);
if (remove && i < list->collection.size) {
cx_arl_remove(list, i, 1, NULL);
@@ -784,7 +838,7 @@
// fallback: linear search
for (size_t i = 0; i < list->collection.size; i++) {
- if (0 == list->collection.cmpfunc(elem, cur)) {
+ if (0 == cx_list_compare_wrapper(elem, cur, list)) {
if (remove) {
cx_arl_remove(list, i, 1, NULL);
}
@@ -795,12 +849,19 @@
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) {
- assert(list->collection.cmpfunc != NULL);
+ // TODO: think about if we can somehow use qsort()_s
+ cx_hack_for_qsort_list = list;
qsort(((cx_array_list *) list)->data,
list->collection.size,
list->collection.elem_size,
- list->collection.cmpfunc
+ cx_hack_cmp_for_qsort
);
}
@@ -808,12 +869,11 @@
const struct cx_list_s *list,
const struct cx_list_s *other
) {
- assert(list->collection.cmpfunc != NULL);
if (list->collection.size == other->collection.size) {
const char *left = ((const cx_array_list *) list)->data;
const char *right = ((const cx_array_list *) other)->data;
for (size_t i = 0; i < list->collection.size; i++) {
- int d = list->collection.cmpfunc(left, right);
+ int d = cx_list_compare_wrapper(left, right, (void*)list);
if (d != 0) {
return d;
}