Added a trivial implementation of radix sorting.

[libucw.git] / lib / sorter / sorter.h

diff --git a/lib/sorter/sorter.h b/lib/sorter/sorter.h
index f3b3a5cb5033a7beb67ad52340a2764e17fb0361..98dd8f776e3aa0bacc0e4423217c26a440ec328a 100644 (file)
--- a/lib/sorter/sorter.h
+++ b/lib/sorter/sorter.h
@@ -52,7 +52,7 @@
  *  SORT_HASH_BITS     signals that a monotone hashing function returning a given number of
  *                     bits is available. Monotone hash is a function f such that f(x) < f(y)
  *                     implies x < y and which is approximately uniformly distributed.
- *  uns PREFIX_hash(SORT_KEY *a, SORT_KEY *b)
+ *  uns PREFIX_hash(SORT_KEY *a)
  *
  *  Unification:
  *
@@ -68,7 +68,8 @@
  *  Input (choose one of these):
  *
  *  SORT_INPUT_FILE    file of a given name
- *  SORT_INPUT_FB      fastbuf stream
+ *  SORT_INPUT_FB      seekable fastbuf stream
+ *  SORT_INPUT_PIPE    non-seekable fastbuf stream
  *  SORT_INPUT_PRESORT custom presorter. Calls function
  *  int PREFIX_presort(struct fastbuf *dest, void *buf, size_t bufsize);
  *                     to get successive batches of pre-sorted data.
@@ -85,11 +86,6 @@
  *
  *  SORT_UNIQUE                all items have distinct keys (checked in debug mode)
  *
- *  FIXME: Maybe implement these:
- *  ??? SORT_DELETE_INPUT      a C expression, if true, the input files are
- *                     deleted as soon as possible
- *  ??? SORT_ALIGNED
- *
  *  The function generated:
  *
  *  <outfb> PREFIX_SORT(<in>, <out> [,<range>]), where:
@@ -168,7 +164,7 @@ static inline int P(hash) (P(key) *x)
 
 static inline void P(copy_data)(P(key) *key, struct fastbuf *in, struct fastbuf *out)
 {
-  bwrite(out, key, sizeof(P(key)));
+  P(write_key)(out, key);
 #ifdef SORT_VAR_DATA
   bbcopy(in, out, SORT_DATA_SIZE(*key));
 #else
@@ -179,6 +175,10 @@ static inline void P(copy_data)(P(key) *key, struct fastbuf *in, struct fastbuf
 #include "lib/sorter/s-internal.h"
 #include "lib/sorter/s-twoway.h"
 
+#if defined(SORT_HASH_BITS) || defined(SORT_INT)
+#include "lib/sorter/s-radix.h"
+#endif
+
 static struct fastbuf *P(sort)(
 #ifdef SORT_INPUT_FILE
                               byte *in,
@@ -200,11 +200,17 @@ static struct fastbuf *P(sort)(
 
 #ifdef SORT_INPUT_FILE
   ctx.in_fb = bopen(in, O_RDONLY, sorter_stream_bufsize);
+  ctx.in_size = bfilesize(ctx.in_fb);
 #elif defined(SORT_INPUT_FB)
   ctx.in_fb = in;
+  ctx.in_size = bfilesize(in);
+#elif defined(SORT_INPUT_PIPE)
+  ctx.in_fb = in;
+  ctx.in_size = ~(u64)0;
 #elif defined(SORT_INPUT_PRESORT)
   ASSERT(!in);
   ctx.custom_presort = P(presort);
+  ctx.in_size = ~(u64)0;
 #else
 #error No input given.
 #endif
@@ -221,10 +227,12 @@ static struct fastbuf *P(sort)(
 
 #ifdef SORT_HASH_BITS
   ctx.hash_bits = SORT_HASH_BITS;
+  ctx.radix_split = P(radix_split);
 #elif defined(SORT_INT)
   ctx.hash_bits = 0;
   while (ctx.hash_bits < 32 && (int_range >> ctx.hash_bits))
     ctx.hash_bits++;
+  ctx.radix_split = P(radix_split);
 #endif
 
   ctx.internal_sort = P(internal);
@@ -242,6 +250,7 @@ static struct fastbuf *P(sort)(
   return ctx.out_fb;
 }
 
+#undef SORT_PREFIX
 #undef SORT_KEY
 #undef SORT_KEY_REGULAR
 #undef SORT_KEY_SIZE