Drizzled Public API Documentation

mf_qsort.cc
00001 /* Copyright (C) 2000 MySQL AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; version 2 of the License.
00006 
00007    This program is distributed in the hope that it will be useful,
00008    but WITHOUT ANY WARRANTY; without even the implied warranty of
00009    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00010    GNU General Public License for more details.
00011 
00012    You should have received a copy of the GNU General Public License
00013    along with this program; if not, write to the Free Software
00014    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */
00015 
00016 /*
00017   qsort implementation optimized for comparison of pointers
00018   Inspired by the qsort implementations by Douglas C. Schmidt,
00019   and Bentley & McIlroy's "Engineering a Sort Function".
00020 */
00021 
00022 
00023 #include <config.h>
00024 
00025 #include <drizzled/internal/my_sys.h>
00026 #include <drizzled/internal/m_string.h>
00027 
00028 namespace drizzled
00029 {
00030 namespace internal
00031 {
00032 
00033 /* We need to use qsort with 2 different compare functions */
00034 #ifdef QSORT_EXTRA_CMP_ARGUMENT
00035 #define CMP(A,B) ((*cmp)(cmp_argument,(A),(B)))
00036 #else
00037 #define CMP(A,B) ((*cmp)((A),(B)))
00038 #endif
00039 
00040 #define SWAP(A, B, size,swap_ptrs)      \
00041 do {              \
00042    if (swap_ptrs)         \
00043    {              \
00044      char **a = (char**) (A), **b = (char**) (B);  \
00045      char *tmp = *a; *a++ = *b; *b++ = tmp;   \
00046    }              \
00047    else             \
00048    {              \
00049      char *a = (A), *b = (B);     \
00050      char *end= a+size;       \
00051      do             \
00052      {              \
00053        char tmp = *a; *a++ = *b; *b++ = tmp;    \
00054      } while (a < end);         \
00055    }              \
00056 } while (0)
00057 
00058 /* Put the median in the middle argument */
00059 #define MEDIAN(low, mid, high)        \
00060 {             \
00061     if (CMP(high,low) < 0)        \
00062       SWAP(high, low, size, ptr_cmp);     \
00063     if (CMP(mid, low) < 0)        \
00064       SWAP(mid, low, size, ptr_cmp);      \
00065     else if (CMP(high, mid) < 0)      \
00066       SWAP(mid, high, size, ptr_cmp);     \
00067 }
00068 
00069 /* The following node is used to store ranges to avoid recursive calls */
00070 
00071 typedef struct st_stack
00072 {
00073   char *low,*high;
00074 } stack_node;
00075 
00076 #define PUSH(LOW,HIGH)  {stack_ptr->low = LOW; stack_ptr++->high = HIGH;}
00077 #define POP(LOW,HIGH)   {LOW = (--stack_ptr)->low; HIGH = stack_ptr->high;}
00078 
00079 /* The following stack size is enough for UINT32_MAX elements */
00080 #define STACK_SIZE  (8 * sizeof(unsigned long int))
00081 #define THRESHOLD_FOR_INSERT_SORT 10
00082 
00083 /****************************************************************************
00084 ** 'standard' quicksort with the following extensions:
00085 **
00086 ** Can be compiled with the qsort2_cmp compare function
00087 ** Store ranges on stack to avoid recursion
00088 ** Use insert sort on small ranges
00089 ** Optimize for sorting of pointers (used often by MySQL)
00090 ** Use median comparison to find partition element
00091 *****************************************************************************/
00092 
00093 #ifdef QSORT_EXTRA_CMP_ARGUMENT
00094 void my_qsort2(void *base_ptr, size_t count, size_t size,
00095                        qsort2_cmp cmp, void *cmp_argument)
00096 #else
00097 void my_qsort(void *base_ptr, size_t count, size_t size,
00098                       qsort_cmp cmp)
00099 #endif
00100 {
00101   char *low, *high, *pivot;
00102   stack_node stack[STACK_SIZE], *stack_ptr;
00103   bool ptr_cmp;
00104   /* Handle the simple case first */
00105   /* This will also make the rest of the code simpler */
00106   if (count <= 1)
00107     return;
00108 
00109   low  = (char*) base_ptr;
00110   high = low+ size * (count - 1);
00111   stack_ptr = stack + 1;
00112 #ifdef HAVE_VALGRIND
00113   /* The first element in the stack will be accessed for the last POP */
00114   stack[0].low=stack[0].high=0;
00115 #endif
00116   pivot = (char *) malloc(size);
00117   ptr_cmp= size == sizeof(char*) && !((low - (char*) 0)& (sizeof(char*)-1));
00118 
00119   /* The following loop sorts elements between high and low */
00120   do
00121   {
00122     char *low_ptr, *high_ptr, *mid;
00123 
00124     count=((size_t) (high - low) / size)+1;
00125     /* If count is small, then an insert sort is faster than qsort */
00126     if (count < THRESHOLD_FOR_INSERT_SORT)
00127     {
00128       for (low_ptr = low + size; low_ptr <= high; low_ptr += size)
00129       {
00130         char *ptr;
00131         for (ptr = low_ptr; ptr > low && CMP(ptr - size, ptr) > 0;
00132              ptr -= size)
00133           SWAP(ptr, ptr - size, size, ptr_cmp);
00134       }
00135       POP(low, high);
00136       continue;
00137     }
00138 
00139     /* Try to find a good middle element */
00140     mid= low + size * (count >> 1);
00141     if (count > 40)       /* Must be bigger than 24 */
00142     {
00143       size_t step = size* (count / 8);
00144       MEDIAN(low, low + step, low+step*2);
00145       MEDIAN(mid - step, mid, mid+step);
00146       MEDIAN(high - 2 * step, high-step, high);
00147       /* Put best median in 'mid' */
00148       MEDIAN(low+step, mid, high-step);
00149       low_ptr  = low;
00150       high_ptr = high;
00151     }
00152     else
00153     {
00154       MEDIAN(low, mid, high);
00155       /* The low and high argument are already in sorted against 'pivot' */
00156       low_ptr  = low + size;
00157       high_ptr = high - size;
00158     }
00159     memcpy(pivot, mid, size);
00160 
00161     do
00162     {
00163       while (CMP(low_ptr, pivot) < 0)
00164         low_ptr += size;
00165       while (CMP(pivot, high_ptr) < 0)
00166         high_ptr -= size;
00167 
00168       if (low_ptr < high_ptr)
00169       {
00170         SWAP(low_ptr, high_ptr, size, ptr_cmp);
00171         low_ptr += size;
00172         high_ptr -= size;
00173       }
00174       else
00175       {
00176         if (low_ptr == high_ptr)
00177         {
00178           low_ptr += size;
00179           high_ptr -= size;
00180         }
00181         break;
00182       }
00183     }
00184     while (low_ptr <= high_ptr);
00185 
00186     /*
00187       Prepare for next iteration.
00188        Skip partitions of size 1 as these doesn't have to be sorted
00189        Push the larger partition and sort the smaller one first.
00190        This ensures that the stack is keept small.
00191     */
00192 
00193     if ((int) (high_ptr - low) <= 0)
00194     {
00195       if ((int) (high - low_ptr) <= 0)
00196       {
00197         POP(low, high);     /* Nothing more to sort */
00198       }
00199       else
00200         low = low_ptr;      /* Ignore small left part. */
00201     }
00202     else if ((int) (high - low_ptr) <= 0)
00203       high = high_ptr;      /* Ignore small right part. */
00204     else if ((high_ptr - low) > (high - low_ptr))
00205     {
00206       PUSH(low, high_ptr);    /* Push larger left part */
00207       low = low_ptr;
00208     }
00209     else
00210     {
00211       PUSH(low_ptr, high);    /* Push larger right part */
00212       high = high_ptr;
00213     }
00214   } while (stack_ptr > stack);
00215   free(pivot);
00216   return;
00217 }
00218 
00219 } /* namespace internal */
00220 } /* namespace drizzled */