← Back to branch summary

~skinny.moey/drizzle/branch-rev

« back to all changes in this revision

Viewing changes to mysys/mf_qsort.c

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/mf_qsort.c
 
1
/* Copyright (C) 2000 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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
     register char **a = (char**) (A), **b = (char**) (B);  \
 
40
     char *tmp = *a; *a++ = *b; *b++ = tmp;             \
 
41
   }                                                    \
 
42
   else                                                 \
 
43
   {                                                    \
 
44
     register char *a = (A), *b = (B);                  \
 
45
     register 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
}