Dave Chinner | 2c76127 | 2010-01-12 17:39:16 +1100 | [diff] [blame] | 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); |