# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1725910479 -7200
# Node ID 9c24a4eb5ac977395d00e72b36d1888c95ac2d5a
# Parent  1c1ee61c01f93294f1ecea20ad636d6cec840bf9
implement optimized sorted insert for linked lists - resolves #415

diff -r 1c1ee61c01f9 -r 9c24a4eb5ac9 src/cx/linked_list.h
--- a/src/cx/linked_list.h	Mon Sep 09 19:00:47 2024 +0200
+++ b/src/cx/linked_list.h	Mon Sep 09 21:34:39 2024 +0200
@@ -324,6 +324,57 @@
 ) __attribute__((__nonnull__(6)));
 
 /**
+ * Inserts a node into a sorted linked list.
+ * The new node must not be part of any list already.
+ *
+ * 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 begin 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
+ */
+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
+) __attribute__((__nonnull__(1, 5, 6)));
+
+/**
+ * Inserts a chain of nodes into a sorted linked list.
+ * The chain must not be part of any list already.
+ *
+ * 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 begin 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
+ */
+void cx_linked_list_insert_sorted_chain(
+        void **begin,
+        void **end,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next,
+        void *insert_begin,
+        cx_compare_func cmp_func
+)  __attribute__((__nonnull__(1, 5, 6)));
+
+/**
  * 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)
diff -r 1c1ee61c01f9 -r 9c24a4eb5ac9 src/linked_list.c
--- a/src/linked_list.c	Mon Sep 09 19:00:47 2024 +0200
+++ b/src/linked_list.c	Mon Sep 09 21:34:39 2024 +0200
@@ -247,6 +247,95 @@
     }
 }
 
+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,
+        ptrdiff_t loc_prev,
+        ptrdiff_t loc_next,
+        void *insert_begin,
+        cx_compare_func cmp_func
+) {
+    assert(begin != NULL);
+    assert(loc_next >= 0);
+    assert(insert_begin != NULL);
+
+    // track currently observed nodes
+    void *dest_prev = NULL;
+    void *dest = *begin;
+    void *src = insert_begin;
+
+    // special case: list is empty
+    if (dest == NULL) {
+        *begin = src;
+        if (end != NULL) {
+            *end = cx_linked_list_last(src, loc_next);
+        }
+        return;
+    }
+
+    // search the list for insertion points
+    while (dest != NULL && src != NULL) {
+        // compare current list node with source node
+        // if less or equal, skip
+        if (cmp_func(dest, src) <= 0) {
+            dest_prev = dest;
+            dest = ll_next(dest);
+            continue;
+        }
+
+        // determine chain of elements that can be inserted
+        void *end_of_chain = src;
+        void *next_in_chain = ll_next(src);
+        while (next_in_chain != NULL) {
+            // once we become larger than the list elem, break
+            if (cmp_func(dest, next_in_chain) <= 0) {
+                break;
+            }
+            // otherwise, we can insert one more
+            end_of_chain = next_in_chain;
+            next_in_chain = ll_next(next_in_chain);
+        }
+
+        // insert the elements
+        if (dest_prev == NULL) {
+            // new begin
+            *begin = src;
+        } else {
+            cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
+        }
+        cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next);
+
+        // continue with next
+        src = next_in_chain;
+        dest_prev = dest;
+        dest = ll_next(dest);
+    }
+
+    // insert remaining items
+    if (src != NULL) {
+        cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
+    }
+
+    // determine new end of list, if requested
+    if (end != NULL) {
+        *end = cx_linked_list_last(
+                dest != NULL ? dest : dest_prev, loc_next);
+    }
+}
+
 void cx_linked_list_remove(
         void **begin,
         void **end,
@@ -510,6 +599,11 @@
     }
 }
 
+static cx_linked_list_node *cx_ll_malloc_node(struct cx_list_s const *list) {
+    return cxMalloc(list->collection.allocator,
+                    sizeof(cx_linked_list_node) + list->collection.elem_size);
+}
+
 static int cx_ll_insert_at(
         struct cx_list_s *list,
         cx_linked_list_node *node,
@@ -517,8 +611,7 @@
 ) {
 
     // create the new new_node
-    cx_linked_list_node *new_node = cxMalloc(list->collection.allocator,
-                                             sizeof(cx_linked_list_node) + list->collection.elem_size);
+    cx_linked_list_node *new_node = cx_ll_malloc_node(list);
 
     // sortir if failed
     if (new_node == NULL) return 1;
@@ -563,7 +656,7 @@
     // we now know exactly where we are
     node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
 
-    // we can add the remaining nodes and immedately advance to the inserted node
+    // we can add the remaining nodes and immediately advance to the inserted node
     char const *source = array;
     for (size_t i = 1; i < n; i++) {
         source += list->collection.elem_size;
@@ -583,6 +676,63 @@
     return 1 != cx_ll_insert_array(list, index, element, 1);
 }
 
+static cx_compare_func cx_ll_insert_sorted_cmp_func;
+
+static int cx_ll_insert_sorted_cmp_helper(void const *l, void const *r) {
+    cx_linked_list_node const *left = l;
+    cx_linked_list_node const *right = r;
+    return cx_ll_insert_sorted_cmp_func(left->payload, right->payload);
+}
+
+static size_t cx_ll_insert_sorted(
+        struct cx_list_s *list,
+        void const *array,
+        size_t n
+) {
+    // special case
+    if (n == 0) return 0;
+
+    // create a new chain of nodes
+    cx_linked_list_node *chain = cx_ll_malloc_node(list);
+    if (chain == NULL) return 0;
+
+    memcpy(chain->payload, array, list->collection.elem_size);
+    chain->prev = NULL;
+    chain->next = NULL;
+
+    // add all elements from the array to that chain
+    cx_linked_list_node *prev = chain;
+    char const *src = array;
+    size_t inserted = 1;
+    for (; inserted < n; inserted++) {
+        cx_linked_list_node *next = cx_ll_malloc_node(list);
+        if (next == NULL) break;
+        src += list->collection.elem_size;
+        memcpy(next->payload, src, list->collection.elem_size);
+        prev->next = next;
+        next->prev = prev;
+        prev = next;
+    }
+    prev->next = NULL;
+
+    // invoke the low level function
+    cx_linked_list *ll = (cx_linked_list *) list;
+    cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc;
+    cx_linked_list_insert_sorted_chain(
+            (void **) &ll->begin,
+            (void **) &ll->end,
+            CX_LL_LOC_PREV,
+            CX_LL_LOC_NEXT,
+            chain,
+            cx_ll_insert_sorted_cmp_helper
+    );
+
+    // adjust the list metadata
+    list->collection.size += inserted;
+
+    return inserted;
+}
+
 static int cx_ll_remove(
         struct cx_list_s *list,
         size_t index
@@ -927,7 +1077,7 @@
         cx_ll_destructor,
         cx_ll_insert_element,
         cx_ll_insert_array,
-        cx_list_default_insert_sorted,
+        cx_ll_insert_sorted,
         cx_ll_insert_iter,
         cx_ll_remove,
         cx_ll_clear,