lib/mpsort.c

   1 /* Sort a vector of pointers to data.
   2
   3    Copyright (C) 2007 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 2, or (at your option)
   8    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 along
  16    with this program; if not, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 /* Written by Paul Eggert.  */
  20
  21 #include <config.h>
  22
  23 #include "mpsort.h"
  24
  25 #include <string.h>
  26
  27 /* The type of qsort-style comparison functions.  */
  28
  29 typedef int (*comparison_function) (void const *, void const *);
  30
  31 static void mpsort_with_tmp (void const **restrict, size_t,
  32                              void const **restrict, comparison_function);
  33
  34 /* Sort a vector BASE containing N pointers, placing the sorted array
  35    into TMP.  Compare pointers with CMP.  N must be at least 2.  */
  36
  37 static void
  38 mpsort_into_tmp (void const **restrict base, size_t n,
  39                  void const **restrict tmp,
  40                  comparison_function cmp)
  41 {
  42   size_t n1 = n / 2;
  43   size_t n2 = n - n1;
  44   size_t a = 0;
  45   size_t alim = n1;
  46   size_t b = n1;
  47   size_t blim = n;
  48   void const *ba;
  49   void const *bb;
  50
  51   mpsort_with_tmp (base + n1, n2, tmp, cmp);
  52   mpsort_with_tmp (base, n1, tmp, cmp);
  53
  54   ba = base[a];
  55   bb = base[b];
  56
  57   for (;;)
  58     if (cmp (ba, bb) <= 0)
  59       {
  60         *tmp++ = ba;
  61         a++;
  62         if (a == alim)
  63           {
  64             a = b;
  65             alim = blim;
  66             break;
  67           }
  68         ba = base[a];
  69       }
  70     else
  71       {
  72         *tmp++ = bb;
  73         b++;
  74         if (b == blim)
  75           break;
  76         bb = base[b];
  77       }
  78
  79   memcpy (tmp, base + a, (alim - a) * sizeof *base);
  80 }
  81
  82 /* Sort a vector BASE containing N pointers, in place.  Use TMP
  83    (containing N / 2 pointers) for temporary storage.  Compare
  84    pointers with CMP.  */
  85
  86 static void
  87 mpsort_with_tmp (void const **restrict base, size_t n,
  88                  void const **restrict tmp,
  89                  comparison_function cmp)
  90 {
  91   if (n <= 2)
  92     {
  93       if (n == 2)
  94         {
  95           void const *p0 = base[0];
  96           void const *p1 = base[1];
  97           if (! (cmp (p0, p1) <= 0))
  98             {
  99               base[0] = p1;
 100               base[1] = p0;
 101             }
 102         }
 103     }
 104   else
 105     {
 106       size_t n1 = n / 2;
 107       size_t n2 = n - n1;
 108       size_t i;
 109       size_t t = 0;
 110       size_t tlim = n1;
 111       size_t b = n1;
 112       size_t blim = n;
 113       void const *bb;
 114       void const *tt;
 115
 116       mpsort_with_tmp (base + n1, n2, tmp, cmp);
 117
 118       if (n1 < 2)
 119         tmp[0] = base[0];
 120       else
 121         mpsort_into_tmp (base, n1, tmp, cmp);
 122
 123       tt = tmp[t];
 124       bb = base[b];
 125
 126       for (i = 0; ; )
 127         if (cmp (tt, bb) <= 0)
 128           {
 129             base[i++] = tt;
 130             t++;
 131             if (t == tlim)
 132               break;
 133             tt = tmp[t];
 134           }
 135         else
 136           {
 137             base[i++] = bb;
 138             b++;
 139             if (b == blim)
 140               {
 141                 memcpy (base + i, tmp + t, (tlim - t) * sizeof *base);
 142                 break;
 143               }
 144             bb = base[b];
 145           }
 146     }
 147 }
 148
 149 /* Sort a vector BASE containing N pointers, in place.  BASE must
 150    contain enough storage to hold N + N / 2 vectors; the trailing
 151    vectors are used for temporaries.  Compare pointers with CMP.  */
 152
 153 void
 154 mpsort (void const **base, size_t n, comparison_function cmp)
 155 {
 156   mpsort_with_tmp (base, n, base + n, cmp);
 157 }