tests/test-array-mergesort.c

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