1 files changed, 94 insertions, 0 deletions
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 <limits.h>
+#include <stddef.h>
+#include <stdlib.h>
+
+#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 }
+};