Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/list.h	Sat Jan 29 12:46:07 2022 +0100
     1.2 +++ b/src/cx/list.h	Sat Jan 29 14:32:04 2022 +0100
     1.3 @@ -80,6 +80,15 @@
     1.4      );
     1.5  
     1.6      /**
     1.7 +     * Member function for inserting an element relative to an iterator position.
     1.8 +     */
     1.9 +    int (*insert_iter)(
    1.10 +            CxIterator *iter,
    1.11 +            void const *elem,
    1.12 +            int prepend
    1.13 +    );
    1.14 +
    1.15 +    /**
    1.16       * Member function for removing an element.
    1.17       */
    1.18      int (*remove)(
    1.19 @@ -168,11 +177,6 @@
    1.20  /**
    1.21   * Adds an item to the end of the list.
    1.22   *
    1.23 - * \remark It is implementation defined whether
    1.24 - * the contents of the element are copied or the
    1.25 - * pointer is added to the list. In the latter case
    1.26 - * the \c itemsize of the list SHALL be \c sizeof(void*).
    1.27 - *
    1.28   * @param list the list
    1.29   * @param elem a pointer to the element to add
    1.30   * @return zero on success, non-zero on memory allocation failure
    1.31 @@ -189,16 +193,13 @@
    1.32   *
    1.33   * If \p index equals the list \c size, this is effectively cxListAdd().
    1.34   *
    1.35 - * \remark It is implementation defined whether
    1.36 - * the contents of the element are copied or the
    1.37 - * pointer is added to the list. In the latter case
    1.38 - * the \c itemsize of the list SHALL be \c sizeof(void*).
    1.39 - *
    1.40   * @param list the list
    1.41   * @param index the index the element shall have
    1.42   * @param elem a pointer to the element to add
    1.43   * @return zero on success, non-zero on memory allocation failure
    1.44   * or when the index is out of bounds
    1.45 + * @see cxListInsertAfter()
    1.46 + * @see cxListInsertBefore()
    1.47   */
    1.48  static inline int cxListInsert(
    1.49          CxList list,
    1.50 @@ -209,6 +210,50 @@
    1.51  }
    1.52  
    1.53  /**
    1.54 + * Inserts an element after the current location of the specified iterator.
    1.55 + *
    1.56 + * The used iterator remains operational, but all other active iterators should
    1.57 + * be considered invalidated.
    1.58 + *
    1.59 + * If \p iter is not a list iterator, the behavior is undefined.
    1.60 + * If \p iter is a past-the-end iterator, the new element gets appended to the list.
    1.61 + *
    1.62 + * @param iter an iterator
    1.63 + * @param elem the element to insert
    1.64 + * @return zero on success, non-zero on memory allocation failure
    1.65 + * @see cxListInsert()
    1.66 + * @see cxListInsertBefore()
    1.67 + */
    1.68 +static inline int cxListInsertAfter(
    1.69 +        CxIterator *iter,
    1.70 +        void const *elem
    1.71 +) {
    1.72 +    return ((cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
    1.73 +}
    1.74 +
    1.75 +/**
    1.76 + * Inserts an element before the current location of the specified iterator.
    1.77 + *
    1.78 + * The used iterator remains operational, but all other active iterators should
    1.79 + * be considered invalidated.
    1.80 + *
    1.81 + * If \p iter is not a list iterator, the behavior is undefined.
    1.82 + * If \p iter is a past-the-end iterator, the new element gets appended to the list.
    1.83 + *
    1.84 + * @param iter an iterator
    1.85 + * @param elem the element to insert
    1.86 + * @return zero on success, non-zero on memory allocation failure
    1.87 + * @see cxListInsert()
    1.88 + * @see cxListInsertAfter()
    1.89 + */
    1.90 +static inline int cxListInsertBefore(
    1.91 +        CxIterator *iter,
    1.92 +        void const *elem
    1.93 +) {
    1.94 +    return ((cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
    1.95 +}
    1.96 +
    1.97 +/**
    1.98   * Removes the element at the specified index.
    1.99   * @param list the list
   1.100   * @param index the index of the element

     2.1 --- a/src/linked_list.c	Sat Jan 29 12:46:07 2022 +0100
     2.2 +++ b/src/linked_list.c	Sat Jan 29 14:32:04 2022 +0100
     2.3 @@ -481,16 +481,11 @@
     2.4      }
     2.5  }
     2.6  
     2.7 -static int cx_ll_insert(
     2.8 +static int cx_ll_insert_at(
     2.9          cx_list_s *list,
    2.10 -        size_t index,
    2.11 +        cx_linked_list_node *node,
    2.12          void const *elem
    2.13  ) {
    2.14 -    // out-of bounds check
    2.15 -    if (index > list->size) return 1;
    2.16 -
    2.17 -    // cast a linked list pointer
    2.18 -    cx_linked_list *ll = (cx_linked_list *) list;
    2.19  
    2.20      // create the new new_node
    2.21      cx_linked_list_node *new_node = cxMalloc(list->allocator,
    2.22 @@ -503,10 +498,8 @@
    2.23      new_node->prev = new_node->next = NULL;
    2.24      memcpy(new_node->payload, elem, list->itemsize);
    2.25  
    2.26 -    // find position efficiently
    2.27 -    cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at(ll, index - 1);
    2.28 -
    2.29      // insert
    2.30 +    cx_linked_list *ll = (cx_linked_list *) list;
    2.31      cx_linked_list_insert_chain(
    2.32              (void **) &ll->begin, (void **) &ll->end,
    2.33              CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
    2.34 @@ -518,6 +511,21 @@
    2.35      return 0;
    2.36  }
    2.37  
    2.38 +static int cx_ll_insert(
    2.39 +        cx_list_s *list,
    2.40 +        size_t index,
    2.41 +        void const *elem
    2.42 +) {
    2.43 +    // out-of bounds check
    2.44 +    if (index > list->size) return 1;
    2.45 +
    2.46 +    // find position efficiently
    2.47 +    cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
    2.48 +
    2.49 +    // perform insert
    2.50 +    return cx_ll_insert_at(list, node, elem);
    2.51 +}
    2.52 +
    2.53  static int cx_ll_add(
    2.54          cx_list_s *list,
    2.55          void const *elem
    2.56 @@ -695,21 +703,51 @@
    2.57      return iter;
    2.58  }
    2.59  
    2.60 +static int cx_ll_insert_iter(
    2.61 +        CxIterator *iter,
    2.62 +        void const *elem,
    2.63 +        int prepend
    2.64 +) {
    2.65 +    cx_list_s *list = iter->src_handle;
    2.66 +    cx_linked_list_node *node = iter->elem_handle;
    2.67 +    if (node != NULL) {
    2.68 +        assert(prepend >= 0 && prepend <= 1);
    2.69 +        cx_linked_list_node *choice[2] = {node, node->prev};
    2.70 +        int result = cx_ll_insert_at(list, choice[prepend], elem);
    2.71 +        iter->index += prepend * (0 == result);
    2.72 +        return result;
    2.73 +    } else {
    2.74 +        int result = cx_ll_insert(list, list->size, elem);
    2.75 +        iter->index = list->size;
    2.76 +        return result;
    2.77 +    }
    2.78 +}
    2.79 +
    2.80 +static int cx_pll_insert_iter(
    2.81 +        CxIterator *iter,
    2.82 +        void const *elem,
    2.83 +        int prepend
    2.84 +) {
    2.85 +    return cx_ll_insert_iter(iter, &elem, prepend);
    2.86 +}
    2.87 +
    2.88  static cx_list_class cx_linked_list_class = {
    2.89          cx_ll_add,
    2.90          cx_ll_insert,
    2.91 +        cx_ll_insert_iter,
    2.92          cx_ll_remove,
    2.93          cx_ll_at,
    2.94          cx_ll_find,
    2.95          cx_ll_sort,
    2.96          cx_ll_compare,
    2.97          cx_ll_reverse,
    2.98 -        cx_ll_iterator,
    2.99 +        cx_ll_iterator
   2.100  };
   2.101  
   2.102  static cx_list_class cx_pointer_linked_list_class = {
   2.103          cx_pll_add,
   2.104          cx_pll_insert,
   2.105 +        cx_pll_insert_iter,
   2.106          cx_ll_remove,
   2.107          cx_pll_at,
   2.108          cx_pll_find,

     3.1 --- a/test/test_list.c	Sat Jan 29 12:46:07 2022 +0100
     3.2 +++ b/test/test_list.c	Sat Jan 29 14:32:04 2022 +0100
     3.3 @@ -1001,6 +1001,92 @@
     3.4      test_hl_linked_list_iterator_impl(list);
     3.5  }
     3.6  
     3.7 +void test_hl_linked_list_insert_via_iterator(void) {
     3.8 +    cxTestingAllocatorReset();
     3.9 +    CxList list = cxLinkedListCreate(cxTestingAllocator, cmp_int, sizeof(int));
    3.10 +    for (int i = 0; i < 5; i++) {
    3.11 +        cxListAdd(list, &i);
    3.12 +    }
    3.13 +    CxIterator iter = cxListIterator(list, 2);
    3.14 +    CU_ASSERT_EQUAL(iter.index, 2)
    3.15 +    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
    3.16 +
    3.17 +    int data = 10;
    3.18 +    cxListInsertAfter(&iter, &data);
    3.19 +    CU_ASSERT_EQUAL(iter.index, 2)
    3.20 +    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
    3.21 +    data = 20;
    3.22 +    cxListInsertBefore(&iter, &data);
    3.23 +    CU_ASSERT_EQUAL(iter.index, 3)
    3.24 +    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
    3.25 +
    3.26 +    data = 30;
    3.27 +    iter = cxListBegin(list);
    3.28 +    cxListInsertBefore(&iter, &data);
    3.29 +    CU_ASSERT_EQUAL(iter.index, 1)
    3.30 +    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 0)
    3.31 +    data = 40;
    3.32 +    iter = cxListIterator(list, list->size);
    3.33 +    cxListInsertBefore(&iter, &data);
    3.34 +    CU_ASSERT_EQUAL(iter.index, 9)
    3.35 +    CU_ASSERT_FALSE(cxIteratorValid(&iter))
    3.36 +    data = 50;
    3.37 +    iter = cxListIterator(list, list->size);
    3.38 +    cxListInsertAfter(&iter, &data);
    3.39 +    CU_ASSERT_EQUAL(iter.index, 10)
    3.40 +    CU_ASSERT_FALSE(cxIteratorValid(&iter))
    3.41 +
    3.42 +    int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
    3.43 +    CxList expected = cxLinkedListFromArray(cxTestingAllocator,
    3.44 +                                            cmp_int, sizeof(int), 10, expdata);
    3.45 +
    3.46 +    CU_ASSERT_EQUAL(0, cxListCompare(list, expected))
    3.47 +    cxLinkedListDestroy(list);
    3.48 +    cxLinkedListDestroy(expected);
    3.49 +    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    3.50 +}
    3.51 +
    3.52 +void test_hl_ptr_linked_list_insert_via_iterator(void) {
    3.53 +    int testdata[] = {0, 1, 2, 3, 4, 10, 20, 30, 40, 50};
    3.54 +    cxTestingAllocatorReset();
    3.55 +    CxList list = cxPointerLinkedListCreate(cxTestingAllocator, cmp_int);
    3.56 +    int i;
    3.57 +    for (i = 0; i < 5; i++) {
    3.58 +        cxListAdd(list, &testdata[i]);
    3.59 +    }
    3.60 +    CxIterator iter = cxListIterator(list, 2);
    3.61 +    CU_ASSERT_EQUAL(iter.index, 2)
    3.62 +    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
    3.63 +
    3.64 +    cxListInsertAfter(&iter, &testdata[i++]);
    3.65 +    CU_ASSERT_EQUAL(iter.index, 2)
    3.66 +    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
    3.67 +    cxListInsertBefore(&iter, &testdata[i++]);
    3.68 +    CU_ASSERT_EQUAL(iter.index, 3)
    3.69 +    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 2)
    3.70 +
    3.71 +    iter = cxListBegin(list);
    3.72 +    cxListInsertBefore(&iter, &testdata[i++]);
    3.73 +    CU_ASSERT_EQUAL(iter.index, 1)
    3.74 +    CU_ASSERT_EQUAL(*(int *) cxIteratorCurrent(&iter), 0)
    3.75 +    iter = cxListIterator(list, list->size);
    3.76 +    cxListInsertBefore(&iter, &testdata[i++]);
    3.77 +    CU_ASSERT_EQUAL(iter.index, 9)
    3.78 +    CU_ASSERT_FALSE(cxIteratorValid(&iter))
    3.79 +    iter = cxListIterator(list, list->size);
    3.80 +    cxListInsertAfter(&iter, &testdata[i++]);
    3.81 +    CU_ASSERT_EQUAL(iter.index, 10)
    3.82 +    CU_ASSERT_FALSE(cxIteratorValid(&iter))
    3.83 +
    3.84 +    int expdata[] = {30, 0, 1, 20, 2, 10, 3, 4, 40, 50};
    3.85 +    for (i = 0; i < 10; i++) {
    3.86 +        CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expdata[i])
    3.87 +    }
    3.88 +
    3.89 +    cxLinkedListDestroy(list);
    3.90 +    CU_ASSERT_TRUE(cxTestingAllocatorVerify())
    3.91 +}
    3.92 +
    3.93  int main() {
    3.94      CU_pSuite suite = NULL;
    3.95  
    3.96 @@ -1037,6 +1123,7 @@
    3.97      cu_add_test(suite, test_hl_linked_list_find);
    3.98      cu_add_test(suite, test_hl_linked_list_sort);
    3.99      cu_add_test(suite, test_hl_linked_list_iterator);
   3.100 +    cu_add_test(suite, test_hl_linked_list_insert_via_iterator);
   3.101  
   3.102      suite = CU_add_suite("high level pointer linked list", NULL, NULL);
   3.103  
   3.104 @@ -1048,6 +1135,7 @@
   3.105      cu_add_test(suite, test_hl_ptr_linked_list_find);
   3.106      cu_add_test(suite, test_hl_ptr_linked_list_sort);
   3.107      cu_add_test(suite, test_hl_ptr_linked_list_iterator);
   3.108 +    cu_add_test(suite, test_hl_ptr_linked_list_insert_via_iterator);
   3.109  
   3.110      CU_basic_set_mode(UCX_CU_BRM);
   3.111