[thirdparty/git.git] / t / helper / test-mergesort.c

#include "test-tool.h"
#include "cache.h"
#include "mergesort.h"

static uint32_t minstd_rand(uint32_t *state)
{
	*state = (uint64_t)*state * 48271 % 2147483647;
	return *state;
}

struct line {
	char *text;
	struct line *next;
};

DEFINE_LIST_SORT(static, sort_lines, struct line, next);

static int compare_strings(const struct line *x, const struct line *y)
{
	return strcmp(x->text, y->text);
}

static int sort_stdin(void)
{
	struct line *line, *p = NULL, *lines = NULL;
	struct strbuf sb = STRBUF_INIT;

	while (!strbuf_getline(&sb, stdin)) {
		line = xmalloc(sizeof(struct line));
		line->text = strbuf_detach(&sb, NULL);
		if (p) {
			line->next = p->next;
			p->next = line;
		} else {
			line->next = NULL;
			lines = line;
		}
		p = line;
	}

	sort_lines(&lines, compare_strings);

	while (lines) {
		puts(lines->text);
		lines = lines->next;
	}
	return 0;
}

static void dist_sawtooth(int *arr, int n, int m)
{
	int i;
	for (i = 0; i < n; i++)
		arr[i] = i % m;
}

static void dist_rand(int *arr, int n, int m)
{
	int i;
	uint32_t seed = 1;
	for (i = 0; i < n; i++)
		arr[i] = minstd_rand(&seed) % m;
}

static void dist_stagger(int *arr, int n, int m)
{
	int i;
	for (i = 0; i < n; i++)
		arr[i] = (i * m + i) % n;
}

static void dist_plateau(int *arr, int n, int m)
{
	int i;
	for (i = 0; i < n; i++)
		arr[i] = (i < m) ? i : m;
}

static void dist_shuffle(int *arr, int n, int m)
{
	int i, j, k;
	uint32_t seed = 1;
	for (i = j = 0, k = 1; i < n; i++)
		arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);
}

#define DIST(name) { #name, dist_##name }

static struct dist {
	const char *name;
	void (*fn)(int *arr, int n, int m);
} dist[] = {
	DIST(sawtooth),
	DIST(rand),
	DIST(stagger),
	DIST(plateau),
	DIST(shuffle),
};

static const struct dist *get_dist_by_name(const char *name)
{
	int i;
	for (i = 0; i < ARRAY_SIZE(dist); i++) {
	       if (!strcmp(dist[i].name, name))
		       return &dist[i];
	}
	return NULL;
}

static void mode_copy(int *arr, int n)
{
	/* nothing */
}

static void mode_reverse(int *arr, int n)
{
	int i, j;
	for (i = 0, j = n - 1; i < j; i++, j--)
		SWAP(arr[i], arr[j]);
}

static void mode_reverse_1st_half(int *arr, int n)
{
	mode_reverse(arr, n / 2);
}

static void mode_reverse_2nd_half(int *arr, int n)
{
	int half = n / 2;
	mode_reverse(arr + half, n - half);
}

static int compare_ints(const void *av, const void *bv)
{
	const int *ap = av, *bp = bv;
	int a = *ap, b = *bp;
	return (a > b) - (a < b);
}

static void mode_sort(int *arr, int n)
{
	QSORT(arr, n, compare_ints);
}

static void mode_dither(int *arr, int n)
{
	int i;
	for (i = 0; i < n; i++)
		arr[i] += i % 5;
}

static void unriffle(int *arr, int n, int *tmp)
{
	int i, j;
	COPY_ARRAY(tmp, arr, n);
	for (i = j = 0; i < n; i += 2)
		arr[j++] = tmp[i];
	for (i = 1; i < n; i += 2)
		arr[j++] = tmp[i];
}

static void unriffle_recursively(int *arr, int n, int *tmp)
{
	if (n > 1) {
		int half = n / 2;
		unriffle(arr, n, tmp);
		unriffle_recursively(arr, half, tmp);
		unriffle_recursively(arr + half, n - half, tmp);
	}
}

static void mode_unriffle(int *arr, int n)
{
	int *tmp;
	ALLOC_ARRAY(tmp, n);
	unriffle_recursively(arr, n, tmp);
	free(tmp);
}

static unsigned int prev_pow2(unsigned int n)
{
	unsigned int pow2 = 1;
	while (pow2 * 2 < n)
		pow2 *= 2;
	return pow2;
}

static void unriffle_recursively_skewed(int *arr, int n, int *tmp)
{
	if (n > 1) {
		int pow2 = prev_pow2(n);
		int rest = n - pow2;
		unriffle(arr + pow2 - rest, rest * 2, tmp);
		unriffle_recursively_skewed(arr, pow2, tmp);
		unriffle_recursively_skewed(arr + pow2, rest, tmp);
	}
}

static void mode_unriffle_skewed(int *arr, int n)
{
	int *tmp;
	ALLOC_ARRAY(tmp, n);
	unriffle_recursively_skewed(arr, n, tmp);
	free(tmp);
}

#define MODE(name) { #name, mode_##name }

static struct mode {
	const char *name;
	void (*fn)(int *arr, int n);
} mode[] = {
	MODE(copy),
	MODE(reverse),
	MODE(reverse_1st_half),
	MODE(reverse_2nd_half),
	MODE(sort),
	MODE(dither),
	MODE(unriffle),
	MODE(unriffle_skewed),
};

static const struct mode *get_mode_by_name(const char *name)
{
	int i;
	for (i = 0; i < ARRAY_SIZE(mode); i++) {
	       if (!strcmp(mode[i].name, name))
		       return &mode[i];
	}
	return NULL;
}

static int generate(int argc, const char **argv)
{
	const struct dist *dist = NULL;
	const struct mode *mode = NULL;
	int i, n, m, *arr;

	if (argc != 4)
		return 1;

	dist = get_dist_by_name(argv[0]);
	mode = get_mode_by_name(argv[1]);
	n = strtol(argv[2], NULL, 10);
	m = strtol(argv[3], NULL, 10);
	if (!dist || !mode)
		return 1;

	ALLOC_ARRAY(arr, n);
	dist->fn(arr, n, m);
	mode->fn(arr, n);
	for (i = 0; i < n; i++)
		printf("%08x\n", arr[i]);
	free(arr);
	return 0;
}

static struct stats {
	int get_next, set_next, compare;
} stats;

struct number {
	int value, rank;
	struct number *next;
};

DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,
		       stats.get_next++, stats.set_next++);

static int compare_numbers(const struct number *an, const struct number *bn)
{
	int a = an->value, b = bn->value;
	stats.compare++;
	return (a > b) - (a < b);
}

static void clear_numbers(struct number *list)
{
	while (list) {
		struct number *next = list->next;
		free(list);
		list = next;
	}
}

static int test(const struct dist *dist, const struct mode *mode, int n, int m)
{
	int *arr;
	size_t i;
	struct number *curr, *list, **tail;
	int is_sorted = 1;
	int is_stable = 1;
	const char *verdict;
	int result = -1;

	ALLOC_ARRAY(arr, n);
	dist->fn(arr, n, m);
	mode->fn(arr, n);
	for (i = 0, tail = &list; i < n; i++) {
		curr = xmalloc(sizeof(*curr));
		curr->value = arr[i];
		curr->rank = i;
		*tail = curr;
		tail = &curr->next;
	}
	*tail = NULL;

	stats.get_next = stats.set_next = stats.compare = 0;
	sort_numbers(&list, compare_numbers);

	QSORT(arr, n, compare_ints);
	for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {
		if (arr[i] != curr->value)
			is_sorted = 0;
		if (curr->next && curr->value == curr->next->value &&
		    curr->rank >= curr->next->rank)
			is_stable = 0;
	}
	if (i < n) {
		verdict = "too short";
	} else if (curr) {
		verdict = "too long";
	} else if (!is_sorted) {
		verdict = "not sorted";
	} else if (!is_stable) {
		verdict = "unstable";
	} else {
		verdict = "OK";
		result = 0;
	}

	printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n",
	       dist->name, mode->name, n, m, stats.get_next, stats.set_next,
	       stats.compare, verdict);

	clear_numbers(list);
	free(arr);

	return result;
}

/*
 * A version of the qsort certification program from "Engineering a Sort
 * Function" by Bentley and McIlroy, Software—Practice and Experience,
 * Volume 23, Issue 11, 1249–1265 (November 1993).
 */
static int run_tests(int argc, const char **argv)
{
	const char *argv_default[] = { "100", "1023", "1024", "1025" };
	if (!argc)
		return run_tests(ARRAY_SIZE(argv_default), argv_default);
	printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n",
	       "distribut", "mode", "n", "m", "get_next", "set_next",
	       "compare", "verdict");
	while (argc--) {
		int i, j, m, n = strtol(*argv++, NULL, 10);
		for (i = 0; i < ARRAY_SIZE(dist); i++) {
			for (j = 0; j < ARRAY_SIZE(mode); j++) {
				for (m = 1; m < 2 * n; m *= 2) {
					if (test(&dist[i], &mode[j], n, m))
						return 1;
				}
			}
		}
	}
	return 0;
}

int cmd__mergesort(int argc, const char **argv)
{
	int i;
	const char *sep;

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