1/*-
2 * Copyright (c) 2017 Miles Fertel
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer,
10 *    without modification.
11 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
12 *    similar to the "NO WARRANTY" disclaimer below ("Disclaimer") and any
13 *    redistribution must be conditioned upon including a substantially
14 *    similar Disclaimer requirement for further binary redistribution.
15 *
16 * NO WARRANTY
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF NONINFRINGEMENT, MERCHANTIBILITY
20 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
21 * THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY,
22 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
25 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
27 * THE POSSIBILITY OF SUCH DAMAGES.
28 *
29 * $FreeBSD$
30 */
31
32#include <math.h>
33#include <stdio.h>
34#include <stdlib.h>
35#include <string.h>
36#include <sysexits.h>
37#include <unistd.h>
38
39#ifdef WIKI
40#include "stdlib/wiki.c"
41#endif
42
43/*
44 * Integer comparison function for stdlib sorting algorithms
45 */
46static int
47sorthelp(const void *a, const void *b)
48{
49	if (*(int *)a > *(int *)b)
50		return 1;
51	if (*(int *)a < *(int *)b)
52		return -1;
53	return 0;
54}
55
56#define NARGS 5
57
58/*
59 * Enumerated types for the different types of tests and sorting algorithms
60 */
61enum test { RAND, SORT, PART, REV, INVALID_TEST };
62
63#ifdef WIKI
64enum sort { MERGE, WIKI, QUICK, HEAP, INVALID_ALG };
65#else
66enum sort { MERGE, QUICK, HEAP, INVALID_ALG };
67#endif
68
69/*
70 * Sort an array with the given algorithm
71 */
72static void
73sort(int *testarray, int elts, enum sort s)
74{
75	switch (s) {
76	case MERGE:
77		mergesort(testarray, (size_t)elts, sizeof(int), sorthelp);
78		break;
79#ifdef WIKI
80	case WIKI:
81		WikiSort(testarray, (size_t)elts, sizeof(int), sorthelp);
82		break;
83#endif
84	case QUICK:
85		qsort(testarray, (size_t)elts, sizeof(int), sorthelp);
86		break;
87	case HEAP:
88		heapsort(testarray, (size_t)elts, sizeof(int), sorthelp);
89		break;
90	// Should never be reached
91	case INVALID_ALG:
92		exit(EX_DATAERR);
93	}
94}
95
96/*
97 * Sort an array of randomly generated integers
98 */
99static void
100rand_bench(int elts, enum sort s)
101{
102	size_t size = sizeof(int) * elts;
103	int *array = malloc(size);
104	arc4random_buf(array, size);
105	sort(array, elts, s);
106	free(array);
107}
108
109/*
110 * Sort an array of increasing integers
111 */
112static void
113sort_bench(int elts, enum sort s)
114{
115	size_t size = sizeof(int) * elts;
116	int *array = malloc(size);
117	for (int i = 0; i < elts; i++) {
118		array[i] = i;
119	}
120	sort(array, elts, s);
121	free(array);
122}
123
124/*
125 * Sort an array of partially increasing, partially random integers
126 */
127static void
128partial_bench(int elts, enum sort s)
129{
130	size_t size = sizeof(int) * elts;
131	int *array = malloc(size);
132	for (int i = 0; i < elts; i++) {
133		if (i <= elts / 2)
134			array[i] = i;
135		else
136			array[i] = arc4random();
137	}
138	sort(array, elts, s);
139	free(array);
140}
141
142/*
143 * Sort an array of decreasing integers
144 */
145static void
146reverse_bench(int elts, enum sort s)
147{
148	size_t size = sizeof(int) * elts;
149	int *array = malloc(size);
150	for (int i = 0; i < elts; i++) {
151		array[i] = elts - i;
152	}
153	sort(array, elts, s);
154	free(array);
155}
156
157static void
158run_bench(enum sort s, enum test t, int runs, int elts)
159{
160	for (int i = 0; i < runs; i++) {
161		switch (t) {
162		case RAND:
163			rand_bench(elts, s);
164			break;
165		case SORT:
166			sort_bench(elts, s);
167			break;
168		case PART:
169			partial_bench(elts, s);
170			break;
171		case REV:
172			reverse_bench(elts, s);
173			break;
174		// Should never be reached
175		case INVALID_TEST:
176			exit(EX_DATAERR);
177		}
178	}
179}
180
181static enum sort
182parse_alg(char *alg)
183{
184	if (strcmp(alg, "merge") == 0)
185		return MERGE;
186#ifdef WIKI
187	else if (strcmp(alg, "wiki") == 0)
188		return WIKI;
189#endif
190	else if (strcmp(alg, "quick") == 0)
191		return QUICK;
192	else if (strcmp(alg, "heap") == 0)
193		return HEAP;
194	else
195		return INVALID_ALG;
196}
197
198static enum test
199parse_test(char *test)
200{
201	if (strcmp(test, "rand") == 0)
202		return RAND;
203	else if (strcmp(test, "sort") == 0)
204		return SORT;
205	else if (strcmp(test, "part") == 0)
206		return PART;
207	else if (strcmp(test, "rev") == 0)
208		return REV;
209	else
210		return INVALID_TEST;
211}
212
213static void
214usage(const char *progname)
215{
216	printf("Usage:\n");
217	printf("\t%s: [alg] [test] [runs] [elt_power]\n", progname);
218	printf("\n");
219	printf("Valid algs:\n");
220#ifdef WIKI
221	printf("\theap merge quick wiki\n");
222#else
223	printf("\theap merge quick\n");
224#endif
225	printf("Valid tests:\n");
226	printf("\trand sort part rev\n");
227	printf("\trand: Random element array \n");
228	printf("\tsort: Increasing order array \n");
229	printf("\tpart: Partially ordered array\n");
230	printf("\trev: Decreasing order array\n");
231	printf("Run the algorithm [runs] times with 2^[elt_power] elements\n");
232	exit(EX_USAGE);
233}
234
235/*
236 * Runs a sorting algorithm with a provided data configuration according to
237 * command line arguments
238 */
239int
240main(int argc, char *argv[])
241{
242	const char *progname = argv[0];
243	int runs, elts;
244	if (argc != NARGS)
245		usage(progname);
246
247	enum sort s = parse_alg(argv[1]);
248	if (s == INVALID_ALG)
249		usage(progname);
250
251	enum test t = parse_test(argv[2]);
252	if (t == INVALID_TEST)
253		usage(progname);
254
255	runs = atoi(argv[3]);
256	elts = pow(2, atoi(argv[4]));
257
258	run_bench(s, t, runs, elts);
259}
260