--- a/src/linked_list.c Tue Dec 16 21:33:58 2025 +0100
+++ b/src/linked_list.c Wed Dec 17 19:05:50 2025 +0100
@@ -65,13 +65,14 @@
return (void *) cur;
}
-void *cx_linked_list_find(
+void *cx_linked_list_find_c(
const void *start,
ptrdiff_t loc_advance,
ptrdiff_t loc_data,
- cx_compare_func cmp_func,
const void *elem,
- size_t *found_index
+ size_t *found_index,
+ cx_compare_func2 cmp_func,
+ void *context
) {
assert(start != NULL);
assert(loc_advance >= 0);
@@ -82,7 +83,7 @@
size_t index = 0;
do {
void *current = ll_data(node);
- if (cmp_func(current, elem) == 0) {
+ if (cmp_func(current, elem, context) == 0) {
if (found_index != NULL) {
*found_index = index;
}
@@ -94,6 +95,19 @@
return NULL;
}
+void *cx_linked_list_find(
+ const void *start,
+ ptrdiff_t loc_advance,
+ ptrdiff_t loc_data,
+ const void *elem,
+ size_t *found_index,
+ cx_compare_func cmp_func
+) {
+ cx_compare_func_wrapper wrapper = {cmp_func};
+ return cx_linked_list_find_c(start, loc_advance, loc_data,
+ elem, found_index, cx_acmp_wrap, &wrapper);
+}
+
void *cx_linked_list_first(
const void *node,
ptrdiff_t loc_prev
@@ -259,7 +273,8 @@
ptrdiff_t loc_prev,
ptrdiff_t loc_next,
void *insert_begin,
- cx_compare_func cmp_func,
+ cx_compare_func2 cmp_func,
+ void *context,
bool allow_duplicates
) {
assert(begin != NULL);
@@ -276,7 +291,7 @@
// determine the new start
{
- int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument);
+ int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument, context);
if (d <= 0) {
// the new chain starts with the original chain
new_begin = new_end = source_original;
@@ -302,7 +317,7 @@
// now successively compare the elements and add them to the correct chains
while (source_original != NULL && source_argument != NULL) {
- int d = cmp_func(source_original, source_argument);
+ int d = cmp_func(source_original, source_argument, context);
if (d <= 0) {
// the original is not larger, add it to the chain
cx_linked_list_link(new_end, source_original, loc_prev, loc_next);
@@ -327,7 +342,7 @@
} else {
// the original is larger, append the source argument to the chain
// check if we must discard the source argument as duplicate
- if (!allow_duplicates && cmp_func(new_end, source_argument) == 0) {
+ if (!allow_duplicates && cmp_func(new_end, source_argument, context) == 0) {
if (dup_end == NULL) {
dup_begin = dup_end = source_argument;
} else {
@@ -356,7 +371,7 @@
} else {
// otherwise we must check one-by-one
while (source_argument != NULL) {
- if (cmp_func(new_end, source_argument) == 0) {
+ if (cmp_func(new_end, source_argument, context) == 0) {
if (dup_end == NULL) {
dup_begin = dup_end = source_argument;
} else {
@@ -402,9 +417,10 @@
void *insert_begin,
cx_compare_func cmp_func
) {
+ cx_compare_func_wrapper wrapper = {cmp_func};
cx_linked_list_insert_sorted_chain_impl(
begin, end, loc_prev, loc_next,
- insert_begin, cmp_func, true);
+ insert_begin, cx_acmp_wrap, &wrapper, true);
}
int cx_linked_list_insert_unique(
@@ -428,9 +444,10 @@
void *insert_begin,
cx_compare_func cmp_func
) {
+ cx_compare_func_wrapper wrapper = {cmp_func};
return cx_linked_list_insert_sorted_chain_impl(
begin, end, loc_prev, loc_next,
- insert_begin, cmp_func, false);
+ insert_begin, cx_acmp_wrap, &wrapper, false);
}
size_t cx_linked_list_remove_chain(
@@ -511,6 +528,8 @@
#endif
static void cx_linked_list_sort_merge(
+ void **begin,
+ void **end,
ptrdiff_t loc_prev,
ptrdiff_t loc_next,
ptrdiff_t loc_data,
@@ -518,9 +537,8 @@
void *ls,
void *le,
void *re,
- cx_compare_func cmp_func,
- void **begin,
- void **end
+ cx_compare_func2 cmp_func,
+ void *context
) {
void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
@@ -532,7 +550,7 @@
rc = le;
size_t n = 0;
while (lc && lc != le && rc != re) {
- if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
+ if (cmp_func(ll_data(lc), ll_data(rc), context) <= 0) {
sorted[n] = lc;
lc = ll_next(lc);
} else {
@@ -566,13 +584,14 @@
}
}
-void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
+void cx_linked_list_sort_c( // NOLINT(misc-no-recursion) - purposely recursive function
void **begin,
void **end,
ptrdiff_t loc_prev,
ptrdiff_t loc_next,
ptrdiff_t loc_data,
- cx_compare_func cmp_func
+ cx_compare_func2 cmp_func,
+ void *context
) {
assert(begin != NULL);
assert(loc_next >= 0);
@@ -590,7 +609,7 @@
// check how many elements are already sorted
lc = ls;
size_t ln = 1;
- while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
+ while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc), context) > 0) {
lc = ll_next(lc);
ln++;
}
@@ -602,7 +621,7 @@
size_t rn = 1;
rc = le;
// skip already sorted elements
- while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
+ while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc), context) > 0) {
rc = ll_next(rc);
rn++;
}
@@ -610,27 +629,65 @@
// {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
void *sorted_begin, *sorted_end;
- cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
+ cx_linked_list_sort_merge(&sorted_begin, &sorted_end,
+ loc_prev, loc_next, loc_data,
ln + rn, ls, le, re, cmp_func,
- &sorted_begin, &sorted_end);
+ context);
// Something left? Sort it!
size_t remainder_length = cx_linked_list_size(re, loc_next);
if (remainder_length > 0) {
void *remainder = re;
- cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
+ cx_linked_list_sort_c(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func, context);
// merge sorted list with (also sorted) remainder
- cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
+ cx_linked_list_sort_merge(&sorted_begin, &sorted_end,
+ loc_prev, loc_next, loc_data,
ln + rn + remainder_length,
sorted_begin, remainder, NULL, cmp_func,
- &sorted_begin, &sorted_end);
+ context);
}
*begin = sorted_begin;
if (end) *end = sorted_end;
}
}
+void cx_linked_list_sort(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ ptrdiff_t loc_data,
+ cx_compare_func cmp_func
+) {
+ cx_compare_func_wrapper wrapper = {cmp_func};
+ cx_linked_list_sort_c(begin, end, loc_prev, loc_next, loc_data, cx_acmp_wrap, &wrapper);
+}
+
+int cx_linked_list_compare_c(
+ const void *begin_left,
+ const void *begin_right,
+ ptrdiff_t loc_advance,
+ ptrdiff_t loc_data,
+ cx_compare_func2 cmp_func,
+ void *context
+) {
+ const void *left = begin_left, *right = begin_right;
+
+ while (left != NULL && right != NULL) {
+ const void *left_data = ll_data(left);
+ const void *right_data = ll_data(right);
+ int result = cmp_func(left_data, right_data, context);
+ if (result != 0) return result;
+ left = ll_advance(left);
+ right = ll_advance(right);
+ }
+
+ if (left != NULL) { return 1; }
+ else if (right != NULL) { return -1; }
+ else { return 0; }
+}
+
int cx_linked_list_compare(
const void *begin_left,
const void *begin_right,
@@ -638,20 +695,9 @@
ptrdiff_t loc_data,
cx_compare_func cmp_func
) {
- const void *left = begin_left, *right = begin_right;
-
- while (left != NULL && right != NULL) {
- const void *left_data = ll_data(left);
- const void *right_data = ll_data(right);
- int result = cmp_func(left_data, right_data);
- if (result != 0) return result;
- left = ll_advance(left);
- right = ll_advance(right);
- }
-
- if (left != NULL) { return 1; }
- else if (right != NULL) { return -1; }
- else { return 0; }
+ cx_compare_func_wrapper wrapper = {cmp_func};
+ return cx_linked_list_compare_c(begin_left, begin_right,
+ loc_advance, loc_data, cx_acmp_wrap, &wrapper);
}
void cx_linked_list_reverse(
@@ -798,13 +844,11 @@
}
}
-static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func;
-static _Thread_local off_t cx_ll_insert_sorted_loc_data;
-
-static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) {
- const char *left = (const char*)l + cx_ll_insert_sorted_loc_data;
- const char *right = (const char*)r + cx_ll_insert_sorted_loc_data;
- return cx_ll_insert_sorted_cmp_func(left, right);
+static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r, void *c) {
+ cx_linked_list *list = c;
+ const char *left = (const char*)l + list->loc_data;
+ const char *right = (const char*)r + list->loc_data;
+ return cx_list_compare_wrapper(left, right, list);
}
static size_t cx_ll_insert_sorted_impl(
@@ -839,29 +883,19 @@
}
CX_LL_PTR(prev, ll->loc_next) = NULL;
- // invoke the low level function
- cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc;
- cx_ll_insert_sorted_loc_data = ll->loc_data;
- if (allow_duplicates) {
- cx_linked_list_insert_sorted_chain(
- &ll->begin,
- &ll->end,
- ll->loc_prev,
- ll->loc_next,
- chain,
- cx_ll_insert_sorted_cmp_helper
- );
- list->collection.size += inserted;
- } else {
- void *duplicates = cx_linked_list_insert_unique_chain(
- &ll->begin,
- &ll->end,
- ll->loc_prev,
- ll->loc_next,
- chain,
- cx_ll_insert_sorted_cmp_helper
- );
- list->collection.size += inserted;
+ // invoke the low-level function
+ void *duplicates = cx_linked_list_insert_sorted_chain_impl(
+ &ll->begin,
+ &ll->end,
+ ll->loc_prev,
+ ll->loc_next,
+ chain,
+ cx_ll_insert_sorted_cmp_helper,
+ list,
+ allow_duplicates
+ );
+ list->collection.size += inserted;
+ if (!allow_duplicates) {
// free the nodes that did not make it into the list
while (duplicates != NULL) {
void *next = CX_LL_PTR(duplicates, ll->loc_next);
@@ -1090,12 +1124,12 @@
size_t index;
cx_linked_list *ll = (cx_linked_list *) list;
- char *node = cx_linked_list_find(
+ char *node = cx_linked_list_find_c(
ll->begin,
ll->loc_next, ll->loc_data,
- list->collection.cmpfunc, elem,
- &index
- );
+ elem, &index,
+ cx_list_compare_wrapper,
+ list);
if (node == NULL) {
return list->collection.size;
}
@@ -1111,9 +1145,9 @@
static void cx_ll_sort(struct cx_list_s *list) {
cx_linked_list *ll = (cx_linked_list *) list;
- cx_linked_list_sort(&ll->begin, &ll->end,
+ cx_linked_list_sort_c(&ll->begin, &ll->end,
ll->loc_prev, ll->loc_next, ll->loc_data,
- list->collection.cmpfunc);
+ cx_list_compare_wrapper, list);
}
static void cx_ll_reverse(struct cx_list_s *list) {
@@ -1129,9 +1163,9 @@
cx_linked_list *right = (cx_linked_list *) other;
assert(left->loc_next == right->loc_next);
assert(left->loc_data == right->loc_data);
- return cx_linked_list_compare(left->begin, right->begin,
+ return cx_linked_list_compare_c(left->begin, right->begin,
left->loc_next, left->loc_data,
- list->collection.cmpfunc);
+ cx_list_compare_wrapper, (void*)list);
}
static bool cx_ll_iter_valid(const void *it) {