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.1 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, 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 4068 invoked from network); 18 Aug 2021 17:41:05 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 18 Aug 2021 17:41:05 -0000 Received: (qmail 32462 invoked by uid 550); 18 Aug 2021 17:41:01 -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 32430 invoked from network); 18 Aug 2021 17:41:00 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed; d=pobox.com; h=from:to:cc :subject:date:message-id:mime-version:content-transfer-encoding; s=sasl; bh=Rz35MaBeDshOsEPEMFCVO1DrR0Ur/whg92G2cOcr3SQ=; b=gALF Q8FS0Nq4B9a96bL9k3gl/bjBgQ0wtPnAF0eQ3AsSqBvLjcNbtKnwwJkcDyFTBkKS Y0GwfugVdDCOkXdwRuIExQwLNv+UUxDKkCbf16dTpX/OqvhLSfP9XFW2f4njjC3e 2uOeQ/sbc53OIfn2G+9OHxPzLQEo/QU7bn1QrbY= From: Olivier Galibert To: musl@lists.openwall.com Cc: Olivier Galibert Date: Wed, 18 Aug 2021 19:36:53 +0200 Message-Id: <20210818173652.9997-1-galibert@pobox.com> X-Mailer: git-send-email 2.32.0 MIME-Version: 1.0 X-Pobox-Relay-ID: 6A97F07E-004B-11EC-AA09-D5C30F5B5667-92059326!pb-smtp20.pobox.com Content-Transfer-Encoding: quoted-printable Subject: [musl] [PATCH] stdlib: implement qsort_r 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. 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 *))= ; =20 +#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)) =20 typedef int (*cmpfun)(const void *, const void *); +typedef int (*cmpfun_r)(const void *, const void *, void *); =20 static inline int pntz(size_t p[2]) { int r =3D ntz(p[0] - 1); @@ -88,7 +89,7 @@ static inline void shr(size_t p[2], int n) p[1] >>=3D n; } =20 -static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshi= ft, 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 =3D head - width; lf =3D head - width - lp[pshift - 2]; =20 - if((*cmp)(ar[0], lf) >=3D 0 && (*cmp)(ar[0], rt) >=3D 0) { + if((*cmp)(ar[0], lf, arg) >=3D 0 && (*cmp)(ar[0], rt, arg) >=3D 0) { break; } - if((*cmp)(lf, rt) >=3D 0) { + if((*cmp)(lf, rt, arg) >=3D 0) { ar[i++] =3D lf; head =3D lf; pshift -=3D 1; @@ -115,7 +116,7 @@ static void sift(unsigned char *head, size_t width, c= mpfun cmp, int pshift, size cycle(width, ar, i); } =20 -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, voi= d *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 wid= th, cmpfun cmp, size_t pp[2], ar[0] =3D head; while(p[0] !=3D 1 || p[1] !=3D 0) { stepson =3D head - lp[pshift]; - if((*cmp)(stepson, ar[0]) <=3D 0) { + if((*cmp)(stepson, ar[0], arg) <=3D 0) { break; } if(!trusty && pshift > 1) { rt =3D head - width; lf =3D head - width - lp[pshift - 2]; - if((*cmp)(rt, stepson) >=3D 0 || (*cmp)(lf, stepson) >=3D 0) { + if((*cmp)(rt, stepson, arg) >=3D 0 || (*cmp)(lf, stepson, arg) >=3D 0= ) { break; } } @@ -150,11 +151,11 @@ static void trinkle(unsigned char *head, size_t wid= th, 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); } } =20 -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 *a= rg) { size_t lp[12*sizeof(size_t)]; size_t i, size =3D width * nel; @@ -173,14 +174,14 @@ void qsort(void *base, size_t nel, size_t width, cm= pfun cmp) =20 while(head < high) { if((p[0] & 3) =3D=3D 3) { - sift(head, width, cmp, pshift, lp); + sift(head, width, cmp, arg, pshift, lp); shr(p, 2); pshift +=3D 2; } else { if(lp[pshift - 1] >=3D 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); } =09 if(pshift =3D=3D 1) { @@ -196,7 +197,7 @@ void qsort(void *base, size_t nel, size_t width, cmpf= un cmp) head +=3D width; } =20 - trinkle(head, width, cmp, p, pshift, 0, lp); + trinkle(head, width, cmp, arg, p, pshift, 0, lp); =20 while(pshift !=3D 1 || p[0] !=3D 1 || p[1] !=3D 0) { if(pshift <=3D 1) { @@ -208,11 +209,21 @@ void qsort(void *base, size_t nel, size_t width, cm= pfun cmp) pshift -=3D 2; p[0] ^=3D 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] |=3D 1; - trinkle(head - width, width, cmp, p, pshift, 1, lp); + trinkle(head - width, width, cmp, arg, p, pshift, 1, lp); } head -=3D 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); +} --=20 2.32.0