Mercurial > hg > ucx / changeset

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

--- a/src/array_list.c	Mon Dec 18 16:14:07 2023 +0100
+++ b/src/array_list.c	Mon Dec 18 18:22:53 2023 +0100
@@ -363,9 +363,10 @@
     }
 }
 
-static ssize_t cx_arl_find(
-        struct cx_list_s const *list,
-        void const *elem
+static ssize_t cx_arl_find_remove(
+        struct cx_list_s *list,
+        void const *elem,
+        bool remove
 ) {
     assert(list->cmpfunc != NULL);
     assert(list->size < SIZE_MAX / 2);
@@ -373,7 +374,15 @@
 
     for (ssize_t i = 0; i < (ssize_t) list->size; i++) {
         if (0 == list->cmpfunc(elem, cur)) {
-            return i;
+            if (remove) {
+                if (0 == cx_arl_remove(list, i)) {
+                    return i;
+                } else {
+                    return -1;
+                }
+            } else {
+                return i;
+            }
         }
         cur += list->item_size;
     }
@@ -501,7 +510,7 @@
         cx_arl_clear,
         cx_arl_swap,
         cx_arl_at,
-        cx_arl_find,
+        cx_arl_find_remove,
         cx_arl_sort,
         cx_arl_compare,
         cx_arl_reverse,

--- a/src/cx/linked_list.h	Mon Dec 18 16:14:07 2023 +0100
+++ b/src/cx/linked_list.h	Mon Dec 18 18:22:53 2023 +0100
@@ -131,6 +131,27 @@
 ) __attribute__((__nonnull__));
 
 /**
+ * Finds the node containing an element within a linked list.
+ *
+ * @param result a pointer to the memory where the node pointer (or \c NULL if the element
+ * could not be found) shall be stored to
+ * @param start a pointer to the start node
+ * @param loc_advance the location of the pointer to advance
+ * @param loc_data the location of the \c data pointer within your node struct
+ * @param cmp_func a compare function to compare \p elem against the node data
+ * @param elem a pointer to the element to find
+ * @return the index of the element or a negative value if it could not be found
+ */
+ssize_t cx_linked_list_find_node(
+        void **result,
+        void const *start,
+        ptrdiff_t loc_advance,
+        ptrdiff_t loc_data,
+        cx_compare_func cmp_func,
+        void const *elem
+) __attribute__((__nonnull__));
+
+/**
  * Finds the first node in a linked list.
  *
  * The function starts with the pointer denoted by \p node and traverses the list

--- a/src/cx/list.h	Mon Dec 18 16:14:07 2023 +0100
+++ b/src/cx/list.h	Mon Dec 18 18:22:53 2023 +0100
@@ -136,11 +136,12 @@
     );
 
     /**
-     * Member function for finding an element.
+     * Member function for finding and optionally removing an element.
      */
-    ssize_t (*find)(
-            struct cx_list_s const *list,
-            void const *elem
+    ssize_t (*find_remove)(
+            struct cx_list_s *list,
+            void const *elem,
+            bool remove
     );
 
     /**
@@ -579,7 +580,25 @@
         CxList const *list,
         void const *elem
 ) {
-    return list->cl->find(list, elem);
+    return list->cl->find_remove((CxList*)list, elem, false);
+}
+
+/**
+ * Removes and returns the index of the first element that equals \p elem.
+ *
+ * Determining equality is performed by the list's comparator function.
+ *
+ * @param list the list
+ * @param elem the element to find and remove
+ * @return the index of the now removed element or a negative
+ * value when the element is not found or could not be removed
+ */
+__attribute__((__nonnull__))
+static inline ssize_t cxListFindRemove(
+        CxList *list,
+        void const *elem
+) {
+    return list->cl->find_remove(list, elem, true);
 }
 
 /**

--- a/src/linked_list.c	Mon Dec 18 16:14:07 2023 +0100
+++ b/src/linked_list.c	Mon Dec 18 18:22:53 2023 +0100
@@ -64,6 +64,23 @@
         cx_compare_func cmp_func,
         void const *elem
 ) {
+    void *dummy;
+    return cx_linked_list_find_node(
+            &dummy, start,
+            loc_advance, loc_data,
+            cmp_func, elem
+    );
+}
+
+ssize_t cx_linked_list_find_node(
+        void **result,
+        void const *start,
+        ptrdiff_t loc_advance,
+        ptrdiff_t loc_data,
+        cx_compare_func cmp_func,
+        void const *elem
+) {
+    assert(result != NULL);
     assert(start != NULL);
     assert(loc_advance >= 0);
     assert(loc_data >= 0);
@@ -74,11 +91,13 @@
     do {
         void *current = ll_data(node);
         if (cmp_func(current, elem) == 0) {
+            *result = (void*) node;
             return index;
         }
         node = ll_advance(node);
         index++;
     } while (node != NULL);
+    *result = NULL;
     return -1;
 }
 
@@ -736,13 +755,35 @@
     return node == NULL ? NULL : node->payload;
 }
 
-static ssize_t cx_ll_find(
-        struct cx_list_s const *list,
-        void const *elem
+static ssize_t cx_ll_find_remove(
+        struct cx_list_s *list,
+        void const *elem,
+        bool remove
 ) {
-    return cx_linked_list_find(((cx_linked_list *) list)->begin,
-                               CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
-                               list->cmpfunc, elem);
+    if (remove) {
+        cx_linked_list *ll = ((cx_linked_list *) list);
+        cx_linked_list_node *node;
+        ssize_t index = cx_linked_list_find_node(
+                (void **) &node,
+                ll->begin,
+                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+                list->cmpfunc, elem
+        );
+        if (node != NULL) {
+            cx_invoke_destructor(list, node->payload);
+            cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
+                                  CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
+            list->size--;
+            cxFree(list->allocator, node);
+        }
+        return index;
+    } else {
+        return cx_linked_list_find(
+                ((cx_linked_list *) list)->begin,
+                CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+                list->cmpfunc, elem
+        );
+    }
 }
 
 static void cx_ll_sort(struct cx_list_s *list) {
@@ -895,7 +936,7 @@
         cx_ll_clear,
         cx_ll_swap,
         cx_ll_at,
-        cx_ll_find,
+        cx_ll_find_remove,
         cx_ll_sort,
         cx_ll_compare,
         cx_ll_reverse,

--- a/src/list.c	Mon Dec 18 16:14:07 2023 +0100
+++ b/src/list.c	Mon Dec 18 18:22:53 2023 +0100
@@ -115,12 +115,13 @@
     return ptr == NULL ? NULL : *ptr;
 }
 
-static ssize_t cx_pl_find(
-        struct cx_list_s const *list,
-        void const *elem
+static ssize_t cx_pl_find_remove(
+        struct cx_list_s *list,
+        void const *elem,
+        bool remove
 ) {
     cx_pl_hack_cmpfunc(list);
-    ssize_t ret = list->climpl->find(list, &elem);
+    ssize_t ret = list->climpl->find_remove(list, &elem, remove);
     cx_pl_unhack_cmpfunc(list);
     return ret;
 }
@@ -171,7 +172,7 @@
         cx_pl_clear,
         cx_pl_swap,
         cx_pl_at,
-        cx_pl_find,
+        cx_pl_find_remove,
         cx_pl_sort,
         cx_pl_compare,
         cx_pl_reverse,
@@ -208,9 +209,10 @@
     return NULL;
 }
 
-static ssize_t cx_emptyl_find(
-        __attribute__((__unused__)) struct cx_list_s const *list,
-        __attribute__((__unused__)) void const *elem
+static ssize_t cx_emptyl_find_remove(
+        __attribute__((__unused__)) struct cx_list_s *list,
+        __attribute__((__unused__)) void const *elem,
+        __attribute__((__unused__)) bool remove
 ) {
     return -1;
 }
@@ -248,7 +250,7 @@
         cx_emptyl_noop,
         NULL,
         cx_emptyl_at,
-        cx_emptyl_find,
+        cx_emptyl_find_remove,
         cx_emptyl_noop,
         cx_emptyl_compare,
         cx_emptyl_noop,

--- a/tests/test_list.cpp	Mon Dec 18 16:14:07 2023 +0100
+++ b/tests/test_list.cpp	Mon Dec 18 18:22:53 2023 +0100
@@ -699,6 +699,27 @@
         EXPECT_NE(cxListRemove(list, testdata_len), 0);
     }
 
+    void verifyFindRemove(CxList *list) const {
+        size_t exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp)
+        int val = testdata.data[exp];
+        // randomly picked number could occur earlier in list - find first position
+        cx_for_n (i, exp) {
+            if (testdata.data[i] == val) {
+                exp = i;
+                break;
+            }
+        }
+        EXPECT_EQ(cxListSize(list), testdata_len);
+        EXPECT_EQ(cxListFind(list, &val), exp);
+        EXPECT_EQ(cxListFindRemove(list, &val), exp);
+        EXPECT_EQ(cxListSize(list), testdata_len - 1);
+        EXPECT_NE(cxListFind(list, &val), exp);
+
+        int notinlist = -1;
+        EXPECT_LT(cxListFindRemove(list, &notinlist), 0);
+        EXPECT_EQ(cxListSize(list), testdata_len - 1);
+    }
+
     static void verifyClear(CxList *list) {
         cxListClear(list);
         EXPECT_EQ(0, cxListSize(list));
@@ -1133,6 +1154,22 @@
     verifyRemove(pointerArrayListFromTestData());
 }
 
+TEST_F(LinkedList, cxListFindRemove) {
+    verifyFindRemove(linkedListFromTestData());
+}
+
+TEST_F(PointerLinkedList, cxListFindRemove) {
+    verifyFindRemove(pointerLinkedListFromTestData());
+}
+
+TEST_F(ArrayList, cxListFindRemove) {
+    verifyFindRemove(arrayListFromTestData());
+}
+
+TEST_F(PointerArrayList, cxListFindRemove) {
+    verifyFindRemove(pointerArrayListFromTestData());
+}
+
 TEST_F(LinkedList, cxListClear) {
     verifyClear(linkedListFromTestData());
 }