--- a/ucx/linked_list.c Sun Dec 07 20:16:59 2025 +0100
+++ b/ucx/linked_list.c Fri Dec 19 17:53:18 2025 +0100
@@ -31,6 +31,15 @@
#include <string.h>
#include <assert.h>
+#if __STDC_VERSION__ < 202311L
+// we cannot simply include stdalign.h
+// because Solaris is not entirely C11 complaint
+#ifndef __alignof_is_defined
+#define alignof _Alignof
+#define __alignof_is_defined 1
+#endif
+#endif
+
// LOW LEVEL LINKED LIST FUNCTIONS
#define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
@@ -56,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);
@@ -73,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;
}
@@ -85,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_ccmp_wrap, &wrapper);
+}
+
void *cx_linked_list_first(
const void *node,
ptrdiff_t loc_prev
@@ -231,26 +254,14 @@
}
}
-void cx_linked_list_insert_sorted(
- void **begin,
- void **end,
- ptrdiff_t loc_prev,
- ptrdiff_t loc_next,
- void *new_node,
- cx_compare_func cmp_func
-) {
- assert(ll_next(new_node) == NULL);
- cx_linked_list_insert_sorted_chain(
- begin, end, loc_prev, loc_next, new_node, cmp_func);
-}
-
static void *cx_linked_list_insert_sorted_chain_impl(
void **begin,
void **end,
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);
@@ -267,7 +278,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;
@@ -293,7 +304,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);
@@ -318,7 +329,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 {
@@ -347,7 +358,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 {
@@ -385,6 +396,19 @@
return dup_begin;
}
+void cx_linked_list_insert_sorted(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *new_node,
+ cx_compare_func cmp_func
+) {
+ assert(ll_next(new_node) == NULL);
+ cx_linked_list_insert_sorted_chain(
+ begin, end, loc_prev, loc_next, new_node, cmp_func);
+}
+
void cx_linked_list_insert_sorted_chain(
void **begin,
void **end,
@@ -393,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_ccmp_wrap, &wrapper, true);
}
int cx_linked_list_insert_unique(
@@ -419,9 +444,66 @@
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_ccmp_wrap, &wrapper, false);
+}
+
+void cx_linked_list_insert_sorted_c(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *new_node,
+ cx_compare_func2 cmp_func,
+ void *context
+) {
+ assert(ll_next(new_node) == NULL);
+ cx_linked_list_insert_sorted_chain_c(
+ begin, end, loc_prev, loc_next, new_node, cmp_func, context);
+}
+
+void cx_linked_list_insert_sorted_chain_c(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *insert_begin,
+ cx_compare_func2 cmp_func,
+ void *context
+) {
+ cx_linked_list_insert_sorted_chain_impl(
+ begin, end, loc_prev, loc_next,
+ insert_begin, cmp_func, context, true);
+}
+
+int cx_linked_list_insert_unique_c(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *new_node,
+ cx_compare_func2 cmp_func,
+ void *context
+) {
+ assert(ll_next(new_node) == NULL);
+ return NULL != cx_linked_list_insert_unique_chain_c(
+ begin, end, loc_prev, loc_next, new_node, cmp_func, context);
+}
+
+void *cx_linked_list_insert_unique_chain_c(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *insert_begin,
+ cx_compare_func2 cmp_func,
+ void *context
+) {
+ return cx_linked_list_insert_sorted_chain_impl(
+ begin, end, loc_prev, loc_next,
+ insert_begin, cmp_func, context, false);
}
size_t cx_linked_list_remove_chain(
@@ -502,6 +584,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,
@@ -509,21 +593,20 @@
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 ?
cxMallocDefault(sizeof(void *) * length) : sbo;
- if (sorted == NULL) abort();
+ if (sorted == NULL) abort(); // LCOV_EXCL_LINE
void *rc, *lc;
lc = ls;
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 {
@@ -557,13 +640,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);
@@ -581,7 +665,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++;
}
@@ -593,7 +677,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++;
}
@@ -601,27 +685,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_ccmp_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,
@@ -629,20 +751,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_ccmp_wrap, &wrapper);
}
void cx_linked_list_reverse(
@@ -692,8 +803,13 @@
}
static void *cx_ll_malloc_node(const cx_linked_list *list) {
- return cxZalloc(list->base.collection.allocator,
- list->loc_data + list->base.collection.elem_size + list->extra_data_len);
+ size_t n;
+ if (list->extra_data_len == 0) {
+ n = list->loc_data + list->base.collection.elem_size;
+ } else {
+ n = list->loc_extra + list->extra_data_len;
+ }
+ return cxZalloc(list->base.collection.allocator, n);
}
static int cx_ll_insert_at(
@@ -784,13 +900,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(
@@ -825,29 +939,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);
@@ -1076,12 +1180,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;
}
@@ -1097,9 +1201,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) {
@@ -1115,9 +1219,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) {
@@ -1215,7 +1319,7 @@
return result;
} else {
if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) {
- return 1;
+ return 1; // LCOV_EXCL_LINE
}
iter->elem_count++;
iter->index = list->collection.size;
@@ -1252,12 +1356,12 @@
cx_ll_sort,
cx_ll_compare,
cx_ll_reverse,
+ NULL, // no overallocation supported
cx_ll_iterator,
};
CxList *cxLinkedListCreate(
const CxAllocator *allocator,
- cx_compare_func comparator,
size_t elem_size
) {
if (allocator == NULL) {
@@ -1266,12 +1370,22 @@
cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
if (list == NULL) return NULL;
- list->extra_data_len = 0;
list->loc_prev = 0;
list->loc_next = sizeof(void*);
list->loc_data = sizeof(void*)*2;
+ list->loc_extra = -1;
+ list->extra_data_len = 0;
cx_list_init((CxList*)list, &cx_linked_list_class,
- allocator, comparator, elem_size);
+ allocator, elem_size);
return (CxList *) list;
}
+
+void cx_linked_list_extra_data(cx_linked_list *list, size_t len) {
+ list->extra_data_len = len;
+
+ off_t loc_extra = list->loc_data + list->base.collection.elem_size;
+ size_t alignment = alignof(void*);
+ size_t padding = alignment - (loc_extra % alignment);
+ list->loc_extra = loc_extra + padding;
+}