Re: [musl] [PATCH] stdlib: implement qsort_r

[Rich Felker <dalias@libc.org>]

On Wed, Aug 18, 2021 at 07:36:53PM +0200, Olivier Galibert wrote:
> The extension qsort_r allows calling qsort on a list of indices
> without having a global variable to hold the data to sort.
> ---
> 
> I didn't see a "clean" patch for the wrapper version in the thread, so
> here is one.  Passes libc-test, of course.

Here is the original patch, which also handles namespace correctly and
separates the translation units:

https://www.openwall.com/lists/musl/2021/03/09/10

Otherwise I think yours is roughly the same. I haven't checked whether
there are any other differences that should be resolved.

One change that should be made to either is that qsort_r should be
under _BSD_SOURCE, not _GNU_SOURCE.

>  include/stdlib.h   |  4 ++++
>  src/stdlib/qsort.c | 39 +++++++++++++++++++++++++--------------
>  2 files changed, 29 insertions(+), 14 deletions(-)
> 
> diff --git a/include/stdlib.h b/include/stdlib.h
> index b54a051f..cacb61bf 100644
> --- a/include/stdlib.h
> +++ b/include/stdlib.h
> @@ -55,6 +55,10 @@ int system (const char *);
>  void *bsearch (const void *, const void *, size_t, size_t, int (*)(const void *, const void *));
>  void qsort (void *, size_t, size_t, int (*)(const void *, const void *));
>  
> +#if defined(_GNU_SOURCE)
> +  void qsort_r (void *, size_t, size_t, int (*)(const void *, const void *, void *), void *);
> +#endif
> +
>  int abs (int);
>  long labs (long);
>  long long llabs (long long);
> diff --git a/src/stdlib/qsort.c b/src/stdlib/qsort.c
> index da58fd31..9add0ac5 100644
> --- a/src/stdlib/qsort.c
> +++ b/src/stdlib/qsort.c
> @@ -32,6 +32,7 @@
>  #define ntz(x) a_ctz_l((x))
>  
>  typedef int (*cmpfun)(const void *, const void *);
> +typedef int (*cmpfun_r)(const void *, const void *, void *);
>  
>  static inline int pntz(size_t p[2]) {
>  	int r = ntz(p[0] - 1);
> @@ -88,7 +89,7 @@ static inline void shr(size_t p[2], int n)
>  	p[1] >>= n;
>  }
>  
> -static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshift, size_t lp[])
> +static void sift(unsigned char *head, size_t width, cmpfun_r cmp, void *arg, int pshift, size_t lp[])
>  {
>  	unsigned char *rt, *lf;
>  	unsigned char *ar[14 * sizeof(size_t) + 1];
> @@ -99,10 +100,10 @@ static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshift, size
>  		rt = head - width;
>  		lf = head - width - lp[pshift - 2];
>  
> -		if((*cmp)(ar[0], lf) >= 0 && (*cmp)(ar[0], rt) >= 0) {
> +		if((*cmp)(ar[0], lf, arg) >= 0 && (*cmp)(ar[0], rt, arg) >= 0) {
>  			break;
>  		}
> -		if((*cmp)(lf, rt) >= 0) {
> +		if((*cmp)(lf, rt, arg) >= 0) {
>  			ar[i++] = lf;
>  			head = lf;
>  			pshift -= 1;
> @@ -115,7 +116,7 @@ static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshift, size
>  	cycle(width, ar, i);
>  }
>  
> -static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2], int pshift, int trusty, size_t lp[])
> +static void trinkle(unsigned char *head, size_t width, cmpfun_r cmp, void *arg, size_t pp[2], int pshift, int trusty, size_t lp[])
>  {
>  	unsigned char *stepson,
>  	              *rt, *lf;
> @@ -130,13 +131,13 @@ static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2],
>  	ar[0] = head;
>  	while(p[0] != 1 || p[1] != 0) {
>  		stepson = head - lp[pshift];
> -		if((*cmp)(stepson, ar[0]) <= 0) {
> +		if((*cmp)(stepson, ar[0], arg) <= 0) {
>  			break;
>  		}
>  		if(!trusty && pshift > 1) {
>  			rt = head - width;
>  			lf = head - width - lp[pshift - 2];
> -			if((*cmp)(rt, stepson) >= 0 || (*cmp)(lf, stepson) >= 0) {
> +			if((*cmp)(rt, stepson, arg) >= 0 || (*cmp)(lf, stepson, arg) >= 0) {
>  				break;
>  			}
>  		}
> @@ -150,11 +151,11 @@ static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2],
>  	}
>  	if(!trusty) {
>  		cycle(width, ar, i);
> -		sift(head, width, cmp, pshift, lp);
> +		sift(head, width, cmp, arg, pshift, lp);
>  	}
>  }
>  
> -void qsort(void *base, size_t nel, size_t width, cmpfun cmp)
> +void qsort_r(void *base, size_t nel, size_t width, cmpfun_r cmp, void *arg)
>  {
>  	size_t lp[12*sizeof(size_t)];
>  	size_t i, size = width * nel;
> @@ -173,14 +174,14 @@ void qsort(void *base, size_t nel, size_t width, cmpfun cmp)
>  
>  	while(head < high) {
>  		if((p[0] & 3) == 3) {
> -			sift(head, width, cmp, pshift, lp);
> +			sift(head, width, cmp, arg, pshift, lp);
>  			shr(p, 2);
>  			pshift += 2;
>  		} else {
>  			if(lp[pshift - 1] >= high - head) {
> -				trinkle(head, width, cmp, p, pshift, 0, lp);
> +				trinkle(head, width, cmp, arg, p, pshift, 0, lp);
>  			} else {
> -				sift(head, width, cmp, pshift, lp);
> +				sift(head, width, cmp, arg, pshift, lp);
>  			}
>  			
>  			if(pshift == 1) {
> @@ -196,7 +197,7 @@ void qsort(void *base, size_t nel, size_t width, cmpfun cmp)
>  		head += width;
>  	}
>  
> -	trinkle(head, width, cmp, p, pshift, 0, lp);
> +	trinkle(head, width, cmp, arg, p, pshift, 0, lp);
>  
>  	while(pshift != 1 || p[0] != 1 || p[1] != 0) {
>  		if(pshift <= 1) {
> @@ -208,11 +209,21 @@ void qsort(void *base, size_t nel, size_t width, cmpfun cmp)
>  			pshift -= 2;
>  			p[0] ^= 7;
>  			shr(p, 1);
> -			trinkle(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, lp);
> +			trinkle(head - lp[pshift] - width, width, cmp, arg, p, pshift + 1, 1, lp);
>  			shl(p, 1);
>  			p[0] |= 1;
> -			trinkle(head - width, width, cmp, p, pshift, 1, lp);
> +			trinkle(head - width, width, cmp, arg, p, pshift, 1, lp);
>  		}
>  		head -= width;
>  	}
>  }
> +
> +static int qsort_cmp(const void *e1, const void *e2, void *arg)
> +{
> +	return ((cmpfun)arg)(e1, e2);
> +}
> +
> +void qsort(void *base, size_t nel, size_t width, cmpfun cmp)
> +{
> +	return qsort_r(base, nel, width, qsort_cmp, cmp);
> +}
> -- 
> 2.32.0