1 /* Test of stable-sorting of an array using mergesort.
2 Copyright (C) 2009-2023 Free Software Foundation, Inc.
3
4 This program is free software: you can redistribute it and/or modify it
5 under the terms of the GNU Lesser General Public License as published
6 by the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General Public License
15 along with this program. If not, see <https://www.gnu.org/licenses/>. */
16
17 #include <config.h>
18
19 #include <stddef.h>
20
21 struct foo { double x; double index; };
22 #define ELEMENT struct foo
23 #define COMPARE(a,b) ((a)->x < (b)->x ? -1 : (a)->x > (b)->x ? 1 : 0)
24 #define STATIC static
25 #include "array-mergesort.h"
26
27 #include <stdlib.h>
28
29 #include "macros.h"
30
31 #define NMAX 257
32 static const struct foo data[NMAX] =
33 {
34 { 2, 0 },
35 { 28, 1 },
36 { 36, 2 },
37 { 43, 3 },
38 { 20, 4 },
39 { 37, 5 },
40 { 19, 6 },
41 { 37, 7 },
42 { 30, 8 },
43 { 18, 9 },
44 { 30, 10 },
45 { 49, 11 },
46 { 16, 12 },
47 { 22, 13 },
48 { 23, 14 },
49 { 3, 15 },
50 { 39, 16 },
51 { 48, 17 },
52 { 18, 18 },
53 { 18, 19 },
54 { 45, 20 },
55 { 39, 21 },
56 { 1, 22 },
57 { 44, 23 },
58 { 24, 24 },
59 { 21, 25 },
60 { 29, 26 },
61 { 3, 27 },
62 { 34, 28 },
63 { 15, 29 },
64 { 39, 30 },
65 { 11, 31 },
66 { 29, 32 },
67 { 27, 33 },
68 { 43, 34 },
69 { 31, 35 },
70 { 28, 36 },
71 { 12, 37 },
72 { 16, 38 },
73 { 34, 39 },
74 { 25, 40 },
75 { 31, 41 },
76 { 29, 42 },
77 { 36, 43 },
78 { 17, 44 },
79 { 18, 45 },
80 { 44, 46 },
81 { 22, 47 },
82 { 23, 48 },
83 { 32, 49 },
84 { 16, 50 },
85 { 47, 51 },
86 { 28, 52 },
87 { 46, 53 },
88 { 49, 54 },
89 { 24, 55 },
90 { 0, 56 },
91 { 20, 57 },
92 { 25, 58 },
93 { 42, 59 },
94 { 48, 60 },
95 { 16, 61 },
96 { 26, 62 },
97 { 32, 63 },
98 { 24, 64 },
99 { 17, 65 },
100 { 47, 66 },
101 { 47, 67 },
102 { 12, 68 },
103 { 33, 69 },
104 { 41, 70 },
105 { 36, 71 },
106 { 8, 72 },
107 { 15, 73 },
108 { 0, 74 },
109 { 32, 75 },
110 { 28, 76 },
111 { 11, 77 },
112 { 46, 78 },
113 { 34, 79 },
114 { 5, 80 },
115 { 20, 81 },
116 { 47, 82 },
117 { 25, 83 },
118 { 7, 84 },
119 { 29, 85 },
120 { 40, 86 },
121 { 5, 87 },
122 { 12, 88 },
123 { 30, 89 },
124 { 1, 90 },
125 { 22, 91 },
126 { 29, 92 },
127 { 42, 93 },
128 { 49, 94 },
129 { 30, 95 },
130 { 40, 96 },
131 { 33, 97 },
132 { 36, 98 },
133 { 12, 99 },
134 { 8, 100 },
135 { 33, 101 },
136 { 5, 102 },
137 { 31, 103 },
138 { 27, 104 },
139 { 19, 105 },
140 { 43, 106 },
141 { 37, 107 },
142 { 9, 108 },
143 { 40, 109 },
144 { 0, 110 },
145 { 35, 111 },
146 { 32, 112 },
147 { 6, 113 },
148 { 27, 114 },
149 { 28, 115 },
150 { 30, 116 },
151 { 37, 117 },
152 { 32, 118 },
153 { 41, 119 },
154 { 14, 120 },
155 { 44, 121 },
156 { 22, 122 },
157 { 26, 123 },
158 { 2, 124 },
159 { 43, 125 },
160 { 20, 126 },
161 { 32, 127 },
162 { 24, 128 },
163 { 33, 129 },
164 { 7, 130 },
165 { 17, 131 },
166 { 10, 132 },
167 { 47, 133 },
168 { 14, 134 },
169 { 29, 135 },
170 { 19, 136 },
171 { 25, 137 },
172 { 25, 138 },
173 { 13, 139 },
174 { 25, 140 },
175 { 32, 141 },
176 { 8, 142 },
177 { 37, 143 },
178 { 31, 144 },
179 { 32, 145 },
180 { 5, 146 },
181 { 45, 147 },
182 { 35, 148 },
183 { 47, 149 },
184 { 3, 150 },
185 { 4, 151 },
186 { 37, 152 },
187 { 43, 153 },
188 { 39, 154 },
189 { 18, 155 },
190 { 13, 156 },
191 { 15, 157 },
192 { 41, 158 },
193 { 34, 159 },
194 { 4, 160 },
195 { 33, 161 },
196 { 20, 162 },
197 { 4, 163 },
198 { 38, 164 },
199 { 47, 165 },
200 { 30, 166 },
201 { 41, 167 },
202 { 23, 168 },
203 { 40, 169 },
204 { 23, 170 },
205 { 35, 171 },
206 { 47, 172 },
207 { 32, 173 },
208 { 15, 174 },
209 { 15, 175 },
210 { 41, 176 },
211 { 35, 177 },
212 { 6, 178 },
213 { 18, 179 },
214 { 35, 180 },
215 { 39, 181 },
216 { 34, 182 },
217 { 6, 183 },
218 { 34, 184 },
219 { 37, 185 },
220 { 15, 186 },
221 { 6, 187 },
222 { 12, 188 },
223 { 39, 189 },
224 { 9, 190 },
225 { 48, 191 },
226 { 37, 192 },
227 { 28, 193 },
228 { 32, 194 },
229 { 1, 195 },
230 { 45, 196 },
231 { 21, 197 },
232 { 11, 198 },
233 { 32, 199 },
234 { 43, 200 },
235 { 35, 201 },
236 { 25, 202 },
237 { 4, 203 },
238 { 20, 204 },
239 { 10, 205 },
240 { 22, 206 },
241 { 44, 207 },
242 { 30, 208 },
243 { 16, 209 },
244 { 42, 210 },
245 { 13, 211 },
246 { 29, 212 },
247 { 23, 213 },
248 { 30, 214 },
249 { 25, 215 },
250 { 49, 216 },
251 { 0, 217 },
252 { 49, 218 },
253 { 29, 219 },
254 { 37, 220 },
255 { 6, 221 },
256 { 27, 222 },
257 { 31, 223 },
258 { 17, 224 },
259 { 45, 225 },
260 { 25, 226 },
261 { 15, 227 },
262 { 34, 228 },
263 { 7, 229 },
264 { 7, 230 },
265 { 4, 231 },
266 { 31, 232 },
267 { 40, 233 },
268 { 17, 234 },
269 { 2, 235 },
270 { 34, 236 },
271 { 17, 237 },
272 { 25, 238 },
273 { 5, 239 },
274 { 48, 240 },
275 { 31, 241 },
276 { 41, 242 },
277 { 45, 243 },
278 { 33, 244 },
279 { 46, 245 },
280 { 19, 246 },
281 { 17, 247 },
282 { 38, 248 },
283 { 43, 249 },
284 { 16, 250 },
285 { 5, 251 },
286 { 21, 252 },
287 { 0, 253 },
288 { 47, 254 },
289 { 40, 255 },
290 { 22, 256 }
291 };
292
293 static int
294 cmp_double (const void *a, const void *b)
295 {
296 return (*(const double *)a < *(const double *)b ? -1 :
297 *(const double *)a > *(const double *)b ? 1 :
298 0);
299 }
300
301 int
302 main ()
303 {
304 size_t n;
305
306 /* Test merge_sort_fromto. */
307 for (n = 1; n <= NMAX; n++)
308 {
309 struct foo *dst;
310 struct foo *tmp;
311 double *qsort_result;
312 size_t i;
313
314 dst = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
315 dst[n].x = 0x4A6A71FE; /* canary */
316 tmp = (struct foo *) malloc ((n / 2 + 1) * sizeof (struct foo));
317 tmp[n / 2].x = 0x587EF149; /* canary */
318
319 merge_sort_fromto (data, dst, n, tmp);
320
321 /* Verify the canaries. */
322 ASSERT (dst[n].x == 0x4A6A71FE);
323 ASSERT (tmp[n / 2].x == 0x587EF149);
324
325 /* Verify the result. */
326 qsort_result = (double *) malloc (n * sizeof (double));
327 for (i = 0; i < n; i++)
328 qsort_result[i] = data[i].x;
329 qsort (qsort_result, n, sizeof (double), cmp_double);
330 for (i = 0; i < n; i++)
331 ASSERT (dst[i].x == qsort_result[i]);
332
333 /* Verify the stability. */
334 for (i = 0; i < n; i++)
335 if (i > 0 && dst[i - 1].x == dst[i].x)
336 ASSERT (dst[i - 1].index < dst[i].index);
337
338 free (qsort_result);
339 free (tmp);
340 free (dst);
341 }
342
343 /* Test merge_sort_inplace. */
344 for (n = 1; n <= NMAX; n++)
345 {
346 struct foo *src;
347 struct foo *tmp;
348 double *qsort_result;
349 size_t i;
350
351 src = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
352 src[n].x = 0x4A6A71FE; /* canary */
353 tmp = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
354 tmp[n].x = 0x587EF149; /* canary */
355
356 for (i = 0; i < n; i++)
357 src[i] = data[i];
358
359 merge_sort_inplace (src, n, tmp);
360
361 /* Verify the canaries. */
362 ASSERT (src[n].x == 0x4A6A71FE);
363 ASSERT (tmp[n].x == 0x587EF149);
364
365 /* Verify the result. */
366 qsort_result = (double *) malloc (n * sizeof (double));
367 for (i = 0; i < n; i++)
368 qsort_result[i] = data[i].x;
369 qsort (qsort_result, n, sizeof (double), cmp_double);
370 for (i = 0; i < n; i++)
371 ASSERT (src[i].x == qsort_result[i]);
372
373 /* Verify the stability. */
374 for (i = 0; i < n; i++)
375 if (i > 0 && src[i - 1].x == src[i].x)
376 ASSERT (src[i - 1].index < src[i].index);
377
378 free (qsort_result);
379 free (tmp);
380 free (src);
381 }
382
383 return 0;
384 }