t/helper/test-mergesort.c

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