1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0 22c761270SDave Chinner #include <linux/kernel.h> 37259fa04SRasmus Villemoes #include <linux/bug.h> 47259fa04SRasmus Villemoes #include <linux/compiler.h> 57259fa04SRasmus Villemoes #include <linux/export.h> 67259fa04SRasmus Villemoes #include <linux/string.h> 72c761270SDave Chinner #include <linux/list_sort.h> 82c761270SDave Chinner #include <linux/list.h> 92c761270SDave Chinner 10835cc0c8SDon Mullis #define MAX_LIST_LENGTH_BITS 20 11835cc0c8SDon Mullis 12835cc0c8SDon Mullis /* 13835cc0c8SDon Mullis * Returns a list organized in an intermediate format suited 14835cc0c8SDon Mullis * to chaining of merge() calls: null-terminated, no reserved or 15835cc0c8SDon Mullis * sentinel head node, "prev" links not maintained. 16835cc0c8SDon Mullis */ 17835cc0c8SDon Mullis static struct list_head *merge(void *priv, 18835cc0c8SDon Mullis int (*cmp)(void *priv, struct list_head *a, 19835cc0c8SDon Mullis struct list_head *b), 20835cc0c8SDon Mullis struct list_head *a, struct list_head *b) 21835cc0c8SDon Mullis { 22835cc0c8SDon Mullis struct list_head head, *tail = &head; 23835cc0c8SDon Mullis 24835cc0c8SDon Mullis while (a && b) { 25835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */ 26835cc0c8SDon Mullis if ((*cmp)(priv, a, b) <= 0) { 27835cc0c8SDon Mullis tail->next = a; 28835cc0c8SDon Mullis a = a->next; 29835cc0c8SDon Mullis } else { 30835cc0c8SDon Mullis tail->next = b; 31835cc0c8SDon Mullis b = b->next; 32835cc0c8SDon Mullis } 33835cc0c8SDon Mullis tail = tail->next; 34835cc0c8SDon Mullis } 35835cc0c8SDon Mullis tail->next = a?:b; 36835cc0c8SDon Mullis return head.next; 37835cc0c8SDon Mullis } 38835cc0c8SDon Mullis 39835cc0c8SDon Mullis /* 40835cc0c8SDon Mullis * Combine final list merge with restoration of standard doubly-linked 41835cc0c8SDon Mullis * list structure. This approach duplicates code from merge(), but 42835cc0c8SDon Mullis * runs faster than the tidier alternatives of either a separate final 43835cc0c8SDon Mullis * prev-link restoration pass, or maintaining the prev links 44835cc0c8SDon Mullis * throughout. 45835cc0c8SDon Mullis */ 46835cc0c8SDon Mullis static void merge_and_restore_back_links(void *priv, 47835cc0c8SDon Mullis int (*cmp)(void *priv, struct list_head *a, 48835cc0c8SDon Mullis struct list_head *b), 49835cc0c8SDon Mullis struct list_head *head, 50835cc0c8SDon Mullis struct list_head *a, struct list_head *b) 51835cc0c8SDon Mullis { 52835cc0c8SDon Mullis struct list_head *tail = head; 5361b3d6c4SRasmus Villemoes u8 count = 0; 54835cc0c8SDon Mullis 55835cc0c8SDon Mullis while (a && b) { 56835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */ 57835cc0c8SDon Mullis if ((*cmp)(priv, a, b) <= 0) { 58835cc0c8SDon Mullis tail->next = a; 59835cc0c8SDon Mullis a->prev = tail; 60835cc0c8SDon Mullis a = a->next; 61835cc0c8SDon Mullis } else { 62835cc0c8SDon Mullis tail->next = b; 63835cc0c8SDon Mullis b->prev = tail; 64835cc0c8SDon Mullis b = b->next; 65835cc0c8SDon Mullis } 66835cc0c8SDon Mullis tail = tail->next; 67835cc0c8SDon Mullis } 68835cc0c8SDon Mullis tail->next = a ? : b; 69835cc0c8SDon Mullis 70835cc0c8SDon Mullis do { 71835cc0c8SDon Mullis /* 72835cc0c8SDon Mullis * In worst cases this loop may run many iterations. 73835cc0c8SDon Mullis * Continue callbacks to the client even though no 74835cc0c8SDon Mullis * element comparison is needed, so the client's cmp() 75835cc0c8SDon Mullis * routine can invoke cond_resched() periodically. 76835cc0c8SDon Mullis */ 7761b3d6c4SRasmus Villemoes if (unlikely(!(++count))) 78f015ac3eSDon Mullis (*cmp)(priv, tail->next, tail->next); 79835cc0c8SDon Mullis 80835cc0c8SDon Mullis tail->next->prev = tail; 81835cc0c8SDon Mullis tail = tail->next; 82835cc0c8SDon Mullis } while (tail->next); 83835cc0c8SDon Mullis 84835cc0c8SDon Mullis tail->next = head; 85835cc0c8SDon Mullis head->prev = tail; 86835cc0c8SDon Mullis } 87835cc0c8SDon Mullis 882c761270SDave Chinner /** 8902b12b7aSDon Mullis * list_sort - sort a list 9002b12b7aSDon Mullis * @priv: private data, opaque to list_sort(), passed to @cmp 912c761270SDave Chinner * @head: the list to sort 922c761270SDave Chinner * @cmp: the elements comparison function 932c761270SDave Chinner * 9402b12b7aSDon Mullis * This function implements "merge sort", which has O(nlog(n)) 9502b12b7aSDon Mullis * complexity. 962c761270SDave Chinner * 9702b12b7aSDon Mullis * The comparison function @cmp must return a negative value if @a 9802b12b7aSDon Mullis * should sort before @b, and a positive value if @a should sort after 9902b12b7aSDon Mullis * @b. If @a and @b are equivalent, and their original relative 10002b12b7aSDon Mullis * ordering is to be preserved, @cmp must return 0. 1012c761270SDave Chinner */ 1022c761270SDave Chinner void list_sort(void *priv, struct list_head *head, 1032c761270SDave Chinner int (*cmp)(void *priv, struct list_head *a, 1042c761270SDave Chinner struct list_head *b)) 1052c761270SDave Chinner { 106835cc0c8SDon Mullis struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists 107835cc0c8SDon Mullis -- last slot is a sentinel */ 108835cc0c8SDon Mullis int lev; /* index into part[] */ 109835cc0c8SDon Mullis int max_lev = 0; 110835cc0c8SDon Mullis struct list_head *list; 1112c761270SDave Chinner 1122c761270SDave Chinner if (list_empty(head)) 1132c761270SDave Chinner return; 1142c761270SDave Chinner 115835cc0c8SDon Mullis memset(part, 0, sizeof(part)); 116835cc0c8SDon Mullis 117835cc0c8SDon Mullis head->prev->next = NULL; 1182c761270SDave Chinner list = head->next; 1192c761270SDave Chinner 120835cc0c8SDon Mullis while (list) { 121835cc0c8SDon Mullis struct list_head *cur = list; 122835cc0c8SDon Mullis list = list->next; 123835cc0c8SDon Mullis cur->next = NULL; 124835cc0c8SDon Mullis 125835cc0c8SDon Mullis for (lev = 0; part[lev]; lev++) { 126835cc0c8SDon Mullis cur = merge(priv, cmp, part[lev], cur); 127835cc0c8SDon Mullis part[lev] = NULL; 128835cc0c8SDon Mullis } 129835cc0c8SDon Mullis if (lev > max_lev) { 130835cc0c8SDon Mullis if (unlikely(lev >= ARRAY_SIZE(part)-1)) { 131d0da23b0SAndrew Morton printk_once(KERN_DEBUG "list too long for efficiency\n"); 132835cc0c8SDon Mullis lev--; 133835cc0c8SDon Mullis } 134835cc0c8SDon Mullis max_lev = lev; 135835cc0c8SDon Mullis } 136835cc0c8SDon Mullis part[lev] = cur; 1372c761270SDave Chinner } 1382c761270SDave Chinner 139835cc0c8SDon Mullis for (lev = 0; lev < max_lev; lev++) 140835cc0c8SDon Mullis if (part[lev]) 141835cc0c8SDon Mullis list = merge(priv, cmp, part[lev], list); 1422c761270SDave Chinner 143835cc0c8SDon Mullis merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); 1442c761270SDave Chinner } 1452c761270SDave Chinner EXPORT_SYMBOL(list_sort); 146