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 * The comparison funtion @cmp must return > 0 if @a should sort after 111043b3f7bSGeorge Spelvin * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should 112043b3f7bSGeorge Spelvin * sort before @b *or* their original order should be preserved. It is 113043b3f7bSGeorge Spelvin * always called with the element that came first in the input in @a, 114043b3f7bSGeorge Spelvin * and list_sort is a stable sort, so it is not necessary to distinguish 115043b3f7bSGeorge Spelvin * the @a < @b and @a == @b cases. 116043b3f7bSGeorge Spelvin * 117043b3f7bSGeorge Spelvin * This is compatible with two styles of @cmp function: 118043b3f7bSGeorge Spelvin * - The traditional style which returns <0 / =0 / >0, or 119043b3f7bSGeorge Spelvin * - Returning a boolean 0/1. 120043b3f7bSGeorge Spelvin * The latter offers a chance to save a few cycles in the comparison 121043b3f7bSGeorge Spelvin * (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c). 122043b3f7bSGeorge Spelvin * 123f35a1abdSJonathan Corbet * A good way to write a multi-word comparison is:: 124f35a1abdSJonathan Corbet * 125043b3f7bSGeorge Spelvin * if (a->high != b->high) 126043b3f7bSGeorge Spelvin * return a->high > b->high; 127043b3f7bSGeorge Spelvin * if (a->middle != b->middle) 128043b3f7bSGeorge Spelvin * return a->middle > b->middle; 129043b3f7bSGeorge Spelvin * return a->low > b->low; 130b5c56e0cSGeorge Spelvin * 131b5c56e0cSGeorge Spelvin * 132b5c56e0cSGeorge Spelvin * This mergesort is as eager as possible while always performing at least 133b5c56e0cSGeorge Spelvin * 2:1 balanced merges. Given two pending sublists of size 2^k, they are 134b5c56e0cSGeorge Spelvin * merged to a size-2^(k+1) list as soon as we have 2^k following elements. 135b5c56e0cSGeorge Spelvin * 136b5c56e0cSGeorge Spelvin * Thus, it will avoid cache thrashing as long as 3*2^k elements can 137b5c56e0cSGeorge Spelvin * fit into the cache. Not quite as good as a fully-eager bottom-up 138b5c56e0cSGeorge Spelvin * mergesort, but it does use 0.2*n fewer comparisons, so is faster in 139b5c56e0cSGeorge Spelvin * the common case that everything fits into L1. 140b5c56e0cSGeorge Spelvin * 141b5c56e0cSGeorge Spelvin * 142b5c56e0cSGeorge Spelvin * The merging is controlled by "count", the number of elements in the 143b5c56e0cSGeorge Spelvin * pending lists. This is beautiully simple code, but rather subtle. 144b5c56e0cSGeorge Spelvin * 145b5c56e0cSGeorge Spelvin * Each time we increment "count", we set one bit (bit k) and clear 146b5c56e0cSGeorge Spelvin * bits k-1 .. 0. Each time this happens (except the very first time 147b5c56e0cSGeorge Spelvin * for each bit, when count increments to 2^k), we merge two lists of 148b5c56e0cSGeorge Spelvin * size 2^k into one list of size 2^(k+1). 149b5c56e0cSGeorge Spelvin * 150b5c56e0cSGeorge Spelvin * This merge happens exactly when the count reaches an odd multiple of 151b5c56e0cSGeorge Spelvin * 2^k, which is when we have 2^k elements pending in smaller lists, 152b5c56e0cSGeorge Spelvin * so it's safe to merge away two lists of size 2^k. 153b5c56e0cSGeorge Spelvin * 154b5c56e0cSGeorge Spelvin * After this happens twice, we have created two lists of size 2^(k+1), 155b5c56e0cSGeorge Spelvin * which will be merged into a list of size 2^(k+2) before we create 156b5c56e0cSGeorge Spelvin * a third list of size 2^(k+1), so there are never more than two pending. 157b5c56e0cSGeorge Spelvin * 158b5c56e0cSGeorge Spelvin * The number of pending lists of size 2^k is determined by the 159b5c56e0cSGeorge Spelvin * state of bit k of "count" plus two extra pieces of information: 160b5c56e0cSGeorge Spelvin * - The state of bit k-1 (when k == 0, consider bit -1 always set), and 161b5c56e0cSGeorge Spelvin * - Whether the higher-order bits are zero or non-zero (i.e. 162b5c56e0cSGeorge Spelvin * is count >= 2^(k+1)). 163b5c56e0cSGeorge Spelvin * There are six states we distinguish. "x" represents some arbitrary 164b5c56e0cSGeorge Spelvin * bits, and "y" represents some arbitrary non-zero bits: 165b5c56e0cSGeorge Spelvin * 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k 166b5c56e0cSGeorge Spelvin * 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k 167b5c56e0cSGeorge Spelvin * 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k 168b5c56e0cSGeorge Spelvin * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k 169b5c56e0cSGeorge Spelvin * 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k 170b5c56e0cSGeorge Spelvin * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k 171b5c56e0cSGeorge Spelvin * (merge and loop back to state 2) 172b5c56e0cSGeorge Spelvin * 173b5c56e0cSGeorge Spelvin * We gain lists of size 2^k in the 2->3 and 4->5 transitions (because 174b5c56e0cSGeorge Spelvin * bit k-1 is set while the more significant bits are non-zero) and 175b5c56e0cSGeorge Spelvin * merge them away in the 5->2 transition. Note in particular that just 176b5c56e0cSGeorge Spelvin * before the 5->2 transition, all lower-order bits are 11 (state 3), 177b5c56e0cSGeorge Spelvin * so there is one list of each smaller size. 178b5c56e0cSGeorge Spelvin * 179b5c56e0cSGeorge Spelvin * When we reach the end of the input, we merge all the pending 180b5c56e0cSGeorge Spelvin * lists, from smallest to largest. If you work through cases 2 to 181b5c56e0cSGeorge Spelvin * 5 above, you can see that the number of elements we merge with a list 182b5c56e0cSGeorge Spelvin * of size 2^k varies from 2^(k-1) (cases 3 and 5 when x == 0) to 183b5c56e0cSGeorge Spelvin * 2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1). 1842c761270SDave Chinner */ 185043b3f7bSGeorge Spelvin __attribute__((nonnull(2,3))) 1862c761270SDave Chinner void list_sort(void *priv, struct list_head *head, 1872c761270SDave Chinner int (*cmp)(void *priv, struct list_head *a, 1882c761270SDave Chinner struct list_head *b)) 1892c761270SDave Chinner { 190043b3f7bSGeorge Spelvin struct list_head *list = head->next, *pending = NULL; 191043b3f7bSGeorge Spelvin size_t count = 0; /* Count of pending */ 1922c761270SDave Chinner 193043b3f7bSGeorge Spelvin if (list == head->prev) /* Zero or one elements */ 1942c761270SDave Chinner return; 1952c761270SDave Chinner 196043b3f7bSGeorge Spelvin /* Convert to a null-terminated singly-linked list. */ 197835cc0c8SDon Mullis head->prev->next = NULL; 1982c761270SDave Chinner 199043b3f7bSGeorge Spelvin /* 200043b3f7bSGeorge Spelvin * Data structure invariants: 201043b3f7bSGeorge Spelvin * - All lists are singly linked and null-terminated; prev 202043b3f7bSGeorge Spelvin * pointers are not maintained. 203043b3f7bSGeorge Spelvin * - pending is a prev-linked "list of lists" of sorted 204043b3f7bSGeorge Spelvin * sublists awaiting further merging. 205b5c56e0cSGeorge Spelvin * - Each of the sorted sublists is power-of-two in size. 206043b3f7bSGeorge Spelvin * - Sublists are sorted by size and age, smallest & newest at front. 207b5c56e0cSGeorge Spelvin * - There are zero to two sublists of each size. 208b5c56e0cSGeorge Spelvin * - A pair of pending sublists are merged as soon as the number 209b5c56e0cSGeorge Spelvin * of following pending elements equals their size (i.e. 210b5c56e0cSGeorge Spelvin * each time count reaches an odd multiple of that size). 211b5c56e0cSGeorge Spelvin * That ensures each later final merge will be at worst 2:1. 212b5c56e0cSGeorge Spelvin * - Each round consists of: 213b5c56e0cSGeorge Spelvin * - Merging the two sublists selected by the highest bit 214b5c56e0cSGeorge Spelvin * which flips when count is incremented, and 215b5c56e0cSGeorge Spelvin * - Adding an element from the input as a size-1 sublist. 216043b3f7bSGeorge Spelvin */ 217043b3f7bSGeorge Spelvin do { 218043b3f7bSGeorge Spelvin size_t bits; 219b5c56e0cSGeorge Spelvin struct list_head **tail = &pending; 220043b3f7bSGeorge Spelvin 221b5c56e0cSGeorge Spelvin /* Find the least-significant clear bit in count */ 222b5c56e0cSGeorge Spelvin for (bits = count; bits & 1; bits >>= 1) 223b5c56e0cSGeorge Spelvin tail = &(*tail)->prev; 224b5c56e0cSGeorge Spelvin /* Do the indicated merge */ 225b5c56e0cSGeorge Spelvin if (likely(bits)) { 226b5c56e0cSGeorge Spelvin struct list_head *a = *tail, *b = a->prev; 227835cc0c8SDon Mullis 228b5c56e0cSGeorge Spelvin a = merge(priv, (cmp_func)cmp, b, a); 229b5c56e0cSGeorge Spelvin /* Install the merged result in place of the inputs */ 230b5c56e0cSGeorge Spelvin a->prev = b->prev; 231b5c56e0cSGeorge Spelvin *tail = a; 232835cc0c8SDon Mullis } 2332c761270SDave Chinner 234b5c56e0cSGeorge Spelvin /* Move one element from input list to pending */ 235b5c56e0cSGeorge Spelvin list->prev = pending; 236b5c56e0cSGeorge Spelvin pending = list; 237b5c56e0cSGeorge Spelvin list = list->next; 238b5c56e0cSGeorge Spelvin pending->next = NULL; 239b5c56e0cSGeorge Spelvin count++; 240b5c56e0cSGeorge Spelvin } while (list); 241b5c56e0cSGeorge Spelvin 242b5c56e0cSGeorge Spelvin /* End of input; merge together all the pending lists. */ 243b5c56e0cSGeorge Spelvin list = pending; 244043b3f7bSGeorge Spelvin pending = pending->prev; 245b5c56e0cSGeorge Spelvin for (;;) { 246b5c56e0cSGeorge Spelvin struct list_head *next = pending->prev; 247b5c56e0cSGeorge Spelvin 248b5c56e0cSGeorge Spelvin if (!next) 249b5c56e0cSGeorge Spelvin break; 250b5c56e0cSGeorge Spelvin list = merge(priv, (cmp_func)cmp, pending, list); 251b5c56e0cSGeorge Spelvin pending = next; 252043b3f7bSGeorge Spelvin } 253043b3f7bSGeorge Spelvin /* The final merge, rebuilding prev links */ 254043b3f7bSGeorge Spelvin merge_final(priv, (cmp_func)cmp, head, pending, list); 2552c761270SDave Chinner } 2562c761270SDave Chinner EXPORT_SYMBOL(list_sort); 257