drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
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
28namespace drizzled {
29namespace 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) \
39do { \
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
69typedef 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
92void my_qsort2(void *base_ptr, size_t count, size_t size,
93 qsort2_cmp cmp, void *cmp_argument)
94#else
95void 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 */
TODO: Rename this file - func.h is stupid.
int(* qsort_cmp)(const void *, const void *)
Definition qsort_cmp.h:26