Imported Upstream version 0.9.1upstream/0.9.1

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;
+}