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