LCOV - code coverage report
Current view: top level - src/port - qsort.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 73 73 100.0 %
Date: 2019-11-13 21:06:57 Functions: 4 4 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*
       2             :  *  qsort.c: standard quicksort algorithm
       3             :  *
       4             :  *  Modifications from vanilla NetBSD source:
       5             :  *    Add do ... while() macro fix
       6             :  *    Remove __inline, _DIAGASSERTs, __P
       7             :  *    Remove ill-considered "swap_cnt" switch to insertion sort,
       8             :  *    in favor of a simple check for presorted input.
       9             :  *    Take care to recurse on the smaller partition, to bound stack usage.
      10             :  *
      11             :  *  CAUTION: if you change this file, see also qsort_arg.c, gen_qsort_tuple.pl
      12             :  *
      13             :  *  src/port/qsort.c
      14             :  */
      15             : 
      16             : /*  $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $   */
      17             : 
      18             : /*-
      19             :  * Copyright (c) 1992, 1993
      20             :  *  The Regents of the University of California.  All rights reserved.
      21             :  *
      22             :  * Redistribution and use in source and binary forms, with or without
      23             :  * modification, are permitted provided that the following conditions
      24             :  * are met:
      25             :  * 1. Redistributions of source code must retain the above copyright
      26             :  *    notice, this list of conditions and the following disclaimer.
      27             :  * 2. Redistributions in binary form must reproduce the above copyright
      28             :  *    notice, this list of conditions and the following disclaimer in the
      29             :  *    documentation and/or other materials provided with the distribution.
      30             :  * 3. Neither the name of the University nor the names of its contributors
      31             :  *    may be used to endorse or promote products derived from this software
      32             :  *    without specific prior written permission.
      33             :  *
      34             :  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
      35             :  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
      36             :  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
      37             :  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
      38             :  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
      39             :  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
      40             :  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
      41             :  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
      42             :  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
      43             :  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
      44             :  * SUCH DAMAGE.
      45             :  */
      46             : 
      47             : #include "c.h"
      48             : 
      49             : 
      50             : static char *med3(char *a, char *b, char *c,
      51             :                   int (*cmp) (const void *, const void *));
      52             : static void swapfunc(char *, char *, size_t, int);
      53             : 
      54             : /*
      55             :  * Qsort routine based on J. L. Bentley and M. D. McIlroy,
      56             :  * "Engineering a sort function",
      57             :  * Software--Practice and Experience 23 (1993) 1249-1265.
      58             :  *
      59             :  * We have modified their original by adding a check for already-sorted input,
      60             :  * which seems to be a win per discussions on pgsql-hackers around 2006-03-21.
      61             :  *
      62             :  * Also, we recurse on the smaller partition and iterate on the larger one,
      63             :  * which ensures we cannot recurse more than log(N) levels (since the
      64             :  * partition recursed to is surely no more than half of the input).  Bentley
      65             :  * and McIlroy explicitly rejected doing this on the grounds that it's "not
      66             :  * worth the effort", but we have seen crashes in the field due to stack
      67             :  * overrun, so that judgment seems wrong.
      68             :  */
      69             : 
      70             : #define swapcode(TYPE, parmi, parmj, n) \
      71             : do {        \
      72             :     size_t i = (n) / sizeof (TYPE);         \
      73             :     TYPE *pi = (TYPE *)(void *)(parmi);         \
      74             :     TYPE *pj = (TYPE *)(void *)(parmj);         \
      75             :     do {                        \
      76             :         TYPE    t = *pi;            \
      77             :         *pi++ = *pj;                \
      78             :         *pj++ = t;              \
      79             :         } while (--i > 0);               \
      80             : } while (0)
      81             : 
      82             : #define SWAPINIT(a, es) swaptype = ((char *)(a) - (char *)0) % sizeof(long) || \
      83             :     (es) % sizeof(long) ? 2 : (es) == sizeof(long)? 0 : 1;
      84             : 
      85             : static void
      86    49233282 : swapfunc(char *a, char *b, size_t n, int swaptype)
      87             : {
      88    49233282 :     if (swaptype <= 1)
      89     4136458 :         swapcode(long, a, b, n);
      90             :     else
      91    45096824 :         swapcode(char, a, b, n);
      92    49233282 : }
      93             : 
      94             : #define swap(a, b)                      \
      95             :     if (swaptype == 0) {                    \
      96             :         long t = *(long *)(void *)(a);          \
      97             :         *(long *)(void *)(a) = *(long *)(void *)(b);    \
      98             :         *(long *)(void *)(b) = t;           \
      99             :     } else                          \
     100             :         swapfunc(a, b, es, swaptype)
     101             : 
     102             : #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
     103             : 
     104             : static char *
     105    10733858 : med3(char *a, char *b, char *c, int (*cmp) (const void *, const void *))
     106             : {
     107    10733858 :     return cmp(a, b) < 0 ?
     108     5216542 :         (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a))
     109    15950400 :         : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c));
     110             : }
     111             : 
     112             : void
     113    13938878 : pg_qsort(void *a, size_t n, size_t es, int (*cmp) (const void *, const void *))
     114             : {
     115             :     char       *pa,
     116             :                *pb,
     117             :                *pc,
     118             :                *pd,
     119             :                *pl,
     120             :                *pm,
     121             :                *pn;
     122             :     size_t      d1,
     123             :                 d2;
     124             :     int         r,
     125             :                 swaptype,
     126             :                 presorted;
     127             : 
     128    13938878 : loop:SWAPINIT(a, es);
     129    13938878 :     if (n < 7)
     130             :     {
     131    18732882 :         for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
     132    42086646 :             for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
     133    14660230 :                  pl -= es)
     134    14660230 :                 swap(pl, pl - es);
     135     5019674 :         return;
     136             :     }
     137     8919204 :     presorted = 1;
     138    66016148 :     for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
     139             :     {
     140    65739088 :         if (cmp(pm - es, pm) > 0)
     141             :         {
     142     8642144 :             presorted = 0;
     143     8642144 :             break;
     144             :         }
     145             :     }
     146     8919204 :     if (presorted)
     147      277060 :         return;
     148     8642144 :     pm = (char *) a + (n / 2) * es;
     149     8642144 :     if (n > 7)
     150             :     {
     151     7867136 :         pl = (char *) a;
     152     7867136 :         pn = (char *) a + (n - 1) * es;
     153     7867136 :         if (n > 40)
     154             :         {
     155      955574 :             size_t      d = (n / 8) * es;
     156             : 
     157      955574 :             pl = med3(pl, pl + d, pl + 2 * d, cmp);
     158      955574 :             pm = med3(pm - d, pm, pm + d, cmp);
     159      955574 :             pn = med3(pn - 2 * d, pn - d, pn, cmp);
     160             :         }
     161     7867136 :         pm = med3(pl, pm, pn, cmp);
     162             :     }
     163     8642144 :     swap(a, pm);
     164     8642144 :     pa = pb = (char *) a + es;
     165     8642144 :     pc = pd = (char *) a + (n - 1) * es;
     166             :     for (;;)
     167             :     {
     168   206633892 :         while (pb <= pc && (r = cmp(pb, a)) <= 0)
     169             :         {
     170   111451250 :             if (r == 0)
     171             :             {
     172      910838 :                 swap(pa, pb);
     173      910838 :                 pa += es;
     174             :             }
     175   111451250 :             pb += es;
     176             :         }
     177   143787132 :         while (pb <= pc && (r = cmp(pc, a)) >= 0)
     178             :         {
     179    74570608 :             if (r == 0)
     180             :             {
     181      793438 :                 swap(pc, pd);
     182      793438 :                 pd -= es;
     183             :             }
     184    74570608 :             pc -= es;
     185             :         }
     186    34608262 :         if (pb > pc)
     187     8642144 :             break;
     188    25966118 :         swap(pb, pc);
     189    25966118 :         pb += es;
     190    25966118 :         pc -= es;
     191             :     }
     192     8642144 :     pn = (char *) a + n * es;
     193     8642144 :     d1 = Min(pa - (char *) a, pb - pa);
     194     8642144 :     vecswap(a, pb - d1, d1);
     195     8642144 :     d1 = Min(pd - pc, pn - pd - es);
     196     8642144 :     vecswap(pb, pn - d1, d1);
     197     8642144 :     d1 = pb - pa;
     198     8642144 :     d2 = pd - pc;
     199     8642144 :     if (d1 <= d2)
     200             :     {
     201             :         /* Recurse on left partition, then iterate on right partition */
     202     3553428 :         if (d1 > es)
     203     2446632 :             pg_qsort(a, d1 / es, es, cmp);
     204     3553428 :         if (d2 > es)
     205             :         {
     206             :             /* Iterate rather than recurse to save stack space */
     207             :             /* pg_qsort(pn - d2, d2 / es, es, cmp); */
     208     3552742 :             a = pn - d2;
     209     3552742 :             n = d2 / es;
     210     3552742 :             goto loop;
     211             :         }
     212             :     }
     213             :     else
     214             :     {
     215             :         /* Recurse on right partition, then iterate on left partition */
     216     5088716 :         if (d2 > es)
     217     1952718 :             pg_qsort(pn - d2, d2 / es, es, cmp);
     218     5088716 :         if (d1 > es)
     219             :         {
     220             :             /* Iterate rather than recurse to save stack space */
     221             :             /* pg_qsort(a, d1 / es, es, cmp); */
     222     5086648 :             n = d1 / es;
     223     5086648 :             goto loop;
     224             :         }
     225             :     }
     226             : }
     227             : 
     228             : /*
     229             :  * qsort comparator wrapper for strcmp.
     230             :  */
     231             : int
     232       62376 : pg_qsort_strcmp(const void *a, const void *b)
     233             : {
     234       62376 :     return strcmp(*(const char *const *) a, *(const char *const *) b);
     235             : }

Generated by: LCOV version 1.13