release/src/router/mysql/mysys/mf_qsort.c

   1 /* Copyright (c) 2000-2002, 2007 MySQL AB
   2
   3    This program is free software; you can redistribute it and/or modify
   4    it under the terms of the GNU General Public License as published by
   5    the Free Software Foundation; version 2 of the License.
   6
   7    This program is distributed in the hope that it will be useful,
   8    but WITHOUT ANY WARRANTY; without even the implied warranty of
   9    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10    GNU General Public License for more details.
  11
  12    You should have received a copy of the GNU General Public License
  13    along with this program; if not, write to the Free Software
  14    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA */
  15
  16 /*
  17   qsort implementation optimized for comparison of pointers
  18   Inspired by the qsort implementations by Douglas C. Schmidt,
  19   and Bentley & McIlroy's "Engineering a Sort Function".
  20 */
  21
  22
  23 #include "mysys_priv.h"
  24 #ifndef SCO
  25 #include <m_string.h>
  26 #endif
  27
  28 /* We need to use qsort with 2 different compare functions */
  29 #ifdef QSORT_EXTRA_CMP_ARGUMENT
  30 #define CMP(A,B) ((*cmp)(cmp_argument,(A),(B)))
  31 #else
  32 #define CMP(A,B) ((*cmp)((A),(B)))
  33 #endif
  34
  35 #define SWAP(A, B, size,swap_ptrs)                      \
  36 do {                                                    \
  37    if (swap_ptrs)                                       \
  38    {                                                    \
  39      reg1 char **a = (char**) (A), **b = (char**) (B);  \
  40      char *tmp = *a; *a++ = *b; *b++ = tmp;             \
  41    }                                                    \
  42    else                                                 \
  43    {                                                    \
  44      reg1 char *a = (A), *b = (B);                      \
  45      reg3 char *end= a+size;                            \
  46      do                                                 \
  47      {                                                  \
  48        char tmp = *a; *a++ = *b; *b++ = tmp;            \
  49      } while (a < end);                                 \
  50    }                                                    \
  51 } while (0)
  52
  53 /* Put the median in the middle argument */
  54 #define MEDIAN(low, mid, high)                          \
  55 {                                                       \
  56     if (CMP(high,low) < 0)                              \
  57       SWAP(high, low, size, ptr_cmp);                   \
  58     if (CMP(mid, low) < 0)                              \
  59       SWAP(mid, low, size, ptr_cmp);                    \
  60     else if (CMP(high, mid) < 0)                        \
  61       SWAP(mid, high, size, ptr_cmp);                   \
  62 }
  63
  64 /* The following node is used to store ranges to avoid recursive calls */
  65
  66 typedef struct st_stack
  67 {
  68   char *low,*high;
  69 } stack_node;
  70
  71 #define PUSH(LOW,HIGH)  {stack_ptr->low = LOW; stack_ptr++->high = HIGH;}
  72 #define POP(LOW,HIGH)   {LOW = (--stack_ptr)->low; HIGH = stack_ptr->high;}
  73
  74 /* The following stack size is enough for ulong ~0 elements */
  75 #define STACK_SIZE      (8 * sizeof(unsigned long int))
  76 #define THRESHOLD_FOR_INSERT_SORT 10
  77 #if defined(QSORT_TYPE_IS_VOID)
  78 #define SORT_RETURN return
  79 #else
  80 #define SORT_RETURN return 0
  81 #endif
  82
  83 /****************************************************************************
  84 ** 'standard' quicksort with the following extensions:
  85 **
  86 ** Can be compiled with the qsort2_cmp compare function
  87 ** Store ranges on stack to avoid recursion
  88 ** Use insert sort on small ranges
  89 ** Optimize for sorting of pointers (used often by MySQL)
  90 ** Use median comparison to find partition element
  91 *****************************************************************************/
  92
  93 #ifdef QSORT_EXTRA_CMP_ARGUMENT
  94 qsort_t my_qsort2(void *base_ptr, size_t count, size_t size, qsort2_cmp cmp,
  95                void *cmp_argument)
  96 #else
  97 qsort_t my_qsort(void *base_ptr, size_t count, size_t size, qsort_cmp cmp)
  98 #endif
  99 {
 100   char *low, *high, *pivot;
 101   stack_node stack[STACK_SIZE], *stack_ptr;
 102   my_bool ptr_cmp;
 103   /* Handle the simple case first */
 104   /* This will also make the rest of the code simpler */
 105   if (count <= 1)
 106     SORT_RETURN;
 107
 108   low  = (char*) base_ptr;
 109   high = low+ size * (count - 1);
 110   stack_ptr = stack + 1;
 111 #ifdef HAVE_purify
 112   /* The first element in the stack will be accessed for the last POP */
 113   stack[0].low=stack[0].high=0;
 114 #endif
 115   pivot = (char *) my_alloca((int) size);
 116   ptr_cmp= size == sizeof(char*) && !((low - (char*) 0)& (sizeof(char*)-1));
 117
 118   /* The following loop sorts elements between high and low */
 119   do
 120   {
 121     char *low_ptr, *high_ptr, *mid;
 122
 123     count=((size_t) (high - low) / size)+1;
 124     /* If count is small, then an insert sort is faster than qsort */
 125     if (count < THRESHOLD_FOR_INSERT_SORT)
 126     {
 127       for (low_ptr = low + size; low_ptr <= high; low_ptr += size)
 128       {
 129         char *ptr;
 130         for (ptr = low_ptr; ptr > low && CMP(ptr - size, ptr) > 0;
 131              ptr -= size)
 132           SWAP(ptr, ptr - size, size, ptr_cmp);
 133       }
 134       POP(low, high);
 135       continue;
 136     }
 137
 138     /* Try to find a good middle element */
 139     mid= low + size * (count >> 1);
 140     if (count > 40)                             /* Must be bigger than 24 */
 141     {
 142       size_t step = size* (count / 8);
 143       MEDIAN(low, low + step, low+step*2);
 144       MEDIAN(mid - step, mid, mid+step);
 145       MEDIAN(high - 2 * step, high-step, high);
 146       /* Put best median in 'mid' */
 147       MEDIAN(low+step, mid, high-step);
 148       low_ptr  = low;
 149       high_ptr = high;
 150     }
 151     else
 152     {
 153       MEDIAN(low, mid, high);
 154       /* The low and high argument are already in sorted against 'pivot' */
 155       low_ptr  = low + size;
 156       high_ptr = high - size;
 157     }
 158     memcpy(pivot, mid, size);
 159
 160     do
 161     {
 162       while (CMP(low_ptr, pivot) < 0)
 163         low_ptr += size;
 164       while (CMP(pivot, high_ptr) < 0)
 165         high_ptr -= size;
 166
 167       if (low_ptr < high_ptr)
 168       {
 169         SWAP(low_ptr, high_ptr, size, ptr_cmp);
 170         low_ptr += size;
 171         high_ptr -= size;
 172       }
 173       else
 174       {
 175         if (low_ptr == high_ptr)
 176         {
 177           low_ptr += size;
 178           high_ptr -= size;
 179         }
 180         break;
 181       }
 182     }
 183     while (low_ptr <= high_ptr);
 184
 185     /*
 186       Prepare for next iteration.
 187        Skip partitions of size 1 as these doesn't have to be sorted
 188        Push the larger partition and sort the smaller one first.
 189        This ensures that the stack is keept small.
 190     */
 191
 192     if ((int) (high_ptr - low) <= 0)
 193     {
 194       if ((int) (high - low_ptr) <= 0)
 195       {
 196         POP(low, high);                 /* Nothing more to sort */
 197       }
 198       else
 199         low = low_ptr;                  /* Ignore small left part. */
 200     }
 201     else if ((int) (high - low_ptr) <= 0)
 202       high = high_ptr;                  /* Ignore small right part. */
 203     else if ((high_ptr - low) > (high - low_ptr))
 204     {
 205       PUSH(low, high_ptr);              /* Push larger left part */
 206       low = low_ptr;
 207     }
 208     else
 209     {
 210       PUSH(low_ptr, high);              /* Push larger right part */
 211       high = high_ptr;
 212     }
 213   } while (stack_ptr > stack);
 214   my_afree(pivot);
 215   SORT_RETURN;
 216 }