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 void mode_copy(int *arr, int n)
 102 {
 103         /* nothing */
 104 }
 105
 106 static void mode_reverse(int *arr, int n)
 107 {
 108         int i, j;
 109         for (i = 0, j = n - 1; i < j; i++, j--)
 110                 SWAP(arr[i], arr[j]);
 111 }
 112
 113 static void mode_reverse_1st_half(int *arr, int n)
 114 {
 115         mode_reverse(arr, n / 2);
 116 }
 117
 118 static void mode_reverse_2nd_half(int *arr, int n)
 119 {
 120         int half = n / 2;
 121         mode_reverse(arr + half, n - half);
 122 }
 123
 124 static int compare_ints(const void *av, const void *bv)
 125 {
 126         const int *ap = av, *bp = bv;
 127         int a = *ap, b = *bp;
 128         return (a > b) - (a < b);
 129 }
 130
 131 static void mode_sort(int *arr, int n)
 132 {
 133         QSORT(arr, n, compare_ints);
 134 }
 135
 136 static void mode_dither(int *arr, int n)
 137 {
 138         int i;
 139         for (i = 0; i < n; i++)
 140                 arr[i] += i % 5;
 141 }
 142
 143 #define MODE(name) { #name, mode_##name }
 144
 145 static struct mode {
 146         const char *name;
 147         void (*fn)(int *arr, int n);
 148 } mode[] = {
 149         MODE(copy),
 150         MODE(reverse),
 151         MODE(reverse_1st_half),
 152         MODE(reverse_2nd_half),
 153         MODE(sort),
 154         MODE(dither),
 155 };
 156
 157 static struct stats {
 158         int get_next, set_next, compare;
 159 } stats;
 160
 161 struct number {
 162         int value, rank;
 163         struct number *next;
 164 };
 165
 166 static void *get_next_number(const void *a)
 167 {
 168         stats.get_next++;
 169         return ((const struct number *)a)->next;
 170 }
 171
 172 static void set_next_number(void *a, void *b)
 173 {
 174         stats.set_next++;
 175         ((struct number *)a)->next = b;
 176 }
 177
 178 static int compare_numbers(const void *av, const void *bv)
 179 {
 180         const struct number *an = av, *bn = bv;
 181         int a = an->value, b = bn->value;
 182         stats.compare++;
 183         return (a > b) - (a < b);
 184 }
 185
 186 static void clear_numbers(struct number *list)
 187 {
 188         while (list) {
 189                 struct number *next = list->next;
 190                 free(list);
 191                 list = next;
 192         }
 193 }
 194
 195 static int test(const struct dist *dist, const struct mode *mode, int n, int m)
 196 {
 197         int *arr;
 198         size_t i;
 199         struct number *curr, *list, **tail;
 200         int is_sorted = 1;
 201         int is_stable = 1;
 202         const char *verdict;
 203         int result = -1;
 204
 205         ALLOC_ARRAY(arr, n);
 206         dist->fn(arr, n, m);
 207         mode->fn(arr, n);
 208         for (i = 0, tail = &list; i < n; i++) {
 209                 curr = xmalloc(sizeof(*curr));
 210                 curr->value = arr[i];
 211                 curr->rank = i;
 212                 *tail = curr;
 213                 tail = &curr->next;
 214         }
 215         *tail = NULL;
 216
 217         stats.get_next = stats.set_next = stats.compare = 0;
 218         list = llist_mergesort(list, get_next_number, set_next_number,
 219                                compare_numbers);
 220
 221         QSORT(arr, n, compare_ints);
 222         for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {
 223                 if (arr[i] != curr->value)
 224                         is_sorted = 0;
 225                 if (curr->next && curr->value == curr->next->value &&
 226                     curr->rank >= curr->next->rank)
 227                         is_stable = 0;
 228         }
 229         if (i < n) {
 230                 verdict = "too short";
 231         } else if (curr) {
 232                 verdict = "too long";
 233         } else if (!is_sorted) {
 234                 verdict = "not sorted";
 235         } else if (!is_stable) {
 236                 verdict = "unstable";
 237         } else {
 238                 verdict = "OK";
 239                 result = 0;
 240         }
 241
 242         printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n",
 243                dist->name, mode->name, n, m, stats.get_next, stats.set_next,
 244                stats.compare, verdict);
 245
 246         clear_numbers(list);
 247         free(arr);
 248
 249         return result;
 250 }
 251
 252 /*
 253  * A version of the qsort certification program from "Engineering a Sort
 254  * Function" by Bentley and McIlroy, Software—Practice and Experience,
 255  * Volume 23, Issue 11, 1249–1265 (November 1993).
 256  */
 257 static int run_tests(int argc, const char **argv)
 258 {
 259         const char *argv_default[] = { "100", "1023", "1024", "1025" };
 260         if (!argc)
 261                 return run_tests(ARRAY_SIZE(argv_default), argv_default);
 262         printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n",
 263                "distribut", "mode", "n", "m", "get_next", "set_next",
 264                "compare", "verdict");
 265         while (argc--) {
 266                 int i, j, m, n = strtol(*argv++, NULL, 10);
 267                 for (i = 0; i < ARRAY_SIZE(dist); i++) {
 268                         for (j = 0; j < ARRAY_SIZE(mode); j++) {
 269                                 for (m = 1; m < 2 * n; m *= 2) {
 270                                         if (test(&dist[i], &mode[j], n, m))
 271                                                 return 1;
 272                                 }
 273                         }
 274                 }
 275         }
 276         return 0;
 277 }
 278
 279 int cmd__mergesort(int argc, const char **argv)
 280 {
 281         if (argc == 2 && !strcmp(argv[1], "sort"))
 282                 return sort_stdin();
 283         if (argc > 1 && !strcmp(argv[1], "test"))
 284                 return run_tests(argc - 2, argv + 2);
 285         fprintf(stderr, "usage: test-tool mergesort sort\n");
 286         fprintf(stderr, "   or: test-tool mergesort test [<n>...]\n");
 287         return 129;
 288 }