# HG changeset patch # User Mike Becker # Date 1643463124 -3600 # Node ID 3dc9075df8223f13db9ef1737ecdc46a8ef1fc7d # Parent 435c9965b2dd4440b76df5c9758b60675286d594 add cxListInsertAfter() and cxListInsertBefore() diff -r 435c9965b2dd -r 3dc9075df822 src/cx/list.h --- 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 diff -r 435c9965b2dd -r 3dc9075df822 src/linked_list.c --- 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, diff -r 435c9965b2dd -r 3dc9075df822 test/test_list.c --- 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);