From f07937bb63ed12a50a203c3f8015649f37bc73e5 Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Sun, 3 Aug 2014 12:47:33 -0500 Subject: Rename generators to testcases This is in preparation for adding an implementation of the quicksort-killer test case, which requires a custom comparison function rather than just a custom imput-generation function. --- bench.c | 36 ++++++----------------- generators.c | 74 ----------------------------------------------- generators.h | 8 ------ testcases.c | 94 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ testcases.h | 17 +++++++++++ 5 files changed, 119 insertions(+), 110 deletions(-) delete mode 100644 generators.c delete mode 100644 generators.h create mode 100644 testcases.c create mode 100644 testcases.h diff --git a/bench.c b/bench.c index abcaca9..e0629b2 100644 --- a/bench.c +++ b/bench.c @@ -3,33 +3,13 @@ #include #include -#include "generators.h" +#include "testcases.h" #include "sorters.h" -#define MIN_SIZE 10000 -#define MAX_SIZE 10000000 - -static int buffer[MAX_SIZE]; -static unsigned long comparisons; - -static int compare(const void *a, const void *b) -{ - const int *aa = a; - const int *bb = b; - - comparisons++; - if (*aa < *bb) - return -1; - else if (*aa > *bb) - return 1; - else - return 0; -} - #define CMP_WIDTH 12 #define MS_WIDTH 6 #define SORT_WIDTH 16 -#define GEN_WIDTH (CMP_WIDTH + MS_WIDTH + 1) +#define TEST_WIDTH (CMP_WIDTH + MS_WIDTH + 1) #define SIZE_WIDTH 10 static inline unsigned long timediff_ms(struct timespec *start, struct timespec *stop) @@ -42,22 +22,22 @@ int main() struct timespec start, stop; printf("%-*s ", SORT_WIDTH, ""); - for (const struct generator *g = generators; g->name; g++) - printf("%*s ", GEN_WIDTH, g->name); + for (const struct testcase *t = testcases; t->name; t++) + printf("%*s ", TEST_WIDTH, t->name); printf(" %*s\n%-*s ", SIZE_WIDTH, "elements", SORT_WIDTH, ""); - for (const struct generator *g = generators; g->name; g++) + for (const struct testcase *t = testcases; t->name; t++) printf("%*s %*s ", CMP_WIDTH, "compares", MS_WIDTH, "ms"); puts(""); for (const struct sorter *s = sorters; s->name; s++) { for (size_t size = MIN_SIZE; size <= MAX_SIZE; size *= 10) { printf("%-*s ", SORT_WIDTH, size == MIN_SIZE ? s->name : ""); - for (const struct generator *g = generators; g->name; g++) { + for (const struct testcase *t = testcases; t->name; t++) { comparisons = 0; - g->func(buffer, size); + t->init(buffer, size); if (clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start)) abort(); - s->func(buffer, size, sizeof(int), compare); + s->func(buffer, size, sizeof(int), t->cmp); if (clock_gettime(CLOCK_THREAD_CPUTIME_ID, &stop)) abort(); printf("%*lu %*lu ", CMP_WIDTH, comparisons, MS_WIDTH, timediff_ms(&start, &stop)); diff --git a/generators.c b/generators.c deleted file mode 100644 index 4c73454..0000000 --- a/generators.c +++ /dev/null @@ -1,74 +0,0 @@ -#include -#include -#include - -#include "generators.h" - -static void generate_random(int *buffer, size_t size) -{ - srandom(1); - for (size_t i = 0; i < size; i++) buffer[i] = random(); - - /* compress the values to nice small numbers to make debugging nicer */ -#if 0 - int maxcompressed = -1; - for (size_t compressed = 0; compressed < size; compressed++) { - size_t minidx = -1; - for (size_t i = 0; i < size; i++) { - if (maxcompressed < buffer[i] && (minidx >= size || buffer[i] < buffer[minidx])) - minidx = i; - } - buffer[minidx] = ++maxcompressed; - } -#endif -} - -static void generate_sorted(int *buffer, size_t size) -{ - for (size_t i = 0; i < size; i++) buffer[i] = i; -} - -static void generate_reverse(int *buffer, size_t size) -{ - for (size_t i = 0; i < size; i++) buffer[i] = size - i - 1; -} - -static void generate_constant(int *buffer, size_t size) -{ - for (size_t i = 0; i < size; i++) buffer[i] = 42; -} - -static void add_noise(int *buffer, size_t size) -{ - int noisemax = size / 4; - int noiseoff = size / 8; - - srandom(1); - for (size_t i = 0; i < size; i++) { - if (random() < 0.2 * RAND_MAX) { - buffer[i] += random() % noisemax - noiseoff; - } - } -} - -static void generate_sorted_noise(int *buffer, size_t size) -{ - generate_sorted(buffer, size); - add_noise(buffer, size); -} - -static void generate_reverse_noise(int *buffer, size_t size) -{ - generate_reverse(buffer, size); - add_noise(buffer, size); -} - -const struct generator generators[] = { - { .name = "random", .func = generate_random }, - { .name = "sorted", .func = generate_sorted }, - { .name = "reverse", .func = generate_reverse }, - { .name = "constant", .func = generate_constant }, - { .name = "sorted+noise", .func = generate_sorted_noise }, - { .name = "reverse+noise", .func = generate_reverse_noise }, - { 0 } -}; diff --git a/generators.h b/generators.h deleted file mode 100644 index e08a0be..0000000 --- a/generators.h +++ /dev/null @@ -1,8 +0,0 @@ -#include - -typedef void (*generatorfn)(int *, size_t); - -extern const struct generator { - const char *name; - generatorfn func; -} generators[]; diff --git a/testcases.c b/testcases.c new file mode 100644 index 0000000..612d1c2 --- /dev/null +++ b/testcases.c @@ -0,0 +1,94 @@ +#include +#include +#include + +#include "testcases.h" + +#define MIN_SIZE 10000 +#define MAX_SIZE 10000000 + +int buffer[MAX_SIZE]; +unsigned long comparisons; + +static int compare(const void *a, const void *b) +{ + const int *aa = a; + const int *bb = b; + + comparisons++; + if (*aa < *bb) + return -1; + else if (*aa > *bb) + return 1; + else + return 0; +} + +static void init_random(int *buffer, size_t size) +{ + srandom(1); + for (size_t i = 0; i < size; i++) buffer[i] = random(); + + /* compress the values to nice small numbers to make debugging nicer */ +#if 0 + int maxcompressed = -1; + for (size_t compressed = 0; compressed < size; compressed++) { + size_t minidx = -1; + for (size_t i = 0; i < size; i++) { + if (maxcompressed < buffer[i] && (minidx >= size || buffer[i] < buffer[minidx])) + minidx = i; + } + buffer[minidx] = ++maxcompressed; + } +#endif +} + +static void init_sorted(int *buffer, size_t size) +{ + for (size_t i = 0; i < size; i++) buffer[i] = i; +} + +static void init_reverse(int *buffer, size_t size) +{ + for (size_t i = 0; i < size; i++) buffer[i] = size - i - 1; +} + +static void init_constant(int *buffer, size_t size) +{ + for (size_t i = 0; i < size; i++) buffer[i] = 42; +} + +static void add_noise(int *buffer, size_t size) +{ + int noisemax = size / 4; + int noiseoff = size / 8; + + srandom(1); + for (size_t i = 0; i < size; i++) { + if (random() < 0.2 * RAND_MAX) { + buffer[i] += random() % noisemax - noiseoff; + } + } +} + +static void init_sorted_noise(int *buffer, size_t size) +{ + init_sorted(buffer, size); + add_noise(buffer, size); +} + +static void init_reverse_noise(int *buffer, size_t size) +{ + init_reverse(buffer, size); + add_noise(buffer, size); +} + +const struct testcase testcases[] = { + { .name = "random", .init = init_random, .cmp = compare }, + { .name = "sorted", .init = init_sorted, .cmp = compare }, + { .name = "reverse", .init = init_reverse, .cmp = compare }, + { .name = "constant", .init = init_constant, .cmp = compare }, + { .name = "sorted+noise", .init = init_sorted_noise, .cmp = compare }, + { .name = "reverse+noise", .init = init_reverse_noise, .cmp = compare }, + { 0 } +}; diff --git a/testcases.h b/testcases.h new file mode 100644 index 0000000..036fe5d --- /dev/null +++ b/testcases.h @@ -0,0 +1,17 @@ +#include + +#include "sorters.h" + +#define MIN_SIZE 10000 +#define MAX_SIZE 10000000 + +extern int buffer[MAX_SIZE]; +extern unsigned long comparisons; + +typedef void (*testinit)(int *, size_t); + +extern const struct testcase { + const char *name; + testinit init; + cmpfun cmp; +} testcases[]; -- cgit v1.2.3