On Tue, Aug 28, 2018 at 11:14 AM Alexander Monakov <amona...@ispras.ru> wrote:
>
> This adds a stable sort to sort.cc: mergesort implementation is stable, so
> we just need network sort limited to sizes 2-3 to get the complete sort
> stable.
>
> As I don't want to duplicate code for this, I've chosen to have gcc_qsort
> accept bit-inverted 'size' parameter to request stable sorting.
OK.
> * gcc/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.
> * gcc/system.h (gcc_stablesort): Declare.
>
> diff --git a/gcc/sort.cc b/gcc/sort.cc
> index 9f8ee12e13b..b3be1eac72b 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 203c6a4f0cf..100feb567c9 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__)
> --
> 2.13.3
>
