t/helper/test-mergesort.c

   1 #include "test-tool.h"
   2 #include "cache.h"
   3 #include "mergesort.h"
   4
   5 struct line {
   6         char *text;
   7         struct line *next;
   8 };
   9
  10 static void *get_next(const void *a)
  11 {
  12         return ((const struct line *)a)->next;
  13 }
  14
  15 static void set_next(void *a, void *b)
  16 {
  17         ((struct line *)a)->next = b;
  18 }
  19
  20 static int compare_strings(const void *a, const void *b)
  21 {
  22         const struct line *x = a, *y = b;
  23         return strcmp(x->text, y->text);
  24 }
  25
  26 static int sort_stdin(void)
  27 {
  28         struct line *line, *p = NULL, *lines = NULL;
  29         struct strbuf sb = STRBUF_INIT;
  30
  31         while (!strbuf_getline(&sb, stdin)) {
  32                 line = xmalloc(sizeof(struct line));
  33                 line->text = strbuf_detach(&sb, NULL);
  34                 if (p) {
  35                         line->next = p->next;
  36                         p->next = line;
  37                 } else {
  38                         line->next = NULL;
  39                         lines = line;
  40                 }
  41                 p = line;
  42         }
  43
  44         lines = llist_mergesort(lines, get_next, set_next, compare_strings);
  45
  46         while (lines) {
  47                 puts(lines->text);
  48                 lines = lines->next;
  49         }
  50         return 0;
  51 }
  52
  53 static void dist_sawtooth(int *arr, int n, int m)
  54 {
  55         int i;
  56         for (i = 0; i < n; i++)
  57                 arr[i] = i % m;
  58 }
  59
  60 static void dist_rand(int *arr, int n, int m)
  61 {
  62         int i;
  63         for (i = 0; i < n; i++)
  64                 arr[i] = rand() % m;
  65 }
  66
  67 static void dist_stagger(int *arr, int n, int m)
  68 {
  69         int i;
  70         for (i = 0; i < n; i++)
  71                 arr[i] = (i * m + i) % n;
  72 }
  73
  74 static void dist_plateau(int *arr, int n, int m)
  75 {
  76         int i;
  77         for (i = 0; i < n; i++)
  78                 arr[i] = (i < m) ? i : m;
  79 }
  80
  81 static void dist_shuffle(int *arr, int n, int m)
  82 {
  83         int i, j, k;
  84         for (i = j = 0, k = 1; i < n; i++)
  85                 arr[i] = (rand() % m) ? (j += 2) : (k += 2);
  86 }
  87
  88 #define DIST(name) { #name, dist_##name }
  89
  90 static struct dist {
  91         const char *name;
  92         void (*fn)(int *arr, int n, int m);
  93 } dist[] = {
  94         DIST(sawtooth),
  95         DIST(rand),
  96         DIST(stagger),
  97         DIST(plateau),
  98         DIST(shuffle),
  99 };
 100
 101 static const struct dist *get_dist_by_name(const char *name)
 102 {
 103         int i;
 104         for (i = 0; i < ARRAY_SIZE(dist); i++) {
 105                if (!strcmp(dist[i].name, name))
 106                        return &dist[i];
 107         }
 108         return NULL;
 109 }
 110
 111 static void mode_copy(int *arr, int n)
 112 {
 113         /* nothing */
 114 }
 115
 116 static void mode_reverse(int *arr, int n)
 117 {
 118         int i, j;
 119         for (i = 0, j = n - 1; i < j; i++, j--)
 120                 SWAP(arr[i], arr[j]);
 121 }
 122
 123 static void mode_reverse_1st_half(int *arr, int n)
 124 {
 125         mode_reverse(arr, n / 2);
 126 }
 127
 128 static void mode_reverse_2nd_half(int *arr, int n)
 129 {
 130         int half = n / 2;
 131         mode_reverse(arr + half, n - half);
 132 }
 133
 134 static int compare_ints(const void *av, const void *bv)
 135 {
 136         const int *ap = av, *bp = bv;
 137         int a = *ap, b = *bp;
 138         return (a > b) - (a < b);
 139 }
 140
 141 static void mode_sort(int *arr, int n)
 142 {
 143         QSORT(arr, n, compare_ints);
 144 }
 145
 146 static void mode_dither(int *arr, int n)
 147 {
 148         int i;
 149         for (i = 0; i < n; i++)
 150                 arr[i] += i % 5;
 151 }
 152
 153 static void unriffle(int *arr, int n, int *tmp)
 154 {
 155         int i, j;
 156         COPY_ARRAY(tmp, arr, n);
 157         for (i = j = 0; i < n; i += 2)
 158                 arr[j++] = tmp[i];
 159         for (i = 1; i < n; i += 2)
 160                 arr[j++] = tmp[i];
 161 }
 162
 163 static void unriffle_recursively(int *arr, int n, int *tmp)
 164 {
 165         if (n > 1) {
 166                 int half = n / 2;
 167                 unriffle(arr, n, tmp);
 168                 unriffle_recursively(arr, half, tmp);
 169                 unriffle_recursively(arr + half, n - half, tmp);
 170         }
 171 }
 172
 173 static void mode_unriffle(int *arr, int n)
 174 {
 175         int *tmp;
 176         ALLOC_ARRAY(tmp, n);
 177         unriffle_recursively(arr, n, tmp);
 178         free(tmp);
 179 }
 180
 181 static unsigned int prev_pow2(unsigned int n)
 182 {
 183         unsigned int pow2 = 1;
 184         while (pow2 * 2 < n)
 185                 pow2 *= 2;
 186         return pow2;
 187 }
 188
 189 static void unriffle_recursively_skewed(int *arr, int n, int *tmp)
 190 {
 191         if (n > 1) {
 192                 int pow2 = prev_pow2(n);
 193                 int rest = n - pow2;
 194                 unriffle(arr + pow2 - rest, rest * 2, tmp);
 195                 unriffle_recursively_skewed(arr, pow2, tmp);
 196                 unriffle_recursively_skewed(arr + pow2, rest, tmp);
 197         }
 198 }
 199
 200 static void mode_unriffle_skewed(int *arr, int n)
 201 {
 202         int *tmp;
 203         ALLOC_ARRAY(tmp, n);
 204         unriffle_recursively_skewed(arr, n, tmp);
 205         free(tmp);
 206 }
 207
 208 #define MODE(name) { #name, mode_##name }
 209
 210 static struct mode {
 211         const char *name;
 212         void (*fn)(int *arr, int n);
 213 } mode[] = {
 214         MODE(copy),
 215         MODE(reverse),
 216         MODE(reverse_1st_half),
 217         MODE(reverse_2nd_half),
 218         MODE(sort),
 219         MODE(dither),
 220         MODE(unriffle),
 221         MODE(unriffle_skewed),
 222 };
 223
 224 static const struct mode *get_mode_by_name(const char *name)
 225 {
 226         int i;
 227         for (i = 0; i < ARRAY_SIZE(mode); i++) {
 228                if (!strcmp(mode[i].name, name))
 229                        return &mode[i];
 230         }
 231         return NULL;
 232 }
 233
 234 static int generate(int argc, const char **argv)
 235 {
 236         const struct dist *dist = NULL;
 237         const struct mode *mode = NULL;
 238         int i, n, m, *arr;
 239
 240         if (argc != 4)
 241                 return 1;
 242
 243         dist = get_dist_by_name(argv[0]);
 244         mode = get_mode_by_name(argv[1]);
 245         n = strtol(argv[2], NULL, 10);
 246         m = strtol(argv[3], NULL, 10);
 247         if (!dist || !mode)
 248                 return 1;
 249
 250         ALLOC_ARRAY(arr, n);
 251         dist->fn(arr, n, m);
 252         mode->fn(arr, n);
 253         for (i = 0; i < n; i++)
 254                 printf("%08x\n", arr[i]);
 255         free(arr);
 256         return 0;
 257 }
 258
 259 static struct stats {
 260         int get_next, set_next, compare;
 261 } stats;
 262
 263 struct number {
 264         int value, rank;
 265         struct number *next;
 266 };
 267
 268 static void *get_next_number(const void *a)
 269 {
 270         stats.get_next++;
 271         return ((const struct number *)a)->next;
 272 }
 273
 274 static void set_next_number(void *a, void *b)
 275 {
 276         stats.set_next++;
 277         ((struct number *)a)->next = b;
 278 }
 279
 280 static int compare_numbers(const void *av, const void *bv)
 281 {
 282         const struct number *an = av, *bn = bv;
 283         int a = an->value, b = bn->value;
 284         stats.compare++;
 285         return (a > b) - (a < b);
 286 }
 287
 288 static void clear_numbers(struct number *list)
 289 {
 290         while (list) {
 291                 struct number *next = list->next;
 292                 free(list);
 293                 list = next;
 294         }
 295 }
 296
 297 static int test(const struct dist *dist, const struct mode *mode, int n, int m)
 298 {
 299         int *arr;
 300         size_t i;
 301         struct number *curr, *list, **tail;
 302         int is_sorted = 1;
 303         int is_stable = 1;
 304         const char *verdict;
 305         int result = -1;
 306
 307         ALLOC_ARRAY(arr, n);
 308         dist->fn(arr, n, m);
 309         mode->fn(arr, n);
 310         for (i = 0, tail = &list; i < n; i++) {
 311                 curr = xmalloc(sizeof(*curr));
 312                 curr->value = arr[i];
 313                 curr->rank = i;
 314                 *tail = curr;
 315                 tail = &curr->next;
 316         }
 317         *tail = NULL;
 318
 319         stats.get_next = stats.set_next = stats.compare = 0;
 320         list = llist_mergesort(list, get_next_number, set_next_number,
 321                                compare_numbers);
 322
 323         QSORT(arr, n, compare_ints);
 324         for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {
 325                 if (arr[i] != curr->value)
 326                         is_sorted = 0;
 327                 if (curr->next && curr->value == curr->next->value &&
 328                     curr->rank >= curr->next->rank)
 329                         is_stable = 0;
 330         }
 331         if (i < n) {
 332                 verdict = "too short";
 333         } else if (curr) {
 334                 verdict = "too long";
 335         } else if (!is_sorted) {
 336                 verdict = "not sorted";
 337         } else if (!is_stable) {
 338                 verdict = "unstable";
 339         } else {
 340                 verdict = "OK";
 341                 result = 0;
 342         }
 343
 344         printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n",
 345                dist->name, mode->name, n, m, stats.get_next, stats.set_next,
 346                stats.compare, verdict);
 347
 348         clear_numbers(list);
 349         free(arr);
 350
 351         return result;
 352 }
 353
 354 /*
 355  * A version of the qsort certification program from "Engineering a Sort
 356  * Function" by Bentley and McIlroy, Software—Practice and Experience,
 357  * Volume 23, Issue 11, 1249–1265 (November 1993).
 358  */
 359 static int run_tests(int argc, const char **argv)
 360 {
 361         const char *argv_default[] = { "100", "1023", "1024", "1025" };
 362         if (!argc)
 363                 return run_tests(ARRAY_SIZE(argv_default), argv_default);
 364         printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n",
 365                "distribut", "mode", "n", "m", "get_next", "set_next",
 366                "compare", "verdict");
 367         while (argc--) {
 368                 int i, j, m, n = strtol(*argv++, NULL, 10);
 369                 for (i = 0; i < ARRAY_SIZE(dist); i++) {
 370                         for (j = 0; j < ARRAY_SIZE(mode); j++) {
 371                                 for (m = 1; m < 2 * n; m *= 2) {
 372                                         if (test(&dist[i], &mode[j], n, m))
 373                                                 return 1;
 374                                 }
 375                         }
 376                 }
 377         }
 378         return 0;
 379 }
 380
 381 int cmd__mergesort(int argc, const char **argv)
 382 {
 383         int i;
 384         const char *sep;
 385
 386         if (argc == 6 && !strcmp(argv[1], "generate"))
 387                 return generate(argc - 2, argv + 2);
 388         if (argc == 2 && !strcmp(argv[1], "sort"))
 389                 return sort_stdin();
 390         if (argc > 1 && !strcmp(argv[1], "test"))
 391                 return run_tests(argc - 2, argv + 2);
 392         fprintf(stderr, "usage: test-tool mergesort generate <distribution> <mode> <n> <m>\n");
 393         fprintf(stderr, "   or: test-tool mergesort sort\n");
 394         fprintf(stderr, "   or: test-tool mergesort test [<n>...]\n");
 395         fprintf(stderr, "\n");
 396         for (i = 0, sep = "distributions: "; i < ARRAY_SIZE(dist); i++, sep = ", ")
 397                 fprintf(stderr, "%s%s", sep, dist[i].name);
 398         fprintf(stderr, "\n");
 399         for (i = 0, sep = "modes: "; i < ARRAY_SIZE(mode); i++, sep = ", ")
 400                 fprintf(stderr, "%s%s", sep, mode[i].name);
 401         fprintf(stderr, "\n");
 402         return 129;
 403 }