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); 103