linux-6.8/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  * Glibc qsort() 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
20  * is_aligned - is this pointer & size okay for word-wide copying?
25  * Returns true if elements can be copied using word loads and stores.
26  * The size must be a multiple of the alignment, and the base address must
41 	return (lsbits & (align - 1)) == 0;  in is_aligned()
45  * swap_words_32 - swap two elements in 32-bit chunks
46  * @a: pointer to the first element to swap
47  * @b: pointer to the second element to swap
61 		u32 t = *(u32 *)(a + (n -= 4));  in swap_words_32()
68  * swap_words_64 - swap two elements in 64-bit chunks
69  * @a: pointer to the first element to swap
70  * @b: pointer to the second element to swap
77  * We'd like to use 64-bit loads if possible.  If they're not, emulating
79  * processors do not.  If CONFIG_64BIT, we definitely have 64-bit loads,
80  * but it's possible to have 64-bit loads without 64-bit pointers (e.g.
87 		u64 t = *(u64 *)(a + (n -= 8));  in swap_words_64()
91 		/* Use two 32-bit transfers to avoid base+index+4 addressing */  in swap_words_64()
92 		u32 t = *(u32 *)(a + (n -= 4));  in swap_words_64()
96 		t = *(u32 *)(a + (n -= 4));  in swap_words_64()
104  * swap_bytes - swap two elements a byte at a time
105  * @a: pointer to the first element to swap
106  * @b: pointer to the second element to swap
114 		char t = ((char *)a)[--n];  in swap_bytes()
122  * a pointer, but small integers make for the smallest compare
132 	swap_func_t swap;  member
142 		((const struct wrapper *)priv)->swap(a, b, (int)size);  in do_swap()
161 		return ((const struct wrapper *)priv)->cmp(a, b);  in do_cmp()
166  * parent - given the offset of the child, find the offset of the parent.
167  * @i: the offset of the heap element whose parent is sought.  Non-zero.
168  * @lsbit: a precomputed 1-bit mask, equal to "size & -size"
172  * (j-1)/2.  But when working in byte offsets, we can't use implicit
177  * an even multiple of @size, and set if it's an odd multiple.
179  * Logically, we're doing "if (i & lsbit) i -= size;", but since the
180  * branch is unpredictable, it's done with a bit of clever branch-free
186 	i -= size;  in parent()
187 	i -= size & -(i & lsbit);  in parent()
192  * sort_r - sort an array of elements
197  * @swap_func: pointer to swap function or NULL
202  * copy (e.g. fix up pointers or auxiliary data), but the built-in swap
203  * avoids a slow retpoline and so is significantly faster.
205  * Sorting time is O(n log n) both on average and worst-case. While
207  * O(n*n) worst-case behavior and extra memory requirements that make
215 	/* pre-scale counters for performance */  in sort_r()
217 	const unsigned int lsbit = size & -size;  /* Used to find parent */  in sort_r()
222 	/* called from 'sort' without swap function, let's pick the default */  in sort_r()
223 	if (swap_func == SWAP_WRAPPER && !((struct wrapper *)priv)->swap)  in sort_r()
237 	 * 1. elements [a,n) satisfy the heap property (compare greater than  in sort_r()
239 	 * 2. elements [n,num*size) are sorted, and  in sort_r()
245 		if (a)			/* Building heap: sift down --a */  in sort_r()
246 			a -= size;  in sort_r()
247 		else if (n -= size)	/* Sorting: Extract root to --n */  in sort_r()
254 		 * "bottom-up" variant, which significantly reduces  in sort_r()
255 		 * calls to cmp_func(): we find the sift-down path all  in sort_r()
256 		 * the way to the leaves (one compare per level), then  in sort_r()
262 		 * average, 3/4 worst-case.)  in sort_r()
287 		.swap = swap_func,  in sort()