[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-Id: <20210309035652.32453-1-ericonr@disroot.org>
Date: Tue, 9 Mar 2021 00:56:52 -0300
From: Érico Nogueira <ericonr@...root.org>
To: musl@...ts.openwall.com
Cc: Érico Nogueira <ericonr@...root.org>
Subject: [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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
