*/
/*
- * 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):
* 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
- * ASORT_HASH(x) FIXME
+ * 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
*
* 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"
#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 10 // FIXME: Tune automatically?
+#endif
+#define ASORT_RADIX_MASK ((1 << (ASORT_RADIX_BITS)) - 1)
+
+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;
*/
/* 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]))
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]))
}
}
+#ifdef ASORT_HASH
+
+static void Q(radix_count)(void *src_ptr, uns num_elts, uns *cnt, uns shift)
+{
+ Q(key) *src = src_ptr;
+ for (uns i=0; i<num_elts; i++)
+ cnt[ (ASORT_HASH(src[i]) >> shift) & ASORT_RADIX_MASK ] ++;
+}
+
+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;
+ for (uns i=0; i<num_elts; i++)
+ dest[ ptrs[ (ASORT_HASH(src[i]) >> shift) & ASORT_RADIX_MASK ]++ ] = src[i];
+}
+
+#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),
+#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 */
#undef ASORT_THRESHOLD
#undef ASORT_PAGE_ALIGNED
#undef ASORT_HASH
+#undef ASORT_RADIX_BITS
+#undef ASORT_RADIX_MASK
#undef Q