Mercurial > hg > ucx / changeset

--- a/src/cx/linked_list.h	Thu Dec 18 16:43:05 2025 +0100
+++ b/src/cx/linked_list.h	Thu Dec 18 16:44:11 2025 +0100
@@ -392,6 +392,92 @@
         ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func);
 
 /**
+ * Inserts a node into a sorted linked list.
+ * 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
+ * @param context context for the compare function
+ */
+cx_attr_nonnull_arg(1, 5, 6)
+CX_EXPORT void cx_linked_list_insert_sorted_c(void **begin, void **end,
+        ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func2 cmp_func, void *context);
+
+/**
+ * Inserts a chain of nodes into a sorted linked list.
+ * 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
+ * chain may be re-linked with nodes from the target list.
+ *
+ * @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
+ * @param context context for the compare function
+ */
+cx_attr_nonnull_arg(1, 5, 6)
+CX_EXPORT void cx_linked_list_insert_sorted_chain_c(void **begin, void **end,
+        ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func2 cmp_func, void *context);
+
+/**
+ * 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_EXPORT int cx_linked_list_insert_unique_c(void **begin, void **end,
+        ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func2 cmp_func, void *context);
+
+/**
+ * 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
+ * @param context context for the compare function
+ * @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_EXPORT void *cx_linked_list_insert_unique_chain_c(void **begin, void **end,
+        ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func2 cmp_func, void *context);
+
+/**
  * 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)

--- a/src/linked_list.c	Thu Dec 18 16:43:05 2025 +0100
+++ b/src/linked_list.c	Thu Dec 18 16:44:11 2025 +0100
@@ -254,19 +254,6 @@
     }
 }
 
-void cx_linked_list_insert_sorted(
-        void **begin,
-        void **end,
-        ptrdiff_t loc_prev,
-        ptrdiff_t loc_next,
-        void *new_node,
-        cx_compare_func cmp_func
-) {
-    assert(ll_next(new_node) == NULL);
-    cx_linked_list_insert_sorted_chain(
-            begin, end, loc_prev, loc_next, new_node, cmp_func);
-}
-
 static void *cx_linked_list_insert_sorted_chain_impl(
         void **begin,
         void **end,
@@ -409,6 +396,19 @@
     return dup_begin;
 }
 
+void cx_linked_list_insert_sorted(
+        void **begin,
+        void **end,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next,
+        void *new_node,
+        cx_compare_func cmp_func
+) {
+    assert(ll_next(new_node) == NULL);
+    cx_linked_list_insert_sorted_chain(
+            begin, end, loc_prev, loc_next, new_node, cmp_func);
+}
+
 void cx_linked_list_insert_sorted_chain(
         void **begin,
         void **end,
@@ -450,6 +450,62 @@
             insert_begin, cx_acmp_wrap, &wrapper, false);
 }
 
+void cx_linked_list_insert_sorted_c(
+        void **begin,
+        void **end,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next,
+        void *new_node,
+        cx_compare_func2 cmp_func,
+        void *context
+) {
+    assert(ll_next(new_node) == NULL);
+    cx_linked_list_insert_sorted_chain_c(
+            begin, end, loc_prev, loc_next, new_node, cmp_func, context);
+}
+
+void cx_linked_list_insert_sorted_chain_c(
+        void **begin,
+        void **end,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next,
+        void *insert_begin,
+        cx_compare_func2 cmp_func,
+        void *context
+) {
+    cx_linked_list_insert_sorted_chain_impl(
+            begin, end, loc_prev, loc_next,
+            insert_begin, cmp_func, context, true);
+}
+
+int cx_linked_list_insert_unique_c(
+        void **begin,
+        void **end,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next,
+        void *new_node,
+        cx_compare_func2 cmp_func,
+        void *context
+) {
+    assert(ll_next(new_node) == NULL);
+    return NULL != cx_linked_list_insert_unique_chain_c(
+            begin, end, loc_prev, loc_next, new_node, cmp_func, context);
+}
+
+void *cx_linked_list_insert_unique_chain_c(
+        void **begin,
+        void **end,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next,
+        void *insert_begin,
+        cx_compare_func2 cmp_func,
+        void *context
+) {
+    return cx_linked_list_insert_sorted_chain_impl(
+            begin, end, loc_prev, loc_next,
+            insert_begin, cmp_func, context, false);
+}
+
 size_t cx_linked_list_remove_chain(
         void **begin,
         void **end,