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 */
46 static int
sorthelp(const void * a,const void * b)47 sorthelp(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 */
61 enum test { RAND, SORT, PART, REV, INVALID_TEST };
62
63 #ifdef WIKI
64 enum sort { MERGE, WIKI, QUICK, HEAP, INVALID_ALG };
65 #else
66 enum sort { MERGE, QUICK, HEAP, INVALID_ALG };
67 #endif
68
69 /*
70 * Sort an array with the given algorithm
71 */
72 static void
sort(int * testarray,int elts,enum sort s)73 sort(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 */
99 static void
rand_bench(int elts,enum sort s)100 rand_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 */
112 static void
sort_bench(int elts,enum sort s)113 sort_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 */
127 static void
partial_bench(int elts,enum sort s)128 partial_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 */
145 static void
reverse_bench(int elts,enum sort s)146 reverse_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
157 static void
run_bench(enum sort s,enum test t,int runs,int elts)158 run_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
181 static enum sort
parse_alg(char * alg)182 parse_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
198 static enum test
parse_test(char * test)199 parse_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
213 static void
usage(const char * progname)214 usage(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 */
239 int
main(int argc,char * argv[])240 main(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