Merge branch 'topic/hda' into for-linus
[linux-2.6/linux-acpi-2.6/ibm-acpi-2.6.git] / lib / list_sort.c
blob19d11e0bb958a874fe7f560f25c75e392cd47aea
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
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.
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,
23 struct list_head *b))
25 struct list_head *p, *q, *e, *list, *tail, *oldhead;
26 int insize, nmerges, psize, qsize, i;
28 if (list_empty(head))
29 return;
31 list = head->next;
32 list_del(head);
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;
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;
77 if (tail)
78 tail->next = e;
79 else
80 list = e;
81 e->prev = tail;
82 tail = e;
84 p = q;
87 tail->next = list;
88 list->prev = tail;
90 if (nmerges <= 1)
91 break;
93 insize *= 2;
96 head->next = list;
97 head->prev = list->prev;
98 list->prev->next = head;
99 list->prev = head;
102 EXPORT_SYMBOL(list_sort);