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.4 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,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 19430 invoked from network); 8 Aug 2021 20:31:20 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 8 Aug 2021 20:31:20 -0000 Received: (qmail 5257 invoked by uid 550); 8 Aug 2021 20:31:18 -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 5239 invoked from network); 8 Aug 2021 20:31:18 -0000 X-Virus-Scanned: Debian amavisd-new at disroot.org Mime-Version: 1.0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=disroot.org; s=mail; t=1628454664; bh=ebuQHrTVezyB06KS7GRgtS0VCAP1pwIy8CHMSaR30uI=; h=Cc:Subject:From:To:Date:In-Reply-To; b=BdETLz+5iPjN463/PM0y7muyMwrtLvaxNIbsthTeNdAG0hsckw8d/7fmaR5PwBfv2 tnqUV41Db1xG7VFmRJ7Wsig2s05EnQEfCD9SyjuJUJHmfDvLPjwcvdaJ2h0RK9xBRo OtP2wz7TVGtQRG5vQYM1BjWsWkd4Wzk2yhxlSo2uUPyl4HTGijQN4FFWSFDryyGF1O nnj8wTfaRpcLCVvlCrLnA+4I5MlExwSQBtV8e2kC1nuPT+YQq/gQf/pmVIQGQLJHl7 8MNOqZ122tMjDpOWnzpKoiwx9lbdq4DCwg6bTJLyzPFeI8KmO8pvF4UaGf+ed6f93L 5bvB1bmOOIaSA== Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=UTF-8 Cc: "Olivier Galibert" From: =?utf-8?q?=C3=89rico_Nogueira?= To: Date: Sun, 08 Aug 2021 17:28:32 -0300 Message-Id: In-Reply-To: <20210808112612.44230-1-galibert@pobox.com> Subject: Re: [musl] [PATCH] stdlib: implement qsort_r A similar implementation was suggested in https://inbox.vuxu.org/musl/20210309035652.32453-1-ericonr@disroot.org/ And mostly voted against, in favor of the wrapper implementation. On Sun Aug 8, 2021 at 8:26 AM -03, 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. > > --- > COPYRIGHT | 4 +- > include/stdlib.h | 4 + > src/stdlib/qsort.c | 200 +--------------------------------- > src/stdlib/qsort_common.ic | 218 +++++++++++++++++++++++++++++++++++++ > src/stdlib/qsort_r.c | 28 +++++ > 5 files changed, 257 insertions(+), 197 deletions(-) > create mode 100644 src/stdlib/qsort_common.ic > create mode 100644 src/stdlib/qsort_r.c > > diff --git a/COPYRIGHT b/COPYRIGHT > index c1628e9a..f5199541 100644 > --- a/COPYRIGHT > +++ b/COPYRIGHT > @@ -142,8 +142,8 @@ originally written by Solar Designer and placed into > the public > domain. The code also comes with a fallback permissive license for use > in jurisdictions that may not recognize the public domain. > =20 > -The smoothsort implementation (src/stdlib/qsort.c) is Copyright =C2=A9 2= 011 > -Valentin Ochs and is licensed under an MIT-style license. > +The smoothsort implementation (src/stdlib/qsort_common.ic) is > +Copyright =C2=A9 2011 Valentin Ochs and is licensed under an MIT-style > license. > =20 > The x86_64 port was written by Nicholas J. Kain and is licensed under > the standard MIT terms. > 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..b0ade53c 100644 > --- a/src/stdlib/qsort.c > +++ b/src/stdlib/qsort.c > @@ -19,200 +19,10 @@ > * IN THE SOFTWARE. > */ > =20 > -/* Minor changes by Rich Felker for integration in musl, 2011-04-27. */ > +/* Instanciate qsort */ > =20 > -/* Smoothsort, an adaptive variant of Heapsort. Memory usage: O(1). > - Run time: Worst case O(n log n), close to O(n) in the mostly-sorted > case. */ > +#define FN(function) function > +#define ARG_PROTO > +#define ARG > =20 > -#include > -#include > -#include > - > -#include "atomic.h" > -#define ntz(x) a_ctz_l((x)) > - > -typedef int (*cmpfun)(const void *, const void *); > - > -static inline int pntz(size_t p[2]) { > - int r =3D ntz(p[0] - 1); > - if(r !=3D 0 || (r =3D 8*sizeof(size_t) + ntz(p[1])) !=3D 8*sizeof(size_= t)) { > - return r; > - } > - return 0; > -} > - > -static void cycle(size_t width, unsigned char* ar[], int n) > -{ > - unsigned char tmp[256]; > - size_t l; > - int i; > - > - if(n < 2) { > - return; > - } > - > - ar[n] =3D tmp; > - while(width) { > - l =3D sizeof(tmp) < width ? sizeof(tmp) : width; > - memcpy(ar[n], ar[0], l); > - for(i =3D 0; i < n; i++) { > - memcpy(ar[i], ar[i + 1], l); > - ar[i] +=3D l; > - } > - width -=3D l; > - } > -} > - > -/* shl() and shr() need n > 0 */ > -static inline void shl(size_t p[2], int n) > -{ > - if(n >=3D 8 * sizeof(size_t)) { > - n -=3D 8 * sizeof(size_t); > - p[1] =3D p[0]; > - p[0] =3D 0; > - } > - p[1] <<=3D n; > - p[1] |=3D p[0] >> (sizeof(size_t) * 8 - n); > - p[0] <<=3D n; > -} > - > -static inline void shr(size_t p[2], int n) > -{ > - if(n >=3D 8 * sizeof(size_t)) { > - n -=3D 8 * sizeof(size_t); > - p[0] =3D p[1]; > - p[1] =3D 0; > - } > - p[0] >>=3D n; > - p[0] |=3D p[1] << (sizeof(size_t) * 8 - n); > - p[1] >>=3D n; > -} > - > -static void sift(unsigned char *head, size_t width, cmpfun cmp, int > pshift, size_t lp[]) > -{ > - unsigned char *rt, *lf; > - unsigned char *ar[14 * sizeof(size_t) + 1]; > - int i =3D 1; > - > - ar[0] =3D head; > - while(pshift > 1) { > - rt =3D head - width; > - lf =3D head - width - lp[pshift - 2]; > - > - if((*cmp)(ar[0], lf) >=3D 0 && (*cmp)(ar[0], rt) >=3D 0) { > - break; > - } > - if((*cmp)(lf, rt) >=3D 0) { > - ar[i++] =3D lf; > - head =3D lf; > - pshift -=3D 1; > - } else { > - ar[i++] =3D rt; > - head =3D rt; > - pshift -=3D 2; > - } > - } > - 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[]) > -{ > - unsigned char *stepson, > - *rt, *lf; > - size_t p[2]; > - unsigned char *ar[14 * sizeof(size_t) + 1]; > - int i =3D 1; > - int trail; > - > - p[0] =3D pp[0]; > - p[1] =3D pp[1]; > - > - 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) { > - 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) { > - break; > - } > - } > - > - ar[i++] =3D stepson; > - head =3D stepson; > - trail =3D pntz(p); > - shr(p, trail); > - pshift +=3D trail; > - trusty =3D 0; > - } > - if(!trusty) { > - cycle(width, ar, i); > - sift(head, width, cmp, pshift, lp); > - } > -} > - > -void qsort(void *base, size_t nel, size_t width, cmpfun cmp) > -{ > - size_t lp[12*sizeof(size_t)]; > - size_t i, size =3D width * nel; > - unsigned char *head, *high; > - size_t p[2] =3D {1, 0}; > - int pshift =3D 1; > - int trail; > - > - if (!size) return; > - > - head =3D base; > - high =3D head + size - width; > - > - /* Precompute Leonardo numbers, scaled by element width */ > - for(lp[0]=3Dlp[1]=3Dwidth, i=3D2; (lp[i]=3Dlp[i-2]+lp[i-1]+width) < siz= e; > i++); > - > - while(head < high) { > - if((p[0] & 3) =3D=3D 3) { > - sift(head, width, cmp, pshift, lp); > - shr(p, 2); > - pshift +=3D 2; > - } else { > - if(lp[pshift - 1] >=3D high - head) { > - trinkle(head, width, cmp, p, pshift, 0, lp); > - } else { > - sift(head, width, cmp, pshift, lp); > - } > - > - if(pshift =3D=3D 1) { > - shl(p, 1); > - pshift =3D 0; > - } else { > - shl(p, pshift - 1); > - pshift =3D 1; > - } > - } > - > - p[0] |=3D 1; > - head +=3D width; > - } > - > - trinkle(head, width, cmp, p, pshift, 0, lp); > - > - while(pshift !=3D 1 || p[0] !=3D 1 || p[1] !=3D 0) { > - if(pshift <=3D 1) { > - trail =3D pntz(p); > - shr(p, trail); > - pshift +=3D trail; > - } else { > - shl(p, 2); > - pshift -=3D 2; > - p[0] ^=3D 7; > - shr(p, 1); > - trinkle(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, lp); > - shl(p, 1); > - p[0] |=3D 1; > - trinkle(head - width, width, cmp, p, pshift, 1, lp); > - } > - head -=3D width; > - } > -} > +#include "qsort_common.ic" > diff --git a/src/stdlib/qsort_common.ic b/src/stdlib/qsort_common.ic > new file mode 100644 > index 00000000..099b1bf4 > --- /dev/null > +++ b/src/stdlib/qsort_common.ic > @@ -0,0 +1,218 @@ > +/* Copyright (C) 2011 by Valentin Ochs > + * > + * Permission is hereby granted, free of charge, to any person > obtaining a copy > + * of this software and associated documentation files (the > "Software"), to > + * deal in the Software without restriction, including without > limitation the > + * rights to use, copy, modify, merge, publish, distribute, sublicense, > and/or > + * sell copies of the Software, and to permit persons to whom the > Software is > + * furnished to do so, subject to the following conditions: > + * > + * The above copyright notice and this permission notice shall be > included in > + * all copies or substantial portions of the Software. > + * > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, > EXPRESS OR > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF > MERCHANTABILITY, > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT > SHALL THE > + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR > OTHER > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, > ARISING > + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER > DEALINGS > + * IN THE SOFTWARE. > + */ > + > +/* Minor changes by Rich Felker for integration in musl, 2011-04-27. */ > + > +/* Smoothsort, an adaptive variant of Heapsort. Memory usage: O(1). > + Run time: Worst case O(n log n), close to O(n) in the mostly-sorted > case. */ > + > +#include > +#include > +#include > + > +#include "atomic.h" > +#define ntz(x) a_ctz_l((x)) > + > +typedef int (*cmpfun)(const void *, const void * ARG_PROTO); > + > +static inline int pntz(size_t p[2]) { > + int r =3D ntz(p[0] - 1); > + if(r !=3D 0 || (r =3D 8*sizeof(size_t) + ntz(p[1])) !=3D 8*sizeof(size_= t)) { > + return r; > + } > + return 0; > +} > + > +static void FN(cycle)(size_t width, unsigned char* ar[], int n) > +{ > + unsigned char tmp[256]; > + size_t l; > + int i; > + > + if(n < 2) { > + return; > + } > + > + ar[n] =3D tmp; > + while(width) { > + l =3D sizeof(tmp) < width ? sizeof(tmp) : width; > + memcpy(ar[n], ar[0], l); > + for(i =3D 0; i < n; i++) { > + memcpy(ar[i], ar[i + 1], l); > + ar[i] +=3D l; > + } > + width -=3D l; > + } > +} > + > +/* shl() and shr() need n > 0 */ > +static inline void FN(shl)(size_t p[2], int n) > +{ > + if(n >=3D 8 * sizeof(size_t)) { > + n -=3D 8 * sizeof(size_t); > + p[1] =3D p[0]; > + p[0] =3D 0; > + } > + p[1] <<=3D n; > + p[1] |=3D p[0] >> (sizeof(size_t) * 8 - n); > + p[0] <<=3D n; > +} > + > +static inline void shr(size_t p[2], int n) > +{ > + if(n >=3D 8 * sizeof(size_t)) { > + n -=3D 8 * sizeof(size_t); > + p[0] =3D p[1]; > + p[1] =3D 0; > + } > + p[0] >>=3D n; > + p[0] |=3D p[1] << (sizeof(size_t) * 8 - n); > + p[1] >>=3D n; > +} > + > +static void FN(sift)(unsigned char *head, size_t width, cmpfun cmp, int > pshift, size_t lp[] ARG_PROTO) > +{ > + unsigned char *rt, *lf; > + unsigned char *ar[14 * sizeof(size_t) + 1]; > + int i =3D 1; > + > + ar[0] =3D head; > + while(pshift > 1) { > + rt =3D head - width; > + lf =3D head - width - lp[pshift - 2]; > + > + if((*cmp)(ar[0], lf ARG) >=3D 0 && (*cmp)(ar[0], rt ARG) >=3D 0) { > + break; > + } > + if((*cmp)(lf, rt ARG) >=3D 0) { > + ar[i++] =3D lf; > + head =3D lf; > + pshift -=3D 1; > + } else { > + ar[i++] =3D rt; > + head =3D rt; > + pshift -=3D 2; > + } > + } > + FN(cycle)(width, ar, i); > +} > + > +static void FN(trinkle)(unsigned char *head, size_t width, cmpfun cmp, > size_t pp[2], int pshift, int trusty, size_t lp[] ARG_PROTO) > +{ > + unsigned char *stepson, > + *rt, *lf; > + size_t p[2]; > + unsigned char *ar[14 * sizeof(size_t) + 1]; > + int i =3D 1; > + int trail; > + > + p[0] =3D pp[0]; > + p[1] =3D pp[1]; > + > + ar[0] =3D head; > + while(p[0] !=3D 1 || p[1] !=3D 0) { > + stepson =3D head - lp[pshift]; > + 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 ARG) >=3D 0 || (*cmp)(lf, stepson ARG) >=3D 0) { > + break; > + } > + } > + > + ar[i++] =3D stepson; > + head =3D stepson; > + trail =3D pntz(p); > + shr(p, trail); > + pshift +=3D trail; > + trusty =3D 0; > + } > + if(!trusty) { > + FN(cycle)(width, ar, i); > + FN(sift)(head, width, cmp, pshift, lp ARG); > + } > +} > + > +void FN(qsort)(void *base, size_t nel, size_t width, cmpfun cmp > ARG_PROTO) > +{ > + size_t lp[12*sizeof(size_t)]; > + size_t i, size =3D width * nel; > + unsigned char *head, *high; > + size_t p[2] =3D {1, 0}; > + int pshift =3D 1; > + int trail; > + > + if (!size) return; > + > + head =3D base; > + high =3D head + size - width; > + > + /* Precompute Leonardo numbers, scaled by element width */ > + for(lp[0]=3Dlp[1]=3Dwidth, i=3D2; (lp[i]=3Dlp[i-2]+lp[i-1]+width) < siz= e; > i++); > + > + while(head < high) { > + if((p[0] & 3) =3D=3D 3) { > + FN(sift)(head, width, cmp, pshift, lp ARG); > + shr(p, 2); > + pshift +=3D 2; > + } else { > + if(lp[pshift - 1] >=3D high - head) { > + FN(trinkle)(head, width, cmp, p, pshift, 0, lp ARG); > + } else { > + FN(sift)(head, width, cmp, pshift, lp ARG); > + } > + > + if(pshift =3D=3D 1) { > + FN(shl)(p, 1); > + pshift =3D 0; > + } else { > + FN(shl)(p, pshift - 1); > + pshift =3D 1; > + } > + } > + > + p[0] |=3D 1; > + head +=3D width; > + } > + > + FN(trinkle)(head, width, cmp, p, pshift, 0, lp ARG); > + > + while(pshift !=3D 1 || p[0] !=3D 1 || p[1] !=3D 0) { > + if(pshift <=3D 1) { > + trail =3D pntz(p); > + shr(p, trail); > + pshift +=3D trail; > + } else { > + FN(shl)(p, 2); > + pshift -=3D 2; > + p[0] ^=3D 7; > + shr(p, 1); > + FN(trinkle)(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, > lp ARG); > + FN(shl)(p, 1); > + p[0] |=3D 1; > + FN(trinkle)(head - width, width, cmp, p, pshift, 1, lp ARG); > + } > + head -=3D width; > + } > +} > diff --git a/src/stdlib/qsort_r.c b/src/stdlib/qsort_r.c > new file mode 100644 > index 00000000..d57e4a1e > --- /dev/null > +++ b/src/stdlib/qsort_r.c > @@ -0,0 +1,28 @@ > +/* Copyright (C) 2011 by Valentin Ochs > + * > + * Permission is hereby granted, free of charge, to any person > obtaining a copy > + * of this software and associated documentation files (the > "Software"), to > + * deal in the Software without restriction, including without > limitation the > + * rights to use, copy, modify, merge, publish, distribute, sublicense, > and/or > + * sell copies of the Software, and to permit persons to whom the > Software is > + * furnished to do so, subject to the following conditions: > + * > + * The above copyright notice and this permission notice shall be > included in > + * all copies or substantial portions of the Software. > + * > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, > EXPRESS OR > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF > MERCHANTABILITY, > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT > SHALL THE > + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR > OTHER > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, > ARISING > + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER > DEALINGS > + * IN THE SOFTWARE. > + */ > + > +/* Instanciate qsort_r */ > + > +#define FN(function) function##_r > +#define ARG_PROTO , void *arg > +#define ARG , arg > + > +#include "qsort_common.ic" >From what I have seen, musl prefers using .h files for these situations instead of inventing new file extensions. It is also my belief that the version I linked was more readable. > -- > 2.32.0