| 1404 |
serge |
1 |
#include |
|
|
2 |
#include |
|
|
3 |
#include |
|
|
4 |
#include |
|
|
5 |
|
|
|
6 |
/** |
|
|
7 |
* list_sort - sort a list. |
|
|
8 |
* @priv: private data, passed to @cmp |
|
|
9 |
* @head: the list to sort |
|
|
10 |
* @cmp: the elements comparison function |
|
|
11 |
* |
|
|
12 |
* This function has been implemented by Mark J Roberts . It |
|
|
13 |
* implements "merge sort" which has O(nlog(n)) complexity. The list is sorted |
|
|
14 |
* in ascending order. |
|
|
15 |
* |
|
|
16 |
* The comparison function @cmp is supposed to return a negative value if @a is |
|
|
17 |
* less than @b, and a positive value if @a is greater than @b. If @a and @b |
|
|
18 |
* are equivalent, then it does not matter what this function returns. |
|
|
19 |
*/ |
|
|
20 |
void list_sort(void *priv, struct list_head *head, |
|
|
21 |
int (*cmp)(void *priv, struct list_head *a, |
|
|
22 |
struct list_head *b)) |
|
|
23 |
{ |
|
|
24 |
struct list_head *p, *q, *e, *list, *tail, *oldhead; |
|
|
25 |
int insize, nmerges, psize, qsize, i; |
|
|
26 |
|
|
|
27 |
if (list_empty(head)) |
|
|
28 |
return; |
|
|
29 |
|
|
|
30 |
list = head->next; |
|
|
31 |
list_del(head); |
|
|
32 |
insize = 1; |
|
|
33 |
for (;;) { |
|
|
34 |
p = oldhead = list; |
|
|
35 |
list = tail = NULL; |
|
|
36 |
nmerges = 0; |
|
|
37 |
|
|
|
38 |
while (p) { |
|
|
39 |
nmerges++; |
|
|
40 |
q = p; |
|
|
41 |
psize = 0; |
|
|
42 |
for (i = 0; i < insize; i++) { |
|
|
43 |
psize++; |
|
|
44 |
q = q->next == oldhead ? NULL : q->next; |
|
|
45 |
if (!q) |
|
|
46 |
break; |
|
|
47 |
} |
|
|
48 |
|
|
|
49 |
qsize = insize; |
|
|
50 |
while (psize > 0 || (qsize > 0 && q)) { |
|
|
51 |
if (!psize) { |
|
|
52 |
e = q; |
|
|
53 |
q = q->next; |
|
|
54 |
qsize--; |
|
|
55 |
if (q == oldhead) |
|
|
56 |
q = NULL; |
|
|
57 |
} else if (!qsize || !q) { |
|
|
58 |
e = p; |
|
|
59 |
p = p->next; |
|
|
60 |
psize--; |
|
|
61 |
if (p == oldhead) |
|
|
62 |
p = NULL; |
|
|
63 |
} else if (cmp(priv, p, q) <= 0) { |
|
|
64 |
e = p; |
|
|
65 |
p = p->next; |
|
|
66 |
psize--; |
|
|
67 |
if (p == oldhead) |
|
|
68 |
p = NULL; |
|
|
69 |
} else { |
|
|
70 |
e = q; |
|
|
71 |
q = q->next; |
|
|
72 |
qsize--; |
|
|
73 |
if (q == oldhead) |
|
|
74 |
q = NULL; |
|
|
75 |
} |
|
|
76 |
if (tail) |
|
|
77 |
tail->next = e; |
|
|
78 |
else |
|
|
79 |
list = e; |
|
|
80 |
e->prev = tail; |
|
|
81 |
tail = e; |
|
|
82 |
} |
|
|
83 |
p = q; |
|
|
84 |
} |
|
|
85 |
|
|
|
86 |
tail->next = list; |
|
|
87 |
list->prev = tail; |
|
|
88 |
|
|
|
89 |
if (nmerges <= 1) |
|
|
90 |
break; |
|
|
91 |
|
|
|
92 |
insize *= 2; |
|
|
93 |
} |
|
|
94 |
|
|
|
95 |
head->next = list; |
|
|
96 |
head->prev = list->prev; |
|
|
97 |
list->prev->next = head; |
|
|
98 |
list->prev = head; |
|
|
99 |
} |
|
|
100 |
|
|
|
101 |
EXPORT_SYMBOL(list_sort); |