Mercurial > hg > ucx / changeset

--- a/src/cx/linked_list.h	Fri Oct 08 18:58:49 2021 +0200
+++ b/src/cx/linked_list.h	Fri Oct 08 19:47:31 2021 +0200
@@ -110,6 +110,18 @@
 void *cx_linked_list_last(void *begin, ptrdiff_t loc_next);
 
 /**
+ * Finds the predecessor of a node in case it is not linked.
+ *
+ * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined.
+ *
+ * @param begin the node where to start the search
+ * @param loc_next the location of the \c next pointer
+ * @param node the successor of the node to find
+ * @return the node or \c NULL if \p node has no predecessor
+ */
+void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node);
+
+/**
  * Adds a new node to a linked list.
  *
  * \remark One of the pointers \p begin and \p end may be \c NULL, but not both.
@@ -117,12 +129,38 @@
  * @param begin a pointer to the begin node pointer (if your list has one)
  * @param end a pointer to the end node pointer (if your list has one)
  * @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 (negative if your struct does not have one)
+ * @param loc_next the location of a \c next pointer within your node struct (required)
  * @param new_node a pointer to the node that shall be appended
  */
 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
 
 /**
+ * Removes a node from the linked list.
+ *
+ * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
+ * addresses are provided, the pointers are adjusted accordingly.
+ *
+ * The following combinations of arguments are valid (more arguments are optional):
+ * \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.
+ *
+ * @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);
+
+
+/**
  * Determines the size of a linked list starting with \p node.
  * @param node the first node
  * @param loc_next the location of the \c next pointer within the node struct
@@ -162,6 +200,17 @@
 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);
 
+
+/**
+ * Reverses the order of the nodes in a linked list.
+ *
+ * @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 your struct does not have one)
+ * @param loc_next the location of a \c next pointer within your node struct (required)
+ */
+void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next);
+
 #ifdef __cplusplus
 } /* extern "C" */
 #endif

--- a/src/linked_list.c	Fri Oct 08 18:58:49 2021 +0200
+++ b/src/linked_list.c	Fri Oct 08 19:47:31 2021 +0200
@@ -36,6 +36,8 @@
 #define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
 
 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
+    assert(start != NULL);
+    assert(loc_advance >= 0);
     size_t i = start_index;
     void *cur = start;
     while (i != index && cur != NULL) {
@@ -46,6 +48,7 @@
 }
 
 void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) {
+    assert(loc_next >= 0);
     if (begin == NULL)
         return NULL;
 
@@ -58,7 +61,21 @@
     return last;
 }
 
+void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) {
+    assert(begin != NULL);
+    assert(loc_next >= 0);
+    if (begin == node) return NULL;
+    void *cur = begin;
+    void *next;
+    while (1) {
+        next = CX_LL_PTR(cur, loc_next);
+        if (next == node) return cur;
+        cur = next;
+    }
+}
+
 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
+    assert(loc_next >= 0);
     void *last;
     if (end == NULL) {
         assert(begin != NULL);
@@ -85,7 +102,48 @@
     }
 }
 
+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);
+
+    // find adjacent nodes
+    void *next = CX_LL_PTR(node, loc_next);
+    void *prev;
+    if (loc_prev >= 0) {
+        prev = CX_LL_PTR(node, loc_prev);
+    } else {
+        prev = cx_linked_list_prev(*begin, loc_next, node);
+    }
+
+    // update links of adjacent nodes
+    if (prev != NULL) {
+        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 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) {
+    assert(loc_next >= 0);
     size_t size = 0;
     while (node != NULL) {
         node = CX_LL_PTR(node, loc_next);
@@ -149,6 +207,9 @@
 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) {
     assert(begin != NULL);
+    assert(loc_next >= 0);
+    assert(loc_data >= 0);
+    assert(cmp_func);
 
     void *lc, *ls, *le, *re;
 
@@ -201,6 +262,32 @@
 #undef ll_next
 #undef ll_data
 
+void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) {
+    assert(begin != NULL);
+    assert(loc_next >= 0);
+
+    // swap all links
+    void *prev = NULL;
+    void *cur = *begin;
+    while (cur != NULL) {
+        void *next = CX_LL_PTR(cur, loc_next);
+
+        CX_LL_PTR(cur, loc_next) = prev;
+        if (loc_prev >= 0) {
+            CX_LL_PTR(cur, loc_prev) = next;
+        }
+
+        prev = cur;
+        cur = next;
+    }
+
+    // update begin and end
+    if (end != NULL) {
+        *end = *begin;
+    }
+    *begin = prev;
+}
+
 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
 
 typedef struct cx_linked_list_node cx_linked_list_node;

--- a/test/test_list.c	Fri Oct 08 18:58:49 2021 +0200
+++ b/test/test_list.c	Fri Oct 08 19:47:31 2021 +0200
@@ -128,7 +128,6 @@
 }
 
 void test_linked_list_last(void) {
-    CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, -1))
     CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, 0))
 
     struct node {
@@ -146,6 +145,97 @@
     CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third)
 }
 
+void test_linked_list_prev(void) {
+    struct node {
+        void *next;
+    };
+    ptrdiff_t loc = offsetof(struct node, next);
+
+    struct node third = {NULL};
+    struct node second = {&third};
+    struct node first = {&second};
+
+    CU_ASSERT_PTR_NULL(cx_linked_list_prev(&first, loc, &first))
+    CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &second), &first)
+    CU_ASSERT_PTR_EQUAL(cx_linked_list_prev(&first, loc, &third), &second)
+}
+
+void test_linked_list_remove(void) {
+    struct node {
+        void *next;
+    };
+    struct dnode {
+        void *next;
+        void *prev;
+    };
+    ptrdiff_t loc = offsetof(struct node, next);
+    ptrdiff_t ploc = offsetof(struct dnode, prev);
+
+    void *begin;
+    void *end;
+    void *result;
+
+    // single linked list
+    struct node third = {NULL};
+    struct node second = {&third};
+    struct node first = {&second};
+    begin = &first;
+
+    result = cx_linked_list_remove(&begin, NULL, -1, loc, &second);
+    CU_ASSERT_PTR_EQUAL(result, &first)
+    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)
+    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)
+    CU_ASSERT_PTR_NULL(begin)
+    CU_ASSERT_PTR_NULL(third.next)
+
+    // doubly linked list
+    struct dnode dthird = {NULL , NULL};
+    struct dnode dsecond = {&dthird, NULL};
+    struct dnode dfirst = {&dsecond, NULL};
+    dthird.prev = &dsecond;
+    dsecond.prev = &dfirst;
+    begin = &dfirst;
+    end = &dthird;
+
+    result = cx_linked_list_remove(&begin, &end, ploc, loc, &dsecond);
+    CU_ASSERT_PTR_EQUAL(result, &dfirst)
+    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)
+    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)
+    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) {
     struct node {
         void *next;
@@ -209,7 +299,7 @@
     CU_ASSERT_EQUAL(begin->data, expected[0])
     struct node *check = begin;
     struct node *check_last = NULL;
-    for (int i = 0 ; i < 100 ; i++) {
+    for (int i = 0; i < 100; i++) {
         CU_ASSERT_EQUAL(check->data, expected[i])
         CU_ASSERT_PTR_EQUAL(check->prev, check_last)
         if (i < 99) {
@@ -222,6 +312,51 @@
     CU_ASSERT_EQUAL(end->data, expected[99])
 }
 
+void test_linked_list_reverse(void) {
+    struct node {
+        void *next;
+    };
+    struct dnode {
+        void *next;
+        void *prev;
+    };
+    ptrdiff_t loc = offsetof(struct node, next);
+    ptrdiff_t ploc = offsetof(struct dnode, prev);
+
+    void *begin;
+    void *end;
+
+    // single linked list
+    struct node third = {NULL};
+    struct node second = {&third};
+    struct node first = {&second};
+    begin = &first;
+
+    cx_linked_list_reverse(&begin, NULL, -1, loc);
+    CU_ASSERT_PTR_EQUAL(begin, &third)
+    CU_ASSERT_PTR_EQUAL(third.next, &second)
+    CU_ASSERT_PTR_EQUAL(second.next, &first)
+    CU_ASSERT_PTR_NULL(first.next)
+
+    // doubly linked list
+    struct dnode dthird = {NULL , NULL};
+    struct dnode dsecond = {&dthird, NULL};
+    struct dnode dfirst = {&dsecond, NULL};
+    dthird.prev = &dsecond;
+    dsecond.prev = &dfirst;
+    begin = &dfirst;
+    end = &dthird;
+
+    cx_linked_list_reverse(&begin, &end, ploc, loc);
+    CU_ASSERT_PTR_EQUAL(begin, &dthird)
+    CU_ASSERT_PTR_EQUAL(end, &dfirst)
+    CU_ASSERT_PTR_EQUAL(dthird.next, &dsecond)
+    CU_ASSERT_PTR_EQUAL(dsecond.next, &dfirst)
+    CU_ASSERT_PTR_NULL(dfirst.next)
+    CU_ASSERT_PTR_NULL(dthird.prev)
+    CU_ASSERT_PTR_EQUAL(dsecond.prev, &dthird)
+    CU_ASSERT_PTR_EQUAL(dfirst.prev, &dsecond)
+}
 
 void test_hl_linked_list_create(void) {
     cxTestingAllocatorReset();
@@ -415,14 +550,14 @@
 
     CxList list = cxLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int, sizeof(int));
 
-    for (int i = 0 ; i < 100 ; i++) {
+    for (int i = 0; i < 100; i++) {
         cxListAdd(list, &scrambled[i]);
     }
 
     cxListSort(list);
 
-    for (int i = 0 ; i < 100 ; i++) {
-        CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i])
+    for (int i = 0; i < 100; i++) {
+        CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
     }
 
     cxLinkedListDestroy(list);
@@ -616,14 +751,14 @@
 
     CxList list = cxPointerLinkedListCreate(cxTestingAllocator, (CxListComparator) cmp_int);
 
-    for (int i = 0 ; i < 100 ; i++) {
+    for (int i = 0; i < 100; i++) {
         cxListAdd(list, &scrambled[i]);
     }
 
     cxListSort(list);
 
-    for (int i = 0 ; i < 100 ; i++) {
-        CU_ASSERT_EQUAL(*(int*)cxListAt(list, i), expected[i])
+    for (int i = 0; i < 100; i++) {
+        CU_ASSERT_EQUAL(*(int *) cxListAt(list, i), expected[i])
     }
 
     cxLinkedListDestroy(list);
@@ -642,8 +777,11 @@
     cu_add_test(suite, test_linked_list_at);
     cu_add_test(suite, test_linked_list_add);
     cu_add_test(suite, test_linked_list_last);
+    cu_add_test(suite, test_linked_list_prev);
+    cu_add_test(suite, test_linked_list_remove);
     cu_add_test(suite, test_linked_list_size);
     cu_add_test(suite, test_linked_list_sort);
+    cu_add_test(suite, test_linked_list_reverse);
 
     suite = CU_add_suite("high level linked list", NULL, NULL);