linux-6.15/lib/sort.c

1 // SPDX-License-Identifier: GPL-2.0
3  * A fast, small, non-recursive O(n log n) sort for the Linux kernel
6  * and 1.5*n*log2(n) + O(n) in the (very contrived) worst case.
8  * Quicksort manages n*log2(n) - 1.26*n for random inputs (1.63*n
9  * better) at the expense of stack usage and much larger code to avoid
18  * is_aligned - is this pointer & size okay for word-wide copying?
23  * Returns true if elements can be copied using word loads and stores.
24  * The size must be a multiple of the alignment, and the base address must
39 	return (lsbits & (align - 1)) == 0;  in is_aligned()
43  * swap_words_32 - swap two elements in 32-bit chunks
44  * @a: pointer to the first element to swap
45  * @b: pointer to the second element to swap
59 		u32 t = *(u32 *)(a + (n -= 4));  in swap_words_32()
66  * swap_words_64 - swap two elements in 64-bit chunks
67  * @a: pointer to the first element to swap
68  * @b: pointer to the second element to swap
75  * We'd like to use 64-bit loads if possible.  If they're not, emulating
77  * processors do not.  If CONFIG_64BIT, we definitely have 64-bit loads,
78  * but it's possible to have 64-bit loads without 64-bit pointers (e.g.
85 		u64 t = *(u64 *)(a + (n -= 8));  in swap_words_64()
89 		/* Use two 32-bit transfers to avoid base+index+4 addressing */  in swap_words_64()
90 		u32 t = *(u32 *)(a + (n -= 4));  in swap_words_64()
94 		t = *(u32 *)(a + (n -= 4));  in swap_words_64()
102  * swap_bytes - swap two elements a byte at a time
103  * @a: pointer to the first element to swap
104  * @b: pointer to the second element to swap
112 		char t = ((char *)a)[--n];  in swap_bytes()
120  * a pointer, but small integers make for the smallest compare
130 	swap_func_t swap;  member
140 		((const struct wrapper *)priv)->swap(a, b, (int)size);  in do_swap()
159 		return ((const struct wrapper *)priv)->cmp(a, b);  in do_cmp()
164  * parent - given the offset of the child, find the offset of the parent.
165  * @i: the offset of the heap element whose parent is sought.  Non-zero.
166  * @lsbit: a precomputed 1-bit mask, equal to "size & -size"
170  * (j-1)/2.  But when working in byte offsets, we can't use implicit
175  * an even multiple of @size, and set if it's an odd multiple.
177  * Logically, we're doing "if (i & lsbit) i -= size;", but since the
178  * branch is unpredictable, it's done with a bit of clever branch-free
184 	i -= size;  in parent()
185 	i -= size & -(i & lsbit);  in parent()
197 	/* pre-scale counters for performance */  in __sort_r()
199 	const unsigned int lsbit = size & -size;  /* Used to find parent */  in __sort_r()
205 	/* called from 'sort' without swap function, let's pick the default */  in __sort_r()
206 	if (swap_func == SWAP_WRAPPER && !((struct wrapper *)priv)->swap)  in __sort_r()
220 	 * 1. elements [a,n) satisfy the heap property (compare greater than  in __sort_r()
222 	 * 2. elements [n,num*size) are sorted, and  in __sort_r()
229 			a -= size << shift;  in __sort_r()
231 			n -= size;  in __sort_r()
235 			n -= size;  in __sort_r()
243 		 * "bottom-up" variant, which significantly reduces  in __sort_r()
244 		 * calls to cmp_func(): we find the sift-down path all  in __sort_r()
245 		 * the way to the leaves (one compare per level), then  in __sort_r()
251 		 * average, 3/4 worst-case.)  in __sort_r()
271 	n -= size;  in __sort_r()
278  * sort_r - sort an array of elements
283  * @swap_func: pointer to swap function or NULL
288  * copy (e.g. fix up pointers or auxiliary data), but the built-in swap
289  * avoids a slow retpoline and so is significantly faster.
292  * properties to ensure correct and stable sorting:
293  * - Antisymmetry: cmp_func(a, b) must return the opposite sign of
295  * - Transitivity: if cmp_func(a, b) <= 0 and cmp_func(b, c) <= 0, then
298  * Sorting time is O(n log n) both on average and worst-case. While
300  * O(n*n) worst-case behavior and extra memory requirements that make
313  * sort_r_nonatomic - sort an array of elements, with cond_resched
318  * @swap_func: pointer to swap function or NULL
339 		.swap = swap_func,  in sort()
352 		.swap = swap_func,  in sort_nonatomic()