src/include/lib/sort_template.h

   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 *,
 189                                                                                 const ST_ELEMENT_TYPE * ST_SORT_PROTO_ARG);
 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
 194                                           ST_SORT_PROTO_ELEMENT_SIZE
 195                                           ST_SORT_PROTO_COMPARE
 196                                           ST_SORT_PROTO_ARG);
 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  */
 260 static pg_noinline ST_ELEMENT_TYPE *
 261 ST_MED3(ST_ELEMENT_TYPE * a,
 262                 ST_ELEMENT_TYPE * b,
 263                 ST_ELEMENT_TYPE * c
 264                 ST_SORT_PROTO_COMPARE
 265                 ST_SORT_PROTO_ARG)
 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
 293                 ST_SORT_PROTO_ELEMENT_SIZE
 294                 ST_SORT_PROTO_COMPARE
 295                 ST_SORT_PROTO_ARG)
 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