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>
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  */
22                int (*cmp)(void *priv, struct list_head *a,
24 {
26         int insize, nmerges, psize, qsize, i;
29                 return;
33         insize = 1;
34         for (;;) {
35                 p = oldhead = list;
36                 list = tail = NULL;
37                 nmerges = 0;
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                         }
50                         qsize = insize;
51                         while (psize > 0 || (qsize > 0 && q)) {
52                                 if (!psize) {
53                                         e = q;
54                                         q = q->next;
55                                         qsize--;
57                                                 q = NULL;
58                                 } else if (!qsize || !q) {
59                                         e = p;
60                                         p = p->next;
61                                         psize--;
63                                                 p = NULL;
64                                 } else if (cmp(priv, p, q) <= 0) {
65                                         e = p;
66                                         p = p->next;
67                                         psize--;
69                                                 p = NULL;
70                                 } else {
71                                         e = q;
72                                         q = q->next;
73                                         qsize--;
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                 }
87                 tail->next = list;
88                 list->prev = tail;
90                 if (nmerges <= 1)
91                         break;
93                 insize *= 2;
94         }