# HG changeset patch # User Mike Becker # Date 1762263522 -3600 # Node ID 9b2b40a3c9f0458cb09db84ca8d894bebd2ec0d2 # Parent 0f4d90a1ae23aa1d48d5b683b8c4d399d3abfdc4 implement cxListIntersection() - resolves #554 diff -r 0f4d90a1ae23 -r 9b2b40a3c9f0 src/list.c --- a/src/list.c Tue Nov 04 14:31:31 2025 +0100 +++ b/src/list.c Tue Nov 04 14:38:42 2025 +0100 @@ -932,3 +932,64 @@ return 0; } + +int cxListIntersection(CxList *dst, + const CxList *src, const CxList *other, + cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data) { + if (clone_allocator == NULL) clone_allocator = cxDefaultAllocator; + + // optimize for sorted collections + if (cxCollectionSorted(src) && cxCollectionSorted(other)) { + bool dst_was_empty = cxCollectionSize(dst) == 0; + + CxIterator src_iter = cxListIterator(src); + CxIterator other_iter = cxListIterator(other); + while (cxIteratorValid(src_iter) && cxIteratorValid(other_iter)) { + void *src_elem = cxIteratorCurrent(src_iter); + void *other_elem = cxIteratorCurrent(other_iter); + int d = src->collection.cmpfunc(src_elem, other_elem); + if (d == 0) { + // is contained, clone it + void **dst_mem = cxListEmplace(dst); + void *target = cxCollectionStoresPointers(dst) ? NULL : dst_mem; + void* dst_ptr = clone_func(target, src_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(src_iter); + } else if (d < 0) { + // the other element is larger, skip the source element + cxIteratorNext(src_iter); + } else { + // the source element is larger, try to find it in the other list + cxIteratorNext(other_iter); + } + } + + // if dst was empty, it is now guaranteed to be sorted + dst->collection.sorted = dst_was_empty; + } else { + CxIterator src_iter = cxListIterator(src); + cx_foreach(void *, elem, src_iter) { + if (!cxListContains(other, 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; +} diff -r 0f4d90a1ae23 -r 9b2b40a3c9f0 tests/test_list.c --- a/tests/test_list.c Tue Nov 04 14:31:31 2025 +0100 +++ b/tests/test_list.c Tue Nov 04 14:38:42 2025 +0100 @@ -2780,6 +2780,98 @@ } } +static CX_TEST_SUBROUTINE(verify_intersection, bool sorted, bool alloc_fail) { + CxTestingAllocator talloc; + cx_testing_allocator_init(&talloc); + + CxList *dst = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS); + cxDefineAdvancedDestructor(dst, cxFree, &talloc); + CxList *src = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int)); + CxList *other = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int)); + + int dst_data[] = {47, 178, 176, 83}; + int src_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 + }; + int other_data[] = { + 75, 137, 176, 111, 85, 27, 197, 141, 46, 103, 69, 146, 49, 79, 63, 130, 154, 45, 38, 139, 193, 90, 64, 142, 115, + 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 + }; + + 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(src, src_data, 50); + cxListAddArray(other, other_data, 50); + if (sorted) { + cxListSort(dst); + cxListSort(src); + cxListSort(other); + } + + // expected 14 elements in the intersection + size_t expected_len = 18; + int expected_unsorted[] = { + 47, 178, 176, 83, + 130, 27, 161, 71, 53, 199, 151, 176, 49, 85, 198, 188, 63, 41 + }; + int expected_sorted[] = { + 47, 83, 176, 178, + 27, 41, 49, 53, 63, 71, 85, 130, 151, 161, 176, 188, 198, 199 + }; + + if (alloc_fail) { + test_clone_func_max_enabled = true; + test_clone_func_max_clones = 10; + expected_len = 14; + } + CxList *expected = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int), expected_len); + cxListAddArray(expected, sorted ? expected_sorted : expected_unsorted, expected_len); + + int result = cxListIntersection(dst, src, other, test_clone_func, &talloc.base, NULL); + if (alloc_fail) { + CX_TEST_ASSERT(result != 0); + } else { + CX_TEST_ASSERT(result == 0); + } + test_clone_func_max_enabled = false; + CX_TEST_ASSERT(expected_len == cxListSize(dst)); + CX_TEST_ASSERT(0 == cxListCompare(dst, expected)); + + cxListFree(dst); + cxListFree(src); + cxListFree(other); + cxListFree(expected); + CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); +} + +CX_TEST(test_list_intersection_unsorted) { + CX_TEST_DO { + CX_TEST_CALL_SUBROUTINE(verify_intersection, false, false); + } +} + +CX_TEST(test_list_intersection_sorted) { + CX_TEST_DO { + CX_TEST_CALL_SUBROUTINE(verify_intersection, true, false); + } +} + +CX_TEST(test_list_intersection_unsorted_alloc_fail) { + CX_TEST_DO { + CX_TEST_CALL_SUBROUTINE(verify_intersection, false, true); + } +} + +CX_TEST(test_list_intersection_sorted_alloc_fail) { + CX_TEST_DO { + CX_TEST_CALL_SUBROUTINE(verify_intersection, true, true); + } +} + CX_TEST(test_list_pointer_list_supports_null) { CxList *list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS); int x = 47; @@ -3239,6 +3331,10 @@ cx_test_register(suite, test_list_difference_sorted); cx_test_register(suite, test_list_difference_unsorted_alloc_fail); cx_test_register(suite, test_list_difference_sorted_alloc_fail); + cx_test_register(suite, test_list_intersection_unsorted); + cx_test_register(suite, test_list_intersection_sorted); + cx_test_register(suite, test_list_intersection_unsorted_alloc_fail); + cx_test_register(suite, test_list_intersection_sorted_alloc_fail); return suite; }