diff options
| -rw-r--r-- | testcases.c | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/testcases.c b/testcases.c index eba3983..b40fa5a 100644 --- a/testcases.c +++ b/testcases.c @@ -90,6 +90,36 @@ static void init_reverse_noise(size_t size) add_noise(size); } +/* quicksort-killer testcase from http://www.cs.dartmouth.edu/~doug/mdmspe.pdf */ +static int qsk_buffer[MAX_SIZE]; +static size_t qsk_nsolid; +static size_t qsk_candidate; + +static void init_qsk(size_t size) +{ + qsk_nsolid = qsk_candidate = 0; + for (size_t i = 0; i < size; i++) { + qsk_buffer[i] = INT_MAX; + buffer[i] = i; + } +} + +static int qsk_compare(const void *a, const void *b) +{ + const int x = *(const int*)a; + const int y = *(const int*)b; + + if (qsk_buffer[x] == INT_MAX && qsk_buffer[y] == INT_MAX) { + if (qsk_buffer[x] == INT_MAX) qsk_buffer[x] = qsk_nsolid++; + else qsk_buffer[y] = qsk_nsolid++; + } + + if (qsk_buffer[x] == INT_MAX) qsk_candidate = x; + else if (qsk_buffer[y] == INT_MAX) qsk_candidate = y; + + return compare(qsk_buffer + x, qsk_buffer + y); +} + const struct testcase testcases[] = { { .name = "random", .init = init_random, .cmp = compare }, { .name = "sorted", .init = init_sorted, .cmp = compare }, @@ -97,5 +127,6 @@ const struct testcase testcases[] = { { .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 }, + { .name = "qsort-killer", .init = init_qsk, .cmp = qsk_compare }, { 0 } }; |