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 8963 invoked from network); 9 Mar 2021 03:57:35 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 9 Mar 2021 03:57:35 -0000 Received: (qmail 16263 invoked by uid 550); 9 Mar 2021 03:57:25 -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 16230 invoked from network); 9 Mar 2021 03:57:24 -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=1615262232; bh=DEnGnTE/ywQjTzuAxHD74qyNG9SQYFcwskai5DCpduQ=; h=From:To:Cc:Subject:Date; b=aUpYzhncreRUvH9HuM4iex8dNzCG9J7AfWiCCqJL0OhMC0EuuiL1vrcN+s4TPZCkx 2wXDJWARXDmbcAnc3SxJ0eEg4K3XnoLXhuNnyVvOy/eWq0y8AFzzmKmOS6cDxauDZp wRK8aoQAVFfG6hI81qaYdNRK+dBa7lo9EiHneZuVhMDkbVTwjcxZ77+l0KVBD0k9+z QjzeEkDbPzBg8/7nm1AkZImQiNELVvP/VM356if85/G/fT2kqm5VcLNCpzUp2DIR6H u+f6y0O5tI3C+oRxN4FJAabNXB+hPaqAbhr7+bdmleHRgr23o+b1KkkS2aJFdH/NfV 6V8205CdsZeAA== To: musl@lists.openwall.com Cc: =?UTF-8?q?=C3=89rico=20Nogueira?= Date: Tue, 9 Mar 2021 00:56:52 -0300 Message-Id: <20210309035652.32453-1-ericonr@disroot.org> Mime-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [musl] [PATCH v2] add qsort_r. since most discussion around the addition of this function has centered around the possible code duplication it requires or that qsort would become much slower if implemented as a wrapper around qsort_r, this commit uses a qsort.c file that's included with the appropriate definitions in order to generate qsort_r. this avoids code duplication and the efficiency loss, at the cost of greater binary size - size(1) reports 602282 vs 600673. this commit requires that the extra argument used by qsort_r always be called 'arg', and it should be the first argument of the function, which allows the usage of variadic macros to call the implementation internal functions, instead of requiring the addition of multiple macros with hard to read definitions. it also requires the comparison function always be called 'cmp'. some of the other functions which don't deal with 'cmp' or 'arg' can probably be factored out into a separate file, allowing for possibly smaller code size, but that hasn't been tried yet. --- And of course, right after I sent the patch I realized there was a much smaller diff that could be applied instead. Sorry for the noise. include/stdlib.h | 1 + src/stdlib/qsort.c | 38 ++++++++++++++++++++++++++++++-------- src/stdlib/qsort_r.c | 2 ++ 3 files changed, 33 insertions(+), 8 deletions(-) create mode 100644 src/stdlib/qsort_r.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/stdlib/qsort.c b/src/stdlib/qsort.c index da58fd31..16dbb50b 100644 --- a/src/stdlib/qsort.c +++ b/src/stdlib/qsort.c @@ -31,7 +31,13 @@ #include "atomic.h" #define ntz(x) a_ctz_l((x)) +#ifdef QSORT_R +typedef int (*cmpfun)(const void *, const void *, void *); +# define call_cmp(v1,v2) ((*cmp)(v1,v2,arg)) +#else typedef int (*cmpfun)(const void *, const void *); +# define call_cmp(v1,v2) ((*cmp)(v1,v2)) +#endif static inline int pntz(size_t p[2]) { int r = ntz(p[0] - 1); @@ -88,7 +94,13 @@ 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[]) +#ifdef QSORT_R +# define sift(...) sift_impl(arg, __VA_ARGS__) +static void sift_impl(void *arg, unsigned char *head, size_t width, cmpfun cmp, int pshift, size_t lp[]) +#else +# define sift sift_impl +static void sift_impl(unsigned char *head, size_t width, cmpfun cmp, int pshift, size_t lp[]) +#endif { unsigned char *rt, *lf; unsigned char *ar[14 * sizeof(size_t) + 1]; @@ -99,10 +111,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(call_cmp(ar[0], lf) >= 0 && call_cmp(ar[0], rt) >= 0) { break; } - if((*cmp)(lf, rt) >= 0) { + if(call_cmp(lf, rt) >= 0) { ar[i++] = lf; head = lf; pshift -= 1; @@ -115,7 +127,13 @@ 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[]) +#ifdef QSORT_R +# define trinkle(...) trinkle_impl(arg, __VA_ARGS__) +static void trinkle_impl(void *arg, unsigned char *head, size_t width, cmpfun cmp, size_t pp[2], int pshift, int trusty, size_t lp[]) +#else +# define trinkle trinkle_impl +static void trinkle_impl(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2], int pshift, int trusty, size_t lp[]) +#endif { unsigned char *stepson, *rt, *lf; @@ -130,13 +148,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(call_cmp(stepson, ar[0]) <= 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(call_cmp(rt, stepson) >= 0 || call_cmp(lf, stepson) >= 0) { break; } } @@ -154,7 +172,11 @@ static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2], } } +#ifdef QSORT_R +void qsort_r(void *base, size_t nel, size_t width, cmpfun cmp, void *arg) +#else void qsort(void *base, size_t nel, size_t width, cmpfun cmp) +#endif { size_t lp[12*sizeof(size_t)]; size_t i, size = width * nel; @@ -182,7 +204,7 @@ void qsort(void *base, size_t nel, size_t width, cmpfun cmp) } else { sift(head, width, cmp, pshift, lp); } - + if(pshift == 1) { shl(p, 1); pshift = 0; @@ -191,7 +213,7 @@ void qsort(void *base, size_t nel, size_t width, cmpfun cmp) pshift = 1; } } - + p[0] |= 1; head += width; } diff --git a/src/stdlib/qsort_r.c b/src/stdlib/qsort_r.c new file mode 100644 index 00000000..48dc04f1 --- /dev/null +++ b/src/stdlib/qsort_r.c @@ -0,0 +1,2 @@ +#define QSORT_R +#include "qsort.c" -- 2.30.1