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 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 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 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 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 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 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 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 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 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 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 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