Mercurial > hg > ucx / file diff

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