Lines Matching +full:compare +full:- +full:and +full:- +full:swap
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()
190 * sort_r - sort an array of elements
195 * @swap_func: pointer to swap function or NULL
200 * copy (e.g. fix up pointers or auxiliary data), but the built-in swap
201 * avoids a slow retpoline and so is significantly faster.
204 * properties to ensure correct and stable sorting:
205 * - Antisymmetry: cmp_func(a, b) must return the opposite sign of
207 * - Transitivity: if cmp_func(a, b) <= 0 and cmp_func(b, c) <= 0, then
210 * Sorting time is O(n log n) both on average and worst-case. While
212 * O(n*n) worst-case behavior and extra memory requirements that make
220 /* pre-scale counters for performance */ in sort_r()
222 const unsigned int lsbit = size & -size; /* Used to find parent */ in sort_r()
228 /* called from 'sort' without swap function, let's pick the default */ in sort_r()
229 if (swap_func == SWAP_WRAPPER && !((struct wrapper *)priv)->swap) in sort_r()
243 * 1. elements [a,n) satisfy the heap property (compare greater than in sort_r()
245 * 2. elements [n,num*size) are sorted, and in sort_r()
252 a -= size << shift; in sort_r()
254 n -= size; in sort_r()
258 n -= size; in sort_r()
266 * "bottom-up" variant, which significantly reduces in sort_r()
267 * calls to cmp_func(): we find the sift-down path all in sort_r()
268 * the way to the leaves (one compare per level), then in sort_r()
274 * average, 3/4 worst-case.) in sort_r()
291 n -= size; in sort_r()
304 .swap = swap_func, in sort()