Mercurial > hg > ucx / changeset

     1.1 --- a/src/cx/linked_list.h	Sat Dec 04 17:38:23 2021 +0100
     1.2 +++ b/src/cx/linked_list.h	Mon Dec 20 11:17:06 2021 +0100
     1.3 @@ -172,20 +172,16 @@
     1.4   * \li \p loc_next and \p loc_prev
     1.5   * \li \p loc_next and \p begin
     1.6   *
     1.7 - * This function returns an adjacent node according to the following rules:
     1.8 - * \li if the node has only one adjacent node, that one is returned
     1.9 - * \li otherwise, the former \c prev node is returned
    1.10 - *
    1.11 - * \remark The \c next and \c prev pointers of the removed node are cleared by this function.
    1.12 + * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used
    1.13 + * to traverse to a former adjacent node in the list.
    1.14   *
    1.15   * @param begin a pointer to the begin node pointer (optional)
    1.16   * @param end a pointer to the end node pointer (optional)
    1.17   * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
    1.18   * @param loc_next the location of a \c next pointer within your node struct (required)
    1.19   * @param node the node to remove
    1.20 - * @return an adjacent node or \c NULL, if this was the last node
    1.21   */
    1.22 -void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node);
    1.23 +void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node);
    1.24  
    1.25  
    1.26  /**
    1.27 @@ -216,6 +212,8 @@
    1.28   * }
    1.29   * \endcode
    1.30   *
    1.31 + * @note This is a recursive function with at most logarithmic recursion depth.
    1.32 + *
    1.33   * @param begin a pointer to the begin node pointer (required)
    1.34   * @param end a pointer to the end node pointer (optional)
    1.35   * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present)

     2.1 --- a/src/linked_list.c	Sat Dec 04 17:38:23 2021 +0100
     2.2 +++ b/src/linked_list.c	Mon Dec 20 11:17:06 2021 +0100
     2.3 @@ -137,7 +137,7 @@
     2.4      }
     2.5  }
     2.6  
     2.7 -void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
     2.8 +void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
     2.9      assert(loc_next >= 0);
    2.10      assert(loc_prev >= 0 || begin != NULL);
    2.11  
    2.12 @@ -150,31 +150,23 @@
    2.13          prev = cx_linked_list_prev(*begin, loc_next, node);
    2.14      }
    2.15  
    2.16 -    // update links of adjacent nodes
    2.17 -    if (prev != NULL) {
    2.18 +    // update next pointer of prev node, or set begin
    2.19 +    if (prev == NULL) {
    2.20 +        if (begin != NULL) {
    2.21 +            *begin = next;
    2.22 +        }
    2.23 +    } else {
    2.24          CX_LL_PTR(prev, loc_next) = next;
    2.25      }
    2.26 -    if (next != NULL && loc_prev >= 0) {
    2.27 +
    2.28 +    // update prev pointer of next node, or set end
    2.29 +    if (next == NULL) {
    2.30 +        if (end != NULL) {
    2.31 +            *end = prev;
    2.32 +        }
    2.33 +    } else if (loc_prev >= 0) {
    2.34          CX_LL_PTR(next, loc_prev) = prev;
    2.35      }
    2.36 -
    2.37 -    // erase links of the target node
    2.38 -    CX_LL_PTR(node, loc_next) = NULL;
    2.39 -    if (loc_prev >= 0) {
    2.40 -        CX_LL_PTR(node, loc_prev) = NULL;
    2.41 -    }
    2.42 -
    2.43 -    // update begin, if required
    2.44 -    if (*begin == node) {
    2.45 -        *begin = next;
    2.46 -    }
    2.47 -
    2.48 -    // update end, if required
    2.49 -    if (end != NULL && *end == node) {
    2.50 -        *end = prev;
    2.51 -    }
    2.52 -
    2.53 -    return prev == NULL ? next : prev;
    2.54  }
    2.55  
    2.56  size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
    2.57 @@ -239,8 +231,9 @@
    2.58      return ret;
    2.59  }
    2.60  
    2.61 -void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
    2.62 -                         ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
    2.63 +void cx_linked_list_sort( /* NOLINT(misc-no-recursion) - purposely recursive function */
    2.64 +        void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
    2.65 +        ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
    2.66      assert(begin != NULL);
    2.67      assert(loc_next >= 0);
    2.68      assert(loc_data >= 0);
    2.69 @@ -424,19 +417,9 @@
    2.70      // out-of-bounds check
    2.71      if (node == NULL) return 1;
    2.72  
    2.73 -    // change left side connection
    2.74 -    if (node->prev == NULL) {
    2.75 -        ll->begin = node->next;
    2.76 -    } else {
    2.77 -        node->prev->next = node->next;
    2.78 -    }
    2.79 -
    2.80 -    // change right side connection
    2.81 -    if (node->next == NULL) {
    2.82 -        ll->end = node->prev;
    2.83 -    } else {
    2.84 -        node->next->prev = node->prev;
    2.85 -    }
    2.86 +    // remove
    2.87 +    cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
    2.88 +                          CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
    2.89  
    2.90      // adjust size
    2.91      list->size--;

     3.1 --- a/test/test_list.c	Sat Dec 04 17:38:23 2021 +0100
     3.2 +++ b/test/test_list.c	Mon Dec 20 11:17:06 2021 +0100
     3.3 @@ -288,7 +288,6 @@
     3.4  
     3.5      void *begin;
     3.6      void *end;
     3.7 -    void *result;
     3.8  
     3.9      // single linked list
    3.10      struct node third = {NULL};
    3.11 @@ -296,23 +295,17 @@
    3.12      struct node first = {&second};
    3.13      begin = &first;
    3.14  
    3.15 -    result = cx_linked_list_remove(&begin, NULL, -1, loc, &second);
    3.16 -    CU_ASSERT_PTR_EQUAL(result, &first)
    3.17 +    cx_linked_list_remove(&begin, NULL, -1, loc, &second);
    3.18      CU_ASSERT_PTR_EQUAL(begin, &first)
    3.19      CU_ASSERT_PTR_EQUAL(first.next, &third)
    3.20 -    CU_ASSERT_PTR_NULL(second.next)
    3.21      CU_ASSERT_PTR_NULL(third.next)
    3.22  
    3.23 -    result = cx_linked_list_remove(&begin, NULL, -1, loc, &first);
    3.24 -    CU_ASSERT_PTR_EQUAL(result, &third)
    3.25 +    cx_linked_list_remove(&begin, NULL, -1, loc, &first);
    3.26      CU_ASSERT_PTR_EQUAL(begin, &third)
    3.27 -    CU_ASSERT_PTR_NULL(first.next)
    3.28      CU_ASSERT_PTR_NULL(third.next)
    3.29  
    3.30 -    result = cx_linked_list_remove(&begin, NULL, -1, loc, &third);
    3.31 -    CU_ASSERT_PTR_NULL(result)
    3.32 +    cx_linked_list_remove(&begin, NULL, -1, loc, &third);
    3.33      CU_ASSERT_PTR_NULL(begin)
    3.34 -    CU_ASSERT_PTR_NULL(third.next)
    3.35  
    3.36      // doubly linked list
    3.37      struct dnode dthird = {NULL , NULL};
    3.38 @@ -323,32 +316,23 @@
    3.39      begin = &dfirst;
    3.40      end = &dthird;
    3.41  
    3.42 -    result = cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
    3.43 -    CU_ASSERT_PTR_EQUAL(result, &dfirst)
    3.44 +    cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
    3.45      CU_ASSERT_PTR_EQUAL(begin, &dfirst)
    3.46      CU_ASSERT_PTR_EQUAL(end, &dthird)
    3.47      CU_ASSERT_PTR_NULL(dfirst.prev)
    3.48      CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird)
    3.49 -    CU_ASSERT_PTR_NULL(dsecond.prev)
    3.50 -    CU_ASSERT_PTR_NULL(dsecond.next)
    3.51      CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst)
    3.52      CU_ASSERT_PTR_NULL(dthird.next)
    3.53  
    3.54 -    result = cx_linked_list_remove(&begin, &end, ploc, loc, &dthird);
    3.55 -    CU_ASSERT_PTR_EQUAL(result, &dfirst)
    3.56 +    cx_linked_list_remove(&begin, &end, ploc, loc, &dthird);
    3.57      CU_ASSERT_PTR_EQUAL(begin, &dfirst)
    3.58      CU_ASSERT_PTR_EQUAL(end, &dfirst)
    3.59      CU_ASSERT_PTR_NULL(dfirst.prev)
    3.60      CU_ASSERT_PTR_NULL(dfirst.next)
    3.61 -    CU_ASSERT_PTR_NULL(dthird.prev)
    3.62 -    CU_ASSERT_PTR_NULL(dthird.next)
    3.63  
    3.64 -    result = cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst);
    3.65 -    CU_ASSERT_PTR_NULL(result)
    3.66 +    cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst);
    3.67      CU_ASSERT_PTR_NULL(begin)
    3.68      CU_ASSERT_PTR_NULL(end)
    3.69 -    CU_ASSERT_PTR_NULL(dfirst.next)
    3.70 -    CU_ASSERT_PTR_NULL(dfirst.prev)
    3.71  }
    3.72  
    3.73  void test_linked_list_size(void) {