mySQL 5.0.11 sources for tomato
[tomato.git] / release / src / router / mysql / mysys / mf_qsort.c
blob27b2579cb6abb1050575077d0e6706780b354ec9
1 /* Copyright (c) 2000-2002, 2007 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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"
24 #ifndef SCO
25 #include <m_string.h>
26 #endif
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
35 #define SWAP(A, B, size,swap_ptrs) \
36 do { \
37 if (swap_ptrs) \
38 { \
39 reg1 char **a = (char**) (A), **b = (char**) (B); \
40 char *tmp = *a; *a++ = *b; *b++ = tmp; \
41 } \
42 else \
43 { \
44 reg1 char *a = (A), *b = (B); \
45 reg3 char *end= a+size; \
46 do \
47 { \
48 char tmp = *a; *a++ = *b; *b++ = tmp; \
49 } while (a < end); \
50 } \
51 } while (0)
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); \
64 /* The following node is used to store ranges to avoid recursive calls */
66 typedef struct st_stack
68 char *low,*high;
69 } stack_node;
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
79 #else
80 #define SORT_RETURN return 0
81 #endif
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,
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
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;
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));
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)
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);
134 POP(low, high);
135 continue;
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);
148 low_ptr = low;
149 high_ptr = high;
151 else
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)
163 low_ptr += size;
164 while (CMP(pivot, high_ptr) < 0)
165 high_ptr -= size;
167 if (low_ptr < high_ptr)
169 SWAP(low_ptr, high_ptr, size, ptr_cmp);
170 low_ptr += size;
171 high_ptr -= size;
173 else
175 if (low_ptr == high_ptr)
177 low_ptr += size;
178 high_ptr -= size;
180 break;
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 */
198 else
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 */
206 low = low_ptr;
208 else
210 PUSH(low_ptr, high); /* Push larger right part */
211 high = high_ptr;
213 } while (stack_ptr > stack);
214 my_afree(pivot);
215 SORT_RETURN;