aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMilan P. Stanić <mps@arvanta.net>2021-09-22 08:51:56 +0000
committerMilan P. Stanić <mps@arvanta.net>2021-09-23 21:04:55 +0000
commitbf5bbfdbf780092f387b7abe401fbfceda90c84d (patch)
treebc29c735813f4eb948b2bb6f7b9c31871263cdfd
parent0f2323f228dc8714e8e1f9480fa9234ac8a276e5 (diff)
downloadaports-bf5bbfdbf780092f387b7abe401fbfceda90c84d.tar.gz
aports-bf5bbfdbf780092f387b7abe401fbfceda90c84d.tar.bz2
aports-bf5bbfdbf780092f387b7abe401fbfceda90c84d.tar.xz
main/musl: add qsort_r patch
this (or modified) patch will be included in next musl release confirmed by Rich Felker on #alpine-devel irc channel changed _GNU_SOURCE to _BSD_SOURCE in patch
-rw-r--r--main/musl/APKBUILD4
-rw-r--r--main/musl/qsort_r.patch213
2 files changed, 216 insertions, 1 deletions
diff --git a/main/musl/APKBUILD b/main/musl/APKBUILD
index 20af23bed1..67b2eca109 100644
--- a/main/musl/APKBUILD
+++ b/main/musl/APKBUILD
@@ -2,7 +2,7 @@
# Maintainer: Timo Teräs <timo.teras@iki.fi>
pkgname=musl
pkgver=1.2.2
-pkgrel=6
+pkgrel=7
pkgdesc="the musl c library (libc) implementation"
url="https://musl.libc.org/"
arch="all"
@@ -26,6 +26,7 @@ source="musl-$commit.tar.gz::https://git.musl-libc.org/cgit/musl/snapshot/$commi
handle-aux-at_base.patch
syscall-cp-epoll.patch
eh-frame.patch
+ qsort_r.patch
ldconfig
__stack_chk_fail_local.c
@@ -178,6 +179,7 @@ f036317426d54efb4df41c08664c8513d3991408b20f4c74220c8b0324d2e96a97094851ea225e36
a76f79b801497ad994746cf82bb6eaf86f9e1ae646e6819fbae8532a7f4eee53a96ac1d4e789ec8f66aea2a68027b0597f7a579b3369e01258da8accfce41370 handle-aux-at_base.patch
d256ba7857c98d39b86aa73674eda5d45ab8134dde3fac2bc48ebb6ba9a824c20c43f2cdc6af54d2a45c162d1e4ec6517c36400992bba10496bcc51b374cbcd0 syscall-cp-epoll.patch
72177ca2cfa74033778064dbd241a333cae842000513ede57a467b68fb5bced91a15674c29acb140ef4e6b596c03f40caece867833581fb2bd7716047d150f8e eh-frame.patch
+307ad7619cff93a86d4de432db56c37d77303203cc0dddf1b0daa60d5c39453a73c387d8965ac3def37e2a92618d2a1cfd3d825866c9cf19cf2f1c46604cf947 qsort_r.patch
8d3a2d5315fc56fee7da9abb8b89bb38c6046c33d154c10d168fb35bfde6b0cf9f13042a3bceee34daf091bc409d699223735dcf19f382eeee1f6be34154f26f ldconfig
062bb49fa54839010acd4af113e20f7263dde1c8a2ca359b5fb2661ef9ed9d84a0f7c3bc10c25dcfa10bb3c5a4874588dff636ac43d5dbb3d748d75400756d0b __stack_chk_fail_local.c
0d80f37b34a35e3d14b012257c50862dfeb9d2c81139ea2dfa101d981d093b009b9fa450ba27a708ac59377a48626971dfc58e20a3799084a65777a0c32cbc7d getconf.c
diff --git a/main/musl/qsort_r.patch b/main/musl/qsort_r.patch
new file mode 100644
index 0000000000..4ea6366c31
--- /dev/null
+++ b/main/musl/qsort_r.patch
@@ -0,0 +1,213 @@
+Date: Tue, 9 Mar 2021 18:02:13 -0300
+From: Érico Nogueira <ericonr@...root.org>
+To: musl@...ts.openwall.com
+Cc: Érico Nogueira <ericonr@...root.org>
+Subject: [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(_BSD_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 _BSD_SOURCE
+ #include <stdint.h>
+ #include <stdlib.h>
+ #include <string.h>
+@@ -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 _BSD_SOURCE
++#include <stdlib.h>
++
++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