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 /*
11835cc0c8SDon Mullis * Returns a list organized in an intermediate format suited
12835cc0c8SDon Mullis * to chaining of merge() calls: null-terminated, no reserved or
13835cc0c8SDon Mullis * sentinel head node, "prev" links not maintained.
14835cc0c8SDon Mullis */
15043b3f7bSGeorge Spelvin __attribute__((nonnull(2,3,4)))
merge(void * priv,list_cmp_func_t cmp,struct list_head * a,struct list_head * b)164f0f586bSSami Tolvanen static struct list_head *merge(void *priv, list_cmp_func_t cmp,
17835cc0c8SDon Mullis struct list_head *a, struct list_head *b)
18835cc0c8SDon Mullis {
19043b3f7bSGeorge Spelvin struct list_head *head, **tail = &head;
20835cc0c8SDon Mullis
21043b3f7bSGeorge Spelvin for (;;) {
22835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */
23043b3f7bSGeorge Spelvin if (cmp(priv, a, b) <= 0) {
24043b3f7bSGeorge Spelvin *tail = a;
25043b3f7bSGeorge Spelvin tail = &a->next;
26835cc0c8SDon Mullis a = a->next;
27043b3f7bSGeorge Spelvin if (!a) {
28043b3f7bSGeorge Spelvin *tail = b;
29043b3f7bSGeorge Spelvin break;
30043b3f7bSGeorge Spelvin }
31835cc0c8SDon Mullis } else {
32043b3f7bSGeorge Spelvin *tail = b;
33043b3f7bSGeorge Spelvin tail = &b->next;
34835cc0c8SDon Mullis b = b->next;
35043b3f7bSGeorge Spelvin if (!b) {
36043b3f7bSGeorge Spelvin *tail = a;
37043b3f7bSGeorge Spelvin break;
38835cc0c8SDon Mullis }
39835cc0c8SDon Mullis }
40043b3f7bSGeorge Spelvin }
41043b3f7bSGeorge Spelvin return head;
42835cc0c8SDon Mullis }
43835cc0c8SDon Mullis
44835cc0c8SDon Mullis /*
45835cc0c8SDon Mullis * Combine final list merge with restoration of standard doubly-linked
46835cc0c8SDon Mullis * list structure. This approach duplicates code from merge(), but
47835cc0c8SDon Mullis * runs faster than the tidier alternatives of either a separate final
48835cc0c8SDon Mullis * prev-link restoration pass, or maintaining the prev links
49835cc0c8SDon Mullis * throughout.
50835cc0c8SDon Mullis */
51043b3f7bSGeorge Spelvin __attribute__((nonnull(2,3,4,5)))
merge_final(void * priv,list_cmp_func_t cmp,struct list_head * head,struct list_head * a,struct list_head * b)524f0f586bSSami Tolvanen static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
53835cc0c8SDon Mullis struct list_head *a, struct list_head *b)
54835cc0c8SDon Mullis {
55835cc0c8SDon Mullis struct list_head *tail = head;
5661b3d6c4SRasmus Villemoes u8 count = 0;
57835cc0c8SDon Mullis
58043b3f7bSGeorge Spelvin for (;;) {
59835cc0c8SDon Mullis /* if equal, take 'a' -- important for sort stability */
60043b3f7bSGeorge Spelvin if (cmp(priv, a, b) <= 0) {
61835cc0c8SDon Mullis tail->next = a;
62835cc0c8SDon Mullis a->prev = tail;
63043b3f7bSGeorge Spelvin tail = a;
64835cc0c8SDon Mullis a = a->next;
65043b3f7bSGeorge Spelvin if (!a)
66043b3f7bSGeorge Spelvin break;
67835cc0c8SDon Mullis } else {
68835cc0c8SDon Mullis tail->next = b;
69835cc0c8SDon Mullis b->prev = tail;
70043b3f7bSGeorge Spelvin tail = b;
71835cc0c8SDon Mullis b = b->next;
72043b3f7bSGeorge Spelvin if (!b) {
73043b3f7bSGeorge Spelvin b = a;
74043b3f7bSGeorge Spelvin break;
75835cc0c8SDon Mullis }
76835cc0c8SDon Mullis }
77043b3f7bSGeorge Spelvin }
78835cc0c8SDon Mullis
79043b3f7bSGeorge Spelvin /* Finish linking remainder of list b on to tail */
80043b3f7bSGeorge Spelvin tail->next = b;
81835cc0c8SDon Mullis do {
82835cc0c8SDon Mullis /*
83043b3f7bSGeorge Spelvin * If the merge is highly unbalanced (e.g. the input is
84043b3f7bSGeorge Spelvin * already sorted), this loop may run many iterations.
85835cc0c8SDon Mullis * Continue callbacks to the client even though no
86835cc0c8SDon Mullis * element comparison is needed, so the client's cmp()
87835cc0c8SDon Mullis * routine can invoke cond_resched() periodically.
88835cc0c8SDon Mullis */
89043b3f7bSGeorge Spelvin if (unlikely(!++count))
90043b3f7bSGeorge Spelvin cmp(priv, b, b);
91043b3f7bSGeorge Spelvin b->prev = tail;
92043b3f7bSGeorge Spelvin tail = b;
93043b3f7bSGeorge Spelvin b = b->next;
94043b3f7bSGeorge Spelvin } while (b);
95835cc0c8SDon Mullis
96043b3f7bSGeorge Spelvin /* And the final links to make a circular doubly-linked list */
97835cc0c8SDon Mullis tail->next = head;
98835cc0c8SDon Mullis head->prev = tail;
99835cc0c8SDon Mullis }
100835cc0c8SDon Mullis
1012c761270SDave Chinner /**
10202b12b7aSDon Mullis * list_sort - sort a list
10302b12b7aSDon Mullis * @priv: private data, opaque to list_sort(), passed to @cmp
1042c761270SDave Chinner * @head: the list to sort
1052c761270SDave Chinner * @cmp: the elements comparison function
1062c761270SDave Chinner *
107*9dbbc3b9SZhen Lei * The comparison function @cmp must return > 0 if @a should sort after
108043b3f7bSGeorge Spelvin * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
109043b3f7bSGeorge Spelvin * sort before @b *or* their original order should be preserved. It is
110043b3f7bSGeorge Spelvin * always called with the element that came first in the input in @a,
111043b3f7bSGeorge Spelvin * and list_sort is a stable sort, so it is not necessary to distinguish
112043b3f7bSGeorge Spelvin * the @a < @b and @a == @b cases.
113043b3f7bSGeorge Spelvin *
114043b3f7bSGeorge Spelvin * This is compatible with two styles of @cmp function:
115043b3f7bSGeorge Spelvin * - The traditional style which returns <0 / =0 / >0, or
116043b3f7bSGeorge Spelvin * - Returning a boolean 0/1.
117043b3f7bSGeorge Spelvin * The latter offers a chance to save a few cycles in the comparison
118043b3f7bSGeorge Spelvin * (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).
119043b3f7bSGeorge Spelvin *
120f35a1abdSJonathan Corbet * A good way to write a multi-word comparison is::
121f35a1abdSJonathan Corbet *
122043b3f7bSGeorge Spelvin * if (a->high != b->high)
123043b3f7bSGeorge Spelvin * return a->high > b->high;
124043b3f7bSGeorge Spelvin * if (a->middle != b->middle)
125043b3f7bSGeorge Spelvin * return a->middle > b->middle;
126043b3f7bSGeorge Spelvin * return a->low > b->low;
127b5c56e0cSGeorge Spelvin *
128b5c56e0cSGeorge Spelvin *
129b5c56e0cSGeorge Spelvin * This mergesort is as eager as possible while always performing at least
130b5c56e0cSGeorge Spelvin * 2:1 balanced merges. Given two pending sublists of size 2^k, they are
131b5c56e0cSGeorge Spelvin * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
132b5c56e0cSGeorge Spelvin *
133b5c56e0cSGeorge Spelvin * Thus, it will avoid cache thrashing as long as 3*2^k elements can
134b5c56e0cSGeorge Spelvin * fit into the cache. Not quite as good as a fully-eager bottom-up
135b5c56e0cSGeorge Spelvin * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
136b5c56e0cSGeorge Spelvin * the common case that everything fits into L1.
137b5c56e0cSGeorge Spelvin *
138b5c56e0cSGeorge Spelvin *
139b5c56e0cSGeorge Spelvin * The merging is controlled by "count", the number of elements in the
140e89b6358SToastC * pending lists. This is beautifully simple code, but rather subtle.
141b5c56e0cSGeorge Spelvin *
142b5c56e0cSGeorge Spelvin * Each time we increment "count", we set one bit (bit k) and clear
143b5c56e0cSGeorge Spelvin * bits k-1 .. 0. Each time this happens (except the very first time
144b5c56e0cSGeorge Spelvin * for each bit, when count increments to 2^k), we merge two lists of
145b5c56e0cSGeorge Spelvin * size 2^k into one list of size 2^(k+1).
146b5c56e0cSGeorge Spelvin *
147b5c56e0cSGeorge Spelvin * This merge happens exactly when the count reaches an odd multiple of
148b5c56e0cSGeorge Spelvin * 2^k, which is when we have 2^k elements pending in smaller lists,
149b5c56e0cSGeorge Spelvin * so it's safe to merge away two lists of size 2^k.
150b5c56e0cSGeorge Spelvin *
151b5c56e0cSGeorge Spelvin * After this happens twice, we have created two lists of size 2^(k+1),
152b5c56e0cSGeorge Spelvin * which will be merged into a list of size 2^(k+2) before we create
153b5c56e0cSGeorge Spelvin * a third list of size 2^(k+1), so there are never more than two pending.
154b5c56e0cSGeorge Spelvin *
155b5c56e0cSGeorge Spelvin * The number of pending lists of size 2^k is determined by the
156b5c56e0cSGeorge Spelvin * state of bit k of "count" plus two extra pieces of information:
1574ae5b8f2SMauro Carvalho Chehab *
158b5c56e0cSGeorge Spelvin * - The state of bit k-1 (when k == 0, consider bit -1 always set), and
159b5c56e0cSGeorge Spelvin * - Whether the higher-order bits are zero or non-zero (i.e.
160b5c56e0cSGeorge Spelvin * is count >= 2^(k+1)).
1614ae5b8f2SMauro Carvalho Chehab *
162b5c56e0cSGeorge Spelvin * There are six states we distinguish. "x" represents some arbitrary
163b5c56e0cSGeorge Spelvin * bits, and "y" represents some arbitrary non-zero bits:
164b5c56e0cSGeorge Spelvin * 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k
165b5c56e0cSGeorge Spelvin * 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
166b5c56e0cSGeorge Spelvin * 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
167b5c56e0cSGeorge Spelvin * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
168b5c56e0cSGeorge Spelvin * 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
169b5c56e0cSGeorge Spelvin * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
170b5c56e0cSGeorge Spelvin * (merge and loop back to state 2)
171b5c56e0cSGeorge Spelvin *
172b5c56e0cSGeorge Spelvin * We gain lists of size 2^k in the 2->3 and 4->5 transitions (because
173b5c56e0cSGeorge Spelvin * bit k-1 is set while the more significant bits are non-zero) and
174b5c56e0cSGeorge Spelvin * merge them away in the 5->2 transition. Note in particular that just
175b5c56e0cSGeorge Spelvin * before the 5->2 transition, all lower-order bits are 11 (state 3),
176b5c56e0cSGeorge Spelvin * so there is one list of each smaller size.
177b5c56e0cSGeorge Spelvin *
178b5c56e0cSGeorge Spelvin * When we reach the end of the input, we merge all the pending
179b5c56e0cSGeorge Spelvin * lists, from smallest to largest. If you work through cases 2 to
180b5c56e0cSGeorge Spelvin * 5 above, you can see that the number of elements we merge with a list
181b5c56e0cSGeorge Spelvin * of size 2^k varies from 2^(k-1) (cases 3 and 5 when x == 0) to
182b5c56e0cSGeorge Spelvin * 2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1).
1832c761270SDave Chinner */
184043b3f7bSGeorge Spelvin __attribute__((nonnull(2,3)))
list_sort(void * priv,struct list_head * head,list_cmp_func_t cmp)1854f0f586bSSami Tolvanen void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
1862c761270SDave Chinner {
187043b3f7bSGeorge Spelvin struct list_head *list = head->next, *pending = NULL;
188043b3f7bSGeorge Spelvin size_t count = 0; /* Count of pending */
1892c761270SDave Chinner
190043b3f7bSGeorge Spelvin if (list == head->prev) /* Zero or one elements */
1912c761270SDave Chinner return;
1922c761270SDave Chinner
193043b3f7bSGeorge Spelvin /* Convert to a null-terminated singly-linked list. */
194835cc0c8SDon Mullis head->prev->next = NULL;
1952c761270SDave Chinner
196043b3f7bSGeorge Spelvin /*
197043b3f7bSGeorge Spelvin * Data structure invariants:
198043b3f7bSGeorge Spelvin * - All lists are singly linked and null-terminated; prev
199043b3f7bSGeorge Spelvin * pointers are not maintained.
200043b3f7bSGeorge Spelvin * - pending is a prev-linked "list of lists" of sorted
201043b3f7bSGeorge Spelvin * sublists awaiting further merging.
202b5c56e0cSGeorge Spelvin * - Each of the sorted sublists is power-of-two in size.
203043b3f7bSGeorge Spelvin * - Sublists are sorted by size and age, smallest & newest at front.
204b5c56e0cSGeorge Spelvin * - There are zero to two sublists of each size.
205b5c56e0cSGeorge Spelvin * - A pair of pending sublists are merged as soon as the number
206b5c56e0cSGeorge Spelvin * of following pending elements equals their size (i.e.
207b5c56e0cSGeorge Spelvin * each time count reaches an odd multiple of that size).
208b5c56e0cSGeorge Spelvin * That ensures each later final merge will be at worst 2:1.
209b5c56e0cSGeorge Spelvin * - Each round consists of:
210b5c56e0cSGeorge Spelvin * - Merging the two sublists selected by the highest bit
211b5c56e0cSGeorge Spelvin * which flips when count is incremented, and
212b5c56e0cSGeorge Spelvin * - Adding an element from the input as a size-1 sublist.
213043b3f7bSGeorge Spelvin */
214043b3f7bSGeorge Spelvin do {
215043b3f7bSGeorge Spelvin size_t bits;
216b5c56e0cSGeorge Spelvin struct list_head **tail = &pending;
217043b3f7bSGeorge Spelvin
218b5c56e0cSGeorge Spelvin /* Find the least-significant clear bit in count */
219b5c56e0cSGeorge Spelvin for (bits = count; bits & 1; bits >>= 1)
220b5c56e0cSGeorge Spelvin tail = &(*tail)->prev;
221b5c56e0cSGeorge Spelvin /* Do the indicated merge */
222b5c56e0cSGeorge Spelvin if (likely(bits)) {
223b5c56e0cSGeorge Spelvin struct list_head *a = *tail, *b = a->prev;
224835cc0c8SDon Mullis
2254f0f586bSSami Tolvanen a = merge(priv, cmp, b, a);
226b5c56e0cSGeorge Spelvin /* Install the merged result in place of the inputs */
227b5c56e0cSGeorge Spelvin a->prev = b->prev;
228b5c56e0cSGeorge Spelvin *tail = a;
229835cc0c8SDon Mullis }
2302c761270SDave Chinner
231b5c56e0cSGeorge Spelvin /* Move one element from input list to pending */
232b5c56e0cSGeorge Spelvin list->prev = pending;
233b5c56e0cSGeorge Spelvin pending = list;
234b5c56e0cSGeorge Spelvin list = list->next;
235b5c56e0cSGeorge Spelvin pending->next = NULL;
236b5c56e0cSGeorge Spelvin count++;
237b5c56e0cSGeorge Spelvin } while (list);
238b5c56e0cSGeorge Spelvin
239b5c56e0cSGeorge Spelvin /* End of input; merge together all the pending lists. */
240b5c56e0cSGeorge Spelvin list = pending;
241043b3f7bSGeorge Spelvin pending = pending->prev;
242b5c56e0cSGeorge Spelvin for (;;) {
243b5c56e0cSGeorge Spelvin struct list_head *next = pending->prev;
244b5c56e0cSGeorge Spelvin
245b5c56e0cSGeorge Spelvin if (!next)
246b5c56e0cSGeorge Spelvin break;
2474f0f586bSSami Tolvanen list = merge(priv, cmp, pending, list);
248b5c56e0cSGeorge Spelvin pending = next;
249043b3f7bSGeorge Spelvin }
250043b3f7bSGeorge Spelvin /* The final merge, rebuilding prev links */
2514f0f586bSSami Tolvanen merge_final(priv, cmp, head, pending, list);
2522c761270SDave Chinner }
2532c761270SDave Chinner EXPORT_SYMBOL(list_sort);
254