# HG changeset patch
# User Mike Becker <universe@uap-core.de>
# Date 1633444391 -7200
# Node ID 75ae1dccd1012a618ac07cb9d0361030fe0f1f03
# Parent  95e42a96352036d63b055632c2c19eef9751ac3b
add cx_linked_list_sort()

diff -r 95e42a963520 -r 75ae1dccd101 src/cx/linked_list.h
--- a/src/cx/linked_list.h	Tue Oct 05 13:04:20 2021 +0200
+++ b/src/cx/linked_list.h	Tue Oct 05 16:33:11 2021 +0200
@@ -122,6 +122,46 @@
  */
 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
 
+/**
+ * Determines the size of a linked list starting with \p node.
+ * @param node the first node
+ * @param loc_next the location of the \c next pointer within the node struct
+ * @return the size of the list or zero if \p node is \c NULL
+ */
+size_t cx_linked_list_size(void *node, ptrdiff_t loc_next);
+
+/**
+ * Sorts a linked list based on a comparison function.
+ *
+ * This function can work with linked lists of the following structures:
+ * \code
+ * typedef struct node node;
+ * struct node {
+ *   node* prev;
+ *   node* next;
+ *   my_payload data; // in this case set follow_ptr = 0
+ * }
+ *
+ * typedef struct ptr_node ptr_node;
+ * struct ptr_node {
+ *   ptr_node* prev;
+ *   ptr_node* next;
+ *   my_payload* data; // in this case set follow_ptr = 1
+ * }
+ * \endcode
+ *
+ * @param begin a pointer to the begin node pointer (required)
+ * @param end a pointer to the end node pointer (optional)
+ * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present)
+ * @param loc_next the location of a \c next pointer within your node struct (required)
+ * @param loc_data the location of the \c data pointer within your node struct
+ * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
+ * If \c true, the data at \p loc_data is dereferenced, assuming to be a pointer, and then passed to \p cmp_func.
+ * @param cmp_func the compare function defining the sort order
+ */
+void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
+                         ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func);
+
 #ifdef __cplusplus
 } /* extern "C" */
 #endif
diff -r 95e42a963520 -r 75ae1dccd101 src/linked_list.c
--- a/src/linked_list.c	Tue Oct 05 13:04:20 2021 +0200
+++ b/src/linked_list.c	Tue Oct 05 16:33:11 2021 +0200
@@ -33,13 +33,13 @@
 
 /* LOW LEVEL LINKED LIST FUNCTIONS */
 
-#define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
+#define CX_LL_PTR(cur, off) (*(void**)(((char*)cur)+off))
 
 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) {
     size_t i = start_index;
     void *cur = start;
     while (i != index && cur != NULL) {
-        cur = *CX_LL_PTR(cur, loc_advance);
+        cur = CX_LL_PTR(cur, loc_advance);
         i < index ? i++ : i--;
     }
     return cur;
@@ -53,7 +53,7 @@
     void *last;
     do {
         last = cur;
-    } while ((cur = *CX_LL_PTR(cur, loc_next)) != NULL);
+    } while ((cur = CX_LL_PTR(cur, loc_next)) != NULL);
 
     return last;
 }
@@ -71,8 +71,7 @@
         *begin = new_node;
     } else {
         // if there is a last node, update its next pointer
-        void **next = CX_LL_PTR(last, loc_next);
-        *next = new_node;
+        CX_LL_PTR(last, loc_next) = new_node;
     }
 
     // if there is an end pointer, update it
@@ -82,11 +81,126 @@
 
     // if the nodes use a prev pointer, update it
     if (loc_prev >= 0) {
-        void **prev = CX_LL_PTR(new_node, loc_prev);
-        *prev = last;
+        CX_LL_PTR(new_node, loc_prev) = last;
     }
 }
 
+size_t cx_linked_list_size(void *node, ptrdiff_t loc_next) {
+    size_t size = 0;
+    while (node != NULL) {
+        node = CX_LL_PTR(node, loc_next);
+        size++;
+    }
+    return size;
+}
+
+#define ll_prev(node) CX_LL_PTR(node, loc_prev)
+#define ll_next(node) CX_LL_PTR(node, loc_next)
+#define ll_data(node) (follow_ptr?CX_LL_PTR(node, loc_data):(((char*)node)+loc_data))
+
+static void *cx_linked_list_sort_merge(ptrdiff_t loc_prev, ptrdiff_t loc_next,
+                                       ptrdiff_t loc_data, int follow_ptr,
+                                       size_t length, void *ls, void *le, void *re,
+                                       CxListComparator cmp_func) {
+    const size_t sbo_len = 1024;
+    void *sbo[sbo_len];
+    void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo;
+    void *rc, *lc;
+
+    lc = ls;
+    rc = le;
+    size_t n = 0;
+    while (lc && lc != le && rc != re) {
+        if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) {
+            sorted[n] = lc;
+            lc = ll_next(lc);
+        } else {
+            sorted[n] = rc;
+            rc = ll_next(rc);
+        }
+        n++;
+    }
+    while (lc && lc != le) {
+        sorted[n] = lc;
+        lc = ll_next(lc);
+        n++;
+    }
+    while (rc && rc != re) {
+        sorted[n] = rc;
+        rc = ll_next(rc);
+        n++;
+    }
+
+    // Update pointer
+    if (loc_prev >= 0) ll_prev(sorted[0]) = NULL;
+    for (size_t i = 0; i < length - 1; i++) {
+        ll_next(sorted[i]) = sorted[i + 1];
+        if (loc_prev >= 0) ll_prev(sorted[i + 1]) = sorted[i];
+    }
+    ll_next(sorted[length - 1]) = NULL;
+
+    void *ret = sorted[0];
+    if (sorted != sbo) {
+        free(sorted);
+    }
+    return ret;
+}
+
+void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next,
+                         ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) {
+    assert(begin != NULL);
+
+    void *lc, *ls, *le, *re;
+
+    // set start node
+    ls = *begin;
+
+    // check how many elements are already sorted
+    lc = ls;
+    size_t ln = 1;
+    while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) {
+        lc = ll_next(lc);
+        ln++;
+    }
+    le = ll_next(lc);
+
+    // if first unsorted node is NULL, the list is already completely sorted
+    if (le != NULL) {
+        void *rc;
+        size_t rn = 1;
+        rc = le;
+        // skip already sorted elements
+        while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) {
+            rc = ll_next(rc);
+            rn++;
+        }
+        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, follow_ptr,
+                                                 ln + rn, ls, le, re, cmp_func);
+
+        // Something left? Sort it!
+        size_t remainder_length = cx_linked_list_size(re, loc_next);
+        if (remainder_length > 0) {
+            void *remainder = re;
+            cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func);
+
+            // merge sorted list with (also sorted) remainder
+            *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr,
+                                               ln + rn + remainder_length,
+                                               sorted, remainder, NULL, cmp_func);
+        } else {
+            // no remainder - we've got our sorted list
+            *begin = sorted;
+        }
+        if (end) *end = cx_linked_list_last(sorted, loc_next);
+    }
+}
+
+#undef ll_next
+#undef ll_data
+
 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
 
 typedef struct cx_linked_list_node cx_linked_list_node;
@@ -109,7 +223,7 @@
     if (index >= list->base.size) {
         return NULL;
     } else if (index > list->base.size / 2) {
-        return cx_linked_list_at(list->end, list->base.size-1, CX_LL_LOC_PREV, index);
+        return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index);
     } else {
         return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
     }
@@ -144,7 +258,7 @@
             node->next = NULL;
             ll->end = node;
         }
-        // check if this shall be the new start node
+            // check if this shall be the new start node
         else if (index == 0) {
             ll->begin->prev = node;
             node->next = ll->begin;
@@ -219,7 +333,7 @@
 static void *cx_pll_at(cx_list_s *list, size_t index) {
     cx_linked_list *ll = (cx_linked_list *) list;
     cx_linked_list_node *node = cx_ll_node_at(ll, index);
-    return node == NULL ? NULL : *(void**)node->payload;
+    return node == NULL ? NULL : *(void **) node->payload;
 }
 
 static size_t cx_ll_find(cx_list_s *list, void *elem) {
@@ -245,7 +359,7 @@
     size_t index;
     cx_linked_list_node *node = ll->begin;
     for (index = 0; index < list->size; index++) {
-        void *current = *(void**)node->payload;
+        void *current = *(void **) node->payload;
         if (cmp(current, elem) == 0) {
             return index;
         }
@@ -263,7 +377,7 @@
 static void *cx_pll_last(cx_list_s *list) {
     cx_linked_list *ll = (cx_linked_list *) list;
     cx_linked_list_node *last = ll->end;
-    return last == NULL ? NULL : *(void**)last->payload;
+    return last == NULL ? NULL : *(void **) last->payload;
 }
 
 static cx_list_class cx_linked_list_class = {
@@ -310,7 +424,7 @@
     list->base.cl = &cx_pointer_linked_list_class;
     list->base.allocator = allocator;
     list->base.cmpfunc = comparator;
-    list->base.itemsize = sizeof(void*);
+    list->base.itemsize = sizeof(void *);
     list->base.capacity = SIZE_MAX;
     list->base.size = 0;
 
diff -r 95e42a963520 -r 75ae1dccd101 test/test_list.c
--- a/test/test_list.c	Tue Oct 05 13:04:20 2021 +0200
+++ b/test/test_list.c	Tue Oct 05 16:33:11 2021 +0200
@@ -146,6 +146,82 @@
     CU_ASSERT_PTR_EQUAL(cx_linked_list_last(&third, loc), &third)
 }
 
+void test_linked_list_size(void) {
+    struct node {
+        void *next;
+    };
+    ptrdiff_t loc = offsetof(struct node, next);
+
+    struct node first = {NULL};
+    struct node second = {NULL};
+    struct node third = {NULL};
+
+    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(NULL, loc), 0)
+    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 1)
+    first.next = &second;
+    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 2)
+    second.next = &third;
+    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&first, loc), 3)
+    CU_ASSERT_PTR_EQUAL(cx_linked_list_size(&second, loc), 2)
+}
+
+void test_linked_list_sort(void) {
+    struct node {
+        void *prev;
+        void *next;
+        int data;
+    };
+
+    int expected[] = {
+            14, 30, 151, 163, 227, 300, 315, 317, 363, 398, 417, 424, 438, 446, 508, 555, 605, 713, 716, 759, 761, 880,
+            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 1707, 1734, 1771, 1874, 1894,
+            1976, 2079, 2124, 2130, 2135, 2266, 2338, 2358, 2430, 2500, 2540, 2542, 2546, 2711, 2733, 2754, 2764, 2797,
+            2888, 2900, 3020, 3053, 3109, 3244, 3275, 3302, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 3675, 3677,
+            3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681,
+            4785, 4791, 4801, 4859, 4903, 4973
+    };
+    int scrambled[] = {
+            759, 716, 880, 761, 2358, 2542, 2500, 2540, 2546, 2711, 2430, 1707, 1874, 1771, 1894, 1734, 1976, 2079,
+            2124, 2130, 2135, 2266, 2338, 2733, 2754, 2764, 2797, 3362, 3363, 3364, 3441, 3515, 3539, 3579, 3655, 2888,
+            2900, 3020, 3053, 3109, 3244, 3275, 3302, 438, 446, 508, 555, 605, 713, 14, 30, 151, 163, 227, 300,
+            894, 1034, 1077, 1191, 1231, 1264, 1297, 1409, 1423, 1511, 1544, 1659, 1686, 315, 317, 363, 398, 417, 424,
+            3675, 3677, 3718, 3724, 3757, 3866, 3896, 3906, 3941, 3984, 3994, 4785, 4791, 4801, 4859, 4903, 4973,
+            4016, 4085, 4121, 4254, 4319, 4366, 4459, 4514, 4681
+    };
+
+    struct node *nodes = calloc(100, sizeof(struct node));
+    for (int i = 0; i < 100; i++) {
+        nodes[i].prev = i == 0 ? NULL : &nodes[i - 1];
+        nodes[i].next = i == 99 ? NULL : &nodes[i + 1];
+        nodes[i].data = scrambled[i];
+    }
+
+    struct node *begin = &nodes[0];
+    struct node *end = &nodes[99];
+
+    cx_linked_list_sort((void **) &begin, (void **) &end,
+                        offsetof(struct node, prev),
+                        offsetof(struct node, next),
+                        offsetof(struct node, data),
+                        0, (CxListComparator) cmp_int);
+
+    CU_ASSERT_PTR_NULL(begin->prev)
+    CU_ASSERT_EQUAL(begin->data, expected[0])
+    struct node *check = begin;
+    struct node *check_last = NULL;
+    for (int i = 0 ; i < 100 ; i++) {
+        CU_ASSERT_EQUAL(check->data, expected[i])
+        CU_ASSERT_PTR_EQUAL(check->prev, check_last)
+        if (i < 99) {
+            CU_ASSERT_PTR_NOT_NULL(check->next)
+        }
+        check_last = check;
+        check = check->next;
+    }
+    CU_ASSERT_PTR_NULL(check)
+    CU_ASSERT_EQUAL(end->data, expected[99])
+}
+
 
 void test_hl_linked_list_create(void) {
     cxTestingAllocatorReset();
@@ -494,6 +570,8 @@
     cu_add_test(suite, test_linked_list_at);
     cu_add_test(suite, test_linked_list_add);
     cu_add_test(suite, test_linked_list_last);
+    cu_add_test(suite, test_linked_list_size);
+    cu_add_test(suite, test_linked_list_sort);
 
     suite = CU_add_suite("high level linked list", NULL, NULL);