1#include <structures/list.h>
2
3void list_sort(struct list_head *head,
4 int (*cmp)(struct list_head *, struct list_head *)) {
5 if (list_empty(head) || head->next->next == head)
6 return;
7
8 struct list_head *list = head->next;
9 head->prev->next = NULL;
10 list->prev = NULL;
11
12 int insize = 1;
13
14 while (1) {
15 struct list_head *p = list;
16 list = NULL;
17 struct list_head *tail = NULL;
18 int nmerges = 0;
19
20 while (p) {
21 nmerges++;
22 struct list_head *q = p;
23 int psize = 0;
24 for (int i = 0; i < insize; i++) {
25 psize++;
26 q = q->next;
27 if (!q)
28 break;
29 }
30
31 int qsize = insize;
32
33 /* Merge the two lists */
34 while (psize > 0 || (qsize > 0 && q)) {
35 struct list_head *e;
36
37 if (psize == 0) {
38 e = q;
39 q = q->next;
40 qsize--;
41 } else if (qsize == 0 || !q) {
42 e = p;
43 p = p->next;
44 psize--;
45 } else if (cmp(p, q) <= 0) {
46 e = p;
47 p = p->next;
48 psize--;
49 } else {
50 e = q;
51 q = q->next;
52 qsize--;
53 }
54
55 if (tail)
56 tail->next = e;
57 else
58 list = e;
59
60 e->prev = tail;
61 tail = e;
62 }
63
64 p = q;
65 }
66
67 tail->next = NULL;
68
69 if (nmerges <= 1)
70 break;
71
72 insize *= 2;
73 }
74
75 struct list_head *prev = head;
76 struct list_head *curr = list;
77 while (curr) {
78 curr->prev = prev;
79 prev->next = curr;
80 prev = curr;
81 curr = curr->next;
82 }
83
84 prev->next = head;
85 head->prev = prev;
86}
87
88/* Example:
89 *
90 * int node_cmp(struct list_head *a, struct list_head *b) {
91 * struct node *na = list_entry(a, struct node, list);
92 * struct node *nb = list_entry(b, struct node, list);
93 * return (na->value > nb->value) - (na->value < nb->value);
94 * }
95 */
96