lib/mpsort.c

   1 /* Sort a vector of pointers to data.
   2
   3    Copyright (C) 2007, 2009-2019 Free Software Foundation, Inc.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 /* Written by Paul Eggert.  */
  19
  20 #include <config.h>
  21
  22 #include "mpsort.h"
  23
  24 #include <string.h>
  25
  26 /* The type of qsort-style comparison functions.  */
  27
  28 typedef int (*comparison_function) (void const *, void const *);
  29
  30 static void mpsort_with_tmp (void const **restrict, size_t,
  31                              void const **restrict, comparison_function);
  32
  33 /* Sort a vector BASE containing N pointers, placing the sorted array
  34    into TMP.  Compare pointers with CMP.  N must be at least 2.  */
  35
  36 static void
  37 mpsort_into_tmp (void const **restrict base, size_t n,
  38                  void const **restrict tmp,
  39                  comparison_function cmp)
  40 {
  41   size_t n1 = n / 2;
  42   size_t n2 = n - n1;
  43   size_t a = 0;
  44   size_t alim = n1;
  45   size_t b = n1;
  46   size_t blim = n;
  47   void const *ba;
  48   void const *bb;
  49
  50   mpsort_with_tmp (base + n1, n2, tmp, cmp);
  51   mpsort_with_tmp (base, n1, tmp, cmp);
  52
  53   ba = base[a];
  54   bb = base[b];
  55
  56   for (;;)
  57     if (cmp (ba, bb) <= 0)
  58       {
  59         *tmp++ = ba;
  60         a++;
  61         if (a == alim)
  62           {
  63             a = b;
  64             alim = blim;
  65             break;
  66           }
  67         ba = base[a];
  68       }
  69     else
  70       {
  71         *tmp++ = bb;
  72         b++;
  73         if (b == blim)
  74           break;
  75         bb = base[b];
  76       }
  77
  78   memcpy (tmp, base + a, (alim - a) * sizeof *base);
  79 }
  80
  81 /* Sort a vector BASE containing N pointers, in place.  Use TMP
  82    (containing N / 2 pointers) for temporary storage.  Compare
  83    pointers with CMP.  */
  84
  85 static void
  86 mpsort_with_tmp (void const **restrict base, size_t n,
  87                  void const **restrict tmp,
  88                  comparison_function cmp)
  89 {
  90   if (n <= 2)
  91     {
  92       if (n == 2)
  93         {
  94           void const *p0 = base[0];
  95           void const *p1 = base[1];
  96           if (! (cmp (p0, p1) <= 0))
  97             {
  98               base[0] = p1;
  99               base[1] = p0;
 100             }
 101         }
 102     }
 103   else
 104     {
 105       size_t n1 = n / 2;
 106       size_t n2 = n - n1;
 107       size_t i;
 108       size_t t = 0;
 109       size_t tlim = n1;
 110       size_t b = n1;
 111       size_t blim = n;
 112       void const *bb;
 113       void const *tt;
 114
 115       mpsort_with_tmp (base + n1, n2, tmp, cmp);
 116
 117       if (n1 < 2)
 118         tmp[0] = base[0];
 119       else
 120         mpsort_into_tmp (base, n1, tmp, cmp);
 121
 122       tt = tmp[t];
 123       bb = base[b];
 124
 125       for (i = 0; ; )
 126         if (cmp (tt, bb) <= 0)
 127           {
 128             base[i++] = tt;
 129             t++;
 130             if (t == tlim)
 131               break;
 132             tt = tmp[t];
 133           }
 134         else
 135           {
 136             base[i++] = bb;
 137             b++;
 138             if (b == blim)
 139               {
 140                 memcpy (base + i, tmp + t, (tlim - t) * sizeof *base);
 141                 break;
 142               }
 143             bb = base[b];
 144           }
 145     }
 146 }
 147
 148 /* Sort a vector BASE containing N pointers, in place.  BASE must
 149    contain enough storage to hold N + N / 2 vectors; the trailing
 150    vectors are used for temporaries.  Compare pointers with CMP.  */
 151
 152 void
 153 mpsort (void const **base, size_t n, comparison_function cmp)
 154 {
 155   mpsort_with_tmp (base, n, base + n, cmp);
 156 }