1/* Sort a vector of pointers to data.
2
3   Copyright (C) 2007, 2009, 2010 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 <http://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
28typedef int (*comparison_function) (void const *, void const *);
29
30static 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
36static void
37mpsort_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
85static void
86mpsort_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
152void
153mpsort (void const **base, size_t n, comparison_function cmp)
154{
155  mpsort_with_tmp (base, n, base + n, cmp);
156}
157