summaryrefslogtreecommitdiff
path: root/tests/test-array-mergesort.c
diff options
context:
space:
mode:
Diffstat (limited to 'tests/test-array-mergesort.c')
-rw-r--r--tests/test-array-mergesort.c395
1 files changed, 395 insertions, 0 deletions
diff --git a/tests/test-array-mergesort.c b/tests/test-array-mergesort.c
new file mode 100644
index 00000000..8a47b676
--- /dev/null
+++ b/tests/test-array-mergesort.c
@@ -0,0 +1,395 @@
+/* Test of stable-sorting of an array using mergesort.
+ Copyright (C) 2009 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 <http://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 <stdio.h>
+#include <stdlib.h>
+
+#define ASSERT(expr) \
+ do \
+ { \
+ if (!(expr)) \
+ { \
+ fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
+ fflush (stderr); \
+ abort (); \
+ } \
+ } \
+ while (0)
+
+#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 0;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-03 01:08:23 +0000