On Wed, 19 Jun 2019 14:15:32 +0200 Boris Brezillon
<boris.brezil...@collabora.com> wrote:
> From: Rasmus Villemoes <li...@rasmusvillemoes.dk>
>
> Our list_sort() utility has always supported a context argument that
> is passed through to the comparison routine. Now there's a use case
> for the similar thing for sort().
>
> This implements sort_r by simply extending the existing sort function
> in the obvious way. To avoid code duplication, we want to implement
> sort() in terms of sort_r(). The naive way to do that is
>
> static int cmp_wrapper(const void *a, const void *b, const void *ctx)
> {
> int (*real_cmp)(const void*, const void*) = ctx;
> return real_cmp(a, b);
> }
>
> sort(..., cmp) { sort_r(..., cmp_wrapper, cmp) }
>
> but this would do two indirect calls for each comparison. Instead, do
> as is done for the default swap functions - that only adds a cost of a
> single easily predicted branch to each comparison call.
>
> Aside from introducing support for the context argument, this also
> serves as preparation for patches that will eliminate the indirect
> comparison calls in common cases.
Acked-by: Andrew Morton <a...@linux-foundation.org>
> --- a/lib/sort.c
> +++ b/lib/sort.c
> @@ -144,6 +144,18 @@ static void do_swap(void *a, void *b, size_t size,
> swap_func_t swap_func)
> swap_func(a, b, (int)size);
> }
>
> +typedef int (*cmp_func_t)(const void *, const void *);
> +typedef int (*cmp_r_func_t)(const void *, const void *, const void *);
> +#define _CMP_WRAPPER ((cmp_r_func_t)0L)
Although I can't say I'm a fan of _CMP_WRAPPER. I don't understand
what the name means. Why not simply open-code NULL in the two sites?
> +static int do_cmp(const void *a, const void *b,
> + cmp_r_func_t cmp, const void *priv)
> +{
> + if (cmp == _CMP_WRAPPER)
> + return ((cmp_func_t)(priv))(a, b);
> + return cmp(a, b, priv);
> +}
> +
> /**
> * parent - given the offset of the child, find the offset of the parent.
> * @i: the offset of the heap element whose parent is sought. Non-zero.
> @@ -171,12 +183,13 @@ static size_t parent(size_t i, unsigned int lsbit,
> size_t size)
> }
>
> /**
> - * sort - sort an array of elements
> + * sort_r - sort an array of elements
> * @base: pointer to data to sort
> * @num: number of elements
> * @size: size of each element
> * @cmp_func: pointer to comparison function
> * @swap_func: pointer to swap function or NULL
> + * @priv: third argument passed to comparison function
Passing priv==NULLis part of the interface and should be documented?
> *
> * This function does a heapsort on the given array. You may provide
> * a swap_func function if you need to do something more than a memory
> @@ -188,9 +201,10 @@ static size_t parent(size_t i, unsigned int lsbit,
> size_t size)
> * O(n*n) worst-case behavior and extra memory requirements that make
> * it less suitable for kernel use.
> */
> -void sort(void *base, size_t num, size_t size,
> - int (*cmp_func)(const void *, const void *),
> - void (*swap_func)(void *, void *, int size))
> +void sort_r(void *base, size_t num, size_t size,
> + int (*cmp_func)(const void *, const void *, const void *),
> + void (*swap_func)(void *, void *, int size),
> + const void *priv)
> {
> /* pre-scale counters for performance */
> size_t n = num * size, a = (num/2) * size;
> @@ -238,12 +252,12 @@ void sort(void *base, size_t num, size_t size,
> * average, 3/4 worst-case.)
> */
> for (b = a; c = 2*b + size, (d = c + size) < n;)
> - b = cmp_func(base + c, base + d) >= 0 ? c : d;
> + b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c
> : d;
> if (d == n) /* Special case last leaf with no sibling */
> b = c;
>
> /* Now backtrack from "b" to the correct location for "a" */
> - while (b != a && cmp_func(base + a, base + b) >= 0)
> + while (b != a && do_cmp(base + a, base + b, cmp_func, priv) >=
> 0)
> b = parent(b, lsbit, size);
> c = b; /* Where "a" belongs */
> while (b != a) { /* Shift it into place */
> @@ -252,4 +266,12 @@ void sort(void *base, size_t num, size_t size,
> }
> }
> }
> +EXPORT_SYMBOL(sort_r);
> +
> +void sort(void *base, size_t num, size_t size,
> + int (*cmp_func)(const void *, const void *),
> + void (*swap_func)(void *, void *, int size))
> +{
> + return sort_r(base, num, size, _CMP_WRAPPER, swap_func, cmp_func);
> +}
> EXPORT_SYMBOL(sort);
