# HG changeset patch # User Mike Becker # Date 1761491803 -3600 # Node ID b6fc5b1d5c5d09e3570628073b8fb72368779a31 # Parent 26e006ba651da5044f8bed56eb3b7344761feeed add implementation for cxListDifference() - issue #745 diff -r 26e006ba651d -r b6fc5b1d5c5d CHANGELOG --- a/CHANGELOG Sun Oct 26 15:51:49 2025 +0100 +++ b/CHANGELOG Sun Oct 26 16:16:43 2025 +0100 @@ -7,7 +7,7 @@ + adds support for integer keys to CxHashKey * adds support for comparing arbitrary strings without explicit call to cx_strcast() * adds cxListClone() and cxMapClone() - * adds cxMapDifference() and cxMapListDifference() + * adds cxListDifference(), cxMapDifference(), and cxMapListDifference() * adds cxListContains() and cxMapContains() * adds cxListSet() * adds cxListFirst() and cxListLast() diff -r 26e006ba651d -r b6fc5b1d5c5d docs/Writerside/topics/about.md --- a/docs/Writerside/topics/about.md Sun Oct 26 15:51:49 2025 +0100 +++ b/docs/Writerside/topics/about.md Sun Oct 26 16:16:43 2025 +0100 @@ -34,7 +34,7 @@ * adds support for integer keys to CxHashKey * adds support for comparing arbitrary strings without explicit call to cx_strcast() * adds cxListClone() and cxMapClone() -* adds cxMapDifference() and cxMapListDifference() +* adds cxListDifference(), cxMapDifference(), and cxMapListDifference() * adds cxListContains() and cxMapContains() * adds cxListSet() * adds cxListFirst() and cxListLast() diff -r 26e006ba651d -r b6fc5b1d5c5d docs/Writerside/topics/list.h.md --- a/docs/Writerside/topics/list.h.md Sun Oct 26 15:51:49 2025 +0100 +++ b/docs/Writerside/topics/list.h.md Sun Oct 26 16:16:43 2025 +0100 @@ -368,6 +368,12 @@ cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data); + +int cxListDifference(CxList *dst, + const CxList *minuend, const CxList *subtrahend, + cx_clone_func clone_func, + const CxAllocator *clone_allocator, + void *data); ``` With `cxListClone()` you can create deep copies of the elements in a list and insert them into another list. @@ -375,9 +381,13 @@ Depending on the concrete list implementation, `cxListClone()` tries to allocate enough memory up-front, before trying to insert anything. +The function `cxListDifference()` is similar to `cxListClone()`, +except that it only clones elements from the minuend that are _not_ contained in the subtrahend. +It is optimized for sorted lists, in which case it will take linear time instead of quadratic time for the operation. + Refer to the documentation of the [clone-function callback](allocator.h.md#clone-function) to learn how to implement it. -The function returns zero if and only if all clone operations were successful. +The functions return zero if and only if all clone operations were successful. > It is perfectly possible to clone items into a list of a different type. > For example, you can clone elements from a list that is just storing pointers (`CX_STORE_POINTERS`) to a list that diff -r 26e006ba651d -r b6fc5b1d5c5d src/cx/list.h --- a/src/cx/list.h Sun Oct 26 15:51:49 2025 +0100 +++ b/src/cx/list.h Sun Oct 26 16:16:43 2025 +0100 @@ -983,6 +983,34 @@ CX_EXPORT int cxListClone(CxList *dst, const CxList *src, cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data); +/** + * Clones elements from a list only if they are not present in another list. + * + * If the @p minuend does not contain duplicates, this is equivalent to adding + * the set difference to the destination list. + * + * If the destination list already contains elements, the difference + * (@p dst + @p minuend) - @p subtrahend is calculated. + * New items for @p dst are always appendend to the list, which means that the + * destination list is not necessarily sorted. + * + * This function is optimized for the case when both the @p minuend and the + * @p subtrahend are sorted. + * + * @param dst the destination list + * @param minuend the list to subtract elements from + * @param subtrahend the elements that shall be subtracted + * @param clone_func the clone function for the elements + * @param clone_allocator the allocator that is passed to the clone function + * @param data optional additional data that is passed to the clone function + * @retval zero when the elements were successfully cloned + * @retval non-zero when an allocation error occurred + */ +cx_attr_nonnull_arg(1, 2, 3) +CX_EXPORT int cxListDifference(CxList *dst, + const CxList *minuend, const CxList *subtrahend, + cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data); + #ifdef __cplusplus } // extern "C" #endif diff -r 26e006ba651d -r b6fc5b1d5c5d src/list.c --- a/src/list.c Sun Oct 26 15:51:49 2025 +0100 +++ b/src/list.c Sun Oct 26 16:16:43 2025 +0100 @@ -805,6 +805,20 @@ list->cl->deallocate(list); } +static void cx_list_pop_uninitialized_elements(CxList *list, size_t n) { + cx_destructor_func destr_bak = list->collection.simple_destructor; + cx_destructor_func2 destr2_bak = list->collection.advanced_destructor; + list->collection.simple_destructor = NULL; + list->collection.advanced_destructor = NULL; + if (n == 1) { + cxListRemove(list, list->collection.size - 1); + } else { + cxListRemoveArray(list,list->collection.size - n, n); + } + list->collection.simple_destructor = destr_bak; + list->collection.advanced_destructor = destr2_bak; +} + int cxListClone(CxList *dst, const CxList *src, cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) { if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; @@ -839,17 +853,109 @@ // if we could not clone everything, free the allocated memory // (disable the destructors!) if (cloned < src->collection.size) { - cx_destructor_func destr_bak = dst->collection.simple_destructor; - cx_destructor_func2 destr2_bak = dst->collection.advanced_destructor; - dst->collection.simple_destructor = NULL; - dst->collection.advanced_destructor = NULL; - cxListRemoveArray(dst, - orig_size + cloned, + cx_list_pop_uninitialized_elements(dst, dst->collection.size - cloned - orig_size); - dst->collection.simple_destructor = destr_bak; - dst->collection.advanced_destructor = destr2_bak; return 1; } return 0; } + +int cxListDifference(CxList *dst, + const CxList *minuend, const CxList *subtrahend, + cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) { + if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; + + // first, remove existing items from dst when needed + if (cxCollectionSorted(dst) && cxCollectionSorted(subtrahend)) { + CxIterator sub_iter = cxListIterator(dst); + CxIterator dst_iter = cxListIterator(dst); + while (cxIteratorValid(dst_iter) && cxIteratorValid(sub_iter)) { + void *dst_elem = cxIteratorCurrent(dst_iter); + void *sub_elem = cxIteratorCurrent(sub_iter); + cx_compare_func cmp = subtrahend->collection.cmpfunc; + int d = cmp(sub_elem, dst_elem); + if (d == 0) { + // is contained, so remove it + cxIteratorFlagRemoval(dst_iter); + cxIteratorNext(dst_iter); + } else if (d < 0) { + // subtrahend is smaller than the dst element, + // check the next element in the subtrahend + cxIteratorNext(sub_iter); + } else { + // subtrahend is larger than the dst element, + // check the next dst element + cxIteratorNext(dst_iter); + } + } + } else { + CxIterator dst_iter = cxListIterator(dst); + cx_foreach(void *, elem, dst_iter) { + if (cxListContains(subtrahend, elem)) { + cxIteratorFlagRemoval(dst_iter); + } + } + } + + // now perform the difference calculation + if (cxCollectionSorted(minuend) && cxCollectionSorted(subtrahend)) { + CxIterator min_iter = cxListIterator(minuend); + CxIterator sub_iter = cxListIterator(subtrahend); + while (cxIteratorValid(min_iter)) { + void *min_elem = cxIteratorCurrent(min_iter); + void *sub_elem; + int d; + if (cxIteratorValid(sub_iter)) { + sub_elem = cxIteratorCurrent(sub_iter); + cx_compare_func cmp = subtrahend->collection.cmpfunc; + d = cmp(sub_elem, min_elem); + } else { + // no more elements in the subtrahend, + // i.e., the min_elem is larger than any elem of the subtrahend + d = 1; + } + if (d == 0) { + // is contained, so skip it + cxIteratorNext(min_iter); + } else if (d < 0) { + // subtrahend is smaller than minuend, + // check the next element + cxIteratorNext(sub_iter); + } else { + // subtrahend is larger than the dst element, + // clone the minuend and advance + void **dst_mem = cxListEmplace(dst); + void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; + void* dst_ptr = clone_func(target, min_elem, clone_allocator, data); + if (dst_ptr == NULL) { + cx_list_pop_uninitialized_elements(dst, 1); + return 1; + } + if (cxCollectionStoresPointers(dst)) { + *dst_mem = dst_ptr; + } + cxIteratorNext(min_iter); + } + } + } else { + CxIterator min_iter = cxListIterator(minuend); + cx_foreach(void *, elem, min_iter) { + if (cxListContains(subtrahend, elem)) { + continue; + } + void **dst_mem = cxListEmplace(dst); + void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; + void* dst_ptr = clone_func(target, elem, clone_allocator, data); + if (dst_ptr == NULL) { + cx_list_pop_uninitialized_elements(dst, 1); + return 1; + } + if (cxCollectionStoresPointers(dst)) { + *dst_mem = dst_ptr; + } + } + } + + return 0; +}