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>
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
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
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.
21 void list_sort(void *priv, struct list_head *head,
22 int (*cmp)(void *priv, struct list_head *a,
25 struct list_head *p, *q, *e, *list, *tail, *oldhead;
26 int insize, nmerges, psize, qsize, i;
43 for (i = 0; i < insize; i++) {
45 q = q->next == oldhead ? NULL : q->next;
51 while (psize > 0 || (qsize > 0 && q)) {
58 } else if (!qsize || !q) {
64 } else if (cmp(priv, p, q) <= 0) {
97 head->prev = list->prev;
98 list->prev->next = head;
102 EXPORT_SYMBOL(list_sort);