* 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:
*
- * SORT_MERGE merge items with identical keys, needs the following functions:
- * void PREFIX_write_merged(struct fastbuf *f, SORT_KEY **keys, uns n, byte *buf)
+ * SORT_UNIFY merge items with identical keys, needs the following functions:
+ * void PREFIX_write_merged(struct fastbuf *f, SORT_KEY **keys, void **data, uns n, void *buf)
* takes n records in memory with keys which compare equal and writes
- * a single record to the given fastbuf. Data for each key can
- * be accessed by the SORT_GET_DATA(*key) macro. `buf' points
- * to a buffer which is guaranteed to hold all given records.
+ * a single record to the given fastbuf. `buf' points to a buffer which
+ * is guaranteed to hold all given records.
* void PREFIX_copy_merged(SORT_KEY **keys, struct fastbuf **data, uns n, struct fastbuf *dest)
* takes n records with keys in memory and data in fastbufs and writes
* a single record.
* Input (choose one of these):
*
* SORT_INPUT_FILE file of a given name
- * SORT_INPUT_FB fastbuf stream
- * SORT_INPUT_PRESORT custom presorter: call function PREFIX_presorter (see below)
- * to get successive batches of pre-sorted data as temporary
- * fastbuf streams or NULL if no more data is available.
+ * 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.
* The function is passed a page-aligned presorting buffer.
+ * It returns 1 on success or 0 on EOF.
*
* Output (chose one of these):
*
*
* 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:
#endif
#endif
-#ifdef SORT_MERGE
+#ifdef SORT_UNIFY
#define LESS <
#else
#define LESS <=
#define SORT_ASSERT_UNIQUE
#endif
+#ifdef SORT_KEY_SIZE
+#define SORT_VAR_KEY
+#else
+#define SORT_KEY_SIZE(key) sizeof(key)
+#endif
+
+#ifdef SORT_DATA_SIZE
+#define SORT_VAR_DATA
+#else
+#define SORT_DATA_SIZE(key) 0
+#endif
+
static inline void P(copy_data)(P(key) *key, struct fastbuf *in, struct fastbuf *out)
{
- bwrite(out, key, sizeof(P(key)));
-#ifdef SORT_DATA_SIZE
+ P(write_key)(out, key);
+#ifdef SORT_VAR_DATA
bbcopy(in, out, SORT_DATA_SIZE(*key));
#else
(void) in;
#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,
#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(presorter);
+ ctx.custom_presort = P(presort);
+ ctx.in_size = ~(u64)0;
#else
#error No input given.
#endif
#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);
return ctx.out_fb;
}
+#undef SORT_PREFIX
#undef SORT_KEY
#undef SORT_KEY_REGULAR
#undef SORT_KEY_SIZE
#undef SORT_DATA_SIZE
+#undef SORT_VAR_KEY
+#undef SORT_VAR_DATA
#undef SORT_INT
#undef SORT_HASH_BITS
-#undef SORT_MERGE
+#undef SORT_UNIFY
#undef SORT_INPUT_FILE
#undef SORT_INPUT_FB
#undef SORT_INPUT_PRESORT