Mercurial > hg > ucx / changeset

--- a/src/cx/list.h	Sat Nov 01 19:48:50 2025 +0100
+++ b/src/cx/list.h	Sun Nov 02 18:04:35 2025 +0100
@@ -989,11 +989,6 @@
  * 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.
  *

--- a/src/list.c	Sat Nov 01 19:48:50 2025 +0100
+++ b/src/list.c	Sun Nov 02 18:04:35 2025 +0100
@@ -866,39 +866,7 @@
         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 dst_iter = cxListIterator(dst);
-        CxIterator sub_iter = cxListIterator(subtrahend);
-        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
+    // optimize for sorted collections
     if (cxCollectionSorted(minuend) && cxCollectionSorted(subtrahend)) {
         bool dst_was_empty = cxCollectionSize(dst) == 0;
 

--- a/src/map.c	Sat Nov 01 19:48:50 2025 +0100
+++ b/src/map.c	Sun Nov 02 18:04:35 2025 +0100
@@ -168,15 +168,6 @@
         cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
     if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
 
-    // if the destination map already contains something,
-    // remove what does not belong to the difference
-    CxMapIterator dst_iter = cxMapIteratorKeys(dst);
-    cx_foreach(const CxHashKey *, key, dst_iter) {
-        if (cxMapContains(subtrahend, *key)) {
-            cxIteratorFlagRemoval(dst_iter);
-        }
-    }
-
     CxMapIterator src_iter = cxMapIterator(minuend);
     cx_foreach(const CxMapEntry *, entry, src_iter) {
         if (cxMapContains(subtrahend, *entry->key)) {
@@ -203,15 +194,6 @@
         cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) {
     if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator;
 
-    // if the destination map already contains something,
-    // remove what does not belong to the difference
-    CxMapIterator dst_iter = cxMapIteratorKeys(dst);
-    cx_foreach(const CxHashKey *, key, dst_iter) {
-        if (cxListContains(keys, key)) {
-            cxIteratorFlagRemoval(dst_iter);
-        }
-    }
-
     CxMapIterator src_iter = cxMapIterator(src);
     cx_foreach(const CxMapEntry *, entry, src_iter) {
         if (cxListContains(keys, entry->key)) {

--- a/tests/test_hash_map.c	Sat Nov 01 19:48:50 2025 +0100
+++ b/tests/test_hash_map.c	Sun Nov 02 18:04:35 2025 +0100
@@ -515,11 +515,14 @@
     cx_testing_allocator_destroy(&talloc);
 }
 
+static bool test_hash_map_clone_func_max_enabled = false;
 static unsigned test_hash_map_clone_func_max_clones;
 static void *test_hash_map_clone_func(void *dst, const void *src,
         const CxAllocator *al, void *data) {
-    if (test_hash_map_clone_func_max_clones == 0) return NULL;
-    test_hash_map_clone_func_max_clones--;
+    if (test_hash_map_clone_func_max_enabled) {
+        if (test_hash_map_clone_func_max_clones == 0) return NULL;
+        test_hash_map_clone_func_max_clones--;
+    }
     if (dst == NULL) {
         dst = cxMalloc(al, sizeof(int));
     }
@@ -540,7 +543,6 @@
     }
     CX_TEST_DO {
         int c = 4;
-        test_hash_map_clone_func_max_clones = 100; // no limit
         CX_TEST_ASSERT(0 == cxMapClone(dst, src, test_hash_map_clone_func, NULL, &c));
         CX_TEST_ASSERT(cxMapSize(dst) == 5);
         CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 1);
@@ -570,8 +572,10 @@
     }
     CX_TEST_DO {
         int c = 4;
+        test_hash_map_clone_func_max_enabled = true;
         test_hash_map_clone_func_max_clones = 2;
         CX_TEST_ASSERT(0 != cxMapClone(dst, src, test_hash_map_clone_func, NULL, &c));
+        test_hash_map_clone_func_max_enabled = false;
         CX_TEST_ASSERT(cxMapSize(dst) == 4);
         CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 1);
         CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k2")) == 13);
@@ -607,7 +611,6 @@
     }
     CX_TEST_DO {
         int c = 4;
-        test_hash_map_clone_func_max_clones = 100; // no limit
         CX_TEST_ASSERT(0 == cxMapClone(dst, src, test_hash_map_clone_func, allocator, &c));
         CX_TEST_ASSERT(cxMapSize(dst) == 5);
         CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 1);
@@ -643,7 +646,6 @@
     }
     CX_TEST_DO {
         int c = 4;
-        test_hash_map_clone_func_max_clones = 100; // no limit
         CX_TEST_ASSERT(0 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, NULL, &c));
         CX_TEST_ASSERT(cxMapSize(dst) == 2);
         CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5);
@@ -670,8 +672,10 @@
     }
     CX_TEST_DO {
         int c = 4;
+        test_hash_map_clone_func_max_enabled = true;
         test_hash_map_clone_func_max_clones = 1;
         CX_TEST_ASSERT(1 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, NULL, &c));
+        test_hash_map_clone_func_max_enabled = false;
         CX_TEST_ASSERT(cxMapSize(dst) == 1);
         // the concrete element which is affected might change when the hash function changes
         CX_TEST_ASSERT(cxMapGet(dst, "k1") == NULL);
@@ -700,7 +704,6 @@
     }
     CX_TEST_DO {
         int c = 4;
-        test_hash_map_clone_func_max_clones = 100; // no limit
         CX_TEST_ASSERT(0 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c));
         CX_TEST_ASSERT(cxMapSize(dst) == 2);
         CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5);
@@ -729,8 +732,10 @@
     }
     CX_TEST_DO {
         int c = 4;
+        test_hash_map_clone_func_max_enabled = true;
         test_hash_map_clone_func_max_clones = 1;
         CX_TEST_ASSERT(1 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c));
+        test_hash_map_clone_func_max_enabled = false;
         CX_TEST_ASSERT(cxMapSize(dst) == 1);
         // the concrete element which is affected might change when the hash function changes
         CX_TEST_ASSERT(cxMapGet(dst, "k1") == NULL);
@@ -757,20 +762,19 @@
         cxMapPut(s2, s2_keys[i], &s2_values[i]);
     }
 
-    // add k5 to dst which is not in src, but shall also be not in the difference
+    // add k5 to dst which is not in src, and also not in the difference
     int *k5 = cxMallocDefault(sizeof(int));
     *k5 = 1337;
     cxMapPut(dst, "k5",k5);
 
     CX_TEST_DO {
         int c = 4;
-        test_hash_map_clone_func_max_clones = 100; // no limit
         CX_TEST_ASSERT(0 == cxMapDifference(dst, s1, s2, test_hash_map_clone_func, NULL, &c));
-        CX_TEST_ASSERT(cxMapSize(dst) == 2);
+        CX_TEST_ASSERT(cxMapSize(dst) == 3);
         CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5);
         CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL);
         CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8);
-        CX_TEST_ASSERT(cxMapGet(dst, "k5") == NULL);
+        CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k5") == 1337);
     }
     cxMapFree(dst);
     cxMapFree(s1);
@@ -794,20 +798,19 @@
         cxListAdd(keys, &key);
     }
 
-    // add k5 to dst which is not in src, but shall also be not in the difference
+    // add k5 to dst which is not in src, and also not in the difference
     int *k5 = cxMallocDefault(sizeof(int));
     *k5 = 1337;
     cxMapPut(dst, "k5",k5);
 
     CX_TEST_DO {
         int c = 4;
-        test_hash_map_clone_func_max_clones = 100; // no limit
         CX_TEST_ASSERT(0 == cxMapListDifference(dst, src, keys, test_hash_map_clone_func, NULL, &c));
-        CX_TEST_ASSERT(cxMapSize(dst) == 2);
+        CX_TEST_ASSERT(cxMapSize(dst) == 3);
         CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k1")) == 5);
         CX_TEST_ASSERT(cxMapGet(dst, "k2") == NULL);
         CX_TEST_ASSERT(*((int*)cxMapGet(dst, "k3")) == 8);
-        CX_TEST_ASSERT(cxMapGet(dst, "k5") == NULL);
+        CX_TEST_ASSERT(*(int*)cxMapGet(dst, "k5") == 1337);
     }
     cxMapFree(dst);
     cxMapFree(src);

--- a/tests/test_list.c	Sat Nov 01 19:48:50 2025 +0100
+++ b/tests/test_list.c	Sun Nov 02 18:04:35 2025 +0100
@@ -2695,11 +2695,7 @@
     CxList *minuend = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int));
     CxList *subtrahend = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int));
 
-    int dst_data[] = {
-        47, 178, 176, 83, 109, 149, 192, 38, 101, 116, 121, 73, 94, 197, 91, 79, 158, 86, 190, 138, 100, 39, 30, 144,
-        35, 182, 155, 84, 139, 186, 67, 123, 62, 37, 3, 64, 172, 56, 160, 1, 156, 132, 131, 49, 10, 126, 171, 145, 77,
-        107
-    };
+    int dst_data[] = {47, 178, 176, 83};
     int minuend_data[] = {
         153, 106, 171, 130, 74, 173, 150, 94, 27, 92, 70, 175, 200, 20, 29, 161, 88, 116, 71, 53, 199, 124, 32, 9, 76,
         151, 33, 51, 37, 65, 176, 49, 12, 162, 28, 85, 4, 177, 198, 54, 109, 188, 44, 77, 194, 63, 41, 129, 97, 83
@@ -2709,11 +2705,10 @@
         120, 78, 100, 101, 42, 21, 1, 161, 10, 114, 198, 181, 178, 136, 188, 59, 41, 73, 99, 151, 144, 118, 53, 199, 71
     };
 
-    {
-        CxList *tmp = cxArrayListCreateSimple(sizeof(int), 50);
-        cxListAddArray(tmp, dst_data, 50);
-        cxListClone(dst, tmp, test_clone_func, &talloc.base, NULL);
-        cxListFree(tmp);
+    for (unsigned i = 0 ; i < cx_nmemb(dst_data) ; i++) {
+        int *x = cxMalloc(&talloc.base, sizeof(int));
+        *x = dst_data[i];
+        cxListAdd(dst, x);
     }
     cxListAddArray(minuend, minuend_data, 50);
     cxListAddArray(subtrahend, subtrahend_data, 50);
@@ -2723,17 +2718,15 @@
         cxListSort(subtrahend);
     }
 
-    // expected 36 elements stay in dst, and 36 will be added from the difference
-    size_t expected_len = 72;
+    // expected 36 elements in the difference
+    size_t expected_len = 40;
     int expected_unsorted[] = {
-        47, 83, 109, 149, 192, 116, 121, 94, 91, 158, 86, 190, 138, 39, 30, 35, 182, 155, 84, 186, 67, 123, 62, 37,
-        3, 172, 56, 160, 156, 132, 131, 126, 171, 145, 77, 107,
+        47, 178, 176, 83,
         153, 106, 171, 74, 173, 150, 94, 92, 70, 175, 200, 20, 29, 88, 116, 124, 32, 9, 76, 33, 51, 37, 65, 12, 162,
         28, 4, 177, 54, 109, 44, 77, 194, 129, 97, 83
     };
     int expected_sorted[] = {
-        3, 30, 35, 37, 39, 47, 56, 62, 67, 77, 83, 84, 86, 91, 94, 107, 109, 116, 121, 123, 126, 131, 132, 138, 145,
-        149, 155, 156, 158, 160, 171, 172, 182, 186, 190, 192,
+        47, 83, 176, 178,
         4, 9, 12, 20, 28, 29, 32, 33, 37, 44, 51, 54, 65, 70, 74, 76, 77, 83, 88, 92, 94, 97, 106, 109, 116, 124, 129,
         150, 153, 162, 171, 173, 175, 177, 194, 200
     };
@@ -2741,7 +2734,7 @@
     if (alloc_fail) {
         test_clone_func_max_enabled = true;
         test_clone_func_max_clones = 30;
-        expected_len = 66;
+        expected_len = 34;
     }
     CxList *expected = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int), expected_len);
     cxListAddArray(expected, sorted ? expected_sorted : expected_unsorted, expected_len);