LCOV - code coverage report
Current view: top level - gdk - gdk_qsort_impl.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 50 50 100.0 %
Date: 2021-09-14 19:48:19 Functions: 23 36 63.9 %

          Line data    Source code
       1             : /*
       2             :  * This Source Code Form is subject to the terms of the Mozilla Public
       3             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       4             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       5             :  *
       6             :  * Copyright 1997 - July 2008 CWI, August 2008 - 2021 MonetDB B.V.
       7             :  */
       8             : 
       9             : /* This file is included multiple times.  We expect the tokens SWAP,
      10             :  * GDKqsort_impl, LE, LT, and EQ to be redefined each time. */
      11             : 
      12             : /* This is an implementation of quicksort with a number of extra
      13             :  * tweaks and optimizations.  This function is an adaptation to fit
      14             :  * into the MonetDB mould from the original version by Bentley &
      15             :  * McIlroy from "Engineering a Sort Function".  Hence the following
      16             :  * copyright notice.  Comments in the code are mine (Sjoerd
      17             :  * Mullender). */
      18             : 
      19             : /*
      20             :  * Copyright (c) 1992, 1993
      21             :  *      The Regents of the University of California.  All rights reserved.
      22             :  *
      23             :  * Redistribution and use in source and binary forms, with or without
      24             :  * modification, are permitted provided that the following conditions
      25             :  * are met:
      26             :  * 1. Redistributions of source code must retain the above copyright
      27             :  *    notice, this list of conditions and the following disclaimer.
      28             :  * 2. Redistributions in binary form must reproduce the above copyright
      29             :  *    notice, this list of conditions and the following disclaimer in the
      30             :  *    documentation and/or other materials provided with the distribution.
      31             :  * 3. All advertising materials mentioning features or use of this software
      32             :  *    must display the following acknowledgement:
      33             :  *      This product includes software developed by the University of
      34             :  *      California, Berkeley and its contributors.
      35             :  * 4. Neither the name of the University nor the names of its contributors
      36             :  *    may be used to endorse or promote products derived from this software
      37             :  *    without specific prior written permission.
      38             :  *
      39             :  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
      40             :  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
      41             :  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
      42             :  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
      43             :  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
      44             :  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
      45             :  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
      46             :  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
      47             :  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
      48             :  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
      49             :  * SUCH DAMAGE.
      50             :  */
      51             : 
      52             : /* when to switch to insertion sort */
      53             : #ifndef INSERTSORT
      54             : #define INSERTSORT     60      /* the original algorithm used 7 */
      55             : #endif
      56             : 
      57             : static void
      58     4213408 : CONCAT3(GDKqsort_impl_, TPE, SUFF)(const struct qsort_t *restrict buf,
      59             :                                   char *restrict h, char *restrict t, size_t n)
      60             : {
      61             :         size_t a, b, c, d;
      62             :         size_t r;
      63             :         bool swap_cnt;
      64             : #ifdef INITIALIZER
      65             :         INITIALIZER;
      66             : #endif
      67             : 
      68             :   loop:
      69     5286982 :         if (n < INSERTSORT) {
      70             :                 /* insertion sort for very small chunks */
      71    57587938 :                 for (b = 1; b < n; b++) {
      72   444710883 :                         for (a = b; a > 0 && LT(a, a - 1, TPE, SUFF); a--) {
      73  3516512121 :                                 SWAP(a, a - 1, TPE);
      74             :                         }
      75             :                 }
      76             :                 return;
      77             :         }
      78             : 
      79             :         /* determine pivot */
      80     1101450 :         b = n >> 1;               /* small arrays: middle element */
      81             : #if INSERTSORT <= 7
      82             :         if (n > 7)
      83             : #endif
      84             :         {
      85             :                 /* for larger arrays, take the middle value from the
      86             :                  * first, middle, and last */
      87             :                 a = 0;
      88     1101450 :                 c = n - 1;
      89             : #if INSERTSORT <= 40
      90             :                 if (n > 40)
      91             : #endif
      92             :                 {
      93             :                         /* for even larger arrays, take the middle
      94             :                          * value of three middle values */
      95     1101450 :                         d = n >> 3;
      96     1101450 :                         a = MED3(a, a + d, a + 2 * d, TPE, SUFF);
      97     1101451 :                         b = MED3(b - d, b, b + d, TPE, SUFF);
      98     1101451 :                         c = MED3(c - 2 * d, c - d, c, TPE, SUFF);
      99             :                 }
     100     1101450 :                 b = MED3(a, b, c, TPE, SUFF);
     101             :         }
     102             :         /* move pivot to start */
     103     1101451 :         if (b != 0)
     104     9064255 :                 SWAP(0, b, TPE);
     105             : 
     106             :         /* Bentley and McIlroy's implementation of Dijkstra's Dutch
     107             :          * National Flag Problem */
     108             :         a = b = 1;
     109             :         c = d = n - 1;
     110             :         swap_cnt = false;
     111             :         for (;;) {
     112             :                 /* loop invariant:
     113             :                  * [0..a): values equal to pivot (cannot be empty)
     114             :                  * [a..b): values less than pivot (can be empty)
     115             :                  * [c+1..d+1): values greater than pivot (can be empty)
     116             :                  * [d+1..n): values equal to pivot (can be empty)
     117             :                  */
     118   363993767 :                 while (b <= c && LE(b, 0, TPE, SUFF)) {
     119   236840614 :                         if (EQ(b, 0, TPE)) {
     120             :                                 swap_cnt = true;
     121   166653044 :                                 SWAP(a, b, TPE);
     122    18371294 :                                 a++;
     123             :                         }
     124   236839602 :                         b++;
     125             :                 }
     126   341538151 :                 while (b <= c && LE(0, c, TPE, SUFF)) {
     127   214385238 :                         if (EQ(0, c, TPE)) {
     128             :                                 swap_cnt = true;
     129    33328501 :                                 SWAP(c, d, TPE);
     130     3650873 :                                 d--;
     131             :                         }
     132   214384241 :                         c--;
     133             :                 }
     134   127154165 :                 if (b > c)
     135             :                         break;
     136  1134431815 :                 SWAP(b, c, TPE);
     137             :                 swap_cnt = true;
     138   126052714 :                 b++;
     139   126052714 :                 c--;
     140             :         }
     141             :         /* in addition to the loop invariant we have:
     142             :          * b == c + 1
     143             :          * i.e., there are b-a values less than the pivot and d-c
     144             :          * values greater than the pivot
     145             :          */
     146             : 
     147     1101451 :         if (!swap_cnt && n < 1024) {
     148             :                 /* switch to insertion sort, but only for small chunks */
     149      637251 :                 for (b = 1; b < n; b++) {
     150     1440329 :                         for (a = b; a > 0 && LT(a, a - 1, TPE, SUFF); a--) {
     151     7272256 :                                 SWAP(a, a - 1, TPE);
     152             :                         }
     153             :                 }
     154             :                 return;
     155             :         }
     156             : 
     157             :         /* move initial values equal to the pivot to the middle */
     158     1096285 :         r = MIN(a, b - a);
     159   129541789 :         multi_SWAP(0, b - r, r);
     160             :         /* move final values equal to the pivot to the middle */
     161     1096285 :         r = MIN(d - c, n - d - 1);
     162    40517502 :         multi_SWAP(b, n - r, r);
     163             :         /* at this point we have:
     164             :          * b == c + 1
     165             :          * [0..b-a): values less than pivot (to be sorted)
     166             :          * [b-a..n-(d-c)): values equal to pivot (in place)
     167             :          * [n-(d-c)..n): values larger than pivot (to be sorted)
     168             :          */
     169             : 
     170             :         /* use recursion for smaller of the two subarrays, loop back
     171             :          * to start for larger of the two */
     172     1096285 :         if (b - a < d - c) {
     173      492284 :                 if ((r = b - a) > 1) {
     174             :                         /* sort values less than pivot */
     175      479473 :                         CONCAT3(GDKqsort_impl_, TPE, SUFF)(buf, h, t, r);
     176             :                 }
     177      492283 :                 if ((r = d - c) > 1) {
     178             :                         /* sort values greater than pivot
     179             :                          * iterate rather than recurse */
     180      491019 :                         h += (n - r) * buf->hs;
     181      491019 :                         if (t && buf->ts)
     182      489467 :                                 t += (n - r) * buf->ts;
     183             :                         n = r;
     184      491019 :                         goto loop;
     185             :                 }
     186             :         } else {
     187      604001 :                 if ((r = d - c) > 1) {
     188             :                         /* sort values greater than pivot */
     189      572721 :                         CONCAT3(GDKqsort_impl_, TPE, SUFF)(
     190      572721 :                                 buf, h + (n - r) * buf->hs,
     191      571227 :                                 t ? t + (n - r) * buf->ts : NULL, r);
     192             :                 }
     193      604003 :                 if ((r = b - a) > 1) {
     194             :                         /* sort values less than pivot
     195             :                          * iterate rather than recurse */
     196             :                         n = r;
     197      582555 :                         goto loop;
     198             :                 }
     199             :         }
     200             : }

Generated by: LCOV version 1.14