384 lines
7.1 KiB
C
384 lines
7.1 KiB
C
/* Test of stable-sorting of an array using mergesort.
|
|
Copyright (C) 2009-2025 Free Software Foundation, Inc.
|
|
|
|
This program is free software: you can redistribute it and/or modify it
|
|
under the terms of the GNU Lesser General Public License as published
|
|
by the Free Software Foundation, either version 3 of the License, or
|
|
(at your option) any later version.
|
|
|
|
This program is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Lesser General Public License for more details.
|
|
|
|
You should have received a copy of the GNU Lesser General Public License
|
|
along with this program. If not, see <https://www.gnu.org/licenses/>. */
|
|
|
|
#include <config.h>
|
|
|
|
#include <stddef.h>
|
|
|
|
struct foo { double x; double index; };
|
|
#define ELEMENT struct foo
|
|
#define COMPARE(a,b) ((a)->x < (b)->x ? -1 : (a)->x > (b)->x ? 1 : 0)
|
|
#define STATIC static
|
|
#include "array-mergesort.h"
|
|
|
|
#include <stdlib.h>
|
|
|
|
#include "macros.h"
|
|
|
|
#define NMAX 257
|
|
static const struct foo data[NMAX] =
|
|
{
|
|
{ 2, 0 },
|
|
{ 28, 1 },
|
|
{ 36, 2 },
|
|
{ 43, 3 },
|
|
{ 20, 4 },
|
|
{ 37, 5 },
|
|
{ 19, 6 },
|
|
{ 37, 7 },
|
|
{ 30, 8 },
|
|
{ 18, 9 },
|
|
{ 30, 10 },
|
|
{ 49, 11 },
|
|
{ 16, 12 },
|
|
{ 22, 13 },
|
|
{ 23, 14 },
|
|
{ 3, 15 },
|
|
{ 39, 16 },
|
|
{ 48, 17 },
|
|
{ 18, 18 },
|
|
{ 18, 19 },
|
|
{ 45, 20 },
|
|
{ 39, 21 },
|
|
{ 1, 22 },
|
|
{ 44, 23 },
|
|
{ 24, 24 },
|
|
{ 21, 25 },
|
|
{ 29, 26 },
|
|
{ 3, 27 },
|
|
{ 34, 28 },
|
|
{ 15, 29 },
|
|
{ 39, 30 },
|
|
{ 11, 31 },
|
|
{ 29, 32 },
|
|
{ 27, 33 },
|
|
{ 43, 34 },
|
|
{ 31, 35 },
|
|
{ 28, 36 },
|
|
{ 12, 37 },
|
|
{ 16, 38 },
|
|
{ 34, 39 },
|
|
{ 25, 40 },
|
|
{ 31, 41 },
|
|
{ 29, 42 },
|
|
{ 36, 43 },
|
|
{ 17, 44 },
|
|
{ 18, 45 },
|
|
{ 44, 46 },
|
|
{ 22, 47 },
|
|
{ 23, 48 },
|
|
{ 32, 49 },
|
|
{ 16, 50 },
|
|
{ 47, 51 },
|
|
{ 28, 52 },
|
|
{ 46, 53 },
|
|
{ 49, 54 },
|
|
{ 24, 55 },
|
|
{ 0, 56 },
|
|
{ 20, 57 },
|
|
{ 25, 58 },
|
|
{ 42, 59 },
|
|
{ 48, 60 },
|
|
{ 16, 61 },
|
|
{ 26, 62 },
|
|
{ 32, 63 },
|
|
{ 24, 64 },
|
|
{ 17, 65 },
|
|
{ 47, 66 },
|
|
{ 47, 67 },
|
|
{ 12, 68 },
|
|
{ 33, 69 },
|
|
{ 41, 70 },
|
|
{ 36, 71 },
|
|
{ 8, 72 },
|
|
{ 15, 73 },
|
|
{ 0, 74 },
|
|
{ 32, 75 },
|
|
{ 28, 76 },
|
|
{ 11, 77 },
|
|
{ 46, 78 },
|
|
{ 34, 79 },
|
|
{ 5, 80 },
|
|
{ 20, 81 },
|
|
{ 47, 82 },
|
|
{ 25, 83 },
|
|
{ 7, 84 },
|
|
{ 29, 85 },
|
|
{ 40, 86 },
|
|
{ 5, 87 },
|
|
{ 12, 88 },
|
|
{ 30, 89 },
|
|
{ 1, 90 },
|
|
{ 22, 91 },
|
|
{ 29, 92 },
|
|
{ 42, 93 },
|
|
{ 49, 94 },
|
|
{ 30, 95 },
|
|
{ 40, 96 },
|
|
{ 33, 97 },
|
|
{ 36, 98 },
|
|
{ 12, 99 },
|
|
{ 8, 100 },
|
|
{ 33, 101 },
|
|
{ 5, 102 },
|
|
{ 31, 103 },
|
|
{ 27, 104 },
|
|
{ 19, 105 },
|
|
{ 43, 106 },
|
|
{ 37, 107 },
|
|
{ 9, 108 },
|
|
{ 40, 109 },
|
|
{ 0, 110 },
|
|
{ 35, 111 },
|
|
{ 32, 112 },
|
|
{ 6, 113 },
|
|
{ 27, 114 },
|
|
{ 28, 115 },
|
|
{ 30, 116 },
|
|
{ 37, 117 },
|
|
{ 32, 118 },
|
|
{ 41, 119 },
|
|
{ 14, 120 },
|
|
{ 44, 121 },
|
|
{ 22, 122 },
|
|
{ 26, 123 },
|
|
{ 2, 124 },
|
|
{ 43, 125 },
|
|
{ 20, 126 },
|
|
{ 32, 127 },
|
|
{ 24, 128 },
|
|
{ 33, 129 },
|
|
{ 7, 130 },
|
|
{ 17, 131 },
|
|
{ 10, 132 },
|
|
{ 47, 133 },
|
|
{ 14, 134 },
|
|
{ 29, 135 },
|
|
{ 19, 136 },
|
|
{ 25, 137 },
|
|
{ 25, 138 },
|
|
{ 13, 139 },
|
|
{ 25, 140 },
|
|
{ 32, 141 },
|
|
{ 8, 142 },
|
|
{ 37, 143 },
|
|
{ 31, 144 },
|
|
{ 32, 145 },
|
|
{ 5, 146 },
|
|
{ 45, 147 },
|
|
{ 35, 148 },
|
|
{ 47, 149 },
|
|
{ 3, 150 },
|
|
{ 4, 151 },
|
|
{ 37, 152 },
|
|
{ 43, 153 },
|
|
{ 39, 154 },
|
|
{ 18, 155 },
|
|
{ 13, 156 },
|
|
{ 15, 157 },
|
|
{ 41, 158 },
|
|
{ 34, 159 },
|
|
{ 4, 160 },
|
|
{ 33, 161 },
|
|
{ 20, 162 },
|
|
{ 4, 163 },
|
|
{ 38, 164 },
|
|
{ 47, 165 },
|
|
{ 30, 166 },
|
|
{ 41, 167 },
|
|
{ 23, 168 },
|
|
{ 40, 169 },
|
|
{ 23, 170 },
|
|
{ 35, 171 },
|
|
{ 47, 172 },
|
|
{ 32, 173 },
|
|
{ 15, 174 },
|
|
{ 15, 175 },
|
|
{ 41, 176 },
|
|
{ 35, 177 },
|
|
{ 6, 178 },
|
|
{ 18, 179 },
|
|
{ 35, 180 },
|
|
{ 39, 181 },
|
|
{ 34, 182 },
|
|
{ 6, 183 },
|
|
{ 34, 184 },
|
|
{ 37, 185 },
|
|
{ 15, 186 },
|
|
{ 6, 187 },
|
|
{ 12, 188 },
|
|
{ 39, 189 },
|
|
{ 9, 190 },
|
|
{ 48, 191 },
|
|
{ 37, 192 },
|
|
{ 28, 193 },
|
|
{ 32, 194 },
|
|
{ 1, 195 },
|
|
{ 45, 196 },
|
|
{ 21, 197 },
|
|
{ 11, 198 },
|
|
{ 32, 199 },
|
|
{ 43, 200 },
|
|
{ 35, 201 },
|
|
{ 25, 202 },
|
|
{ 4, 203 },
|
|
{ 20, 204 },
|
|
{ 10, 205 },
|
|
{ 22, 206 },
|
|
{ 44, 207 },
|
|
{ 30, 208 },
|
|
{ 16, 209 },
|
|
{ 42, 210 },
|
|
{ 13, 211 },
|
|
{ 29, 212 },
|
|
{ 23, 213 },
|
|
{ 30, 214 },
|
|
{ 25, 215 },
|
|
{ 49, 216 },
|
|
{ 0, 217 },
|
|
{ 49, 218 },
|
|
{ 29, 219 },
|
|
{ 37, 220 },
|
|
{ 6, 221 },
|
|
{ 27, 222 },
|
|
{ 31, 223 },
|
|
{ 17, 224 },
|
|
{ 45, 225 },
|
|
{ 25, 226 },
|
|
{ 15, 227 },
|
|
{ 34, 228 },
|
|
{ 7, 229 },
|
|
{ 7, 230 },
|
|
{ 4, 231 },
|
|
{ 31, 232 },
|
|
{ 40, 233 },
|
|
{ 17, 234 },
|
|
{ 2, 235 },
|
|
{ 34, 236 },
|
|
{ 17, 237 },
|
|
{ 25, 238 },
|
|
{ 5, 239 },
|
|
{ 48, 240 },
|
|
{ 31, 241 },
|
|
{ 41, 242 },
|
|
{ 45, 243 },
|
|
{ 33, 244 },
|
|
{ 46, 245 },
|
|
{ 19, 246 },
|
|
{ 17, 247 },
|
|
{ 38, 248 },
|
|
{ 43, 249 },
|
|
{ 16, 250 },
|
|
{ 5, 251 },
|
|
{ 21, 252 },
|
|
{ 0, 253 },
|
|
{ 47, 254 },
|
|
{ 40, 255 },
|
|
{ 22, 256 }
|
|
};
|
|
|
|
static int
|
|
cmp_double (const void *a, const void *b)
|
|
{
|
|
return (*(const double *)a < *(const double *)b ? -1 :
|
|
*(const double *)a > *(const double *)b ? 1 :
|
|
0);
|
|
}
|
|
|
|
int
|
|
main ()
|
|
{
|
|
size_t n;
|
|
|
|
/* Test merge_sort_fromto. */
|
|
for (n = 1; n <= NMAX; n++)
|
|
{
|
|
struct foo *dst;
|
|
struct foo *tmp;
|
|
double *qsort_result;
|
|
size_t i;
|
|
|
|
dst = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
|
|
dst[n].x = 0x4A6A71FE; /* canary */
|
|
tmp = (struct foo *) malloc ((n / 2 + 1) * sizeof (struct foo));
|
|
tmp[n / 2].x = 0x587EF149; /* canary */
|
|
|
|
merge_sort_fromto (data, dst, n, tmp);
|
|
|
|
/* Verify the canaries. */
|
|
ASSERT (dst[n].x == 0x4A6A71FE);
|
|
ASSERT (tmp[n / 2].x == 0x587EF149);
|
|
|
|
/* Verify the result. */
|
|
qsort_result = (double *) malloc (n * sizeof (double));
|
|
for (i = 0; i < n; i++)
|
|
qsort_result[i] = data[i].x;
|
|
qsort (qsort_result, n, sizeof (double), cmp_double);
|
|
for (i = 0; i < n; i++)
|
|
ASSERT (dst[i].x == qsort_result[i]);
|
|
|
|
/* Verify the stability. */
|
|
for (i = 0; i < n; i++)
|
|
if (i > 0 && dst[i - 1].x == dst[i].x)
|
|
ASSERT (dst[i - 1].index < dst[i].index);
|
|
|
|
free (qsort_result);
|
|
free (tmp);
|
|
free (dst);
|
|
}
|
|
|
|
/* Test merge_sort_inplace. */
|
|
for (n = 1; n <= NMAX; n++)
|
|
{
|
|
struct foo *src;
|
|
struct foo *tmp;
|
|
double *qsort_result;
|
|
size_t i;
|
|
|
|
src = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
|
|
src[n].x = 0x4A6A71FE; /* canary */
|
|
tmp = (struct foo *) malloc ((n + 1) * sizeof (struct foo));
|
|
tmp[n].x = 0x587EF149; /* canary */
|
|
|
|
for (i = 0; i < n; i++)
|
|
src[i] = data[i];
|
|
|
|
merge_sort_inplace (src, n, tmp);
|
|
|
|
/* Verify the canaries. */
|
|
ASSERT (src[n].x == 0x4A6A71FE);
|
|
ASSERT (tmp[n].x == 0x587EF149);
|
|
|
|
/* Verify the result. */
|
|
qsort_result = (double *) malloc (n * sizeof (double));
|
|
for (i = 0; i < n; i++)
|
|
qsort_result[i] = data[i].x;
|
|
qsort (qsort_result, n, sizeof (double), cmp_double);
|
|
for (i = 0; i < n; i++)
|
|
ASSERT (src[i].x == qsort_result[i]);
|
|
|
|
/* Verify the stability. */
|
|
for (i = 0; i < n; i++)
|
|
if (i > 0 && src[i - 1].x == src[i].x)
|
|
ASSERT (src[i - 1].index < src[i].index);
|
|
|
|
free (qsort_result);
|
|
free (tmp);
|
|
free (src);
|
|
}
|
|
|
|
return test_exit_status;
|
|
}
|