PostgreSQL Source Code git master
sort_template.h
Go to the documentation of this file.
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-2025, 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
188typedef int (*ST_COMPARATOR_TYPE_NAME) (const ST_ELEMENT_TYPE *,
190#endif
191
192/* Declare the sort function. Note optional arguments at end. */
193ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE * first, size_t n
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 */
261ST_MED3(ST_ELEMENT_TYPE * a,
266{
267 return DO_COMPARE(a, b) < 0 ?
268 (DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
269 : (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));
270}
271
272static inline void
273ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b)
274{
275 ST_POINTER_TYPE tmp = *a;
276
277 *a = *b;
278 *b = tmp;
279}
280
281static inline void
282ST_SWAPN(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b, size_t n)
283{
284 for (size_t i = 0; i < n; ++i)
285 ST_SWAP(&a[i], &b[i]);
286}
287
288/*
289 * Sort an array.
290 */
291ST_SCOPE void
292ST_SORT(ST_ELEMENT_TYPE * data, size_t n
296{
297 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
310loop:
311 DO_CHECK_FOR_INTERRUPTS();
312 if (n < 7)
313 {
314 for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
315 pm += ST_POINTER_STEP)
316 for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
317 pl -= ST_POINTER_STEP)
318 DO_SWAP(pl, pl - ST_POINTER_STEP);
319 return;
320 }
321 presorted = 1;
322 for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
323 pm += ST_POINTER_STEP)
324 {
325 DO_CHECK_FOR_INTERRUPTS();
326 if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
327 {
328 presorted = 0;
329 break;
330 }
331 }
332 if (presorted)
333 return;
334 pm = a + (n / 2) * ST_POINTER_STEP;
335 if (n > 7)
336 {
337 pl = a;
338 pn = a + (n - 1) * ST_POINTER_STEP;
339 if (n > 40)
340 {
341 size_t d = (n / 8) * ST_POINTER_STEP;
342
343 pl = DO_MED3(pl, pl + d, pl + 2 * d);
344 pm = DO_MED3(pm - d, pm, pm + d);
345 pn = DO_MED3(pn - 2 * d, pn - d, pn);
346 }
347 pm = DO_MED3(pl, pm, pn);
348 }
349 DO_SWAP(a, pm);
350 pa = pb = a + ST_POINTER_STEP;
351 pc = pd = a + (n - 1) * ST_POINTER_STEP;
352 for (;;)
353 {
354 while (pb <= pc && (r = DO_COMPARE(pb, a)) <= 0)
355 {
356 if (r == 0)
357 {
358 DO_SWAP(pa, pb);
359 pa += ST_POINTER_STEP;
360 }
361 pb += ST_POINTER_STEP;
362 DO_CHECK_FOR_INTERRUPTS();
363 }
364 while (pb <= pc && (r = DO_COMPARE(pc, a)) >= 0)
365 {
366 if (r == 0)
367 {
368 DO_SWAP(pc, pd);
369 pd -= ST_POINTER_STEP;
370 }
371 pc -= ST_POINTER_STEP;
372 DO_CHECK_FOR_INTERRUPTS();
373 }
374 if (pb > pc)
375 break;
376 DO_SWAP(pb, pc);
377 pb += ST_POINTER_STEP;
378 pc -= ST_POINTER_STEP;
379 }
380 pn = a + n * ST_POINTER_STEP;
381 d1 = Min(pa - a, pb - pa);
382 DO_SWAPN(a, pb - d1, d1);
383 d1 = Min(pd - pc, pn - pd - ST_POINTER_STEP);
384 DO_SWAPN(pb, pn - d1, d1);
385 d1 = pb - pa;
386 d2 = pd - pc;
387 if (d1 <= d2)
388 {
389 /* Recurse on left partition, then iterate on right partition */
390 if (d1 > ST_POINTER_STEP)
391 DO_SORT(a, d1 / ST_POINTER_STEP);
392 if (d2 > ST_POINTER_STEP)
393 {
394 /* Iterate rather than recurse to save stack space */
395 /* DO_SORT(pn - d2, d2 / ST_POINTER_STEP) */
396 a = pn - d2;
397 n = d2 / ST_POINTER_STEP;
398 goto loop;
399 }
400 }
401 else
402 {
403 /* Recurse on right partition, then iterate on left partition */
404 if (d2 > ST_POINTER_STEP)
405 DO_SORT(pn - d2, d2 / ST_POINTER_STEP);
406 if (d1 > ST_POINTER_STEP)
407 {
408 /* Iterate rather than recurse to save stack space */
409 /* DO_SORT(a, d1 / ST_POINTER_STEP) */
410 n = d1 / ST_POINTER_STEP;
411 goto loop;
412 }
413 }
414}
415#endif
416
417#undef DO_CHECK_FOR_INTERRUPTS
418#undef DO_COMPARE
419#undef DO_MED3
420#undef DO_SORT
421#undef DO_SWAP
422#undef DO_SWAPN
423#undef ST_CHECK_FOR_INTERRUPTS
424#undef ST_COMPARATOR_TYPE_NAME
425#undef ST_COMPARE
426#undef ST_COMPARE_ARG_TYPE
427#undef ST_COMPARE_RUNTIME_POINTER
428#undef ST_ELEMENT_TYPE
429#undef ST_ELEMENT_TYPE_VOID
430#undef ST_MAKE_NAME
431#undef ST_MAKE_NAME_
432#undef ST_MAKE_PREFIX
433#undef ST_MED3
434#undef ST_POINTER_STEP
435#undef ST_POINTER_TYPE
436#undef ST_SCOPE
437#undef ST_SORT
438#undef ST_SORT_INVOKE_ARG
439#undef ST_SORT_INVOKE_COMPARE
440#undef ST_SORT_INVOKE_ELEMENT_SIZE
441#undef ST_SORT_PROTO_ARG
442#undef ST_SORT_PROTO_COMPARE
443#undef ST_SORT_PROTO_ELEMENT_SIZE
444#undef ST_SWAP
445#undef ST_SWAPN
#define ST_SORT
Definition: _int_tool.c:214
#define ST_ELEMENT_TYPE
Definition: _int_tool.c:215
#define ST_SCOPE
Definition: _int_tool.c:218
#define pg_noinline
Definition: c.h:272
#define Min(x, y)
Definition: c.h:961
int b
Definition: isn.c:69
int a
Definition: isn.c:68
int i
Definition: isn.c:72
const void * data
char * c
#define ST_COMPARATOR_TYPE_NAME
#define ST_SORT_PROTO_COMPARE
#define ST_SORT_PROTO_ELEMENT_SIZE
#define ST_SORT_PROTO_ARG