[PATCH v2] stdlib: Reinstate stable mergesort implementation on qsort

[Florian Weimer]

* Adhemerval Zanella:

> diff --git a/manual/search.texi b/manual/search.texi
> index a550858478..5691bf2f2b 100644
> --- a/manual/search.texi

> @@ -199,8 +199,9 @@ Functions}):
>  The @code{qsort} function derives its name from the fact that it was
>  originally implemented using the ``quick sort'' algorithm.
>  
> +The implementation of @code{qsort} in this library might not be an
> +in-place sort and might thereby use an extra amount of memory to store
> +the array.
>  @end deftypefun

I'd appreciate if a native speaker could have look at this.

> +typedef uint32_t __attribute__ ((__may_alias__)) u32_alias_t;
> +typedef uint64_t __attribute__ ((__may_alias__)) u64_alias_t;

What's the code generation impact of may_alias here?

> +    case SWAP_VOID_ARG:
> +      while (n1 > 0 && n2 > 0)
> +	{
> +	  if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
> +	    {
> +	      *(void **) tmp = *(void **) b1;
> +	      b1 += sizeof (void *);
> +	      --n1;
> +	    }
> +	  else
> +	    {
> +	      *(void **) tmp = *(void **) b2;
> +	      b2 += sizeof (void *);
> +	      --n2;
> +	    }
> +	  tmp += sizeof (void *);
> +	}
> +    default:
> +      while (n1 > 0 && n2 > 0)

Missing break before “default:”.

>  void
>  __qsort_r (void *const pbase, size_t total_elems, size_t size,
>  	   __compar_d_fn_t cmp, void *arg)
>  {
>    if (total_elems <= 1)
>      return;
>  
> +  char tmp[QSORT_STACK_SIZE];
> +  size_t total_size = total_elems * size;
> +  char *buf;

You need to ensure alignment now that you aren't using alloca anymore, I
think.

Rest looks okay.

Thanks,
Florian