/* Sort a vector of pointers to data.

   Copyright (C) 2007 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program 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 General Public License for more details.

   You should have received a copy of the GNU General Public License along
   with this program; if not, write to the Free Software Foundation,
   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */

/* Written by Paul Eggert.  */

#include <config.h>

#include "mpsort.h"

#include <string.h>

/* The type of qsort-style comparison functions.  */

typedef int (*comparison_function) (void const *, void const *);

static void mpsort_with_tmp (void const **restrict, size_t,
			     void const **restrict, comparison_function);

/* Sort a vector BASE containing N pointers, placing the sorted array
   into TMP.  Compare pointers with CMP.  N must be at least 2.  */

static void
mpsort_into_tmp (void const **restrict base, size_t n,
		 void const **restrict tmp,
		 comparison_function cmp)
{
  size_t n1 = n / 2;
  size_t n2 = n - n1;
  size_t a = 0;
  size_t alim = n1;
  size_t b = n1;
  size_t blim = n;
  void const *ba;
  void const *bb;

  mpsort_with_tmp (base + n1, n2, tmp, cmp);
  mpsort_with_tmp (base, n1, tmp, cmp);

  ba = base[a];
  bb = base[b];

  for (;;)
    if (cmp (ba, bb) <= 0)
      {
	*tmp++ = ba;
	a++;
	if (a == alim)
	  {
	    a = b;
	    alim = blim;
	    break;
	  }
	ba = base[a];
      }
    else
      {
	*tmp++ = bb;
	b++;
	if (b == blim)
	  break;
	bb = base[b];
      }

  memcpy (tmp, base + a, (alim - a) * sizeof *base);
}

/* Sort a vector BASE containing N pointers, in place.  Use TMP
   (containing N / 2 pointers) for temporary storage.  Compare
   pointers with CMP.  */

static void
mpsort_with_tmp (void const **restrict base, size_t n,
		 void const **restrict tmp,
		 comparison_function cmp)
{
  if (n <= 2)
    {
      if (n == 2)
	{
	  void const *p0 = base[0];
	  void const *p1 = base[1];
	  if (! (cmp (p0, p1) <= 0))
	    {
	      base[0] = p1;
	      base[1] = p0;
	    }
	}
    }
  else
    {
      size_t n1 = n / 2;
      size_t n2 = n - n1;
      size_t i;
      size_t t = 0;
      size_t tlim = n1;
      size_t b = n1;
      size_t blim = n;
      void const *bb;
      void const *tt;

      mpsort_with_tmp (base + n1, n2, tmp, cmp);

      if (n1 < 2)
	tmp[0] = base[0];
      else
	mpsort_into_tmp (base, n1, tmp, cmp);

      tt = tmp[t];
      bb = base[b];

      for (i = 0; ; )
	if (cmp (tt, bb) <= 0)
	  {
	    base[i++] = tt;
	    t++;
	    if (t == tlim)
	      break;
	    tt = tmp[t];
	  }
	else
	  {
	    base[i++] = bb;
	    b++;
	    if (b == blim)
	      {
		memcpy (base + i, tmp + t, (tlim - t) * sizeof *base);
		break;
	      }
	    bb = base[b];
	  }
    }
}

/* Sort a vector BASE containing N pointers, in place.  BASE must
   contain enough storage to hold N + N / 2 vectors; the trailing
   vectors are used for temporaries.  Compare pointers with CMP.  */

void
mpsort (void const **base, size_t n, comparison_function cmp)
{
  mpsort_with_tmp (base, n, base + n, cmp);
}