--- 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) {