Mercurial > hg > ucx / changeset

--- 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;

--- 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);
 }
 
 /**

--- 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;

--- 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;
+}

--- 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);