1 /*
2 * autogenerated by src/backend/utils/sort/gen_qsort_tuple.pl, do not edit!
3 *
4 * This file is included by tuplesort.c, rather than compiled separately.
5 */
6
7 /* $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $ */
8
9 /*-
10 * Copyright (c) 1992, 1993
11 * The Regents of the University of California. All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
21 * 3. Neither the name of the University nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 */
37
38 /*
39 * Qsort routine based on J. L. Bentley and M. D. McIlroy,
40 * "Engineering a sort function",
41 * Software--Practice and Experience 23 (1993) 1249-1265.
42 *
43 * We have modified their original by adding a check for already-sorted input,
44 * which seems to be a win per discussions on pgsql-hackers around 2006-03-21.
45 *
46 * Also, we recurse on the smaller partition and iterate on the larger one,
47 * which ensures we cannot recurse more than log(N) levels (since the
48 * partition recursed to is surely no more than half of the input). Bentley
49 * and McIlroy explicitly rejected doing this on the grounds that it's "not
50 * worth the effort", but we have seen crashes in the field due to stack
51 * overrun, so that judgment seems wrong.
52 */
53
54 static void
swapfunc(SortTuple * a,SortTuple * b,size_t n)55 swapfunc(SortTuple *a, SortTuple *b, size_t n)
56 {
57 do
58 {
59 SortTuple t = *a;
60 *a++ = *b;
61 *b++ = t;
62 } while (--n > 0);
63 }
64
65 #define swap(a, b) \
66 do { \
67 SortTuple t = *(a); \
68 *(a) = *(b); \
69 *(b) = t; \
70 } while (0)
71
72 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n)
73
74 static SortTuple *
med3_tuple(SortTuple * a,SortTuple * b,SortTuple * c,SortTupleComparator cmp_tuple,Tuplesortstate * state)75 med3_tuple(SortTuple *a, SortTuple *b, SortTuple *c, SortTupleComparator cmp_tuple, Tuplesortstate *state)
76 {
77 return cmp_tuple(a, b, state) < 0 ?
78 (cmp_tuple(b, c, state) < 0 ? b :
79 (cmp_tuple(a, c, state) < 0 ? c : a))
80 : (cmp_tuple(b, c, state) > 0 ? b :
81 (cmp_tuple(a, c, state) < 0 ? a : c));
82 }
83
84 static void
qsort_tuple(SortTuple * a,size_t n,SortTupleComparator cmp_tuple,Tuplesortstate * state)85 qsort_tuple(SortTuple *a, size_t n, SortTupleComparator cmp_tuple, Tuplesortstate *state)
86 {
87 SortTuple *pa,
88 *pb,
89 *pc,
90 *pd,
91 *pl,
92 *pm,
93 *pn;
94 size_t d1,
95 d2;
96 int r,
97 presorted;
98
99 loop:
100 CHECK_FOR_INTERRUPTS();
101 if (n < 7)
102 {
103 for (pm = a + 1; pm < a + n; pm++)
104 for (pl = pm; pl > a && cmp_tuple(pl - 1, pl, state) > 0; pl--)
105 swap(pl, pl - 1);
106 return;
107 }
108 presorted = 1;
109 for (pm = a + 1; pm < a + n; pm++)
110 {
111 CHECK_FOR_INTERRUPTS();
112 if (cmp_tuple(pm - 1, pm, state) > 0)
113 {
114 presorted = 0;
115 break;
116 }
117 }
118 if (presorted)
119 return;
120 pm = a + (n / 2);
121 if (n > 7)
122 {
123 pl = a;
124 pn = a + (n - 1);
125 if (n > 40)
126 {
127 size_t d = (n / 8);
128
129 pl = med3_tuple(pl, pl + d, pl + 2 * d, cmp_tuple, state);
130 pm = med3_tuple(pm - d, pm, pm + d, cmp_tuple, state);
131 pn = med3_tuple(pn - 2 * d, pn - d, pn, cmp_tuple, state);
132 }
133 pm = med3_tuple(pl, pm, pn, cmp_tuple, state);
134 }
135 swap(a, pm);
136 pa = pb = a + 1;
137 pc = pd = a + (n - 1);
138 for (;;)
139 {
140 while (pb <= pc && (r = cmp_tuple(pb, a, state)) <= 0)
141 {
142 if (r == 0)
143 {
144 swap(pa, pb);
145 pa++;
146 }
147 pb++;
148 CHECK_FOR_INTERRUPTS();
149 }
150 while (pb <= pc && (r = cmp_tuple(pc, a, state)) >= 0)
151 {
152 if (r == 0)
153 {
154 swap(pc, pd);
155 pd--;
156 }
157 pc--;
158 CHECK_FOR_INTERRUPTS();
159 }
160 if (pb > pc)
161 break;
162 swap(pb, pc);
163 pb++;
164 pc--;
165 }
166 pn = a + n;
167 d1 = Min(pa - a, pb - pa);
168 vecswap(a, pb - d1, d1);
169 d1 = Min(pd - pc, pn - pd - 1);
170 vecswap(pb, pn - d1, d1);
171 d1 = pb - pa;
172 d2 = pd - pc;
173 if (d1 <= d2)
174 {
175 /* Recurse on left partition, then iterate on right partition */
176 if (d1 > 1)
177 qsort_tuple(a, d1, cmp_tuple, state);
178 if (d2 > 1)
179 {
180 /* Iterate rather than recurse to save stack space */
181 /* qsort_tuple(pn - d2, d2, cmp_tuple, state); */
182 a = pn - d2;
183 n = d2;
184 goto loop;
185 }
186 }
187 else
188 {
189 /* Recurse on right partition, then iterate on left partition */
190 if (d2 > 1)
191 qsort_tuple(pn - d2, d2, cmp_tuple, state);
192 if (d1 > 1)
193 {
194 /* Iterate rather than recurse to save stack space */
195 /* qsort_tuple(a, d1, cmp_tuple, state); */
196 n = d1;
197 goto loop;
198 }
199 }
200 }
201
202 #define cmp_ssup(a, b, ssup) \
203 ApplySortComparator((a)->datum1, (a)->isnull1, \
204 (b)->datum1, (b)->isnull1, ssup)
205
206 static SortTuple *
med3_ssup(SortTuple * a,SortTuple * b,SortTuple * c,SortSupport ssup)207 med3_ssup(SortTuple *a, SortTuple *b, SortTuple *c, SortSupport ssup)
208 {
209 return cmp_ssup(a, b, ssup) < 0 ?
210 (cmp_ssup(b, c, ssup) < 0 ? b :
211 (cmp_ssup(a, c, ssup) < 0 ? c : a))
212 : (cmp_ssup(b, c, ssup) > 0 ? b :
213 (cmp_ssup(a, c, ssup) < 0 ? a : c));
214 }
215
216 static void
qsort_ssup(SortTuple * a,size_t n,SortSupport ssup)217 qsort_ssup(SortTuple *a, size_t n, SortSupport ssup)
218 {
219 SortTuple *pa,
220 *pb,
221 *pc,
222 *pd,
223 *pl,
224 *pm,
225 *pn;
226 size_t d1,
227 d2;
228 int r,
229 presorted;
230
231 loop:
232 CHECK_FOR_INTERRUPTS();
233 if (n < 7)
234 {
235 for (pm = a + 1; pm < a + n; pm++)
236 for (pl = pm; pl > a && cmp_ssup(pl - 1, pl, ssup) > 0; pl--)
237 swap(pl, pl - 1);
238 return;
239 }
240 presorted = 1;
241 for (pm = a + 1; pm < a + n; pm++)
242 {
243 CHECK_FOR_INTERRUPTS();
244 if (cmp_ssup(pm - 1, pm, ssup) > 0)
245 {
246 presorted = 0;
247 break;
248 }
249 }
250 if (presorted)
251 return;
252 pm = a + (n / 2);
253 if (n > 7)
254 {
255 pl = a;
256 pn = a + (n - 1);
257 if (n > 40)
258 {
259 size_t d = (n / 8);
260
261 pl = med3_ssup(pl, pl + d, pl + 2 * d, ssup);
262 pm = med3_ssup(pm - d, pm, pm + d, ssup);
263 pn = med3_ssup(pn - 2 * d, pn - d, pn, ssup);
264 }
265 pm = med3_ssup(pl, pm, pn, ssup);
266 }
267 swap(a, pm);
268 pa = pb = a + 1;
269 pc = pd = a + (n - 1);
270 for (;;)
271 {
272 while (pb <= pc && (r = cmp_ssup(pb, a, ssup)) <= 0)
273 {
274 if (r == 0)
275 {
276 swap(pa, pb);
277 pa++;
278 }
279 pb++;
280 CHECK_FOR_INTERRUPTS();
281 }
282 while (pb <= pc && (r = cmp_ssup(pc, a, ssup)) >= 0)
283 {
284 if (r == 0)
285 {
286 swap(pc, pd);
287 pd--;
288 }
289 pc--;
290 CHECK_FOR_INTERRUPTS();
291 }
292 if (pb > pc)
293 break;
294 swap(pb, pc);
295 pb++;
296 pc--;
297 }
298 pn = a + n;
299 d1 = Min(pa - a, pb - pa);
300 vecswap(a, pb - d1, d1);
301 d1 = Min(pd - pc, pn - pd - 1);
302 vecswap(pb, pn - d1, d1);
303 d1 = pb - pa;
304 d2 = pd - pc;
305 if (d1 <= d2)
306 {
307 /* Recurse on left partition, then iterate on right partition */
308 if (d1 > 1)
309 qsort_ssup(a, d1, ssup);
310 if (d2 > 1)
311 {
312 /* Iterate rather than recurse to save stack space */
313 /* qsort_ssup(pn - d2, d2, ssup); */
314 a = pn - d2;
315 n = d2;
316 goto loop;
317 }
318 }
319 else
320 {
321 /* Recurse on right partition, then iterate on left partition */
322 if (d2 > 1)
323 qsort_ssup(pn - d2, d2, ssup);
324 if (d1 > 1)
325 {
326 /* Iterate rather than recurse to save stack space */
327 /* qsort_ssup(a, d1, ssup); */
328 n = d1;
329 goto loop;
330 }
331 }
332 }
333