# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1684662778 -7200
# Node ID 425d4279856f10a843c26947d3b64170c2eac874
# Parent  3390b58ad15a49f5ac7877d750a6a0704f36059f
improve cx_linked_list_sort() - fixes #257

diff -r 3390b58ad15a -r 425d4279856f src/linked_list.c
--- a/src/linked_list.c	Fri May 05 19:07:56 2023 +0200
+++ b/src/linked_list.c	Sun May 21 11:52:58 2023 +0200
@@ -283,7 +283,7 @@
 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
 #endif
 
-static void *cx_linked_list_sort_merge(
+static void cx_linked_list_sort_merge(
         ptrdiff_t loc_prev,
         ptrdiff_t loc_next,
         ptrdiff_t loc_data,
@@ -291,7 +291,9 @@
         void *ls,
         void *le,
         void *re,
-        cx_compare_func cmp_func
+        cx_compare_func cmp_func,
+        void **begin,
+        void **end
 ) {
     void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
     void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
@@ -330,11 +332,11 @@
     }
     ll_next(sorted[length - 1]) = NULL;
 
-    void *ret = sorted[0];
+    *begin = sorted[0];
+    *end = sorted[length-1];
     if (sorted != sbo) {
         free(sorted);
     }
-    return ret;
 }
 
 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
@@ -380,8 +382,10 @@
         re = ll_next(rc);
 
         // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
-        void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
-                                                 ln + rn, ls, le, re, cmp_func);
+        void *sorted_begin, *sorted_end;
+        cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
+                                  ln + rn, ls, le, re, cmp_func,
+                                  &sorted_begin, &sorted_end);
 
         // Something left? Sort it!
         size_t remainder_length = cx_linked_list_size(re, loc_next);
@@ -390,14 +394,13 @@
             cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
 
             // merge sorted list with (also sorted) remainder
-            *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
-                                               ln + rn + remainder_length,
-                                               sorted, remainder, NULL, cmp_func);
-        } else {
-            // no remainder - we've got our sorted list
-            *begin = sorted;
+            cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
+                                      ln + rn + remainder_length,
+                                      sorted_begin, remainder, NULL, cmp_func,
+                                      &sorted_begin, &sorted_end);
         }
-        if (end) *end = cx_linked_list_last(sorted, loc_next);
+        *begin = sorted_begin;
+        if (end) *end = sorted_end;
     }
 }