Mercurial > hg > ucx / changeset

--- a/src/cx/linked_list.h	Sun Oct 03 13:07:48 2021 +0200
+++ b/src/cx/linked_list.h	Sun Oct 03 14:06:57 2021 +0200
@@ -25,6 +25,15 @@
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */
+/**
+ * \file linked_list.h
+ * \brief Linked list implementation.
+ * \details Also provides several low-level functions for custom linked list implementations.
+ * \author Mike Becker
+ * \author Olaf Wintermann
+ * \version 3.0
+ * \copyright 2-Clause BSD License
+ */
 
 #ifndef UCX_LINKED_LIST_H
 #define UCX_LINKED_LIST_H
@@ -36,6 +45,13 @@
 extern "C" {
 #endif
 
+CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size);
+
+void cxLinkedListDestroy(CxList list);
+
+size_t cxLinkedListRecalculateSize(CxList list);
+
+
 /**
  * Finds the node at a certain index.
  *
@@ -55,17 +71,35 @@
  */
 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index);
 
+/**
+ * Finds the last node in a linked list.
+ *
+ * If a pointer to \p end is provided, the result is just \c *end.
+ * Otherwise, this function starts with the pointer denoted by \c *begin and
+ * traverses the list along a next pointer whose location within the node struct is
+ * denoted by \p loc_next.
+ *
+ * If both \p begin and \p end are \c NULL, an empty list is assumed and this function returns \c NULL.
+ *
+ * @param begin a pointer to the begin node pointer (optional)
+ * @param end a pointer to the end node pointer (optional)
+ * @param loc_next the location of the \c next pointer (only required when \p end is \c NULL)
+ * @return a pointer to the last node or \c NULL if the list is empty
+ */
 void *cx_linked_list_last(void **begin, void **end, ptrdiff_t loc_next);
 
-int cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
-
-extern cx_list_class cx_linked_list_class;
-
-CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size);
-
-void cxLinkedListDestroy(CxList list);
-
-size_t cxLinkedListRecalculateSize(CxList list);
+/**
+ * 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.
+ *
+ * @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 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);
 
 #ifdef __cplusplus
 } /* extern "C" */

--- a/src/cx/list.h	Sun Oct 03 13:07:48 2021 +0200
+++ b/src/cx/list.h	Sun Oct 03 14:06:57 2021 +0200
@@ -25,6 +25,14 @@
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */
+/**
+ * \file list.h
+ * \brief Interface for list implementations.
+ * \author Mike Becker
+ * \author Olaf Wintermann
+ * \version 3.0
+ * \copyright 2-Clause BSD License
+ */
 
 #ifndef UCX_LIST_H
 #define UCX_LIST_H

--- a/src/cx/tree.h	Sun Oct 03 13:07:48 2021 +0200
+++ b/src/cx/tree.h	Sun Oct 03 14:06:57 2021 +0200
@@ -25,6 +25,14 @@
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */
+/**
+ * \file tree.h
+ * \brief Interface for tree implementations.
+ * \author Olaf Wintermann
+ * \author Mike Becker
+ * \version 3.0
+ * \copyright 2-Clause BSD License
+ */
 
 #ifndef UCX_TREE_H
 #define UCX_TREE_H
@@ -36,23 +44,93 @@
 #ifdef __cplusplus
 extern "C" {
 #endif
- 
-void* cx_tree_last(void *node, ptrdiff_t loc_next);
-    
-int cx_tree_add_node(void *node, ptrdiff_t loc_parent, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
+
+/**
+ * Adds a sibling to the current tree node.
+ *
+ * In case your struct does not have a \p prev or a \p parent pointer,
+ * specify a negative location. The location of the \p next pointer is
+ * mandatory.
+ *
+ * \attention Do not use this function to add siblings in a tree where the
+ * nodes store a pointer to the last sibling because that would not be modified by this function.
+ *
+ * \remark If yo do not provide a location to the parent pointer, a call to this function is
+ * effectively the same as a call to cx_linked_list_add().
+ *
+ * @param node a pointer to the node
+ * @param loc_prev the location of a \c prev pointer within your node struct
+ * @param loc_next the location of a \c next pointer within your node struct
+ * @param loc_parent the location of a \c parent pointer within your node struct
+ * @param new_node the new node that shall be added as a sibling
+ */
+void cx_tree_add_sibling(void *node,
+                         ptrdiff_t loc_prev, ptrdiff_t loc_next,
+                         ptrdiff_t loc_parent,
+                         void *new_node)
+__attribute__((__nonnull__));
 
-int cx_tree_add_child_node(
-        void *parent,
-        ptrdiff_t loc_parent,
-        ptrdiff_t loc_prev,
-        ptrdiff_t loc_next,
-        void **children_begin,
-        void **children_end,
-        void *new_node);
+/**
+ * Adds a node to the list of children.
+ *
+ * \par Example with a full structure
+ * A full tree node structure may look like this:
+ * \code
+ * typedef struct MyTreeNode MyTreeNode;
+ * struct MyTreeNode {
+ *   MyTreeNode* parent;
+ *   MyTreeNode* first_child;
+ *   MyTreeNode* last_child;
+ *   MyTreeNode* prev_sibling;
+ *   MyTreeNode* next_sibling;
+ *   // ...contents...
+ * }
+ * \endcode
+ * Adding a new child to a node with the above structure can be performed with the following call:
+ * \code
+ * MyTreeNode *node, *child; // given
+ * cx_tree_add_child(&node->first_child, &node->last_child,
+ *                   offsetof(MyTreeNode, prev_sibling), offsetof(MyTreeNode, next_sibling),
+ *                   child, offsetof(MyTreeNode, parent), node);
+ * \endcode
+ *
+ * \par Example with a reduced structure
+ * The minimal reasonable structure with parent pointer looks like this:
+ * \code
+ * typedef struct MyTreeNode MyTreeNode;
+ * struct MyTreeNode {
+ *   MyTreeNode* parent;
+ *   MyTreeNode* children;
+ *   MyTreeNode* next_sibling;
+ *   // ...contents...
+ * }
+ * \endcode
+ * This simplifies the function call to:
+ * \code
+ * MyTreeNode *node, *child; // given
+ * cx_tree_add_child(&node->children, NULL, -1, offsetof(MyTreeNode, next_sibling),
+ *                   child, offsetof(MyTreeNode, parent), node);
+ * \endcode
+ *
+ * \remark If your tree structure does not possess a parent pointer, a call to this function is
+ * effectively the same as a call to cx_linked_list_add().
+ *
+ * @param children_begin a pointer to the begin node pointer (if your list has one)
+ * @param children_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
+ * @param loc_next the location of a \c next pointer within your node struct
+ * @param new_node a pointer to the node that shall be appended
+ * @param loc_parent the location of a \c parent pointer within your node struct
+ * @param parent the parent node
+ */
+void cx_tree_add_child(void **children_begin, void **children_end,
+                       ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node,
+                       ptrdiff_t loc_parent, void *parent)
+__attribute__((__nonnull__ (5)));
 
 
 #ifdef __cplusplus
-}
+} /* extern "C" */
 #endif
 
 #endif /* UCX_TREE_H */

--- a/src/linked_list.c	Sun Oct 03 13:07:48 2021 +0200
+++ b/src/linked_list.c	Sun Oct 03 14:06:57 2021 +0200
@@ -29,6 +29,7 @@
 #include "cx/linked_list.h"
 #include <stdint.h>
 #include <string.h>
+#include <assert.h>
 
 /* LOW LEVEL LINKED LIST FUNCTIONS */
 
@@ -61,16 +62,11 @@
     }
 }
 
-int cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
+void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
     void *last = cx_linked_list_last(begin, end, loc_next);
     if (last == NULL) {
-        if (begin == NULL) {
-            // no current list and no begin ptr to write to - we don't find something to append to
-            return 1;
-        } else {
-            // start fresh list
-            *begin = new_node;
-        }
+        assert(begin != NULL);
+        *begin = new_node;
     } else {
         // if there is a last node, update its next pointer
         void **next = CX_LL_PTR(last, loc_next);
@@ -87,8 +83,6 @@
         void **prev = CX_LL_PTR(new_node, loc_prev);
         *prev = last;
     }
-
-    return 0;
 }
 
 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */

--- a/src/tree.c	Sun Oct 03 13:07:48 2021 +0200
+++ b/src/tree.c	Sun Oct 03 14:06:57 2021 +0200
@@ -31,7 +31,7 @@
 
 #define CX_TR_PTR(cur, off) ((void**)(((char*)cur)+off))
 
-void* cx_tree_last(void *node, ptrdiff_t loc_next) {
+void *cx_tree_last(void *node, ptrdiff_t loc_next) {
     void *last;
     do {
         last = node;
@@ -39,40 +39,22 @@
     return last;
 }
 
-int cx_tree_add_node(void *node, ptrdiff_t loc_parent, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) {
-    void *last = cx_tree_last(node, loc_next);
-    if(!last)
-        return 1;
-    
-    // next pointer must be present
-    *CX_TR_PTR(last, loc_next) = new_node;
-    
-    // optional fields
-    if(loc_parent >= 0) {
+void cx_tree_add_sibling(void *node, ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_parent, void *new_node) {
+    cx_linked_list_add(&node, NULL, loc_prev, loc_next, new_node);
+
+    // optional parent link
+    if (loc_parent >= 0) {
         *CX_TR_PTR(new_node, loc_parent) = *CX_TR_PTR(node, loc_parent);
     }
-    if(loc_prev >= 0) {
-        *CX_TR_PTR(new_node, loc_prev) = last;
-    }
-    
-    return 0;
 }
 
-int cx_tree_add_child_node(
-        void *parent,
-        ptrdiff_t loc_parent,
-        ptrdiff_t loc_prev,
-        ptrdiff_t loc_next,
-        void **children_begin,
-        void **children_end,
-        void *new_node)
-{
-    if(cx_linked_list_add(children_begin, children_end, loc_prev, loc_next, new_node)) {
-        return 1;
-    }
-    // optional field
-    if(loc_parent >= 0) {
+void cx_tree_add_child(void **children_begin, void **children_end,
+                  ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node,
+                  ptrdiff_t loc_parent, void *parent) {
+    cx_linked_list_add(children_begin, children_end, loc_prev, loc_next, new_node);
+
+    // optional parent link
+    if (loc_parent >= 0) {
         *CX_TR_PTR(new_node, loc_parent) = parent;
     }
-    return 0;
 }

--- a/test/test_list.c	Sun Oct 03 13:07:48 2021 +0200
+++ b/test/test_list.c	Sun Oct 03 14:06:57 2021 +0200
@@ -112,16 +112,13 @@
     ptrdiff_t loc_prev = offsetof(struct node, prev);
     ptrdiff_t loc_next = offsetof(struct node, next);
 
-    int ret;
-    ret = cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[0]);
-    CU_ASSERT_EQUAL(ret, 0)
+    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)
 
-    ret = cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
-    CU_ASSERT_EQUAL(ret, 0)
+    cx_linked_list_add(&begin, &end, loc_prev, loc_next, &nodes[1]);
     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
     CU_ASSERT_PTR_EQUAL(end, &nodes[1])
     CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
@@ -132,16 +129,14 @@
     begin = NULL;
     end = NULL;
 
-    ret = cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
-    CU_ASSERT_EQUAL(ret, 0)
+    cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[0]);
     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
-    ret = cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
-    CU_ASSERT_EQUAL(ret, 0)
+    cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[1]);
     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
     CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
     CU_ASSERT_PTR_EQUAL(nodes[1].prev, &nodes[0])
 
-    ret = cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
+    cx_linked_list_add(&begin, NULL, loc_prev, loc_next, &nodes[2]);
     CU_ASSERT_PTR_EQUAL(nodes[1].next, &nodes[2])
     CU_ASSERT_PTR_EQUAL(nodes[2].prev, &nodes[1])
 
@@ -150,12 +145,10 @@
     begin = NULL;
     end = NULL;
 
-    ret = cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
-    CU_ASSERT_EQUAL(ret, 0)
+    cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[0]);
     CU_ASSERT_PTR_EQUAL(begin, &nodes[0])
     CU_ASSERT_PTR_EQUAL(end, &nodes[0])
-    ret = cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
-    CU_ASSERT_EQUAL(ret, 0)
+    cx_linked_list_add(&begin, &end, -1, loc_next, &nodes[1]);
     CU_ASSERT_PTR_EQUAL(end, &nodes[1])
     CU_ASSERT_PTR_EQUAL(nodes[0].next, &nodes[1])
     CU_ASSERT_PTR_NULL(nodes[1].prev)

--- a/test/test_tree.c	Sun Oct 03 13:07:48 2021 +0200
+++ b/test/test_tree.c	Sun Oct 03 14:06:57 2021 +0200
@@ -60,15 +60,13 @@
     memset(&c, 0, sizeof(TestNode));
     
     // test
-    int ret = cx_tree_add_node(&a, offsetof(TestNode, parent), offsetof(TestNode, prev), offsetof(TestNode, next), &b);
-    CU_ASSERT_EQUAL(ret, 0)
+    cx_tree_add_sibling(&a, offsetof(TestNode, prev), offsetof(TestNode, next), offsetof(TestNode, parent), &b);
     CU_ASSERT_PTR_EQUAL(b.parent, &root)
     CU_ASSERT_PTR_EQUAL(b.prev, &a)
     CU_ASSERT_PTR_NULL(b.next)
     CU_ASSERT_PTR_EQUAL(a.next, &b)
-    
-    ret = cx_tree_add_node(&a, -1, -1, offsetof(TestNode, next), &c);
-    CU_ASSERT_EQUAL(ret, 0)
+
+    cx_tree_add_sibling(&a, -1, offsetof(TestNode, next), -1, &c);
     CU_ASSERT_PTR_NULL(c.parent)
     CU_ASSERT_PTR_NULL(c.prev)
     CU_ASSERT_PTR_NULL(c.next)
@@ -89,63 +87,57 @@
     TestNode a1;
     memset(&a1, 0, sizeof(TestNode));
     
-    int ret;
-    
     // test
-    ret = cx_tree_add_child_node(
-            &root,
-            offsetof(TestNode, parent),
+    cx_tree_add_child(
+            (void **) &root.children_begin,
+            (void **) &root.children_end,
             offsetof(TestNode, prev),
             offsetof(TestNode, next),
-            (void**)&root.children_begin,
-            (void**)&root.children_end,
-            &a);
-    CU_ASSERT_EQUAL(ret, 0)
+            &a,
+            offsetof(TestNode, parent),
+            &root);
     CU_ASSERT_PTR_EQUAL(root.children_begin, &a)
     CU_ASSERT_PTR_EQUAL(root.children_end, &a)
     CU_ASSERT_PTR_EQUAL(a.parent, &root)
     CU_ASSERT_PTR_NULL(a.prev)
     CU_ASSERT_PTR_NULL(a.next)
 
-    ret = cx_tree_add_child_node(
-            &root,
-            offsetof(TestNode, parent),
+    cx_tree_add_child(
+            (void **) &root.children_begin,
+            (void **) &root.children_end,
             offsetof(TestNode, prev),
             offsetof(TestNode, next),
-            (void**)&root.children_begin,
-            (void**)&root.children_end,
-            &b);
-    CU_ASSERT_EQUAL(ret, 0)
+            &b,
+            offsetof(TestNode, parent),
+            &root);
     CU_ASSERT_PTR_NOT_NULL(root.children_begin)
     CU_ASSERT_PTR_EQUAL(root.children_begin->next, &b)
     CU_ASSERT_PTR_EQUAL(root.children_end, &b)
     CU_ASSERT_PTR_EQUAL(b.parent, &root)
     CU_ASSERT_PTR_EQUAL(b.prev, &a)
-    
-    ret = cx_tree_add_child_node(
-            &root,
-            -1,
+
+    cx_tree_add_child(
+            (void **) &root.children_begin,
+            NULL,
             -1,
             offsetof(TestNode, next),
-            (void**)&root.children_begin,
-            NULL,
-            &c);
-    CU_ASSERT_EQUAL(ret, 0)
+            &c,
+            -1,
+            &root);
     CU_ASSERT_PTR_EQUAL(root.children_end, &b) // children_end unchanged
     CU_ASSERT_PTR_EQUAL(b.next, &c)
     CU_ASSERT_PTR_NULL(c.prev)
     CU_ASSERT_PTR_NULL(c.next)
     CU_ASSERT_PTR_NULL(c.parent)
-    
-    ret = cx_tree_add_child_node(
-            &a,
-            offsetof(TestNode, parent),
+
+    cx_tree_add_child(
+            (void **) &a.children_begin,
+            (void **) &a.children_end,
             offsetof(TestNode, prev),
             offsetof(TestNode, next),
-            (void**)&a.children_begin,
-            (void**)&a.children_end,
-            &a1);
-    CU_ASSERT_EQUAL(ret, 0);
+            &a1,
+            offsetof(TestNode, parent),
+            &a);
     CU_ASSERT_PTR_EQUAL(a.children_begin, &a1);
     CU_ASSERT_PTR_EQUAL(a1.parent, &a);
     CU_ASSERT_PTR_NOT_NULL(root.children_begin)