12c761270SDave Chinner #include <linux/kernel.h> 22c761270SDave Chinner #include <linux/module.h> 32c761270SDave Chinner #include <linux/list_sort.h> 42c761270SDave Chinner #include <linux/slab.h> 52c761270SDave Chinner #include <linux/list.h> 62c761270SDave Chinner 7835cc0c8SDon Mullis #define MAX_LIST_LENGTH_BITS 20 8835cc0c8SDon Mullis 9835cc0c8SDon Mullis /* 10835cc0c8SDon Mullis * Returns a list organized in an intermediate format suited 11835cc0c8SDon Mullis * to chaining of merge() calls: null-terminated, no reserved or 12835cc0c8SDon Mullis * sentinel head node, "prev" links not maintained. 13835cc0c8SDon Mullis */ 14835cc0c8SDon Mullis static struct list_head *merge(void *priv, 15835cc0c8SDon Mullis int (*cmp)(void *priv, struct list_head *a, 16835cc0c8SDon Mullis struct list_head *b), 17835cc0c8SDon Mullis struct list_head *a, struct list_head *b) 18835cc0c8SDon Mullis { 19835cc0c8SDon Mullis struct list_head head, *tail = &head; 20835cc0c8SDon Mullis 21835cc0c8SDon Mullis while (a && b) { 22835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */ 23835cc0c8SDon Mullis if ((*cmp)(priv, a, b) <= 0) { 24835cc0c8SDon Mullis tail->next = a; 25835cc0c8SDon Mullis a = a->next; 26835cc0c8SDon Mullis } else { 27835cc0c8SDon Mullis tail->next = b; 28835cc0c8SDon Mullis b = b->next; 29835cc0c8SDon Mullis } 30835cc0c8SDon Mullis tail = tail->next; 31835cc0c8SDon Mullis } 32835cc0c8SDon Mullis tail->next = a?:b; 33835cc0c8SDon Mullis return head.next; 34835cc0c8SDon Mullis } 35835cc0c8SDon Mullis 36835cc0c8SDon Mullis /* 37835cc0c8SDon Mullis * Combine final list merge with restoration of standard doubly-linked 38835cc0c8SDon Mullis * list structure. This approach duplicates code from merge(), but 39835cc0c8SDon Mullis * runs faster than the tidier alternatives of either a separate final 40835cc0c8SDon Mullis * prev-link restoration pass, or maintaining the prev links 41835cc0c8SDon Mullis * throughout. 42835cc0c8SDon Mullis */ 43835cc0c8SDon Mullis static void merge_and_restore_back_links(void *priv, 44835cc0c8SDon Mullis int (*cmp)(void *priv, struct list_head *a, 45835cc0c8SDon Mullis struct list_head *b), 46835cc0c8SDon Mullis struct list_head *head, 47835cc0c8SDon Mullis struct list_head *a, struct list_head *b) 48835cc0c8SDon Mullis { 49835cc0c8SDon Mullis struct list_head *tail = head; 50835cc0c8SDon Mullis 51835cc0c8SDon Mullis while (a && b) { 52835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */ 53835cc0c8SDon Mullis if ((*cmp)(priv, a, b) <= 0) { 54835cc0c8SDon Mullis tail->next = a; 55835cc0c8SDon Mullis a->prev = tail; 56835cc0c8SDon Mullis a = a->next; 57835cc0c8SDon Mullis } else { 58835cc0c8SDon Mullis tail->next = b; 59835cc0c8SDon Mullis b->prev = tail; 60835cc0c8SDon Mullis b = b->next; 61835cc0c8SDon Mullis } 62835cc0c8SDon Mullis tail = tail->next; 63835cc0c8SDon Mullis } 64835cc0c8SDon Mullis tail->next = a ? : b; 65835cc0c8SDon Mullis 66835cc0c8SDon Mullis do { 67835cc0c8SDon Mullis /* 68835cc0c8SDon Mullis * In worst cases this loop may run many iterations. 69835cc0c8SDon Mullis * Continue callbacks to the client even though no 70835cc0c8SDon Mullis * element comparison is needed, so the client's cmp() 71835cc0c8SDon Mullis * routine can invoke cond_resched() periodically. 72835cc0c8SDon Mullis */ 73f015ac3eSDon Mullis (*cmp)(priv, tail->next, tail->next); 74835cc0c8SDon Mullis 75835cc0c8SDon Mullis tail->next->prev = tail; 76835cc0c8SDon Mullis tail = tail->next; 77835cc0c8SDon Mullis } while (tail->next); 78835cc0c8SDon Mullis 79835cc0c8SDon Mullis tail->next = head; 80835cc0c8SDon Mullis head->prev = tail; 81835cc0c8SDon Mullis } 82835cc0c8SDon Mullis 832c761270SDave Chinner /** 8402b12b7aSDon Mullis * list_sort - sort a list 8502b12b7aSDon Mullis * @priv: private data, opaque to list_sort(), passed to @cmp 862c761270SDave Chinner * @head: the list to sort 872c761270SDave Chinner * @cmp: the elements comparison function 882c761270SDave Chinner * 8902b12b7aSDon Mullis * This function implements "merge sort", which has O(nlog(n)) 9002b12b7aSDon Mullis * complexity. 912c761270SDave Chinner * 9202b12b7aSDon Mullis * The comparison function @cmp must return a negative value if @a 9302b12b7aSDon Mullis * should sort before @b, and a positive value if @a should sort after 9402b12b7aSDon Mullis * @b. If @a and @b are equivalent, and their original relative 9502b12b7aSDon Mullis * ordering is to be preserved, @cmp must return 0. 962c761270SDave Chinner */ 972c761270SDave Chinner void list_sort(void *priv, struct list_head *head, 982c761270SDave Chinner int (*cmp)(void *priv, struct list_head *a, 992c761270SDave Chinner struct list_head *b)) 1002c761270SDave Chinner { 101835cc0c8SDon Mullis struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists 102835cc0c8SDon Mullis -- last slot is a sentinel */ 103835cc0c8SDon Mullis int lev; /* index into part[] */ 104835cc0c8SDon Mullis int max_lev = 0; 105835cc0c8SDon Mullis struct list_head *list; 1062c761270SDave Chinner 1072c761270SDave Chinner if (list_empty(head)) 1082c761270SDave Chinner return; 1092c761270SDave Chinner 110835cc0c8SDon Mullis memset(part, 0, sizeof(part)); 111835cc0c8SDon Mullis 112835cc0c8SDon Mullis head->prev->next = NULL; 1132c761270SDave Chinner list = head->next; 1142c761270SDave Chinner 115835cc0c8SDon Mullis while (list) { 116835cc0c8SDon Mullis struct list_head *cur = list; 117835cc0c8SDon Mullis list = list->next; 118835cc0c8SDon Mullis cur->next = NULL; 119835cc0c8SDon Mullis 120835cc0c8SDon Mullis for (lev = 0; part[lev]; lev++) { 121835cc0c8SDon Mullis cur = merge(priv, cmp, part[lev], cur); 122835cc0c8SDon Mullis part[lev] = NULL; 123835cc0c8SDon Mullis } 124835cc0c8SDon Mullis if (lev > max_lev) { 125835cc0c8SDon Mullis if (unlikely(lev >= ARRAY_SIZE(part)-1)) { 126835cc0c8SDon Mullis printk_once(KERN_DEBUG "list passed to" 127835cc0c8SDon Mullis " list_sort() too long for" 128835cc0c8SDon Mullis " efficiency\n"); 129835cc0c8SDon Mullis lev--; 130835cc0c8SDon Mullis } 131835cc0c8SDon Mullis max_lev = lev; 132835cc0c8SDon Mullis } 133835cc0c8SDon Mullis part[lev] = cur; 1342c761270SDave Chinner } 1352c761270SDave Chinner 136835cc0c8SDon Mullis for (lev = 0; lev < max_lev; lev++) 137835cc0c8SDon Mullis if (part[lev]) 138835cc0c8SDon Mullis list = merge(priv, cmp, part[lev], list); 1392c761270SDave Chinner 140835cc0c8SDon Mullis merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); 1412c761270SDave Chinner } 1422c761270SDave Chinner EXPORT_SYMBOL(list_sort); 143835cc0c8SDon Mullis 1446d411e6cSArtem Bityutskiy #ifdef CONFIG_TEST_LIST_SORT 145835cc0c8SDon Mullis struct debug_el { 146835cc0c8SDon Mullis struct list_head l_h; 147835cc0c8SDon Mullis int value; 148835cc0c8SDon Mullis unsigned serial; 149835cc0c8SDon Mullis }; 150835cc0c8SDon Mullis 151835cc0c8SDon Mullis static int cmp(void *priv, struct list_head *a, struct list_head *b) 152835cc0c8SDon Mullis { 153835cc0c8SDon Mullis return container_of(a, struct debug_el, l_h)->value 154835cc0c8SDon Mullis - container_of(b, struct debug_el, l_h)->value; 155835cc0c8SDon Mullis } 156835cc0c8SDon Mullis 157835cc0c8SDon Mullis /* 158835cc0c8SDon Mullis * The pattern of set bits in the list length determines which cases 159835cc0c8SDon Mullis * are hit in list_sort(). 160835cc0c8SDon Mullis */ 161835cc0c8SDon Mullis #define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */ 162835cc0c8SDon Mullis 163835cc0c8SDon Mullis static int __init list_sort_test(void) 164835cc0c8SDon Mullis { 165835cc0c8SDon Mullis int i, r = 1, count; 166835cc0c8SDon Mullis struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL); 167835cc0c8SDon Mullis struct list_head *cur; 168835cc0c8SDon Mullis 169835cc0c8SDon Mullis printk(KERN_WARNING "testing list_sort()\n"); 170835cc0c8SDon Mullis 171835cc0c8SDon Mullis cur = head; 172835cc0c8SDon Mullis for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) { 173835cc0c8SDon Mullis struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL); 174835cc0c8SDon Mullis BUG_ON(!el); 175835cc0c8SDon Mullis /* force some equivalencies */ 176835cc0c8SDon Mullis el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3); 177835cc0c8SDon Mullis el->serial = i; 178835cc0c8SDon Mullis 179835cc0c8SDon Mullis el->l_h.prev = cur; 180835cc0c8SDon Mullis cur->next = &el->l_h; 181835cc0c8SDon Mullis cur = cur->next; 182835cc0c8SDon Mullis } 183835cc0c8SDon Mullis head->prev = cur; 184835cc0c8SDon Mullis 185835cc0c8SDon Mullis list_sort(NULL, head, cmp); 186835cc0c8SDon Mullis 187835cc0c8SDon Mullis count = 1; 188835cc0c8SDon Mullis for (cur = head->next; cur->next != head; cur = cur->next) { 189835cc0c8SDon Mullis struct debug_el *el = container_of(cur, struct debug_el, l_h); 190835cc0c8SDon Mullis int cmp_result = cmp(NULL, cur, cur->next); 191835cc0c8SDon Mullis if (cur->next->prev != cur) { 192835cc0c8SDon Mullis printk(KERN_EMERG "list_sort() returned " 193835cc0c8SDon Mullis "a corrupted list!\n"); 194835cc0c8SDon Mullis return 1; 195835cc0c8SDon Mullis } else if (cmp_result > 0) { 196835cc0c8SDon Mullis printk(KERN_EMERG "list_sort() failed to sort!\n"); 197835cc0c8SDon Mullis return 1; 198835cc0c8SDon Mullis } else if (cmp_result == 0 && 199835cc0c8SDon Mullis el->serial >= container_of(cur->next, 200835cc0c8SDon Mullis struct debug_el, l_h)->serial) { 201835cc0c8SDon Mullis printk(KERN_EMERG "list_sort() failed to preserve order" 202835cc0c8SDon Mullis " of equivalent elements!\n"); 203835cc0c8SDon Mullis return 1; 204835cc0c8SDon Mullis } 205835cc0c8SDon Mullis kfree(cur->prev); 206835cc0c8SDon Mullis count++; 207835cc0c8SDon Mullis } 208835cc0c8SDon Mullis kfree(cur); 209835cc0c8SDon Mullis if (count != LIST_SORT_TEST_LENGTH) { 210835cc0c8SDon Mullis printk(KERN_EMERG "list_sort() returned list of" 211835cc0c8SDon Mullis "different length!\n"); 212835cc0c8SDon Mullis return 1; 213835cc0c8SDon Mullis } 214835cc0c8SDon Mullis return 0; 215835cc0c8SDon Mullis } 216835cc0c8SDon Mullis module_init(list_sort_test); 2176d411e6cSArtem Bityutskiy #endif /* CONFIG_TEST_LIST_SORT */ 218