add cx_linked_list_{prev, remove, reverse}

Fri, 08 Oct 2021 19:47:31 +0200

author
Mike Becker <universe@uap-core.de>
date
Fri, 08 Oct 2021 19:47:31 +0200
changeset 473
1bd4b8c28722
parent 472
18f964adad1b
child 474
9c1fccda16bc

add cx_linked_list_{prev, remove, reverse}

changes assertions for some low level methods (loc_next is now always mandatory)

src/cx/linked_list.h file | annotate | diff | comparison | revisions
src/linked_list.c file | annotate | diff | comparison | revisions
test/test_list.c file | annotate | diff | comparison | revisions
     1.1 --- a/src/cx/linked_list.h	Fri Oct 08 18:58:49 2021 +0200
     1.2 +++ b/src/cx/linked_list.h	Fri Oct 08 19:47:31 2021 +0200
     1.3 @@ -110,6 +110,18 @@
     1.4  void *cx_linked_list_last(void *begin, ptrdiff_t loc_next);
     1.5  
     1.6  /**
     1.7 + * Finds the predecessor of a node in case it is not linked.
     1.8 + *
     1.9 + * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined.
    1.10 + *
    1.11 + * @param begin the node where to start the search
    1.12 + * @param loc_next the location of the \c next pointer
    1.13 + * @param node the successor of the node to find
    1.14 + * @return the node or \c NULL if \p node has no predecessor
    1.15 + */
    1.16 +void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node);
    1.17 +
    1.18 +/**
    1.19   * Adds a new node to a linked list.
    1.20   *
    1.21   * \remark One of the pointers \p begin and \p end may be \c NULL, but not both.
    1.22 @@ -117,12 +129,38 @@
    1.23   * @param begin a pointer to the begin node pointer (if your list has one)
    1.24   * @param end a pointer to the end node pointer (if your list has one)
    1.25   * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
    1.26 - * @param loc_next the location of a \c next pointer within your node struct (negative if your struct does not have one)
    1.27 + * @param loc_next the location of a \c next pointer within your node struct (required)
    1.28   * @param new_node a pointer to the node that shall be appended
    1.29   */
    1.30  void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
    1.31  
    1.32  /**
    1.33 + * Removes a node from the linked list.
    1.34 + *
    1.35 + * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
    1.36 + * addresses are provided, the pointers are adjusted accordingly.
    1.37 + *
    1.38 + * The following combinations of arguments are valid (more arguments are optional):
    1.39 + * \li \p loc_next and \p loc_prev
    1.40 + * \li \p loc_next and \p begin
    1.41 + *
    1.42 + * This function returns an adjacent node according to the following rules:
    1.43 + * \li if the node has only one adjacent node, that one is returned
    1.44 + * \li otherwise, the former \c prev node is returned
    1.45 + *
    1.46 + * \remark The \c next and \c prev pointers of the removed node are cleared by this function.
    1.47 + *
    1.48 + * @param begin a pointer to the begin node pointer (optional)
    1.49 + * @param end a pointer to the end node pointer (optional)
    1.50 + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
    1.51 + * @param loc_next the location of a \c next pointer within your node struct (required)
    1.52 + * @param node the node to remove
    1.53 + * @return an adjacent node or \c NULL, if this was the last node
    1.54 + */
    1.55 +void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node);
    1.56 +
    1.57 +
    1.58 +/**
    1.59   * Determines the size of a linked list starting with \p node.
    1.60   * @param node the first node
    1.61   * @param loc_next the location of the \c next pointer within the node struct
    1.62 @@ -162,6 +200,17 @@
    1.63  void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
    1.64                           ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func);
    1.65  
    1.66 +
    1.67 +/**
    1.68 + * Reverses the order of the nodes in a linked list.
    1.69 + *
    1.70 + * @param begin a pointer to the begin node pointer (required)
    1.71 + * @param end a pointer to the end node pointer (optional)
    1.72 + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
    1.73 + * @param loc_next the location of a \c next pointer within your node struct (required)
    1.74 + */
    1.75 +void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next);
    1.76 +
    1.77  #ifdef __cplusplus
    1.78  } /* extern "C" */
    1.79  #endif
     2.1 --- a/src/linked_list.c	Fri Oct 08 18:58:49 2021 +0200
     2.2 +++ b/src/linked_list.c	Fri Oct 08 19:47:31 2021 +0200
     2.3 @@ -36,6 +36,8 @@
     2.4  #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
     2.5  
     2.6  void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
     2.7 +    assert(start != NULL);
     2.8 +    assert(loc_advance >= 0);
     2.9      size_t i = start_index;
    2.10      void *cur = start;
    2.11      while (i != index && cur != NULL) {
    2.12 @@ -46,6 +48,7 @@
    2.13  }
    2.14  
    2.15  void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) {
    2.16 +    assert(loc_next >= 0);
    2.17      if (begin == NULL)
    2.18          return NULL;
    2.19  
    2.20 @@ -58,7 +61,21 @@
    2.21      return last;
    2.22  }
    2.23  
    2.24 +void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) {
    2.25 +    assert(begin != NULL);
    2.26 +    assert(loc_next >= 0);
    2.27 +    if (begin == node) return NULL;
    2.28 +    void *cur = begin;
    2.29 +    void *next;
    2.30 +    while (1) {
    2.31 +        next = CX_LL_PTR(cur, loc_next);
    2.32 +        if (next == node) return cur;
    2.33 +        cur = next;
    2.34 +    }
    2.35 +}
    2.36 +
    2.37  void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
    2.38 +    assert(loc_next >= 0);
    2.39      void *last;
    2.40      if (end == NULL) {
    2.41          assert(begin != NULL);
    2.42 @@ -85,7 +102,48 @@
    2.43      }
    2.44  }
    2.45  
    2.46 +void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) {
    2.47 +    assert(loc_next >= 0);
    2.48 +    assert(loc_prev >= 0 || begin != NULL);
    2.49 +
    2.50 +    // find adjacent nodes
    2.51 +    void *next = CX_LL_PTR(node, loc_next);
    2.52 +    void *prev;
    2.53 +    if (loc_prev >= 0) {
    2.54 +        prev = CX_LL_PTR(node, loc_prev);
    2.55 +    } else {
    2.56 +        prev = cx_linked_list_prev(*begin, loc_next, node);
    2.57 +    }
    2.58 +
    2.59 +    // update links of adjacent nodes
    2.60 +    if (prev != NULL) {
    2.61 +        CX_LL_PTR(prev, loc_next) = next;
    2.62 +    }
    2.63 +    if (next != NULL && loc_prev >= 0) {
    2.64 +        CX_LL_PTR(next, loc_prev) = prev;
    2.65 +    }
    2.66 +
    2.67 +    // erase links of the target node
    2.68 +    CX_LL_PTR(node, loc_next) = NULL;
    2.69 +    if (loc_prev >= 0) {
    2.70 +        CX_LL_PTR(node, loc_prev) = NULL;
    2.71 +    }
    2.72 +
    2.73 +    // update begin, if required
    2.74 +    if (*begin == node) {
    2.75 +        *begin = next;
    2.76 +    }
    2.77 +
    2.78 +    // update end, if required
    2.79 +    if (end != NULL && *end == node) {
    2.80 +        *end = prev;
    2.81 +    }
    2.82 +
    2.83 +    return prev == NULL ? next : prev;
    2.84 +}
    2.85 +
    2.86  size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
    2.87 +    assert(loc_next >= 0);
    2.88      size_t size = 0;
    2.89      while (node != NULL) {
    2.90          node = CX_LL_PTR(node, loc_next);
    2.91 @@ -149,6 +207,9 @@
    2.92  void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
    2.93                           ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
    2.94      assert(begin != NULL);
    2.95 +    assert(loc_next >= 0);
    2.96 +    assert(loc_data >= 0);
    2.97 +    assert(cmp_func);
    2.98  
    2.99      void *lc, *ls, *le, *re;
   2.100  
   2.101 @@ -201,6 +262,32 @@
   2.102  #undef ll_next
   2.103  #undef ll_data
   2.104  
   2.105 +void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
   2.106 +    assert(begin != NULL);
   2.107 +    assert(loc_next >= 0);
   2.108 +
   2.109 +    // swap all links
   2.110 +    void *prev = NULL;
   2.111 +    void *cur = *begin;
   2.112 +    while (cur != NULL) {
   2.113 +        void *next = CX_LL_PTR(cur, loc_next);
   2.114 +
   2.115 +        CX_LL_PTR(cur, loc_next) = prev;
   2.116 +        if (loc_prev >= 0) {
   2.117 +            CX_LL_PTR(cur, loc_prev) = next;
   2.118 +        }
   2.119 +
   2.120 +        prev = cur;
   2.121 +        cur = next;
   2.122 +    }
   2.123 +
   2.124 +    // update begin and end
   2.125 +    if (end != NULL) {
   2.126 +        *end = *begin;
   2.127 +    }
   2.128 +    *begin = prev;
   2.129 +}
   2.130 +
   2.131  /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
   2.132  
   2.133  typedef struct cx_linked_list_node cx_linked_list_node;
     3.1 --- a/test/test_list.c	Fri Oct 08 18:58:49 2021 +0200
     3.2 +++ b/test/test_list.c	Fri Oct 08 19:47:31 2021 +0200
     3.3 @@ -128,7 +128,6 @@
     3.4  }
     3.5  
     3.6  void test_linked_list_last(void) {
     3.7 -    CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, -1))
     3.8      CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, 0))
     3.9  
    3.10      struct node {
    3.11 @@ -146,6 +145,97 @@
    3.12      CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third)
    3.13  }
    3.14  
    3.15 +void test_linked_list_prev(void) {
    3.16 +    struct node {
    3.17 +        void *next;
    3.18 +    };
    3.19 +    ptrdiff_t loc = offsetof(struct node, next);
    3.20 +
    3.21 +    struct node third = {NULL};
    3.22 +    struct node second = {&third};
    3.23 +    struct node first = {&second};
    3.24 +
    3.25 +    CU_ASSERT_PTR_NULL(cx_linked_list_prev(&first, loc, &first))
    3.26 +    CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &second), &first)
    3.27 +    CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &third), &second)
    3.28 +}
    3.29 +
    3.30 +void test_linked_list_remove(void) {
    3.31 +    struct node {
    3.32 +        void *next;
    3.33 +    };
    3.34 +    struct dnode {
    3.35 +        void *next;
    3.36 +        void *prev;
    3.37 +    };
    3.38 +    ptrdiff_t loc = offsetof(struct node, next);
    3.39 +    ptrdiff_t ploc = offsetof(struct dnode, prev);
    3.40 +
    3.41 +    void *begin;
    3.42 +    void *end;
    3.43 +    void *result;
    3.44 +
    3.45 +    // single linked list
    3.46 +    struct node third = {NULL};
    3.47 +    struct node second = {&third};
    3.48 +    struct node first = {&second};
    3.49 +    begin = &first;
    3.50 +
    3.51 +    result = cx_linked_list_remove(&begin, NULL, -1, loc, &second);
    3.52 +    CU_ASSERT_PTR_EQUAL(result, &first)
    3.53 +    CU_ASSERT_PTR_EQUAL(begin, &first)
    3.54 +    CU_ASSERT_PTR_EQUAL(first.next, &third)
    3.55 +    CU_ASSERT_PTR_NULL(second.next)
    3.56 +    CU_ASSERT_PTR_NULL(third.next)
    3.57 +
    3.58 +    result = cx_linked_list_remove(&begin, NULL, -1, loc, &first);
    3.59 +    CU_ASSERT_PTR_EQUAL(result, &third)
    3.60 +    CU_ASSERT_PTR_EQUAL(begin, &third)
    3.61 +    CU_ASSERT_PTR_NULL(first.next)
    3.62 +    CU_ASSERT_PTR_NULL(third.next)
    3.63 +
    3.64 +    result = cx_linked_list_remove(&begin, NULL, -1, loc, &third);
    3.65 +    CU_ASSERT_PTR_NULL(result)
    3.66 +    CU_ASSERT_PTR_NULL(begin)
    3.67 +    CU_ASSERT_PTR_NULL(third.next)
    3.68 +
    3.69 +    // doubly linked list
    3.70 +    struct dnode dthird = {NULL , NULL};
    3.71 +    struct dnode dsecond = {&dthird, NULL};
    3.72 +    struct dnode dfirst = {&dsecond, NULL};
    3.73 +    dthird.prev = &dsecond;
    3.74 +    dsecond.prev = &dfirst;
    3.75 +    begin = &dfirst;
    3.76 +    end = &dthird;
    3.77 +
    3.78 +    result = cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
    3.79 +    CU_ASSERT_PTR_EQUAL(result, &dfirst)
    3.80 +    CU_ASSERT_PTR_EQUAL(begin, &dfirst)
    3.81 +    CU_ASSERT_PTR_EQUAL(end, &dthird)
    3.82 +    CU_ASSERT_PTR_NULL(dfirst.prev)
    3.83 +    CU_ASSERT_PTR_EQUAL(dfirst.next, &dthird)
    3.84 +    CU_ASSERT_PTR_NULL(dsecond.prev)
    3.85 +    CU_ASSERT_PTR_NULL(dsecond.next)
    3.86 +    CU_ASSERT_PTR_EQUAL(dthird.prev, &dfirst)
    3.87 +    CU_ASSERT_PTR_NULL(dthird.next)
    3.88 +
    3.89 +    result = cx_linked_list_remove(&begin, &end, ploc, loc, &dthird);
    3.90 +    CU_ASSERT_PTR_EQUAL(result, &dfirst)
    3.91 +    CU_ASSERT_PTR_EQUAL(begin, &dfirst)
    3.92 +    CU_ASSERT_PTR_EQUAL(end, &dfirst)
    3.93 +    CU_ASSERT_PTR_NULL(dfirst.prev)
    3.94 +    CU_ASSERT_PTR_NULL(dfirst.next)
    3.95 +    CU_ASSERT_PTR_NULL(dthird.prev)
    3.96 +    CU_ASSERT_PTR_NULL(dthird.next)
    3.97 +
    3.98 +    result = cx_linked_list_remove(&begin, &end, ploc, loc, &dfirst);
    3.99 +    CU_ASSERT_PTR_NULL(result)
   3.100 +    CU_ASSERT_PTR_NULL(begin)
   3.101 +    CU_ASSERT_PTR_NULL(end)
   3.102 +    CU_ASSERT_PTR_NULL(dfirst.next)
   3.103 +    CU_ASSERT_PTR_NULL(dfirst.prev)
   3.104 +}
   3.105 +
   3.106  void test_linked_list_size(void) {
   3.107      struct node {
   3.108          void *next;
   3.109 @@ -209,7 +299,7 @@
   3.110      CU_ASSERT_EQUAL(begin->data, expected[0])
   3.111      struct node *check = begin;
   3.112      struct node *check_last = NULL;
   3.113 -    for (int i = 0 ; i < 100 ; i++) {
   3.114 +    for (int i = 0; i < 100; i++) {
   3.115          CU_ASSERT_EQUAL(check->data, expected[i])
   3.116          CU_ASSERT_PTR_EQUAL(check->prev, check_last)
   3.117          if (i < 99) {
   3.118 @@ -222,6 +312,51 @@
   3.119      CU_ASSERT_EQUAL(end->data, expected[99])
   3.120  }
   3.121  
   3.122 +void test_linked_list_reverse(void) {
   3.123 +    struct node {
   3.124 +        void *next;
   3.125 +    };
   3.126 +    struct dnode {
   3.127 +        void *next;
   3.128 +        void *prev;
   3.129 +    };
   3.130 +    ptrdiff_t loc = offsetof(struct node, next);
   3.131 +    ptrdiff_t ploc = offsetof(struct dnode, prev);
   3.132 +
   3.133 +    void *begin;
   3.134 +    void *end;
   3.135 +
   3.136 +    // single linked list
   3.137 +    struct node third = {NULL};
   3.138 +    struct node second = {&third};
   3.139 +    struct node first = {&second};
   3.140 +    begin = &first;
   3.141 +
   3.142 +    cx_linked_list_reverse(&begin, NULL, -1, loc);
   3.143 +    CU_ASSERT_PTR_EQUAL(begin, &third)
   3.144 +    CU_ASSERT_PTR_EQUAL(third.next, &second)
   3.145 +    CU_ASSERT_PTR_EQUAL(second.next, &first)
   3.146 +    CU_ASSERT_PTR_NULL(first.next)
   3.147 +
   3.148 +    // doubly linked list
   3.149 +    struct dnode dthird = {NULL , NULL};
   3.150 +    struct dnode dsecond = {&dthird, NULL};
   3.151 +    struct dnode dfirst = {&dsecond, NULL};
   3.152 +    dthird.prev = &dsecond;
   3.153 +    dsecond.prev = &dfirst;
   3.154 +    begin = &dfirst;
   3.155 +    end = &dthird;
   3.156 +
   3.157 +    cx_linked_list_reverse(&begin, &end, ploc, loc);
   3.158 +    CU_ASSERT_PTR_EQUAL(begin, &dthird)
   3.159 +    CU_ASSERT_PTR_EQUAL(end, &dfirst)
   3.160 +    CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond)
   3.161 +    CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst)
   3.162 +    CU_ASSERT_PTR_NULL(dfirst.next)
   3.163 +    CU_ASSERT_PTR_NULL(dthird.prev)
   3.164 +    CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird)
   3.165 +    CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond)
   3.166 +}
   3.167  
   3.168  void test_hl_linked_list_create(void) {
   3.169      cxTestingAllocatorReset();
   3.170 @@ -415,14 +550,14 @@
   3.171  
   3.172      CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
   3.173  
   3.174 -    for (int i = 0 ; i < 100 ; i++) {
   3.175 +    for (int i = 0; i < 100; i++) {
   3.176          cxListAdd(list, &scrambled[i]);
   3.177      }
   3.178  
   3.179      cxListSort(list);
   3.180  
   3.181 -    for (int i = 0 ; i < 100 ; i++) {
   3.182 -        CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i])
   3.183 +    for (int i = 0; i < 100; i++) {
   3.184 +        CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
   3.185      }
   3.186  
   3.187      cxLinkedListDestroy(list);
   3.188 @@ -616,14 +751,14 @@
   3.189  
   3.190      CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
   3.191  
   3.192 -    for (int i = 0 ; i < 100 ; i++) {
   3.193 +    for (int i = 0; i < 100; i++) {
   3.194          cxListAdd(list, &scrambled[i]);
   3.195      }
   3.196  
   3.197      cxListSort(list);
   3.198  
   3.199 -    for (int i = 0 ; i < 100 ; i++) {
   3.200 -        CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i])
   3.201 +    for (int i = 0; i < 100; i++) {
   3.202 +        CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
   3.203      }
   3.204  
   3.205      cxLinkedListDestroy(list);
   3.206 @@ -642,8 +777,11 @@
   3.207      cu_add_test(suite, test_linked_list_at);
   3.208      cu_add_test(suite, test_linked_list_add);
   3.209      cu_add_test(suite, test_linked_list_last);
   3.210 +    cu_add_test(suite, test_linked_list_prev);
   3.211 +    cu_add_test(suite, test_linked_list_remove);
   3.212      cu_add_test(suite, test_linked_list_size);
   3.213      cu_add_test(suite, test_linked_list_sort);
   3.214 +    cu_add_test(suite, test_linked_list_reverse);
   3.215  
   3.216      suite = CU_add_suite("high level linked list", NULL, NULL);
   3.217  

mercurial