tests/test-array-mergesort.c

   1 /* Test of stable-sorting of an array using mergesort.
   2    Copyright (C) 2009-2014 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 <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 }