LCOV - code coverage report
Current view: top level - src/include/lib - sort_template.h (source / functions) Hit Total Coverage
Test: PostgreSQL 15devel Lines: 82 82 100.0 %
Date: 2021-12-05 01:09:12 Functions: 24 24 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, 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 *
     248    45984818 : 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             : {
     254    45984818 :     return DO_COMPARE(a, b) < 0 ?
     255    22644364 :         (DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
     256    68629182 :         : (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));
     257             : }
     258             : 
     259             : static inline void
     260  4581270516 : ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b)
     261             : {
     262  4581270516 :     ST_POINTER_TYPE tmp = *a;
     263             : 
     264  4581270516 :     *a = *b;
     265  4581270516 :     *b = tmp;
     266  4581270516 : }
     267             : 
     268             : static inline void
     269   348085664 : ST_SWAPN(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b, size_t n)
     270             : {
     271  4880563568 :     for (size_t i = 0; i < n; ++i)
     272  4532477904 :         ST_SWAP(&a[i], &b[i]);
     273   348085664 : }
     274             : 
     275             : /*
     276             :  * Sort an array.
     277             :  */
     278             : ST_SCOPE void
     279    25507130 : 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             : {
     284    25507130 :     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    59698434 : loop:
     298     7225040 :     DO_CHECK_FOR_INTERRUPTS();
     299    59698434 :     if (n < 7)
     300             :     {
     301    96767852 :         for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
     302    72055524 :              pm += ST_POINTER_STEP)
     303   152764574 :             for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
     304    80709018 :                  pl -= ST_POINTER_STEP)
     305    80709018 :                 DO_SWAP(pl, pl - ST_POINTER_STEP);
     306    24712296 :         return;
     307             :     }
     308    34986106 :     presorted = 1;
     309   230075240 :     for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
     310   195089134 :          pm += ST_POINTER_STEP)
     311             :     {
     312    24194052 :         DO_CHECK_FOR_INTERRUPTS();
     313   229287036 :         if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
     314             :         {
     315    34197890 :             presorted = 0;
     316    34197890 :             break;
     317             :         }
     318             :     }
     319    34986094 :     if (presorted)
     320      788204 :         return;
     321    34197890 :     pm = a + (n / 2) * ST_POINTER_STEP;
     322    34197890 :     if (n > 7)
     323             :     {
     324    30986822 :         pl = a;
     325    30986822 :         pn = a + (n - 1) * ST_POINTER_STEP;
     326    30986822 :         if (n > 40)
     327             :         {
     328     4999332 :             size_t      d = (n / 8) * ST_POINTER_STEP;
     329             : 
     330     4999332 :             pl = DO_MED3(pl, pl + d, pl + 2 * d);
     331     4999332 :             pm = DO_MED3(pm - d, pm, pm + d);
     332     4999332 :             pn = DO_MED3(pn - 2 * d, pn - d, pn);
     333             :         }
     334    30986822 :         pm = DO_MED3(pl, pm, pn);
     335             :     }
     336    34197890 :     DO_SWAP(a, pm);
     337    34197890 :     pa = pb = a + ST_POINTER_STEP;
     338    34197890 :     pc = pd = a + (n - 1) * ST_POINTER_STEP;
     339             :     for (;;)
     340             :     {
     341   725164740 :         while (pb <= pc && (r = DO_COMPARE(pb, a)) <= 0)
     342             :         {
     343   482414190 :             if (r == 0)
     344             :             {
     345     2753738 :                 DO_SWAP(pa, pb);
     346     2753738 :                 pa += ST_POINTER_STEP;
     347             :             }
     348   482414190 :             pb += ST_POINTER_STEP;
     349    64561586 :             DO_CHECK_FOR_INTERRUPTS();
     350             :         }
     351   644916800 :         while (pb <= pc && (r = DO_COMPARE(pc, a)) >= 0)
     352             :         {
     353   402166250 :             if (r == 0)
     354             :             {
     355     2269190 :                 DO_SWAP(pc, pd);
     356     2269190 :                 pd -= ST_POINTER_STEP;
     357             :             }
     358   402166250 :             pc -= ST_POINTER_STEP;
     359    54923664 :             DO_CHECK_FOR_INTERRUPTS();
     360             :         }
     361   242750550 :         if (pb > pc)
     362    34197890 :             break;
     363   208552660 :         DO_SWAP(pb, pc);
     364   208552660 :         pb += ST_POINTER_STEP;
     365   208552660 :         pc -= ST_POINTER_STEP;
     366             :     }
     367    34197890 :     pn = a + n * ST_POINTER_STEP;
     368    34197890 :     d1 = Min(pa - a, pb - pa);
     369    34197890 :     DO_SWAPN(a, pb - d1, d1);
     370    34197890 :     d1 = Min(pd - pc, pn - pd - ST_POINTER_STEP);
     371    34197890 :     DO_SWAPN(pb, pn - d1, d1);
     372    34197890 :     d1 = pb - pa;
     373    34197890 :     d2 = pd - pc;
     374    34197890 :     if (d1 <= d2)
     375             :     {
     376             :         /* Recurse on left partition, then iterate on right partition */
     377    15768258 :         if (d1 > ST_POINTER_STEP)
     378    12480882 :             DO_SORT(a, d1 / ST_POINTER_STEP);
     379    15768258 :         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    15764880 :             a = pn - d2;
     384    15764880 :             n = d2 / ST_POINTER_STEP;
     385    15764880 :             goto loop;
     386             :         }
     387             :     }
     388             :     else
     389             :     {
     390             :         /* Recurse on right partition, then iterate on left partition */
     391    18429632 :         if (d2 > ST_POINTER_STEP)
     392    10372094 :             DO_SORT(pn - d2, d2 / ST_POINTER_STEP);
     393    18429632 :         if (d1 > ST_POINTER_STEP)
     394             :         {
     395             :             /* Iterate rather than recurse to save stack space */
     396             :             /* DO_SORT(a, d1 / ST_POINTER_STEP) */
     397    18426424 :             n = d1 / ST_POINTER_STEP;
     398    18426424 :             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

Generated by: LCOV version 1.14