Rev 6934 | Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1412 | 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 |
||
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);=>=>> |