Mercurial > hg > ucx / changeset

--- a/CHANGELOG	Sun May 04 12:15:03 2025 +0200
+++ b/CHANGELOG	Sun May 04 17:22:30 2025 +0200
@@ -7,14 +7,17 @@
  * adds cxListFirst() and cxListLast()
  * adds cxListRemoveAndGetFirst() and cxListRemoveAndGetLast(),
    and corresponding macro aliases cxListPopFront() and cxListPop()
+ * adds cxListEmplace() and cxListEmplaceAt()
  * adds cxBufferShrink()
  * adds cxTreeSize()
  * adds CX_PRIstr and CX_SFMT macros for formatting UCX strings
  * adds cx_strcpy() and cx_strcpy_a()
+ * improves performance of the CxList array list implementation
  * changes grow strategy for the mempory pool to reduce reallocations
  * changes grow strategy for CxBuffer, which does now take the page size into account
  * changes the implementation of cx_strreplacen() for improved efficiency
  * changes all cxListIterator() without index to also accept NULL as list argument
+ * changes insert_element member function of CxList to accept NULL source and return a pointer to the inserted element
  * fixes that starting an iteration in a non-root node incorrectly continues iteration with the siblings of that node
  * fixes unnecessary allocations in cx_strcat() family of functions
  * fixes errno value after failing cxBufferSeek() to be consistently EINVAL

--- a/docs/Writerside/topics/about.md	Sun May 04 12:15:03 2025 +0200
+++ b/docs/Writerside/topics/about.md	Sun May 04 17:22:30 2025 +0200
@@ -34,14 +34,17 @@
 * adds cxListFirst() and cxListLast()
 * adds cxListRemoveAndGetFirst() and cxListRemoveAndGetLast(),
   and corresponding macro aliases cxListPopFront() and cxListPop()
+* adds cxListEmplace() and cxListEmplaceAt()
 * adds cxBufferShrink()
 * adds cxTreeSize()
 * adds CX_PRIstr and CX_SFMT macros for formatting UCX strings
 * adds cx_strcpy() and cx_strcpy_a()
+* improves performance of the CxList array list implementation
 * changes grow strategy for the memory pool to reduce reallocations
 * changes grow strategy for CxBuffer, which does now take the page size into account
 * changes the implementation of cx_strreplacen() for improved efficiency
 * changes all cxListIterator() without index to also accept NULL as list argument
+* changes insert_element member function of CxList to accept NULL source and return a pointer to the inserted element
 * fixes that starting an iteration in a non-root node incorrectly continues iteration with the siblings of that node
 * fixes unnecessary allocations in cx_strcat() family of functions
 * fixes errno value after failing cxBufferSeek() to be consistently EINVAL

--- a/docs/Writerside/topics/list.h.md	Sun May 04 12:15:03 2025 +0200
+++ b/docs/Writerside/topics/list.h.md	Sun May 04 17:22:30 2025 +0200
@@ -116,6 +116,10 @@
 
 int cxListInsert(CxList *list, size_t index, const void *elem);
 
+void *cxListEmplace(CxList *list);
+
+void *cxListEmplaceAt(CxList *list, size_t index);
+
 int cxListInsertSorted(CxList *list, const void *elem);
 
 size_t cxListAddArray(CxList *list, const void *array, size_t n);
@@ -132,8 +136,13 @@
 ```
 
 The function `cxListAdd()` appends the element `elem` to the list and returns zero on success or non-zero when allocating the memory for the element fails.
-Similarly, `cxListInsert()` adds the element at the specified `index`,
-and `cxListInsertSorted()` adds the element at the correct position so that the list remains sorted according to the list's compare function.
+Similarly, `cxListInsert()` adds the element at the specified `index`.
+
+The functions `cxListEmplace()` and `cxListEmplaceAt()` behave like `cxListAdd()` and `cxListInsert()`,
+except that they only allocate the memory and return a pointer to it, leaving it to the callee to copy the element data into it.
+Be aware that when the list is storing pointers, the allocated memory will be for the pointer, not the actual element's data.
+
+The function `cxListInsertSorted()` inserts the element at the correct position so that the list remains sorted according to the list's compare function.
 
 When you are currently iterating through a list, you can insert elements before or after the current position of the iterator
 with `cxListInsertBefore()` or `cxListInsertAfter()`, respectively.
@@ -405,7 +414,7 @@
 |------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
 | `clear`          | Invoke destructor functions on all elements and remove them from the list.                                                                                                                                                                                                                                                 |
 | `deallocate`     | Invoke destructor functions on all elements and deallocate the entire list memory.                                                                                                                                                                                                                                         |
-| `insert_element` | Insert a single element at the specified index. Return zero on success and non-zero on failure.                                                                                                                                                                                                                            |
+| `insert_element` | Insert a single element at the specified index. Return a pointer to the data of the inserted element or `NULL` on failure.                                                                                                                                                                                                 |
 | `insert_array`   | Insert an array of elements starting at the specified index. Return the number of elements inserted.                                                                                                                                                                                                                       |
 | `insert_sorted`  | Insert an array of sorted elements into a sorted list. Return the number of elements inserted.                                                                                                                                                                                                                             |
 | `insert_iter`    | Insert a single element depending on the iterator position. The third argument to this function is zero when the element shall be inserted after the iterator position and non-zero if it shall be inserted before the iterator position. The implementation is also responsible for adjusting the iterator, respectively. |

--- a/src/array_list.c	Sun May 04 12:15:03 2025 +0200
+++ b/src/array_list.c	Sun May 04 17:22:30 2025 +0200
@@ -638,50 +638,38 @@
     // get a correctly typed pointer to the list
     cx_array_list *arl = (cx_array_list *) list;
 
-    // do we need to move some elements?
-    if (index < list->collection.size) {
-        const char *first_to_move = (const char *) arl->data;
-        first_to_move += index * list->collection.elem_size;
-        size_t elems_to_move = list->collection.size - index;
-        size_t start_of_moved = index + n;
-
-        if (cx_array_copy(
-                &arl->data,
-                &list->collection.size,
-                &arl->capacity,
-                0,
-                start_of_moved,
-                first_to_move,
-                list->collection.elem_size,
-                elems_to_move,
-                &arl->reallocator
-        )) {
-            // if moving existing elems is unsuccessful, abort
+    // guarantee enough capacity
+    if (arl->capacity < list->collection.size + n) {
+        size_t new_capacity = list->collection.size + n;
+        new_capacity = new_capacity - (new_capacity % 16) + 16;
+        if (cxReallocateArray(
+                list->collection.allocator,
+                &arl->data, new_capacity,
+                list->collection.elem_size)
+        ) {
             return 0;
         }
+        arl->capacity = new_capacity;
     }
 
-    // note that if we had to move the elements, the following operation
-    // is guaranteed to succeed, because we have the memory already allocated
-    // therefore, it is impossible to leave this function with an invalid array
+    // determine insert position
+    char *arl_data = arl->data;
+    char *insert_pos = arl_data + index * list->collection.elem_size;
 
-    // place the new elements
-    if (cx_array_copy(
-            &arl->data,
-            &list->collection.size,
-            &arl->capacity,
-            0,
-            index,
-            array,
-            list->collection.elem_size,
-            n,
-            &arl->reallocator
-    )) {
-        // array list implementation is "all or nothing"
-        return 0;
-    } else {
-        return n;
+    // do we need to move some elements?
+    if (index < list->collection.size) {
+        size_t elems_to_move = list->collection.size - index;
+        char *target = insert_pos + n * list->collection.elem_size;
+        memmove(target, insert_pos, elems_to_move * list->collection.elem_size);
     }
+
+    // place the new elements, if any
+    if (array != NULL) {
+        memcpy(insert_pos, array, n * list->collection.elem_size);
+    }
+    list->collection.size += n;
+
+    return n;
 }
 
 static size_t cx_arl_insert_sorted(
@@ -709,12 +697,16 @@
     }
 }
 
-static int cx_arl_insert_element(
+static void *cx_arl_insert_element(
         struct cx_list_s *list,
         size_t index,
         const void *element
 ) {
-    return 1 != cx_arl_insert_array(list, index, element, 1);
+    if (cx_arl_insert_array(list, index, element, 1) == 1) {
+        return ((char*)((cx_array_list *) list)->data) + index * list->collection.elem_size;
+    } else {
+        return NULL;
+    }
 }
 
 static int cx_arl_insert_iter(
@@ -724,26 +716,23 @@
 ) {
     struct cx_list_s *list = iter->src_handle.m;
     if (iter->index < list->collection.size) {
-        int result = cx_arl_insert_element(
-                list,
-                iter->index + 1 - prepend,
-                elem
-        );
-        if (result == 0) {
-            iter->elem_count++;
-            if (prepend != 0) {
-                iter->index++;
-                iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size;
-            }
+        if (cx_arl_insert_element(list,
+                iter->index + 1 - prepend, elem) == NULL) {
+            return 1;
+        }
+        iter->elem_count++;
+        if (prepend != 0) {
+            iter->index++;
+            iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size;
         }
-        return result;
+        return 0;
     } else {
-        int result = cx_arl_insert_element(list, list->collection.size, elem);
-        if (result == 0) {
-            iter->elem_count++;
-            iter->index = list->collection.size;
+        if (cx_arl_insert_element(list, list->collection.size, elem) == NULL) {
+            return 1;
         }
-        return result;
+        iter->elem_count++;
+        iter->index = list->collection.size;
+        return 0;
     }
 }
 

--- a/src/cx/list.h	Sun May 04 12:15:03 2025 +0200
+++ b/src/cx/list.h	Sun May 04 17:22:30 2025 +0200
@@ -80,8 +80,10 @@
 
     /**
      * Member function for inserting a single element.
+     * The data pointer may be @c NULL in which case the function shall only allocate memory.
+     * Returns a pointer to the data of the inserted element.
      */
-    int (*insert_element)(
+    void *(*insert_element)(
             struct cx_list_s *list,
             size_t index,
             const void *data
@@ -370,6 +372,7 @@
  * @retval zero success
  * @retval non-zero memory allocation failure
  * @see cxListAddArray()
+ * @see cxListEmplace()
  */
 cx_attr_nonnull
 static inline int cxListAdd(
@@ -377,7 +380,7 @@
         const void *elem
 ) {
     list->collection.sorted = false;
-    return list->cl->insert_element(list, list->collection.size, elem);
+    return list->cl->insert_element(list, list->collection.size, elem) == NULL;
 }
 
 /**
@@ -418,6 +421,7 @@
  * @retval non-zero memory allocation failure or the index is out of bounds
  * @see cxListInsertAfter()
  * @see cxListInsertBefore()
+ * @see cxListEmplaceAt()
  */
 cx_attr_nonnull
 static inline int cxListInsert(
@@ -426,7 +430,41 @@
         const void *elem
 ) {
     list->collection.sorted = false;
-    return list->cl->insert_element(list, index, elem);
+    return list->cl->insert_element(list, index, elem) == NULL;
+}
+
+/**
+ * Allocates memory for an element at the specified index and returns a pointer to that memory.
+ *
+ * @remark When the list is storing pointers, this will return a @c void**.
+ *
+ * @param list the list
+ * @param index the index where to emplace the element
+ * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds
+ * @see cxListEmplace()
+ * @see cxListInsert()
+ */
+cx_attr_nonnull
+static inline void *cxListEmplaceAt(CxList *list, size_t index) {
+    list->collection.sorted = false;
+    return list->cl->insert_element(list, index, NULL);
+}
+
+
+/**
+ * Allocates memory for an element at the end of the list and returns a pointer to that memory.
+ *
+ * @remark When the list is storing pointers, this will return a @c void**.
+ *
+ * @param list the list
+ * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds
+ * @see cxListEmplaceAt()
+ * @see cxListAdd()
+ */
+cx_attr_nonnull
+static inline void *cxListEmplace(CxList *list) {
+    list->collection.sorted = false;
+    return list->cl->insert_element(list, list->collection.size, NULL);
 }
 
 /**

--- a/src/linked_list.c	Sun May 04 12:15:03 2025 +0200
+++ b/src/linked_list.c	Sun May 04 17:22:30 2025 +0200
@@ -613,7 +613,9 @@
 
     // initialize new new_node
     new_node->prev = new_node->next = NULL;
-    memcpy(new_node->payload, elem, list->collection.elem_size);
+    if (elem != NULL) {
+        memcpy(new_node->payload, elem, list->collection.elem_size);
+    }
 
     // insert
     cx_linked_list *ll = (cx_linked_list *) list;
@@ -659,12 +661,26 @@
     return n;
 }
 
-static int cx_ll_insert_element(
+static void *cx_ll_insert_element(
         struct cx_list_s *list,
         size_t index,
         const void *element
 ) {
-    return 1 != cx_ll_insert_array(list, index, element, 1);
+    // out-of-bounds check
+    if (index > list->collection.size) return NULL;
+
+    // find position efficiently
+    cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
+
+    // perform first insert
+    if (cx_ll_insert_at(list, node, element)) return NULL;
+
+    // return a pointer to the data of the inserted node
+    if (node == NULL) {
+        return ((cx_linked_list *) list)->begin->payload;
+    } else {
+        return node->next->payload;
+    }
 }
 
 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func;
@@ -1056,12 +1072,12 @@
         }
         return result;
     } else {
-        int result = cx_ll_insert_element(list, list->collection.size, elem);
-        if (result == 0) {
-            iter->elem_count++;
-            iter->index = list->collection.size;
+        if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) {
+            return 1;
         }
-        return result;
+        iter->elem_count++;
+        iter->index = list->collection.size;
+        return 0;
     }
 }
 

--- a/src/list.c	Sun May 04 12:15:03 2025 +0200
+++ b/src/list.c	Sun May 04 17:22:30 2025 +0200
@@ -62,7 +62,7 @@
     list->climpl->deallocate(list);
 }
 
-static int cx_pl_insert_element(
+static void *cx_pl_insert_element(
         struct cx_list_s *list,
         size_t index,
         const void *element
@@ -282,7 +282,7 @@
     const char *src = data;
     size_t i = 0;
     for (; i < n; i++) {
-        if (0 != invoke_list_func(
+        if (NULL == invoke_list_func(
             insert_element, list, index + i,
             src + (i * elem_size))) return i;
     }
@@ -329,7 +329,7 @@
 
         // insert the elements at location si
         if (ins == 1) {
-            if (0 != invoke_list_func(
+            if (NULL == invoke_list_func(
                 insert_element, list, di, src)) return inserted;
         } else {
             size_t r = invoke_list_func(insert_array, list, di, src, ins);

--- a/tests/test_list.c	Sun May 04 12:15:03 2025 +0200
+++ b/tests/test_list.c	Sun May 04 17:22:30 2025 +0200
@@ -1370,6 +1370,63 @@
     CX_TEST_ASSERT(*(int *) cxListAt(list, 3) == 42);
 })
 
+roll_out_test_combos(emplace, {
+    if (isptrlist) {
+        int **x;
+        int y = 5;
+        int z = 7;
+        int w = 13;
+
+        x = cxListEmplace(list);
+        CX_TEST_ASSERT(x != NULL);
+        CX_TEST_ASSERT(cxListSize(list) == 1);
+        *x = &y;
+        CX_TEST_ASSERT(*(int*)cxListAt(list, 0) == 5);
+
+        x = cxListEmplace(list);
+        CX_TEST_ASSERT(x != NULL);
+        CX_TEST_ASSERT(cxListSize(list) == 2);
+        *x = &z;
+        CX_TEST_ASSERT(*(int*)cxListAt(list, 1) == 7);
+
+        CX_TEST_ASSERT(NULL == cxListEmplaceAt(list, 3));
+        CX_TEST_ASSERT(cxListSize(list) == 2);
+
+        x = cxListEmplaceAt(list, 1);
+        CX_TEST_ASSERT(x != NULL);
+        CX_TEST_ASSERT(cxListSize(list) == 3);
+        *x = &w;
+        CX_TEST_ASSERT(*(int*)cxListAt(list, 0) == 5);
+        CX_TEST_ASSERT(*(int*)cxListAt(list, 1) == 13);
+        CX_TEST_ASSERT(*(int*)cxListAt(list, 2) == 7);
+    } else {
+        int *x;
+
+        x = cxListEmplace(list);
+        CX_TEST_ASSERT(x != NULL);
+        CX_TEST_ASSERT(cxListSize(list) == 1);
+        *x = 5;
+        CX_TEST_ASSERT(*(int*)cxListAt(list, 0) == 5);
+
+        x = cxListEmplace(list);
+        CX_TEST_ASSERT(x != NULL);
+        CX_TEST_ASSERT(cxListSize(list) == 2);
+        *x = 7;
+        CX_TEST_ASSERT(*(int*)cxListAt(list, 1) == 7);
+
+        CX_TEST_ASSERT(NULL == cxListEmplaceAt(list, 3));
+        CX_TEST_ASSERT(cxListSize(list) == 2);
+
+        x = cxListEmplaceAt(list, 1);
+        CX_TEST_ASSERT(x != NULL);
+        CX_TEST_ASSERT(cxListSize(list) == 3);
+        *x = 13;
+        CX_TEST_ASSERT(*(int*)cxListAt(list, 0) == 5);
+        CX_TEST_ASSERT(*(int*)cxListAt(list, 1) == 13);
+        CX_TEST_ASSERT(*(int*)cxListAt(list, 2) == 7);
+    }
+})
+
 roll_out_test_combos_with_defaulted_funcs(insert_array, {
     int a[5] = array_init(5, 47, 11, 13, 42);
     int b[5] = array_init(9, 18, 72, 50, 7);
@@ -1988,7 +2045,7 @@
 static CX_TEST_SUBROUTINE(test_list_verify_destructor, CxList *list,
                           const int *testdata, size_t testdata_len) {
     destr_test_ctr = 0;
-    
+
     int off = list->collection.store_pointer ? 1 : 0;
 
     cxListRemove(list, 15);
@@ -2064,6 +2121,8 @@
     cx_test_register(suite, test_list_parl_add);
     cx_test_register(suite, test_list_arl_insert);
     cx_test_register(suite, test_list_parl_insert);
+    cx_test_register(suite, test_list_arl_emplace);
+    cx_test_register(suite, test_list_parl_emplace);
     cx_test_register(suite, test_list_arl_insert_array);
     cx_test_register(suite, test_list_parl_insert_array);
     cx_test_register(suite, test_list_arl_insert_sorted);
@@ -2169,6 +2228,8 @@
     cx_test_register(suite, test_list_pll_add);
     cx_test_register(suite, test_list_ll_insert);
     cx_test_register(suite, test_list_pll_insert);
+    cx_test_register(suite, test_list_ll_emplace);
+    cx_test_register(suite, test_list_pll_emplace);
     cx_test_register(suite, test_list_ll_insert_array);
     cx_test_register(suite, test_list_pll_insert_array);
     cx_test_register(suite, test_list_ll_insert_sorted);