From: Rasmus Villemoes <linux@rasmusvillemoes.dk>
To: Boris Brezillon <boris.brezillon@collabora.com>,
linux-kernel@vger.kernel.org
Cc: George Spelvin <lkml@sdf.org>,
Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
Andrew Morton <akpm@linux-foundation.org>,
Andrey Abramov <st5pub@yandex.ru>,
kernel@collabora.com
Subject: Re: [PATCH] lib/sort: Add the sort_r() variant
Date: Thu, 23 May 2019 22:04:35 +0200 [thread overview]
Message-ID: <bc3f2b9b-627f-bcc7-c16d-391a962258c0@rasmusvillemoes.dk> (raw)
In-Reply-To: <20190522112550.31814-1-boris.brezillon@collabora.com>
On 22/05/2019 13.25, Boris Brezillon wrote:
> Some users might need extra context to compare 2 elements. This patch
> adds the sort_r() which is similar to the qsort_r() variant of qsort().
>
> Signed-off-by: Boris Brezillon <boris.brezillon@collabora.com>
> ---
> Hello,
>
> A few more details about this patch.
>
> Even though I post it as a standalone patch, I do intend to use it in
> a real driver (v4l2 driver), just didn't want to have it burried in a
> huge patch series.
>
> Note that sort() and sort_r() are now implemented as wrappers around
> do_sort() so that most of the code can be shared. I initially went for
> a solution that implemented sort() as a wrapper around sort_r() (which
> basically contained the do_sort() logic without the cmp_func arg)
> but realized this was adding one extra indirect call (the compare func
> wrapper), which I know are being chased.
Hm, I don't like the "pass one or the other, but not both". Yes, the
direct way to implement sort() in terms of sort_r would be
cmp_wrapper(void *a, void *b, void *priv)
{ return ((cmp_func_t)priv)(a, b); }
void sort(...) { sort_r(...., cmp_wrapper, cmp_func); }
but it's easy enough to get rid of that extra indirect call similar to
how the swap functions are done: pass a sentinel value, and use a single
(highly predictable) branch to check whether we have an old-style cmp
function.
[Are there actually any architectures where passing a third argument to
a function just expecting two would not Just Work? I.e., could one
simply cast a new-style comparison function to an old-style and pass
NULL as priv? Well, we'd better not go down that road.]
So I propose this somewhat simpler (at least in terms of diffstat)
patch, which also fits nicely with some optimizations I plan on doing to
eliminate "trivial" comparison functions (those that just do a single
integer comparison of some field inside the structs). Sorry if it's
whitespace-damaged. I also wonder if one should make the priv argument
void* instead of const void*, to help avoid mixing up the elements with
the context, but the function should be pure, so I'm inclined to stick
with the three const void* args.
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 50855ea8c262..8737d47d87bf 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -141,6 +141,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)1L)
+
+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.
@@ -168,12 +180,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
@@ -185,9 +198,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;
@@ -235,12 +249,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 */
@@ -249,4 +263,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-05-23 20:04 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-05-22 11:25 [PATCH] lib/sort: Add the sort_r() variant Boris Brezillon
2019-05-22 18:33 ` Andrew Morton
2019-05-23 8:14 ` Boris Brezillon
2019-05-23 20:04 ` Rasmus Villemoes [this message]
2019-05-24 15:09 ` Boris Brezillon
2019-06-17 13:51 ` Boris Brezillon
2019-06-17 21:14 ` [PATCH] lib/sort.c: implement sort() variant taking context argument Rasmus Villemoes
2019-06-18 8:40 ` 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=bc3f2b9b-627f-bcc7-c16d-391a962258c0@rasmusvillemoes.dk \
--to=linux@rasmusvillemoes.dk \
--cc=akpm@linux-foundation.org \
--cc=andriy.shevchenko@linux.intel.com \
--cc=boris.brezillon@collabora.com \
--cc=kernel@collabora.com \
--cc=linux-kernel@vger.kernel.org \
--cc=lkml@sdf.org \
--cc=st5pub@yandex.ru \
/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).