LCOV - code coverage report
Current view: top level - src/backend/utils/sort - qsort_tuple.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 146 146 100.0 %
Date: 2019-11-21 13:06:38 Functions: 5 5 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*
       2             :  * autogenerated by src/backend/utils/sort/gen_qsort_tuple.pl, do not edit!
       3             :  *
       4             :  * This file is included by tuplesort.c, rather than compiled separately.
       5             :  */
       6             : 
       7             : /*  $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $   */
       8             : 
       9             : /*-
      10             :  * Copyright (c) 1992, 1993
      11             :  *  The Regents of the University of California.  All rights reserved.
      12             :  *
      13             :  * Redistribution and use in source and binary forms, with or without
      14             :  * modification, are permitted provided that the following conditions
      15             :  * are met:
      16             :  * 1. Redistributions of source code must retain the above copyright
      17             :  *    notice, this list of conditions and the following disclaimer.
      18             :  * 2. Redistributions in binary form must reproduce the above copyright
      19             :  *    notice, this list of conditions and the following disclaimer in the
      20             :  *    documentation and/or other materials provided with the distribution.
      21             :  * 3. Neither the name of the University nor the names of its contributors
      22             :  *    may be used to endorse or promote products derived from this software
      23             :  *    without specific prior written permission.
      24             :  *
      25             :  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
      26             :  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
      27             :  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
      28             :  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
      29             :  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
      30             :  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
      31             :  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
      32             :  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
      33             :  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
      34             :  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
      35             :  * SUCH DAMAGE.
      36             :  */
      37             : 
      38             : /*
      39             :  * Qsort routine based on J. L. Bentley and M. D. McIlroy,
      40             :  * "Engineering a sort function",
      41             :  * Software--Practice and Experience 23 (1993) 1249-1265.
      42             :  *
      43             :  * We have modified their original by adding a check for already-sorted input,
      44             :  * which seems to be a win per discussions on pgsql-hackers around 2006-03-21.
      45             :  *
      46             :  * Also, we recurse on the smaller partition and iterate on the larger one,
      47             :  * which ensures we cannot recurse more than log(N) levels (since the
      48             :  * partition recursed to is surely no more than half of the input).  Bentley
      49             :  * and McIlroy explicitly rejected doing this on the grounds that it's "not
      50             :  * worth the effort", but we have seen crashes in the field due to stack
      51             :  * overrun, so that judgment seems wrong.
      52             :  */
      53             : 
      54             : static void
      55     3765130 : swapfunc(SortTuple *a, SortTuple *b, size_t n)
      56             : {
      57             :     do
      58             :     {
      59     3765130 :         SortTuple   t = *a;
      60     3765130 :         *a++ = *b;
      61     3765130 :         *b++ = t;
      62     3765130 :     } while (--n > 0);
      63     2882510 : }
      64             : 
      65             : #define swap(a, b)                      \
      66             :     do {                                \
      67             :         SortTuple t = *(a);             \
      68             :         *(a) = *(b);                    \
      69             :         *(b) = t;                       \
      70             :     } while (0);
      71             : 
      72             : #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n)
      73             : 
      74             : static SortTuple *
      75     3476506 : med3_tuple(SortTuple *a, SortTuple *b, SortTuple *c, SortTupleComparator cmp_tuple, Tuplesortstate *state)
      76             : {
      77     3476506 :     return cmp_tuple(a, b, state) < 0 ?
      78     2642624 :         (cmp_tuple(b, c, state) < 0 ? b :
      79     1006902 :             (cmp_tuple(a, c, state) < 0 ? c : a))
      80     6528280 :         : (cmp_tuple(b, c, state) > 0 ? b :
      81     1416052 :             (cmp_tuple(a, c, state) < 0 ? a : c));
      82             : }
      83             : 
      84             : static void
      85     4399500 : qsort_tuple(SortTuple *a, size_t n, SortTupleComparator cmp_tuple, Tuplesortstate *state)
      86             : {
      87             :     SortTuple  *pa,
      88             :                *pb,
      89             :                *pc,
      90             :                *pd,
      91             :                *pl,
      92             :                *pm,
      93             :                *pn;
      94             :     size_t      d1,
      95             :                 d2;
      96             :     int         r,
      97             :                 presorted;
      98             : 
      99             : loop:
     100     4399500 :     CHECK_FOR_INTERRUPTS();
     101     4399500 :     if (n < 7)
     102             :     {
     103     7194786 :         for (pm = a + 1; pm < a + n; pm++)
     104    11641008 :             for (pl = pm; pl > a && cmp_tuple(pl - 1, pl, state) > 0; pl--)
     105     6245330 :                 swap(pl, pl - 1);
     106     1799108 :         return;
     107             :     }
     108     2600360 :     presorted = 1;
     109    16681068 :     for (pm = a + 1; pm < a + n; pm++)
     110             :     {
     111    16660318 :         CHECK_FOR_INTERRUPTS();
     112    16660318 :         if (cmp_tuple(pm - 1, pm, state) > 0)
     113             :         {
     114     2579598 :             presorted = 0;
     115     2579598 :             break;
     116             :         }
     117             :     }
     118     2600348 :     if (presorted)
     119       20750 :         return;
     120     2579598 :     pm = a + (n / 2);
     121     2579598 :     if (n > 7)
     122             :     {
     123     2340040 :         pl = a;
     124     2340040 :         pn = a + (n - 1);
     125     2340040 :         if (n > 40)
     126             :         {
     127      378822 :             size_t      d = (n / 8);
     128             : 
     129      378822 :             pl = med3_tuple(pl, pl + d, pl + 2 * d, cmp_tuple, state);
     130      378822 :             pm = med3_tuple(pm - d, pm, pm + d, cmp_tuple, state);
     131      378822 :             pn = med3_tuple(pn - 2 * d, pn - d, pn, cmp_tuple, state);
     132             :         }
     133     2340040 :         pm = med3_tuple(pl, pm, pn, cmp_tuple, state);
     134             :     }
     135     2579598 :     swap(a, pm);
     136     2579598 :     pa = pb = a + 1;
     137     2579598 :     pc = pd = a + (n - 1);
     138             :     for (;;)
     139             :     {
     140   103866846 :         while (pb <= pc && (r = cmp_tuple(pb, a, state)) <= 0)
     141             :         {
     142    42309468 :             if (r == 0)
     143             :             {
     144      136720 :                 swap(pa, pb);
     145      136720 :                 pa++;
     146             :             }
     147    42309468 :             pb++;
     148    42309468 :             CHECK_FOR_INTERRUPTS();
     149             :         }
     150    76272712 :         while (pb <= pc && (r = cmp_tuple(pc, a, state)) >= 0)
     151             :         {
     152    33514728 :             if (r == 0)
     153             :             {
     154      129778 :                 swap(pc, pd);
     155      129778 :                 pd--;
     156             :             }
     157    33514728 :             pc--;
     158    33514728 :             CHECK_FOR_INTERRUPTS();
     159             :         }
     160    21378992 :         if (pb > pc)
     161     2579598 :             break;
     162    18799394 :         swap(pb, pc);
     163    18799394 :         pb++;
     164    18799394 :         pc--;
     165             :     }
     166     2579598 :     pn = a + n;
     167     2579598 :     d1 = Min(pa - a, pb - pa);
     168     2579598 :     vecswap(a, pb - d1, d1);
     169     2579598 :     d1 = Min(pd - pc, pn - pd - 1);
     170     2579598 :     vecswap(pb, pn - d1, d1);
     171     2579598 :     d1 = pb - pa;
     172     2579598 :     d2 = pd - pc;
     173     2579598 :     if (d1 <= d2)
     174             :     {
     175             :         /* Recurse on left partition, then iterate on right partition */
     176     1164884 :         if (d1 > 1)
     177     1002720 :             qsort_tuple(a, d1, cmp_tuple, state);
     178     1164884 :         if (d2 > 1)
     179             :         {
     180             :             /* Iterate rather than recurse to save stack space */
     181             :             /* qsort_tuple(pn - d2, d2, cmp_tuple, state); */
     182     1164872 :             a = pn - d2;
     183     1164872 :             n = d2;
     184     1164872 :             goto loop;
     185             :         }
     186             :     }
     187             :     else
     188             :     {
     189             :         /* Recurse on right partition, then iterate on left partition */
     190     1414714 :         if (d2 > 1)
     191      791066 :             qsort_tuple(pn - d2, d2, cmp_tuple, state);
     192     1414714 :         if (d1 > 1)
     193             :         {
     194             :             /* Iterate rather than recurse to save stack space */
     195             :             /* qsort_tuple(a, d1, cmp_tuple, state); */
     196     1414668 :             n = d1;
     197     1414668 :             goto loop;
     198             :         }
     199             :     }
     200             : }
     201             : 
     202             : #define cmp_ssup(a, b, ssup) \
     203             :     ApplySortComparator((a)->datum1, (a)->isnull1, \
     204             :                         (b)->datum1, (b)->isnull1, ssup)
     205             : 
     206             : static SortTuple *
     207      386726 : med3_ssup(SortTuple *a, SortTuple *b, SortTuple *c, SortSupport ssup)
     208             : {
     209      386726 :     return cmp_ssup(a, b, ssup) < 0 ?
     210      287030 :         (cmp_ssup(b, c, ssup) < 0 ? b :
     211      108614 :             (cmp_ssup(a, c, ssup) < 0 ? c : a))
     212      739232 :         : (cmp_ssup(b, c, ssup) > 0 ? b :
     213      174090 :             (cmp_ssup(a, c, ssup) < 0 ? a : c));
     214             : }
     215             : 
     216             : static void
     217      466262 : qsort_ssup(SortTuple *a, size_t n, SortSupport ssup)
     218             : {
     219             :     SortTuple  *pa,
     220             :                *pb,
     221             :                *pc,
     222             :                *pd,
     223             :                *pl,
     224             :                *pm,
     225             :                *pn;
     226             :     size_t      d1,
     227             :                 d2;
     228             :     int         r,
     229             :                 presorted;
     230             : 
     231             : loop:
     232      466262 :     CHECK_FOR_INTERRUPTS();
     233      466262 :     if (n < 7)
     234             :     {
     235      640294 :         for (pm = a + 1; pm < a + n; pm++)
     236      914642 :             for (pl = pm; pl > a && cmp_ssup(pl - 1, pl, ssup) > 0; pl--)
     237      438334 :                 swap(pl, pl - 1);
     238      163986 :         return;
     239             :     }
     240      302276 :     presorted = 1;
     241     4010540 :     for (pm = a + 1; pm < a + n; pm++)
     242             :     {
     243     4003988 :         CHECK_FOR_INTERRUPTS();
     244     4003988 :         if (cmp_ssup(pm - 1, pm, ssup) > 0)
     245             :         {
     246      295724 :             presorted = 0;
     247      295724 :             break;
     248             :         }
     249             :     }
     250      302276 :     if (presorted)
     251        6552 :         return;
     252      295724 :     pm = a + (n / 2);
     253      295724 :     if (n > 7)
     254             :     {
     255      278342 :         pl = a;
     256      278342 :         pn = a + (n - 1);
     257      278342 :         if (n > 40)
     258             :         {
     259       36128 :             size_t      d = (n / 8);
     260             : 
     261       36128 :             pl = med3_ssup(pl, pl + d, pl + 2 * d, ssup);
     262       36128 :             pm = med3_ssup(pm - d, pm, pm + d, ssup);
     263       36128 :             pn = med3_ssup(pn - 2 * d, pn - d, pn, ssup);
     264             :         }
     265      278342 :         pm = med3_ssup(pl, pm, pn, ssup);
     266             :     }
     267      295724 :     swap(a, pm);
     268      295724 :     pa = pb = a + 1;
     269      295724 :     pc = pd = a + (n - 1);
     270             :     for (;;)
     271             :     {
     272    12692862 :         while (pb <= pc && (r = cmp_ssup(pb, a, ssup)) <= 0)
     273             :         {
     274     6398480 :             if (r == 0)
     275             :             {
     276      401976 :                 swap(pa, pb);
     277      401976 :                 pa++;
     278             :             }
     279     6398480 :             pb++;
     280     6398480 :             CHECK_FOR_INTERRUPTS();
     281             :         }
     282     9221768 :         while (pb <= pc && (r = cmp_ssup(pc, a, ssup)) >= 0)
     283             :         {
     284     4828364 :             if (r == 0)
     285             :             {
     286      293254 :                 swap(pc, pd);
     287      293254 :                 pd--;
     288             :             }
     289     4828364 :             pc--;
     290     4828364 :             CHECK_FOR_INTERRUPTS();
     291             :         }
     292     2196702 :         if (pb > pc)
     293      295724 :             break;
     294     1900978 :         swap(pb, pc);
     295     1900978 :         pb++;
     296     1900978 :         pc--;
     297             :     }
     298      295724 :     pn = a + n;
     299      295724 :     d1 = Min(pa - a, pb - pa);
     300      295724 :     vecswap(a, pb - d1, d1);
     301      295724 :     d1 = Min(pd - pc, pn - pd - 1);
     302      295724 :     vecswap(pb, pn - d1, d1);
     303      295724 :     d1 = pb - pa;
     304      295724 :     d2 = pd - pc;
     305      295724 :     if (d1 <= d2)
     306             :     {
     307             :         /* Recurse on left partition, then iterate on right partition */
     308      130208 :         if (d1 > 1)
     309       78844 :             qsort_ssup(a, d1, ssup);
     310      130208 :         if (d2 > 1)
     311             :         {
     312             :             /* Iterate rather than recurse to save stack space */
     313             :             /* qsort_ssup(pn - d2, d2, ssup); */
     314      130174 :             a = pn - d2;
     315      130174 :             n = d2;
     316      130174 :             goto loop;
     317             :         }
     318             :     }
     319             :     else
     320             :     {
     321             :         /* Recurse on right partition, then iterate on left partition */
     322      165516 :         if (d2 > 1)
     323       61028 :             qsort_ssup(pn - d2, d2, ssup);
     324      165516 :         if (d1 > 1)
     325             :         {
     326             :             /* Iterate rather than recurse to save stack space */
     327             :             /* qsort_ssup(a, d1, ssup); */
     328      165500 :             n = d1;
     329      165500 :             goto loop;
     330             :         }
     331             :     }
     332             : }

Generated by: LCOV version 1.13