qsort_r again

[David Holland <dholland-tech%netbsd.org@localhost>]

(Cc: tech-kern because of kheapsort())

Some time back I made a set of patches for qsort_r(), that is, a
version of qsort that allows passing a data pointer through, along
with corresponding mergesort_r() and heapsort_r().

After some discussion the conclusion was that instead of using thunks
to implement qsort in terms of qsort_r, it was better to implement
both versions in terms of a common internal version. The following
patchset does that.

heapsort() is used in two places in the kernel as kheapsort(), which
takes an extra argument so that the heapsort code itself doesn't have
to know how to malloc in the kernel. I have done the following:
   - add kheapsort_r()
   - change the signature of plain kheapsort() to move the extra
     argument to a place it is less likely to cause confusion with the
     data argument;
   - update the callers for the signature change;
but I have not changed either caller to call kheapsort_r
instead. Based on the code, this should probably be done later; then
the plain kheapsort can be removed.

Note that this set of names and signatures matches what's in Linux.
Apparently FreeBSD did it differently, but there are reasons to prefer
this arrangement of arguments.

Joerg also says that the _r names are inappropriate because the
originals are reentrant, but I think that's tilting at windmills and
it's more useful to be compatible.

   ------

Index: common/lib/libc/stdlib/heapsort.c
===================================================================
RCS file: /cvsroot/src/common/lib/libc/stdlib/heapsort.c,v
retrieving revision 1.3
diff -u -p -r1.3 heapsort.c
--- common/lib/libc/stdlib/heapsort.c	17 Nov 2008 10:21:30 -0000	1.3
+++ common/lib/libc/stdlib/heapsort.c	27 Aug 2016 20:06:46 -0000
@@ -60,6 +60,7 @@ __RCSID("$NetBSD: heapsort.c,v 1.3 2008/
 
 #include <assert.h>
 #include <errno.h>
+#include <stdbool.h>
 #include <stdlib.h>
 
 #if HAVE_NBTOOL_CONFIG_H
@@ -69,10 +70,24 @@ __RCSID("$NetBSD: heapsort.c,v 1.3 2008/
 
 #ifdef __weak_alias
 __weak_alias(heapsort,_heapsort)
+__weak_alias(heapsort_r,_heapsort_r)
 #endif
 #endif	/* _KERNEL || _STANDALONE */
 
 /*
+ * Union of comparison function pointers for the plain and _r forms
+ */
+union heapsort_cmp {
+	int (*cmp)(const void *, const void *);
+	int (*cmp_r)(const void *, const void *, void *);
+};
+
+/*
+ * Macro for calling through the union
+ */
+#define COMPAR(a, b, d)	(is_r ? compar->cmp_r(a, b, d) : compar->cmp(a, b))
+
+/*
  * Swap two areas of size number of bytes.  Although qsort(3) permits random
  * blocks of memory to be sorted, sorting pointers is almost certainly the
  * common case (and, were it not, could easily be made so).  Regardless, it
@@ -109,12 +124,12 @@ __weak_alias(heapsort,_heapsort)
 	for (par_i = initval; (child_i = par_i * 2) <= nmemb; \
 	    par_i = child_i) { \
 		child = base + child_i * size; \
-		if (child_i < nmemb && compar(child, child + size) < 0) { \
+		if (child_i < nmemb && COMPAR(child, child + size, data) < 0) {\
 			child += size; \
 			++child_i; \
 		} \
 		par = base + par_i * size; \
-		if (compar(child, par) <= 0) \
+		if (COMPAR(child, par, data) <= 0) \
 			break; \
 		SWAP(par, child, count, size, tmp); \
 	} \
@@ -140,7 +155,7 @@ __weak_alias(heapsort,_heapsort)
 #define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) { \
 	for (par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i) { \
 		child = base + child_i * size; \
-		if (child_i < nmemb && compar(child, child + size) < 0) { \
+		if (child_i < nmemb && COMPAR(child, child + size, data) < 0) {\
 			child += size; \
 			++child_i; \
 		} \
@@ -152,7 +167,7 @@ __weak_alias(heapsort,_heapsort)
 		par_i = child_i / 2; \
 		child = base + child_i * size; \
 		par = base + par_i * size; \
-		if (child_i == 1 || compar(k, par) < 0) { \
+		if (child_i == 1 || COMPAR(k, par, data) < 0) { \
 			COPY(child, k, count, size, tmp1, tmp2); \
 			break; \
 		} \
@@ -168,13 +183,13 @@ __weak_alias(heapsort,_heapsort)
  * only advantage over quicksort is that it requires little additional memory.
  */
 #if defined(_KERNEL) || defined(_STANDALONE)
-int
-kheapsort(void *vbase, size_t nmemb, size_t size,
-    int (*compar)(const void *, const void *), void *k)
+static int
+kheapsort_internal(void *vbase, size_t nmemb, size_t size, void *k,
+    bool is_r, const union heapsort_cmp *compar, void *data)
 #else
-int
-heapsort(void *vbase, size_t nmemb, size_t size,
-    int (*compar)(const void *, const void *))
+static int
+heapsort_internal(void *vbase, size_t nmemb, size_t size,
+    bool is_r, const union heapsort_cmp *compar, void *data)
 #endif
 {
 	size_t cnt, i, j, l;
@@ -186,6 +201,7 @@ heapsort(void *vbase, size_t nmemb, size
 
 	_DIAGASSERT(vbase != NULL);
 	_DIAGASSERT(compar != NULL);
+	_DIAGASSERT(is_r ? compar->cmp_r != NULL : compar->cmp != NULL);
 
 	if (nmemb <= 1)
 		return (0);
@@ -227,3 +243,49 @@ heapsort(void *vbase, size_t nmemb, size
 #endif
 	return (0);
 }
+
+////////////////////////////////////////////////////////////
+// heapsort_r() with data pointer
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+int
+kheapsort_r(void *vbase, size_t nmemb, size_t size, void *k,
+    int (*compar)(const void *, const void *, void *), void *data)
+{
+	union heapsort_cmp cmp = { .cmp_r = compar };
+
+	return kheapsort_internal(vbase, nmemb, size, k, true, &cmp, data);
+}
+#else
+int
+heapsort_r(void *vbase, size_t nmemb, size_t size,
+    int (*compar)(const void *, const void *, void *), void *data)
+{
+	union heapsort_cmp cmp = { .cmp_r = compar };
+
+	return heapsort_internal(vbase, nmemb, size, true, &cmp, data);
+}
+#endif
+
+////////////////////////////////////////////////////////////
+// original heapsort()
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+int
+kheapsort(void *vbase, size_t nmemb, size_t size, void *k,
+    int (*compar)(const void *, const void *))
+{
+	union heapsort_cmp cmp = { .cmp = compar };
+
+	return kheapsort_internal(vbase, nmemb, size, k, false, &cmp, NULL);
+}
+#else
+int
+heapsort(void *vbase, size_t nmemb, size_t size,
+    int (*compar)(const void *, const void *))
+{
+	union heapsort_cmp cmp = { .cmp = compar };
+
+	return heapsort_internal(vbase, nmemb, size, false, &cmp, NULL);
+}
+#endif
Index: include/stdlib.h
===================================================================
RCS file: /cvsroot/src/include/stdlib.h,v
retrieving revision 1.117
diff -u -p -r1.117 stdlib.h
--- include/stdlib.h	1 Jul 2016 22:42:01 -0000	1.117
+++ include/stdlib.h	27 Aug 2016 20:06:46 -0000
@@ -310,9 +310,16 @@ int	 getenv_r(const char *, char *, size
 
 void	 cfree(void *);
 
-int	 heapsort(void *, size_t, size_t, int (*)(const void *, const void *));
+int	 heapsort(void *, size_t, size_t,
+	    int (*)(const void *, const void *));
+int	 heapsort_r(void *, size_t, size_t,
+	    int (*)(const void *, const void *, void *), void *);
 int	 mergesort(void *, size_t, size_t,
 	    int (*)(const void *, const void *));
+int	 mergesort_r(void *, size_t, size_t,
+	    int (*)(const void *, const void *, void *), void *);
+void	 qsort_r(void *, size_t, size_t,
+	    int (*)(const void *, const void *, void *), void *);
 int	 ptsname_r(int, char *, size_t);
 int	 radixsort(const unsigned char **, int, const unsigned char *,
 	    unsigned);
Index: lib/libc/include/namespace.h
===================================================================
RCS file: /cvsroot/src/lib/libc/include/namespace.h,v
retrieving revision 1.180
diff -u -p -r1.180 namespace.h
--- lib/libc/include/namespace.h	3 Apr 2016 00:19:42 -0000	1.180
+++ lib/libc/include/namespace.h	27 Aug 2016 20:06:46 -0000
@@ -402,6 +402,7 @@
 #define gmtime_r		_gmtime_r
 #define group_from_gid		_group_from_gid
 #define heapsort		_heapsort
+#define heapsort_r		_heapsort_r
 #define herror			_herror
 #define hes_error		_hes_error
 #define hes_free		_hes_free
@@ -482,6 +483,7 @@
 #define lseek			_lseek
 #define membar_producer		_membar_producer
 #define mergesort		_mergesort
+#define mergesort_r		_mergesort_r
 #define mi_vector_hash		_mi_vector_hash
 #define mkstemp			_mkstemp
 #define mktime_z		_mktime_z
@@ -543,6 +545,7 @@
 #define pwrite			_pwrite
 #define qabs			_qabs
 #define qdiv			_qdiv
+#define qsort_r			_qsort_r
 #define radixsort		_radixsort
 #define random			_random
 #define randomid		_randomid
Index: lib/libc/stdlib/Makefile.inc
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/Makefile.inc,v
retrieving revision 1.92
diff -u -p -r1.92 Makefile.inc
--- lib/libc/stdlib/Makefile.inc	1 Apr 2016 12:37:48 -0000	1.92
+++ lib/libc/stdlib/Makefile.inc	27 Aug 2016 20:06:46 -0000
@@ -76,8 +76,9 @@ MLINKS+=jemalloc.3 malloc.conf.5
 MLINKS+=lsearch.3 lfind.3
 MLINKS+=malloc.3 calloc.3 malloc.3 realloc.3 malloc.3 free.3
 MLINKS+=posix_memalign.3 aligned_alloc.3
-MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3
 MLINKS+=ptsname.3 ptsname_r.3
+MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3
+MLINKS+=qsort.3 qsort_r.3 qsort.3 heapsort_r.3 qsort.3 mergesort_r.3
 MLINKS+=rand.3 rand_r.3
 MLINKS+=rand.3 srand.3
 MLINKS+=rand48.3 drand48.3 rand48.3 erand48.3 rand48.3 lrand48.3
Index: lib/libc/stdlib/merge.c
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/merge.c,v
retrieving revision 1.14
diff -u -p -r1.14 merge.c
--- lib/libc/stdlib/merge.c	13 Mar 2012 21:13:48 -0000	1.14
+++ lib/libc/stdlib/merge.c	27 Aug 2016 20:06:46 -0000
@@ -60,17 +60,33 @@ __RCSID("$NetBSD: merge.c,v 1.14 2012/03
 
 #include <assert.h>
 #include <errno.h>
+#include <stdbool.h>
 #include <stdlib.h>
 #include <string.h>
 
 #ifdef __weak_alias
 __weak_alias(mergesort,_mergesort)
+__weak_alias(mergesort_r,_mergesort_r)
 #endif
 
+/*
+ * Union of comparison function pointers for the plain and _r forms
+ */
+union mergesort_cmp {
+	int (*cmp)(const void *, const void *);
+	int (*cmp_r)(const void *, const void *, void *);
+};
+
+/*
+ * Macro for calling through the union
+ */
+#define COMPAR(a, b, d)	(is_r ? compar->cmp_r(a, b, d) : compar->cmp(a, b))
+
+
 static void setup(u_char *, u_char *, size_t, size_t,
-    int (*)(const void *, const void *));
+    bool is_r, const union mergesort_cmp *, void *);
 static void insertionsort(u_char *, size_t, size_t,
-    int (*)(const void *, const void *));
+    bool is_r, const union mergesort_cmp *, void *);
 
 #define ISIZE sizeof(int)
 #define PSIZE sizeof(u_char *)
@@ -107,9 +123,9 @@ static void insertionsort(u_char *, size
 /*
  * Arguments are as for qsort.
  */
-int
-mergesort(void *base, size_t nmemb, size_t size,
-    int (*cmp)(const void *, const void *))
+static int
+mergesort_internal(void *base, size_t nmemb, size_t size,
+    bool is_r, const union mergesort_cmp *compar, void *data)
 {
 	size_t i;
 	int sense;
@@ -118,7 +134,8 @@ mergesort(void *base, size_t nmemb, size
 	u_char *list2, *list1, *p2, *p, *last, **p1;
 
 	_DIAGASSERT(base != NULL);
-	_DIAGASSERT(cmp != NULL);
+	_DIAGASSERT(compar != NULL);
+	_DIAGASSERT(is_r ? compar->cmp_r != NULL : compar->cmp != NULL);
 
 	if (size < PSIZE / 2) {		/* Pointers must fit into 2 * size. */
 		errno = EINVAL;
@@ -137,7 +154,7 @@ mergesort(void *base, size_t nmemb, size
 		return (-1);
 
 	list1 = base;
-	setup(list1, list2, nmemb, size, cmp);
+	setup(list1, list2, nmemb, size, is_r, compar, data);
 	last = list2 + nmemb * size;
 	i = big = 0;
 	while (*EVAL(list2) != last) {
@@ -151,7 +168,7 @@ mergesort(void *base, size_t nmemb, size
 	    		p2 = *EVAL(p2);
 	    	l2 = list1 + (p2 - list2);
 	    	while (f1 < l1 && f2 < l2) {
-	    		if ((*cmp)(f1, f2) <= 0) {
+	    		if (COMPAR(f1, f2, data) <= 0) {
 	    			q = f2;
 	    			b = f1, t = l1;
 	    			sense = -1;
@@ -164,7 +181,7 @@ mergesort(void *base, size_t nmemb, size
 #if 0
 LINEAR:
 #endif
-				while ((b += size) < t && cmp(q, b) >sense)
+				while ((b += size) < t && COMPAR(q, b, data)>sense)
 	    				if (++i == 6) {
 	    					big = 1;
 	    					goto EXPONENTIAL;
@@ -173,12 +190,12 @@ LINEAR:
 EXPONENTIAL:	    		for (i = size; ; i <<= 1)
 	    				if ((p = (b + i)) >= t) {
 	    					if ((p = t - size) > b &&
-						    (*cmp)(q, p) <= sense)
+						    COMPAR(q, p, data) <= sense)
 	    						t = p;
 	    					else
 	    						b = p;
 	    					break;
-	    				} else if ((*cmp)(q, p) <= sense) {
+	    				} else if (COMPAR(q, p, data) <= sense) {
 	    					t = p;
 	    					if (i == size)
 	    						big = 0; 
@@ -190,16 +207,17 @@ SLOWCASE:
 #endif
 				while (t > b+size) {
 	    				i = (((t - b) / size) >> 1) * size;
-	    				if ((*cmp)(q, p = b + i) <= sense)
+	    				if (COMPAR(q, p = b + i, data) <= sense)
 	    					t = p;
 	    				else
 	    					b = p;
 	    			}
 	    			goto COPY;
 FASTCASE:	    		while (i > size)
-	    				if ((*cmp)(q,
+	    				if (COMPAR(q,
 	    					p = b +
-						    (i = (unsigned int) i >> 1)) <= sense)
+						    (i = (unsigned int) i >> 1),
+						     data) <= sense)
 	    					t = p;
 	    				else
 	    					b = p;
@@ -276,22 +294,22 @@ COPY:	    			b = t;
  * is defined.  Otherwise simple pairwise merging is used.)
  */
 
-/* XXX: shouldn't this function be static? - lukem 990810 */
-void
+static void
 setup(u_char *list1, u_char *list2, size_t n, size_t size,
-    int (*cmp)(const void *, const void *))
+    bool is_r, const union mergesort_cmp *compar, void *data)
 {
 	int length, tmp, sense;
 	u_char *f1, *f2, *s, *l2, *last, *p2;
 	size_t size2, i;
 
-	_DIAGASSERT(cmp != NULL);
+	_DIAGASSERT(compar != NULL);
+	_DIAGASSERT(is_r ? compar->cmp_r != NULL : compar->cmp != NULL);
 	_DIAGASSERT(list1 != NULL);
 	_DIAGASSERT(list2 != NULL);
 
 	size2 = size*2;
 	if (n <= 5) {
-		insertionsort(list1, n, size, cmp);
+		insertionsort(list1, n, size, is_r, compar, data);
 		*EVAL(list2) = list2 + n*size;
 		return;
 	}
@@ -300,19 +318,19 @@ setup(u_char *list1, u_char *list2, size
 	 * for simplicity.
 	 */
 	i = 4 + (n & 1);
-	insertionsort(list1 + (n - i) * size, i, size, cmp);
+	insertionsort(list1 + (n - i) * size, i, size, is_r, compar, data);
 	last = list1 + size * (n - i);
 	*EVAL(list2 + (last - list1)) = list2 + n * size;
 
 #ifdef NATURAL
 	p2 = list2;
 	f1 = list1;
-	sense = (cmp(f1, f1 + size) > 0);
+	sense = (COMPAR(f1, f1 + size, data) > 0);
 	for (; f1 < last; sense = !sense) {
 		length = 2;
 					/* Find pairs with same sense. */
 		for (f2 = f1 + size2; f2 < last; f2 += size2) {
-			if ((cmp(f2, f2+ size) > 0) != sense)
+			if ((COMPAR(f2, f2 + size, data) > 0) != sense)
 				break;
 			length += 2;
 		}
@@ -325,7 +343,7 @@ setup(u_char *list1, u_char *list2, size
 		} else {				/* Natural merge */
 			l2 = f2;
 			for (f2 = f1 + size2; f2 < l2; f2 += size2) {
-				if ((cmp(f2-size, f2) > 0) != sense) {
+				if ((COMPAR(f2-size, f2, data) > 0) != sense) {
 					p2 = *EVAL(p2) = f2 - list1 + list2;
 					if (sense > 0)
 						reverse(f1, f2 - size);
@@ -335,7 +353,7 @@ setup(u_char *list1, u_char *list2, size
 			if (sense > 0)
 				reverse(f1, f2 - size);
 			f1 = f2;
-			if (f2 < last || cmp(f2 - size, f2) > 0)
+			if (f2 < last || COMPAR(f2 - size, f2, data) > 0)
 				p2 = *EVAL(p2) = f2 - list1 + list2;
 			else
 				p2 = *EVAL(p2) = list2 + n*size;
@@ -344,7 +362,7 @@ setup(u_char *list1, u_char *list2, size
 #else		/* pairwise merge only. */
 	for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
 		p2 = *EVAL(p2) = p2 + size2;
-		if (cmp (f1, f1 + size) > 0)
+		if (COMPAR (f1, f1 + size, data) > 0)
 			swap(f1, f1 + size);
 	}
 #endif /* NATURAL */
@@ -356,19 +374,44 @@ setup(u_char *list1, u_char *list2, size
  */
 static void
 insertionsort(u_char *a, size_t n, size_t size,
-    int (*cmp)(const void *, const void *))
+    bool is_r, const union mergesort_cmp *compar, void *data)
 {
 	u_char *ai, *s, *t, *u, tmp;
 	size_t i;
 
 	_DIAGASSERT(a != NULL);
-	_DIAGASSERT(cmp != NULL);
+	_DIAGASSERT(compar != NULL);
+	_DIAGASSERT(is_r ? compar->cmp_r != NULL : compar->cmp != NULL);
 
 	for (ai = a+size; --n >= 1; ai += size)
 		for (t = ai; t > a; t -= size) {
 			u = t - size;
-			if (cmp(u, t) <= 0)
+			if (COMPAR(u, t, data) <= 0)
 				break;
 			swap(u, t);
 		}
 }
+
+////////////////////////////////////////////////////////////
+// mergesort_r()
+
+int
+mergesort_r(void *base, size_t nmemb, size_t size,
+    int (*compar)(const void *, const void *, void *), void *data)
+{
+	union mergesort_cmp cmp = { .cmp_r = compar };
+
+	return mergesort_internal(base, nmemb, size, true, &cmp, data);
+}
+
+////////////////////////////////////////////////////////////
+// original mergesort()
+
+int
+mergesort(void *base, size_t nmemb, size_t size,
+    int (*compar)(const void *, const void *))
+{
+	union mergesort_cmp cmp = { .cmp = compar };
+
+	return mergesort_internal(base, nmemb, size, false, &cmp, NULL);
+}
Index: lib/libc/stdlib/qsort.3
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/qsort.3,v
retrieving revision 1.14
diff -u -p -r1.14 qsort.3
--- lib/libc/stdlib/qsort.3	19 Sep 2014 16:02:58 -0000	1.14
+++ lib/libc/stdlib/qsort.3	27 Aug 2016 20:06:46 -0000
@@ -33,13 +33,16 @@
 .\"
 .\"     from: @(#)qsort.3	8.1 (Berkeley) 6/4/93
 .\"
-.Dd June 4, 1993
+.Dd December 8, 2013
 .Dt QSORT 3
 .Os
 .Sh NAME
 .Nm qsort ,
 .Nm heapsort ,
-.Nm mergesort
+.Nm mergesort ,
+.Nm qsort_r ,
+.Nm heapsort_r ,
+.Nm mergesort_r
 .Nd sort functions
 .Sh LIBRARY
 .Lb libc
@@ -51,6 +54,11 @@
 .Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
 .Ft int
 .Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
+.Ft void
+.Fn qsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *userdata"
+.Fn heapsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *userdata"
+.Ft int
+.Fn mergesort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *userdata"
 .Sh DESCRIPTION
 The
 .Fn qsort
@@ -147,16 +155,35 @@ is faster than
 .Fn heapsort .
 Memory availability and pre-existing order in the data can make this
 untrue.
+.Pp
+The
+.Fn qsort_r ,
+.Fn heapsort_r ,
+and
+.Fn mergesort_r
+functions are the same as
+.Fn qsort ,
+.Fn heapsort ,
+and
+.Fn mergesort
+respectively except that they accept an additional argument
+.Fa userdata
+which is passed through as an additional argument (the third and last)
+of the comparison function.
 .Sh RETURN VALUES
 The
 .Fn qsort
-function
-returns no value.
+and
+.Fn qsort_r
+functions
+return no value.
 .Pp
 Upon successful completion,
-.Fn heapsort
-and
+.Fn heapsort ,
 .Fn mergesort
+.Fn heapsort_r ,
+and
+.Fn mergesort_r
 return 0.
 Otherwise, they return \-1 and the global variable
 .Va errno
@@ -169,8 +196,12 @@ did not permit the comparison routine it
 This is no longer true.
 .Sh ERRORS
 The
-.Fn heapsort
-function succeeds unless:
+.Fn heapsort ,
+.Fn mergesort
+.Fn heapsort_r ,
+and
+.Fn heapsort_r
+functions succeed unless:
 .Bl -tag -width Er
 .It Bq Er EINVAL
 The
@@ -180,6 +211,8 @@ the
 .Fa size
 argument to
 .Fn mergesort
+or
+.Fn mergesort_r
 is less than
 .Dq "sizeof(void *) / 2" .
 .It Bq Er ENOMEM
@@ -236,3 +269,11 @@ The
 function
 conforms to
 .St -ansiC .
+.Sh HISTORY
+The
+.Fn qsort_r ,
+.Fn heapsort_r ,
+and
+.Fn mergesort_r
+functions were added in
+.Nx 7.0 .
Index: lib/libc/stdlib/qsort.c
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/qsort.c,v
retrieving revision 1.22
diff -u -p -r1.22 qsort.c
--- lib/libc/stdlib/qsort.c	26 May 2012 21:47:05 -0000	1.22
+++ lib/libc/stdlib/qsort.c	27 Aug 2016 20:06:46 -0000
@@ -40,13 +40,32 @@ __RCSID("$NetBSD: qsort.c,v 1.22 2012/05
 
 #include <sys/types.h>
 
+#include "namespace.h"
 #include <assert.h>
 #include <errno.h>
+#include <stdbool.h>
 #include <stdlib.h>
 
-static inline char	*med3(char *, char *, char *,
-    int (*)(const void *, const void *));
-static inline void	 swapfunc(char *, char *, size_t, int);
+#ifdef __weak_alias
+__weak_alias(qsort_r,_qsort_r)
+#endif
+
+////////////////////////////////////////////////////////////
+// qsort_internal
+
+/*
+ * Union of comparison function pointers for the plain and _r forms
+ */
+union qsort_cmp {
+	int (*cmp)(const void *, const void *);
+	int (*cmp_r)(const void *, const void *, void *);
+};
+
+/*
+ * Macro for calling through the union
+ */
+#define COMPAR(a, b, d)	(is_r ? compar->cmp_r(a, b, d) : compar->cmp(a, b))
+
 
 #define min(a, b)	(a) < (b) ? a : b
 
@@ -89,29 +108,31 @@ swapfunc(char *a, char *b, size_t n, int
 
 static inline char *
 med3(char *a, char *b, char *c,
-    int (*cmp)(const void *, const void *))
+    bool is_r, const union qsort_cmp *compar, void *data)
 {
 
-	return cmp(a, b) < 0 ?
-	       (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
-              :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
+	return COMPAR(a, b, data) < 0 ?
+	       (COMPAR(b, c, data) < 0 ? b : (COMPAR(a, c, data) < 0 ? c : a ))
+              :(COMPAR(b, c, data) > 0 ? b : (COMPAR(a, c, data) < 0 ? a : c ));
 }
 
-void
-qsort(void *a, size_t n, size_t es,
-    int (*cmp)(const void *, const void *))
+static void
+qsort_internal(void *a, size_t n, size_t es,
+    bool is_r, const union qsort_cmp *compar, void *data)
 {
 	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 	size_t d, r;
 	int swaptype, cmp_result;
 
 	_DIAGASSERT(a != NULL || n == 0 || es == 0);
-	_DIAGASSERT(cmp != NULL);
+	_DIAGASSERT(compar != NULL);
+	_DIAGASSERT(is_r ? compar->cmp_r != NULL : compar->cmp != NULL);
 
 loop:	SWAPINIT(a, es);
 	if (n < 7) {
 		for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
-			for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
+			for (pl = pm;
+			     pl > (char *) a && COMPAR(pl - es, pl, data) > 0;
 			     pl -= es)
 				swap(pl, pl - es);
 		return;
@@ -122,25 +143,25 @@ loop:	SWAPINIT(a, es);
 		pn = (char *) a + (n - 1) * es;
 		if (n > 40) {
 			d = (n / 8) * es;
-			pl = med3(pl, pl + d, pl + 2 * d, cmp);
-			pm = med3(pm - d, pm, pm + d, cmp);
-			pn = med3(pn - 2 * d, pn - d, pn, cmp);
+			pl = med3(pl, pl + d, pl + 2 * d, is_r, compar, data);
+			pm = med3(pm - d, pm, pm + d, is_r, compar, data);
+			pn = med3(pn - 2 * d, pn - d, pn, is_r, compar, data);
 		}
-		pm = med3(pl, pm, pn, cmp);
+		pm = med3(pl, pm, pn, is_r, compar, data);
 	}
 	swap(a, pm);
 	pa = pb = (char *) a + es;
 
 	pc = pd = (char *) a + (n - 1) * es;
 	for (;;) {
-		while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
+		while (pb <= pc && (cmp_result = COMPAR(pb, a, data)) <= 0) {
 			if (cmp_result == 0) {
 				swap(pa, pb);
 				pa += es;
 			}
 			pb += es;
 		}
-		while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
+		while (pb <= pc && (cmp_result = COMPAR(pc, a, data)) >= 0) {
 			if (cmp_result == 0) {
 				swap(pc, pd);
 				pd -= es;
@@ -160,12 +181,36 @@ loop:	SWAPINIT(a, es);
 	r = min((size_t)(pd - pc), pn - pd - es);
 	vecswap(pb, pn - r, r);
 	if ((r = pb - pa) > es)
-		qsort(a, r / es, es, cmp);
+		qsort_internal(a, r / es, es, is_r, compar, data);
 	if ((r = pd - pc) > es) { 
 		/* Iterate rather than recurse to save stack space */
 		a = pn - r;
 		n = r / es;
 		goto loop;
 	}
-/*		qsort(pn - r, r / es, es, cmp);*/
+/*		qsort_internal(pn - r, r / es, es, cmp);*/
+}
+
+////////////////////////////////////////////////////////////
+// qsort_r()
+
+void
+qsort_r(void *a, size_t n, size_t es,
+    int (*compar)(const void *, const void *, void *), void *data)
+{
+	union qsort_cmp cmp = { .cmp_r = compar };
+
+	qsort_internal(a, n, es, true, &cmp, data);
+}
+
+////////////////////////////////////////////////////////////
+// original qsort()
+
+void
+qsort(void *a, size_t n, size_t es,
+    int (*compar)(const void *, const void *))
+{
+	union qsort_cmp cmp = { .cmp = compar };
+
+	qsort_internal(a, n, es, false, &cmp, NULL);
 }
Index: sys/kern/kern_ksyms.c
===================================================================
RCS file: /cvsroot/src/sys/kern/kern_ksyms.c,v
retrieving revision 1.84
diff -u -p -r1.84 kern_ksyms.c
--- sys/kern/kern_ksyms.c	7 Jul 2016 06:55:43 -0000	1.84
+++ sys/kern/kern_ksyms.c	27 Aug 2016 20:06:47 -0000
@@ -397,7 +397,7 @@ addsymtab(const char *name, void *symsta
 	tab->sd_symsize = n * sizeof(Elf_Sym);
 	tab->sd_nglob = nglob;
 	addsymtab_strstart = str;
-	if (kheapsort(nsym, n, sizeof(Elf_Sym), addsymtab_compar, &ts) != 0)
+	if (kheapsort(nsym, n, sizeof(Elf_Sym), &ts, addsymtab_compar) != 0)
 		panic("addsymtab");
 
 #ifdef KDTRACE_HOOKS
Index: sys/lib/libkern/libkern.h
===================================================================
RCS file: /cvsroot/src/sys/lib/libkern/libkern.h,v
retrieving revision 1.124
diff -u -p -r1.124 libkern.h
--- sys/lib/libkern/libkern.h	7 Jul 2016 06:55:43 -0000	1.124
+++ sys/lib/libkern/libkern.h	27 Aug 2016 20:06:47 -0000
@@ -451,8 +451,10 @@ uintmax_t strtou(const char * __restrict
 
 int	 snprintb(char *, size_t, const char *, uint64_t);
 int	 snprintb_m(char *, size_t, const char *, uint64_t, size_t);
-int	 kheapsort(void *, size_t, size_t, int (*)(const void *, const void *),
-		   void *);
+int	 kheapsort(void *, size_t, size_t, void *,
+	    int (*)(const void *, const void *));
+int	 kheapsort_r(void *, size_t, size_t, void *,
+	    int (*)(const void *, const void *, void *), void *);
 uint32_t crc32(uint32_t, const uint8_t *, size_t);
 #if __GNUC_PREREQ__(4, 5) \
     && (defined(__alpha_cix__) || defined(__mips_popcount))
Index: sys/ufs/ext2fs/ext2fs_htree.c
===================================================================
RCS file: /cvsroot/src/sys/ufs/ext2fs/ext2fs_htree.c,v
retrieving revision 1.9
diff -u -p -r1.9 ext2fs_htree.c
--- sys/ufs/ext2fs/ext2fs_htree.c	23 Aug 2016 06:23:26 -0000	1.9
+++ sys/ufs/ext2fs/ext2fs_htree.c	27 Aug 2016 20:06:47 -0000
@@ -306,7 +306,7 @@ ext2fs_htree_split_dirblock(char *block1
 	 * Sort directory entry descriptors by name hash value.
 	 */
 	kheapsort(sort_info, entry_cnt, sizeof(struct ext2fs_htree_sort_entry),
-	    ext2fs_htree_cmp_sort_entry, &dummy);
+	    &dummy, ext2fs_htree_cmp_sort_entry);
 
 	/*
 	 * Count the number of entries to move to directory block 2.
Index: distrib/sets/lists/comp/mi
===================================================================
RCS file: /cvsroot/src/distrib/sets/lists/comp/mi,v
retrieving revision 1.2059
diff -u -p -r1.2059 mi
--- distrib/sets/lists/comp/mi	27 Aug 2016 08:03:47 -0000	1.2059
+++ distrib/sets/lists/comp/mi	27 Aug 2016 20:06:47 -0000
@@ -6693,6 +6693,7 @@
 ./usr/share/man/cat3/hdestroy1_r.0		comp-c-catman		.cat
 ./usr/share/man/cat3/hdestroy_r.0		comp-c-catman		.cat
 ./usr/share/man/cat3/heapsort.0			comp-c-catman		.cat
+./usr/share/man/cat3/heapsort_r.0		comp-c-catman		.cat
 ./usr/share/man/cat3/herror.0			comp-c-catman		.cat
 ./usr/share/man/cat3/hesiod.0			comp-c-catman		hesiod,.cat
 ./usr/share/man/cat3/hesiod_end.0		comp-c-catman		hesiod,.cat
@@ -7772,6 +7773,7 @@
 ./usr/share/man/cat3/menu_win.0			comp-c-catman		.cat
 ./usr/share/man/cat3/menus.0			comp-c-catman		.cat
 ./usr/share/man/cat3/mergesort.0		comp-c-catman		.cat
+./usr/share/man/cat3/mergesort_r.0		comp-c-catman		.cat
 ./usr/share/man/cat3/meta.0			comp-c-catman		.cat
 ./usr/share/man/cat3/mi_vector_hash.0		comp-c-catman		.cat
 ./usr/share/man/cat3/minor.0			comp-c-catman		.cat
@@ -8506,6 +8508,7 @@
 ./usr/share/man/cat3/qdiv.0			comp-c-catman		.cat
 ./usr/share/man/cat3/qiflush.0			comp-c-catman		.cat
 ./usr/share/man/cat3/qsort.0			comp-c-catman		.cat
+./usr/share/man/cat3/qsort_r.0			comp-c-catman		.cat
 ./usr/share/man/cat3/queue.0			comp-c-catman		.cat
 ./usr/share/man/cat3/quick_exit.0		comp-c-catman		.cat
 ./usr/share/man/cat3/quota_close.0		comp-c-catman		.cat
@@ -13975,6 +13978,7 @@
 ./usr/share/man/html3/hdestroy1_r.html		comp-c-htmlman		html
 ./usr/share/man/html3/hdestroy_r.html		comp-c-htmlman		html
 ./usr/share/man/html3/heapsort.html		comp-c-htmlman		html
+./usr/share/man/html3/heapsort_r.html		comp-c-htmlman		html
 ./usr/share/man/html3/herror.html		comp-c-htmlman		html
 ./usr/share/man/html3/hesiod.html		comp-c-htmlman		hesiod,html
 ./usr/share/man/html3/hesiod_end.html		comp-c-htmlman		hesiod,html
@@ -15021,6 +15025,7 @@
 ./usr/share/man/html3/menu_win.html		comp-c-htmlman		html
 ./usr/share/man/html3/menus.html		comp-c-htmlman		html
 ./usr/share/man/html3/mergesort.html		comp-c-htmlman		html
+./usr/share/man/html3/mergesort_r.html		comp-c-htmlman		html
 ./usr/share/man/html3/meta.html			comp-c-htmlman		html
 ./usr/share/man/html3/mi_vector_hash.html	comp-c-htmlman		html
 ./usr/share/man/html3/minor.html		comp-c-htmlman		html
@@ -15750,6 +15755,7 @@
 ./usr/share/man/html3/qdiv.html			comp-c-htmlman		html
 ./usr/share/man/html3/qiflush.html		comp-c-htmlman		html
 ./usr/share/man/html3/qsort.html		comp-c-htmlman		html
+./usr/share/man/html3/qsort_r.html		comp-c-htmlman		html
 ./usr/share/man/html3/queue.html		comp-c-htmlman		html
 ./usr/share/man/html3/quick_exit.html		comp-c-htmlman		html
 ./usr/share/man/html3/quota_close.html		comp-c-htmlman		html
@@ -21174,6 +21180,7 @@
 ./usr/share/man/man3/hdestroy1_r.3		comp-c-man		.man
 ./usr/share/man/man3/hdestroy_r.3		comp-c-man		.man
 ./usr/share/man/man3/heapsort.3			comp-c-man		.man
+./usr/share/man/man3/heapsort_r.3		comp-c-man		.man
 ./usr/share/man/man3/herror.3			comp-c-man		.man
 ./usr/share/man/man3/hesiod.3			comp-c-man		hesiod,.man
 ./usr/share/man/man3/hesiod_end.3		comp-c-man		hesiod,.man
@@ -22253,6 +22260,7 @@
 ./usr/share/man/man3/menu_win.3			comp-c-man		.man
 ./usr/share/man/man3/menus.3			comp-c-man		.man
 ./usr/share/man/man3/mergesort.3		comp-c-man		.man
+./usr/share/man/man3/mergesort_r.3		comp-c-man		.man
 ./usr/share/man/man3/meta.3			comp-c-man		.man
 ./usr/share/man/man3/mi_vector_hash.3		comp-c-man		.man
 ./usr/share/man/man3/minor.3			comp-c-man		.man
@@ -22987,6 +22995,7 @@
 ./usr/share/man/man3/qdiv.3			comp-c-man		.man
 ./usr/share/man/man3/qiflush.3			comp-c-man		.man
 ./usr/share/man/man3/qsort.3			comp-c-man		.man
+./usr/share/man/man3/qsort_r.3			comp-c-man		.man
 ./usr/share/man/man3/queue.3			comp-c-man		.man
 ./usr/share/man/man3/quick_exit.3		comp-c-man		.man
 ./usr/share/man/man3/quota_close.3		comp-c-man		.man

-- 
David A. Holland
dholland%netbsd.org@localhost