--- a/ucx/cx/linked_list.h Sat Oct 04 14:54:25 2025 +0200
+++ b/ucx/cx/linked_list.h Sun Oct 19 21:20:08 2025 +0200
@@ -44,11 +44,43 @@
#endif
/**
+ * Metadata for a linked list.
+ */
+typedef struct cx_linked_list_s {
+ /** Base members. */
+ struct cx_list_s base;
+ /**
+ * Location of the prev pointer (mandatory).
+ */
+ off_t loc_prev;
+ /**
+ * Location of the next pointer (mandatory).
+ */
+ off_t loc_next;
+ /**
+ * Location of the payload (mandatory).
+ */
+ off_t loc_data;
+ /**
+ * Additional bytes to allocate @em behind the payload (e.g. for metadata).
+ */
+ size_t extra_data_len;
+ /**
+ * Pointer to the first node.
+ */
+ void *begin;
+ /**
+ * Pointer to the last node.
+ */
+ void *end;
+} cx_linked_list;
+
+/**
* Allocates a linked list for storing elements with @p elem_size bytes each.
*
* If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
- * copies of the added elements and the compare function will be automatically set
- * to cx_cmp_ptr(), if none is given.
+ * copies of the added elements, and the compare function will be automatically set
+ * to cx_cmp_ptr() if none is given.
*
* @param allocator the allocator for allocating the list nodes
* (if @c NULL, the cxDefaultAllocator will be used)
@@ -76,7 +108,7 @@
* after list creation or use cxLinkedListCreate().
*
* If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
- * copies of the added elements and the compare function will be automatically set
+ * copies of the added elements, and the compare function will be automatically set
* to cx_cmp_ptr().
*
* @param elem_size (@c size_t) the size of each element in bytes
@@ -89,12 +121,12 @@
* Finds the node at a certain index.
*
* This function can be used to start at an arbitrary position within the list.
- * If the search index is large than the start index, @p loc_advance must denote
- * the location of some sort of @c next pointer (i.e. a pointer to the next node).
+ * If the search index is larger than the start index, @p loc_advance must denote
+ * the location of a @c next pointer (i.e., a pointer to the next node).
* But it is also possible that the search index is smaller than the start index
- * (e.g. in cases where traversing a list backwards is faster) in which case
- * @p loc_advance must denote the location of some sort of @c prev pointer
- * (i.e. a pointer to the previous node).
+ * (e.g., in cases where traversing a list backwards is faster).
+ * In that case @p loc_advance must denote the location of a @c prev pointer
+ * (i.e., a pointer to the previous node).
*
* @param start a pointer to the start node
* @param start_index the start index
@@ -122,7 +154,7 @@
* @param elem a pointer to the element to find
* @param found_index an optional pointer where the index of the found node
* (given that @p start has index 0) is stored
- * @return the index of the element, if found - unspecified if not found
+ * @return a pointer to the found node or @c NULL if no matching node was found
*/
cx_attr_nonnull_arg(1, 4, 5)
cx_attr_export
@@ -193,7 +225,7 @@
/**
* Adds a new node to a linked list.
- * The node must not be part of any list already.
+ * The node must not be part of any list yet.
*
* @remark One of the pointers @p begin or @p end may be @c NULL, but not both.
*
@@ -215,7 +247,7 @@
/**
* Prepends a new node to a linked list.
- * The node must not be part of any list already.
+ * The node must not be part of any list yet.
*
* @remark One of the pointers @p begin or @p end may be @c NULL, but not both.
*
@@ -273,7 +305,7 @@
/**
* Inserts a new node after a given node of a linked list.
- * The new node must not be part of any list already.
+ * The new node must not be part of any list yet.
*
* @note If you specify @c NULL as the @p node to insert after, this function needs either the @p begin or
* the @p end pointer to determine the start of the list. Then the new node will be prepended to the list.
@@ -298,7 +330,7 @@
/**
* Inserts a chain of nodes after a given node of a linked list.
- * The chain must not be part of any list already.
+ * The chain must not be part of any list yet.
*
* If you do not explicitly specify the end of the chain, it will be determined by traversing
* the @c next pointer.
@@ -330,7 +362,7 @@
/**
* Inserts a node into a sorted linked list.
- * The new node must not be part of any list already.
+ * The new node must not be part of any list yet.
*
* If the list starting with the node pointed to by @p begin is not sorted
* already, the behavior is undefined.
@@ -355,14 +387,14 @@
/**
* Inserts a chain of nodes into a sorted linked list.
- * The chain must not be part of any list already.
+ * The chain must not be part of any list yet.
*
* If either the list starting with the node pointed to by @p begin or the list
* starting with @p insert_begin is not sorted, the behavior is undefined.
*
* @attention In contrast to cx_linked_list_insert_chain(), the source chain
* will be broken and inserted into the target list so that the resulting list
- * will be sorted according to @p cmp_func. That means, each node in the source
+ * will be sorted according to @p cmp_func. That means each node in the source
* chain may be re-linked with nodes from the target list.
*
* @param begin a pointer to the beginning node pointer (required)
@@ -384,9 +416,66 @@
);
/**
+ * Inserts a node into a sorted linked list if no other node with the same value already exists.
+ * The new node must not be part of any list yet.
+ *
+ * If the list starting with the node pointed to by @p begin is not sorted
+ * already, the behavior is undefined.
+ *
+ * @param begin a pointer to the beginning node pointer (required)
+ * @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 inserted
+ * @param cmp_func a compare function that will receive the node pointers
+ * @retval zero when the node was inserted
+ * @retval non-zero when a node with the same value already exists
+ */
+cx_attr_nonnull_arg(1, 5, 6)
+cx_attr_export
+int cx_linked_list_insert_unique(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *new_node,
+ cx_compare_func cmp_func
+);
+
+/**
+ * Inserts a chain of nodes into a sorted linked list, avoiding duplicates.
+ * The chain must not be part of any list yet.
+ *
+ * If either the list starting with the node pointed to by @p begin or the list
+ * starting with @p insert_begin is not sorted, the behavior is undefined.
+ *
+ * @attention In contrast to cx_linked_list_insert_sorted(), not all nodes of the
+ * chain might be added. This function returns a new chain consisting of all the duplicates.
+ *
+ * @param begin a pointer to the beginning node pointer (required)
+ * @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 insert_begin a pointer to the first node of the chain that shall be inserted
+ * @param cmp_func a compare function that will receive the node pointers
+ * @return a pointer to a new chain with all duplicates that were not inserted (or @c NULL when there were no duplicates)
+ */
+cx_attr_nonnull_arg(1, 5, 6)
+cx_attr_nodiscard
+cx_attr_export
+void *cx_linked_list_insert_unique_chain(
+ void **begin,
+ void **end,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next,
+ void *insert_begin,
+ cx_compare_func cmp_func
+);
+
+/**
* Removes a chain of nodes from the linked list.
*
- * If one of the nodes to remove is the beginning (resp. end) node of the list and if @p begin (resp. @p end)
+ * If one of the nodes to remove is the beginning (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):
@@ -418,7 +507,7 @@
/**
* Removes a node from the linked list.
*
- * If the node to remove is the beginning (resp. end) node of the list and if @p begin (resp. @p end)
+ * If the node to remove is the beginning (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):
@@ -496,7 +585,7 @@
/**
* Compares two lists element wise.
*
- * @attention Both list must have the same structure.
+ * @attention Both lists must have the same structure.
*
* @param begin_left the beginning of the left list (@c NULL denotes an empty list)
* @param begin_right the beginning of the right list (@c NULL denotes an empty list)