diff options
Diffstat (limited to 'libmailutils/list/sort.c')
-rw-r--r-- | libmailutils/list/sort.c | 84 |
1 files changed, 44 insertions, 40 deletions
diff --git a/libmailutils/list/sort.c b/libmailutils/list/sort.c index 565880933..9793ca2d1 100644 --- a/libmailutils/list/sort.c +++ b/libmailutils/list/sort.c @@ -1,5 +1,5 @@ /* GNU Mailutils -- a suite of utilities for electronic mail - Copyright (C) 2011-2019 Free Software Foundation, Inc. + Copyright (C) 2011-2024 Free Software Foundation, Inc. This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public @@ -26,12 +26,9 @@ static void _list_append_entry (struct _mu_list *list, struct list_data *ent) { - ent->prev = list->head.prev ? list->head.prev : &list->head; + ent->prev = list->head.prev; ent->next = &list->head; - if (list->head.prev) - list->head.prev->next = ent; - else - list->head.next = ent; + list->head.prev->next = ent; list->head.prev = ent; list->count++; } @@ -42,7 +39,7 @@ _list_qsort (mu_list_t list, int cmp (const void *, const void *, void *), { struct list_data *cur, *middle; struct _mu_list high_list, low_list; - int rc; + size_t n; if (list->count < 2) return; @@ -62,56 +59,63 @@ _list_qsort (mu_list_t list, int cmp (const void *, const void *, void *), } return; } - - cur = list->head.next; - do { - cur = cur->next; - if (cur == &list->head) - return; - } while ((rc = cmp (list->head.next->item, cur->item, data)) == 0); - - /* Select the lower of the two as the middle value */ - middle = (rc > 0) ? cur : list->head.next; + middle = list->head.next; + for (n = list->count / 2; n > 0; n--) + middle = middle->next; + /* Split into two sublists */ - memset (&high_list, 0, sizeof (high_list)); - memset (&low_list, 0, sizeof (low_list)); + _mu_list_init (&high_list); + _mu_list_init (&low_list); for (cur = list->head.next; cur != &list->head; ) { struct list_data *next = cur->next; cur->next = NULL; - if (cmp (middle->item, cur->item, data) < 0) - _list_append_entry (&high_list, cur); - else - _list_append_entry (&low_list, cur); + if (cur != middle) + { + if (cmp (middle->item, cur->item, data) < 0) + _list_append_entry (&high_list, cur); + else + _list_append_entry (&low_list, cur); + } cur = next; } /* Sort both sublists recursively */ _list_qsort (&low_list, cmp, data); _list_qsort (&high_list, cmp, data); - - /* Join both lists in order */ - if (low_list.head.prev) - cur = low_list.head.prev; - else + + /* Join low_list + middle + high_list */ + if (low_list.head.prev == _mu_list_null (&low_list)) cur = &low_list.head; - cur->next = high_list.head.next; - if (high_list.head.next) - high_list.head.next->prev = cur; + else + cur = low_list.head.prev; + + cur->next = middle; + middle->prev = cur; + middle->next = &low_list.head; + low_list.head.prev = middle; + cur = middle; + + if (high_list.head.next != _mu_list_null (&high_list)) + { + cur->next = high_list.head.next; + high_list.head.next->prev = cur; + + low_list.head.prev = high_list.head.prev; + low_list.head.prev->next = &low_list.head; + + low_list.count += high_list.count; + } - low_list.head.prev = high_list.head.prev; - high_list.head.prev = &low_list.head; - low_list.count += high_list.count; - /* Return the resulting list */ - list->head = low_list.head; - if (list->head.next) - list->head.next->prev = &list->head; - if (list->head.prev) - list->head.prev->next = &list->head; + list->head.next = low_list.head.next; + list->head.next->prev = _mu_list_null (list); + + list->head.prev = low_list.head.prev; + list->head.prev->next = _mu_list_null (list); } void |