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
30 #include <math.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <sysexits.h>
35 #include <unistd.h>
36
37 #ifdef WIKI
38 #include "stdlib/wiki.c"
39 #endif
40
41 /*
42 * Integer comparison function for stdlib sorting algorithms
43 */
44 static int
sorthelp(const void * a,const void * b)45 sorthelp(const void *a, const void *b)
46 {
47 if (*(int *)a > *(int *)b)
48 return 1;
49 if (*(int *)a < *(int *)b)
50 return -1;
51 return 0;
52 }
53
54 #define NARGS 5
55
56 /*
57 * Enumerated types for the different types of tests and sorting algorithms
58 */
59 enum test { RAND, SORT, PART, REV, INVALID_TEST };
60
61 #ifdef WIKI
62 enum sort { MERGE, WIKI, QUICK, HEAP, INVALID_ALG };
63 #else
64 enum sort { MERGE, QUICK, HEAP, INVALID_ALG };
65 #endif
66
67 /*
68 * Sort an array with the given algorithm
69 */
70 static void
sort(int * testarray,int elts,enum sort s)71 sort(int *testarray, int elts, enum sort s)
72 {
73 switch (s) {
74 case MERGE:
75 mergesort(testarray, (size_t)elts, sizeof(int), sorthelp);
76 break;
77 #ifdef WIKI
78 case WIKI:
79 WikiSort(testarray, (size_t)elts, sizeof(int), sorthelp);
80 break;
81 #endif
82 case QUICK:
83 qsort(testarray, (size_t)elts, sizeof(int), sorthelp);
84 break;
85 case HEAP:
86 heapsort(testarray, (size_t)elts, sizeof(int), sorthelp);
87 break;
88 // Should never be reached
89 case INVALID_ALG:
90 exit(EX_DATAERR);
91 }
92 }
93
94 /*
95 * Sort an array of randomly generated integers
96 */
97 static void
rand_bench(int elts,enum sort s)98 rand_bench(int elts, enum sort s)
99 {
100 size_t size = sizeof(int) * elts;
101 int *array = malloc(size);
102 arc4random_buf(array, size);
103 sort(array, elts, s);
104 free(array);
105 }
106
107 /*
108 * Sort an array of increasing integers
109 */
110 static void
sort_bench(int elts,enum sort s)111 sort_bench(int elts, enum sort s)
112 {
113 size_t size = sizeof(int) * elts;
114 int *array = malloc(size);
115 for (int i = 0; i < elts; i++) {
116 array[i] = i;
117 }
118 sort(array, elts, s);
119 free(array);
120 }
121
122 /*
123 * Sort an array of partially increasing, partially random integers
124 */
125 static void
partial_bench(int elts,enum sort s)126 partial_bench(int elts, enum sort s)
127 {
128 size_t size = sizeof(int) * elts;
129 int *array = malloc(size);
130 for (int i = 0; i < elts; i++) {
131 if (i <= elts / 2)
132 array[i] = i;
133 else
134 array[i] = arc4random();
135 }
136 sort(array, elts, s);
137 free(array);
138 }
139
140 /*
141 * Sort an array of decreasing integers
142 */
143 static void
reverse_bench(int elts,enum sort s)144 reverse_bench(int elts, enum sort s)
145 {
146 size_t size = sizeof(int) * elts;
147 int *array = malloc(size);
148 for (int i = 0; i < elts; i++) {
149 array[i] = elts - i;
150 }
151 sort(array, elts, s);
152 free(array);
153 }
154
155 static void
run_bench(enum sort s,enum test t,int runs,int elts)156 run_bench(enum sort s, enum test t, int runs, int elts)
157 {
158 for (int i = 0; i < runs; i++) {
159 switch (t) {
160 case RAND:
161 rand_bench(elts, s);
162 break;
163 case SORT:
164 sort_bench(elts, s);
165 break;
166 case PART:
167 partial_bench(elts, s);
168 break;
169 case REV:
170 reverse_bench(elts, s);
171 break;
172 // Should never be reached
173 case INVALID_TEST:
174 exit(EX_DATAERR);
175 }
176 }
177 }
178
179 static enum sort
parse_alg(char * alg)180 parse_alg(char *alg)
181 {
182 if (strcmp(alg, "merge") == 0)
183 return MERGE;
184 #ifdef WIKI
185 else if (strcmp(alg, "wiki") == 0)
186 return WIKI;
187 #endif
188 else if (strcmp(alg, "quick") == 0)
189 return QUICK;
190 else if (strcmp(alg, "heap") == 0)
191 return HEAP;
192 else
193 return INVALID_ALG;
194 }
195
196 static enum test
parse_test(char * test)197 parse_test(char *test)
198 {
199 if (strcmp(test, "rand") == 0)
200 return RAND;
201 else if (strcmp(test, "sort") == 0)
202 return SORT;
203 else if (strcmp(test, "part") == 0)
204 return PART;
205 else if (strcmp(test, "rev") == 0)
206 return REV;
207 else
208 return INVALID_TEST;
209 }
210
211 static void
usage(const char * progname)212 usage(const char *progname)
213 {
214 printf("Usage:\n");
215 printf("\t%s: [alg] [test] [runs] [elt_power]\n", progname);
216 printf("\n");
217 printf("Valid algs:\n");
218 #ifdef WIKI
219 printf("\theap merge quick wiki\n");
220 #else
221 printf("\theap merge quick\n");
222 #endif
223 printf("Valid tests:\n");
224 printf("\trand sort part rev\n");
225 printf("\trand: Random element array \n");
226 printf("\tsort: Increasing order array \n");
227 printf("\tpart: Partially ordered array\n");
228 printf("\trev: Decreasing order array\n");
229 printf("Run the algorithm [runs] times with 2^[elt_power] elements\n");
230 exit(EX_USAGE);
231 }
232
233 /*
234 * Runs a sorting algorithm with a provided data configuration according to
235 * command line arguments
236 */
237 int
main(int argc,char * argv[])238 main(int argc, char *argv[])
239 {
240 const char *progname = argv[0];
241 int runs, elts;
242 if (argc != NARGS)
243 usage(progname);
244
245 enum sort s = parse_alg(argv[1]);
246 if (s == INVALID_ALG)
247 usage(progname);
248
249 enum test t = parse_test(argv[2]);
250 if (t == INVALID_TEST)
251 usage(progname);
252
253 runs = atoi(argv[3]);
254 elts = pow(2, atoi(argv[4]));
255
256 run_bench(s, t, runs, elts);
257 }
258