Line data Source code
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
55 202403 : swapfunc(SortTuple *a, SortTuple *b, size_t n)
56 : {
57 : do
58 : {
59 202403 : SortTuple t = *a;
60 202403 : *a++ = *b;
61 202403 : *b++ = t;
62 202403 : } while (--n > 0);
63 99012 : }
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 *
75 103158 : med3_tuple(SortTuple *a, SortTuple *b, SortTuple *c, SortTupleComparator cmp_tuple, Tuplesortstate *state)
76 : {
77 206316 : return cmp_tuple(a, b, state) < 0 ?
78 82528 : (cmp_tuple(b, c, state) < 0 ? b :
79 32234 : (cmp_tuple(a, c, state) < 0 ? c : a))
80 191022 : : (cmp_tuple(b, c, state) > 0 ? b :
81 37570 : (cmp_tuple(a, c, state) < 0 ? a : c));
82 : }
83 :
84 : static void
85 133423 : 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 133423 : CHECK_FOR_INTERRUPTS();
101 133423 : if (n < 7)
102 : {
103 239249 : for (pm = a + 1; pm < a + n; pm++)
104 388698 : for (pl = pm; pl > a && cmp_tuple(pl - 1, pl, state) > 0; pl--)
105 208430 : swap(pl, pl - 1);
106 58981 : return;
107 : }
108 74436 : presorted = 1;
109 420088 : for (pm = a + 1; pm < a + n; pm++)
110 : {
111 419575 : CHECK_FOR_INTERRUPTS();
112 419575 : if (cmp_tuple(pm - 1, pm, state) > 0)
113 : {
114 73923 : presorted = 0;
115 73923 : break;
116 : }
117 : }
118 74436 : if (presorted)
119 513 : return;
120 73923 : pm = a + (n / 2);
121 73923 : if (n > 7)
122 : {
123 66372 : pl = a;
124 66372 : pn = a + (n - 1);
125 66372 : if (n > 40)
126 : {
127 12262 : size_t d = (n / 8);
128 :
129 12262 : pl = med3_tuple(pl, pl + d, pl + 2 * d, cmp_tuple, state);
130 12262 : pm = med3_tuple(pm - d, pm, pm + d, cmp_tuple, state);
131 12262 : pn = med3_tuple(pn - 2 * d, pn - d, pn, cmp_tuple, state);
132 : }
133 66372 : pm = med3_tuple(pl, pm, pn, cmp_tuple, state);
134 : }
135 73923 : swap(a, pm);
136 73923 : pa = pb = a + 1;
137 73923 : pc = pd = a + (n - 1);
138 : for (;;)
139 : {
140 3184542 : while (pb <= pc && (r = cmp_tuple(pb, a, state)) <= 0)
141 : {
142 1297020 : if (r == 0)
143 : {
144 17231 : swap(pa, pb);
145 17231 : pa++;
146 : }
147 1297020 : pb++;
148 1297020 : CHECK_FOR_INTERRUPTS();
149 : }
150 3104956 : while (pb <= pc && (r = cmp_tuple(pc, a, state)) >= 0)
151 : {
152 1217434 : if (r == 0)
153 : {
154 14159 : swap(pc, pd);
155 14159 : pd--;
156 : }
157 1217434 : pc--;
158 1217434 : CHECK_FOR_INTERRUPTS();
159 : }
160 943761 : if (pb > pc)
161 73923 : break;
162 869838 : swap(pb, pc);
163 869838 : pb++;
164 869838 : pc--;
165 869838 : }
166 73923 : pn = a + n;
167 73923 : d1 = Min(pa - a, pb - pa);
168 73923 : vecswap(a, pb - d1, d1);
169 73923 : d1 = Min(pd - pc, pn - pd - 1);
170 73923 : vecswap(pb, pn - d1, d1);
171 73923 : d1 = pb - pa;
172 73923 : d2 = pd - pc;
173 73923 : if (d1 <= d2)
174 : {
175 : /* Recurse on left partition, then iterate on right partition */
176 36623 : if (d1 > 1)
177 31378 : qsort_tuple(a, d1, cmp_tuple, state);
178 36623 : if (d2 > 1)
179 : {
180 : /* Iterate rather than recurse to save stack space */
181 : /* qsort_tuple(pn - d2, d2, cmp_tuple, state); */
182 36620 : a = pn - d2;
183 36620 : n = d2;
184 36620 : goto loop;
185 : }
186 : }
187 : else
188 : {
189 : /* Recurse on right partition, then iterate on left partition */
190 37300 : if (d2 > 1)
191 27495 : qsort_tuple(pn - d2, d2, cmp_tuple, state);
192 37300 : if (d1 > 1)
193 : {
194 : /* Iterate rather than recurse to save stack space */
195 : /* qsort_tuple(a, d1, cmp_tuple, state); */
196 37296 : n = d1;
197 37296 : 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 *
207 33784 : med3_ssup(SortTuple *a, SortTuple *b, SortTuple *c, SortSupport ssup)
208 : {
209 67568 : return cmp_ssup(a, b, ssup) < 0 ?
210 27472 : (cmp_ssup(b, c, ssup) < 0 ? b :
211 11317 : (cmp_ssup(a, c, ssup) < 0 ? c : a))
212 62343 : : (cmp_ssup(b, c, ssup) > 0 ? b :
213 12404 : (cmp_ssup(a, c, ssup) < 0 ? a : c));
214 : }
215 :
216 : static void
217 42391 : 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 42391 : CHECK_FOR_INTERRUPTS();
233 42391 : if (n < 7)
234 : {
235 78589 : for (pm = a + 1; pm < a + n; pm++)
236 121949 : for (pl = pm; pl > a && cmp_ssup(pl - 1, pl, ssup) > 0; pl--)
237 62787 : swap(pl, pl - 1);
238 19427 : return;
239 : }
240 22964 : presorted = 1;
241 194039 : for (pm = a + 1; pm < a + n; pm++)
242 : {
243 193374 : CHECK_FOR_INTERRUPTS();
244 193374 : if (cmp_ssup(pm - 1, pm, ssup) > 0)
245 : {
246 22299 : presorted = 0;
247 22299 : break;
248 : }
249 : }
250 22964 : if (presorted)
251 665 : return;
252 22299 : pm = a + (n / 2);
253 22299 : if (n > 7)
254 : {
255 20758 : pl = a;
256 20758 : pn = a + (n - 1);
257 20758 : if (n > 40)
258 : {
259 4342 : size_t d = (n / 8);
260 :
261 4342 : pl = med3_ssup(pl, pl + d, pl + 2 * d, ssup);
262 4342 : pm = med3_ssup(pm - d, pm, pm + d, ssup);
263 4342 : pn = med3_ssup(pn - 2 * d, pn - d, pn, ssup);
264 : }
265 20758 : pm = med3_ssup(pl, pm, pn, ssup);
266 : }
267 22299 : swap(a, pm);
268 22299 : pa = pb = a + 1;
269 22299 : pc = pd = a + (n - 1);
270 : for (;;)
271 : {
272 1095581 : while (pb <= pc && (r = cmp_ssup(pb, a, ssup)) <= 0)
273 : {
274 495103 : if (r == 0)
275 : {
276 50664 : swap(pa, pb);
277 50664 : pa++;
278 : }
279 495103 : pb++;
280 495103 : CHECK_FOR_INTERRUPTS();
281 : }
282 992543 : while (pb <= pc && (r = cmp_ssup(pc, a, ssup)) >= 0)
283 : {
284 392065 : if (r == 0)
285 : {
286 30063 : swap(pc, pd);
287 30063 : pd--;
288 : }
289 392065 : pc--;
290 392065 : CHECK_FOR_INTERRUPTS();
291 : }
292 300239 : if (pb > pc)
293 22299 : break;
294 277940 : swap(pb, pc);
295 277940 : pb++;
296 277940 : pc--;
297 277940 : }
298 22299 : pn = a + n;
299 22299 : d1 = Min(pa - a, pb - pa);
300 22299 : vecswap(a, pb - d1, d1);
301 22299 : d1 = Min(pd - pc, pn - pd - 1);
302 22299 : vecswap(pb, pn - d1, d1);
303 22299 : d1 = pb - pa;
304 22299 : d2 = pd - pc;
305 22299 : if (d1 <= d2)
306 : {
307 : /* Recurse on left partition, then iterate on right partition */
308 11722 : if (d1 > 1)
309 10051 : qsort_ssup(a, d1, ssup);
310 11722 : if (d2 > 1)
311 : {
312 : /* Iterate rather than recurse to save stack space */
313 : /* qsort_ssup(pn - d2, d2, ssup); */
314 11715 : a = pn - d2;
315 11715 : n = d2;
316 11715 : goto loop;
317 : }
318 : }
319 : else
320 : {
321 : /* Recurse on right partition, then iterate on left partition */
322 10577 : if (d2 > 1)
323 8888 : qsort_ssup(pn - d2, d2, ssup);
324 10577 : if (d1 > 1)
325 : {
326 : /* Iterate rather than recurse to save stack space */
327 : /* qsort_ssup(a, d1, ssup); */
328 10575 : n = d1;
329 10575 : goto loop;
330 : }
331 : }
332 : }
|
