8  * Returns a list organized in an intermediate format suited
12 __attribute__((nonnull(2,3,4)))
14 				struct list_head *a, struct list_head *b)  in merge()  argument
19 		/* if equal, take 'a' -- important for sort stability */  in merge()
20 		if (cmp(priv, a, b) <= 0) {  in merge()
21 			*tail = a;  in merge()
22 			tail = &a->next;  in merge()
23 			a = a->next;  in merge()
24 			if (!a) {  in merge()
33 				*tail = a;  in merge()
44  * runs faster than the tidier alternatives of either a separate final
48 __attribute__((nonnull(2,3,4,5)))
50 			struct list_head *a, struct list_head *b)  in merge_final()  argument
56 		/* if equal, take 'a' -- important for sort stability */  in merge_final()
57 		if (cmp(priv, a, b) <= 0) {  in merge_final()
58 			tail->next = a;  in merge_final()
59 			a->prev = tail;  in merge_final()
60 			tail = a;  in merge_final()
61 			a = a->next;  in merge_final()
62 			if (!a)  in merge_final()
70 				b = a;  in merge_final()
93 	/* And the final links to make a circular doubly-linked list */  in merge_final()
99  * list_sort - sort a list
104  * The comparison function @cmp must return > 0 if @a should sort after
105  * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
107  * always called with the element that came first in the input in @a,
108  * and list_sort is a stable sort, so it is not necessary to distinguish
109  * the @a < @b and @a == @b cases.
113  * - Antisymmetry: cmp(@a, @b) must return the opposite sign of
114  * cmp(@b, @a).
115  * - Transitivity: if cmp(@a, @b) <= 0 and cmp(@b, @c) <= 0, then
116  * cmp(@a, @c) <= 0.
120  * - Returning a boolean 0/1.
121  * The latter offers a chance to save a few cycles in the comparison
124  * A good way to write a multi-word comparison is::
126  *	if (a->high != b->high)
127  *		return a->high > b->high;
128  *	if (a->middle != b->middle)
129  *		return a->middle > b->middle;
130  *	return a->low > b->low;
134  * 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
135  * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
137  * Thus, it will avoid cache thrashing as long as 3*2^k elements can
138  * fit into the cache.  Not quite as good as a fully-eager bottom-up
148  * for each bit, when count increments to 2^k), we merge two lists of
149  * size 2^k into one list of size 2^(k+1).
152  * 2^k, which is when we have 2^k elements pending in smaller lists,
153  * so it's safe to merge away two lists of size 2^k.
155  * After this happens twice, we have created two lists of size 2^(k+1),
156  * which will be merged into a list of size 2^(k+2) before we create
157  * a third list of size 2^(k+1), so there are never more than two pending.
159  * The number of pending lists of size 2^k is determined by the
164  *   is count >= 2^(k+1)).
168  * 0:  00x: 0 pending of size 2^k;           x pending of sizes < 2^k
169  * 1:  01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
170  * 2: x10x: 0 pending of size 2^k; 2^k     + x pending of sizes < 2^k
171  * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
172  * 4: y00x: 1 pending of size 2^k; 2^k     + x pending of sizes < 2^k
173  * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
174  * (merge and loop back to state 2)
176  * We gain lists of size 2^k in the 2->3 and 4->5 transitions (because
178  * merge them away in the 5->2 transition.  Note in particular that just
179  * before the 5->2 transition, all lower-order bits are 11 (state 3),
183  * lists, from smallest to largest.  If you work through cases 2 to
184  * 5 above, you can see that the number of elements we merge with a list
185  * of size 2^k varies from 2^(k-1) (cases 3 and 5 when x == 0) to
186  * 2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1).
188 __attribute__((nonnull(2,3)))
197 	/* Convert to a null-terminated singly-linked list. */  in list_sort()
204 	 * - pending is a prev-linked "list of lists" of sorted  in list_sort()
209 	 * - A pair of pending sublists are merged as soon as the number  in list_sort()
212 	 *   That ensures each later final merge will be at worst 2:1.  in list_sort()
216 	 *   - Adding an element from the input as a size-1 sublist.  in list_sort()
227 			struct list_head *a = *tail, *b = a->prev;  in list_sort()  local
229 			a = merge(priv, cmp, b, a);  in list_sort()
231 			a->prev = b->prev;  in list_sort()
232 			*tail = a;  in list_sort()