18  * is_aligned - is this pointer & size okay for word-wide copying?
20  * @size: size of each element
24  * The size must be a multiple of the alignment, and the base address must
31 static bool is_aligned(const void *base, size_t size, unsigned char align)  in is_aligned()  argument
33 	unsigned char lsbits = (unsigned char)size;  in is_aligned()
46  * @n: element size (must be a multiple of 4)
69  * @n: element size (must be a multiple of 8)
105  * @n: element size
137 static void do_swap(void *a, void *b, size_t size, swap_r_func_t swap_func, const void *priv)  in do_swap()  argument
140 		((const struct wrapper *)priv)->swap(a, b, (int)size);  in do_swap()
145 		swap_words_64(a, b, size);  in do_swap()
147 		swap_words_32(a, b, size);  in do_swap()
149 		swap_bytes(a, b, size);  in do_swap()
151 		swap_func(a, b, (int)size, priv);  in do_swap()
166  * @lsbit: a precomputed 1-bit mask, equal to "size & -size"
167  * @size: size of each element
169  * In terms of array indexes, the parent of element j = @i/@size is simply
174  * @size has a least significant bit.  That bit will be clear if @i is
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
182 static size_t parent(size_t i, unsigned int lsbit, size_t size)  in parent()  argument
184 	i -= size;  in parent()
185 	i -= size & -(i & lsbit);  in parent()
191 static void __sort_r(void *base, size_t num, size_t size,  in __sort_r()  argument
198 	size_t n = num * size, a = (num/2) * size;  in __sort_r()
199 	const unsigned int lsbit = size & -size;  /* Used to find parent */  in __sort_r()
202 	if (!a)		/* num < 2 || size == 0 */  in __sort_r()
210 		if (is_aligned(base, size, 8))  in __sort_r()
212 		else if (is_aligned(base, size, 4))  in __sort_r()
222 	 * 2. elements [n,num*size) are sorted, and  in __sort_r()
229 			a -= size << shift;  in __sort_r()
230 		else if (n > 3 * size) { /* Sorting: Extract two largest elements */  in __sort_r()
231 			n -= size;  in __sort_r()
232 			do_swap(base, base + n, size, swap_func, priv);  in __sort_r()
233 			shift = do_cmp(base + size, base + 2 * size, cmp_func, priv) <= 0;  in __sort_r()
234 			a = size << shift;  in __sort_r()
235 			n -= size;  in __sort_r()
236 			do_swap(base + a, base + n, size, swap_func, priv);  in __sort_r()
253 		for (b = a; c = 2*b + size, (d = c + size) < n;)  in __sort_r()
260 			b = parent(b, lsbit, size);  in __sort_r()
263 			b = parent(b, lsbit, size);  in __sort_r()
264 			do_swap(base + b, base + c, size, swap_func, priv);  in __sort_r()
271 	n -= size;  in __sort_r()
272 	do_swap(base, base + n, size, swap_func, priv);  in __sort_r()
273 	if (n == size * 2 && do_cmp(base, base + size, cmp_func, priv) > 0)  in __sort_r()
274 		do_swap(base, base + size, size, swap_func, priv);  in __sort_r()
281  * @size: size of each element
303 void sort_r(void *base, size_t num, size_t size,  in sort_r()  argument
308 	__sort_r(base, num, size, cmp_func, swap_func, priv, false);  in sort_r()
316  * @size: size of each element
324 void sort_r_nonatomic(void *base, size_t num, size_t size,  in sort_r_nonatomic()  argument
329 	__sort_r(base, num, size, cmp_func, swap_func, priv, true);  in sort_r_nonatomic()
333 void sort(void *base, size_t num, size_t size,  in sort()  argument
342 	return __sort_r(base, num, size, _CMP_WRAPPER, SWAP_WRAPPER, &w, false);  in sort()
346 void sort_nonatomic(void *base, size_t num, size_t size,  in sort_nonatomic()  argument
355 	return __sort_r(base, num, size, _CMP_WRAPPER, SWAP_WRAPPER, &w, true);  in sort_nonatomic()