Mercurial > hg > ucx / changeset

--- a/src/cx/list.h	Sat Jan 29 12:46:07 2022 +0100
+++ b/src/cx/list.h	Sat Jan 29 14:32:04 2022 +0100
@@ -80,6 +80,15 @@
     );
 
     /**
+     * Member function for inserting an element relative to an iterator position.
+     */
+    int (*insert_iter)(
+            CxIterator *iter,
+            void const *elem,
+            int prepend
+    );
+
+    /**
      * Member function for removing an element.
      */
     int (*remove)(
@@ -168,11 +177,6 @@
 /**
  * Adds an item to the end of the list.
  *
- * \remark It is implementation defined whether
- * the contents of the element are copied or the
- * pointer is added to the list. In the latter case
- * the \c itemsize of the list SHALL be \c sizeof(void*).
- *
  * @param list the list
  * @param elem a pointer to the element to add
  * @return zero on success, non-zero on memory allocation failure
@@ -189,16 +193,13 @@
  *
  * If \p index equals the list \c size, this is effectively cxListAdd().
  *
- * \remark It is implementation defined whether
- * the contents of the element are copied or the
- * pointer is added to the list. In the latter case
- * the \c itemsize of the list SHALL be \c sizeof(void*).
- *
  * @param list the list
  * @param index the index the element shall have
  * @param elem a pointer to the element to add
  * @return zero on success, non-zero on memory allocation failure
  * or when the index is out of bounds
+ * @see cxListInsertAfter()
+ * @see cxListInsertBefore()
  */
 static inline int cxListInsert(
         CxList list,
@@ -209,6 +210,50 @@
 }
 
 /**
+ * Inserts an element after the current location of the specified iterator.
+ *
+ * The used iterator remains operational, but all other active iterators should
+ * be considered invalidated.
+ *
+ * If \p iter is not a list iterator, the behavior is undefined.
+ * If \p iter is a past-the-end iterator, the new element gets appended to the list.
+ *
+ * @param iter an iterator
+ * @param elem the element to insert
+ * @return zero on success, non-zero on memory allocation failure
+ * @see cxListInsert()
+ * @see cxListInsertBefore()
+ */
+static inline int cxListInsertAfter(
+        CxIterator *iter,
+        void const *elem
+) {
+    return ((cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
+}
+
+/**
+ * Inserts an element before the current location of the specified iterator.
+ *
+ * The used iterator remains operational, but all other active iterators should
+ * be considered invalidated.
+ *
+ * If \p iter is not a list iterator, the behavior is undefined.
+ * If \p iter is a past-the-end iterator, the new element gets appended to the list.
+ *
+ * @param iter an iterator
+ * @param elem the element to insert
+ * @return zero on success, non-zero on memory allocation failure
+ * @see cxListInsert()
+ * @see cxListInsertAfter()
+ */
+static inline int cxListInsertBefore(
+        CxIterator *iter,
+        void const *elem
+) {
+    return ((cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
+}
+
+/**
  * Removes the element at the specified index.
  * @param list the list
  * @param index the index of the element

--- a/src/linked_list.c	Sat Jan 29 12:46:07 2022 +0100
+++ b/src/linked_list.c	Sat Jan 29 14:32:04 2022 +0100
@@ -481,16 +481,11 @@
     }
 }
 
-static int cx_ll_insert(
+static int cx_ll_insert_at(
         cx_list_s *list,
-        size_t index,
+        cx_linked_list_node *node,
         void const *elem
 ) {
-    // out-of bounds check
-    if (index > list->size) return 1;
-
-    // cast a linked list pointer
-    cx_linked_list *ll = (cx_linked_list *) list;
 
     // create the new new_node
     cx_linked_list_node *new_node = cxMalloc(list->allocator,
@@ -503,10 +498,8 @@
     new_node->prev = new_node->next = NULL;
     memcpy(new_node->payload, elem, list->itemsize);
 
-    // find position efficiently
-    cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at(ll, index - 1);
-
     // insert
+    cx_linked_list *ll = (cx_linked_list *) list;
     cx_linked_list_insert_chain(
             (void **) &ll->begin, (void **) &ll->end,
             CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
@@ -518,6 +511,21 @@
     return 0;
 }
 
+static int cx_ll_insert(
+        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);
+}
+
 static int cx_ll_add(
         cx_list_s *list,
         void const *elem
@@ -695,21 +703,51 @@
     return iter;
 }
 
+static int cx_ll_insert_iter(
+        CxIterator *iter,
+        void const *elem,
+        int prepend
+) {
+    cx_list_s *list = iter->src_handle;
+    cx_linked_list_node *node = iter->elem_handle;
+    if (node != NULL) {
+        assert(prepend >= 0 && prepend <= 1);
+        cx_linked_list_node *choice[2] = {node, node->prev};
+        int result = cx_ll_insert_at(list, choice[prepend], elem);
+        iter->index += prepend * (0 == result);
+        return result;
+    } else {
+        int result = cx_ll_insert(list, list->size, elem);
+        iter->index = list->size;
+        return result;
+    }
+}
+
+static int cx_pll_insert_iter(
+        CxIterator *iter,
+        void const *elem,
+        int prepend
+) {
+    return cx_ll_insert_iter(iter, &elem, prepend);
+}
+
 static cx_list_class cx_linked_list_class = {
         cx_ll_add,
         cx_ll_insert,
+        cx_ll_insert_iter,
         cx_ll_remove,
         cx_ll_at,
         cx_ll_find,
         cx_ll_sort,
         cx_ll_compare,
         cx_ll_reverse,
-        cx_ll_iterator,
+        cx_ll_iterator
 };
 
 static cx_list_class cx_pointer_linked_list_class = {
         cx_pll_add,
         cx_pll_insert,
+        cx_pll_insert_iter,
         cx_ll_remove,
         cx_pll_at,
         cx_pll_find,

--- a/test/test_list.c	Sat Jan 29 12:46:07 2022 +0100
+++ b/test/test_list.c	Sat Jan 29 14:32:04 2022 +0100
@@ -1001,6 +1001,92 @@
     test_hl_linked_list_iterator_impl(list);
 }
 
+void test_hl_linked_list_insert_via_iterator(void) {
+    cxTestingAllocatorReset();
+    CxList list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
+    for (int i = 0; i < 5; i++) {
+        cxListAdd(list, &i);
+    }
+    CxIterator iter = cxListIterator(list, 2);
+    CU_ASSERT_EQUAL(iter.index, 2)
+    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
+
+    int data = 10;
+    cxListInsertAfter(&iter, &data);
+    CU_ASSERT_EQUAL(iter.index, 2)
+    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
+    data = 20;
+    cxListInsertBefore(&iter, &data);
+    CU_ASSERT_EQUAL(iter.index, 3)
+    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
+
+    data = 30;
+    iter = cxListBegin(list);
+    cxListInsertBefore(&iter, &data);
+    CU_ASSERT_EQUAL(iter.index, 1)
+    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 0)
+    data = 40;
+    iter = cxListIterator(list, list->size);
+    cxListInsertBefore(&iter, &data);
+    CU_ASSERT_EQUAL(iter.index, 9)
+    CU_ASSERT_FALSE(cxIteratorValid(&iter))
+    data = 50;
+    iter = cxListIterator(list, list->size);
+    cxListInsertAfter(&iter, &data);
+    CU_ASSERT_EQUAL(iter.index, 10)
+    CU_ASSERT_FALSE(cxIteratorValid(&iter))
+
+    int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
+    CxList expected = cxLinkedListFromArray(cxTestingAllocator,
+                                            cmp_int, sizeof(int), 10, expdata);
+
+    CU_ASSERT_EQUAL(0, cxListCompare(list, expected))
+    cxLinkedListDestroy(list);
+    cxLinkedListDestroy(expected);
+    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
+}
+
+void test_hl_ptr_linked_list_insert_via_iterator(void) {
+    int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50};
+    cxTestingAllocatorReset();
+    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
+    int i;
+    for (i = 0; i < 5; i++) {
+        cxListAdd(list, &testdata[i]);
+    }
+    CxIterator iter = cxListIterator(list, 2);
+    CU_ASSERT_EQUAL(iter.index, 2)
+    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
+
+    cxListInsertAfter(&iter, &testdata[i++]);
+    CU_ASSERT_EQUAL(iter.index, 2)
+    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
+    cxListInsertBefore(&iter, &testdata[i++]);
+    CU_ASSERT_EQUAL(iter.index, 3)
+    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
+
+    iter = cxListBegin(list);
+    cxListInsertBefore(&iter, &testdata[i++]);
+    CU_ASSERT_EQUAL(iter.index, 1)
+    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 0)
+    iter = cxListIterator(list, list->size);
+    cxListInsertBefore(&iter, &testdata[i++]);
+    CU_ASSERT_EQUAL(iter.index, 9)
+    CU_ASSERT_FALSE(cxIteratorValid(&iter))
+    iter = cxListIterator(list, list->size);
+    cxListInsertAfter(&iter, &testdata[i++]);
+    CU_ASSERT_EQUAL(iter.index, 10)
+    CU_ASSERT_FALSE(cxIteratorValid(&iter))
+
+    int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
+    for (i = 0; i < 10; i++) {
+        CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expdata[i])
+    }
+
+    cxLinkedListDestroy(list);
+    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
+}
+
 int main() {
     CU_pSuite suite = NULL;
 
@@ -1037,6 +1123,7 @@
     cu_add_test(suite, test_hl_linked_list_find);
     cu_add_test(suite, test_hl_linked_list_sort);
     cu_add_test(suite, test_hl_linked_list_iterator);
+    cu_add_test(suite, test_hl_linked_list_insert_via_iterator);
 
     suite = CU_add_suite("high level pointer linked list", NULL, NULL);
 
@@ -1048,6 +1135,7 @@
     cu_add_test(suite, test_hl_ptr_linked_list_find);
     cu_add_test(suite, test_hl_ptr_linked_list_sort);
     cu_add_test(suite, test_hl_ptr_linked_list_iterator);
+    cu_add_test(suite, test_hl_ptr_linked_list_insert_via_iterator);
 
     CU_basic_set_mode(UCX_CU_BRM);