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