diff options
| author | Alexander Monakov <amonakov@ispras.ru> | 2018-09-03 19:51:24 +0300 |
|---|---|---|
| committer | Alexander Monakov <amonakov@gcc.gnu.org> | 2018-09-03 19:51:24 +0300 |
| commit | a6405b11a6456fe63e16945f32e1ddc2035ecdf0 (patch) | |
| tree | 5757fd55f33239602823d6e5a3826392f65fb9c5 | |
| parent | 71acd8b9d9d8c9437bfffa51f1b56f93cfbc20e9 (diff) | |
| download | gcc-a6405b11a6456fe63e16945f32e1ddc2035ecdf0.zip gcc-a6405b11a6456fe63e16945f32e1ddc2035ecdf0.tar.gz gcc-a6405b11a6456fe63e16945f32e1ddc2035ecdf0.tar.bz2 | |
introduce gcc_stablesort
* sort.cc (struct sort_ctx): New field 'nlim'. Use it...
(mergesort): ... here as maximum count for using netsort.
(gcc_qsort): Set nlim to 3 if stable sort is requested.
(gcc_stablesort): New.
* system.h (gcc_stablesort): Declare.
From-SVN: r264066
| -rw-r--r-- | gcc/ChangeLog | 8 | ||||
| -rw-r--r-- | gcc/sort.cc | 15 | ||||
| -rw-r--r-- | gcc/system.h | 2 |
3 files changed, 23 insertions, 2 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index bfa9ce6..99c5ca7 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,13 @@ 2018-09-03 Alexander Monakov <amonakov@ispras.ru> + * sort.cc (struct sort_ctx): New field 'nlim'. Use it... + (mergesort): ... here as maximum count for using netsort. + (gcc_qsort): Set nlim to 3 if stable sort is requested. + (gcc_stablesort): New. + * system.h (gcc_stablesort): Declare. + +2018-09-03 Alexander Monakov <amonakov@ispras.ru> + * sort.cc (gcc_qsort) [CHECKING_P]: Call qsort_chk. * system.h (qsort): Always redirect to gcc_qsort. Update comment. * vec.c (qsort_chk): Do not call gcc_qsort. Update comment. diff --git a/gcc/sort.cc b/gcc/sort.cc index 9f8ee12..b3be1ea 100644 --- a/gcc/sort.cc +++ b/gcc/sort.cc @@ -55,6 +55,7 @@ struct sort_ctx char *out; // output buffer size_t n; // number of elements size_t size; // element size + size_t nlim; // limit for network sort }; /* Helper for netsort. Permute, possibly in-place, 2 or 3 elements, @@ -178,7 +179,7 @@ do { \ static void mergesort (char *in, sort_ctx *c, size_t n, char *out, char *tmp) { - if (likely (n <= 5)) + if (likely (n <= c->nlim)) { c->out = out; c->n = n; @@ -221,8 +222,12 @@ gcc_qsort (void *vbase, size_t n, size_t size, cmp_fn *cmp) { if (n < 2) return; + size_t nlim = 5; + bool stable = (ssize_t) size < 0; + if (stable) + nlim = 3, size = ~size; char *base = (char *)vbase; - sort_ctx c = {cmp, base, n, size}; + sort_ctx c = {cmp, base, n, size, nlim}; long long scratch[32]; size_t bufsz = (n / 2) * size; void *buf = bufsz <= sizeof scratch ? scratch : xmalloc (bufsz); @@ -233,3 +238,9 @@ gcc_qsort (void *vbase, size_t n, size_t size, cmp_fn *cmp) qsort_chk (vbase, n, size, cmp); #endif } + +void +gcc_stablesort (void *vbase, size_t n, size_t size, cmp_fn *cmp) +{ + gcc_qsort (vbase, n, ~size, cmp); +} diff --git a/gcc/system.h b/gcc/system.h index 203c6a4..100feb5 100644 --- a/gcc/system.h +++ b/gcc/system.h @@ -1202,6 +1202,8 @@ helper_const_non_const_cast (const char *p) corresponding to vec::qsort (cmp): they use C qsort internally anyway. */ void qsort_chk (void *, size_t, size_t, int (*)(const void *, const void *)); void gcc_qsort (void *, size_t, size_t, int (*)(const void *, const void *)); +void gcc_stablesort (void *, size_t, size_t, + int (*)(const void *, const void *)); #define PP_5th(a1, a2, a3, a4, a5, ...) a5 #undef qsort #define qsort(...) PP_5th (__VA_ARGS__, gcc_qsort, 3, 2, qsort, 0) (__VA_ARGS__) |