Mercurial > hg > th-libs
changeset 759:618c7fa3a4f8
Add th_llist_mergesort() for sorting linked lists.
author | Matti Hamalainen <ccr@tnsp.org> |
---|---|
date | Sun, 05 Feb 2023 02:16:22 +0200 |
parents | 72fb5ce9086a |
children | 1cb9454ec569 |
files | th_datastruct.c th_datastruct.h |
diffstat | 2 files changed, 79 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- 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 */
--- 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