# HG changeset patch # User Mike Becker # Date 1674501731 -3600 # Node ID eafb45eefc51a97a38c0eed8c10407147ea7d881 # Parent ceadf0792ded6d7a7f51aedac17d71d4d2d61e29 add cxListInsertArray() - fixes #224 diff -r ceadf0792ded -r eafb45eefc51 src/array_list.c --- 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, diff -r ceadf0792ded -r eafb45eefc51 src/cx/list.h --- 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 diff -r ceadf0792ded -r eafb45eefc51 src/linked_list.c --- 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, diff -r ceadf0792ded -r eafb45eefc51 test/test_list.cpp --- 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()); }