From 4e24c3e353b3352f5eee42455b8322da5be0718d Mon Sep 17 00:00:00 2001
From: millert <>
Date: Mon, 22 May 2017 17:16:43 +0000
Subject: Instead of embedding pre-generated tables from  McIlroy's "A Killer
 Adversary for Quicksort", just include the code to generate them. Also allow
 the number of elements to be specified on the command line.

---
 src/regress/lib/libc/qsort/antiqsort.c | 58 ++++++++++++++++++++++++++++++++++
 1 file changed, 58 insertions(+)
 create mode 100644 src/regress/lib/libc/qsort/antiqsort.c

(limited to 'src/regress/lib/libc/qsort/antiqsort.c')

diff --git a/src/regress/lib/libc/qsort/antiqsort.c b/src/regress/lib/libc/qsort/antiqsort.c
new file mode 100644
index 0000000000..cb3b7b2525
--- /dev/null
+++ b/src/regress/lib/libc/qsort/antiqsort.c
@@ -0,0 +1,58 @@
+/*
+ * A Killer Adversary for Quicksort
+ * M. D. MCILROY
+ * http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
+ *
+ * For comparison:
+ *  Bentley & McIlroy: 4096 items, 1645585 compares
+ *  random pivot:      4096 items, 8388649 compares
+ *  introsort:         4096 items, 151580 compares
+ *  heapsort:          4096 items, 48233 compares
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+static int *val;				/* item values */
+static int ncmp;				/* number of comparisons */
+static int nsolid;				/* number of solid items */
+static int candidate;				/* pivot candidate */
+static int gas;					/* gas value */
+
+#define freeze(x)	(val[(x)] = nsolid++)
+
+static int
+cmp(const void *px, const void *py)
+{
+	const int x = *(const int *)px;
+	const int y = *(const int *)py;
+
+	ncmp++;
+	if (val[x] == gas && val[y] == gas) {
+		if (x == candidate)
+			freeze(x);
+		else
+			freeze(y);
+	}
+	if (val[x] == gas)
+		candidate = x;
+	else if (val[y] == gas)
+		candidate = y;
+	return val[x] > val[y] ? 1 : val[x] < val[y] ? -1 : 0;
+}
+
+int
+antiqsort(int n, int *a, int *ptr)
+{
+	int i;
+
+	val = a;
+	gas = n - 1;
+	nsolid = ncmp = candidate = 0;
+	for (i = 0; i < n; i++) {
+		ptr[i] = i;
+		val[i] = gas;
+	}
+	qsort(ptr, n, sizeof(*ptr), cmp);
+	return ncmp;
+}
-- 
cgit v1.2.3-55-g6feb