Linux-Media Archive on lore.kernel.org
 help / color / Atom feed
From: Ezequiel Garcia <ezequiel@collabora.com>
To: linux-media@vger.kernel.org
Cc: kernel@collabora.com,
	Nicolas Dufresne <nicolas.dufresne@collabora.com>,
	Tomasz Figa <tfiga@chromium.org>,
	linux-rockchip@lists.infradead.org,
	Heiko Stuebner <heiko@sntech.de>, Jonas Karlman <jonas@kwiboo.se>,
	Philipp Zabel <p.zabel@pengutronix.de>,
	Boris Brezillon <boris.brezillon@collabora.com>,
	Paul Kocialkowski <paul.kocialkowski@bootlin.com>,
	Alexandre Courbot <acourbot@chromium.org>,
	fbuergisser@chromium.org, linux-kernel@vger.kernel.org,
	Rasmus Villemoes <linux@rasmusvillemoes.dk>,
	Andrew Morton <akpm@linux-foundation.org>
Subject: [PATCH v5 01/11] lib/sort.c: implement sort() variant taking context argument
Date: Mon, 12 Aug 2019 16:35:12 -0300
Message-ID: <20190812193522.10911-2-ezequiel@collabora.com> (raw)
In-Reply-To: <20190812193522.10911-1-ezequiel@collabora.com>

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.

Requested-by: Boris Brezillon <boris.brezillon@collabora.com>
Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
Signed-off-by: Boris Brezillon <boris.brezillon@collabora.com>
Acked-by: Andrew Morton <akpm@linux-foundation.org>
Tested-by: Philipp Zabel <p.zabel@pengutronix.de>
---
 include/linux/sort.h |  5 +++++
 lib/sort.c           | 34 ++++++++++++++++++++++++++++------
 2 files changed, 33 insertions(+), 6 deletions(-)

diff --git a/include/linux/sort.h b/include/linux/sort.h
index 2b99a5dd073d..61b96d0ebc44 100644
--- a/include/linux/sort.h
+++ b/include/linux/sort.h
@@ -4,6 +4,11 @@
 
 #include <linux/types.h>
 
+void sort_r(void *base, size_t num, size_t size,
+	    int (*cmp)(const void *, const void *, const void *),
+	    void (*swap)(void *, void *, int),
+	    const void *priv);
+
 void sort(void *base, size_t num, size_t size,
 	  int (*cmp)(const void *, const void *),
 	  void (*swap)(void *, void *, int));
diff --git a/lib/sort.c b/lib/sort.c
index cf408aec3733..d54cf97e9548 100644
--- 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)
+
+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
  *
  * 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);
-- 
2.22.0


  reply index

Thread overview: 18+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-08-12 19:35 [PATCH v5 00/11] media: hantro: Add support for H264 decoding Ezequiel Garcia
2019-08-12 19:35 ` Ezequiel Garcia [this message]
2019-08-12 19:35 ` [PATCH v5 02/11] media: uapi: h264: Rename pixel format Ezequiel Garcia
2019-08-12 19:35 ` [PATCH v5 03/11] media: uapi: h264: Add the concept of decoding mode Ezequiel Garcia
2019-08-13  6:46   ` Hans Verkuil
2019-08-14 12:23   ` Paul Kocialkowski
2019-08-14 14:08     ` Ezequiel Garcia
2019-08-12 19:35 ` [PATCH v5 04/11] media: uapi: h264: Add the concept of start code Ezequiel Garcia
2019-08-14  8:11   ` Hans Verkuil
2019-08-14 11:49     ` Paul Kocialkowski
2019-08-14 14:12       ` Ezequiel Garcia
2019-08-12 19:35 ` [PATCH v5 05/11] media: uapi: h264: Get rid of the p0/b0/b1 ref-lists Ezequiel Garcia
2019-08-12 19:35 ` [PATCH v5 06/11] media: cedrus: Cleanup control initialization Ezequiel Garcia
2019-08-12 19:35 ` [PATCH v5 07/11] media: cedrus: Specify H264 startcode and decoding mode Ezequiel Garcia
2019-08-12 19:35 ` [PATCH v5 08/11] media: hantro: Move copy_metadata() before doing a decode operation Ezequiel Garcia
2019-08-12 19:35 ` [PATCH v5 09/11] media: hantro: Add core bits to support H264 decoding Ezequiel Garcia
2019-08-12 19:35 ` [PATCH v5 10/11] media: hantro: Add support for H264 decoding on G1 Ezequiel Garcia
2019-08-12 19:35 ` [PATCH v5 11/11] media: hantro: Enable H264 decoding on rk3288 Ezequiel Garcia

Reply instructions:

You may reply publically 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=20190812193522.10911-2-ezequiel@collabora.com \
    --to=ezequiel@collabora.com \
    --cc=acourbot@chromium.org \
    --cc=akpm@linux-foundation.org \
    --cc=boris.brezillon@collabora.com \
    --cc=fbuergisser@chromium.org \
    --cc=heiko@sntech.de \
    --cc=jonas@kwiboo.se \
    --cc=kernel@collabora.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-media@vger.kernel.org \
    --cc=linux-rockchip@lists.infradead.org \
    --cc=linux@rasmusvillemoes.dk \
    --cc=nicolas.dufresne@collabora.com \
    --cc=p.zabel@pengutronix.de \
    --cc=paul.kocialkowski@bootlin.com \
    --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

Linux-Media Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-media/0 linux-media/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-media linux-media/ https://lore.kernel.org/linux-media \
		linux-media@vger.kernel.org
	public-inbox-index linux-media

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-media


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git