X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Fsorter%2Farray.h;h=aa0e2266f990c2449063b2412b018343a357a71e;hb=c0544008a494710146ac6cf88b61b5fd2d46f51b;hp=73da6908df5af00f4182fb3c046f05b5ee6110cb;hpb=0ce1209ffd78ede3a5d353393e281cc6a7995cd3;p=libucw.git

diff --git a/lib/sorter/array.h b/lib/sorter/array.h
index 73da6908..aa0e2266 100644
--- a/lib/sorter/array.h
+++ b/lib/sorter/array.h
@@ -8,11 +8,14 @@
  */
 
 /*
- *  This is a generator of routines for sorting arrays, very similar to the one
- *  in lib/arraysort.h.
+ *  This is a generator of routines for sorting huge arrays, similar to the one
+ *  in lib/arraysort.h. It cannot handle discontiguous arrays, but it is able
+ *  to employ radix-sorting if a monotone hash function is available and also
+ *  use several threads in parallel on SMP systems (this assumes that all
+ *  callbacks you provide are thread-safe).
  *
- *  FIXME: <comments>
- *  FIXME: Note on thread-safety
+ *  It is usually called internally by the generic shorter machinery, but
+ *  you are free to use it explicitly if you need.
  *
  *  So much for advocacy, there are the parameters (those marked with [*]
  *  are mandatory):
@@ -21,14 +24,23 @@
  *			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_HASH(x)	a monotone hash function (safisfying hash(x) < hash(y) => x<y)
+ *  ASORT_LONG_HASH	hashes are 64-bit numbers (default is 32 bits)
+ *
+ *  Fine-tuning parameters: (if you really insist)
+ *
  *  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
- *  ASORT_HASH(x)	FIXME
- *  ASORT_SWAP		FIXME: probably keep private
+ *  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)
- *  is declared and all parameter macros are automatically undef'd.
+ *  is declared and all parameter macros are automatically undef'd. Here `buf' is an
+ *  auxiliary buffer of the same size as the input array, required whenever radix
+ *  sorting should be used, and `hash_bits' is the number of significant bits returned
+ *  by the hash function. If the buffer is specified, the sorting function returns either
+ *  a pointer to the input array or to the buffer, depending on where the result is stored.
+ *  If you do not use hashing, these parameters should be NULL and 0, respectively.
  */
 
 #include "lib/sorter/common.h"
@@ -49,20 +61,26 @@ typedef ASORT_KEY_TYPE Q(key);
 #define ASORT_THRESHOLD 8		/* Guesswork and experimentation */
 #endif
 
-static void Q(raw_sort)(Q(key) *array, uns array_size)
+#ifndef ASORT_RADIX_BITS
+#define ASORT_RADIX_BITS 12		// FIXME: Tune automatically?
+#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;
   struct stk { int l, r; } stack[8*sizeof(uns)];
   int l, r, left, right, m;
   uns sp = 0;
   Q(key) pivot;
 
-  if (array_size <= 1)
+  if (num_elts <= 1)
     return;
 
-  /* QuickSort with optimizations a'la Sedgewick, but stop at ASORT_THRESHOLD */
-
   left = 0;
-  right = array_size - 1;
+  right = num_elts - 1;
   for(;;)
     {
       l = left;
@@ -140,7 +158,7 @@ static void Q(raw_sort)(Q(key) *array, uns array_size)
    */
 
   /* Find minimal element which will serve as a barrier */
-  r = MIN(array_size, ASORT_THRESHOLD);
+  r = MIN(num_elts, ASORT_THRESHOLD);
   m = 0;
   for (l=1; l<r; l++)
     if (ASORT_LT(array[l], array[m]))
@@ -148,7 +166,7 @@ static void Q(raw_sort)(Q(key) *array, uns array_size)
   ASORT_SWAP(0,m);
 
   /* Insertion sort */
-  for (m=1; m<(int)array_size; m++)
+  for (m=1; m<(int)num_elts; m++)
     {
       l=m;
       while (ASORT_LT(array[m], array[l-1]))
@@ -161,12 +179,129 @@ static void Q(raw_sort)(Q(key) *array, uns array_size)
     }
 }
 
+/* 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)
+{
+  Q(key) *src = src_ptr;
+  uns i;
+
+  switch (shift)
+    {
+#define RC(s) \
+    case s:								\
+      for (i=0; i<num_elts; i++)					\
+	cnt[ (ASORT_HASH(src[i]) >> s) & ASORT_RADIX_MASK ] ++;		\
+      break;								\
+
+#ifdef ASORT_LONG_HASH
+      RC(63); RC(62); RC(61); RC(60); RC(59); RC(58); RC(57); RC(56);
+      RC(55); RC(54); RC(53); RC(52); RC(51); RC(50); RC(49); RC(48);
+      RC(47); RC(46); RC(45); RC(44); RC(43); RC(42); RC(41); RC(40);
+      RC(39); RC(38); RC(37); RC(36); RC(35); RC(34); RC(33); RC(32);
+#endif
+      RC(31); RC(30); RC(29); RC(28); RC(27); RC(26); RC(25); RC(24);
+      RC(23); RC(22); RC(21); RC(20); RC(19); RC(18); RC(17); RC(16);
+      RC(15); RC(14); RC(13); RC(12); RC(11); RC(10); RC(9); RC(8);
+      RC(7); RC(6); RC(5); RC(4); RC(3); RC(2); RC(1); RC(0);
+    default:
+      ASSERT(0);
+    }
+#undef RC
+}
+
+static void Q(radix_split)(void *src_ptr, void *dest_ptr, uns num_elts, uns *ptrs, uns shift)
+{
+  Q(key) *src = src_ptr, *dest = dest_ptr;
+  uns i;
+
+  switch (shift)
+    {
+#define RS(s) \
+    case s:										\
+      for (i=0; i<num_elts; i++)							\
+	dest[ ptrs[ (ASORT_HASH(src[i]) >> s) & ASORT_RADIX_MASK ]++ ] = src[i];	\
+      break;
+
+#ifdef ASORT_LONG_HASH
+      RS(63); RS(62); RS(61); RS(60); RS(59); RS(58); RS(57); RS(56);
+      RS(55); RS(54); RS(53); RS(52); RS(51); RS(50); RS(49); RS(48);
+      RS(47); RS(46); RS(45); RS(44); RS(43); RS(42); RS(41); RS(40);
+      RS(39); RS(38); RS(37); RS(36); RS(35); RS(34); RS(33); RS(32);
+#endif
+      RS(31); RS(30); RS(29); RS(28); RS(27); RS(26); RS(25); RS(24);
+      RS(23); RS(22); RS(21); RS(20); RS(19); RS(18); RS(17); RS(16);
+      RS(15); RS(14); RS(13); RS(12); RS(11); RS(10); RS(9); RS(8);
+      RS(7); RS(6); RS(5); RS(4); RS(3); RS(2); RS(1); RS(0);
+    default:
+      ASSERT(0);
+    }
+#undef RS
+}
+
+#endif
+
 static Q(key) *Q(sort)(Q(key) *array, uns num_elts, Q(key) *buffer, uns hash_bits)
 {
-  (void) buffer;
-  (void) hash_bits;
-  Q(raw_sort)(array, num_elts);
-  return array;
+  struct asort_context ctx = {
+    .array = array,
+    .buffer = buffer,
+    .num_elts = num_elts,
+    .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),
+    .radix_bits = ASORT_RADIX_BITS,
+#endif
+  };
+  asort_run(&ctx);
+  return ctx.array;
 }
 
 /* FIXME */
@@ -177,4 +312,7 @@ static Q(key) *Q(sort)(Q(key) *array, uns num_elts, Q(key) *buffer, uns hash_bit
 #undef ASORT_THRESHOLD
 #undef ASORT_PAGE_ALIGNED
 #undef ASORT_HASH
+#undef ASORT_RADIX_BITS
+#undef ASORT_RADIX_MASK
+#undef ASORT_LONG_HASH
 #undef Q