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.

1 files changed, 58 insertions, 0 deletions

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;
+}