From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.3 required=5.0 tests=MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 24012 invoked from network); 18 Aug 2021 20:18:43 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 18 Aug 2021 20:18:43 -0000 Received: (qmail 18097 invoked by uid 550); 18 Aug 2021 20:18:41 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 18077 invoked from network); 18 Aug 2021 20:18:40 -0000 Date: Wed, 18 Aug 2021 16:18:27 -0400 From: Rich Felker To: Olivier Galibert Cc: musl@lists.openwall.com Message-ID: <20210818201827.GM13220@brightrain.aerifal.cx> References: <20210818173652.9997-1-galibert@pobox.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20210818173652.9997-1-galibert@pobox.com> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] [PATCH] stdlib: implement qsort_r 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