/* Copyright (c) 2000-2002, 2007 MySQL AB

   Use is subject to license terms

   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; version 2 of the License.

   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-1335  USA */

/*

  qsort implementation optimized for comparison of pointers

  Inspired by the qsort implementations by Douglas C. Schmidt,

  and Bentley & McIlroy's "Engineering a Sort Function".

*/

#include "mysys_priv.h"

#ifndef SCO

#include <m_string.h>

#endif

/* We need to use qsort with 2 different compare functions */

#ifdef QSORT_EXTRA_CMP_ARGUMENT

#define CMP(A,B) ((*cmp)(cmp_argument,(A),(B)))

#else

#define CMP(A,B) ((*cmp)((A),(B)))

#endif

#define SWAP(A, B, size,swap_ptrs)      \

do {             \

   if (swap_ptrs)         \

   {             \

     reg1 char **a = (char**) (A), **b = (char**) (B);  \

     char *tmp = *a; *a++ = *b; *b++ = tmp;   \

   }              \

   else             \

   {             \

     reg1 char *a = (A), *b = (B);     \

     reg3 char *end= a+size;       \

     do             \

     {             \

       char tmp = *a; *a++ = *b; *b++ = tmp;    \

     } while (a < end);          \

   }              \

} while (0)

/* Put the median in the middle argument */

#define MEDIAN(low, mid, high)        \

{             \

    if (CMP(high,low) < 0)       \

      SWAP(high, low, size, ptr_cmp);     \

    if (CMP(mid, low) < 0)       \

      SWAP(mid, low, size, ptr_cmp);      \

    else if (CMP(high, mid) < 0)     \

      SWAP(mid, high, size, ptr_cmp);     \

}

/* The following node is used to store ranges to avoid recursive calls */

typedef struct st_stack

{

  char *low,*high;

} stack_node;

#define PUSH(LOW,HIGH)  {stack_ptr->low = LOW; stack_ptr++->high = HIGH;}

#define POP(LOW,HIGH)   {LOW = (--stack_ptr)->low; HIGH = stack_ptr->high;}

/* The following stack size is enough for ulong ~0 elements */

#define STACK_SIZE  (8 * sizeof(unsigned long int))

#define THRESHOLD_FOR_INSERT_SORT 10

#if defined(QSORT_TYPE_IS_VOID)

#define SORT_RETURN return

#else

#define SORT_RETURN return 0

#endif

/****************************************************************************

** 'standard' quicksort with the following extensions:

**

** Can be compiled with the qsort2_cmp compare function

** Store ranges on stack to avoid recursion

** Use insert sort on small ranges

** Optimize for sorting of pointers (used often by MySQL)

** Use median comparison to find partition element

*****************************************************************************/

#ifdef QSORT_EXTRA_CMP_ARGUMENT

qsort_t my_qsort2(void *base_ptr, size_t count, size_t size, qsort2_cmp cmp,

         void *cmp_argument)

#else

qsort_t my_qsort(void *base_ptr, size_t count, size_t size, qsort_cmp cmp)

#endif

{

  char *low, *high, *pivot;

  stack_node stack[STACK_SIZE], *stack_ptr;

  my_bool ptr_cmp;

  /* Handle the simple case first */

  /* This will also make the rest of the code simpler */

  if (count <= 1)

    SORT_RETURN;

  low  = (char*) base_ptr;

  high = low+ size * (count - 1);

  stack_ptr = stack + 1;

#ifdef HAVE_valgrind

  /* The first element in the stack will be accessed for the last POP */

  stack[0].low=stack[0].high=0;

#endif

  pivot = (char *) my_alloca((int) size);

  ptr_cmp= size == sizeof(char*) && (intptr_t)low % sizeof(char*) == 0;

  /* The following loop sorts elements between high and low */

  do

  {

    char *low_ptr, *high_ptr, *mid;

    count=((size_t) (high - low) / size)+1;

    /* If count is small, then an insert sort is faster than qsort */

    if (count < THRESHOLD_FOR_INSERT_SORT)

    {

      for (low_ptr = low + size; low_ptr <= high; low_ptr += size)

      {

  char *ptr;

  for (ptr = low_ptr; ptr > low && CMP(ptr - size, ptr) > 0;

       ptr -= size)

    SWAP(ptr, ptr - size, size, ptr_cmp);

      }

      POP(low, high);

      continue;

    }

    /* Try to find a good middle element */

    mid= low + size * (count >> 1);

    if (count > 40)       /* Must be bigger than 24 */

    {

      size_t step = size* (count / 8);

      MEDIAN(low, low + step, low+step*2);

      MEDIAN(mid - step, mid, mid+step);

      MEDIAN(high - 2 * step, high-step, high);

      /* Put best median in 'mid' */

      MEDIAN(low+step, mid, high-step);

      low_ptr  = low;

      high_ptr = high;

    }

    else

    {

      MEDIAN(low, mid, high);

      /* The low and high argument are already in sorted against 'pivot' */

      low_ptr  = low + size;

      high_ptr = high - size;

    }

    memcpy(pivot, mid, size);

    do

    {

      while (CMP(low_ptr, pivot) < 0)

  low_ptr += size;

      while (CMP(pivot, high_ptr) < 0)

  high_ptr -= size;

      if (low_ptr < high_ptr)

      {

  SWAP(low_ptr, high_ptr, size, ptr_cmp);

  low_ptr += size;

  high_ptr -= size;

      }

      else 

      {

  if (low_ptr == high_ptr)

  {

    low_ptr += size;

    high_ptr -= size;

  }

  break;

      }

    }

    while (low_ptr <= high_ptr);

    /*

      Prepare for next iteration.

       Skip partitions of size 1 as these doesn't have to be sorted

       Push the larger partition and sort the smaller one first.

       This ensures that the stack is keept small.

    */

    if ((int) (high_ptr - low) <= 0)

    {

      if ((int) (high - low_ptr) <= 0)

      {

  POP(low, high);      /* Nothing more to sort */

      }

      else

  low = low_ptr;     /* Ignore small left part. */

    }

    else if ((int) (high - low_ptr) <= 0)

      high = high_ptr;     /* Ignore small right part. */

    else if ((high_ptr - low) > (high - low_ptr))

    {

      PUSH(low, high_ptr);    /* Push larger left part */

      low = low_ptr;

    }

    else

    {

      PUSH(low_ptr, high);    /* Push larger right part */

      high = high_ptr;

    }

  } while (stack_ptr > stack);

  my_afree(pivot);

  SORT_RETURN;

}