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