Age Owner 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-2023, 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 *,
179 : const ST_ELEMENT_TYPE * ST_SORT_PROTO_ARG);
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
184 : ST_SORT_PROTO_ELEMENT_SIZE
185 : ST_SORT_PROTO_COMPARE
186 : ST_SORT_PROTO_ARG);
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 : */
247 : static pg_noinline ST_ELEMENT_TYPE *
697 tgl 248 CBC 30800562 : ST_MED3(ST_ELEMENT_TYPE * a,
249 : ST_ELEMENT_TYPE * b,
250 : ST_ELEMENT_TYPE * c
251 : ST_SORT_PROTO_COMPARE
252 : ST_SORT_PROTO_ARG)
253 : {
767 tmunro 254 30800562 : return DO_COMPARE(a, b) < 0 ?
255 14520707 : (DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
256 45321269 : : (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));
257 : }
258 :
259 : static inline void
697 tgl 260 3125647306 : ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b)
261 : {
767 tmunro 262 3125647306 : ST_POINTER_TYPE tmp = *a;
263 :
264 3125647306 : *a = *b;
265 3125647306 : *b = tmp;
266 3125647306 : }
267 :
268 : static inline void
697 tgl 269 235093320 : ST_SWAPN(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b, size_t n)
270 : {
767 tmunro 271 3328162617 : for (size_t i = 0; i < n; ++i)
272 3093069297 : ST_SWAP(&a[i], &b[i]);
273 235093320 : }
274 :
275 : /*
276 : * Sort an array.
277 : */
278 : ST_SCOPE void
697 tgl 279 16977727 : ST_SORT(ST_ELEMENT_TYPE * data, size_t n
280 : ST_SORT_PROTO_ELEMENT_SIZE
281 : ST_SORT_PROTO_COMPARE
282 : ST_SORT_PROTO_ARG)
283 : {
767 tmunro 284 16977727 : 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 22882783 : loop:
298 30307643 : DO_CHECK_FOR_INTERRUPTS();
299 39860510 : if (n < 7)
300 : {
301 64354298 : for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
302 47934649 : pm += ST_POINTER_STEP)
303 101169085 : for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
304 53234406 : pl -= ST_POINTER_STEP)
305 53234406 : DO_SWAP(pl, pl - ST_POINTER_STEP);
306 16419619 : return;
307 : }
308 23440861 : presorted = 1;
309 141972363 : for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
310 118531502 : pm += ST_POINTER_STEP)
311 : {
312 104377344 : DO_CHECK_FOR_INTERRUPTS();
313 141421835 : if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
314 : {
315 22890321 : presorted = 0;
316 22890321 : break;
317 : }
318 : }
319 23440849 : if (presorted)
320 550528 : return;
321 22890321 : pm = a + (n / 2) * ST_POINTER_STEP;
322 22890321 : if (n > 7)
323 : {
324 20790828 : pl = a;
325 20790828 : pn = a + (n - 1) * ST_POINTER_STEP;
326 20790828 : if (n > 40)
327 : {
328 3336578 : size_t d = (n / 8) * ST_POINTER_STEP;
329 :
330 3336578 : pl = DO_MED3(pl, pl + d, pl + 2 * d);
331 3336578 : pm = DO_MED3(pm - d, pm, pm + d);
332 3336578 : pn = DO_MED3(pn - 2 * d, pn - d, pn);
333 : }
334 20790828 : pm = DO_MED3(pl, pm, pn);
335 : }
336 22890321 : DO_SWAP(a, pm);
337 22890321 : pa = pb = a + ST_POINTER_STEP;
338 22890321 : pc = pd = a + (n - 1) * ST_POINTER_STEP;
339 : for (;;)
340 : {
341 497426882 : while (pb <= pc && (r = DO_COMPARE(pb, a)) <= 0)
342 : {
343 332246462 : if (r == 0)
344 : {
345 1770553 : DO_SWAP(pa, pb);
346 1770553 : pa += ST_POINTER_STEP;
347 : }
348 332246462 : pb += ST_POINTER_STEP;
349 267473513 : DO_CHECK_FOR_INTERRUPTS();
350 : }
351 435076212 : while (pb <= pc && (r = DO_COMPARE(pc, a)) >= 0)
352 : {
353 269895792 : if (r == 0)
354 : {
355 1705308 : DO_SWAP(pc, pd);
356 1705308 : pd -= ST_POINTER_STEP;
357 : }
358 269895792 : pc -= ST_POINTER_STEP;
359 226164548 : DO_CHECK_FOR_INTERRUPTS();
360 : }
361 165180420 : if (pb > pc)
362 22890321 : break;
363 142290099 : DO_SWAP(pb, pc);
364 142290099 : pb += ST_POINTER_STEP;
365 142290099 : pc -= ST_POINTER_STEP;
366 : }
367 22890321 : pn = a + n * ST_POINTER_STEP;
368 22890321 : d1 = Min(pa - a, pb - pa);
369 22890321 : DO_SWAPN(a, pb - d1, d1);
370 22890321 : d1 = Min(pd - pc, pn - pd - ST_POINTER_STEP);
371 22890321 : DO_SWAPN(pb, pn - d1, d1);
372 22890321 : d1 = pb - pa;
373 22890321 : d2 = pd - pc;
374 22890321 : if (d1 <= d2)
375 : {
376 : /* Recurse on left partition, then iterate on right partition */
377 10183780 : if (d1 > ST_POINTER_STEP)
378 8266665 : DO_SORT(a, d1 / ST_POINTER_STEP);
379 10183780 : 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 10179252 : a = pn - d2;
384 10179252 : n = d2 / ST_POINTER_STEP;
385 10179252 : goto loop;
386 : }
387 : }
388 : else
389 : {
390 : /* Recurse on right partition, then iterate on left partition */
391 12706541 : if (d2 > ST_POINTER_STEP)
392 7016945 : DO_SORT(pn - d2, d2 / ST_POINTER_STEP);
393 12706541 : if (d1 > ST_POINTER_STEP)
394 : {
395 : /* Iterate rather than recurse to save stack space */
396 : /* DO_SORT(a, d1 / ST_POINTER_STEP) */
397 12703531 : n = d1 / ST_POINTER_STEP;
398 12703531 : 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_CHECK_FOR_INTERRUPTS
411 : #undef ST_COMPARATOR_TYPE_NAME
412 : #undef ST_COMPARE
413 : #undef ST_COMPARE_ARG_TYPE
414 : #undef ST_COMPARE_RUNTIME_POINTER
415 : #undef ST_ELEMENT_TYPE
416 : #undef ST_ELEMENT_TYPE_VOID
417 : #undef ST_MAKE_NAME
418 : #undef ST_MAKE_NAME_
419 : #undef ST_MAKE_PREFIX
420 : #undef ST_MED3
421 : #undef ST_POINTER_STEP
422 : #undef ST_POINTER_TYPE
423 : #undef ST_SCOPE
424 : #undef ST_SORT
425 : #undef ST_SORT_INVOKE_ARG
426 : #undef ST_SORT_INVOKE_COMPARE
427 : #undef ST_SORT_INVOKE_ELEMENT_SIZE
428 : #undef ST_SORT_PROTO_ARG
429 : #undef ST_SORT_PROTO_COMPARE
430 : #undef ST_SORT_PROTO_ELEMENT_SIZE
431 : #undef ST_SWAP
432 : #undef ST_SWAPN
|
