6 static uint32_t minstd_rand(uint32_t *state
)
8 *state
= (uint64_t)*state
* 48271 % 2147483647;
17 DEFINE_LIST_SORT(static, sort_lines
, struct line
, next
);
19 static int compare_strings(const struct line
*x
, const struct line
*y
)
21 return strcmp(x
->text
, y
->text
);
24 static int sort_stdin(void)
27 struct line
**tail
= &lines
;
28 struct strbuf sb
= STRBUF_INIT
;
29 struct mem_pool lines_pool
;
32 strbuf_read(&sb
, 0, 0);
35 * Split by newline, but don't create an item
36 * for the empty string after the last separator.
38 if (sb
.len
&& sb
.buf
[sb
.len
- 1] == '\n')
39 strbuf_setlen(&sb
, sb
.len
- 1);
41 mem_pool_init(&lines_pool
, 0);
44 char *eol
= strchr(p
, '\n');
45 struct line
*line
= mem_pool_alloc(&lines_pool
, sizeof(*line
));
56 sort_lines(&lines
, compare_strings
);
65 static void dist_sawtooth(int *arr
, int n
, int m
)
68 for (i
= 0; i
< n
; i
++)
72 static void dist_rand(int *arr
, int n
, int m
)
76 for (i
= 0; i
< n
; i
++)
77 arr
[i
] = minstd_rand(&seed
) % m
;
80 static void dist_stagger(int *arr
, int n
, int m
)
83 for (i
= 0; i
< n
; i
++)
84 arr
[i
] = (i
* m
+ i
) % n
;
87 static void dist_plateau(int *arr
, int n
, int m
)
90 for (i
= 0; i
< n
; i
++)
91 arr
[i
] = (i
< m
) ? i
: m
;
94 static void dist_shuffle(int *arr
, int n
, int m
)
98 for (i
= j
= 0, k
= 1; i
< n
; i
++)
99 arr
[i
] = minstd_rand(&seed
) % m
? (j
+= 2) : (k
+= 2);
102 #define DIST(name) { #name, dist_##name }
106 void (*fn
)(int *arr
, int n
, int m
);
115 static const struct dist
*get_dist_by_name(const char *name
)
118 for (i
= 0; i
< ARRAY_SIZE(dist
); i
++) {
119 if (!strcmp(dist
[i
].name
, name
))
125 static void mode_copy(int *arr
, int n
)
130 static void mode_reverse(int *arr
, int n
)
133 for (i
= 0, j
= n
- 1; i
< j
; i
++, j
--)
134 SWAP(arr
[i
], arr
[j
]);
137 static void mode_reverse_1st_half(int *arr
, int n
)
139 mode_reverse(arr
, n
/ 2);
142 static void mode_reverse_2nd_half(int *arr
, int n
)
145 mode_reverse(arr
+ half
, n
- half
);
148 static int compare_ints(const void *av
, const void *bv
)
150 const int *ap
= av
, *bp
= bv
;
151 int a
= *ap
, b
= *bp
;
152 return (a
> b
) - (a
< b
);
155 static void mode_sort(int *arr
, int n
)
157 QSORT(arr
, n
, compare_ints
);
160 static void mode_dither(int *arr
, int n
)
163 for (i
= 0; i
< n
; i
++)
167 static void unriffle(int *arr
, int n
, int *tmp
)
170 COPY_ARRAY(tmp
, arr
, n
);
171 for (i
= j
= 0; i
< n
; i
+= 2)
173 for (i
= 1; i
< n
; i
+= 2)
177 static void unriffle_recursively(int *arr
, int n
, int *tmp
)
181 unriffle(arr
, n
, tmp
);
182 unriffle_recursively(arr
, half
, tmp
);
183 unriffle_recursively(arr
+ half
, n
- half
, tmp
);
187 static void mode_unriffle(int *arr
, int n
)
191 unriffle_recursively(arr
, n
, tmp
);
195 static unsigned int prev_pow2(unsigned int n
)
197 unsigned int pow2
= 1;
203 static void unriffle_recursively_skewed(int *arr
, int n
, int *tmp
)
206 int pow2
= prev_pow2(n
);
208 unriffle(arr
+ pow2
- rest
, rest
* 2, tmp
);
209 unriffle_recursively_skewed(arr
, pow2
, tmp
);
210 unriffle_recursively_skewed(arr
+ pow2
, rest
, tmp
);
214 static void mode_unriffle_skewed(int *arr
, int n
)
218 unriffle_recursively_skewed(arr
, n
, tmp
);
222 #define MODE(name) { #name, mode_##name }
226 void (*fn
)(int *arr
, int n
);
230 MODE(reverse_1st_half
),
231 MODE(reverse_2nd_half
),
235 MODE(unriffle_skewed
),
238 static const struct mode
*get_mode_by_name(const char *name
)
241 for (i
= 0; i
< ARRAY_SIZE(mode
); i
++) {
242 if (!strcmp(mode
[i
].name
, name
))
248 static int generate(int argc
, const char **argv
)
250 const struct dist
*dist
= NULL
;
251 const struct mode
*mode
= NULL
;
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);
267 for (i
= 0; i
< n
; i
++)
268 printf("%08x\n", arr
[i
]);
273 static struct stats
{
274 int get_next
, set_next
, compare
;
282 DEFINE_LIST_SORT_DEBUG(static, sort_numbers
, struct number
, next
,
283 stats
.get_next
++, stats
.set_next
++);
285 static int compare_numbers(const struct number
*an
, const struct number
*bn
)
287 int a
= an
->value
, b
= bn
->value
;
289 return (a
> b
) - (a
< b
);
292 static void clear_numbers(struct number
*list
)
295 struct number
*next
= list
->next
;
301 static int test(const struct dist
*dist
, const struct mode
*mode
, int n
, int m
)
305 struct number
*curr
, *list
, **tail
;
314 for (i
= 0, tail
= &list
; i
< n
; i
++) {
315 curr
= xmalloc(sizeof(*curr
));
316 curr
->value
= arr
[i
];
323 stats
.get_next
= stats
.set_next
= stats
.compare
= 0;
324 sort_numbers(&list
, compare_numbers
);
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
)
330 if (curr
->next
&& curr
->value
== curr
->next
->value
&&
331 curr
->rank
>= curr
->next
->rank
)
335 verdict
= "too short";
337 verdict
= "too long";
338 } else if (!is_sorted
) {
339 verdict
= "not sorted";
340 } else if (!is_stable
) {
341 verdict
= "unstable";
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
);
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).
362 static int run_tests(int argc
, const char **argv
)
364 const char *argv_default
[] = { "100", "1023", "1024", "1025" };
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");
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
))
384 int cmd__mergesort(int argc
, const char **argv
)
389 if (argc
== 6 && !strcmp(argv
[1], "generate"))
390 return generate(argc
- 2, argv
+ 2);
391 if (argc
== 2 && !strcmp(argv
[1], "sort"))
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");