Mercurial > hg > ucx / changeset

--- a/src/cx/linked_list.h	Sat Dec 04 17:38:23 2021 +0100
+++ b/src/cx/linked_list.h	Mon Dec 20 11:17:06 2021 +0100
@@ -172,20 +172,16 @@
  * \li \p loc_next and \p loc_prev
  * \li \p loc_next and \p begin
  *
- * This function returns an adjacent node according to the following rules:
- * \li if the node has only one adjacent node, that one is returned
- * \li otherwise, the former \c prev node is returned
- *
- * \remark The \c next and \c prev pointers of the removed node are cleared by this function.
+ * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used
+ * to traverse to a former adjacent node in the list.
  *
  * @param begin a pointer to the begin node pointer (optional)
  * @param end a pointer to the end node pointer (optional)
  * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
  * @param loc_next the location of a \c next pointer within your node struct (required)
  * @param node the node to remove
- * @return an adjacent node or \c NULL, if this was the last node
  */
-void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node);
+void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node);
 
 
 /**
@@ -216,6 +212,8 @@
  * }
  * \endcode
  *
+ * @note This is a recursive function with at most logarithmic recursion depth.
+ *
  * @param begin a pointer to the begin node pointer (required)
  * @param end a pointer to the end node pointer (optional)
  * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present)

--- a/src/linked_list.c	Sat Dec 04 17:38:23 2021 +0100
+++ b/src/linked_list.c	Mon Dec 20 11:17:06 2021 +0100
@@ -137,7 +137,7 @@
     }
 }
 
-void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
+void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
     assert(loc_next >= 0);
     assert(loc_prev >= 0 || begin != NULL);
 
@@ -150,31 +150,23 @@
         prev = cx_linked_list_prev(*begin, loc_next, node);
     }
 
-    // update links of adjacent nodes
-    if (prev != NULL) {
+    // update next pointer of prev node, or set begin
+    if (prev == NULL) {
+        if (begin != NULL) {
+            *begin = next;
+        }
+    } else {
         CX_LL_PTR(prev, loc_next) = next;
     }
-    if (next != NULL && loc_prev >= 0) {
-        CX_LL_PTR(next, loc_prev) = prev;
-    }
 
-    // erase links of the target node
-    CX_LL_PTR(node, loc_next) = NULL;
-    if (loc_prev >= 0) {
-        CX_LL_PTR(node, loc_prev) = NULL;
+    // update prev pointer of next node, or set end
+    if (next == NULL) {
+        if (end != NULL) {
+            *end = prev;
+        }
+    } else if (loc_prev >= 0) {
+        CX_LL_PTR(next, loc_prev) = prev;
     }
-
-    // update begin, if required
-    if (*begin == node) {
-        *begin = next;
-    }
-
-    // update end, if required
-    if (end != NULL && *end == node) {
-        *end = prev;
-    }
-
-    return prev == NULL ? next : prev;
 }
 
 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
@@ -239,8 +231,9 @@
     return ret;
 }
 
-void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
-                         ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
+void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
+        void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
+        ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
     assert(begin != NULL);
     assert(loc_next >= 0);
     assert(loc_data >= 0);
@@ -424,19 +417,9 @@
     // out-of-bounds check
     if (node == NULL) return 1;
 
-    // change left side connection
-    if (node->prev == NULL) {
-        ll->begin = node->next;
-    } else {
-        node->prev->next = node->next;
-    }
-
-    // change right side connection
-    if (node->next == NULL) {
-        ll->end = node->prev;
-    } else {
-        node->next->prev = node->prev;
-    }
+    // remove
+    cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
+                          CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
 
     // adjust size
     list->size--;

--- a/test/test_list.c	Sat Dec 04 17:38:23 2021 +0100
+++ b/test/test_list.c	Mon Dec 20 11:17:06 2021 +0100
@@ -288,7 +288,6 @@
 
     void *begin;
     void *end;
-    void *result;
 
     // single linked list
     struct node third = {NULL};
@@ -296,23 +295,17 @@
     struct node first = {&second};
     begin = &first;
 
-    result = cx_linked_list_remove(&begin, NULL, -1, loc, &second);
-    CU_ASSERT_PTR_EQUAL(result, &first)
+    cx_linked_list_remove(&begin, NULL, -1, loc, &second);
     CU_ASSERT_PTR_EQUAL(begin, &first)
     CU_ASSERT_PTR_EQUAL(first.next, &third)
-    CU_ASSERT_PTR_NULL(second.next)
     CU_ASSERT_PTR_NULL(third.next)
 
-    result = cx_linked_list_remove(&begin, NULL, -1, loc, &first);
-    CU_ASSERT_PTR_EQUAL(result, &third)
+    cx_linked_list_remove(&begin, NULL, -1, loc, &first);
     CU_ASSERT_PTR_EQUAL(begin, &third)
-    CU_ASSERT_PTR_NULL(first.next)
     CU_ASSERT_PTR_NULL(third.next)
 
-    result = cx_linked_list_remove(&begin, NULL, -1, loc, &third);
-    CU_ASSERT_PTR_NULL(result)
+    cx_linked_list_remove(&begin, NULL, -1, loc, &third);
     CU_ASSERT_PTR_NULL(begin)
-    CU_ASSERT_PTR_NULL(third.next)
 
     // doubly linked list
     struct dnode dthird = {NULL , NULL};
@@ -323,32 +316,23 @@
     begin = &dfirst;
     end = &dthird;
 
-    result = cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
-    CU_ASSERT_PTR_EQUAL(result, &dfirst)
+    cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
     CU_ASSERT_PTR_EQUAL(begin, &dfirst)
     CU_ASSERT_PTR_EQUAL(end, &dthird)
     CU_ASSERT_PTR_NULL(dfirst.prev)
     CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird)
-    CU_ASSERT_PTR_NULL(dsecond.prev)
-    CU_ASSERT_PTR_NULL(dsecond.next)
     CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst)
     CU_ASSERT_PTR_NULL(dthird.next)
 
-    result = cx_linked_list_remove(&begin, &end, ploc, loc, &dthird);
-    CU_ASSERT_PTR_EQUAL(result, &dfirst)
+    cx_linked_list_remove(&begin, &end, ploc, loc, &dthird);
     CU_ASSERT_PTR_EQUAL(begin, &dfirst)
     CU_ASSERT_PTR_EQUAL(end, &dfirst)
     CU_ASSERT_PTR_NULL(dfirst.prev)
     CU_ASSERT_PTR_NULL(dfirst.next)
-    CU_ASSERT_PTR_NULL(dthird.prev)
-    CU_ASSERT_PTR_NULL(dthird.next)
 
-    result = cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst);
-    CU_ASSERT_PTR_NULL(result)
+    cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst);
     CU_ASSERT_PTR_NULL(begin)
     CU_ASSERT_PTR_NULL(end)
-    CU_ASSERT_PTR_NULL(dfirst.next)
-    CU_ASSERT_PTR_NULL(dfirst.prev)
 }
 
 void test_linked_list_size(void) {