Mercurial > hg > ucx / changeset

     1.1 --- a/src/array_list.c	Mon Jan 23 20:00:26 2023 +0100
     1.2 +++ b/src/array_list.c	Mon Jan 23 20:22:11 2023 +0100
     1.3 @@ -185,17 +185,50 @@
     1.4      );
     1.5  }
     1.6  
     1.7 -static size_t cx_arl_add_array(
     1.8 +static size_t cx_arl_insert_array(
     1.9          struct cx_list_s *list,
    1.10 +        size_t index,
    1.11          void const *array,
    1.12          size_t n
    1.13  ) {
    1.14 +    // out of bounds and special case check
    1.15 +    if (index > list->size || n == 0) return 0;
    1.16 +
    1.17 +    // get a correctly typed pointer to the list
    1.18      cx_array_list *arl = (cx_array_list *) list;
    1.19 +
    1.20 +    // do we need to move some elements?
    1.21 +    if (index < list->size) {
    1.22 +        char const *first_to_move = (char const *) arl->data;
    1.23 +        first_to_move += index * list->itemsize;
    1.24 +        size_t elems_to_move = list->size - index;
    1.25 +        size_t start_of_moved = index + n;
    1.26 +
    1.27 +        if (CX_ARRAY_COPY_SUCCESS != cx_array_copy(
    1.28 +                &arl->data,
    1.29 +                &list->size,
    1.30 +                &list->capacity,
    1.31 +                start_of_moved,
    1.32 +                first_to_move,
    1.33 +                list->itemsize,
    1.34 +                elems_to_move,
    1.35 +                &arl->reallocator
    1.36 +        )) {
    1.37 +            // if moving existing elems is unsuccessful, abort
    1.38 +            return 0;
    1.39 +        }
    1.40 +    }
    1.41 +
    1.42 +    // note that if we had to move the elements, the following operation
    1.43 +    // is guaranteed to succeed, because we have the memory already allocated
    1.44 +    // therefore, it is impossible to leave this function with an invalid array
    1.45 +
    1.46 +    // place the new elements
    1.47      if (CX_ARRAY_COPY_SUCCESS == cx_array_copy(
    1.48              &arl->data,
    1.49              &list->size,
    1.50              &list->capacity,
    1.51 -            list->size,
    1.52 +            index,
    1.53              array,
    1.54              list->itemsize,
    1.55              n,
    1.56 @@ -208,6 +241,14 @@
    1.57      }
    1.58  }
    1.59  
    1.60 +static size_t cx_arl_add_array(
    1.61 +        struct cx_list_s *list,
    1.62 +        void const *array,
    1.63 +        size_t n
    1.64 +) {
    1.65 +    return cx_arl_insert_array(list, list->size, array, n);
    1.66 +}
    1.67 +
    1.68  static int cx_arl_insert(
    1.69          struct cx_list_s *list,
    1.70          size_t index,
    1.71 @@ -440,6 +481,7 @@
    1.72          cx_arl_add,
    1.73          cx_arl_add_array,
    1.74          cx_arl_insert,
    1.75 +        cx_arl_insert_array,
    1.76          cx_arl_insert_iter,
    1.77          cx_arl_remove,
    1.78          cx_arl_at,

     2.1 --- a/src/cx/list.h	Mon Jan 23 20:00:26 2023 +0100
     2.2 +++ b/src/cx/list.h	Mon Jan 23 20:22:11 2023 +0100
     2.3 @@ -148,6 +148,16 @@
     2.4      );
     2.5  
     2.6      /**
     2.7 +     * Member function for inserting multiple elements.
     2.8 +     */
     2.9 +    size_t (*insert_array)(
    2.10 +            struct cx_list_s *list,
    2.11 +            size_t index,
    2.12 +            void const *data,
    2.13 +            size_t n
    2.14 +    );
    2.15 +
    2.16 +    /**
    2.17       * Member function for inserting an element relative to an iterator position.
    2.18       */
    2.19      int (*insert_iter)(
    2.20 @@ -281,6 +291,32 @@
    2.21  }
    2.22  
    2.23  /**
    2.24 + * Inserts multiple items to the list at the specified index.
    2.25 + * If \p index equals the list size, this is effectively cxListAddArray().
    2.26 + *
    2.27 + * This method is usually more efficient than invoking cxListInsert()
    2.28 + * multiple times.
    2.29 + *
    2.30 + * If there is not enough memory to add all elements, the returned value is
    2.31 + * less than \p n.
    2.32 + *
    2.33 + * @param list the list
    2.34 + * @param index the index where to add the elements
    2.35 + * @param array a pointer to the elements to add
    2.36 + * @param n the number of elements to add
    2.37 + * @return the number of added elements
    2.38 + */
    2.39 +__attribute__((__nonnull__))
    2.40 +static inline size_t cxListInsertArray(
    2.41 +        CxList *list,
    2.42 +        size_t index,
    2.43 +        void const *array,
    2.44 +        size_t n
    2.45 +) {
    2.46 +    return list->cl->insert_array(list, index, array, n);
    2.47 +}
    2.48 +
    2.49 +/**
    2.50   * Inserts an element after the current location of the specified iterator.
    2.51   *
    2.52   * The used iterator remains operational, but all other active iterators should

     3.1 --- a/src/linked_list.c	Mon Jan 23 20:00:26 2023 +0100
     3.2 +++ b/src/linked_list.c	Mon Jan 23 20:22:11 2023 +0100
     3.3 @@ -518,19 +518,47 @@
     3.4      return 0;
     3.5  }
     3.6  
     3.7 +static size_t cx_ll_insert_array(
     3.8 +        struct cx_list_s *list,
     3.9 +        size_t index,
    3.10 +        void const *array,
    3.11 +        size_t n
    3.12 +) {
    3.13 +    // out-of bounds and corner case check
    3.14 +    if (index > list->size || n == 0) return 0;
    3.15 +
    3.16 +    // find position efficiently
    3.17 +    cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
    3.18 +
    3.19 +    // perform first insert
    3.20 +    if (0 != cx_ll_insert_at(list, node, array)) {
    3.21 +        return 1;
    3.22 +    }
    3.23 +
    3.24 +    // is there more?
    3.25 +    if (n == 1) return 1;
    3.26 +
    3.27 +    // we now know exactly where we are
    3.28 +    node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
    3.29 +
    3.30 +    // we can add the remaining nodes and immedately advance to the inserted node
    3.31 +    char const *source = array;
    3.32 +    for (size_t i = 1; i < n; i++) {
    3.33 +        source += list->itemsize;
    3.34 +        if (0 != cx_ll_insert_at(list, node, source)) {
    3.35 +            return i;
    3.36 +        }
    3.37 +        node = node->next;
    3.38 +    }
    3.39 +    return n;
    3.40 +}
    3.41 +
    3.42  static int cx_ll_insert(
    3.43          struct cx_list_s *list,
    3.44          size_t index,
    3.45          void const *elem
    3.46  ) {
    3.47 -    // out-of bounds check
    3.48 -    if (index > list->size) return 1;
    3.49 -
    3.50 -    // find position efficiently
    3.51 -    cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
    3.52 -
    3.53 -    // perform insert
    3.54 -    return cx_ll_insert_at(list, node, elem);
    3.55 +    return cx_ll_insert_array(list, index, elem, 1) != 1;
    3.56  }
    3.57  
    3.58  static int cx_ll_add(
    3.59 @@ -545,13 +573,7 @@
    3.60          void const *array,
    3.61          size_t n
    3.62  ) {
    3.63 -    // TODO: redirect to cx_ll_insert_array
    3.64 -    cx_for_n (i, n) {
    3.65 -        if (cx_ll_add(list, ((char const *) array) + i * list->itemsize)) {
    3.66 -            return i;
    3.67 -        }
    3.68 -    }
    3.69 -    return n;
    3.70 +    return cx_ll_insert_array(list, list->size, array, n);
    3.71  }
    3.72  
    3.73  static int cx_pll_insert(
    3.74 @@ -783,6 +805,7 @@
    3.75          cx_ll_add,
    3.76          cx_ll_add_array,
    3.77          cx_ll_insert,
    3.78 +        cx_ll_insert_array,
    3.79          cx_ll_insert_iter,
    3.80          cx_ll_remove,
    3.81          cx_ll_at,
    3.82 @@ -799,6 +822,7 @@
    3.83          cx_pll_add,
    3.84          cx_ll_add_array,
    3.85          cx_pll_insert,
    3.86 +        cx_ll_insert_array,
    3.87          cx_pll_insert_iter,
    3.88          cx_ll_remove,
    3.89          cx_pll_at,

     4.1 --- a/test/test_list.cpp	Mon Jan 23 20:00:26 2023 +0100
     4.2 +++ b/test/test_list.cpp	Mon Jan 23 20:22:11 2023 +0100
     4.3 @@ -633,6 +633,34 @@
     4.4          EXPECT_EQ(*(int *) cxListAt(list, 3), 42);
     4.5      }
     4.6  
     4.7 +    static void verifyInsertArray(CxList *list) {
     4.8 +        int a[5] = {5, 47, 11, 13, 42};
     4.9 +        int b[5] = {9, 18, 72, 50, 7};
    4.10 +
    4.11 +        size_t inserted;
    4.12 +
    4.13 +        inserted = cxListInsertArray(list, 0, a, 5);
    4.14 +        EXPECT_EQ(inserted, 5);
    4.15 +        EXPECT_EQ(*(int *) cxListAt(list, 0), 5);
    4.16 +        EXPECT_EQ(*(int *) cxListAt(list, 1), 47);
    4.17 +        EXPECT_EQ(*(int *) cxListAt(list, 2), 11);
    4.18 +        EXPECT_EQ(*(int *) cxListAt(list, 3), 13);
    4.19 +        EXPECT_EQ(*(int *) cxListAt(list, 4), 42);
    4.20 +
    4.21 +        inserted = cxListInsertArray(list, 3, b, 5);
    4.22 +        EXPECT_EQ(inserted, 5);
    4.23 +        EXPECT_EQ(*(int *) cxListAt(list, 0), 5);
    4.24 +        EXPECT_EQ(*(int *) cxListAt(list, 1), 47);
    4.25 +        EXPECT_EQ(*(int *) cxListAt(list, 2), 11);
    4.26 +        EXPECT_EQ(*(int *) cxListAt(list, 3), 9);
    4.27 +        EXPECT_EQ(*(int *) cxListAt(list, 4), 18);
    4.28 +        EXPECT_EQ(*(int *) cxListAt(list, 5), 72);
    4.29 +        EXPECT_EQ(*(int *) cxListAt(list, 6), 50);
    4.30 +        EXPECT_EQ(*(int *) cxListAt(list, 7), 7);
    4.31 +        EXPECT_EQ(*(int *) cxListAt(list, 8), 13);
    4.32 +        EXPECT_EQ(*(int *) cxListAt(list, 9), 42);
    4.33 +    }
    4.34 +
    4.35      void verifyRemove(CxList *list) const {
    4.36          EXPECT_EQ(cxListRemove(list, 2), 0);
    4.37          EXPECT_EQ(cxListRemove(list, 4), 0);
    4.38 @@ -824,6 +852,19 @@
    4.39      verifyInsert(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 2)));
    4.40  }
    4.41  
    4.42 +TEST_F(LinkedList, cxListInsertArray) {
    4.43 +    verifyInsertArray(autofree(cxLinkedListCreate(&testingAllocator, cx_cmp_int, sizeof(int))));
    4.44 +}
    4.45 +
    4.46 +TEST_F(PointerLinkedList, cxListInsertArray) {
    4.47 +    //TODO: this is unfixably broken - solve with issue #234
    4.48 +    //verifyInsertArray(autofree(cxPointerLinkedListCreate(&testingAllocator, cx_cmp_int)));
    4.49 +}
    4.50 +
    4.51 +TEST_F(ArrayList, cxListInsertArray) {
    4.52 +    verifyInsertArray(autofree(cxArrayListCreate(&testingAllocator, cx_cmp_int, sizeof(int), 4)));
    4.53 +}
    4.54 +
    4.55  TEST_F(LinkedList, cxListRemove) {
    4.56      verifyRemove(linkedListFromTestData());
    4.57  }