Mercurial > hg > ucx / changeset

     1.1 --- a/src/array_list.c	Wed Feb 08 20:26:26 2023 +0100
     1.2 +++ b/src/array_list.c	Wed Feb 15 16:48:11 2023 +0100
     1.3 @@ -395,6 +395,21 @@
     1.4      }
     1.5  }
     1.6  
     1.7 +static void cx_arl_iter_prev(void *it) {
     1.8 +    struct cx_iterator_base_s *itbase = it;
     1.9 +    struct cx_mut_iterator_s *iter = it;
    1.10 +    cx_array_list *const list = iter->src_handle;
    1.11 +    if (itbase->remove) {
    1.12 +        itbase->remove = false;
    1.13 +        cx_arl_remove(iter->src_handle, iter->index);
    1.14 +    }
    1.15 +    iter->index--;
    1.16 +    if (iter->index < list->base.size) {
    1.17 +        iter->elem_handle = ((char *) list->data)
    1.18 +                            + iter->index * list->base.itemsize;
    1.19 +    }
    1.20 +}
    1.21 +
    1.22  static bool cx_arl_iter_flag_rm(void *it) {
    1.23      struct cx_iterator_base_s *iter = it;
    1.24      if (iter->mutating) {
    1.25 @@ -407,7 +422,8 @@
    1.26  
    1.27  static struct cx_iterator_s cx_arl_iterator(
    1.28          struct cx_list_s const *list,
    1.29 -        size_t index
    1.30 +        size_t index,
    1.31 +        bool backwards
    1.32  ) {
    1.33      struct cx_iterator_s iter;
    1.34  
    1.35 @@ -416,7 +432,7 @@
    1.36      iter.elem_handle = cx_arl_at(list, index);
    1.37      iter.base.valid = cx_arl_iter_valid;
    1.38      iter.base.current = cx_arl_iter_current;
    1.39 -    iter.base.next = cx_arl_iter_next;
    1.40 +    iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
    1.41      iter.base.flag_removal = cx_arl_iter_flag_rm;
    1.42      iter.base.remove = false;
    1.43      iter.base.mutating = false;

     2.1 --- a/src/cx/list.h	Wed Feb 08 20:26:26 2023 +0100
     2.2 +++ b/src/cx/list.h	Wed Feb 15 16:48:11 2023 +0100
     2.3 @@ -211,7 +211,8 @@
     2.4       */
     2.5      struct cx_iterator_s (*iterator)(
     2.6              struct cx_list_s const *list,
     2.7 -            size_t index
     2.8 +            size_t index,
     2.9 +            bool backward
    2.10      );
    2.11  };
    2.12  
    2.13 @@ -456,11 +457,30 @@
    2.14   * @return a new iterator
    2.15   */
    2.16  __attribute__((__nonnull__, __warn_unused_result__))
    2.17 -static inline CxIterator cxListIterator(
    2.18 +static inline CxIterator cxListIteratorAt(
    2.19          CxList const *list,
    2.20          size_t index
    2.21  ) {
    2.22 -    return list->cl->iterator(list, index);
    2.23 +    return list->cl->iterator(list, index, false);
    2.24 +}
    2.25 +
    2.26 +/**
    2.27 + * Returns a backwards iterator pointing to the item at the specified index.
    2.28 + *
    2.29 + * The returned iterator is position-aware.
    2.30 + *
    2.31 + * If the index is out of range, a past-the-end iterator will be returned.
    2.32 + *
    2.33 + * @param list the list
    2.34 + * @param index the index where the iterator shall point at
    2.35 + * @return a new iterator
    2.36 + */
    2.37 +__attribute__((__nonnull__, __warn_unused_result__))
    2.38 +static inline CxIterator cxListBackwardsIteratorAt(
    2.39 +        CxList const *list,
    2.40 +        size_t index
    2.41 +) {
    2.42 +    return list->cl->iterator(list, index, true);
    2.43  }
    2.44  
    2.45  /**
    2.46 @@ -475,7 +495,25 @@
    2.47   * @return a new iterator
    2.48   */
    2.49  __attribute__((__nonnull__, __warn_unused_result__))
    2.50 -CxMutIterator cxListMutIterator(
    2.51 +CxMutIterator cxListMutIteratorAt(
    2.52 +        CxList *list,
    2.53 +        size_t index
    2.54 +);
    2.55 +
    2.56 +/**
    2.57 + * Returns a mutating backwards iterator pointing to the item at the
    2.58 + * specified index.
    2.59 + *
    2.60 + * The returned iterator is position-aware.
    2.61 + *
    2.62 + * If the index is out of range, a past-the-end iterator will be returned.
    2.63 + *
    2.64 + * @param list the list
    2.65 + * @param index the index where the iterator shall point at
    2.66 + * @return a new iterator
    2.67 + */
    2.68 +__attribute__((__nonnull__, __warn_unused_result__))
    2.69 +CxMutIterator cxListMutBackwardsIteratorAt(
    2.70          CxList *list,
    2.71          size_t index
    2.72  );
    2.73 @@ -491,8 +529,8 @@
    2.74   * @return a new iterator
    2.75   */
    2.76  __attribute__((__nonnull__, __warn_unused_result__))
    2.77 -static inline CxIterator cxListBegin(CxList const *list) {
    2.78 -    return list->cl->iterator(list, 0);
    2.79 +static inline CxIterator cxListIterator(CxList const *list) {
    2.80 +    return list->cl->iterator(list, 0, false);
    2.81  }
    2.82  
    2.83  /**
    2.84 @@ -506,8 +544,39 @@
    2.85   * @return a new iterator
    2.86   */
    2.87  __attribute__((__nonnull__, __warn_unused_result__))
    2.88 -static inline CxMutIterator cxListBeginMut(CxList *list) {
    2.89 -    return cxListMutIterator(list, 0);
    2.90 +static inline CxMutIterator cxListMutIterator(CxList *list) {
    2.91 +    return cxListMutIteratorAt(list, 0);
    2.92 +}
    2.93 +
    2.94 +
    2.95 +/**
    2.96 + * Returns a backwards iterator pointing to the last item of the list.
    2.97 + *
    2.98 + * The returned iterator is position-aware.
    2.99 + *
   2.100 + * If the list is empty, a past-the-end iterator will be returned.
   2.101 + *
   2.102 + * @param list the list
   2.103 + * @return a new iterator
   2.104 + */
   2.105 +__attribute__((__nonnull__, __warn_unused_result__))
   2.106 +static inline CxIterator cxListBackwardsIterator(CxList const *list) {
   2.107 +    return list->cl->iterator(list, list->size - 1, true);
   2.108 +}
   2.109 +
   2.110 +/**
   2.111 + * Returns a mutating backwards iterator pointing to the last item of the list.
   2.112 + *
   2.113 + * The returned iterator is position-aware.
   2.114 + *
   2.115 + * If the list is empty, a past-the-end iterator will be returned.
   2.116 + *
   2.117 + * @param list the list
   2.118 + * @return a new iterator
   2.119 + */
   2.120 +__attribute__((__nonnull__, __warn_unused_result__))
   2.121 +static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) {
   2.122 +    return cxListMutBackwardsIteratorAt(list, list->size - 1);
   2.123  }
   2.124  
   2.125  /**

     3.1 --- a/src/linked_list.c	Wed Feb 08 20:26:26 2023 +0100
     3.2 +++ b/src/linked_list.c	Wed Feb 15 16:48:11 2023 +0100
     3.3 @@ -764,6 +764,27 @@
     3.4      }
     3.5  }
     3.6  
     3.7 +static void cx_ll_iter_prev(void *it) {
     3.8 +    struct cx_iterator_base_s *itbase = it;
     3.9 +    if (itbase->remove) {
    3.10 +        itbase->remove = false;
    3.11 +        struct cx_mut_iterator_s *iter = it;
    3.12 +        cx_linked_list *ll = iter->src_handle;
    3.13 +        cx_linked_list_node *node = iter->elem_handle;
    3.14 +        iter->elem_handle = node->prev;
    3.15 +        iter->index--;
    3.16 +        cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
    3.17 +                              CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
    3.18 +        ll->base.size--;
    3.19 +        cxFree(ll->base.allocator, node);
    3.20 +    } else {
    3.21 +        struct cx_iterator_s *iter = it;
    3.22 +        iter->index--;
    3.23 +        cx_linked_list_node *node = iter->elem_handle;
    3.24 +        iter->elem_handle = node->prev;
    3.25 +    }
    3.26 +}
    3.27 +
    3.28  static void *cx_ll_iter_current(void const *it) {
    3.29      struct cx_iterator_s const *iter = it;
    3.30      cx_linked_list_node *node = iter->elem_handle;
    3.31 @@ -782,7 +803,8 @@
    3.32  
    3.33  static CxIterator cx_ll_iterator(
    3.34          struct cx_list_s const *list,
    3.35 -        size_t index
    3.36 +        size_t index,
    3.37 +        bool backwards
    3.38  ) {
    3.39      CxIterator iter;
    3.40      iter.index = index;
    3.41 @@ -790,7 +812,7 @@
    3.42      iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
    3.43      iter.base.valid = cx_ll_iter_valid;
    3.44      iter.base.current = cx_ll_iter_current;
    3.45 -    iter.base.next = cx_ll_iter_next;
    3.46 +    iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
    3.47      iter.base.flag_removal = cx_ll_iter_flag_rm;
    3.48      iter.base.mutating = false;
    3.49      iter.base.remove = false;

     4.1 --- a/src/list.c	Wed Feb 08 20:26:26 2023 +0100
     4.2 +++ b/src/list.c	Wed Feb 15 16:48:11 2023 +0100
     4.3 @@ -149,9 +149,10 @@
     4.4  
     4.5  static struct cx_iterator_s cx_pl_iterator(
     4.6          struct cx_list_s const *list,
     4.7 -        size_t index
     4.8 +        size_t index,
     4.9 +        bool backwards
    4.10  ) {
    4.11 -    struct cx_iterator_s iter = list->climpl->iterator(list, index);
    4.12 +    struct cx_iterator_s iter = list->climpl->iterator(list, index, backwards);
    4.13      iter.base.current_impl = iter.base.current;
    4.14      iter.base.current = cx_pl_iter_current;
    4.15      return iter;
    4.16 @@ -194,14 +195,14 @@
    4.17  void cxListDestroy(CxList *list) {
    4.18      switch (list->content_destructor_type) {
    4.19          case CX_DESTRUCTOR_SIMPLE: {
    4.20 -            CxIterator iter = cxListBegin(list);
    4.21 +            CxIterator iter = cxListIterator(list);
    4.22              cx_foreach(void*, elem, iter) {
    4.23                  list->simple_destructor(elem);
    4.24              }
    4.25              break;
    4.26          }
    4.27          case CX_DESTRUCTOR_ADVANCED: {
    4.28 -            CxIterator iter = cxListBegin(list);
    4.29 +            CxIterator iter = cxListIterator(list);
    4.30              cx_foreach(void*, elem, iter) {
    4.31                  list->advanced_destructor.func(list->advanced_destructor.data, elem);
    4.32              }
    4.33 @@ -225,8 +226,8 @@
    4.34      } else {
    4.35          // different compare functions, use iterator
    4.36          if (list->size == other->size) {
    4.37 -            CxIterator left = cxListBegin(list);
    4.38 -            CxIterator right = cxListBegin(other);
    4.39 +            CxIterator left = cxListIterator(list);
    4.40 +            CxIterator right = cxListIterator(other);
    4.41              for (size_t i = 0; i < list->size; i++) {
    4.42                  void *leftValue = cxIteratorCurrent(left);
    4.43                  void *rightValue = cxIteratorCurrent(right);
    4.44 @@ -244,11 +245,11 @@
    4.45      }
    4.46  }
    4.47  
    4.48 -CxMutIterator cxListMutIterator(
    4.49 +CxMutIterator cxListMutIteratorAt(
    4.50          CxList *list,
    4.51          size_t index
    4.52  ) {
    4.53 -    CxIterator it = list->cl->iterator(list, index);
    4.54 +    CxIterator it = list->cl->iterator(list, index, false);
    4.55      it.base.mutating = true;
    4.56  
    4.57      // we know the iterators share the same memory layout
    4.58 @@ -256,3 +257,16 @@
    4.59      memcpy(&iter, &it, sizeof(CxMutIterator));
    4.60      return iter;
    4.61  }
    4.62 +
    4.63 +CxMutIterator cxListMutBackwardsIteratorAt(
    4.64 +        CxList *list,
    4.65 +        size_t index
    4.66 +) {
    4.67 +    CxIterator it = list->cl->iterator(list, index, true);
    4.68 +    it.base.mutating = true;
    4.69 +
    4.70 +    // we know the iterators share the same memory layout
    4.71 +    CxMutIterator iter;
    4.72 +    memcpy(&iter, &it, sizeof(CxMutIterator));
    4.73 +    return iter;
    4.74 +}

     5.1 --- a/tests/test_list.cpp	Wed Feb 08 20:26:26 2023 +0100
     5.2 +++ b/tests/test_list.cpp	Wed Feb 15 16:48:11 2023 +0100
     5.3 @@ -735,13 +735,13 @@
     5.4          result = cxListSwap(list, 16, 17);
     5.5          EXPECT_NE(0, result);
     5.6  
     5.7 -        auto iter = cxListBegin(list);
     5.8 +        auto iter = cxListIterator(list);
     5.9          cx_foreach(int*, e, iter) {
    5.10              EXPECT_EQ(*e, swapped[iter.index]);
    5.11          }
    5.12 -        // TODO: replace with backward iterator
    5.13 -        cx_for_n(i, 16) {
    5.14 -            EXPECT_EQ(*((int *) cxListAt(list, i)), swapped[i]);
    5.15 +        iter = cxListBackwardsIterator(list);
    5.16 +        cx_foreach(int*, e, iter) {
    5.17 +            EXPECT_EQ(*e, swapped[iter.index]);
    5.18          }
    5.19      }
    5.20  
    5.21 @@ -777,16 +777,44 @@
    5.22      }
    5.23  
    5.24      void verifyIterator(CxList *list) const {
    5.25 -        int i = 0;
    5.26 -        auto iter = cxListBeginMut(list);
    5.27 +        auto iter = cxListIterator(list);
    5.28 +        size_t i = 0;
    5.29          cx_foreach(int*, x, iter) {
    5.30 -            ASSERT_EQ(iter.index, (size_t) (i + 1) / 2);
    5.31 -            ASSERT_EQ(*x, testdata.data[i]);
    5.32 -            if (i % 2 == 1) cxIteratorFlagRemoval(iter);
    5.33 +            ASSERT_EQ(i, iter.index);
    5.34 +            EXPECT_EQ(*x, testdata.data[iter.index]);
    5.35              i++;
    5.36          }
    5.37 +        ASSERT_EQ(i, list->size);
    5.38 +        iter = cxListBackwardsIterator(list);
    5.39 +        cx_foreach(int*, x, iter) {
    5.40 +            ASSERT_EQ(i - 1, iter.index);
    5.41 +            EXPECT_EQ(*x, testdata.data[iter.index]);
    5.42 +            i--;
    5.43 +        }
    5.44 +        ASSERT_EQ(i, 0);
    5.45          auto len = testdata_len;
    5.46 -        EXPECT_EQ(i, len);
    5.47 +        i = len / 2;
    5.48 +        auto mut_iter = cxListMutIteratorAt(list, i);
    5.49 +        size_t j = 0;
    5.50 +        cx_foreach(int*, x, mut_iter) {
    5.51 +            ASSERT_EQ(mut_iter.index, len / 2 + j / 2);
    5.52 +            ASSERT_EQ(*x, testdata.data[i]);
    5.53 +            if (i % 2 == 1) cxIteratorFlagRemoval(mut_iter);
    5.54 +            i++;
    5.55 +            j++;
    5.56 +        }
    5.57 +        ASSERT_EQ(i, len);
    5.58 +        i = len / 2;
    5.59 +        j = 0;
    5.60 +        mut_iter = cxListMutBackwardsIteratorAt(list, i - 1);
    5.61 +        cx_foreach(int*, x, mut_iter) {
    5.62 +            ASSERT_EQ(mut_iter.index, len / 2 - 1 - j);
    5.63 +            ASSERT_EQ(*x, testdata.data[i - 1]);
    5.64 +            if (i % 2 == 0) cxIteratorFlagRemoval(mut_iter);
    5.65 +            i--;
    5.66 +            j++;
    5.67 +        }
    5.68 +        ASSERT_EQ(i, 0);
    5.69          ASSERT_EQ(list->size, len / 2);
    5.70          cx_for_n(j, len / 2) ASSERT_EQ(*(int *) cxListAt(list, j), testdata.data[j * 2]);
    5.71      }
    5.72 @@ -794,7 +822,7 @@
    5.73      static void verifyInsertViaIterator(CxList *list) {
    5.74          int newdata[] = {10, 20, 30, 40, 50};
    5.75  
    5.76 -        auto iter = cxListMutIterator(list, 2);
    5.77 +        auto iter = cxListMutIteratorAt(list, 2);
    5.78          EXPECT_TRUE(cxIteratorValid(iter));
    5.79          EXPECT_EQ(iter.index, 2);
    5.80          EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
    5.81 @@ -807,16 +835,16 @@
    5.82          EXPECT_EQ(iter.index, 3);
    5.83          EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 2);
    5.84  
    5.85 -        iter = cxListBeginMut(list);
    5.86 +        iter = cxListMutIterator(list);
    5.87          cxListInsertBefore(&iter, &newdata[2]);
    5.88          EXPECT_TRUE(cxIteratorValid(iter));
    5.89          EXPECT_EQ(iter.index, 1);
    5.90          EXPECT_EQ(*(int *) cxIteratorCurrent(iter), 0);
    5.91 -        iter = cxListMutIterator(list, list->size);
    5.92 +        iter = cxListMutIteratorAt(list, list->size);
    5.93          cxListInsertBefore(&iter, &newdata[3]);
    5.94          EXPECT_FALSE(cxIteratorValid(iter));
    5.95          EXPECT_EQ(iter.index, 9);
    5.96 -        iter = cxListMutIterator(list, list->size);
    5.97 +        iter = cxListMutIteratorAt(list, list->size);
    5.98          cxListInsertAfter(&iter, &newdata[4]);
    5.99          EXPECT_FALSE(cxIteratorValid(iter));
   5.100          EXPECT_EQ(iter.index, 10);