Mercurial > hg > ucx / changeset

--- a/src/array_list.c	Mon Jan 23 20:00:26 2023 +0100
+++ b/src/array_list.c	Mon Jan 23 20:22:11 2023 +0100
@@ -185,17 +185,50 @@
     );
 }
 
-static size_t cx_arl_add_array(
+static size_t cx_arl_insert_array(
         struct cx_list_s *list,
+        size_t index,
         void const *array,
         size_t n
 ) {
+    // out of bounds and special case check
+    if (index > list->size || n == 0) return 0;
+
+    // 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->size) {
+        char const *first_to_move = (char const *) arl->data;
+        first_to_move += index * list->itemsize;
+        size_t elems_to_move = list->size - index;
+        size_t start_of_moved = index + n;
+
+        if (CX_ARRAY_COPY_SUCCESS != cx_array_copy(
+                &arl->data,
+                &list->size,
+                &list->capacity,
+                start_of_moved,
+                first_to_move,
+                list->itemsize,
+                elems_to_move,
+                &arl->reallocator
+        )) {
+            // if moving existing elems is unsuccessful, abort
+            return 0;
+        }
+    }
+
+    // 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
+
+    // place the new elements
     if (CX_ARRAY_COPY_SUCCESS == cx_array_copy(
             &arl->data,
             &list->size,
             &list->capacity,
-            list->size,
+            index,
             array,
             list->itemsize,
             n,
@@ -208,6 +241,14 @@
     }
 }
 
+static size_t cx_arl_add_array(
+        struct cx_list_s *list,
+        void const *array,
+        size_t n
+) {
+    return cx_arl_insert_array(list, list->size, array, n);
+}
+
 static int cx_arl_insert(
         struct cx_list_s *list,
         size_t index,
@@ -440,6 +481,7 @@
         cx_arl_add,
         cx_arl_add_array,
         cx_arl_insert,
+        cx_arl_insert_array,
         cx_arl_insert_iter,
         cx_arl_remove,
         cx_arl_at,

--- a/src/cx/list.h	Mon Jan 23 20:00:26 2023 +0100
+++ b/src/cx/list.h	Mon Jan 23 20:22:11 2023 +0100
@@ -148,6 +148,16 @@
     );
 
     /**
+     * Member function for inserting multiple elements.
+     */
+    size_t (*insert_array)(
+            struct cx_list_s *list,
+            size_t index,
+            void const *data,
+            size_t n
+    );
+
+    /**
      * Member function for inserting an element relative to an iterator position.
      */
     int (*insert_iter)(
@@ -281,6 +291,32 @@
 }
 
 /**
+ * Inserts multiple items to the list at the specified index.
+ * If \p index equals the list size, this is effectively cxListAddArray().
+ *
+ * This method is usually more efficient than invoking cxListInsert()
+ * multiple times.
+ *
+ * If there is not enough memory to add all elements, the returned value is
+ * less than \p n.
+ *
+ * @param list the list
+ * @param index the index where to add the elements
+ * @param array a pointer to the elements to add
+ * @param n the number of elements to add
+ * @return the number of added elements
+ */
+__attribute__((__nonnull__))
+static inline size_t cxListInsertArray(
+        CxList *list,
+        size_t index,
+        void const *array,
+        size_t n
+) {
+    return list->cl->insert_array(list, index, array, n);
+}
+
+/**
  * Inserts an element after the current location of the specified iterator.
  *
  * The used iterator remains operational, but all other active iterators should

--- a/src/linked_list.c	Mon Jan 23 20:00:26 2023 +0100
+++ b/src/linked_list.c	Mon Jan 23 20:22:11 2023 +0100
@@ -518,19 +518,47 @@
     return 0;
 }
 
+static size_t cx_ll_insert_array(
+        struct cx_list_s *list,
+        size_t index,
+        void const *array,
+        size_t n
+) {
+    // out-of bounds and corner case check
+    if (index > list->size || n == 0) return 0;
+
+    // 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 (0 != cx_ll_insert_at(list, node, array)) {
+        return 1;
+    }
+
+    // is there more?
+    if (n == 1) return 1;
+
+    // we now know exactly where we are
+    node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
+
+    // we can add the remaining nodes and immedately advance to the inserted node
+    char const *source = array;
+    for (size_t i = 1; i < n; i++) {
+        source += list->itemsize;
+        if (0 != cx_ll_insert_at(list, node, source)) {
+            return i;
+        }
+        node = node->next;
+    }
+    return n;
+}
+
 static int cx_ll_insert(
         struct cx_list_s *list,
         size_t index,
         void const *elem
 ) {
-    // out-of bounds check
-    if (index > list->size) return 1;
-
-    // find position efficiently
-    cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
-
-    // perform insert
-    return cx_ll_insert_at(list, node, elem);
+    return cx_ll_insert_array(list, index, elem, 1) != 1;
 }
 
 static int cx_ll_add(
@@ -545,13 +573,7 @@
         void const *array,
         size_t n
 ) {
-    // TODO: redirect to cx_ll_insert_array
-    cx_for_n (i, n) {
-        if (cx_ll_add(list, ((char const *) array) + i * list->itemsize)) {
-            return i;
-        }
-    }
-    return n;
+    return cx_ll_insert_array(list, list->size, array, n);
 }
 
 static int cx_pll_insert(
@@ -783,6 +805,7 @@
         cx_ll_add,
         cx_ll_add_array,
         cx_ll_insert,
+        cx_ll_insert_array,
         cx_ll_insert_iter,
         cx_ll_remove,
         cx_ll_at,
@@ -799,6 +822,7 @@
         cx_pll_add,
         cx_ll_add_array,
         cx_pll_insert,
+        cx_ll_insert_array,
         cx_pll_insert_iter,
         cx_ll_remove,
         cx_pll_at,

--- a/test/test_list.cpp	Mon Jan 23 20:00:26 2023 +0100
+++ b/test/test_list.cpp	Mon Jan 23 20:22:11 2023 +0100
@@ -633,6 +633,34 @@
         EXPECT_EQ(*(int *) cxListAt(list, 3), 42);
     }
 
+    static void verifyInsertArray(CxList *list) {
+        int a[5] = {5, 47, 11, 13, 42};
+        int b[5] = {9, 18, 72, 50, 7};
+
+        size_t inserted;
+
+        inserted = cxListInsertArray(list, 0, a, 5);
+        EXPECT_EQ(inserted, 5);
+        EXPECT_EQ(*(int *) cxListAt(list, 0), 5);
+        EXPECT_EQ(*(int *) cxListAt(list, 1), 47);
+        EXPECT_EQ(*(int *) cxListAt(list, 2), 11);
+        EXPECT_EQ(*(int *) cxListAt(list, 3), 13);
+        EXPECT_EQ(*(int *) cxListAt(list, 4), 42);
+
+        inserted = cxListInsertArray(list, 3, b, 5);
+        EXPECT_EQ(inserted, 5);
+        EXPECT_EQ(*(int *) cxListAt(list, 0), 5);
+        EXPECT_EQ(*(int *) cxListAt(list, 1), 47);
+        EXPECT_EQ(*(int *) cxListAt(list, 2), 11);
+        EXPECT_EQ(*(int *) cxListAt(list, 3), 9);
+        EXPECT_EQ(*(int *) cxListAt(list, 4), 18);
+        EXPECT_EQ(*(int *) cxListAt(list, 5), 72);
+        EXPECT_EQ(*(int *) cxListAt(list, 6), 50);
+        EXPECT_EQ(*(int *) cxListAt(list, 7), 7);
+        EXPECT_EQ(*(int *) cxListAt(list, 8), 13);
+        EXPECT_EQ(*(int *) cxListAt(list, 9), 42);
+    }
+
     void verifyRemove(CxList *list) const {
         EXPECT_EQ(cxListRemove(list, 2), 0);
         EXPECT_EQ(cxListRemove(list, 4), 0);
@@ -824,6 +852,19 @@
     verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 2)));
 }
 
+TEST_F(LinkedList, cxListInsertArray) {
+    verifyInsertArray(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
+}
+
+TEST_F(PointerLinkedList, cxListInsertArray) {
+    //TODO: this is unfixably broken - solve with issue #234
+    //verifyInsertArray(autofree(cxPointerLinkedListCreate(&testingAllocator, cx_cmp_int)));
+}
+
+TEST_F(ArrayList, cxListInsertArray) {
+    verifyInsertArray(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4)));
+}
+
 TEST_F(LinkedList, cxListRemove) {
     verifyRemove(linkedListFromTestData());
 }