# HG changeset patch # User Mike Becker # Date 1676476091 -3600 # Node ID 7340c4255f1fc4c67e48624667aad61f122107a0 # Parent c9d00886117885a105cb6c5b8b748a0621f24fdd implement backwards iterator - fixes #238 diff -r c9d008861178 -r 7340c4255f1f src/array_list.c --- a/src/array_list.c Wed Feb 08 20:26:26 2023 +0100 +++ b/src/array_list.c Wed Feb 15 16:48:11 2023 +0100 @@ -395,6 +395,21 @@ } } +static void cx_arl_iter_prev(void *it) { + struct cx_iterator_base_s *itbase = it; + struct cx_mut_iterator_s *iter = it; + cx_array_list *const list = iter->src_handle; + if (itbase->remove) { + itbase->remove = false; + cx_arl_remove(iter->src_handle, iter->index); + } + iter->index--; + if (iter->index < list->base.size) { + iter->elem_handle = ((char *) list->data) + + iter->index * list->base.itemsize; + } +} + static bool cx_arl_iter_flag_rm(void *it) { struct cx_iterator_base_s *iter = it; if (iter->mutating) { @@ -407,7 +422,8 @@ static struct cx_iterator_s cx_arl_iterator( struct cx_list_s const *list, - size_t index + size_t index, + bool backwards ) { struct cx_iterator_s iter; @@ -416,7 +432,7 @@ iter.elem_handle = cx_arl_at(list, index); iter.base.valid = cx_arl_iter_valid; iter.base.current = cx_arl_iter_current; - iter.base.next = cx_arl_iter_next; + iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next; iter.base.flag_removal = cx_arl_iter_flag_rm; iter.base.remove = false; iter.base.mutating = false; diff -r c9d008861178 -r 7340c4255f1f src/cx/list.h --- a/src/cx/list.h Wed Feb 08 20:26:26 2023 +0100 +++ b/src/cx/list.h Wed Feb 15 16:48:11 2023 +0100 @@ -211,7 +211,8 @@ */ struct cx_iterator_s (*iterator)( struct cx_list_s const *list, - size_t index + size_t index, + bool backward ); }; @@ -456,11 +457,30 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxListIterator( +static inline CxIterator cxListIteratorAt( CxList const *list, size_t index ) { - return list->cl->iterator(list, index); + return list->cl->iterator(list, index, false); +} + +/** + * Returns a backwards iterator pointing to the item at the specified index. + * + * The returned iterator is position-aware. + * + * If the index is out of range, a past-the-end iterator will be returned. + * + * @param list the list + * @param index the index where the iterator shall point at + * @return a new iterator + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxIterator cxListBackwardsIteratorAt( + CxList const *list, + size_t index +) { + return list->cl->iterator(list, index, true); } /** @@ -475,7 +495,25 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -CxMutIterator cxListMutIterator( +CxMutIterator cxListMutIteratorAt( + CxList *list, + size_t index +); + +/** + * Returns a mutating backwards iterator pointing to the item at the + * specified index. + * + * The returned iterator is position-aware. + * + * If the index is out of range, a past-the-end iterator will be returned. + * + * @param list the list + * @param index the index where the iterator shall point at + * @return a new iterator + */ +__attribute__((__nonnull__, __warn_unused_result__)) +CxMutIterator cxListMutBackwardsIteratorAt( CxList *list, size_t index ); @@ -491,8 +529,8 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxListBegin(CxList const *list) { - return list->cl->iterator(list, 0); +static inline CxIterator cxListIterator(CxList const *list) { + return list->cl->iterator(list, 0, false); } /** @@ -506,8 +544,39 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxListBeginMut(CxList *list) { - return cxListMutIterator(list, 0); +static inline CxMutIterator cxListMutIterator(CxList *list) { + return cxListMutIteratorAt(list, 0); +} + + +/** + * Returns a backwards iterator pointing to the last item of the list. + * + * The returned iterator is position-aware. + * + * If the list is empty, a past-the-end iterator will be returned. + * + * @param list the list + * @return a new iterator + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxIterator cxListBackwardsIterator(CxList const *list) { + return list->cl->iterator(list, list->size - 1, true); +} + +/** + * Returns a mutating backwards iterator pointing to the last item of the list. + * + * The returned iterator is position-aware. + * + * If the list is empty, a past-the-end iterator will be returned. + * + * @param list the list + * @return a new iterator + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) { + return cxListMutBackwardsIteratorAt(list, list->size - 1); } /** diff -r c9d008861178 -r 7340c4255f1f src/linked_list.c --- a/src/linked_list.c Wed Feb 08 20:26:26 2023 +0100 +++ b/src/linked_list.c Wed Feb 15 16:48:11 2023 +0100 @@ -764,6 +764,27 @@ } } +static void cx_ll_iter_prev(void *it) { + struct cx_iterator_base_s *itbase = it; + if (itbase->remove) { + itbase->remove = false; + struct cx_mut_iterator_s *iter = it; + cx_linked_list *ll = iter->src_handle; + cx_linked_list_node *node = iter->elem_handle; + iter->elem_handle = node->prev; + iter->index--; + cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, + CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); + ll->base.size--; + cxFree(ll->base.allocator, node); + } else { + struct cx_iterator_s *iter = it; + iter->index--; + cx_linked_list_node *node = iter->elem_handle; + iter->elem_handle = node->prev; + } +} + static void *cx_ll_iter_current(void const *it) { struct cx_iterator_s const *iter = it; cx_linked_list_node *node = iter->elem_handle; @@ -782,7 +803,8 @@ static CxIterator cx_ll_iterator( struct cx_list_s const *list, - size_t index + size_t index, + bool backwards ) { CxIterator iter; iter.index = index; @@ -790,7 +812,7 @@ iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); iter.base.valid = cx_ll_iter_valid; iter.base.current = cx_ll_iter_current; - iter.base.next = cx_ll_iter_next; + iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; iter.base.flag_removal = cx_ll_iter_flag_rm; iter.base.mutating = false; iter.base.remove = false; diff -r c9d008861178 -r 7340c4255f1f src/list.c --- a/src/list.c Wed Feb 08 20:26:26 2023 +0100 +++ b/src/list.c Wed Feb 15 16:48:11 2023 +0100 @@ -149,9 +149,10 @@ static struct cx_iterator_s cx_pl_iterator( struct cx_list_s const *list, - size_t index + size_t index, + bool backwards ) { - struct cx_iterator_s iter = list->climpl->iterator(list, index); + struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards); iter.base.current_impl = iter.base.current; iter.base.current = cx_pl_iter_current; return iter; @@ -194,14 +195,14 @@ void cxListDestroy(CxList *list) { switch (list->content_destructor_type) { case CX_DESTRUCTOR_SIMPLE: { - CxIterator iter = cxListBegin(list); + CxIterator iter = cxListIterator(list); cx_foreach(void*, elem, iter) { list->simple_destructor(elem); } break; } case CX_DESTRUCTOR_ADVANCED: { - CxIterator iter = cxListBegin(list); + CxIterator iter = cxListIterator(list); cx_foreach(void*, elem, iter) { list->advanced_destructor.func(list->advanced_destructor.data, elem); } @@ -225,8 +226,8 @@ } else { // different compare functions, use iterator if (list->size == other->size) { - CxIterator left = cxListBegin(list); - CxIterator right = cxListBegin(other); + CxIterator left = cxListIterator(list); + CxIterator right = cxListIterator(other); for (size_t i = 0; i < list->size; i++) { void *leftValue = cxIteratorCurrent(left); void *rightValue = cxIteratorCurrent(right); @@ -244,11 +245,11 @@ } } -CxMutIterator cxListMutIterator( +CxMutIterator cxListMutIteratorAt( CxList *list, size_t index ) { - CxIterator it = list->cl->iterator(list, index); + CxIterator it = list->cl->iterator(list, index, false); it.base.mutating = true; // we know the iterators share the same memory layout @@ -256,3 +257,16 @@ memcpy(&iter, &it, sizeof(CxMutIterator)); return iter; } + +CxMutIterator cxListMutBackwardsIteratorAt( + CxList *list, + size_t index +) { + CxIterator it = list->cl->iterator(list, index, true); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); + return iter; +} diff -r c9d008861178 -r 7340c4255f1f tests/test_list.cpp --- a/tests/test_list.cpp Wed Feb 08 20:26:26 2023 +0100 +++ b/tests/test_list.cpp Wed Feb 15 16:48:11 2023 +0100 @@ -735,13 +735,13 @@ result = cxListSwap(list, 16, 17); EXPECT_NE(0, result); - auto iter = cxListBegin(list); + auto iter = cxListIterator(list); cx_foreach(int*, e, iter) { EXPECT_EQ(*e, swapped[iter.index]); } - // TODO: replace with backward iterator - cx_for_n(i, 16) { - EXPECT_EQ(*((int *) cxListAt(list, i)), swapped[i]); + iter = cxListBackwardsIterator(list); + cx_foreach(int*, e, iter) { + EXPECT_EQ(*e, swapped[iter.index]); } } @@ -777,16 +777,44 @@ } void verifyIterator(CxList *list) const { - int i = 0; - auto iter = cxListBeginMut(list); + auto iter = cxListIterator(list); + size_t i = 0; cx_foreach(int*, x, iter) { - ASSERT_EQ(iter.index, (size_t) (i + 1) / 2); - ASSERT_EQ(*x, testdata.data[i]); - if (i % 2 == 1) cxIteratorFlagRemoval(iter); + ASSERT_EQ(i, iter.index); + EXPECT_EQ(*x, testdata.data[iter.index]); i++; } + ASSERT_EQ(i, list->size); + iter = cxListBackwardsIterator(list); + cx_foreach(int*, x, iter) { + ASSERT_EQ(i - 1, iter.index); + EXPECT_EQ(*x, testdata.data[iter.index]); + i--; + } + ASSERT_EQ(i, 0); auto len = testdata_len; - EXPECT_EQ(i, len); + i = len / 2; + auto mut_iter = cxListMutIteratorAt(list, i); + size_t j = 0; + cx_foreach(int*, x, mut_iter) { + ASSERT_EQ(mut_iter.index, len / 2 + j / 2); + ASSERT_EQ(*x, testdata.data[i]); + if (i % 2 == 1) cxIteratorFlagRemoval(mut_iter); + i++; + j++; + } + ASSERT_EQ(i, len); + i = len / 2; + j = 0; + mut_iter = cxListMutBackwardsIteratorAt(list, i - 1); + cx_foreach(int*, x, mut_iter) { + ASSERT_EQ(mut_iter.index, len / 2 - 1 - j); + ASSERT_EQ(*x, testdata.data[i - 1]); + if (i % 2 == 0) cxIteratorFlagRemoval(mut_iter); + i--; + j++; + } + ASSERT_EQ(i, 0); ASSERT_EQ(list->size, len / 2); cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]); } @@ -794,7 +822,7 @@ static void verifyInsertViaIterator(CxList *list) { int newdata[] = {10, 20, 30, 40, 50}; - auto iter = cxListMutIterator(list, 2); + auto iter = cxListMutIteratorAt(list, 2); EXPECT_TRUE(cxIteratorValid(iter)); EXPECT_EQ(iter.index, 2); EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2); @@ -807,16 +835,16 @@ EXPECT_EQ(iter.index, 3); EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2); - iter = cxListBeginMut(list); + iter = cxListMutIterator(list); cxListInsertBefore(&iter, &newdata[2]); EXPECT_TRUE(cxIteratorValid(iter)); EXPECT_EQ(iter.index, 1); EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 0); - iter = cxListMutIterator(list, list->size); + iter = cxListMutIteratorAt(list, list->size); cxListInsertBefore(&iter, &newdata[3]); EXPECT_FALSE(cxIteratorValid(iter)); EXPECT_EQ(iter.index, 9); - iter = cxListMutIterator(list, list->size); + iter = cxListMutIteratorAt(list, list->size); cxListInsertAfter(&iter, &newdata[4]); EXPECT_FALSE(cxIteratorValid(iter)); EXPECT_EQ(iter.index, 10);