1 #include <linux/kernel.h> 2 #include <linux/bug.h> 3 #include <linux/compiler.h> 4 #include <linux/export.h> 5 #include <linux/string.h> 6 #include <linux/list_sort.h> 7 #include <linux/list.h> 8 9 #define MAX_LIST_LENGTH_BITS 20 10 11 /* 12 * Returns a list organized in an intermediate format suited 13 * to chaining of merge() calls: null-terminated, no reserved or 14 * sentinel head node, "prev" links not maintained. 15 */ 16 static struct list_head *merge(void *priv, 17 int (*cmp)(void *priv, struct list_head *a, 18 struct list_head *b), 19 struct list_head *a, struct list_head *b) 20 { 21 struct list_head head, *tail = &head; 22 23 while (a && b) { 24 /* if equal, take 'a' -- important for sort stability */ 25 if ((*cmp)(priv, a, b) <= 0) { 26 tail->next = a; 27 a = a->next; 28 } else { 29 tail->next = b; 30 b = b->next; 31 } 32 tail = tail->next; 33 } 34 tail->next = a?:b; 35 return head.next; 36 } 37 38 /* 39 * Combine final list merge with restoration of standard doubly-linked 40 * list structure. This approach duplicates code from merge(), but 41 * runs faster than the tidier alternatives of either a separate final 42 * prev-link restoration pass, or maintaining the prev links 43 * throughout. 44 */ 45 static void merge_and_restore_back_links(void *priv, 46 int (*cmp)(void *priv, struct list_head *a, 47 struct list_head *b), 48 struct list_head *head, 49 struct list_head *a, struct list_head *b) 50 { 51 struct list_head *tail = head; 52 u8 count = 0; 53 54 while (a && b) { 55 /* if equal, take 'a' -- important for sort stability */ 56 if ((*cmp)(priv, a, b) <= 0) { 57 tail->next = a; 58 a->prev = tail; 59 a = a->next; 60 } else { 61 tail->next = b; 62 b->prev = tail; 63 b = b->next; 64 } 65 tail = tail->next; 66 } 67 tail->next = a ? : b; 68 69 do { 70 /* 71 * In worst cases this loop may run many iterations. 72 * Continue callbacks to the client even though no 73 * element comparison is needed, so the client's cmp() 74 * routine can invoke cond_resched() periodically. 75 */ 76 if (unlikely(!(++count))) 77 (*cmp)(priv, tail->next, tail->next); 78 79 tail->next->prev = tail; 80 tail = tail->next; 81 } while (tail->next); 82 83 tail->next = head; 84 head->prev = tail; 85 } 86 87 /** 88 * list_sort - sort a list 89 * @priv: private data, opaque to list_sort(), passed to @cmp 90 * @head: the list to sort 91 * @cmp: the elements comparison function 92 * 93 * This function implements "merge sort", which has O(nlog(n)) 94 * complexity. 95 * 96 * The comparison function @cmp must return a negative value if @a 97 * should sort before @b, and a positive value if @a should sort after 98 * @b. If @a and @b are equivalent, and their original relative 99 * ordering is to be preserved, @cmp must return 0. 100 */ 101 void list_sort(void *priv, struct list_head *head, 102 int (*cmp)(void *priv, struct list_head *a, 103 struct list_head *b)) 104 { 105 struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists 106 -- last slot is a sentinel */ 107 int lev; /* index into part[] */ 108 int max_lev = 0; 109 struct list_head *list; 110 111 if (list_empty(head)) 112 return; 113 114 memset(part, 0, sizeof(part)); 115 116 head->prev->next = NULL; 117 list = head->next; 118 119 while (list) { 120 struct list_head *cur = list; 121 list = list->next; 122 cur->next = NULL; 123 124 for (lev = 0; part[lev]; lev++) { 125 cur = merge(priv, cmp, part[lev], cur); 126 part[lev] = NULL; 127 } 128 if (lev > max_lev) { 129 if (unlikely(lev >= ARRAY_SIZE(part)-1)) { 130 printk_once(KERN_DEBUG "list too long for efficiency\n"); 131 lev--; 132 } 133 max_lev = lev; 134 } 135 part[lev] = cur; 136 } 137 138 for (lev = 0; lev < max_lev; lev++) 139 if (part[lev]) 140 list = merge(priv, cmp, part[lev], list); 141 142 merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); 143 } 144 EXPORT_SYMBOL(list_sort); 145