1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
#include <limits.h>
#include <stddef.h>
#include <stdlib.h>
#include "testcases.h"
int buffer[MAX_SIZE];
unsigned long comparisons;
void assert_sorted(size_t size, cmpfun cmp)
{
for (size_t i = 1; i < size; i++) {
if (cmp(buffer + i-1, buffer + i) > 0) abort();
}
}
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(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(size_t size)
{
for (size_t i = 0; i < size; i++) buffer[i] = i;
}
static void init_sorted2(size_t size)
{
size_t half = size / 2;
for (size_t i = 0; i < half; i++) buffer[i] = i;
for (size_t i = 0; i < size - half; i++) buffer[half+i] = i;
}
static void init_reverse(size_t size)
{
for (size_t i = 0; i < size; i++) buffer[i] = size - i - 1;
}
static void init_constant(size_t size)
{
for (size_t i = 0; i < size; i++) buffer[i] = 42;
}
static void add_noise(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(size_t size)
{
init_sorted(size);
add_noise(size);
}
static void init_reverse_noise(size_t size)
{
init_reverse(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 },
{ .name = "sorted-sorted", .init = init_sorted2, .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 },
{ .name = "qsort-killer", .init = init_qsk, .cmp = qsk_compare },
{ 0 }
};
|
