# HG changeset patch # User Mike Becker # Date 1762103075 -3600 # Node ID a58c65d31342203718ad6462e429d429e477eab9 # Parent dc886f1a6155247a187da01cf322e4b6d73f50a3 difference shall not check already present items in the destination - fixes #753 diff -r dc886f1a6155 -r a58c65d31342 src/cx/list.h --- 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. * diff -r dc886f1a6155 -r a58c65d31342 src/list.c --- 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; diff -r dc886f1a6155 -r a58c65d31342 src/map.c --- 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)) { diff -r dc886f1a6155 -r a58c65d31342 tests/test_hash_map.c --- 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); diff -r dc886f1a6155 -r a58c65d31342 tests/test_list.c --- 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);