sort.c
3.18 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/* GNU Mailutils -- a suite of utilities for electronic mail
Copyright (C) 2011 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
License as published by the Free Software Foundation; either
version 3 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General
Public License along with this library. If not, see
<http://www.gnu.org/licenses/>. */
#ifdef HAVE_CONFIG_H
# include <config.h>
#endif
#include <stdlib.h>
#include <string.h>
#include <mailutils/errno.h>
#include <mailutils/sys/list.h>
static void
_list_append_entry (struct _mu_list *list, struct list_data *ent)
{
ent->prev = list->head.prev ? list->head.prev : &list->head;
ent->next = &list->head;
if (list->head.prev)
list->head.prev->next = ent;
else
list->head.next = ent;
list->head.prev = ent;
list->count++;
}
static void
_list_qsort (mu_list_t list, mu_list_comparator_t cmp)
{
struct list_data *cur, *middle;
struct _mu_list high_list, low_list;
int rc;
if (list->count < 2)
return;
if (list->count == 2)
{
if (cmp (list->head.prev->item, list->head.next->item) < 0)
{
cur = list->head.prev;
list->head.prev = list->head.next;
list->head.next = cur;
list->head.next->prev = &list->head;
list->head.next->next = list->head.prev;
list->head.prev->next = &list->head;
list->head.prev->prev = list->head.next;
}
return;
}
cur = list->head.next;
do {
cur = cur->next;
if (!cur)
return;
} while ((rc = cmp (list->head.next->item, cur->item)) == 0);
/* Select the lower of the two as the middle value */
middle = (rc > 0) ? cur : list->head.next;
/* Split into two sublists */
memset (&high_list, 0, sizeof (high_list));
memset (&low_list, 0, sizeof (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) < 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);
_list_qsort (&high_list, cmp);
/* Join both lists in order */
if (low_list.head.prev)
cur = low_list.head.prev;
else
cur = &low_list.head;
cur->next = high_list.head.next;
if (high_list.head.next)
high_list.head.next->prev = cur;
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;
}
void
mu_list_sort (mu_list_t list, mu_list_comparator_t comp)
{
if (list)
_list_qsort (list, comp ? comp : list->comp);
}