PostgreSQL Source Code  git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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-2024, 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 *,
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
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  */
261 ST_MED3(ST_ELEMENT_TYPE * a,
262  ST_ELEMENT_TYPE * b,
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 
272 static inline void
273 ST_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 
281 static inline void
282 ST_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  */
291 ST_SCOPE void
292 ST_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 
310 loop:
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: bufmgr.c:5950
#define ST_ELEMENT_TYPE
Definition: bufmgr.c:5951
#define ST_SCOPE
Definition: bufmgr.c:5953
#define pg_noinline
Definition: c.h:265
#define Min(x, y)
Definition: c.h:983
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