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 10043b3f7bSGeorge Spelvin typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *, 11043b3f7bSGeorge Spelvin struct list_head const *, struct list_head const *); 12835cc0c8SDon Mullis 13835cc0c8SDon Mullis /* 14835cc0c8SDon Mullis * Returns a list organized in an intermediate format suited 15835cc0c8SDon Mullis * to chaining of merge() calls: null-terminated, no reserved or 16835cc0c8SDon Mullis * sentinel head node, "prev" links not maintained. 17835cc0c8SDon Mullis */ 18043b3f7bSGeorge Spelvin __attribute__((nonnull(2,3,4))) 19043b3f7bSGeorge Spelvin static struct list_head *merge(void *priv, cmp_func cmp, 20835cc0c8SDon Mullis struct list_head *a, struct list_head *b) 21835cc0c8SDon Mullis { 22043b3f7bSGeorge Spelvin struct list_head *head, **tail = &head; 23835cc0c8SDon Mullis 24043b3f7bSGeorge Spelvin for (;;) { 25835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */ 26043b3f7bSGeorge Spelvin if (cmp(priv, a, b) <= 0) { 27043b3f7bSGeorge Spelvin *tail = a; 28043b3f7bSGeorge Spelvin tail = &a->next; 29835cc0c8SDon Mullis a = a->next; 30043b3f7bSGeorge Spelvin if (!a) { 31043b3f7bSGeorge Spelvin *tail = b; 32043b3f7bSGeorge Spelvin break; 33043b3f7bSGeorge Spelvin } 34835cc0c8SDon Mullis } else { 35043b3f7bSGeorge Spelvin *tail = b; 36043b3f7bSGeorge Spelvin tail = &b->next; 37835cc0c8SDon Mullis b = b->next; 38043b3f7bSGeorge Spelvin if (!b) { 39043b3f7bSGeorge Spelvin *tail = a; 40043b3f7bSGeorge Spelvin break; 41835cc0c8SDon Mullis } 42835cc0c8SDon Mullis } 43043b3f7bSGeorge Spelvin } 44043b3f7bSGeorge Spelvin return head; 45835cc0c8SDon Mullis } 46835cc0c8SDon Mullis 47835cc0c8SDon Mullis /* 48835cc0c8SDon Mullis * Combine final list merge with restoration of standard doubly-linked 49835cc0c8SDon Mullis * list structure. This approach duplicates code from merge(), but 50835cc0c8SDon Mullis * runs faster than the tidier alternatives of either a separate final 51835cc0c8SDon Mullis * prev-link restoration pass, or maintaining the prev links 52835cc0c8SDon Mullis * throughout. 53835cc0c8SDon Mullis */ 54043b3f7bSGeorge Spelvin __attribute__((nonnull(2,3,4,5))) 55043b3f7bSGeorge Spelvin static void merge_final(void *priv, cmp_func cmp, struct list_head *head, 56835cc0c8SDon Mullis struct list_head *a, struct list_head *b) 57835cc0c8SDon Mullis { 58835cc0c8SDon Mullis struct list_head *tail = head; 5961b3d6c4SRasmus Villemoes u8 count = 0; 60835cc0c8SDon Mullis 61043b3f7bSGeorge Spelvin for (;;) { 62835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */ 63043b3f7bSGeorge Spelvin if (cmp(priv, a, b) <= 0) { 64835cc0c8SDon Mullis tail->next = a; 65835cc0c8SDon Mullis a->prev = tail; 66043b3f7bSGeorge Spelvin tail = a; 67835cc0c8SDon Mullis a = a->next; 68043b3f7bSGeorge Spelvin if (!a) 69043b3f7bSGeorge Spelvin break; 70835cc0c8SDon Mullis } else { 71835cc0c8SDon Mullis tail->next = b; 72835cc0c8SDon Mullis b->prev = tail; 73043b3f7bSGeorge Spelvin tail = b; 74835cc0c8SDon Mullis b = b->next; 75043b3f7bSGeorge Spelvin if (!b) { 76043b3f7bSGeorge Spelvin b = a; 77043b3f7bSGeorge Spelvin break; 78835cc0c8SDon Mullis } 79835cc0c8SDon Mullis } 80043b3f7bSGeorge Spelvin } 81835cc0c8SDon Mullis 82043b3f7bSGeorge Spelvin /* Finish linking remainder of list b on to tail */ 83043b3f7bSGeorge Spelvin tail->next = b; 84835cc0c8SDon Mullis do { 85835cc0c8SDon Mullis /* 86043b3f7bSGeorge Spelvin * If the merge is highly unbalanced (e.g. the input is 87043b3f7bSGeorge Spelvin * already sorted), this loop may run many iterations. 88835cc0c8SDon Mullis * Continue callbacks to the client even though no 89835cc0c8SDon Mullis * element comparison is needed, so the client's cmp() 90835cc0c8SDon Mullis * routine can invoke cond_resched() periodically. 91835cc0c8SDon Mullis */ 92043b3f7bSGeorge Spelvin if (unlikely(!++count)) 93043b3f7bSGeorge Spelvin cmp(priv, b, b); 94043b3f7bSGeorge Spelvin b->prev = tail; 95043b3f7bSGeorge Spelvin tail = b; 96043b3f7bSGeorge Spelvin b = b->next; 97043b3f7bSGeorge Spelvin } while (b); 98835cc0c8SDon Mullis 99043b3f7bSGeorge Spelvin /* And the final links to make a circular doubly-linked list */ 100835cc0c8SDon Mullis tail->next = head; 101835cc0c8SDon Mullis head->prev = tail; 102835cc0c8SDon Mullis } 103835cc0c8SDon Mullis 1042c761270SDave Chinner /** 10502b12b7aSDon Mullis * list_sort - sort a list 10602b12b7aSDon Mullis * @priv: private data, opaque to list_sort(), passed to @cmp 1072c761270SDave Chinner * @head: the list to sort 1082c761270SDave Chinner * @cmp: the elements comparison function 1092c761270SDave Chinner * 110043b3f7bSGeorge Spelvin * This function implements a bottom-up merge sort, which has O(nlog(n)) 111043b3f7bSGeorge Spelvin * complexity. We use depth-first order to take advantage of cacheing. 112043b3f7bSGeorge Spelvin * (E.g. when we get to the fourth element, we immediately merge the 113043b3f7bSGeorge Spelvin * first two 2-element lists.) 1142c761270SDave Chinner * 115043b3f7bSGeorge Spelvin * The comparison funtion @cmp must return > 0 if @a should sort after 116043b3f7bSGeorge Spelvin * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should 117043b3f7bSGeorge Spelvin * sort before @b *or* their original order should be preserved. It is 118043b3f7bSGeorge Spelvin * always called with the element that came first in the input in @a, 119043b3f7bSGeorge Spelvin * and list_sort is a stable sort, so it is not necessary to distinguish 120043b3f7bSGeorge Spelvin * the @a < @b and @a == @b cases. 121043b3f7bSGeorge Spelvin * 122043b3f7bSGeorge Spelvin * This is compatible with two styles of @cmp function: 123043b3f7bSGeorge Spelvin * - The traditional style which returns <0 / =0 / >0, or 124043b3f7bSGeorge Spelvin * - Returning a boolean 0/1. 125043b3f7bSGeorge Spelvin * The latter offers a chance to save a few cycles in the comparison 126043b3f7bSGeorge Spelvin * (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c). 127043b3f7bSGeorge Spelvin * 128043b3f7bSGeorge Spelvin * A good way to write a multi-word comparison is 129043b3f7bSGeorge Spelvin * if (a->high != b->high) 130043b3f7bSGeorge Spelvin * return a->high > b->high; 131043b3f7bSGeorge Spelvin * if (a->middle != b->middle) 132043b3f7bSGeorge Spelvin * return a->middle > b->middle; 133043b3f7bSGeorge Spelvin * return a->low > b->low; 1342c761270SDave Chinner */ 135043b3f7bSGeorge Spelvin __attribute__((nonnull(2,3))) 1362c761270SDave Chinner void list_sort(void *priv, struct list_head *head, 1372c761270SDave Chinner int (*cmp)(void *priv, struct list_head *a, 1382c761270SDave Chinner struct list_head *b)) 1392c761270SDave Chinner { 140043b3f7bSGeorge Spelvin struct list_head *list = head->next, *pending = NULL; 141043b3f7bSGeorge Spelvin size_t count = 0; /* Count of pending */ 1422c761270SDave Chinner 143043b3f7bSGeorge Spelvin if (list == head->prev) /* Zero or one elements */ 1442c761270SDave Chinner return; 1452c761270SDave Chinner 146043b3f7bSGeorge Spelvin /* Convert to a null-terminated singly-linked list. */ 147835cc0c8SDon Mullis head->prev->next = NULL; 1482c761270SDave Chinner 149043b3f7bSGeorge Spelvin /* 150043b3f7bSGeorge Spelvin * Data structure invariants: 151043b3f7bSGeorge Spelvin * - All lists are singly linked and null-terminated; prev 152043b3f7bSGeorge Spelvin * pointers are not maintained. 153043b3f7bSGeorge Spelvin * - pending is a prev-linked "list of lists" of sorted 154043b3f7bSGeorge Spelvin * sublists awaiting further merging. 155043b3f7bSGeorge Spelvin * - Each of the sorted sublists is power-of-two in size, 156043b3f7bSGeorge Spelvin * corresponding to bits set in "count". 157043b3f7bSGeorge Spelvin * - Sublists are sorted by size and age, smallest & newest at front. 158043b3f7bSGeorge Spelvin */ 159043b3f7bSGeorge Spelvin do { 160043b3f7bSGeorge Spelvin size_t bits; 161835cc0c8SDon Mullis struct list_head *cur = list; 162043b3f7bSGeorge Spelvin 163043b3f7bSGeorge Spelvin /* Extract the head of "list" as a single-element list "cur" */ 164835cc0c8SDon Mullis list = list->next; 165835cc0c8SDon Mullis cur->next = NULL; 166835cc0c8SDon Mullis 167043b3f7bSGeorge Spelvin /* Do merges corresponding to set lsbits in count */ 168043b3f7bSGeorge Spelvin for (bits = count; bits & 1; bits >>= 1) { 169043b3f7bSGeorge Spelvin cur = merge(priv, (cmp_func)cmp, pending, cur); 170043b3f7bSGeorge Spelvin pending = pending->prev; /* Untouched by merge() */ 171835cc0c8SDon Mullis } 172043b3f7bSGeorge Spelvin /* And place the result at the head of "pending" */ 173043b3f7bSGeorge Spelvin cur->prev = pending; 174043b3f7bSGeorge Spelvin pending = cur; 175043b3f7bSGeorge Spelvin count++; 176043b3f7bSGeorge Spelvin } while (list->next); 1772c761270SDave Chinner 178043b3f7bSGeorge Spelvin /* Now merge together last element with all pending lists */ 179043b3f7bSGeorge Spelvin while (pending->prev) { 180043b3f7bSGeorge Spelvin list = merge(priv, (cmp_func)cmp, pending, list); 181043b3f7bSGeorge Spelvin pending = pending->prev; 182043b3f7bSGeorge Spelvin } 183043b3f7bSGeorge Spelvin /* The final merge, rebuilding prev links */ 184043b3f7bSGeorge Spelvin merge_final(priv, (cmp_func)cmp, head, pending, list); 1852c761270SDave Chinner } 1862c761270SDave Chinner EXPORT_SYMBOL(list_sort); 187