Drizzled Public API Documentation

mf_qsort.cc
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., 51 Franklin St, 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 <config.h>
24 
25 #include <drizzled/internal/my_sys.h>
26 #include <drizzled/internal/m_string.h>
27 
28 namespace drizzled {
29 namespace internal {
30 
31 /* We need to use qsort with 2 different compare functions */
32 #ifdef QSORT_EXTRA_CMP_ARGUMENT
33 #define CMP(A,B) ((*cmp)(cmp_argument,(A),(B)))
34 #else
35 #define CMP(A,B) ((*cmp)((A),(B)))
36 #endif
37 
38 #define SWAP(A, B, size,swap_ptrs) \
39 do { \
40  if (swap_ptrs) \
41  { \
42  char **a = (char**) (A), **b = (char**) (B); \
43  char *tmp = *a; *a++ = *b; *b++ = tmp; \
44  } \
45  else \
46  { \
47  char *a = (A), *b = (B); \
48  char *end= a+size; \
49  do \
50  { \
51  char tmp = *a; *a++ = *b; *b++ = tmp; \
52  } while (a < end); \
53  } \
54 } while (0)
55 
56 /* Put the median in the middle argument */
57 #define MEDIAN(low, mid, high) \
58 { \
59  if (CMP(high,low) < 0) \
60  SWAP(high, low, size, ptr_cmp); \
61  if (CMP(mid, low) < 0) \
62  SWAP(mid, low, size, ptr_cmp); \
63  else if (CMP(high, mid) < 0) \
64  SWAP(mid, high, size, ptr_cmp); \
65 }
66 
67 /* The following node is used to store ranges to avoid recursive calls */
68 
69 typedef struct st_stack
70 {
71  char *low,*high;
72 } stack_node;
73 
74 #define PUSH(LOW,HIGH) {stack_ptr->low = LOW; stack_ptr++->high = HIGH;}
75 #define POP(LOW,HIGH) {LOW = (--stack_ptr)->low; HIGH = stack_ptr->high;}
76 
77 /* The following stack size is enough for UINT32_MAX elements */
78 #define STACK_SIZE (8 * sizeof(unsigned long int))
79 #define THRESHOLD_FOR_INSERT_SORT 10
80 
81 /****************************************************************************
82 ** 'standard' quicksort with the following extensions:
83 **
84 ** Can be compiled with the qsort2_cmp compare function
85 ** Store ranges on stack to avoid recursion
86 ** Use insert sort on small ranges
87 ** Optimize for sorting of pointers (used often by MySQL)
88 ** Use median comparison to find partition element
89 *****************************************************************************/
90 
91 #ifdef QSORT_EXTRA_CMP_ARGUMENT
92 void my_qsort2(void *base_ptr, size_t count, size_t size,
93  qsort2_cmp cmp, void *cmp_argument)
94 #else
95 void my_qsort(void *base_ptr, size_t count, size_t size,
96  qsort_cmp cmp)
97 #endif
98 {
99  char *low, *high, *pivot;
100  stack_node stack[STACK_SIZE], *stack_ptr;
101  bool ptr_cmp;
102  /* Handle the simple case first */
103  /* This will also make the rest of the code simpler */
104  if (count <= 1)
105  return;
106 
107  low = (char*) base_ptr;
108  high = low+ size * (count - 1);
109  stack_ptr = stack + 1;
110 #ifdef HAVE_VALGRIND
111  /* The first element in the stack will be accessed for the last POP */
112  stack[0].low=stack[0].high=0;
113 #endif
114  pivot = (char *) malloc(size);
115  ptr_cmp= size == sizeof(char*) && !((low - (char*) 0)& (sizeof(char*)-1));
116 
117  /* The following loop sorts elements between high and low */
118  do
119  {
120  char *low_ptr, *high_ptr, *mid;
121 
122  count=((size_t) (high - low) / size)+1;
123  /* If count is small, then an insert sort is faster than qsort */
124  if (count < THRESHOLD_FOR_INSERT_SORT)
125  {
126  for (low_ptr = low + size; low_ptr <= high; low_ptr += size)
127  {
128  char *ptr;
129  for (ptr = low_ptr; ptr > low && CMP(ptr - size, ptr) > 0;
130  ptr -= size)
131  SWAP(ptr, ptr - size, size, ptr_cmp);
132  }
133  POP(low, high);
134  continue;
135  }
136 
137  /* Try to find a good middle element */
138  mid= low + size * (count >> 1);
139  if (count > 40) /* Must be bigger than 24 */
140  {
141  size_t step = size* (count / 8);
142  MEDIAN(low, low + step, low+step*2);
143  MEDIAN(mid - step, mid, mid+step);
144  MEDIAN(high - 2 * step, high-step, high);
145  /* Put best median in 'mid' */
146  MEDIAN(low+step, mid, high-step);
147  low_ptr = low;
148  high_ptr = high;
149  }
150  else
151  {
152  MEDIAN(low, mid, high);
153  /* The low and high argument are already in sorted against 'pivot' */
154  low_ptr = low + size;
155  high_ptr = high - size;
156  }
157  memcpy(pivot, mid, size);
158 
159  do
160  {
161  while (CMP(low_ptr, pivot) < 0)
162  low_ptr += size;
163  while (CMP(pivot, high_ptr) < 0)
164  high_ptr -= size;
165 
166  if (low_ptr < high_ptr)
167  {
168  SWAP(low_ptr, high_ptr, size, ptr_cmp);
169  low_ptr += size;
170  high_ptr -= size;
171  }
172  else
173  {
174  if (low_ptr == high_ptr)
175  {
176  low_ptr += size;
177  high_ptr -= size;
178  }
179  break;
180  }
181  }
182  while (low_ptr <= high_ptr);
183 
184  /*
185  Prepare for next iteration.
186  Skip partitions of size 1 as these doesn't have to be sorted
187  Push the larger partition and sort the smaller one first.
188  This ensures that the stack is keept small.
189  */
190 
191  if ((int) (high_ptr - low) <= 0)
192  {
193  if ((int) (high - low_ptr) <= 0)
194  {
195  POP(low, high); /* Nothing more to sort */
196  }
197  else
198  low = low_ptr; /* Ignore small left part. */
199  }
200  else if ((int) (high - low_ptr) <= 0)
201  high = high_ptr; /* Ignore small right part. */
202  else if ((high_ptr - low) > (high - low_ptr))
203  {
204  PUSH(low, high_ptr); /* Push larger left part */
205  low = low_ptr;
206  }
207  else
208  {
209  PUSH(low_ptr, high); /* Push larger right part */
210  high = high_ptr;
211  }
212  } while (stack_ptr > stack);
213  free(pivot);
214  return;
215 }
216 
217 } /* namespace internal */
218 } /* namespace drizzled */