Coverage Report

Created: 2025-01-28 06:58

/src/libunistring/lib/array-mergesort.h
Line
Count
Source (jump to first uncovered line)
1
/* Stable-sorting of an array using mergesort.
2
   Copyright (C) 2009-2024 Free Software Foundation, Inc.
3
   Written by Bruno Haible <bruno@clisp.org>, 2009.
4
5
   This file is free software: you can redistribute it and/or modify
6
   it under the terms of the GNU Lesser General Public License as
7
   published by the Free Software Foundation; either version 2.1 of the
8
   License, or (at your option) any later version.
9
10
   This file 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 Lesser General Public License for more details.
14
15
   You should have received a copy of the GNU Lesser General Public License
16
   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
17
18
/* This file implements stable sorting of an array, using the mergesort
19
   algorithm.
20
   Worst-case running time for an array of length N is O(N log N).
21
   Unlike the mpsort module, the algorithm here attempts to minimize not
22
   only the number of comparisons, but also the number of copying operations.
23
24
   Before including this file, you need to define
25
     ELEMENT      The type of every array element.
26
     COMPARE      A two-argument macro that takes two 'const ELEMENT *'
27
                  pointers and returns a negative, zero, or positive 'int'
28
                  value if the element pointed to by the first argument is,
29
                  respectively, less, equal, or greater than the element
30
                  pointed to by the second argument.
31
     STATIC       The storage class of the functions being defined.
32
     STATIC_FROMTO  (Optional.) Overrides STATIC for the 'merge_sort_fromto'
33
                    function.
34
   Before including this file, you also need to include:
35
     #include <stddef.h>
36
 */
37
38
/* Merge the sorted arrays src1[0..n1-1] and src2[0..n2-1] into
39
   dst[0..n1+n2-1].  In case of ambiguity, put the elements of src1
40
   before the elements of src2.
41
   n1 and n2 must be > 0.
42
   The arrays src1 and src2 must not overlap the dst array, except that
43
   src1 may be dst[n2..n1+n2-1], or src2 may be dst[n1..n1+n2-1].  */
44
static void
45
merge (const ELEMENT *src1, size_t n1,
46
       const ELEMENT *src2, size_t n2,
47
       ELEMENT *dst)
48
77.9k
{
49
77.9k
  for (;;) /* while (n1 > 0 && n2 > 0) */
50
459k
    {
51
459k
      if (COMPARE (src1, src2) <= 0)
52
399k
        {
53
399k
          *dst++ = *src1++;
54
399k
          n1--;
55
399k
          if (n1 == 0)
56
74.1k
            break;
57
399k
        }
58
60.3k
      else
59
60.3k
        {
60
60.3k
          *dst++ = *src2++;
61
60.3k
          n2--;
62
60.3k
          if (n2 == 0)
63
3.83k
            break;
64
60.3k
        }
65
459k
    }
66
  /* Here n1 == 0 || n2 == 0 but also n1 > 0 || n2 > 0.  */
67
77.9k
  if (n1 > 0)
68
3.83k
    {
69
3.83k
      if (dst != src1)
70
3.83k
        do
71
6.25k
          {
72
6.25k
            *dst++ = *src1++;
73
6.25k
            n1--;
74
6.25k
          }
75
6.25k
        while (n1 > 0);
76
3.83k
    }
77
74.1k
  else /* n2 > 0 */
78
74.1k
    {
79
74.1k
      if (dst != src2)
80
0
        do
81
0
          {
82
0
            *dst++ = *src2++;
83
0
            n2--;
84
0
          }
85
0
        while (n2 > 0);
86
74.1k
    }
87
77.9k
}
88
89
/* Sort src[0..n-1] into dst[0..n-1], using tmp[0..n/2-1] as temporary
90
   (scratch) storage.
91
   The arrays src, dst, tmp must not overlap.  */
92
#ifdef STATIC_FROMTO
93
STATIC_FROMTO
94
#else
95
STATIC
96
#endif
97
void
98
merge_sort_fromto (const ELEMENT *src, ELEMENT *dst, size_t n, ELEMENT *tmp)
99
134k
{
100
134k
  switch (n)
101
134k
    {
102
0
    case 0:
103
0
      return;
104
0
    case 1:
105
      /* Nothing to do.  */
106
0
      dst[0] = src[0];
107
0
      return;
108
67.1k
    case 2:
109
      /* Trivial case.  */
110
67.1k
      if (COMPARE (&src[0], &src[1]) <= 0)
111
63.3k
        {
112
          /* src[0] <= src[1] */
113
63.3k
          dst[0] = src[0];
114
63.3k
          dst[1] = src[1];
115
63.3k
        }
116
3.84k
      else
117
3.84k
        {
118
3.84k
          dst[0] = src[1];
119
3.84k
          dst[1] = src[0];
120
3.84k
        }
121
67.1k
      break;
122
10.8k
    case 3:
123
      /* Simple case.  */
124
10.8k
      if (COMPARE (&src[0], &src[1]) <= 0)
125
8.27k
        {
126
8.27k
          if (COMPARE (&src[1], &src[2]) <= 0)
127
6.00k
            {
128
              /* src[0] <= src[1] <= src[2] */
129
6.00k
              dst[0] = src[0];
130
6.00k
              dst[1] = src[1];
131
6.00k
              dst[2] = src[2];
132
6.00k
            }
133
2.27k
          else if (COMPARE (&src[0], &src[2]) <= 0)
134
1.42k
            {
135
              /* src[0] <= src[2] < src[1] */
136
1.42k
              dst[0] = src[0];
137
1.42k
              dst[1] = src[2];
138
1.42k
              dst[2] = src[1];
139
1.42k
            }
140
848
          else
141
848
            {
142
              /* src[2] < src[0] <= src[1] */
143
848
              dst[0] = src[2];
144
848
              dst[1] = src[0];
145
848
              dst[2] = src[1];
146
848
            }
147
8.27k
        }
148
2.52k
      else
149
2.52k
        {
150
2.52k
          if (COMPARE (&src[0], &src[2]) <= 0)
151
1.00k
            {
152
              /* src[1] < src[0] <= src[2] */
153
1.00k
              dst[0] = src[1];
154
1.00k
              dst[1] = src[0];
155
1.00k
              dst[2] = src[2];
156
1.00k
            }
157
1.52k
          else if (COMPARE (&src[1], &src[2]) <= 0)
158
809
            {
159
              /* src[1] <= src[2] < src[0] */
160
809
              dst[0] = src[1];
161
809
              dst[1] = src[2];
162
809
              dst[2] = src[0];
163
809
            }
164
716
          else
165
716
            {
166
              /* src[2] < src[1] < src[0] */
167
716
              dst[0] = src[2];
168
716
              dst[1] = src[1];
169
716
              dst[2] = src[0];
170
716
            }
171
2.52k
        }
172
10.8k
      break;
173
56.6k
    default:
174
56.6k
      {
175
56.6k
        size_t n1 = n / 2;
176
56.6k
        size_t n2 = (n + 1) / 2;
177
        /* Note: n1 + n2 = n, n1 <= n2.  */
178
        /* Sort src[n1..n-1] into dst[n1..n-1], scratching tmp[0..n2/2-1].  */
179
56.6k
        merge_sort_fromto (src + n1, dst + n1, n2, tmp);
180
        /* Sort src[0..n1-1] into tmp[0..n1-1], scratching dst[0..n1-1].  */
181
56.6k
        merge_sort_fromto (src, tmp, n1, dst);
182
        /* Merge the two half results.  */
183
56.6k
        merge (tmp, n1, dst + n1, n2, dst);
184
56.6k
      }
185
56.6k
      break;
186
134k
    }
187
134k
}
188
189
/* Sort src[0..n-1], using tmp[0..n-1] as temporary (scratch) storage.
190
   The arrays src, tmp must not overlap. */
191
STATIC void
192
merge_sort_inplace (ELEMENT *src, size_t n, ELEMENT *tmp)
193
93.0k
{
194
93.0k
  switch (n)
195
93.0k
    {
196
0
    case 0:
197
0
    case 1:
198
      /* Nothing to do.  */
199
0
      return;
200
74.4k
    case 2:
201
      /* Trivial case.  */
202
74.4k
      if (COMPARE (&src[0], &src[1]) <= 0)
203
73.6k
        {
204
          /* src[0] <= src[1] */
205
73.6k
        }
206
773
      else
207
773
        {
208
773
          ELEMENT t = src[0];
209
773
          src[0] = src[1];
210
773
          src[1] = t;
211
773
        }
212
74.4k
      break;
213
7.20k
    case 3:
214
      /* Simple case.  */
215
7.20k
      if (COMPARE (&src[0], &src[1]) <= 0)
216
5.08k
        {
217
5.08k
          if (COMPARE (&src[1], &src[2]) <= 0)
218
3.90k
            {
219
              /* src[0] <= src[1] <= src[2] */
220
3.90k
            }
221
1.18k
          else if (COMPARE (&src[0], &src[2]) <= 0)
222
660
            {
223
              /* src[0] <= src[2] < src[1] */
224
660
              ELEMENT t = src[1];
225
660
              src[1] = src[2];
226
660
              src[2] = t;
227
660
            }
228
526
          else
229
526
            {
230
              /* src[2] < src[0] <= src[1] */
231
526
              ELEMENT t = src[0];
232
526
              src[0] = src[2];
233
526
              src[2] = src[1];
234
526
              src[1] = t;
235
526
            }
236
5.08k
        }
237
2.11k
      else
238
2.11k
        {
239
2.11k
          if (COMPARE (&src[0], &src[2]) <= 0)
240
894
            {
241
              /* src[1] < src[0] <= src[2] */
242
894
              ELEMENT t = src[0];
243
894
              src[0] = src[1];
244
894
              src[1] = t;
245
894
            }
246
1.22k
          else if (COMPARE (&src[1], &src[2]) <= 0)
247
791
            {
248
              /* src[1] <= src[2] < src[0] */
249
791
              ELEMENT t = src[0];
250
791
              src[0] = src[1];
251
791
              src[1] = src[2];
252
791
              src[2] = t;
253
791
            }
254
433
          else
255
433
            {
256
              /* src[2] < src[1] < src[0] */
257
433
              ELEMENT t = src[0];
258
433
              src[0] = src[2];
259
433
              src[2] = t;
260
433
            }
261
2.11k
        }
262
7.20k
      break;
263
11.3k
    default:
264
11.3k
      {
265
11.3k
        size_t n1 = n / 2;
266
11.3k
        size_t n2 = (n + 1) / 2;
267
        /* Note: n1 + n2 = n, n1 <= n2.  */
268
        /* Sort src[n1..n-1], scratching tmp[0..n2-1].  */
269
11.3k
        merge_sort_inplace (src + n1, n2, tmp);
270
        /* Sort src[0..n1-1] into tmp[0..n1-1], scratching tmp[n1..2*n1-1].  */
271
11.3k
        merge_sort_fromto (src, tmp, n1, tmp + n1);
272
        /* Merge the two half results.  */
273
11.3k
        merge (tmp, n1, src + n1, n2, src);
274
11.3k
      }
275
11.3k
      break;
276
93.0k
    }
277
93.0k
}
278
279
#undef ELEMENT
280
#undef COMPARE
281
#undef STATIC