summaryrefslogtreecommitdiff
path: root/libmailutils/list/sort.c
diff options
context:
space:
mode:
Diffstat (limited to 'libmailutils/list/sort.c')
-rw-r--r--libmailutils/list/sort.c84
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

Return to:

Send suggestions and report system problems to the System administrator.