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 #define MAX_LIST_LENGTH_BITS 20 8 9 /* 10 * Returns a list organized in an intermediate format suited 11 * to chaining of merge() calls: null-terminated, no reserved or 12 * sentinel head node, "prev" links not maintained. 13 */ 14 static struct list_head *merge(void *priv, 15 int (*cmp)(void *priv, struct list_head *a, 16 struct list_head *b), 17 struct list_head *a, struct list_head *b) 18 { 19 struct list_head head, *tail = &head; 20 21 while (a && b) { 22 /* if equal, take 'a' -- important for sort stability */ 23 if ((*cmp)(priv, a, b) <= 0) { 24 tail->next = a; 25 a = a->next; 26 } else { 27 tail->next = b; 28 b = b->next; 29 } 30 tail = tail->next; 31 } 32 tail->next = a?:b; 33 return head.next; 34 } 35 36 /* 37 * Combine final list merge with restoration of standard doubly-linked 38 * list structure. This approach duplicates code from merge(), but 39 * runs faster than the tidier alternatives of either a separate final 40 * prev-link restoration pass, or maintaining the prev links 41 * throughout. 42 */ 43 static void merge_and_restore_back_links(void *priv, 44 int (*cmp)(void *priv, struct list_head *a, 45 struct list_head *b), 46 struct list_head *head, 47 struct list_head *a, struct list_head *b) 48 { 49 struct list_head *tail = head; 50 51 while (a && b) { 52 /* if equal, take 'a' -- important for sort stability */ 53 if ((*cmp)(priv, a, b) <= 0) { 54 tail->next = a; 55 a->prev = tail; 56 a = a->next; 57 } else { 58 tail->next = b; 59 b->prev = tail; 60 b = b->next; 61 } 62 tail = tail->next; 63 } 64 tail->next = a ? : b; 65 66 do { 67 /* 68 * In worst cases this loop may run many iterations. 69 * Continue callbacks to the client even though no 70 * element comparison is needed, so the client's cmp() 71 * routine can invoke cond_resched() periodically. 72 */ 73 (*cmp)(priv, tail, tail); 74 75 tail->next->prev = tail; 76 tail = tail->next; 77 } while (tail->next); 78 79 tail->next = head; 80 head->prev = tail; 81 } 82 83 /** 84 * list_sort - sort a list 85 * @priv: private data, opaque to list_sort(), passed to @cmp 86 * @head: the list to sort 87 * @cmp: the elements comparison function 88 * 89 * This function implements "merge sort", which has O(nlog(n)) 90 * complexity. 91 * 92 * The comparison function @cmp must return a negative value if @a 93 * should sort before @b, and a positive value if @a should sort after 94 * @b. If @a and @b are equivalent, and their original relative 95 * ordering is to be preserved, @cmp must return 0. 96 */ 97 void list_sort(void *priv, struct list_head *head, 98 int (*cmp)(void *priv, struct list_head *a, 99 struct list_head *b)) 100 { 101 struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists 102 -- last slot is a sentinel */ 103 int lev; /* index into part[] */ 104 int max_lev = 0; 105 struct list_head *list; 106 107 if (list_empty(head)) 108 return; 109 110 memset(part, 0, sizeof(part)); 111 112 head->prev->next = NULL; 113 list = head->next; 114 115 while (list) { 116 struct list_head *cur = list; 117 list = list->next; 118 cur->next = NULL; 119 120 for (lev = 0; part[lev]; lev++) { 121 cur = merge(priv, cmp, part[lev], cur); 122 part[lev] = NULL; 123 } 124 if (lev > max_lev) { 125 if (unlikely(lev >= ARRAY_SIZE(part)-1)) { 126 printk_once(KERN_DEBUG "list passed to" 127 " list_sort() too long for" 128 " efficiency\n"); 129 lev--; 130 } 131 max_lev = lev; 132 } 133 part[lev] = cur; 134 } 135 136 for (lev = 0; lev < max_lev; lev++) 137 if (part[lev]) 138 list = merge(priv, cmp, part[lev], list); 139 140 merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); 141 } 142 EXPORT_SYMBOL(list_sort); 143 144 #ifdef DEBUG_LIST_SORT 145 struct debug_el { 146 struct list_head l_h; 147 int value; 148 unsigned serial; 149 }; 150 151 static int cmp(void *priv, struct list_head *a, struct list_head *b) 152 { 153 return container_of(a, struct debug_el, l_h)->value 154 - container_of(b, struct debug_el, l_h)->value; 155 } 156 157 /* 158 * The pattern of set bits in the list length determines which cases 159 * are hit in list_sort(). 160 */ 161 #define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */ 162 163 static int __init list_sort_test(void) 164 { 165 int i, r = 1, count; 166 struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL); 167 struct list_head *cur; 168 169 printk(KERN_WARNING "testing list_sort()\n"); 170 171 cur = head; 172 for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) { 173 struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL); 174 BUG_ON(!el); 175 /* force some equivalencies */ 176 el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3); 177 el->serial = i; 178 179 el->l_h.prev = cur; 180 cur->next = &el->l_h; 181 cur = cur->next; 182 } 183 head->prev = cur; 184 185 list_sort(NULL, head, cmp); 186 187 count = 1; 188 for (cur = head->next; cur->next != head; cur = cur->next) { 189 struct debug_el *el = container_of(cur, struct debug_el, l_h); 190 int cmp_result = cmp(NULL, cur, cur->next); 191 if (cur->next->prev != cur) { 192 printk(KERN_EMERG "list_sort() returned " 193 "a corrupted list!\n"); 194 return 1; 195 } else if (cmp_result > 0) { 196 printk(KERN_EMERG "list_sort() failed to sort!\n"); 197 return 1; 198 } else if (cmp_result == 0 && 199 el->serial >= container_of(cur->next, 200 struct debug_el, l_h)->serial) { 201 printk(KERN_EMERG "list_sort() failed to preserve order" 202 " of equivalent elements!\n"); 203 return 1; 204 } 205 kfree(cur->prev); 206 count++; 207 } 208 kfree(cur); 209 if (count != LIST_SORT_TEST_LENGTH) { 210 printk(KERN_EMERG "list_sort() returned list of" 211 "different length!\n"); 212 return 1; 213 } 214 return 0; 215 } 216 module_init(list_sort_test); 217 #endif 218