From: Andrew Morton <akpm@linux-foundation.org>
To: Boris Brezillon <boris.brezillon@collabora.com>
Cc: Mauro Carvalho Chehab <mchehab@kernel.org>,
Hans Verkuil <hans.verkuil@cisco.com>,
Laurent Pinchart <laurent.pinchart@ideasonboard.com>,
Sakari Ailus <sakari.ailus@iki.fi>,
linux-media@vger.kernel.org, linux-kernel@vger.kernel.org,
Tomasz Figa <tfiga@chromium.org>,
Nicolas Dufresne <nicolas@ndufresne.ca>,
kernel@collabora.com,
Paul Kocialkowski <paul.kocialkowski@bootlin.com>,
Ezequiel Garcia <ezequiel@collabora.com>,
Jonas Karlman <jonas@kwiboo.se>,
linux-rockchip@lists.infradead.org,
Heiko Stuebner <heiko@sntech.de>,
Rasmus Villemoes <linux@rasmusvillemoes.dk>,
Philipp Zabel <p.zabel@pengutronix.de>
Subject: Re: [PATCH 1/9] lib/sort.c: implement sort() variant taking context argument
Date: Thu, 25 Jul 2019 17:05:47 -0700 [thread overview]
Message-ID: <20190725170547.a8a357dd76cc586f475b782d@linux-foundation.org> (raw)
In-Reply-To: <20190619121540.29320-2-boris.brezillon@collabora.com>
On Wed, 19 Jun 2019 14:15:32 +0200 Boris Brezillon <boris.brezillon@collabora.com> wrote:
> From: Rasmus Villemoes <linux@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 <akpm@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);
next prev parent reply other threads:[~2019-07-26 0:05 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-06-19 12:15 [PATCH 0/9] media: hantro: Add support for H264 decoding Boris Brezillon
2019-06-19 12:15 ` [PATCH 1/9] lib/sort.c: implement sort() variant taking context argument Boris Brezillon
2019-07-25 12:40 ` Boris Brezillon
2019-07-26 0:05 ` Andrew Morton [this message]
2019-07-26 6:59 ` Rasmus Villemoes
2019-06-19 12:15 ` [PATCH 2/9] media: hantro: Move copy_metadata() before doing a decode operation Boris Brezillon
2019-06-19 12:15 ` [PATCH 3/9] media: hantro: Constify the control array Boris Brezillon
2019-07-05 16:05 ` Ezequiel Garcia
2019-07-05 17:17 ` Boris Brezillon
2019-06-19 12:15 ` [PATCH 4/9] media: hantro: Simplify the controls creation logic Boris Brezillon
2019-06-19 12:15 ` [PATCH 5/9] media: hantro: Add hantro_get_{src,dst}_buf() helpers Boris Brezillon
2019-06-19 12:15 ` [PATCH 6/9] media: hantro: Add helpers to prepare/finish a run Boris Brezillon
2019-06-19 12:15 ` [PATCH 7/9] media: hantro: Add core bits to support H264 decoding Boris Brezillon
2019-07-25 13:31 ` Rasmus Villemoes
2019-07-26 10:06 ` Boris Brezillon
2019-08-01 4:06 ` Tomasz Figa
2019-08-01 5:42 ` Boris Brezillon
2019-08-01 7:04 ` Paul Kocialkowski
2019-08-01 7:12 ` Tomasz Figa
2019-08-05 18:38 ` Ezequiel Garcia
2019-06-19 12:15 ` [PATCH 8/9] media: hantro: Add support for H264 decoding on G1 Boris Brezillon
2019-06-19 12:15 ` [PATCH 9/9] media: hantro: Enable H264 decoding on rk3288 Boris Brezillon
2019-06-19 12:23 ` [PATCH 0/9] media: hantro: Add support for H264 decoding Boris Brezillon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20190725170547.a8a357dd76cc586f475b782d@linux-foundation.org \
--to=akpm@linux-foundation.org \
--cc=boris.brezillon@collabora.com \
--cc=ezequiel@collabora.com \
--cc=hans.verkuil@cisco.com \
--cc=heiko@sntech.de \
--cc=jonas@kwiboo.se \
--cc=kernel@collabora.com \
--cc=laurent.pinchart@ideasonboard.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-media@vger.kernel.org \
--cc=linux-rockchip@lists.infradead.org \
--cc=linux@rasmusvillemoes.dk \
--cc=mchehab@kernel.org \
--cc=nicolas@ndufresne.ca \
--cc=p.zabel@pengutronix.de \
--cc=paul.kocialkowski@bootlin.com \
--cc=sakari.ailus@iki.fi \
--cc=tfiga@chromium.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).