From: Olivier Galibert <galibert@pobox.com>
To: musl@lists.openwall.com
Cc: Olivier Galibert <galibert@pobox.com>
Subject: [musl] [PATCH] stdlib: implement qsort_r
Date: Wed, 18 Aug 2021 19:36:53 +0200 [thread overview]
Message-ID: <20210818173652.9997-1-galibert@pobox.com> (raw)
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 *));
+#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))
typedef int (*cmpfun)(const void *, const void *);
+typedef int (*cmpfun_r)(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_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 = 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_r 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_r cmp, void *arg)
{
size_t lp[12*sizeof(size_t)];
size_t i, size = width * nel;
@@ -173,14 +174,14 @@ 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) {
@@ -196,7 +197,7 @@ void qsort(void *base, size_t nel, size_t width, cmpfun cmp)
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,21 @@ 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;
}
}
+
+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);
+}
--
2.32.0
next reply other threads:[~2021-08-18 17:41 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-08-18 17:36 Olivier Galibert [this message]
2021-08-18 20:18 ` Rich Felker
-- strict thread matches above, loose matches on Subject: below --
2021-08-08 11:26 Olivier Galibert
2021-08-08 12:42 ` Jon Chesterfield
2021-08-08 19:39 ` Olivier Galibert
2021-08-08 20:35 ` Érico Nogueira
2021-08-08 21:21 ` Jon Chesterfield
2021-08-08 23:05 ` Rich Felker
2021-08-09 6:03 ` Olivier Galibert
2021-08-09 17:27 ` Florian Weimer
2021-08-08 20:28 ` Érico Nogueira
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20210818173652.9997-1-galibert@pobox.com \
--to=galibert@pobox.com \
--cc=musl@lists.openwall.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).