1
/* Copyright (C) 2000 MySQL AB
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.
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.
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 */
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".
23
#include "mysys_priv.h"
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)))
32
#define CMP(A,B) ((*cmp)((A),(B)))
35
#define SWAP(A, B, size,swap_ptrs) \
39
register char **a = (char**) (A), **b = (char**) (B); \
40
char *tmp = *a; *a++ = *b; *b++ = tmp; \
44
register char *a = (A), *b = (B); \
45
register char *end= a+size; \
48
char tmp = *a; *a++ = *b; *b++ = tmp; \
53
/* Put the median in the middle argument */
54
#define MEDIAN(low, mid, high) \
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); \
64
/* The following node is used to store ranges to avoid recursive calls */
66
typedef struct st_stack
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;}
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
80
#define SORT_RETURN return 0
83
/****************************************************************************
84
** 'standard' quicksort with the following extensions:
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
*****************************************************************************/
93
#ifdef QSORT_EXTRA_CMP_ARGUMENT
94
qsort_t my_qsort2(void *base_ptr, size_t count, size_t size, qsort2_cmp cmp,
97
qsort_t my_qsort(void *base_ptr, size_t count, size_t size, qsort_cmp cmp)
100
char *low, *high, *pivot;
101
stack_node stack[STACK_SIZE], *stack_ptr;
103
/* Handle the simple case first */
104
/* This will also make the rest of the code simpler */
108
low = (char*) base_ptr;
109
high = low+ size * (count - 1);
110
stack_ptr = stack + 1;
112
/* The first element in the stack will be accessed for the last POP */
113
stack[0].low=stack[0].high=0;
115
pivot = (char *) my_alloca((int) size);
116
ptr_cmp= size == sizeof(char*) && !((low - (char*) 0)& (sizeof(char*)-1));
118
/* The following loop sorts elements between high and low */
121
char *low_ptr, *high_ptr, *mid;
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)
127
for (low_ptr = low + size; low_ptr <= high; low_ptr += size)
130
for (ptr = low_ptr; ptr > low && CMP(ptr - size, ptr) > 0;
132
SWAP(ptr, ptr - size, size, ptr_cmp);
138
/* Try to find a good middle element */
139
mid= low + size * (count >> 1);
140
if (count > 40) /* Must be bigger than 24 */
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);
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;
158
memcpy(pivot, mid, size);
162
while (CMP(low_ptr, pivot) < 0)
164
while (CMP(pivot, high_ptr) < 0)
167
if (low_ptr < high_ptr)
169
SWAP(low_ptr, high_ptr, size, ptr_cmp);
175
if (low_ptr == high_ptr)
183
while (low_ptr <= high_ptr);
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.
192
if ((int) (high_ptr - low) <= 0)
194
if ((int) (high - low_ptr) <= 0)
196
POP(low, high); /* Nothing more to sort */
199
low = low_ptr; /* Ignore small left part. */
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))
205
PUSH(low, high_ptr); /* Push larger left part */
210
PUSH(low_ptr, high); /* Push larger right part */
213
} while (stack_ptr > stack);