Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * sort_template.h
4 : : *
5 : : * A template for a sort algorithm that supports varying degrees of
6 : : * specialization.
7 : : *
8 : : * Copyright (c) 2021-2026, PostgreSQL Global Development Group
9 : : * Portions Copyright (c) 1992-1994, Regents of the University of California
10 : : *
11 : : * Usage notes:
12 : : *
13 : : * To generate functions specialized for a type, the following parameter
14 : : * macros should be #define'd before this file is included.
15 : : *
16 : : * - ST_SORT - the name of a sort function to be generated
17 : : * - ST_ELEMENT_TYPE - type of the referenced elements
18 : : * - ST_DECLARE - if defined the functions and types are declared
19 : : * - ST_DEFINE - if defined the functions and types are defined
20 : : * - ST_SCOPE - scope (e.g. extern, static inline) for functions
21 : : * - ST_CHECK_FOR_INTERRUPTS - if defined the sort is interruptible
22 : : *
23 : : * Instead of ST_ELEMENT_TYPE, ST_ELEMENT_TYPE_VOID can be defined. Then
24 : : * the generated functions will automatically gain an "element_size"
25 : : * parameter. This allows us to generate a traditional qsort function.
26 : : *
27 : : * One of the following macros must be defined, to show how to compare
28 : : * elements. The first two options are arbitrary expressions depending
29 : : * on whether an extra pass-through argument is desired, and the third
30 : : * option should be defined if the sort function should receive a
31 : : * function pointer at runtime.
32 : : *
33 : : * - ST_COMPARE(a, b) - a simple comparison expression
34 : : * - ST_COMPARE(a, b, arg) - variant that takes an extra argument
35 : : * - ST_COMPARE_RUNTIME_POINTER - sort function takes a function pointer
36 : : *
37 : : * NB: If the comparator function is inlined, some compilers may produce
38 : : * worse code with the optimized comparison routines in common/int.h than
39 : : * with code with the following form:
40 : : *
41 : : * if (a < b)
42 : : * return -1;
43 : : * if (a > b)
44 : : * return 1;
45 : : * return 0;
46 : : *
47 : : * To say that the comparator and therefore also sort function should
48 : : * receive an extra pass-through argument, specify the type of the
49 : : * argument.
50 : : *
51 : : * - ST_COMPARE_ARG_TYPE - type of extra argument
52 : : *
53 : : * The prototype of the generated sort function is:
54 : : *
55 : : * void ST_SORT(ST_ELEMENT_TYPE *data, size_t n,
56 : : * [size_t element_size,]
57 : : * [ST_SORT_compare_function compare,]
58 : : * [ST_COMPARE_ARG_TYPE *arg]);
59 : : *
60 : : * ST_SORT_compare_function is a function pointer of the following type:
61 : : *
62 : : * int (*)(const ST_ELEMENT_TYPE *a, const ST_ELEMENT_TYPE *b,
63 : : * [ST_COMPARE_ARG_TYPE *arg])
64 : : *
65 : : * HISTORY
66 : : *
67 : : * Modifications from vanilla NetBSD source:
68 : : * - Add do ... while() macro fix
69 : : * - Remove __inline, _DIAGASSERTs, __P
70 : : * - Remove ill-considered "swap_cnt" switch to insertion sort, in favor
71 : : * of a simple check for presorted input.
72 : : * - Take care to recurse on the smaller partition, to bound stack usage
73 : : * - Convert into a header that can generate specialized functions
74 : : *
75 : : * IDENTIFICATION
76 : : * src/include/lib/sort_template.h
77 : : *
78 : : *-------------------------------------------------------------------------
79 : : */
80 : :
81 : : /* $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $ */
82 : :
83 : : /*-
84 : : * Copyright (c) 1992, 1993
85 : : * The Regents of the University of California. All rights reserved.
86 : : *
87 : : * Redistribution and use in source and binary forms, with or without
88 : : * modification, are permitted provided that the following conditions
89 : : * are met:
90 : : * 1. Redistributions of source code must retain the above copyright
91 : : * notice, this list of conditions and the following disclaimer.
92 : : * 2. Redistributions in binary form must reproduce the above copyright
93 : : * notice, this list of conditions and the following disclaimer in the
94 : : * documentation and/or other materials provided with the distribution.
95 : : * 3. Neither the name of the University nor the names of its contributors
96 : : * may be used to endorse or promote products derived from this software
97 : : * without specific prior written permission.
98 : : *
99 : : * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
100 : : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
101 : : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
102 : : * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
103 : : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
104 : : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
105 : : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
106 : : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
107 : : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
108 : : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
109 : : * SUCH DAMAGE.
110 : : */
111 : :
112 : : /*
113 : : * Qsort routine based on J. L. Bentley and M. D. McIlroy,
114 : : * "Engineering a sort function",
115 : : * Software--Practice and Experience 23 (1993) 1249-1265.
116 : : *
117 : : * We have modified their original by adding a check for already-sorted
118 : : * input, which seems to be a win per discussions on pgsql-hackers around
119 : : * 2006-03-21.
120 : : *
121 : : * Also, we recurse on the smaller partition and iterate on the larger one,
122 : : * which ensures we cannot recurse more than log(N) levels (since the
123 : : * partition recursed to is surely no more than half of the input). Bentley
124 : : * and McIlroy explicitly rejected doing this on the grounds that it's "not
125 : : * worth the effort", but we have seen crashes in the field due to stack
126 : : * overrun, so that judgment seems wrong.
127 : : */
128 : :
129 : : #define ST_MAKE_PREFIX(a) CppConcat(a,_)
130 : : #define ST_MAKE_NAME(a,b) ST_MAKE_NAME_(ST_MAKE_PREFIX(a),b)
131 : : #define ST_MAKE_NAME_(a,b) CppConcat(a,b)
132 : :
133 : : /*
134 : : * If the element type is void, we'll also need an element_size argument
135 : : * because we don't know the size.
136 : : */
137 : : #ifdef ST_ELEMENT_TYPE_VOID
138 : : #define ST_ELEMENT_TYPE void
139 : : #define ST_SORT_PROTO_ELEMENT_SIZE , size_t element_size
140 : : #define ST_SORT_INVOKE_ELEMENT_SIZE , element_size
141 : : #else
142 : : #define ST_SORT_PROTO_ELEMENT_SIZE
143 : : #define ST_SORT_INVOKE_ELEMENT_SIZE
144 : : #endif
145 : :
146 : : /*
147 : : * If the user wants to be able to pass in compare functions at runtime,
148 : : * we'll need to make that an argument of the sort and med3 functions.
149 : : */
150 : : #ifdef ST_COMPARE_RUNTIME_POINTER
151 : : /*
152 : : * The type of the comparator function pointer that ST_SORT will take, unless
153 : : * you've already declared a type name manually and want to use that instead of
154 : : * having a new one defined.
155 : : */
156 : : #ifndef ST_COMPARATOR_TYPE_NAME
157 : : #define ST_COMPARATOR_TYPE_NAME ST_MAKE_NAME(ST_SORT, compare_function)
158 : : #endif
159 : : #define ST_COMPARE compare
160 : : #ifndef ST_COMPARE_ARG_TYPE
161 : : #define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
162 : : #define ST_SORT_INVOKE_COMPARE , compare
163 : : #else
164 : : #define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
165 : : #define ST_SORT_INVOKE_COMPARE , compare
166 : : #endif
167 : : #else
168 : : #define ST_SORT_PROTO_COMPARE
169 : : #define ST_SORT_INVOKE_COMPARE
170 : : #endif
171 : :
172 : : /*
173 : : * If the user wants to use a compare function or expression that takes an
174 : : * extra argument, we'll need to make that an argument of the sort, compare and
175 : : * med3 functions.
176 : : */
177 : : #ifdef ST_COMPARE_ARG_TYPE
178 : : #define ST_SORT_PROTO_ARG , ST_COMPARE_ARG_TYPE *arg
179 : : #define ST_SORT_INVOKE_ARG , arg
180 : : #else
181 : : #define ST_SORT_PROTO_ARG
182 : : #define ST_SORT_INVOKE_ARG
183 : : #endif
184 : :
185 : : #ifdef ST_DECLARE
186 : :
187 : : #ifdef ST_COMPARE_RUNTIME_POINTER
188 : : typedef int (*ST_COMPARATOR_TYPE_NAME) (const ST_ELEMENT_TYPE *,
189 : : const ST_ELEMENT_TYPE * ST_SORT_PROTO_ARG);
190 : : #endif
191 : :
192 : : /* Declare the sort function. Note optional arguments at end. */
193 : : ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE * first, size_t n
194 : : ST_SORT_PROTO_ELEMENT_SIZE
195 : : ST_SORT_PROTO_COMPARE
196 : : ST_SORT_PROTO_ARG);
197 : :
198 : : #endif
199 : :
200 : : #ifdef ST_DEFINE
201 : :
202 : : /* sort private helper functions */
203 : : #define ST_MED3 ST_MAKE_NAME(ST_SORT, med3)
204 : : #define ST_SWAP ST_MAKE_NAME(ST_SORT, swap)
205 : : #define ST_SWAPN ST_MAKE_NAME(ST_SORT, swapn)
206 : :
207 : : /* Users expecting to run very large sorts may need them to be interruptible. */
208 : : #ifdef ST_CHECK_FOR_INTERRUPTS
209 : : #define DO_CHECK_FOR_INTERRUPTS() CHECK_FOR_INTERRUPTS()
210 : : #else
211 : : #define DO_CHECK_FOR_INTERRUPTS()
212 : : #endif
213 : :
214 : : /*
215 : : * Create wrapper macros that know how to invoke compare, med3 and sort with
216 : : * the right arguments.
217 : : */
218 : : #ifdef ST_COMPARE_RUNTIME_POINTER
219 : : #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_) ST_SORT_INVOKE_ARG)
220 : : #elif defined(ST_COMPARE_ARG_TYPE)
221 : : #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_), arg)
222 : : #else
223 : : #define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_))
224 : : #endif
225 : : #define DO_MED3(a_, b_, c_) \
226 : : ST_MED3((a_), (b_), (c_) \
227 : : ST_SORT_INVOKE_COMPARE \
228 : : ST_SORT_INVOKE_ARG)
229 : : #define DO_SORT(a_, n_) \
230 : : ST_SORT((a_), (n_) \
231 : : ST_SORT_INVOKE_ELEMENT_SIZE \
232 : : ST_SORT_INVOKE_COMPARE \
233 : : ST_SORT_INVOKE_ARG)
234 : :
235 : : /*
236 : : * If we're working with void pointers, we'll use pointer arithmetic based on
237 : : * uint8, and use the runtime element_size to step through the array and swap
238 : : * elements. Otherwise we'll work with ST_ELEMENT_TYPE.
239 : : */
240 : : #ifndef ST_ELEMENT_TYPE_VOID
241 : : #define ST_POINTER_TYPE ST_ELEMENT_TYPE
242 : : #define ST_POINTER_STEP 1
243 : : #define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
244 : : #define DO_SWAP(a_, b_) ST_SWAP((a_), (b_))
245 : : #else
246 : : #define ST_POINTER_TYPE uint8
247 : : #define ST_POINTER_STEP element_size
248 : : #define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
249 : : #define DO_SWAP(a_, b_) DO_SWAPN((a_), (b_), element_size)
250 : : #endif
251 : :
252 : : /*
253 : : * Find the median of three values. Currently, performance seems to be best
254 : : * if the comparator is inlined here, but the med3 function is not inlined
255 : : * in the qsort function.
256 : : *
257 : : * Refer to the comment at the top of this file for known caveats to consider
258 : : * when writing inlined comparator functions.
259 : : */
260 : : static pg_noinline ST_ELEMENT_TYPE *
1768 tgl@sss.pgh.pa.us 261 :CBC 20723767 : ST_MED3(ST_ELEMENT_TYPE * a,
262 : : ST_ELEMENT_TYPE * b,
263 : : ST_ELEMENT_TYPE * c
264 : : ST_SORT_PROTO_COMPARE
265 : : ST_SORT_PROTO_ARG)
266 : : {
1838 tmunro@postgresql.or 267 : 20723767 : return DO_COMPARE(a, b) < 0 ?
268 [ + + + + ]: 11429602 : (DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
269 [ + + + + : 32153369 : : (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));
+ + ]
270 : : }
271 : :
272 : : static inline void
1768 tgl@sss.pgh.pa.us 273 : 1568326074 : ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b)
274 : : {
1838 tmunro@postgresql.or 275 : 1568326074 : ST_POINTER_TYPE tmp = *a;
276 : :
277 : 1568326074 : *a = *b;
278 : 1568326074 : *b = tmp;
279 : 1568326074 : }
280 : :
281 : : static inline void
1768 tgl@sss.pgh.pa.us 282 : 129766659 : ST_SWAPN(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b, size_t n)
283 : : {
1838 tmunro@postgresql.or 284 [ + + ]: 1654877461 : for (size_t i = 0; i < n; ++i)
285 : 1525110802 : ST_SWAP(&a[i], &b[i]);
286 : 129766659 : }
287 : :
288 : : /*
289 : : * Sort an array.
290 : : */
291 : : ST_SCOPE void
1768 tgl@sss.pgh.pa.us 292 : 18502331 : ST_SORT(ST_ELEMENT_TYPE * data, size_t n
293 : : ST_SORT_PROTO_ELEMENT_SIZE
294 : : ST_SORT_PROTO_COMPARE
295 : : ST_SORT_PROTO_ARG)
296 : : {
1838 tmunro@postgresql.or 297 : 18502331 : ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data,
298 : : *pa,
299 : : *pb,
300 : : *pc,
301 : : *pd,
302 : : *pl,
303 : : *pm,
304 : : *pn;
305 : : size_t d1,
306 : : d2;
307 : : int r,
308 : : presorted;
309 : :
310 : 15553069 : loop:
311 [ + + ]: 15725761 : DO_CHECK_FOR_INTERRUPTS();
312 [ + + ]: 34055400 : if (n < 7)
313 : : {
314 : : /*
315 : : * Not strictly necessary, but a caller may pass a NULL pointer input
316 : : * and zero length, and this silences warnings about applying offsets
317 : : * to NULL pointers.
318 : : */
36 john.naylor@postgres 319 [ + + ]:GNC 17967350 : if (n < 2)
320 : 5690488 : return;
321 : :
1838 tmunro@postgresql.or 322 [ + + ]:CBC 46915574 : for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
323 : 34638712 : pm += ST_POINTER_STEP)
324 [ + + + + ]: 72526504 : for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
325 : 37887759 : pl -= ST_POINTER_STEP)
326 : 37887759 : DO_SWAP(pl, pl - ST_POINTER_STEP);
327 : 12276829 : return;
328 : : }
329 : 16088050 : presorted = 1;
330 [ + + ]: 160564718 : for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
331 : 144476668 : pm += ST_POINTER_STEP)
332 : : {
333 [ + + ]: 41323308 : DO_CHECK_FOR_INTERRUPTS();
334 [ + + ]: 160029749 : if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
335 : : {
336 : 15553069 : presorted = 0;
337 : 15553069 : break;
338 : : }
339 : : }
340 [ + + ]: 16088038 : if (presorted)
341 : 534969 : return;
342 : 15553069 : pm = a + (n / 2) * ST_POINTER_STEP;
343 [ + + ]: 15553069 : if (n > 7)
344 : : {
345 : 13994347 : pl = a;
346 : 13994347 : pn = a + (n - 1) * ST_POINTER_STEP;
347 [ + + ]: 13994347 : if (n > 40)
348 : : {
349 : 2243140 : size_t d = (n / 8) * ST_POINTER_STEP;
350 : :
351 : 2243140 : pl = DO_MED3(pl, pl + d, pl + 2 * d);
352 : 2243140 : pm = DO_MED3(pm - d, pm, pm + d);
353 : 2243140 : pn = DO_MED3(pn - 2 * d, pn - d, pn);
354 : : }
355 : 13994347 : pm = DO_MED3(pl, pm, pn);
356 : : }
357 : 15553069 : DO_SWAP(a, pm);
358 : 15553069 : pa = pb = a + ST_POINTER_STEP;
359 : 15553069 : pc = pd = a + (n - 1) * ST_POINTER_STEP;
360 : : for (;;)
361 : : {
362 [ + + + + ]: 311441815 : while (pb <= pc && (r = DO_COMPARE(pb, a)) <= 0)
363 : : {
364 [ + + ]: 210648363 : if (r == 0)
365 : : {
366 : 1788069 : DO_SWAP(pa, pb);
367 : 1788069 : pa += ST_POINTER_STEP;
368 : : }
369 : 210648363 : pb += ST_POINTER_STEP;
370 [ + + ]: 119322729 : DO_CHECK_FOR_INTERRUPTS();
371 : : }
372 [ + + + + ]: 294099750 : while (pb <= pc && (r = DO_COMPARE(pc, a)) >= 0)
373 : : {
374 [ + + ]: 193306298 : if (r == 0)
375 : : {
376 : 1406513 : DO_SWAP(pc, pd);
377 : 1406513 : pd -= ST_POINTER_STEP;
378 : : }
379 : 193306298 : pc -= ST_POINTER_STEP;
380 [ + + ]: 103180710 : DO_CHECK_FOR_INTERRUPTS();
381 : : }
382 [ + + ]: 100793452 : if (pb > pc)
383 : 15553069 : break;
384 : 85240383 : DO_SWAP(pb, pc);
385 : 85240383 : pb += ST_POINTER_STEP;
386 : 85240383 : pc -= ST_POINTER_STEP;
387 : : }
388 : 15553069 : pn = a + n * ST_POINTER_STEP;
389 [ + + ]: 15553069 : d1 = Min(pa - a, pb - pa);
390 : 15553069 : DO_SWAPN(a, pb - d1, d1);
391 : 15553069 : d1 = Min(pd - pc, pn - pd - ST_POINTER_STEP);
392 : 15553069 : DO_SWAPN(pb, pn - d1, d1);
393 : 15553069 : d1 = pb - pa;
394 : 15553069 : d2 = pd - pc;
395 [ + + ]: 15553069 : if (d1 <= d2)
396 : : {
397 : : /* Recurse on left partition, then iterate on right partition */
36 john.naylor@postgres 398 :GNC 7806041 : DO_SORT(a, d1 / ST_POINTER_STEP);
399 : :
400 : : /* Iterate rather than recurse to save stack space */
401 : : /* DO_SORT(pn - d2, d2 / ST_POINTER_STEP) */
402 : 7806041 : a = pn - d2;
403 : 7806041 : n = d2 / ST_POINTER_STEP;
404 : 7806041 : goto loop;
405 : : }
406 : : else
407 : : {
408 : : /* Recurse on right partition, then iterate on left partition */
409 : 7747028 : DO_SORT(pn - d2, d2 / ST_POINTER_STEP);
410 : :
411 : : /* Iterate rather than recurse to save stack space */
412 : : /* DO_SORT(a, d1 / ST_POINTER_STEP) */
413 : 7747028 : n = d1 / ST_POINTER_STEP;
414 : 7747028 : goto loop;
415 : : }
416 : : }
417 : : #endif
418 : :
419 : : #undef DO_CHECK_FOR_INTERRUPTS
420 : : #undef DO_COMPARE
421 : : #undef DO_MED3
422 : : #undef DO_SORT
423 : : #undef DO_SWAP
424 : : #undef DO_SWAPN
425 : : #undef ST_CHECK_FOR_INTERRUPTS
426 : : #undef ST_COMPARATOR_TYPE_NAME
427 : : #undef ST_COMPARE
428 : : #undef ST_COMPARE_ARG_TYPE
429 : : #undef ST_COMPARE_RUNTIME_POINTER
430 : : #undef ST_ELEMENT_TYPE
431 : : #undef ST_ELEMENT_TYPE_VOID
432 : : #undef ST_MAKE_NAME
433 : : #undef ST_MAKE_NAME_
434 : : #undef ST_MAKE_PREFIX
435 : : #undef ST_MED3
436 : : #undef ST_POINTER_STEP
437 : : #undef ST_POINTER_TYPE
438 : : #undef ST_SCOPE
439 : : #undef ST_SORT
440 : : #undef ST_SORT_INVOKE_ARG
441 : : #undef ST_SORT_INVOKE_COMPARE
442 : : #undef ST_SORT_INVOKE_ELEMENT_SIZE
443 : : #undef ST_SORT_PROTO_ARG
444 : : #undef ST_SORT_PROTO_COMPARE
445 : : #undef ST_SORT_PROTO_ELEMENT_SIZE
446 : : #undef ST_SWAP
447 : : #undef ST_SWAPN
|
