Mercurial > hg > ucx / changeset

--- a/CHANGELOG	Mon Oct 20 20:38:02 2025 +0200
+++ b/CHANGELOG	Tue Oct 21 17:06:17 2025 +0200
@@ -6,6 +6,7 @@
  * adds new key-value-based list implementation
  + adds support for integer keys to CxHashKey
  * adds support for comparing arbitrary strings without explicit call to cx_strcast()
+ * adds cxListClone()
  * adds cxListSet()
  * adds cxListContains()
  * adds cxListFirst() and cxListLast()

--- a/docs/Writerside/topics/about.md	Mon Oct 20 20:38:02 2025 +0200
+++ b/docs/Writerside/topics/about.md	Tue Oct 21 17:06:17 2025 +0200
@@ -33,6 +33,7 @@
 * adds new key-value-based list implementation
 * adds support for integer keys to CxHashKey
 * adds support for comparing arbitrary strings without explicit call to cx_strcast()
+* adds cxListClone()
 * adds cxListSet()
 * adds cxListContains()
 * adds cxListFirst() and cxListLast()

--- a/docs/Writerside/topics/allocator.h.md	Mon Oct 20 20:38:02 2025 +0200
+++ b/docs/Writerside/topics/allocator.h.md	Tue Oct 21 17:06:17 2025 +0200
@@ -147,6 +147,8 @@
 The `allocator.h` header also declares two function pointers for destructor functions.
 
 ```C
+#include <cx/allocator.h>
+
 typedef void (*cx_destructor_func)(void *memory);
 typedef void (*cx_destructor_func2)(void *data, void *memory);
 ```
@@ -171,6 +173,54 @@
 > On the other hand, when the list is storing just pointers to the elements, you _may_ want the destructor
 > function to also deallocate the element's memory when the element is removed from that list.
 
+## Clone Function
+
+```C
+#include <cx/allocator.h>
+
+typedef void*(cx_clone_func)(
+        void *target, const void *source,
+        const CxAllocator *allocator,
+        void *data);
+```
+
+A clone function is a callback invoked when a deep copy of an object is supposed to be made.
+If `target` is not `NULL`, memory for the first level was already allocated, and only the deeper levels need to
+be allocated by the clone function.
+If `target` is `NULL`, the clone function must allocate all memory.
+The `source` pointer is never `NULL` and points to the source object.
+The optional `data` pointer can be used to pass additional state.
+
+A very basic clone function that performs a deep copy of a struct with two strings is shown below.
+
+```C
+#include <cx/string.h>
+#include <cx/allocator.h>
+
+struct kv_pair {
+    cxmutstr key;
+    cxmutstr value;
+};
+
+void *clone_kv_pair(
+        void *target, const void *source,
+        const CxAllocator *allocator,
+        [[maybe_unused]] void *data) {
+    const struct kv_pair *src = source;
+    struct kv_pair *dst;
+    if (target == NULL) {
+        dst = cxMalloc(allocator, sizeof(struct kv_pair));
+    } else {
+        dst = target;
+    }
+    dst->key = cx_strdup_a(allocator, src->key);
+    dst->value = cx_strdup_a(allocator, src->value);
+    return dst;
+}
+```
+
+Clone functions are, for example, used by the functions to clone [lists](list.h.md#clone) or maps.
+
 <seealso>
 <category ref="apidoc">
 <a href="https://ucx.sourceforge.io/api/allocator_8h.html">allocator.h</a>

--- a/docs/Writerside/topics/list.h.md	Mon Oct 20 20:38:02 2025 +0200
+++ b/docs/Writerside/topics/list.h.md	Tue Oct 21 17:06:17 2025 +0200
@@ -352,6 +352,24 @@
 The return value of `cxListCompare()` is zero if the lists are element-wise equivalent.
 If they are not, the non-zero return value equals the return value of the used compare function for the first pair of elements that are not equal. 
 
+## Clone
+
+```C
+#include <cx/allocator.h>
+
+typedef void*(cx_clone_func)(
+        void *target, const void *source,
+        const CxAllocator *allocator,
+        void *data);
+
+#include <cx/list.h>
+
+size_t cxListClone(CxList *dst, const CxList *src,
+        cx_clone_func clone_func,
+        const CxAllocator *clone_allocator,
+        void *data);
+```
+
 ## Dispose
 
 ```C

--- a/src/cx/list.h	Mon Oct 20 20:38:02 2025 +0200
+++ b/src/cx/list.h	Tue Oct 21 17:06:17 2025 +0200
@@ -961,6 +961,27 @@
 CX_EXPORT void cxListFree(CxList *list);
 
 
+/**
+ * Performs a deep clone of one list into another.
+ *
+ * If the destination list already contains elements, the cloned elements
+ * are appended to that list.
+ *
+ * @attention If the cloned elements need to be destroyed by a destructor
+ * function, you must make sure that the destination list also uses this
+ * destructor function.
+ *
+ * @param dst the destination list
+ * @param src the source list
+ * @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
+ * @return the number of elements that have been successfully cloned
+ */
+cx_attr_nonnull_arg(1, 2, 3)
+CX_EXPORT size_t cxListClone(CxList *dst, const CxList *src,
+        cx_clone_func clone_func, const CxAllocator *clone_allocator, void *data);
+
 #ifdef __cplusplus
 } // extern "C"
 #endif

--- a/src/list.c	Mon Oct 20 20:38:02 2025 +0200
+++ b/src/list.c	Tue Oct 21 17:06:17 2025 +0200
@@ -804,3 +804,61 @@
     if (list == NULL) return;
     list->cl->deallocate(list);
 }
+
+size_t cxListClone(CxList *dst, const CxList *src, cx_clone_func clone_func,
+    const CxAllocator *clone_allocator, void *data) {
+
+    // remember the original size
+    size_t orig_size = dst->collection.size;
+
+    // first, try to allocate the memory in the new list
+    CxIterator empl_iter = cxListEmplaceArray(dst, src->collection.size);
+
+    // get an iterator over the source elements
+    CxIterator src_iter = cxListIterator(src);
+
+    // now clone the elements
+    size_t cloned = empl_iter.elem_count;
+    if (cxCollectionStoresPointers(dst)) {
+        for (size_t i = 0 ; i < empl_iter.elem_count; i++) {
+            void *src_elem = cxIteratorCurrent(src_iter);
+            void **dest_memory = cxIteratorCurrent(empl_iter);
+            void *dest_ptr = clone_func(NULL, src_elem, clone_allocator, data);
+            if (dest_ptr == NULL) {
+                cloned = i;
+                break;
+            }
+            *dest_memory = dest_ptr;
+            cxIteratorNext(src_iter);
+            cxIteratorNext(empl_iter);
+        }
+    } else {
+        for (size_t i = 0 ; i < empl_iter.elem_count; i++) {
+            void *src_elem = cxIteratorCurrent(src_iter);
+            void *dest_memory = cxIteratorCurrent(empl_iter);
+            if (clone_func(dest_memory, src_elem, clone_allocator, data) == NULL) {
+                cloned = i;
+                break;
+            }
+            cxIteratorNext(src_iter);
+            cxIteratorNext(empl_iter);
+        }
+    }
+
+    // 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,
+            dst->collection.size - cloned - orig_size);
+        dst->collection.simple_destructor = destr_bak;
+        dst->collection.advanced_destructor = destr2_bak;
+    }
+
+    // return how many elements we have cloned
+    return cloned;
+}
\ No newline at end of file

--- a/tests/test_list.c	Mon Oct 20 20:38:02 2025 +0200
+++ b/tests/test_list.c	Tue Oct 21 17:06:17 2025 +0200
@@ -2526,6 +2526,86 @@
     free(testdata);
 })
 
+static void *test_clone_func(void *dest, const void *src, const CxAllocator *al, void *data) {
+    if (dest == NULL) {
+        dest = cxMalloc(al, sizeof(int));
+    }
+
+    *((int*) dest) = *(int*) src + *(int*) data;
+    (*(int*) data)++;
+
+    // TODO: create a separate test with another clone func which simulates a failure after a few allocations
+    return dest;
+}
+
+static CX_TEST_SUBROUTINE(verify_clone, CxList *target, CxList *source, bool target_isptrlist) {
+    // testing allocator for the target elements if target_isptrlist is true
+    CxTestingAllocator talloc;
+    cx_testing_allocator_init(&talloc);
+    CxAllocator *testing_alloc = &talloc.base;
+
+    // register a destructor for the target list if it is storing pointers
+    if (target_isptrlist) {
+        cxDefineAdvancedDestructor(target, cxFree, testing_alloc);
+    }
+
+    // fill the source list
+    int source_data[8] = array_init(1, 2, 3, 4, 5, 6, 7, 8);
+    for (unsigned i = 0 ; i < 8 ; i++) {
+        cxListAdd(source, &source_data[i]);
+    }
+
+    // add some initial data to the target
+    int initial_data[4] = array_init(1, 2, 3, 4);
+    for (unsigned i = 0; i < 4; i++) {
+        if (target_isptrlist) {
+            int *x = cxMalloc(testing_alloc, sizeof(int));
+            *x = initial_data[i];
+            cxListAdd(target, x);
+        } else {
+            cxListAdd(target, &initial_data[i]);
+        }
+    }
+
+    // perform the test
+    int expected_data[12] = array_init(1, 2, 3, 4, 1, 3, 5, 7, 9, 11, 13, 15);
+    int c = 0;
+    size_t cloned = cxListClone(target, source, test_clone_func, testing_alloc, &c);
+    CX_TEST_ASSERT(cloned == 8);
+    CX_TEST_ASSERT(c == 8);
+    CX_TEST_ASSERT(cxListSize(target) == 12);
+    CX_TEST_ASSERT(cxListSize(source) == 8);
+    for (unsigned i = 0 ; i < 12 ; i++) {
+        CX_TEST_ASSERT(*(int*)cxListAt(target, i) == expected_data[i]);
+    }
+    for (unsigned i = 0 ; i < 8 ; i++) {
+        CX_TEST_ASSERT(*(int*)cxListAt(source, i) == source_data[i]);
+    }
+    cxListFree(target);
+    CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
+    cx_testing_allocator_destroy(&talloc);
+}
+
+roll_out_test_combos(clone_into_arl, {
+    CxList *target = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int), 8);
+    CX_TEST_CALL_SUBROUTINE(verify_clone, target, list, false);
+})
+
+roll_out_test_combos(clone_into_ll, {
+    CxList *target = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, sizeof(int));
+    CX_TEST_CALL_SUBROUTINE(verify_clone, target, list, false);
+})
+
+roll_out_test_combos(clone_into_parl, {
+    CxList *target = cxArrayListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS, 8);
+    CX_TEST_CALL_SUBROUTINE(verify_clone, target, list, true);
+})
+
+roll_out_test_combos(clone_into_pll, {
+    CxList *target = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS);
+    CX_TEST_CALL_SUBROUTINE(verify_clone, target, list, true);
+})
+
 CX_TEST(test_list_pointer_list_supports_null) {
     CxList *list = cxLinkedListCreate(cxDefaultAllocator, cx_cmp_int, CX_STORE_POINTERS);
     int x = 47;
@@ -2698,6 +2778,14 @@
     cx_test_register(suite, test_list_parl_simple_destr);
     cx_test_register(suite, test_list_arl_advanced_destr);
     cx_test_register(suite, test_list_parl_advanced_destr);
+    cx_test_register(suite, test_list_arl_clone_into_arl);
+    cx_test_register(suite, test_list_parl_clone_into_arl);
+    cx_test_register(suite, test_list_arl_clone_into_ll);
+    cx_test_register(suite, test_list_parl_clone_into_ll);
+    cx_test_register(suite, test_list_arl_clone_into_parl);
+    cx_test_register(suite, test_list_parl_clone_into_parl);
+    cx_test_register(suite, test_list_arl_clone_into_pll);
+    cx_test_register(suite, test_list_parl_clone_into_pll);
 
     return suite;
 }
@@ -2817,6 +2905,14 @@
     cx_test_register(suite, test_list_pll_simple_destr);
     cx_test_register(suite, test_list_ll_advanced_destr);
     cx_test_register(suite, test_list_pll_advanced_destr);
+    cx_test_register(suite, test_list_ll_clone_into_arl);
+    cx_test_register(suite, test_list_pll_clone_into_arl);
+    cx_test_register(suite, test_list_ll_clone_into_ll);
+    cx_test_register(suite, test_list_pll_clone_into_ll);
+    cx_test_register(suite, test_list_ll_clone_into_parl);
+    cx_test_register(suite, test_list_pll_clone_into_parl);
+    cx_test_register(suite, test_list_ll_clone_into_pll);
+    cx_test_register(suite, test_list_pll_clone_into_pll);
 
     return suite;
 }
@@ -2909,6 +3005,15 @@
     cx_test_register(suite, test_list_pkvl_simple_destr);
     cx_test_register(suite, test_list_kvl_advanced_destr);
     cx_test_register(suite, test_list_pkvl_advanced_destr);
+    // note: kv-lists also support a list clone, but that does not clone the keys
+    cx_test_register(suite, test_list_kvl_clone_into_arl);
+    cx_test_register(suite, test_list_pkvl_clone_into_arl);
+    cx_test_register(suite, test_list_kvl_clone_into_ll);
+    cx_test_register(suite, test_list_pkvl_clone_into_ll);
+    cx_test_register(suite, test_list_kvl_clone_into_parl);
+    cx_test_register(suite, test_list_pkvl_clone_into_parl);
+    cx_test_register(suite, test_list_kvl_clone_into_pll);
+    cx_test_register(suite, test_list_pkvl_clone_into_pll);
 
     return suite;
 }