MobilityDB 1.1
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
178typedef 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. */
183ST_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 */
247static pg_noinline ST_ELEMENT_TYPE *
248ST_MED3(ST_ELEMENT_TYPE * a,
249 ST_ELEMENT_TYPE * b,
250 ST_ELEMENT_TYPE * c
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
259static inline void
260ST_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
268static inline void
269ST_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 */
278ST_SCOPE void
279ST_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
297loop:
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((long unsigned int) (pd - pc), pn - pd - ST_POINTER_STEP); // MobilityDB
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 pg_noinline
Definition: c.h:213
#define Min(x, y)
Definition: c.h:993
#define ST_SORT
Definition: qsort.c:7
#define ST_SCOPE
Definition: qsort.c:10
#define ST_COMPARATOR_TYPE_NAME
Definition: qsort_arg.c:9
#define ST_SORT_PROTO_COMPARE
Definition: sort_template.h:158
#define ST_SORT_PROTO_ELEMENT_SIZE
Definition: sort_template.h:132
#define ST_SORT_PROTO_ARG
Definition: sort_template.h:171