Mercurial > hg > ucx / changeset

     1.1 --- a/CHANGELOG	Mon Dec 18 16:14:07 2023 +0100
     1.2 +++ b/CHANGELOG	Mon Dec 18 18:22:53 2023 +0100
     1.3 @@ -1,5 +1,7 @@
     1.4  Version 3.1 - tbd.
     1.5  ------------------------
     1.6 + * adds cx_linked_list_find_node()
     1.7 + * adds cxListFindRemove()
     1.8   * adds cxBufferReset()
     1.9   * adds cx_cmp_ptr()
    1.10   * fixes wrong link from UCX 2 documentation to UCX 3 documentation

     2.1 --- a/src/array_list.c	Mon Dec 18 16:14:07 2023 +0100
     2.2 +++ b/src/array_list.c	Mon Dec 18 18:22:53 2023 +0100
     2.3 @@ -363,9 +363,10 @@
     2.4      }
     2.5  }
     2.6  
     2.7 -static ssize_t cx_arl_find(
     2.8 -        struct cx_list_s const *list,
     2.9 -        void const *elem
    2.10 +static ssize_t cx_arl_find_remove(
    2.11 +        struct cx_list_s *list,
    2.12 +        void const *elem,
    2.13 +        bool remove
    2.14  ) {
    2.15      assert(list->cmpfunc != NULL);
    2.16      assert(list->size < SIZE_MAX / 2);
    2.17 @@ -373,7 +374,15 @@
    2.18  
    2.19      for (ssize_t i = 0; i < (ssize_t) list->size; i++) {
    2.20          if (0 == list->cmpfunc(elem, cur)) {
    2.21 -            return i;
    2.22 +            if (remove) {
    2.23 +                if (0 == cx_arl_remove(list, i)) {
    2.24 +                    return i;
    2.25 +                } else {
    2.26 +                    return -1;
    2.27 +                }
    2.28 +            } else {
    2.29 +                return i;
    2.30 +            }
    2.31          }
    2.32          cur += list->item_size;
    2.33      }
    2.34 @@ -501,7 +510,7 @@
    2.35          cx_arl_clear,
    2.36          cx_arl_swap,
    2.37          cx_arl_at,
    2.38 -        cx_arl_find,
    2.39 +        cx_arl_find_remove,
    2.40          cx_arl_sort,
    2.41          cx_arl_compare,
    2.42          cx_arl_reverse,

     3.1 --- a/src/cx/linked_list.h	Mon Dec 18 16:14:07 2023 +0100
     3.2 +++ b/src/cx/linked_list.h	Mon Dec 18 18:22:53 2023 +0100
     3.3 @@ -131,6 +131,27 @@
     3.4  ) __attribute__((__nonnull__));
     3.5  
     3.6  /**
     3.7 + * Finds the node containing an element within a linked list.
     3.8 + *
     3.9 + * @param result a pointer to the memory where the node pointer (or \c NULL if the element
    3.10 + * could not be found) shall be stored to
    3.11 + * @param start a pointer to the start node
    3.12 + * @param loc_advance the location of the pointer to advance
    3.13 + * @param loc_data the location of the \c data pointer within your node struct
    3.14 + * @param cmp_func a compare function to compare \p elem against the node data
    3.15 + * @param elem a pointer to the element to find
    3.16 + * @return the index of the element or a negative value if it could not be found
    3.17 + */
    3.18 +ssize_t cx_linked_list_find_node(
    3.19 +        void **result,
    3.20 +        void const *start,
    3.21 +        ptrdiff_t loc_advance,
    3.22 +        ptrdiff_t loc_data,
    3.23 +        cx_compare_func cmp_func,
    3.24 +        void const *elem
    3.25 +) __attribute__((__nonnull__));
    3.26 +
    3.27 +/**
    3.28   * Finds the first node in a linked list.
    3.29   *
    3.30   * The function starts with the pointer denoted by \p node and traverses the list

     4.1 --- a/src/cx/list.h	Mon Dec 18 16:14:07 2023 +0100
     4.2 +++ b/src/cx/list.h	Mon Dec 18 18:22:53 2023 +0100
     4.3 @@ -136,11 +136,12 @@
     4.4      );
     4.5  
     4.6      /**
     4.7 -     * Member function for finding an element.
     4.8 +     * Member function for finding and optionally removing an element.
     4.9       */
    4.10 -    ssize_t (*find)(
    4.11 -            struct cx_list_s const *list,
    4.12 -            void const *elem
    4.13 +    ssize_t (*find_remove)(
    4.14 +            struct cx_list_s *list,
    4.15 +            void const *elem,
    4.16 +            bool remove
    4.17      );
    4.18  
    4.19      /**
    4.20 @@ -579,7 +580,25 @@
    4.21          CxList const *list,
    4.22          void const *elem
    4.23  ) {
    4.24 -    return list->cl->find(list, elem);
    4.25 +    return list->cl->find_remove((CxList*)list, elem, false);
    4.26 +}
    4.27 +
    4.28 +/**
    4.29 + * Removes and returns the index of the first element that equals \p elem.
    4.30 + *
    4.31 + * Determining equality is performed by the list's comparator function.
    4.32 + *
    4.33 + * @param list the list
    4.34 + * @param elem the element to find and remove
    4.35 + * @return the index of the now removed element or a negative
    4.36 + * value when the element is not found or could not be removed
    4.37 + */
    4.38 +__attribute__((__nonnull__))
    4.39 +static inline ssize_t cxListFindRemove(
    4.40 +        CxList *list,
    4.41 +        void const *elem
    4.42 +) {
    4.43 +    return list->cl->find_remove(list, elem, true);
    4.44  }
    4.45  
    4.46  /**

     5.1 --- a/src/linked_list.c	Mon Dec 18 16:14:07 2023 +0100
     5.2 +++ b/src/linked_list.c	Mon Dec 18 18:22:53 2023 +0100
     5.3 @@ -64,6 +64,23 @@
     5.4          cx_compare_func cmp_func,
     5.5          void const *elem
     5.6  ) {
     5.7 +    void *dummy;
     5.8 +    return cx_linked_list_find_node(
     5.9 +            &dummy, start,
    5.10 +            loc_advance, loc_data,
    5.11 +            cmp_func, elem
    5.12 +    );
    5.13 +}
    5.14 +
    5.15 +ssize_t cx_linked_list_find_node(
    5.16 +        void **result,
    5.17 +        void const *start,
    5.18 +        ptrdiff_t loc_advance,
    5.19 +        ptrdiff_t loc_data,
    5.20 +        cx_compare_func cmp_func,
    5.21 +        void const *elem
    5.22 +) {
    5.23 +    assert(result != NULL);
    5.24      assert(start != NULL);
    5.25      assert(loc_advance >= 0);
    5.26      assert(loc_data >= 0);
    5.27 @@ -74,11 +91,13 @@
    5.28      do {
    5.29          void *current = ll_data(node);
    5.30          if (cmp_func(current, elem) == 0) {
    5.31 +            *result = (void*) node;
    5.32              return index;
    5.33          }
    5.34          node = ll_advance(node);
    5.35          index++;
    5.36      } while (node != NULL);
    5.37 +    *result = NULL;
    5.38      return -1;
    5.39  }
    5.40  
    5.41 @@ -736,13 +755,35 @@
    5.42      return node == NULL ? NULL : node->payload;
    5.43  }
    5.44  
    5.45 -static ssize_t cx_ll_find(
    5.46 -        struct cx_list_s const *list,
    5.47 -        void const *elem
    5.48 +static ssize_t cx_ll_find_remove(
    5.49 +        struct cx_list_s *list,
    5.50 +        void const *elem,
    5.51 +        bool remove
    5.52  ) {
    5.53 -    return cx_linked_list_find(((cx_linked_list *) list)->begin,
    5.54 -                               CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
    5.55 -                               list->cmpfunc, elem);
    5.56 +    if (remove) {
    5.57 +        cx_linked_list *ll = ((cx_linked_list *) list);
    5.58 +        cx_linked_list_node *node;
    5.59 +        ssize_t index = cx_linked_list_find_node(
    5.60 +                (void **) &node,
    5.61 +                ll->begin,
    5.62 +                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
    5.63 +                list->cmpfunc, elem
    5.64 +        );
    5.65 +        if (node != NULL) {
    5.66 +            cx_invoke_destructor(list, node->payload);
    5.67 +            cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
    5.68 +                                  CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
    5.69 +            list->size--;
    5.70 +            cxFree(list->allocator, node);
    5.71 +        }
    5.72 +        return index;
    5.73 +    } else {
    5.74 +        return cx_linked_list_find(
    5.75 +                ((cx_linked_list *) list)->begin,
    5.76 +                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
    5.77 +                list->cmpfunc, elem
    5.78 +        );
    5.79 +    }
    5.80  }
    5.81  
    5.82  static void cx_ll_sort(struct cx_list_s *list) {
    5.83 @@ -895,7 +936,7 @@
    5.84          cx_ll_clear,
    5.85          cx_ll_swap,
    5.86          cx_ll_at,
    5.87 -        cx_ll_find,
    5.88 +        cx_ll_find_remove,
    5.89          cx_ll_sort,
    5.90          cx_ll_compare,
    5.91          cx_ll_reverse,

     6.1 --- a/src/list.c	Mon Dec 18 16:14:07 2023 +0100
     6.2 +++ b/src/list.c	Mon Dec 18 18:22:53 2023 +0100
     6.3 @@ -115,12 +115,13 @@
     6.4      return ptr == NULL ? NULL : *ptr;
     6.5  }
     6.6  
     6.7 -static ssize_t cx_pl_find(
     6.8 -        struct cx_list_s const *list,
     6.9 -        void const *elem
    6.10 +static ssize_t cx_pl_find_remove(
    6.11 +        struct cx_list_s *list,
    6.12 +        void const *elem,
    6.13 +        bool remove
    6.14  ) {
    6.15      cx_pl_hack_cmpfunc(list);
    6.16 -    ssize_t ret = list->climpl->find(list, &elem);
    6.17 +    ssize_t ret = list->climpl->find_remove(list, &elem, remove);
    6.18      cx_pl_unhack_cmpfunc(list);
    6.19      return ret;
    6.20  }
    6.21 @@ -171,7 +172,7 @@
    6.22          cx_pl_clear,
    6.23          cx_pl_swap,
    6.24          cx_pl_at,
    6.25 -        cx_pl_find,
    6.26 +        cx_pl_find_remove,
    6.27          cx_pl_sort,
    6.28          cx_pl_compare,
    6.29          cx_pl_reverse,
    6.30 @@ -208,9 +209,10 @@
    6.31      return NULL;
    6.32  }
    6.33  
    6.34 -static ssize_t cx_emptyl_find(
    6.35 -        __attribute__((__unused__)) struct cx_list_s const *list,
    6.36 -        __attribute__((__unused__)) void const *elem
    6.37 +static ssize_t cx_emptyl_find_remove(
    6.38 +        __attribute__((__unused__)) struct cx_list_s *list,
    6.39 +        __attribute__((__unused__)) void const *elem,
    6.40 +        __attribute__((__unused__)) bool remove
    6.41  ) {
    6.42      return -1;
    6.43  }
    6.44 @@ -248,7 +250,7 @@
    6.45          cx_emptyl_noop,
    6.46          NULL,
    6.47          cx_emptyl_at,
    6.48 -        cx_emptyl_find,
    6.49 +        cx_emptyl_find_remove,
    6.50          cx_emptyl_noop,
    6.51          cx_emptyl_compare,
    6.52          cx_emptyl_noop,

     7.1 --- a/tests/test_list.cpp	Mon Dec 18 16:14:07 2023 +0100
     7.2 +++ b/tests/test_list.cpp	Mon Dec 18 18:22:53 2023 +0100
     7.3 @@ -699,6 +699,27 @@
     7.4          EXPECT_NE(cxListRemove(list, testdata_len), 0);
     7.5      }
     7.6  
     7.7 +    void verifyFindRemove(CxList *list) const {
     7.8 +        size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp)
     7.9 +        int val = testdata.data[exp];
    7.10 +        // randomly picked number could occur earlier in list - find first position
    7.11 +        cx_for_n (i, exp) {
    7.12 +            if (testdata.data[i] == val) {
    7.13 +                exp = i;
    7.14 +                break;
    7.15 +            }
    7.16 +        }
    7.17 +        EXPECT_EQ(cxListSize(list), testdata_len);
    7.18 +        EXPECT_EQ(cxListFind(list, &val), exp);
    7.19 +        EXPECT_EQ(cxListFindRemove(list, &val), exp);
    7.20 +        EXPECT_EQ(cxListSize(list), testdata_len - 1);
    7.21 +        EXPECT_NE(cxListFind(list, &val), exp);
    7.22 +
    7.23 +        int notinlist = -1;
    7.24 +        EXPECT_LT(cxListFindRemove(list, &notinlist), 0);
    7.25 +        EXPECT_EQ(cxListSize(list), testdata_len - 1);
    7.26 +    }
    7.27 +
    7.28      static void verifyClear(CxList *list) {
    7.29          cxListClear(list);
    7.30          EXPECT_EQ(0, cxListSize(list));
    7.31 @@ -1133,6 +1154,22 @@
    7.32      verifyRemove(pointerArrayListFromTestData());
    7.33  }
    7.34  
    7.35 +TEST_F(LinkedList, cxListFindRemove) {
    7.36 +    verifyFindRemove(linkedListFromTestData());
    7.37 +}
    7.38 +
    7.39 +TEST_F(PointerLinkedList, cxListFindRemove) {
    7.40 +    verifyFindRemove(pointerLinkedListFromTestData());
    7.41 +}
    7.42 +
    7.43 +TEST_F(ArrayList, cxListFindRemove) {
    7.44 +    verifyFindRemove(arrayListFromTestData());
    7.45 +}
    7.46 +
    7.47 +TEST_F(PointerArrayList, cxListFindRemove) {
    7.48 +    verifyFindRemove(pointerArrayListFromTestData());
    7.49 +}
    7.50 +
    7.51  TEST_F(LinkedList, cxListClear) {
    7.52      verifyClear(linkedListFromTestData());
    7.53  }