Mercurial > hg > ucx / changeset

--- a/src/cx/linked_list.h	Sat Oct 09 11:12:48 2021 +0200
+++ b/src/cx/linked_list.h	Sat Dec 04 17:38:23 2021 +0100
@@ -97,17 +97,30 @@
 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index);
 
 /**
+ * Finds the first node in a linked list.
+ *
+ * The function starts with the pointer denoted by \p node and traverses the list
+ * along a prev pointer whose location within the node struct is
+ * denoted by \p loc_prev.
+ *
+ * @param node a pointer to a node in the list
+ * @param loc_prev the location of the \c prev pointer
+ * @return a pointer to the first node or \c NULL if \p node is \c NULL
+ */
+void *cx_linked_list_first(void *node, ptrdiff_t loc_prev);
+
+/**
  * Finds the last node in a linked list.
  *
- * The function starts with the pointer denoted by \p begin and traverses the list
+ * The function starts with the pointer denoted by \p node and traverses the list
  * along a next pointer whose location within the node struct is
  * denoted by \p loc_next.
  *
- * @param begin a pointer to the begin node
+ * @param node a pointer to a node in the list
  * @param loc_next the location of the \c next pointer
  * @return a pointer to the last node or \c NULL if \p begin is \c NULL
  */
-void *cx_linked_list_last(void *begin, ptrdiff_t loc_next);
+void *cx_linked_list_last(void *node, ptrdiff_t loc_next);
 
 /**
  * Finds the predecessor of a node in case it is not linked.
@@ -123,6 +136,7 @@
 
 /**
  * Adds a new node to a linked list.
+ * The node must not be part of any list already.
  *
  * \remark One of the pointers \p begin and \p end may be \c NULL, but not both.
  *
@@ -135,6 +149,20 @@
 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
 
 /**
+ * Prepends a new node to a linked list.
+ * The node must not be part of any list already.
+ *
+ * \remark One of the pointers \p begin and \p end may be \c NULL, but not both.
+ *
+ * @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 (required)
+ * @param new_node a pointer to the node that shall be prepended
+ */
+void cx_linked_list_prepend(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)

--- a/src/linked_list.c	Sat Oct 09 11:12:48 2021 +0200
+++ b/src/linked_list.c	Sat Dec 04 17:38:23 2021 +0100
@@ -47,12 +47,16 @@
     return cur;
 }
 
-void *cx_linked_list_last(void *begin, ptrdiff_t loc_next) {
+void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) {
+    return cx_linked_list_last(node, loc_prev);
+}
+
+void *cx_linked_list_last(void *node, ptrdiff_t loc_next) {
     assert(loc_next >= 0);
-    if (begin == NULL)
+    if (node == NULL)
         return NULL;
 
-    void *cur = begin;
+    void *cur = node;
     void *last;
     do {
         last = cur;
@@ -76,6 +80,7 @@
 
 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
     assert(loc_next >= 0);
+    assert(CX_LL_PTR(new_node, loc_next) == NULL);
     void *last;
     if (end == NULL) {
         assert(begin != NULL);
@@ -84,8 +89,9 @@
         last = *end;
     }
     if (last == NULL) {
-        assert(begin != NULL);
-        *begin = new_node;
+        if (begin != NULL) {
+            *begin = new_node;
+        }
     } else {
         // if there is a last node, update its next pointer
         CX_LL_PTR(last, loc_next) = new_node;
@@ -93,15 +99,44 @@
 
     // if there is an end pointer, update it
     if (end != NULL) {
-        *end = cx_linked_list_last(new_node, loc_next);
+        *end = new_node;
     }
 
     // if the nodes use a prev pointer, update it
     if (loc_prev >= 0) {
+        assert(CX_LL_PTR(new_node, loc_prev) == NULL);
         CX_LL_PTR(new_node, loc_prev) = last;
     }
 }
 
+void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
+    assert(loc_next >= 0);
+    assert(CX_LL_PTR(new_node, loc_next) == NULL);
+    void *first;
+    if (begin == NULL) {
+        assert(end != NULL);
+        assert(loc_prev >= 0);
+        first = cx_linked_list_first(*end, loc_prev);
+    } else {
+        first = *begin;
+    }
+    if (first == NULL) {
+        if (end != NULL) {
+            *end = new_node;
+        }
+    } else {
+        CX_LL_PTR(new_node, loc_next) = first;
+        if (loc_prev >= 0) {
+            CX_LL_PTR(first, loc_prev) = new_node;
+        }
+    }
+
+    if (begin != NULL) {
+        assert(loc_prev < 0 || CX_LL_PTR(new_node, loc_prev) == NULL);
+        *begin = new_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);

--- a/test/test_list.c	Sat Oct 09 11:12:48 2021 +0200
+++ b/test/test_list.c	Sat Dec 04 17:38:23 2021 +0100
@@ -88,8 +88,8 @@
     cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
-    CU_ASSERT_PTR_EQUAL(nodes[0].prev, NULL)
-    CU_ASSERT_PTR_EQUAL(nodes[0].next, NULL)
+    CU_ASSERT_PTR_NULL(nodes[0].prev)
+    CU_ASSERT_PTR_NULL(nodes[0].next)
 
     cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
@@ -113,6 +113,23 @@
     CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
     CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
 
+    // test with end only / prev, next
+    memset(nodes, 0, 4 * sizeof(struct node));
+    begin = NULL;
+    end = NULL;
+
+    cx_linked_list_add(NULL, &end, loc_prev, loc_next, &nodes[0]);
+    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
+    cx_linked_list_add(NULL, &end,  loc_prev, loc_next, &nodes[1]);
+    CU_ASSERT_PTR_EQUAL(end, &nodes[1])
+    CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
+    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
+
+    cx_linked_list_add(NULL, &end,  loc_prev, loc_next, &nodes[2]);
+    CU_ASSERT_PTR_EQUAL(end, &nodes[2])
+    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
+    CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
+
     // test with begin, end / next
     memset(nodes, 0, 4 * sizeof(struct node));
     begin = NULL;
@@ -127,6 +144,104 @@
     CU_ASSERT_PTR_NULL(nodes[1].prev)
 }
 
+void test_linked_list_prepend(void) {
+    struct node {
+        void *prev;
+        void *next;
+    };
+
+    struct node nodes[4];
+
+    // test with begin, end / prev, next
+    memset(nodes, 0, 4 * sizeof(struct node));
+    void *begin = NULL;
+    void *end = NULL;
+
+    ptrdiff_t loc_prev = offsetof(struct node, prev);
+    ptrdiff_t loc_next = offsetof(struct node, next);
+
+    cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[0]);
+    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
+    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
+    CU_ASSERT_PTR_NULL(nodes[0].prev)
+    CU_ASSERT_PTR_NULL(nodes[0].next)
+
+    cx_linked_list_prepend(&begin, &end, loc_prev, loc_next, &nodes[1]);
+    CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
+    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
+    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
+    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
+
+    // test with begin only / prev, next
+    memset(nodes, 0, 4 * sizeof(struct node));
+    begin = NULL;
+    end = NULL;
+
+    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[0]);
+    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
+    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[1]);
+    CU_ASSERT_PTR_EQUAL(begin, &nodes[1])
+    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
+    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
+
+    cx_linked_list_prepend(&begin, NULL, loc_prev, loc_next, &nodes[2]);
+    CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
+    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
+    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
+
+    // test with end only / prev, next
+    memset(nodes, 0, 4 * sizeof(struct node));
+    begin = NULL;
+    end = NULL;
+
+    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[0]);
+    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
+    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[1]);
+    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
+    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
+    CU_ASSERT_PTR_EQUAL(nodes[0].prev, &nodes[1])
+
+    cx_linked_list_prepend(NULL, &end, loc_prev, loc_next, &nodes[2]);
+    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
+    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
+    CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[2])
+
+    // test with begin, end / next
+    memset(nodes, 0, 4 * sizeof(struct node));
+    begin = NULL;
+    end = NULL;
+
+    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[0]);
+    CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
+    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
+    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[1]);
+    cx_linked_list_prepend(&begin, &end, -1, loc_next, &nodes[2]);
+    CU_ASSERT_PTR_EQUAL(begin, &nodes[2])
+    CU_ASSERT_PTR_EQUAL(end, &nodes[0])
+    CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[0])
+    CU_ASSERT_PTR_EQUAL(nodes[2].next, &nodes[1])
+    CU_ASSERT_PTR_NULL(nodes[1].prev)
+    CU_ASSERT_PTR_NULL(nodes[0].prev)
+}
+
+void test_linked_list_first(void) {
+    CU_ASSERT_PTR_NULL(cx_linked_list_first(NULL, 0))
+
+    struct node {
+        int data;
+        void *prev;
+    };
+    ptrdiff_t loc = offsetof(struct node, prev);
+
+    struct node first = {1, NULL};
+    struct node second = {2, &first};
+    struct node third = {3, &second};
+
+    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&first, loc), &first)
+    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&second, loc), &first)
+    CU_ASSERT_PTR_EQUAL(cx_linked_list_first(&third, loc), &first)
+}
+
 void test_linked_list_last(void) {
     CU_ASSERT_PTR_NULL(cx_linked_list_last(NULL, 0))
 
@@ -738,7 +853,9 @@
     suite = CU_add_suite("low level linked list", NULL, NULL);
 
     cu_add_test(suite, test_linked_list_at);
+    cu_add_test(suite, test_linked_list_prepend);
     cu_add_test(suite, test_linked_list_add);
+    cu_add_test(suite, test_linked_list_first);
     cu_add_test(suite, test_linked_list_last);
     cu_add_test(suite, test_linked_list_prev);
     cu_add_test(suite, test_linked_list_remove);