changeset
huge refactoring of collections to add support for 3-arg compare functions
Wed, 17 Dec 2025 19:05:50 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Wed, 17 Dec 2025 19:05:50 +0100
- changeset 1618
- ef7cab6eb131
- parent 1617
- d4385f35f8b0
- child 1619
- 0db02ab1457c
huge refactoring of collections to add support for 3-arg compare functions
--- a/CHANGELOG Tue Dec 16 21:33:58 2025 +0100 +++ b/CHANGELOG Wed Dec 17 19:05:50 2025 +0100 @@ -2,6 +2,8 @@ ------------------------ * adds cx_system_page_size() to allocator.h + * adds cx_compare_func2 function pointer that supports compare functions with custom data + * adds cx_cmp_memcmp() as default implementation for cx_compare_func2 * adds a new (optional) capacity parameter to cxJsonCreateArr() and cxJsonObjPutArr() * adds cxJsonFromString(), cxJsonToString(), and cxJsonToPrettyString() * adds cxJsonClone() @@ -38,6 +40,7 @@ * removes the flush feature from CxBuffer * removes the ability to remove elements from the iterators created with cxIterator() and cxIteratorPtr() * removes several unnecessary convenience functions + * removes the complicated wrapping for pointer lists Version 3.2 - 2025-11-30 ------------------------
--- a/docs/Writerside/topics/about.md Tue Dec 16 21:33:58 2025 +0100 +++ b/docs/Writerside/topics/about.md Wed Dec 17 19:05:50 2025 +0100 @@ -29,6 +29,8 @@ ### Version 4.0 - preview {collapsible="true"} * adds cx_system_page_size() to allocator.h +* adds cx_compare_func2 function pointer that supports compare functions with custom data +* adds cx_cmp_memcmp() as default implementation for cx_compare_func2 * adds a new (optional) capacity parameter to cxJsonCreateArr() and cxJsonObjPutArr() * adds cxJsonFromString(), cxJsonToString(), and cxJsonToPrettyString() * adds cxJsonClone() @@ -65,6 +67,7 @@ * removes the flush feature from CxBuffer * removes the ability to remove elements from the iterators created with cxIterator() and cxIteratorPtr() * removes several unnecessary convenience functions +* removes the complicated wrapping of pointer lists ### Version 3.2 - 2025-11-30 {collapsible="true"}
--- a/docs/Writerside/topics/array_list.h.md Tue Dec 16 21:33:58 2025 +0100 +++ b/docs/Writerside/topics/array_list.h.md Wed Dec 17 19:05:50 2025 +0100 @@ -175,6 +175,18 @@ size_t cx_array_binary_search_sup( const void *arr, size_t size, size_t elem_size, const void *elem, cx_compare_func cmp_func); + +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 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 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); ``` The function `cx_array_binary_search()` searches the array `arr` for the data pointed to by `elem` using the compare function `cmp_func`. @@ -194,9 +206,11 @@ the binary search and the infimum report the largest index and the supremum reports the smallest index of the identical items, respectively. +The function variants with the `_c` suffix allow additional `context` for the compare function. + > Note that all the above functions are only well-defined on arrays which are sorted with respect to the given compare function. > -> This can, for example, easily be achieved by calling the standard library's `qsort()` function. +> This can, for example, easily be achieved by calling the standard library's `qsort()` or `qsort_s()` function. >{style="note"} > Despite the name, neither C nor POSIX standards require the standard library's `bsearch()` function to be implemented using binary search.
--- a/docs/Writerside/topics/collection.h.md Tue Dec 16 21:33:58 2025 +0100 +++ b/docs/Writerside/topics/collection.h.md Wed Dec 17 19:05:50 2025 +0100 @@ -21,17 +21,19 @@ The following attributes are declared by the `CX_COLLECTION_BASE` macro: -| Attribute | Description | -|-----------------------|----------------------------------------------------------------------------------------------------------------| -| `allocator` | The [allocator](allocator.h.md) that shall be used for the collection data. | -| `cmpfunc` | A function to [compare](compare.h.md) two elements. | -| `elem_size` | The size of one element in bytes. | -| `size` | The size, meaning the number of elements, currently stored. | -| `simple_destructor` | An optional simple [destructor function](allocator.h.md#destructor-functions). | -| `advanced_destructor` | An optional advanced destructor function. | -| `destructor_data` | A pointer to the custom data that shall be passed to the advanced destructor. | -| `store_pointer` | A `bool` indicating whether this collection stores pointers instead of the element's data. | -| `sorted` | A `bool` indicating whether the elements are currently guaranteed sorted with respect to the compare function. | +| Attribute | Description | +|-----------------------|-----------------------------------------------------------------------------------------------------------------------------------| +| `allocator` | The [allocator](allocator.h.md) that shall be used for the collection data. | +| `elem_size` | The size of one element in bytes. | +| `size` | The size, meaning the number of elements, currently stored. | +| `simple_cmp` | A function to [compare](compare.h.md) two elements. | +| `advanced_cmp` | A function that compares two elements and supports custom data. If specified, this has precedence over the `simple_cmp` function. | +| `cmp_data` | A pointer to the custom data that shall be passed to the `advanced_cmp` function. | +| `simple_destructor` | An optional simple [destructor function](allocator.h.md#destructor-functions). | +| `advanced_destructor` | An optional advanced destructor function. | +| `destructor_data` | A pointer to the custom data that shall be passed to the advanced destructor. | +| `store_pointer` | A `bool` indicating whether this collection stores pointers instead of the element's data. | +| `sorted` | A `bool` indicating whether the elements are currently guaranteed sorted with respect to the compare function. | The attributes can be accessed directly via the `collection` member of your struct, or with the following convenience macros. @@ -44,15 +46,52 @@ In each case the argument `c` is a pointer to your collection. The macro will then access the base data with `c->collection`. -On the other hand, the following macros can be used to set the properties of a collection: +## Comparator Functions + +For working with comparators, the following macros are defined: ```C -cxSetCompareFunc(c, func) -cxSetDestructor(c, destr) -cxSetAdvancedDestructor(c, destr, data) +cxSetCompareFunc(c, func) +cxSetAdvancedCompareFunc(c, func, data) + +// use in your collection's implementation +cx_invoke_compare_func(c, left, right) + +// the following two can be used to optimize loops +cx_invoke_simple_compare_func(c, left, right) +cx_invoke_advanced_compare_func(c, left, right) + +// convenience macro for addressing and dereference elements in pointer collections +cx_ref(c, elem) +cx_deref(c, elem) ``` -More details on the destructor functions follow in the next section. +If an advanced compare function is specified, `cx_invoke_compare_func()` will only invoke the advanced comparator. +Otherwise, the simple comparator is invoked. +If neither comparator is specified, invoking a comparator leads to undefined behavior. + +In contrast to the destructors (below), comparators must always be invoked with a pointer to the element's data. +That means, if the collection is storing pointers, you must dereference the pointers to those pointers first, before invoking the comparator. +The reason for this is that the comparator cannot know if an argument points to an element of the collection or to external data the elements shall be compared with. + +A typical use case would be this: + +```C +void *arg = // ... passed as argument, e.g. in cxListContains() +void *elem = // ... get a pointer to the element +void *data; + +// manually ... +if (cxCollectionStoresPointers(this_collection)) { + data = *(void**)elem; +} else { + data = elem; +} + +// ... or with the convenience macro +data = cx_deref(this_collection, elem); +int result = cx_invoke_compare_func(this_collection, data, arg); +``` ## Destructor Functions @@ -65,7 +104,7 @@ // use in your collection's implementation cx_invoke_destructor(c, elem) -// the following two should not be used +// the following two can be used to optimize loops cx_invoke_simple_destructor(c, elem) cx_invoke_advanced_destructor(c, elem) ```
--- a/docs/Writerside/topics/compare.h.md Tue Dec 16 21:33:58 2025 +0100 +++ b/docs/Writerside/topics/compare.h.md Wed Dec 17 19:05:50 2025 +0100 @@ -2,9 +2,10 @@ The `compare.h` header file contains a collection of compare functions for various primitive types. -They come in two flavors: +They come in three flavors: - prefixed with `cx_vcmp` they are taking the values directly as arguments - prefixed with `cx_cmp` the signature is designed to be compatible with the `cx_compare_func` function pointer type. +- prefixed with `cx_ccmp` the signature is designed to be compatible with the `cx_compare_func2` function pointer type. ## Examples @@ -13,10 +14,10 @@ ```C CxList *list = cxArrayListCreate( cxDefaultAllocator, // use the default allocator - cx_cmp_int32, // the compare function for the elements sizeof(int32_t), // the size of one element 256 // reseve space for 256 elements ); +cxSetCompareFunc(list, cx_cmp_int32); // the compare function for the elements ``` In the next example we simply want to compare two `double` values with rounding tolerance. @@ -29,6 +30,16 @@ } ``` +If you only have a `cx_compare_func` at hand but need to call a function that expects a `cx_compare_func2` and a `context`, +you can use `cx_ccmp_wrap` and the `cx_compare_func_wrapper` struct to wrap your function. + +```C +void some_fun(int x, int y, cx_compare_func2 f, void *context); + +cx_compare_func_wrapper wrapper = {my_cmp_fun}; +some_fun(x, y, cx_ccmp_wrap, &wrapper); +``` + ## List of Functions ```C @@ -73,6 +84,10 @@ int cx_cmp_uintptr(const void *a, const void *b); int cx_cmp_ulongint(const void *a, const void *b); int cx_cmp_ulonglong(const void *a, const void *b); + +// Three-arguments Flavour +int cx_ccmp_memcmp(const void *a, const void *b, void *size); +int cx_ccmp_wrap(const void *a, const void *b, void *cmp_fun_wrapper); ``` <seealso>
--- a/docs/Writerside/topics/linked_list.h.md Tue Dec 16 21:33:58 2025 +0100 +++ b/docs/Writerside/topics/linked_list.h.md Wed Dec 17 19:05:50 2025 +0100 @@ -182,8 +182,13 @@ void *cx_linked_list_find(const void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, - cx_compare_func cmp_func, - const void *elem, size_t *found_index); + const void *elem, size_t *found_index, + cx_compare_func cmp_func); + +void *cx_linked_list_find_c(const void *start, + ptrdiff_t loc_advance, ptrdiff_t loc_data, + const void *elem, size_t *found_index, + cx_compare_func2 cmp_func, void *context); size_t cx_linked_list_size(const void *node, ptrdiff_t loc_next); ``` @@ -204,6 +209,8 @@ If `loc_data` is zero, `elem` is expected to point to a node structure (which is usually artificially created for the sake of comparison and not contained in the list). When the searched element is found, a pointer to the node is returned and the index (assuming `start` has index zero) is written to the optional `found_index`, if non-`NULL`. +The function `cx_linked_list_find_c()` allows additional `context` for the compare function. + The size of a list, or sub-list, can be determined with `cx_linked_list_size()` which may start at an arbitrary `node´ in the list. > A creative way of using `cx_linked_list_size()` in doubly-linked lists is to use the offset of the `prev` pointer @@ -251,6 +258,11 @@ 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); + +void cx_linked_list_sort_c(void **begin, void **end, + ptrdiff_t loc_prev, ptrdiff_t loc_next, + ptrdiff_t loc_data, cx_compare_func2 cmp_func, + void *context); ``` The function `cx_linked_list_reverse()` swaps all links of all nodes in the specified list, effectively reversing the order of elements. @@ -259,6 +271,8 @@ The non-negative `loc_data` offset is used to calculate the pointers that are passed to the compare function. If you choose `loc_data` to be zero, the pointers to the nodes themselves are passed. +The function `cx_linked_list_sort_c()` allows additional `context` for the compare function. + > The `begin` pointer is required in all of the above functions while the `end` pointer is still optional. > {style="note"} @@ -276,6 +290,12 @@ ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func ); + +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 +); ``` For comparing two linked list, you need to specify where to start, @@ -288,6 +308,8 @@ The `loc_data` offset is used to calculate the pointer that is passed to the `cmp_fnc`. This can either be the offset of a specific field in the struct or simply zero, in which case the pointers to the nodes themselves are passed to the compare function. +The function `cx_linked_list_compare_c()` allows additional `context` for the compare function. + <seealso> <category ref="apidoc"> <a href="https://ucx.sourceforge.io/api/linked__list_8h.html">linked_list.h</a>
--- a/docs/Writerside/topics/list.h.md Tue Dec 16 21:33:58 2025 +0100 +++ b/docs/Writerside/topics/list.h.md Wed Dec 17 19:05:50 2025 +0100 @@ -474,7 +474,7 @@ If you want to create your own list implementation, this is extremely easy. You need to define a function for creating your list and assign a `cx_list_class` structure with the pointers to your implementation. -Then you call the `cx_list_init()` helper function to initialize the collection sture. +Then you call the `cx_list_init()` helper function to initialize the collection structure. This also automatically adds support for `CX_STORE_POINTERS` to your list. ```C @@ -544,10 +544,6 @@ | `change_capacity` | When your list supports overallocation, the capacity shall be changed to the specified value. Return non-zero on error and zero on success. When the list does not support overallocation, this function pointer can be `NULL`. | | `iterator` | Create an iterator starting at the specified index. The Boolean argument indicates whether iteration is supposed to traverse backwards. | -> If you initialize your list with `cx_list_init()`, you do not have to worry about making a -> difference between storing pointers and storing elements, because your implementation will -> be automatically wrapped. -> This means you only have to handle the one single case described above. ### Default Class Function Implementations
--- 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; }
--- a/src/compare.c Tue Dec 16 21:33:58 2025 +0100 +++ b/src/compare.c Wed Dec 17 19:05:50 2025 +0100 @@ -29,6 +29,7 @@ #include "cx/compare.h" #include <math.h> +#include <string.h> int cx_vcmp_int(int a, int b) { if (a == b) { @@ -289,3 +290,21 @@ return p1 < p2 ? -1 : 1; } } + +int cx_acmp_memcmp( + const void *ptr1, + const void *ptr2, + void *size +) { + size_t n = *(size_t*)size; + return memcmp(ptr1, ptr2, n); +} + +int cx_acmp_wrap( + const void *ptr1, + const void *ptr2, + void *w +) { + cx_compare_func_wrapper *wrapper = w; + return wrapper->cmp(ptr1, ptr2); +}
--- a/src/cx/array_list.h Tue Dec 16 21:33:58 2025 +0100 +++ b/src/cx/array_list.h Wed Dec 17 19:05:50 2025 +0100 @@ -707,6 +707,91 @@ CX_EXPORT size_t cx_array_binary_search_sup(const void *arr, size_t size, size_t elem_size, const void *elem, cx_compare_func cmp_func); + +/** + * Searches the largest lower bound in a sorted array. + * + * In other words, this function returns the index of the largest element + * in @p arr that is less or equal to @p elem with respect to @p cmp_func. + * When no such element exists, @p size is returned. + * + * When such an element exists more than once, the largest index of all those + * elements is returned. + * + * If @p elem is contained in the array, this is identical to + * #cx_array_binary_search(). + * + * If the array is not sorted with respect to the @p cmp_func, the behavior + * is undefined. + * + * @param arr the array to search + * @param size the size of the array + * @param elem_size the size of one element + * @param elem the element to find + * @param cmp_func the compare function + * @param context the context for the compare function + * @return the index of the largest lower bound, or @p size + * @see cx_array_binary_search_sup() + * @see cx_array_binary_search() + */ +cx_attr_nonnull +CX_EXPORT 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); + +/** + * Searches an item in a sorted array. + * + * When such an element exists more than once, the largest index of all those + * elements is returned. + * + * If the array is not sorted with respect to the @p cmp_func, the behavior + * is undefined. + * + * @param arr the array to search + * @param size the size of the array + * @param elem_size the size of one element + * @param elem the element to find + * @param cmp_func the compare function + * @param context the context for the compare function + * @return the index of the element in the array, or @p size if the element + * cannot be found + * @see cx_array_binary_search_inf() + * @see cx_array_binary_search_sup() + */ +cx_attr_nonnull +CX_EXPORT 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); + +/** + * Searches the smallest upper bound in a sorted array. + * + * In other words, this function returns the index of the smallest element + * in @p arr that is greater or equal to @p elem with respect to @p cmp_func. + * When no such element exists, @p size is returned. + * + * When such an element exists more than once, the smallest index of all those + * elements is returned. + * + * If @p elem is contained in the array, this is identical to + * #cx_array_binary_search(). + * + * If the array is not sorted with respect to the @p cmp_func, the behavior + * is undefined. + * + * @param arr the array to search + * @param size the size of the array + * @param elem_size the size of one element + * @param elem the element to find + * @param cmp_func the compare function + * @param context the context for the compare function + * @return the index of the smallest upper bound, or @p size + * @see cx_array_binary_search_inf() + * @see cx_array_binary_search() + */ +cx_attr_nonnull +CX_EXPORT 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); + /** * Swaps two array elements. *
--- a/src/cx/collection.h Tue Dec 16 21:33:58 2025 +0100 +++ b/src/cx/collection.h Wed Dec 17 19:05:50 2025 +0100 @@ -58,10 +58,6 @@ */ const CxAllocator *allocator; /** - * The comparator function for the elements. - */ - cx_compare_func cmpfunc; - /** * The size of each element. */ size_t elem_size; @@ -70,6 +66,19 @@ */ size_t size; /** + * A two-argument comparator function for the elements. + */ + cx_compare_func simple_cmp; + /** + * A three-argument comparator function for the elements. + * If specified, this function has precedence over the @c simple_cmp function. + */ + cx_compare_func2 advanced_cmp; + /** + * A pointer to custom data for the @c advanced_cmp function + */ + void *cmp_data; + /** * An optional simple destructor for the collection's elements. * * @attention Read the documentation of the particular collection implementation @@ -139,6 +148,25 @@ */ #define cxCollectionStoresPointers(c) ((c)->collection.store_pointer) + +/** + * Convenience macro for adding indirection to an element if the collection is storing pointers. + * + * @param c a pointer to a struct that contains #CX_COLLECTION_BASE + * @param elem the pointer that shall be taken the address from, if the collection is storing pointers + * @return if the collection is storing pointers, takes the address of @p elem, otherwise returns @p elem + */ +#define cx_ref(c, elem) (cxCollectionStoresPointers(c) ? ((void*)&(elem)) : (elem)) + +/** + * Convenience macro for dereferencing an element if the collection is storing pointers. + * + * @param c a pointer to a struct that contains #CX_COLLECTION_BASE + * @param elem a pointer to the collection element + * @return if the collection is storing pointers, dereferences @p elem, otherwise returns @p elem + */ +#define cx_deref(c, elem) (cxCollectionStoresPointers(c) ? *((void**)(elem)) : (elem)) + /** * Indicates whether the collection can guarantee that the stored elements are currently sorted. * @@ -154,27 +182,87 @@ #define cxCollectionSorted(c) ((c)->collection.sorted || (c)->collection.size == 0) /** - * Sets the compare function for a collection. + * Sets a simple compare function for a collection. + * + * Erases a possible advanced compare function. + * If you want to set both, because you want to access the simple function + * in your advanced function, you must set the simple function first. + * + * @param c a pointer to a struct that contains #CX_COLLECTION_BASE + * @param func (@c cx_compare_func) the compare function + */ +#define cxSetCompareFunc(c, func) \ + (c)->collection.simple_cmp = (cx_compare_func)(func); \ + (c)->collection.advanced_cmp = NULL + +/** + * Sets an advanced compare function that supports custom data for a collection. + * + * @param c a pointer to a struct that contains #CX_COLLECTION_BASE + * @param func (@c cx_compare_func2) the compare function + * @param data (@c void*) the pointer to custom data that is passed to the compare function + */ +#define cxSetAdvancedCompareFunc(c, func, data) \ + (c)->collection.advanced_cmp = (cx_compare_func2) func; \ + (c)->collection.destructor_data = data + +/** + * Invokes the simple comparator function for two elements. + * + * Usually only used by collection implementations. There should be no need + * to invoke this macro manually. * * @param c a pointer to a struct that contains #CX_COLLECTION_BASE - * @param func (@c cx_compare_func) the compare function that shall be used by @c c + * @param left (@c void*) pointer to data + * @param right (@c void*) pointer to data + */ +#define cx_invoke_simple_compare_func(c, left, right) \ + (c)->collection.simple_cmp(left, right) + +/** + * Invokes the advanced comparator function for two elements. + * + * Usually only used by collection implementations. There should be no need + * to invoke this macro manually. + * + * @param c a pointer to a struct that contains #CX_COLLECTION_BASE + * @param left (@c void*) pointer to data + * @param right (@c void*) pointer to data */ -#define cxSetCompareFunc(c, func) (c)->collection.cmpfunc = (cx_compare_func)(func) +#define cx_invoke_advanced_compare_func(c, left, right) \ + (c)->collection.advanced_cmp(left, right, (c)->collection.cmp_data) + + +/** + * Invokes the configured comparator function for two elements. + * + * Usually only used by collection implementations. There should be no need + * to invoke this macro manually. + * + * @param c a pointer to a struct that contains #CX_COLLECTION_BASE + * @param left (@c void*) pointer to data + * @param right (@c void*) pointer to data + */ +#define cx_invoke_compare_func(c, left, right) \ + (((c)->collection.advanced_cmp) ? \ + cx_invoke_advanced_compare_func(c,left,right) : \ + cx_invoke_simple_compare_func(c,left,right)) /** * Sets a simple destructor function for this collection. * * @param c a pointer to a struct that contains #CX_COLLECTION_BASE - * @param destr the destructor function + * @param destr (@c cx_destructor_func) the destructor function */ #define cxSetDestructor(c, destr) \ (c)->collection.simple_destructor = (cx_destructor_func) destr /** - * Sets a simple destructor function for this collection. + * Sets an advanced destructor function for this collection. * * @param c a pointer to a struct that contains #CX_COLLECTION_BASE - * @param destr the destructor function + * @param destr (@c cx_destructor_func2) the destructor function + * @param data (@c void*) the additional data the advanced destructor is invoked with */ #define cxSetAdvancedDestructor(c, destr, data) \ (c)->collection.advanced_destructor = (cx_destructor_func2) destr; \
--- a/src/cx/compare.h Tue Dec 16 21:33:58 2025 +0100 +++ b/src/cx/compare.h Wed Dec 17 19:05:50 2025 +0100 @@ -57,6 +57,13 @@ typedef int (*cx_compare_func)(const void *left, const void *right); /** + * A comparator function comparing two arbitrary values. + * + * Functions with this signature allow specifying a pointer to custom data. + */ +typedef int (*cx_compare_func2)(const void *left, const void *right, void *data); + +/** * Compares two integers of type int. * * @note the parameters deliberately have type @c void* to be @@ -527,6 +534,41 @@ cx_attr_nonnull cx_attr_nodiscard CX_EXPORT int cx_cmp_ptr(const void *ptr1, const void *ptr2); +/** + * A @c cx_compare_func2 compatible wrapper for @c memcmp(). + * + * @param ptr1 pointer one + * @param ptr2 pointer two + * @param n (@c size_t*) a pointer to the length + * @return the result of @c memcmp() + */ +cx_attr_nonnull cx_attr_nodiscard +CX_EXPORT int cx_acmp_memcmp(const void *ptr1, const void *ptr2, void *n); + +/** Wraps a compare function for cx_acmp_wrap. */ +typedef struct { + /** The wrapped compare function */ + cx_compare_func cmp; +} cx_compare_func_wrapper; + +/** + * A @c cx_compare_func2 wrapper for a @c cx_compare_func(). + * + * This is not strictly compatible with a @c cx_compare_func2 because + * ISO C does not define conversions between function and object pointers. + * + * But it works on all tested platforms to cast a pointer to this function to + * a @c cx_compare_func2. + * + * @param ptr1 pointer one + * @param ptr2 pointer two + * @param cmp_wrapper a pointer to a @c cx_compare_func_wrapper + * @return the result of the invoked compare function + * @see cx_compare_func_wrapper_s + */ +cx_attr_nonnull cx_attr_nodiscard +CX_EXPORT int cx_acmp_wrap(const void *ptr1, const void *ptr2, void* cmp_wrapper); + #ifdef __cplusplus } // extern "C" #endif
--- a/src/cx/linked_list.h Tue Dec 16 21:33:58 2025 +0100 +++ b/src/cx/linked_list.h Wed Dec 17 19:05:50 2025 +0100 @@ -142,16 +142,34 @@ * @param start a pointer to the start node * @param loc_advance the location of the pointer to advance * @param loc_data the location of the @c data pointer within your node struct - * @param cmp_func a compare function to compare @p elem against the node data * @param elem a pointer to the element to find * @param found_index an optional pointer where the index of the found node * (given that @p start has index 0) is stored + * @param cmp_func a compare function to compare @p elem against the node data * @return a pointer to the found node or @c NULL if no matching node was found */ -cx_attr_nonnull_arg(1, 4, 5) +cx_attr_nonnull_arg(1, 4, 6) CX_EXPORT void *cx_linked_list_find(const void *start, ptrdiff_t loc_advance, - ptrdiff_t loc_data, cx_compare_func cmp_func, const void *elem, - size_t *found_index); + ptrdiff_t loc_data, const void *elem, size_t *found_index, + cx_compare_func cmp_func); + +/** + * Finds the node containing an element within a linked list. + * + * @param start a pointer to the start node + * @param loc_advance the location of the pointer to advance + * @param loc_data the location of the @c data pointer within your node struct + * @param elem a pointer to the element to find + * @param found_index an optional pointer where the index of the found node + * (given that @p start has index 0) is stored + * @param cmp_func a compare function to compare @p elem against the node data + * @param context additional context for the compare function + * @return a pointer to the found node or @c NULL if no matching node was found + */ +cx_attr_nonnull_arg(1, 4, 6) +CX_EXPORT void *cx_linked_list_find_c(const void *start, ptrdiff_t loc_advance, + ptrdiff_t loc_data, const void *elem, size_t *found_index, + cx_compare_func2 cmp_func, void *context); /** * Finds the first node in a linked list. @@ -434,16 +452,6 @@ /** * Sorts a linked list based on a comparison function. * - * This function can work with linked lists of the following structure: - * @code - * typedef struct node node; - * struct node { - * node* prev; - * node* next; - * my_payload data; - * } - * @endcode - * * @note This is a recursive function with at most logarithmic recursion depth. * * @param begin a pointer to the beginning node pointer (required) @@ -457,6 +465,23 @@ CX_EXPORT 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); +/** + * Sorts a linked list based on a comparison function. + * + * @note This is a recursive function with at most logarithmic recursion depth. + * + * @param begin a pointer to the beginning node pointer (required) + * @param end a pointer to the end node pointer (optional) + * @param loc_prev the location of a @c prev pointer within your node struct (negative if not present) + * @param loc_next the location of a @c next pointer within your node struct (required) + * @param loc_data the location of the @c data pointer within your node struct + * @param cmp_func the compare function defining the sort order + * @param context additional context for the compare function + */ +cx_attr_nonnull_arg(1, 6) +CX_EXPORT void cx_linked_list_sort_c(void **begin, void **end, + ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func2 cmp_func, void *context); + /** * Compares two lists element wise. @@ -476,6 +501,23 @@ ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func); /** + * Compares two lists element wise. + * + * @attention Both lists must have the same structure. + * + * @param begin_left the beginning of the left list (@c NULL denotes an empty list) + * @param begin_right the beginning of the right list (@c NULL denotes an empty list) + * @param loc_advance the location of the pointer to advance + * @param loc_data the location of the @c data pointer within your node struct + * @param cmp_func the function to compare the elements + * @return the first non-zero result of invoking @p cmp_func or: negative if the left list is smaller than the + * right list, positive if the left list is larger than the right list, zero if both lists are equal. + */ +cx_attr_nonnull_arg(5) +CX_EXPORT 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); + +/** * Reverses the order of the nodes in a linked list. * * @param begin a pointer to the beginning node pointer (required)
--- a/src/cx/list.h Tue Dec 16 21:33:58 2025 +0100 +++ b/src/cx/list.h Wed Dec 17 19:05:50 2025 +0100 @@ -60,10 +60,6 @@ * The list class definition. */ const cx_list_class *cl; - /** - * The actual implementation in case the list class is delegating. - */ - const cx_list_class *climpl; }; /** @@ -308,7 +304,7 @@ * allocator = cxDefaultAllocator; * } * - * MyCustomList *list = cxCalloc(allocator, 1, sizeof(MyCustomList)); + * MyCustomList *list = cxZalloc(allocator, sizeof(MyCustomList)); * if (list == NULL) return NULL; * * // initialize @@ -332,6 +328,18 @@ size_t elem_size); /** + * A @c cx_compare_func2 compatible wrapper for the compare functions of a list. + * + * @param left first element + * @param right second element + * @param list the list which is comparing the elements + * @return the comparison result + */ +cx_attr_nonnull +CX_EXPORT int cx_list_compare_wrapper( + const void *left, const void *right, void *list); + +/** * Returns the number of elements currently stored in the list. * * @param list the list
--- a/src/hash_map.c Tue Dec 16 21:33:58 2025 +0100 +++ b/src/hash_map.c Wed Dec 17 19:05:50 2025 +0100 @@ -414,8 +414,7 @@ buckets = 16; } - struct cx_hash_map_s *map = cxCalloc(allocator, 1, - sizeof(struct cx_hash_map_s)); + struct cx_hash_map_s *map = cxZalloc(allocator, sizeof(struct cx_hash_map_s)); if (map == NULL) return NULL; // initialize hash map members @@ -433,9 +432,12 @@ if (itemsize > 0) { map->base.collection.elem_size = itemsize; + map->base.collection.advanced_cmp = cx_acmp_memcmp; + map->base.collection.cmp_data = &map->base.collection.elem_size; } else { map->base.collection.elem_size = sizeof(void *); map->base.collection.store_pointer = true; + map->base.collection.simple_cmp = cx_cmp_ptr; } return (CxMap *) map;
--- a/src/kv_list.c Tue Dec 16 21:33:58 2025 +0100 +++ b/src/kv_list.c Wed Dec 17 19:05:50 2025 +0100 @@ -221,11 +221,12 @@ size_t index; cx_linked_list *ll = &kv_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; @@ -599,13 +600,8 @@ // remember the base methods and override them kv_list->map_methods = map->cl; map->cl = &cx_kv_map_class; - if (list->climpl == NULL) { - kv_list->list_methods = list->cl; - list->cl = &cx_kv_list_class; - } else { - kv_list->list_methods = list->climpl; - list->climpl = &cx_kv_list_class; - } + kv_list->list_methods = list->cl; + list->cl = &cx_kv_list_class; return list; }
--- 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) {
--- a/src/list.c Tue Dec 16 21:33:58 2025 +0100 +++ b/src/list.c Wed Dec 17 19:05:50 2025 +0100 @@ -31,198 +31,29 @@ #include <string.h> #include <assert.h> -// <editor-fold desc="Store Pointers Functionality"> - -static _Thread_local cx_compare_func cx_pl_cmpfunc_impl; - -static int cx_pl_cmpfunc( - const void *l, - const void *r -) { - // l and r are guaranteed to be non-NULL pointing to the list's memory - void *const *lptr = l; - void *const *rptr = r; - const void *left = *lptr; - const void *right = *rptr; - if (left == NULL) { - // NULL is smaller than any value except NULL - return right == NULL ? 0 : -1; - } else if (right == NULL) { - // any value is larger than NULL - return 1; +int cx_list_compare_wrapper(const void *l, const void *r, void *c) { + CxList *list = c; + const void *left; + const void *right; + if (cxCollectionStoresPointers(list)) { + left = *(void**)l; + right = *(void**)r; + // for historic reasons, we are handling the NULL case here + // because every UCX compare function does not support NULL arguments + if (left == NULL) { + if (right == NULL) return 0; + return -1; + } else if (right == NULL) { + return 1; + } + } else { + left = l; + right = r; } - return cx_pl_cmpfunc_impl(left, right); -} - -static void cx_pl_hack_cmpfunc(const struct cx_list_s *list) { - // cast away const - this is the hacky thing - struct cx_collection_s *l = (struct cx_collection_s*) &list->collection; - cx_pl_cmpfunc_impl = l->cmpfunc; - l->cmpfunc = cx_pl_cmpfunc; -} - -static void cx_pl_unhack_cmpfunc(const struct cx_list_s *list) { - // cast away const - this is the hacky thing - struct cx_collection_s *l = (struct cx_collection_s*) &list->collection; - l->cmpfunc = cx_pl_cmpfunc_impl; -} - -static void cx_pl_destructor(struct cx_list_s *list) { - list->climpl->deallocate(list); -} - -static void *cx_pl_insert_element( - struct cx_list_s *list, - size_t index, - const void *element -) { - return list->climpl->insert_element(list, index, &element); -} - -static size_t cx_pl_insert_array( - struct cx_list_s *list, - size_t index, - const void *array, - size_t n -) { - return list->climpl->insert_array(list, index, array, n); -} - -static size_t cx_pl_insert_sorted( - struct cx_list_s *list, - const void *array, - size_t n -) { - cx_pl_hack_cmpfunc(list); - size_t result = list->climpl->insert_sorted(list, array, n); - cx_pl_unhack_cmpfunc(list); - return result; -} - -static size_t cx_pl_insert_unique( - struct cx_list_s *list, - const void *array, - size_t n -) { - cx_pl_hack_cmpfunc(list); - size_t result = list->climpl->insert_unique(list, array, n); - cx_pl_unhack_cmpfunc(list); - return result; -} - -static int cx_pl_insert_iter( - struct cx_iterator_s *iter, - const void *elem, - int prepend -) { - struct cx_list_s *list = iter->src_handle; - return list->climpl->insert_iter(iter, &elem, prepend); + return cx_invoke_compare_func(list, left, right); } -static size_t cx_pl_remove( - struct cx_list_s *list, - size_t index, - size_t num, - void *targetbuf -) { - return list->climpl->remove(list, index, num, targetbuf); -} - -static void cx_pl_clear(struct cx_list_s *list) { - list->climpl->clear(list); -} - -static int cx_pl_swap( - struct cx_list_s *list, - size_t i, - size_t j -) { - return list->climpl->swap(list, i, j); -} - -static void *cx_pl_at( - const struct cx_list_s *list, - size_t index -) { - void **ptr = list->climpl->at(list, index); - return ptr == NULL ? NULL : *ptr; -} - -static size_t cx_pl_find_remove( - struct cx_list_s *list, - const void *elem, - bool remove -) { - cx_pl_hack_cmpfunc(list); - size_t ret = list->climpl->find_remove(list, &elem, remove); - cx_pl_unhack_cmpfunc(list); - return ret; -} - -static void cx_pl_sort(struct cx_list_s *list) { - cx_pl_hack_cmpfunc(list); - list->climpl->sort(list); - cx_pl_unhack_cmpfunc(list); -} - -static int cx_pl_compare( - const struct cx_list_s *list, - const struct cx_list_s *other -) { - cx_pl_hack_cmpfunc(list); - int ret = list->climpl->compare(list, other); - cx_pl_unhack_cmpfunc(list); - return ret; -} - -static void cx_pl_reverse(struct cx_list_s *list) { - list->climpl->reverse(list); -} - -static void *cx_pl_iter_current(const void *it) { - const struct cx_iterator_s *iter = it; - void **ptr = iter->base.current_impl(it); - return ptr == NULL ? NULL : *ptr; -} - -static int cx_pl_change_capacity(struct cx_list_s *list, size_t cap) { - if (list->climpl->change_capacity == NULL) { - return 0; - } else { - return list->climpl->change_capacity(list, cap); - } -} - -static struct cx_iterator_s cx_pl_iterator( - const struct cx_list_s *list, - size_t index, - bool backwards -) { - struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards); - iter.base.current_impl = iter.base.current; - iter.base.current = cx_pl_iter_current; - return iter; -} - -static cx_list_class cx_pointer_list_class = { - cx_pl_destructor, - cx_pl_insert_element, - cx_pl_insert_array, - cx_pl_insert_sorted, - cx_pl_insert_unique, - cx_pl_insert_iter, - cx_pl_remove, - cx_pl_clear, - cx_pl_swap, - cx_pl_at, - cx_pl_find_remove, - cx_pl_sort, - cx_pl_compare, - cx_pl_reverse, - cx_pl_change_capacity, - cx_pl_iterator, -}; -// </editor-fold> +#define cx_list_compare_wrapper(l, r, c) cx_list_compare_wrapper(l, r, (void*)c) // <editor-fold desc="empty list implementation"> @@ -283,27 +114,24 @@ CxList cx_empty_list = { { NULL, - NULL, 0, 0, NULL, NULL, NULL, + NULL, + NULL, + NULL, false, true, }, &cx_empty_list_class, - NULL }; CxList *const cxEmptyList = &cx_empty_list; // </editor-fold> -#define invoke_list_func(name, list, ...) \ - ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \ - (list, __VA_ARGS__) - size_t cx_list_default_insert_array( struct cx_list_s *list, size_t index, @@ -313,8 +141,7 @@ const char *src = data; size_t i = 0; for (; i < n; i++) { - if (NULL == invoke_list_func( - insert_element, list, index + i, src) + if (NULL == list->cl->insert_element(list, index + i, src) ) { return i; // LCOV_EXCL_LINE } @@ -335,7 +162,6 @@ if (n == 0) return 0; size_t elem_size = list->collection.elem_size; - cx_compare_func cmp = list->collection.cmpfunc; const char *src = sorted_data; // track indices and number of inserted items @@ -343,19 +169,19 @@ // search the list for insertion points while (di < list->collection.size) { - const void *list_elm = invoke_list_func(at, list, di); + const void *list_elm = list->cl->at(list, di); // compare the current list element with the first source element // if less, skip the list elements // if equal, skip the list elements and optionally the source elements { - int d = cmp(list_elm, src); + int d = cx_list_compare_wrapper(list_elm, src, list); if (d <= 0) { if (!allow_duplicates && d == 0) { src += elem_size; si++; processed++; // we also count duplicates for the return value - while (si < n && cmp(list_elm, src) == 0) { + while (si < n && cx_list_compare_wrapper(list_elm, src, list) == 0) { src += elem_size; si++; processed++; @@ -375,7 +201,7 @@ while (++si < n) { if (!allow_duplicates) { // skip duplicates within the source - if (cmp(next, next + elem_size) == 0) { + if (cx_list_compare_wrapper(next, next + elem_size, list) == 0) { next += elem_size; skip++; continue; @@ -389,7 +215,7 @@ } next += elem_size; // once we become larger than the list elem, break - if (cmp(list_elm, next) <= 0) { + if (cx_list_compare_wrapper(list_elm, next, list) <= 0) { break; } // otherwise, we can insert one more @@ -398,11 +224,11 @@ // insert the elements at location si if (ins == 1) { - if (NULL == invoke_list_func(insert_element, list, di, src)) { + if (NULL == list->cl->insert_element(list, di, src)) { return processed; // LCOV_EXCL_LINE } } else { - size_t r = invoke_list_func(insert_array, list, di, src, ins); + size_t r = list->cl->insert_array(list, di, src, ins); if (r < ins) { return processed + r; // LCOV_EXCL_LINE } @@ -420,13 +246,13 @@ // insert remaining items if (si < n) { if (allow_duplicates) { - processed += invoke_list_func(insert_array, list, di, src, n - si); + processed += list->cl->insert_array(list, di, src, n - si); } else { - const void *last = di == 0 ? NULL : invoke_list_func(at, list, di - 1); + const void *last = di == 0 ? NULL : list->cl->at(list, di - 1); for (; si < n; si++) { // skip duplicates within the source - if (last == NULL || cmp(last, src) != 0) { - if (NULL == invoke_list_func(insert_element, list, di, src)) { + if (last == NULL || cx_list_compare_wrapper(last, src, list) != 0) { + if (NULL == list->cl->insert_element(list, di, src)) { return processed; // LCOV_EXCL_LINE } last = src; @@ -457,6 +283,12 @@ return cx_list_default_insert_sorted_impl(list, sorted_data, n, false); } +// 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); +} + void cx_list_default_sort(struct cx_list_s *list) { size_t elem_size = list->collection.elem_size; size_t list_size = list->collection.size; @@ -466,19 +298,20 @@ // copy elements from source array char *loc = tmp; for (size_t i = 0; i < list_size; i++) { - void *src = invoke_list_func(at, list, i); + void *src = list->cl->at(list, i); memcpy(loc, src, elem_size); loc += elem_size; } // qsort - qsort(tmp, list_size, elem_size, - list->collection.cmpfunc); + // TODO: qsort_s() is not as nice as we thought + cx_hack_for_qsort_list = list; + qsort(tmp, list_size, elem_size, cx_hack_cmp_for_qsort); // copy elements back loc = tmp; for (size_t i = 0; i < list_size; i++) { - void *dest = invoke_list_func(at, list, i); + void *dest = list->cl->at(list, i); memcpy(dest, loc, elem_size); loc += elem_size; } @@ -496,8 +329,8 @@ void *tmp = cxMallocDefault(elem_size); if (tmp == NULL) return 1; // LCOV_EXCL_LINE - void *ip = invoke_list_func(at, list, i); - void *jp = invoke_list_func(at, list, j); + void *ip = list->cl->at(list, i); + void *jp = list->cl->at(list, j); memcpy(tmp, ip, elem_size); memcpy(ip, jp, elem_size); @@ -516,17 +349,20 @@ ) { list->cl = cl; list->collection.allocator = allocator; - list->collection.cmpfunc = NULL; + list->collection.size = 0; + list->collection.sorted = false; // should be set by the implementation if (elem_size > 0) { list->collection.elem_size = elem_size; + list->collection.simple_cmp = NULL; + list->collection.advanced_cmp = cx_acmp_memcmp; + list->collection.cmp_data = &list->collection.elem_size; + list->collection.store_pointer = false; } else { list->collection.elem_size = sizeof(void *); - if (list->collection.cmpfunc == NULL) { - list->collection.cmpfunc = cx_cmp_ptr; - } + list->collection.simple_cmp = cx_cmp_ptr; + list->collection.advanced_cmp = NULL; + list->collection.cmp_data = NULL; list->collection.store_pointer = true; - list->climpl = list->cl; - list->cl = &cx_pointer_list_class; } } @@ -534,33 +370,28 @@ const CxList *list, const CxList *other ) { + // check if we cannot use the list internal function bool cannot_optimize = false; // if one is storing pointers but the other is not cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer; - // if one class is wrapped but the other is not - cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL); - - // if the compare functions do not match or both are NULL - if (!cannot_optimize) { - cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ? - list->climpl->compare : list->cl->compare); - cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ? - other->climpl->compare : other->cl->compare); - cannot_optimize |= list_cmp != other_cmp; - cannot_optimize |= list_cmp == NULL; - } + // check if the lists are incompatible or this list does not implement compare + cx_compare_func list_cmp = (cx_compare_func) list->cl->compare; + cx_compare_func other_cmp = (cx_compare_func) other->cl->compare; + cannot_optimize |= list_cmp != other_cmp; + cannot_optimize |= list_cmp == NULL; if (cannot_optimize) { // lists are definitely different - cannot use internal compare function if (list->collection.size == other->collection.size) { - CxIterator left = list->cl->iterator(list, 0, false); - CxIterator right = other->cl->iterator(other, 0, false); + CxIterator left = cxListIterator(list); + CxIterator right = cxListIterator(other); for (size_t i = 0; i < list->collection.size; i++) { void *leftValue = cxIteratorCurrent(left); void *rightValue = cxIteratorCurrent(right); - int d = list->collection.cmpfunc(leftValue, rightValue); + // values are already unwrapped, invoke immediately + int d = cx_invoke_compare_func(list, leftValue, rightValue); if (d != 0) { return d; } @@ -583,7 +414,7 @@ int cxListAdd(CxList *list, const void *elem) { list->collection.sorted = false; - return list->cl->insert_element(list, list->collection.size, elem) == NULL; + return list->cl->insert_element(list, list->collection.size, cx_ref(list, elem)) == NULL; } size_t cxListAddArray(CxList *list, const void *array, size_t n) { @@ -593,7 +424,7 @@ int cxListInsert(CxList *list, size_t index, const void *elem) { list->collection.sorted = false; - return list->cl->insert_element(list, index, elem) == NULL; + return list->cl->insert_element(list, index, cx_ref(list, elem)) == NULL; } void *cxListEmplaceAt(CxList *list, size_t index) { @@ -620,11 +451,6 @@ iter.index = 0; // replace the valid function to abort iteration when c is reached iter.base.valid = cx_list_emplace_iterator_valid; - // if we are storing pointers, we want to return the pure pointers. - // therefore, we must unwrap the "current" method - if (list->collection.store_pointer) { - iter.base.current = iter.base.current_impl; - } return iter; } @@ -635,15 +461,13 @@ int cxListInsertSorted(CxList *list, const void *elem) { assert(cxCollectionSorted(list)); list->collection.sorted = true; - const void *data = list->collection.store_pointer ? &elem : elem; - return list->cl->insert_sorted(list, data, 1) == 0; + return list->cl->insert_sorted(list, cx_ref(list, elem), 1) == 0; } int cxListInsertUnique(CxList *list, const void *elem) { if (cxCollectionSorted(list)) { list->collection.sorted = true; - const void *data = list->collection.store_pointer ? &elem : elem; - return list->cl->insert_unique(list, data, 1) == 0; + return list->cl->insert_unique(list, cx_ref(list, elem), 1) == 0; } else { if (cxListContains(list, elem)) { return 0; @@ -672,8 +496,7 @@ const char *source = array; for (size_t i = 0 ; i < n; i++) { // note: this also checks elements added in a previous iteration - const void *data = list->collection.store_pointer ? - *((const void**)source) : source; + const void *data = cx_deref(list, source); if (!cxListContains(list, data)) { if (cxListAdd(list, data)) { return i; // LCOV_EXCL_LINE @@ -686,15 +509,15 @@ } int cxListInsertAfter(CxIterator *iter, const void *elem) { - CxList* list = (CxList*)iter->src_handle; + CxList* list = iter->src_handle; list->collection.sorted = false; - return list->cl->insert_iter(iter, elem, 0); + return list->cl->insert_iter(iter, cx_ref(list, elem), 0); } int cxListInsertBefore(CxIterator *iter, const void *elem) { - CxList* list = (CxList*)iter->src_handle; + CxList* list = iter->src_handle; list->collection.sorted = false; - return list->cl->insert_iter(iter, elem, 1); + return list->cl->insert_iter(iter, cx_ref(list, elem), 1); } int cxListRemove(CxList *list, size_t index) { @@ -733,15 +556,17 @@ } void *cxListAt(const CxList *list, size_t index) { - return list->cl->at(list, index); + void *result = list->cl->at(list, index); + if (result == NULL) return NULL; + return cx_deref(list, result); } void *cxListFirst(const CxList *list) { - return list->cl->at(list, 0); + return cxListAt(list, 0); } void *cxListLast(const CxList *list) { - return list->cl->at(list, list->collection.size - 1); + return cxListAt(list, list->collection.size - 1); } int cxListSet(CxList *list, size_t index, const void *elem) { @@ -750,8 +575,7 @@ } if (list->collection.store_pointer) { - // For pointer collections, always use climpl - void **target = list->climpl->at(list, index); + void **target = list->cl->at(list, index); *target = (void *)elem; } else { void *target = list->cl->at(list, index); @@ -761,32 +585,48 @@ return 0; } +static void *cx_pl_iter_current(const void *it) { + const struct cx_iterator_s *iter = it; + void **ptr = iter->base.current_impl(it); + return ptr == NULL ? NULL : *ptr; +} + +CX_INLINE CxIterator cx_pl_iter_wrap(const CxList *list, CxIterator iter) { + if (cxCollectionStoresPointers(list)) { + iter.base.current_impl = iter.base.current; + iter.base.current = cx_pl_iter_current; + return iter; + } else { + return iter; + } +} + CxIterator cxListIteratorAt(const CxList *list, size_t index) { if (list == NULL) list = cxEmptyList; - return list->cl->iterator(list, index, false); + return cx_pl_iter_wrap(list, list->cl->iterator(list, index, false)); } CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index) { if (list == NULL) list = cxEmptyList; - return list->cl->iterator(list, index, true); + return cx_pl_iter_wrap(list, list->cl->iterator(list, index, true)); } CxIterator cxListIterator(const CxList *list) { if (list == NULL) list = cxEmptyList; - return list->cl->iterator(list, 0, false); + return cx_pl_iter_wrap(list, list->cl->iterator(list, 0, false)); } CxIterator cxListBackwardsIterator(const CxList *list) { if (list == NULL) list = cxEmptyList; - return list->cl->iterator(list, list->collection.size - 1, true); + return cx_pl_iter_wrap(list, list->cl->iterator(list, list->collection.size - 1, true)); } size_t cxListFind(const CxList *list, const void *elem) { - return list->cl->find_remove((CxList*)list, elem, false); + return list->cl->find_remove((CxList*)list, cx_ref(list, elem), false); } bool cxListContains(const CxList* list, const void* elem) { - return list->cl->find_remove((CxList*)list, elem, false) < list->collection.size; + return list->cl->find_remove((CxList*)list, cx_ref(list, elem), false) < list->collection.size; } bool cxListIndexValid(const CxList *list, size_t index) { @@ -794,7 +634,7 @@ } size_t cxListFindRemove(CxList *list, const void *elem) { - return list->cl->find_remove(list, elem, true); + return list->cl->find_remove(list, cx_ref(list, elem), true); } void cxListSort(CxList *list) { @@ -901,8 +741,7 @@ int d; if (cxIteratorValid(sub_iter)) { sub_elem = cxIteratorCurrent(sub_iter); - cx_compare_func cmp = subtrahend->collection.cmpfunc; - d = cmp(sub_elem, min_elem); + d = cx_list_compare_wrapper(sub_elem, min_elem, subtrahend); } else { // no more elements in the subtrahend, // i.e., the min_elem is larger than any elem of the subtrahend @@ -970,7 +809,7 @@ while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) { void *src_elem = cxIteratorCurrent(src_iter); void *other_elem = cxIteratorCurrent(other_iter); - int d = src->collection.cmpfunc(src_elem, other_elem); + int d = cx_list_compare_wrapper(src_elem, other_elem, src); if (d == 0) { // is contained, clone it void **dst_mem = cxListEmplace(dst); @@ -1040,7 +879,7 @@ } else { src_elem = cxIteratorCurrent(src_iter); other_elem = cxIteratorCurrent(other_iter); - d = src->collection.cmpfunc(src_elem, other_elem); + d = cx_list_compare_wrapper(src_elem, other_elem, src); } void *clone_from; if (d < 0) {
--- a/src/map.c Tue Dec 16 21:33:58 2025 +0100 +++ b/src/map.c Wed Dec 17 19:05:50 2025 +0100 @@ -70,12 +70,14 @@ CxMap cx_empty_map = { { NULL, - NULL, 0, 0, NULL, NULL, NULL, + NULL, + NULL, + NULL, false, true }, @@ -349,7 +351,7 @@ return -1; } // compare the values - const int d = map->collection.cmpfunc(value_left, value_right); + const int d = cx_invoke_compare_func(map, value_left, value_right); if (d != 0) { return d; }
--- a/tests/test_hash_map.c Tue Dec 16 21:33:58 2025 +0100 +++ b/tests/test_hash_map.c Wed Dec 17 19:05:50 2025 +0100 @@ -48,7 +48,9 @@ CX_TEST_ASSERT(map->collection.size == 0); CX_TEST_ASSERT(map->collection.allocator == allocator); CX_TEST_ASSERT(!map->collection.store_pointer); - CX_TEST_ASSERT(map->collection.cmpfunc == NULL); + CX_TEST_ASSERT(map->collection.simple_cmp == NULL); + CX_TEST_ASSERT(map->collection.advanced_cmp == cx_acmp_memcmp); + CX_TEST_ASSERT(map->collection.cmp_data == &map->collection.elem_size); CX_TEST_ASSERT(map->collection.simple_destructor == NULL); CX_TEST_ASSERT(map->collection.advanced_destructor == NULL); CX_TEST_ASSERT(map->collection.destructor_data == NULL); @@ -74,6 +76,8 @@ CX_TEST_ASSERT(map->collection.allocator == allocator); CX_TEST_ASSERT(map->collection.store_pointer); CX_TEST_ASSERT(map->collection.elem_size == sizeof(void *)); + CX_TEST_ASSERT(map->collection.simple_cmp == cx_cmp_ptr); + CX_TEST_ASSERT(map->collection.advanced_cmp == NULL); cxMapFree(map); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); @@ -1272,9 +1276,8 @@ CX_TEST(test_hash_map_compare) { CxMap *map1 = cxHashMapCreate(NULL, sizeof(int), 0); CxMap *map2 = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0); - // TODO: fix specification of compare function once #622 is realized - map1->collection.cmpfunc = cx_cmp_int; - map2->collection.cmpfunc = cx_cmp_int; + cxSetCompareFunc(map1, cx_cmp_int); + cxSetCompareFunc(map2, cx_cmp_int); // some ints we can point to in the pointer map int z13 = 13;
--- a/tests/test_list.c Tue Dec 16 21:33:58 2025 +0100 +++ b/tests/test_list.c Wed Dec 17 19:05:50 2025 +0100 @@ -491,24 +491,24 @@ int s; s = 2; node *n = list; - CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == n); + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, &s, &i, cx_cmp_int) == n); CX_TEST_ASSERT(i == 0); n = n->next; s = 4; - CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == n); + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, &s, &i, cx_cmp_int) == n); CX_TEST_ASSERT(i == 1); n = n->next; s = 6; - CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == n); + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, &s, &i, cx_cmp_int) == n); CX_TEST_ASSERT(i == 2); n = n->next; s = 8; - CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == n); + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, &s, &i, cx_cmp_int) == n); CX_TEST_ASSERT(i == 3); s = 10; - CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == NULL); + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, &s, &i, cx_cmp_int) == NULL); s = -2; - CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, cx_cmp_int, &s, &i) == NULL); + CX_TEST_ASSERT(cx_linked_list_find(list, loc_next, loc_data, &s, &i, cx_cmp_int) == NULL); } destroy_nodes_test_data(list); } @@ -1288,7 +1288,8 @@ CX_TEST_ASSERT(list->collection.destructor_data == NULL); CX_TEST_ASSERT(cxListSize(list) == 0); CX_TEST_ASSERT(list->collection.allocator == alloc); - CX_TEST_ASSERT(list->collection.cmpfunc == cx_cmp_int); + CX_TEST_ASSERT(list->collection.simple_cmp == cx_cmp_int); + CX_TEST_ASSERT(list->collection.advanced_cmp == NULL); CX_TEST_ASSERT(!list->collection.store_pointer); cxListFree(list); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); @@ -1306,7 +1307,9 @@ CX_TEST_ASSERT(list->collection.destructor_data == NULL); CX_TEST_ASSERT(cxListSize(list) == 0); CX_TEST_ASSERT(list->collection.allocator == cxDefaultAllocator); - CX_TEST_ASSERT(list->collection.cmpfunc == NULL); + CX_TEST_ASSERT(list->collection.simple_cmp == NULL); + CX_TEST_ASSERT(list->collection.advanced_cmp == cx_acmp_memcmp); + CX_TEST_ASSERT(list->collection.cmp_data == &list->collection.elem_size); CX_TEST_ASSERT(!list->collection.store_pointer); } cxListFree(list); @@ -1322,7 +1325,8 @@ CX_TEST_ASSERT(list->collection.destructor_data == NULL); CX_TEST_ASSERT(cxListSize(list) == 0); CX_TEST_ASSERT(list->collection.allocator == cxDefaultAllocator); - CX_TEST_ASSERT(list->collection.cmpfunc == cx_cmp_ptr); + CX_TEST_ASSERT(list->collection.simple_cmp == cx_cmp_ptr); + CX_TEST_ASSERT(list->collection.advanced_cmp == NULL); CX_TEST_ASSERT(list->collection.store_pointer); } cxListFree(list); @@ -1342,7 +1346,8 @@ CX_TEST_ASSERT(list->collection.destructor_data == NULL); CX_TEST_ASSERT(cxListSize(list) == 0); CX_TEST_ASSERT(list->collection.allocator == alloc); - CX_TEST_ASSERT(list->collection.cmpfunc == cx_cmp_int); + CX_TEST_ASSERT(list->collection.simple_cmp == cx_cmp_int); + CX_TEST_ASSERT(list->collection.advanced_cmp == NULL); CX_TEST_ASSERT(!list->collection.store_pointer); cxListFree(list); CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); @@ -1360,7 +1365,9 @@ CX_TEST_ASSERT(list->collection.destructor_data == NULL); CX_TEST_ASSERT(cxListSize(list) == 0); CX_TEST_ASSERT(list->collection.allocator == cxDefaultAllocator); - CX_TEST_ASSERT(list->collection.cmpfunc == NULL); + CX_TEST_ASSERT(list->collection.simple_cmp == NULL); + CX_TEST_ASSERT(list->collection.advanced_cmp == cx_acmp_memcmp); + CX_TEST_ASSERT(list->collection.cmp_data == &list->collection.elem_size); CX_TEST_ASSERT(!list->collection.store_pointer); } cxListFree(list); @@ -1376,7 +1383,8 @@ CX_TEST_ASSERT(list->collection.destructor_data == NULL); CX_TEST_ASSERT(cxListSize(list) == 0); CX_TEST_ASSERT(list->collection.allocator == cxDefaultAllocator); - CX_TEST_ASSERT(list->collection.cmpfunc == cx_cmp_ptr); + CX_TEST_ASSERT(list->collection.simple_cmp == cx_cmp_ptr); + CX_TEST_ASSERT(list->collection.advanced_cmp == NULL); CX_TEST_ASSERT(list->collection.store_pointer); } cxListFree(list); @@ -1543,19 +1551,14 @@ roll_out_test_invokers(name) static void set_default_class_funcs(CxList *list, cx_list_class *defaulted_cl) { - const cx_list_class *cl = list->climpl == NULL ? list->cl : list->climpl; - memcpy(defaulted_cl, cl, sizeof(cx_list_class)); + memcpy(defaulted_cl, list->cl, sizeof(cx_list_class)); defaulted_cl->insert_array = cx_list_default_insert_array; defaulted_cl->insert_unique = cx_list_default_insert_unique; defaulted_cl->insert_sorted = cx_list_default_insert_sorted; defaulted_cl->sort = cx_list_default_sort; defaulted_cl->swap = cx_list_default_swap; defaulted_cl->compare = NULL; - if (list->climpl == NULL) { - list->cl = defaulted_cl; - } else { - list->climpl = defaulted_cl; - } + list->cl = defaulted_cl; } #define do_set_default_class_funcs(list) \
--- a/tests/ucxtest.c Tue Dec 16 21:33:58 2025 +0100 +++ b/tests/ucxtest.c Wed Dec 17 19:05:50 2025 +0100 @@ -57,7 +57,7 @@ CxTestSuite *cx_test_suite_printf(void); CxTestSuite *cx_test_suite_mempool(void); -#define break_on_failure false +#define break_on_failure true #define run_tests(suite) cx_test_run_stdout(suite); success += (suite)->success; failure += (suite)->failure; \ if (!cx_testing_allocator_verify(&testing_allocator) || (break_on_failure && failure > 0)) break; #define execute_test_suites(...) unsigned success = 0, failure = 0; CxTestSuite* test_suites[] = {__VA_ARGS__}; \
