# HG changeset patch
# User Matti Hamalainen <ccr@tnsp.org>
# Date 1675556182 -7200
# Node ID 618c7fa3a4f8e219d7d478098a7787a3967c38b7
# Parent  72fb5ce9086a044aaa3c14a13197cb5c622f6317
Add th_llist_mergesort() for sorting linked lists.

diff -r 72fb5ce9086a -r 618c7fa3a4f8 th_datastruct.c
--- a/th_datastruct.c	Wed Feb 01 16:43:36 2023 +0200
+++ b/th_datastruct.c	Sun Feb 05 02:16:22 2023 +0200
@@ -340,6 +340,81 @@
 }
 
 
+static th_llist_t *th_llist_mergesort_merge(th_llist_t *left, th_llist_t *right,
+    int (compare)(const th_llist_t *lnode, const th_llist_t *rnode, void *userdata),
+    void *userdata)
+{
+    th_llist_t *result;
+
+    if (left == NULL)
+        return right;
+    else
+    if (right == NULL)
+        return left;
+
+    if (compare(left, right, userdata))
+    {
+        result = left;
+        result->next = th_llist_mergesort_merge(left->next, right, compare, userdata);
+    }
+    else
+    {
+        result = right;
+        result->next = th_llist_mergesort_merge(left, right->next, compare, userdata);
+    }
+
+    if (result->next != NULL)
+        result->prev = result->prev;
+
+    return result;
+}
+
+
+static void th_llist_mergesort_do(th_llist_t **list,
+    int (compare)(const th_llist_t *lnode, const th_llist_t *rnode, void *userdata),
+    void *userdata)
+{
+    th_llist_t *head = *list, *left, *right, *slow, *fast;
+
+    if (head == NULL || head->next == NULL)
+        return;
+
+    slow = head;
+    fast = head->next;
+    while (fast != NULL)
+    {
+        fast = fast->next;
+        if (fast != NULL)
+        {
+            slow = slow->next;
+            fast = fast->next;
+        }
+    }
+
+    left = head;
+    right = slow->next;
+    slow->next = NULL;
+
+    th_llist_mergesort_do(&left, compare, userdata);
+    th_llist_mergesort_do(&right, compare, userdata);
+
+    *list = th_llist_mergesort_merge(left, right, compare, userdata);
+}
+
+
+void th_llist_mergesort(th_llist_t **list,
+    int (compare)(const th_llist_t *lnode, const th_llist_t *rnode, void *userdata),
+    void *userdata)
+{
+    if (list != NULL && *list != NULL)
+    {
+        size_t num = (*list)->num;
+        th_llist_mergesort_do(list, compare, userdata);
+        (*list)->num = num;
+    }
+}
+
+
 /*
  * Ringbuffers
  */
diff -r 72fb5ce9086a -r 618c7fa3a4f8 th_datastruct.h
--- a/th_datastruct.h	Wed Feb 01 16:43:36 2023 +0200
+++ b/th_datastruct.h	Sun Feb 05 02:16:22 2023 +0200
@@ -51,6 +51,10 @@
 th_llist_t *   th_llist_find_data(th_llist_t *list, const void *data);
 th_llist_t *   th_llist_find_func(th_llist_t *list, const void *userdata, int (compare)(const void *, const void *));
 
+void           th_llist_mergesort(th_llist_t **list,
+               int (compare)(const th_llist_t *lnode, const th_llist_t *rnode, void *userdata),
+               void *userdata);
+
 
 /** @brief
  * Ringbuffer data structure