Coverage Report

Created: 2025-01-28 06:58

/src/gnutls/lib/unistring/array-mergesort.h
Line
Count
Source (jump to first uncovered line)
1
/* Stable-sorting of an array using mergesort.
2
   Copyright (C) 2009-2025 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
37.1k
{
194
37.1k
  switch (n)
195
37.1k
    {
196
0
    case 0:
197
0
    case 1:
198
      /* Nothing to do.  */
199
0
      return;
200
21.7k
    case 2:
201
      /* Trivial case.  */
202
21.7k
      if (COMPARE (&src[0], &src[1]) <= 0)
203
21.3k
        {
204
          /* src[0] <= src[1] */
205
21.3k
        }
206
465
      else
207
465
        {
208
465
          ELEMENT t = src[0];
209
465
          src[0] = src[1];
210
465
          src[1] = t;
211
465
        }
212
21.7k
      break;
213
5.43k
    case 3:
214
      /* Simple case.  */
215
5.43k
      if (COMPARE (&src[0], &src[1]) <= 0)
216
3.94k
        {
217
3.94k
          if (COMPARE (&src[1], &src[2]) <= 0)
218
3.40k
            {
219
              /* src[0] <= src[1] <= src[2] */
220
3.40k
            }
221
545
          else if (COMPARE (&src[0], &src[2]) <= 0)
222
265
            {
223
              /* src[0] <= src[2] < src[1] */
224
265
              ELEMENT t = src[1];
225
265
              src[1] = src[2];
226
265
              src[2] = t;
227
265
            }
228
280
          else
229
280
            {
230
              /* src[2] < src[0] <= src[1] */
231
280
              ELEMENT t = src[0];
232
280
              src[0] = src[2];
233
280
              src[2] = src[1];
234
280
              src[1] = t;
235
280
            }
236
3.94k
        }
237
1.48k
      else
238
1.48k
        {
239
1.48k
          if (COMPARE (&src[0], &src[2]) <= 0)
240
709
            {
241
              /* src[1] < src[0] <= src[2] */
242
709
              ELEMENT t = src[0];
243
709
              src[0] = src[1];
244
709
              src[1] = t;
245
709
            }
246
778
          else if (COMPARE (&src[1], &src[2]) <= 0)
247
528
            {
248
              /* src[1] <= src[2] < src[0] */
249
528
              ELEMENT t = src[0];
250
528
              src[0] = src[1];
251
528
              src[1] = src[2];
252
528
              src[2] = t;
253
528
            }
254
250
          else
255
250
            {
256
              /* src[2] < src[1] < src[0] */
257
250
              ELEMENT t = src[0];
258
250
              src[0] = src[2];
259
250
              src[2] = t;
260
250
            }
261
1.48k
        }
262
5.43k
      break;
263
9.88k
    default:
264
9.88k
      {
265
9.88k
        size_t n1 = n / 2;
266
9.88k
        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
9.88k
        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
9.88k
        merge_sort_fromto (src, tmp, n1, tmp + n1);
272
        /* Merge the two half results.  */
273
9.88k
        merge (tmp, n1, src + n1, n2, src);
274
9.88k
      }
275
9.88k
      break;
276
37.1k
    }
277
37.1k
}
278
279
#undef ELEMENT
280
#undef COMPARE
281
#undef STATIC