Re: [PATCH] lib/sort: Add the sort_r() variant

[Rasmus Villemoes]

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@xxxxxxxxxxxxx>
> ---
> 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);