Mercurial > hg > ucx / changeset

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

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

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

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

--- 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;
+}