t/helper/test-mergesort.c

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