]>
Commit | Line | Data |
---|---|---|
34889d3c | 1 | #include "test-tool.h" |
0db71e0f RS |
2 | #include "cache.h" |
3 | #include "mergesort.h" | |
4 | ||
c90cfc22 RS |
5 | static uint32_t minstd_rand(uint32_t *state) |
6 | { | |
7 | *state = (uint64_t)*state * 48271 % 2147483647; | |
8 | return *state; | |
9 | } | |
10 | ||
0db71e0f RS |
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 | ||
d536a711 | 32 | static int sort_stdin(void) |
0db71e0f RS |
33 | { |
34 | struct line *line, *p = NULL, *lines = NULL; | |
35 | struct strbuf sb = STRBUF_INIT; | |
36 | ||
2e670101 | 37 | while (!strbuf_getline(&sb, stdin)) { |
0db71e0f RS |
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 | ||
7365c95d | 50 | lines = llist_mergesort(lines, get_next, set_next, compare_strings); |
0db71e0f RS |
51 | |
52 | while (lines) { | |
2e670101 | 53 | puts(lines->text); |
0db71e0f RS |
54 | lines = lines->next; |
55 | } | |
56 | return 0; | |
57 | } | |
d536a711 | 58 | |
e031e971 RS |
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; | |
c90cfc22 | 69 | uint32_t seed = 1; |
e031e971 | 70 | for (i = 0; i < n; i++) |
c90cfc22 | 71 | arr[i] = minstd_rand(&seed) % m; |
e031e971 RS |
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; | |
c90cfc22 | 91 | uint32_t seed = 1; |
e031e971 | 92 | for (i = j = 0, k = 1; i < n; i++) |
c90cfc22 | 93 | arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2); |
e031e971 RS |
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 | ||
0cecb755 RS |
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 | ||
e031e971 RS |
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 | ||
1aa58992 RS |
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 | ||
f1ed4ce9 RS |
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 | ||
e031e971 RS |
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), | |
1aa58992 | 228 | MODE(unriffle), |
f1ed4ce9 | 229 | MODE(unriffle_skewed), |
e031e971 RS |
230 | }; |
231 | ||
0cecb755 RS |
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 | ||
e031e971 RS |
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 | ||
d536a711 RS |
389 | int cmd__mergesort(int argc, const char **argv) |
390 | { | |
0cecb755 RS |
391 | int i; |
392 | const char *sep; | |
393 | ||
394 | if (argc == 6 && !strcmp(argv[1], "generate")) | |
395 | return generate(argc - 2, argv + 2); | |
d536a711 RS |
396 | if (argc == 2 && !strcmp(argv[1], "sort")) |
397 | return sort_stdin(); | |
e031e971 RS |
398 | if (argc > 1 && !strcmp(argv[1], "test")) |
399 | return run_tests(argc - 2, argv + 2); | |
0cecb755 RS |
400 | fprintf(stderr, "usage: test-tool mergesort generate <distribution> <mode> <n> <m>\n"); |
401 | fprintf(stderr, " or: test-tool mergesort sort\n"); | |
e031e971 | 402 | fprintf(stderr, " or: test-tool mergesort test [<n>...]\n"); |
0cecb755 RS |
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"); | |
e031e971 | 410 | return 129; |
d536a711 | 411 | } |