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