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 21535 invoked from network); 8 Aug 2021 11:29:11 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 8 Aug 2021 11:29:11 -0000 Received: (qmail 18350 invoked by uid 550); 8 Aug 2021 11:29:06 -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 18314 invoked from network); 8 Aug 2021 11:29:05 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed; d=pobox.com; h=from:to:cc :subject:date:message-id:mime-version:content-type :content-transfer-encoding; s=sasl; bh=Lo4N4+SyfbU73HzeuqrHaB8DQ r74WjvjTrGDdVZeirY=; b=FP9BjdRP6aZ0xiDMrSyCC2fJOItwTtD8YDDVhz9Ad VXdc3hB2rT2Zv3cCXeQGifD797tTDk7ifCTulr5Ql/+LXCWoVYHM0WJUC6nMxMuf dy1FEeFi/4iHHs6PzDyh44J14PgXo1it1MTdCHCDXlgV1OEbyBWNHBzBI6Gn4E2i YY= From: Olivier Galibert To: musl@lists.openwall.com Cc: Olivier Galibert Date: Sun, 8 Aug 2021 13:26:13 +0200 Message-Id: <20210808112612.44230-1-galibert@pobox.com> X-Mailer: git-send-email 2.32.0 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Pobox-Relay-ID: CD8C6434-F83B-11EB-9F10-8B3BC6D8090B-92059326!pb-smtp1.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. --- 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 l= icense. =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 c= ase. */ +#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 pshi= ft, 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); - } - =09 - if(pshift =3D=3D 1) { - shl(p, 1); - pshift =3D 0; - } else { - shl(p, pshift - 1); - pshift =3D 1; - } - } - =09 - 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 limitatio= n the + * rights to use, copy, modify, merge, publish, distribute, sublicense, = and/or + * sell copies of the Software, and to permit persons to whom the Softwa= re is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be includ= ed in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRE= SS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILI= TY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHA= LL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHE= R + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISI= NG + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER D= EALINGS + * 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 c= ase. */ + +#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, s= ize_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_PROT= O) +{ + 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); + } + =09 + if(pshift =3D=3D 1) { + FN(shl)(p, 1); + pshift =3D 0; + } else { + FN(shl)(p, pshift - 1); + pshift =3D 1; + } + } + =09 + 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 limitatio= n the + * rights to use, copy, modify, merge, publish, distribute, sublicense, = and/or + * sell copies of the Software, and to permit persons to whom the Softwa= re is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be includ= ed in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRE= SS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILI= TY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHA= LL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHE= R + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISI= NG + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER D= EALINGS + * IN THE SOFTWARE. + */ + +/* Instanciate qsort_r */ + +#define FN(function) function##_r +#define ARG_PROTO , void *arg +#define ARG , arg + +#include "qsort_common.ic" --=20 2.32.0