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