From 556cfa14c25a4124673e2a7489308e82021cf58b Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Fri, 7 Sep 2007 12:30:18 +0200
Subject: [PATCH] Cleanup of array sorter interface and added quicksplit.

---
 lib/sorter/array.h      | 58 ++++++++++++++++++++++++++++++++++++-----
 lib/sorter/common.h     |  1 +
 lib/sorter/s-fixint.h   |  1 -
 lib/sorter/s-internal.h |  1 -
 4 files changed, 53 insertions(+), 8 deletions(-)

diff --git a/lib/sorter/array.h b/lib/sorter/array.h
index ef1d0551..aa75e05a 100644
--- a/lib/sorter/array.h
+++ b/lib/sorter/array.h
@@ -24,11 +24,13 @@
  *			defined by the sorter)
  *  ASORT_KEY_TYPE  [*]	data type of a single array entry key
  *  ASORT_LT(x,y)	x < y for ASORT_TYPE (default: "x<y")
- *  ASORT_THRESHOLD	threshold for switching between quicksort and insertsort
- *  ASORT_PAGE_ALIGNED	the array is guaranteed to be aligned to a multiple of CPU_PAGE_SIZE  (FIXME: Do we need this?)
  *  ASORT_HASH(x)	a monotone hash function (safisfying hash(x) < hash(y) => x<y)
- *  ASORT_RADIX_BITS	FIXME
- *  ASORT_SWAP		FIXME: probably keep private
+ *
+ *  Fine-tuning parameters: (if you really insist)
+ *
+ *  ASORT_THRESHOLD	threshold for switching between quicksort and insertsort
+ *  ASORT_RADIX_BITS	how many bits of the hash functions are to be used at once for
+ *			radix-sorting.
  *
  *  After including this file, a function
  * 	ASORT_KEY_TYPE *ASORT_PREFIX(sort)(ASORT_KEY_TYPE *array, uns num_elts, ASORT_KEY_TYPE *buf, uns hash_bits)
@@ -63,6 +65,8 @@ typedef ASORT_KEY_TYPE Q(key);
 #endif
 #define ASORT_RADIX_MASK ((1 << (ASORT_RADIX_BITS)) - 1)
 
+/* QuickSort with optimizations a'la Sedgewick, inspired by qsort() from GNU libc. */
+
 static void Q(quicksort)(void *array_ptr, uns num_elts)
 {
   Q(key) *array = array_ptr;
@@ -74,8 +78,6 @@ static void Q(quicksort)(void *array_ptr, uns num_elts)
   if (num_elts <= 1)
     return;
 
-  /* QuickSort with optimizations a'la Sedgewick, but stop at ASORT_THRESHOLD */
-
   left = 0;
   right = num_elts - 1;
   for(;;)
@@ -176,6 +178,49 @@ static void Q(quicksort)(void *array_ptr, uns num_elts)
     }
 }
 
+/* Just the splitting part of QuickSort */
+
+static void Q(quicksplit)(void *array_ptr, uns num_elts, uns *leftp, uns *rightp)
+{
+  Q(key) *array = array_ptr;
+  int l, r, m;
+  Q(key) pivot;
+
+  l = 0;
+  r = num_elts - 1;
+  m = (l+r)/2;
+  if (ASORT_LT(array[m], array[l]))
+    ASORT_SWAP(l,m);
+  if (ASORT_LT(array[r], array[m]))
+    {
+      ASORT_SWAP(m,r);
+      if (ASORT_LT(array[m], array[l]))
+	ASORT_SWAP(l,m);
+    }
+  pivot = array[m];
+  do
+    {
+      while (ASORT_LT(array[l], pivot))
+	l++;
+      while (ASORT_LT(pivot, array[r]))
+	r--;
+      if (l < r)
+	{
+	  ASORT_SWAP(l,r);
+	  l++;
+	  r--;
+	}
+      else if (l == r)
+	{
+	  l++;
+	  r--;
+	}
+    }
+  while (l <= r);
+  *leftp = l;
+  *rightp = r;
+}
+
 #ifdef ASORT_HASH
 
 static void Q(radix_count)(void *src_ptr, uns num_elts, uns *cnt, uns shift)
@@ -203,6 +248,7 @@ static Q(key) *Q(sort)(Q(key) *array, uns num_elts, Q(key) *buffer, uns hash_bit
     .hash_bits = hash_bits,
     .elt_size = sizeof(Q(key)),
     .quicksort = Q(quicksort),
+    .quicksplit = Q(quicksplit),
 #ifdef ASORT_HASH
     .radix_count = Q(radix_count),
     .radix_split = Q(radix_split),
diff --git a/lib/sorter/common.h b/lib/sorter/common.h
index b8438ff7..f3ff562a 100644
--- a/lib/sorter/common.h
+++ b/lib/sorter/common.h
@@ -126,6 +126,7 @@ struct asort_context {
   uns hash_bits;			// Remaining bits of hash function
   uns radix_bits;			// How many bits to process in a single radix-sort pass
   void (*quicksort)(void *array_ptr, uns num_elts);
+  void (*quicksplit)(void *array_ptr, uns num_elts, uns *leftp, uns *rightp);
   void (*radix_count)(void *src_ptr, uns num_elts, uns *cnt, uns shift);
   void (*radix_split)(void *src_ptr, void *dest_ptr, uns num_elts, uns *ptrs, uns shift);
 };
diff --git a/lib/sorter/s-fixint.h b/lib/sorter/s-fixint.h
index 7aafa7de..de152b0a 100644
--- a/lib/sorter/s-fixint.h
+++ b/lib/sorter/s-fixint.h
@@ -12,7 +12,6 @@
 #define ASORT_PREFIX(x) SORT_PREFIX(array_##x)
 #define ASORT_KEY_TYPE P(key)
 #define ASORT_LT(x,y) (P(compare)(&(x), &(y)) < 0)
-#define ASORT_PAGE_ALIGNED
 #ifdef SORT_INTERNAL_RADIX
 #define ASORT_HASH(x) P(hash)(&(x))
 #endif
diff --git a/lib/sorter/s-internal.h b/lib/sorter/s-internal.h
index 85557f12..765ed4b9 100644
--- a/lib/sorter/s-internal.h
+++ b/lib/sorter/s-internal.h
@@ -17,7 +17,6 @@ typedef struct {
 #define ASORT_PREFIX(x) SORT_PREFIX(array_##x)
 #define ASORT_KEY_TYPE P(internal_item_t)
 #define ASORT_LT(x,y) (P(compare)((x).key, (y).key) < 0)
-#define ASORT_PAGE_ALIGNED
 #include "lib/sorter/array.h"
 
 /*
-- 
2.39.2