LCOV - code coverage report
Current view: top level - src/include/lib - sort_template.h (source / functions) Hit Total Coverage
Test: PostgreSQL 17beta1 Lines: 82 82 100.0 %
Date: 2024-06-14 18:11:26 Functions: 40 40 100.0 %
Legend: Lines: hit not hit

          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-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    33729334 : 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    33729334 :     return DO_COMPARE(a, b) < 0 ?
     268    19230020 :         (DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
     269    52959354 :         : (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));
     270             : }
     271             : 
     272             : static inline void
     273  2343089726 : ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b)
     274             : {
     275  2343089726 :     ST_POINTER_TYPE tmp = *a;
     276             : 
     277  2343089726 :     *a = *b;
     278  2343089726 :     *b = tmp;
     279  2343089726 : }
     280             : 
     281             : static inline void
     282   237368460 : ST_SWAPN(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b, size_t n)
     283             : {
     284  2541765534 :     for (size_t i = 0; i < n; ++i)
     285  2304397074 :         ST_SWAP(&a[i], &b[i]);
     286   237368460 : }
     287             : 
     288             : /*
     289             :  * Sort an array.
     290             :  */
     291             : ST_SCOPE void
     292    21085164 : 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    21085164 :     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    46256056 : loop:
     311    19118268 :     DO_CHECK_FOR_INTERRUPTS();
     312    46256056 :     if (n < 7)
     313             :     {
     314    75644352 :         for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
     315    55136732 :              pm += ST_POINTER_STEP)
     316   115753816 :             for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
     317    60617024 :                  pl -= ST_POINTER_STEP)
     318    60617024 :                 DO_SWAP(pl, pl - ST_POINTER_STEP);
     319    20507560 :         return;
     320             :     }
     321    25748436 :     presorted = 1;
     322   288516510 :     for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
     323   262768074 :          pm += ST_POINTER_STEP)
     324             :     {
     325    65357358 :         DO_CHECK_FOR_INTERRUPTS();
     326   287943150 :         if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
     327             :         {
     328    25175052 :             presorted = 0;
     329    25175052 :             break;
     330             :         }
     331             :     }
     332    25748412 :     if (presorted)
     333      573360 :         return;
     334    25175052 :     pm = a + (n / 2) * ST_POINTER_STEP;
     335    25175052 :     if (n > 7)
     336             :     {
     337    22854202 :         pl = a;
     338    22854202 :         pn = a + (n - 1) * ST_POINTER_STEP;
     339    22854202 :         if (n > 40)
     340             :         {
     341     3625044 :             size_t      d = (n / 8) * ST_POINTER_STEP;
     342             : 
     343     3625044 :             pl = DO_MED3(pl, pl + d, pl + 2 * d);
     344     3625044 :             pm = DO_MED3(pm - d, pm, pm + d);
     345     3625044 :             pn = DO_MED3(pn - 2 * d, pn - d, pn);
     346             :         }
     347    22854202 :         pm = DO_MED3(pl, pm, pn);
     348             :     }
     349    25175052 :     DO_SWAP(a, pm);
     350    25175052 :     pa = pb = a + ST_POINTER_STEP;
     351    25175052 :     pc = pd = a + (n - 1) * ST_POINTER_STEP;
     352             :     for (;;)
     353             :     {
     354   507475776 :         while (pb <= pc && (r = DO_COMPARE(pb, a)) <= 0)
     355             :         {
     356   348187424 :             if (r == 0)
     357             :             {
     358     2938064 :                 DO_SWAP(pa, pb);
     359     2938064 :                 pa += ST_POINTER_STEP;
     360             :             }
     361   348187424 :             pb += ST_POINTER_STEP;
     362   187172942 :             DO_CHECK_FOR_INTERRUPTS();
     363             :         }
     364   478668636 :         while (pb <= pc && (r = DO_COMPARE(pc, a)) >= 0)
     365             :         {
     366   319380284 :             if (r == 0)
     367             :             {
     368     2867568 :                 DO_SWAP(pc, pd);
     369     2867568 :                 pd -= ST_POINTER_STEP;
     370             :             }
     371   319380284 :             pc -= ST_POINTER_STEP;
     372   154399206 :             DO_CHECK_FOR_INTERRUPTS();
     373             :         }
     374   159288352 :         if (pb > pc)
     375    25175052 :             break;
     376   134113300 :         DO_SWAP(pb, pc);
     377   134113300 :         pb += ST_POINTER_STEP;
     378   134113300 :         pc -= ST_POINTER_STEP;
     379             :     }
     380    25175052 :     pn = a + n * ST_POINTER_STEP;
     381    25175052 :     d1 = Min(pa - a, pb - pa);
     382    25175052 :     DO_SWAPN(a, pb - d1, d1);
     383    25175052 :     d1 = Min(pd - pc, pn - pd - ST_POINTER_STEP);
     384    25175052 :     DO_SWAPN(pb, pn - d1, d1);
     385    25175052 :     d1 = pb - pa;
     386    25175052 :     d2 = pd - pc;
     387    25175052 :     if (d1 <= d2)
     388             :     {
     389             :         /* Recurse on left partition, then iterate on right partition */
     390    12824230 :         if (d1 > ST_POINTER_STEP)
     391    10510558 :             DO_SORT(a, d1 / ST_POINTER_STEP);
     392    12824230 :         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    12821744 :             a = pn - d2;
     397    12821744 :             n = d2 / ST_POINTER_STEP;
     398    12821744 :             goto loop;
     399             :         }
     400             :     }
     401             :     else
     402             :     {
     403             :         /* Recurse on right partition, then iterate on left partition */
     404    12350822 :         if (d2 > ST_POINTER_STEP)
     405     6823628 :             DO_SORT(pn - d2, d2 / ST_POINTER_STEP);
     406    12350822 :         if (d1 > ST_POINTER_STEP)
     407             :         {
     408             :             /* Iterate rather than recurse to save stack space */
     409             :             /* DO_SORT(a, d1 / ST_POINTER_STEP) */
     410    12349148 :             n = d1 / ST_POINTER_STEP;
     411    12349148 :             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

Generated by: LCOV version 1.14