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 30825 invoked from network); 9 Mar 2021 21:02:55 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 9 Mar 2021 21:02:55 -0000 Received: (qmail 31980 invoked by uid 550); 9 Mar 2021 21:02:50 -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 31950 invoked from network); 9 Mar 2021 21:02:49 -0000 X-Virus-Scanned: Debian amavisd-new at disroot.org From: =?UTF-8?q?=C3=89rico=20Nogueira?= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=disroot.org; s=mail; t=1615323756; bh=WvSYaPbxczVTXopEq6OGngAITsYeQ+5Q+1AM11CgLd8=; h=From:To:Cc:Subject:Date; b=QiGvgpEwCIz1CAg0SCb34op35yzYGNLCj1cR/bNVJYfdQphNyrbnOX0UjfLvbG6fD L67wR+GOTQHs/Evo6GJjbiyps4CxNdWdzyM6OEHrBGErms652ObfsLtCAxJbEfLDbG YcUJZgW7rBnMOuK+dh5ri/x5kmY7PDkXaOPfErmwVCxJNv2Ah+GOJaPzXM7Cf+LXEG NcU/xKrXOH3BG9HCJEl+ADenpJlzun8zUBDtGHBp6tKsTfNysROpD4c+Z1ShYUMdix Rcz9rWNoWAJjDHmbt5EY7QHDiy0zJg9u6qcCg80tz7R1W58oFKk+8ER8tqzJ30qcTc D16wWQK8GvUQw== To: musl@lists.openwall.com Cc: =?UTF-8?q?=C3=89rico=20Nogueira?= Date: Tue, 9 Mar 2021 18:02:13 -0300 Message-Id: <20210309210213.29539-1-ericonr@disroot.org> Mime-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [musl] [PATCH v3] add qsort_r and make qsort a wrapper around it we make qsort a wrapper by providing a wrapper_cmp function that uses the extra argument as a function pointer. should be optimized to a tail call on most architectures, as long as it's built with -fomit-frame-pointer, so the performance impact should be minimal. to keep the git history clean, for now qsort_r is implemented in qsort.c and qsort is implemented in qsort_nr.c. qsort.c also received a few trivial cleanups, including replacing (*cmp)() calls with cmp(). qsort_nr.c contains only wrapper_cmp and qsort as a qsort_r wrapper itself. --- Following suggestions from IRC, as few changes as possible to the files, a final clean up commit after this one would involve some git mv's (I won't make a patch for it). Added weak_alias to force qsort to use libc's qsort_r. If this can't be accepted due to the overhead on some archs (ppc, mips, arm in some situations?), maybe we could revisit v2 of the patch? include/stdlib.h | 1 + src/include/stdlib.h | 1 + src/stdlib/qsort.c | 37 ++++++++++++++++++++----------------- src/stdlib/qsort_nr.c | 14 ++++++++++++++ 4 files changed, 36 insertions(+), 17 deletions(-) create mode 100644 src/stdlib/qsort_nr.c diff --git a/include/stdlib.h b/include/stdlib.h index b54a051f..0c0ced5f 100644 --- a/include/stdlib.h +++ b/include/stdlib.h @@ -158,6 +158,7 @@ struct __locale_struct; float strtof_l(const char *__restrict, char **__restrict, struct __locale_struct *); double strtod_l(const char *__restrict, char **__restrict, struct __locale_struct *); long double strtold_l(const char *__restrict, char **__restrict, struct __locale_struct *); +void qsort_r (void *, size_t, size_t, int (*)(const void *, const void *, void *), void *); #endif #if defined(_LARGEFILE64_SOURCE) || defined(_GNU_SOURCE) diff --git a/src/include/stdlib.h b/src/include/stdlib.h index e9da2015..812b04de 100644 --- a/src/include/stdlib.h +++ b/src/include/stdlib.h @@ -8,6 +8,7 @@ hidden void __env_rm_add(char *, char *); hidden int __mkostemps(char *, int, int); hidden int __ptsname_r(int, char *, size_t); hidden char *__randname(char *); +hidden void __qsort_r (void *, size_t, size_t, int (*)(const void *, const void *, void *), void *); hidden void *__libc_malloc(size_t); hidden void *__libc_malloc_impl(size_t); diff --git a/src/stdlib/qsort.c b/src/stdlib/qsort.c index da58fd31..20e40dda 100644 --- a/src/stdlib/qsort.c +++ b/src/stdlib/qsort.c @@ -24,6 +24,7 @@ /* 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 _GNU_SOURCE #include #include #include @@ -31,7 +32,7 @@ #include "atomic.h" #define ntz(x) a_ctz_l((x)) -typedef int (*cmpfun)(const void *, const void *); +typedef int (*cmpfun)(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 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 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 cmp, void *arg) { size_t lp[12*sizeof(size_t)]; size_t i, size = width * nel; @@ -173,16 +174,16 @@ 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) { shl(p, 1); pshift = 0; @@ -191,12 +192,12 @@ void qsort(void *base, size_t nel, size_t width, cmpfun cmp) pshift = 1; } } - + p[0] |= 1; 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,13 @@ 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; } } + +weak_alias(__qsort_r, qsort_r); diff --git a/src/stdlib/qsort_nr.c b/src/stdlib/qsort_nr.c new file mode 100644 index 00000000..fe408fb1 --- /dev/null +++ b/src/stdlib/qsort_nr.c @@ -0,0 +1,14 @@ +#define _GNU_SOURCE +#include + +typedef int (*cmpfun)(const void *, const void *); + +static int wrapper_cmp(const void *v1, const void *v2, void *cmp) +{ + return ((cmpfun)cmp)(v1, v2); +} + +void qsort(void *base, size_t nel, size_t width, cmpfun cmp) +{ + __qsort_r(base, nel, width, wrapper_cmp, cmp); +} -- 2.30.2