linux-6.12.1/lib/list_sort.c

15 __attribute__((nonnull(2,3,4)))
51 __attribute__((nonnull(2,3,4,5)))
130  * 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
131  * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
133  * Thus, it will avoid cache thrashing as long as 3*2^k elements can
142  * Each time we increment "count", we set one bit (bit k) and clear
143  * bits k-1 .. 0.  Each time this happens (except the very first time
144  * for each bit, when count increments to 2^k), we merge two lists of
145  * size 2^k into one list of size 2^(k+1).
148  * 2^k, which is when we have 2^k elements pending in smaller lists,
149  * so it's safe to merge away two lists of size 2^k.
151  * After this happens twice, we have created two lists of size 2^(k+1),
152  * which will be merged into a list of size 2^(k+2) before we create
153  * a third list of size 2^(k+1), so there are never more than two pending.
155  * The number of pending lists of size 2^k is determined by the
156  * state of bit k of "count" plus two extra pieces of information:
158  * - The state of bit k-1 (when k == 0, consider bit -1 always set), and
160  *   is count >= 2^(k+1)).
164  * 0:  00x: 0 pending of size 2^k;           x pending of sizes < 2^k
165  * 1:  01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
166  * 2: x10x: 0 pending of size 2^k; 2^k     + x pending of sizes < 2^k
167  * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
168  * 4: y00x: 1 pending of size 2^k; 2^k     + x pending of sizes < 2^k
169  * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
170  * (merge and loop back to state 2)
172  * We gain lists of size 2^k in the 2->3 and 4->5 transitions (because
173  * bit k-1 is set while the more significant bits are non-zero) and
174  * merge them away in the 5->2 transition.  Note in particular that just
175  * before the 5->2 transition, all lower-order bits are 11 (state 3),
179  * lists, from smallest to largest.  If you work through cases 2 to
181  * of size 2^k varies from 2^(k-1) (cases 3 and 5 when x == 0) to
182  * 2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1).
184 __attribute__((nonnull(2,3)))
208 	 *   That ensures each later final merge will be at worst 2:1.  in list_sort()