mf_qsort.c 6.08 KB
Newer Older
bk@work.mysql.com's avatar
bk@work.mysql.com committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
   
   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.
   
   This 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
   Library General Public License for more details.
   
   You should have received a copy of the GNU Library General Public
   License along with this library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
   MA 02111-1307, USA */

18 19 20 21 22
/*
  qsort implementation optimized for comparison of pointers
  Inspired by the qsort implementations by Douglas C. Schmidt,
  and Bentley & McIlroy's "Engineering a Sort Function".
*/
bk@work.mysql.com's avatar
bk@work.mysql.com committed
23 24 25


#include "mysys_priv.h"
26
#include "m_string.h"
bk@work.mysql.com's avatar
bk@work.mysql.com committed
27

28
/* We need to use qsort with 2 different compare functions */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
29 30 31 32 33 34
#ifdef QSORT_EXTRA_CMP_ARGUMENT
#define CMP(A,B) ((*cmp)(cmp_argument,(A),(B)))
#else
#define CMP(A,B) ((*cmp)((A),(B)))
#endif

35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
#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);			\
}
bk@work.mysql.com's avatar
bk@work.mysql.com committed
63

64
/* The following node is used to store ranges to avoid recursive calls */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
65

66
typedef struct st_stack
bk@work.mysql.com's avatar
bk@work.mysql.com committed
67
{
68
  char *low,*high;
monty@work.mysql.com's avatar
monty@work.mysql.com committed
69
} stack_node;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
70

71 72
#define PUSH(LOW,HIGH)  {stack_ptr->low = LOW; stack_ptr++->high = HIGH;}
#define POP(LOW,HIGH)   {LOW = (--stack_ptr)->low; HIGH = stack_ptr->high;}
bk@work.mysql.com's avatar
bk@work.mysql.com committed
73

74 75 76
/* The following stack size is enough for ulong ~0 elements */
#define STACK_SIZE	(8 * sizeof(unsigned long int))
#define THRESHOLD_FOR_INSERT_SORT 10
bk@work.mysql.com's avatar
bk@work.mysql.com committed
77 78 79 80 81 82
#if defined(QSORT_TYPE_IS_VOID)
#define SORT_RETURN return
#else
#define SORT_RETURN return 0
#endif

83 84 85 86 87 88 89 90 91 92
/****************************************************************************
** '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
*****************************************************************************/

bk@work.mysql.com's avatar
bk@work.mysql.com committed
93
#ifdef QSORT_EXTRA_CMP_ARGUMENT
94
qsort_t qsort2(void *base_ptr, size_t count, size_t size, qsort2_cmp cmp,
bk@work.mysql.com's avatar
bk@work.mysql.com committed
95 96
	       void *cmp_argument)
#else
97
qsort_t qsort(void *base_ptr, size_t count, size_t size, qsort_cmp cmp)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
98 99
#endif
{
100
  char *low, *high, *pivot;
monty@work.mysql.com's avatar
monty@work.mysql.com committed
101
  stack_node stack[STACK_SIZE], *stack_ptr;
102 103 104 105 106 107 108 109 110
  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;
111
#ifdef HAVE_purify
112
  /* The first element in the stack will be accessed for the last POP */
monty@hundin.mysql.fi's avatar
monty@hundin.mysql.fi committed
113
  stack[0].low=stack[0].high=0;
114
#endif
115 116 117 118 119 120 121
  pivot = (char *) my_alloca((int) size);
  ptr_cmp= size == sizeof(char*) && !((low - (char*) 0)& (sizeof(char*)-1));

  /* The following loop sorts elements between high and low */
  do
  {
    char *low_ptr, *high_ptr, *mid;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
122

123 124 125
    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)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
126
    {
127
      for (low_ptr = low + size; low_ptr <= high; low_ptr += size)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
128
      {
129 130 131 132
	char *ptr;
	for (ptr = low_ptr; ptr > low && CMP(ptr - size, ptr) > 0;
	     ptr -= size)
	  SWAP(ptr, ptr - size, size, ptr_cmp);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
133
      }
134 135 136
      POP(low, high);
      continue;
    }
bk@work.mysql.com's avatar
bk@work.mysql.com committed
137

138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
    /* 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);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
159

160 161 162 163 164 165 166 167
    do
    {
      while (CMP(low_ptr, pivot) < 0)
	low_ptr += size;
      while (CMP(pivot, high_ptr) < 0)
	high_ptr -= size;

      if (low_ptr < high_ptr)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
168
      {
169 170 171
	SWAP(low_ptr, high_ptr, size, ptr_cmp);
	low_ptr += size;
	high_ptr -= size;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
172
      }
173
      else 
bk@work.mysql.com's avatar
bk@work.mysql.com committed
174
      {
175 176 177 178 179 180
	if (low_ptr == high_ptr)
	{
	  low_ptr += size;
	  high_ptr -= size;
	}
	break;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
181 182
      }
    }
183
    while (low_ptr <= high_ptr);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
184

185 186 187 188 189 190
    /*
      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.
    */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
191

192
    if ((int) (high_ptr - low) <= 0)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
193
    {
194
      if ((int) (high - low_ptr) <= 0)
bk@work.mysql.com's avatar
bk@work.mysql.com committed
195
      {
196
	POP(low, high);			/* Nothing more to sort */
bk@work.mysql.com's avatar
bk@work.mysql.com committed
197
      }
198 199 200 201 202 203 204 205 206 207 208 209 210 211
      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;
bk@work.mysql.com's avatar
bk@work.mysql.com committed
212
    }
213 214
  } while (stack_ptr > stack);
  my_afree(pivot);
bk@work.mysql.com's avatar
bk@work.mysql.com committed
215 216
  SORT_RETURN;
}