/* An alternative to qsort, with an identical interface.

   This file is part of the GNU C Library.

   Copyright (C) 1992-2018 Free Software Foundation, Inc.

   Written by Mike Haertel, September 1988.

   The GNU C Library is free software; you can redistribute it and/or

   modify it under the terms of the GNU Lesser General Public

   License as published by the Free Software Foundation; either

   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public

   License along with the GNU C Library; if not, see

   <http://www.gnu.org/licenses/>.  */

#include <alloca.h>

#include <stdint.h>

#include <stdlib.h>

#include <string.h>

#include <unistd.h>

#include <memcopy.h>

#include <errno.h>

#include <atomic.h>

struct msort_param

{

  size_t s;

  size_t var;

  __compar_d_fn_t cmp;

  void *arg;

  char *t;

};

static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);

static void

msort_with_tmp (const struct msort_param *p, void *b, size_t n)

{

  char *b1, *b2;

  size_t n1, n2;

  if (n <= 1)

    return;

  n1 = n / 2;

  n2 = n - n1;

  b1 = b;

  b2 = (char *) b + (n1 * p->s);

  msort_with_tmp (p, b1, n1);

  msort_with_tmp (p, b2, n2);

  char *tmp = p->t;

  const size_t s = p->s;

  __compar_d_fn_t cmp = p->cmp;

  void *arg = p->arg;

  switch (p->var)

    {

    case 0:

      while (n1 > 0 && n2 > 0)

	{

	  if ((*cmp) (b1, b2, arg) <= 0)

	    {

	      *(uint32_t *) tmp = *(uint32_t *) b1;

	      b1 += sizeof (uint32_t);

	      --n1;

	    }

	  else

	    {

	      *(uint32_t *) tmp = *(uint32_t *) b2;

	      b2 += sizeof (uint32_t);

	      --n2;

	    }

	  tmp += sizeof (uint32_t);

	}

      break;

    case 1:

      while (n1 > 0 && n2 > 0)

	{

	  if ((*cmp) (b1, b2, arg) <= 0)

	    {

	      *(uint64_t *) tmp = *(uint64_t *) b1;

	      b1 += sizeof (uint64_t);

	      --n1;

	    }

	  else

	    {

	      *(uint64_t *) tmp = *(uint64_t *) b2;

	      b2 += sizeof (uint64_t);

	      --n2;

	    }

	  tmp += sizeof (uint64_t);

	}

      break;

    case 2:

      while (n1 > 0 && n2 > 0)

	{

	  unsigned long *tmpl = (unsigned long *) tmp;

	  unsigned long *bl;

	  tmp += s;

	  if ((*cmp) (b1, b2, arg) <= 0)

	    {

	      bl = (unsigned long *) b1;

	      b1 += s;

	      --n1;

	    }

	  else

	    {

	      bl = (unsigned long *) b2;

	      b2 += s;

	      --n2;

	    }

	  while (tmpl < (unsigned long *) tmp)

	    *tmpl++ = *bl++;

	}

      break;

    case 3:

      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 *);

	}

      break;

    default:

      while (n1 > 0 && n2 > 0)

	{

	  if ((*cmp) (b1, b2, arg) <= 0)

	    {

	      tmp = (char *) __mempcpy (tmp, b1, s);

	      b1 += s;

	      --n1;

	    }

	  else

	    {

	      tmp = (char *) __mempcpy (tmp, b2, s);

	      b2 += s;

	      --n2;

	    }

	}

      break;

    }

  if (n1 > 0)

    memcpy (tmp, b1, n1 * s);

  memcpy (b, p->t, (n - n2) * s);

}

void

__qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)

{

  size_t size = n * s;

  char *tmp = NULL;

  struct msort_param p;

  /* For large object sizes use indirect sorting.  */

  if (s > 32)

    size = 2 * n * sizeof (void *) + s;

  if (size < 1024)

    /* The temporary array is small, so put it on the stack.  */

    p.t = __alloca (size);

  else

    {

      /* We should avoid allocating too much memory since this might

	 have to be backed up by swap space.  */

      static long int phys_pages;

      static int pagesize;

      if (pagesize == 0)

	{

	  phys_pages = __sysconf (_SC_PHYS_PAGES);

	  if (phys_pages == -1)

	    /* Error while determining the memory size.  So let's

	       assume there is enough memory.  Otherwise the

	       implementer should provide a complete implementation of

	       the `sysconf' function.  */

	    phys_pages = (long int) (~0ul >> 1);

	  /* The following determines that we will never use more than

	     a quarter of the physical memory.  */

	  phys_pages /= 4;

	  /* Make sure phys_pages is written to memory.  */

	  atomic_write_barrier ();

	  pagesize = __sysconf (_SC_PAGESIZE);

	}

      /* Just a comment here.  We cannot compute

	   phys_pages * pagesize

	   and compare the needed amount of memory against this value.

	   The problem is that some systems might have more physical

	   memory then can be represented with a `size_t' value (when

	   measured in bytes.  */

      /* If the memory requirements are too high don't allocate memory.  */

      if (size / pagesize > (size_t) phys_pages)

	{

	  _quicksort (b, n, s, cmp, arg);

	  return;

	}

      /* It's somewhat large, so malloc it.  */

      int save = errno;

      tmp = malloc (size);

      __set_errno (save);

      if (tmp == NULL)

	{

	  /* Couldn't get space, so use the slower algorithm

	     that doesn't need a temporary array.  */

	  _quicksort (b, n, s, cmp, arg);

	  return;

	}

      p.t = tmp;

    }

  p.s = s;

  p.var = 4;

  p.cmp = cmp;

  p.arg = arg;

  if (s > 32)

    {

      /* Indirect sorting.  */

      char *ip = (char *) b;

      void **tp = (void **) (p.t + n * sizeof (void *));

      void **t = tp;

      void *tmp_storage = (void *) (tp + n);

      while ((void *) t < tmp_storage)

	{

	  *t++ = ip;

	  ip += s;

	}

      p.s = sizeof (void *);

      p.var = 3;

      msort_with_tmp (&p, p.t + n * sizeof (void *), n);

      /* tp[0] .. tp[n - 1] is now sorted, copy around entries of

	 the original array.  Knuth vol. 3 (2nd ed.) exercise 5.2-10.  */

      char *kp;

      size_t i;

      for (i = 0, ip = (char *) b; i < n; i++, ip += s)

	if ((kp = tp[i]) != ip)

	  {

	    size_t j = i;

	    char *jp = ip;

	    memcpy (tmp_storage, ip, s);

	    do

	      {

		size_t k = (kp - (char *) b) / s;

		tp[j] = jp;

		memcpy (jp, kp, s);

		j = k;

		jp = kp;

		kp = tp[k];

	      }

	    while (kp != ip);

	    tp[j] = jp;

	    memcpy (jp, tmp_storage, s);

	  }

    }

  else

    {

      if ((s & (sizeof (uint32_t) - 1)) == 0

	  && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0)

	{

	  if (s == sizeof (uint32_t))

	    p.var = 0;

	  else if (s == sizeof (uint64_t)

		   && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0)

	    p.var = 1;

	  else if ((s & (sizeof (unsigned long) - 1)) == 0

		   && ((char *) b - (char *) 0)

		      % __alignof__ (unsigned long) == 0)

	    p.var = 2;

	}

      msort_with_tmp (&p, b, n);

    }

  free (tmp);

}

libc_hidden_def (__qsort_r)

weak_alias (__qsort_r, qsort_r)

void

qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)

{

  return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);

}

libc_hidden_def (qsort)