* of the GNU Lesser General Public License.
*/
+#include "lib/stkstring.h"
+
#define ASORT_PREFIX(x) SORT_PREFIX(array_##x)
#define ASORT_KEY_TYPE P(key)
#define ASORT_ELT(i) ary[i]
#define ASORT_EXTRA_ARGS , P(key) *ary
#include "lib/arraysort.h"
+/*
+ * This is a more efficient implementation of the internal sorter,
+ * which runs under the following assumptions:
+ *
+ * - the keys have fixed (and small) size
+ * - no data are present after the key
+ * - unification does not require any workspace
+ */
+
+static size_t P(internal_workspace)(void)
+{
+ size_t workspace = 0;
+#ifdef CONFIG_UNIFY
+ workspace = sizeof(P(key) *);
+#endif
+#if 0 // FIXME: Workspace for radix-sort if needed
+ workspace = MAX(workspace, sizeof(P(key)));
+#endif
+ return workspace;
+}
+
+static uns P(internal_num_keys)(struct sort_context *ctx)
+{
+ size_t bufsize = ctx->big_buf_size;
+ size_t workspace = P(internal_workspace)();
+ if (workspace)
+ bufsize -= CPU_PAGE_SIZE;
+ u64 maxkeys = bufsize / (sizeof(P(key)) + workspace);
+ return MIN(maxkeys, ~0U); // The number of records must fit in uns
+}
+
static int P(internal)(struct sort_context *ctx, struct sort_bucket *bin, struct sort_bucket *bout, struct sort_bucket *bout_only)
{
sorter_alloc_buf(ctx);
struct fastbuf *in = sbuck_read(bin);
P(key) *buf = ctx->big_buf;
- size_t bufsize = ctx->big_buf_half_size; /* FIXME: In some cases, we can use the whole buffer */
-#ifdef CPU_64BIT_POINTERS
- bufsize = MIN((u64)bufsize, (u64)~0U * sizeof(P(key))); // The number of records must fit in uns
-#endif
- uns maxkeys = bufsize / sizeof(P(key));
+ uns maxkeys = P(internal_num_keys)(ctx);
- SORT_XTRACE(3, "s-fixint: Reading (maxkeys=%u)", maxkeys);
+ SORT_XTRACE(4, "s-fixint: Reading (maxkeys=%u)", maxkeys);
uns n = 0;
while (n < maxkeys && P(read_key)(in, &buf[n]))
n++;
+ if (!n)
+ return 0;
+ void *workspace UNUSED = ALIGN_PTR(&buf[n], CPU_PAGE_SIZE);
- SORT_XTRACE(3, "s-fixint: Sorting %u items", n);
+ SORT_XTRACE(3, "s-fixint: Sorting %u items (%s items, %s workspace)",
+ n,
+ stk_fsize(n * sizeof(P(key))),
+ stk_fsize(n * P(internal_workspace)()));
+ timestamp_t timer;
+ init_timer(&timer);
P(array_sort)(n, buf);
+ ctx->total_int_time += get_timer(&timer);
- SORT_XTRACE(3, "s-fixint: Writing");
- struct fastbuf *out = sbuck_write((n < maxkeys) ? bout_only : bout);
+ SORT_XTRACE(4, "s-fixint: Writing");
+ if (n < maxkeys)
+ bout = bout_only;
+ struct fastbuf *out = sbuck_write(bout);
bout->runs++;
uns merged UNUSED = 0;
for (uns i=0; i<n; i++)
#ifdef SORT_UNIFY
if (i < n-1 && !P(compare)(&buf[i], &buf[i+1]))
{
- ASSERT(0); /* FIXME: Implement */
+ P(key) **keys = workspace;
+ uns n = 2;
+ keys[0] = &buf[i];
+ keys[1] = &buf[i+1];
+ while (!P(compare)(&buf[i], &buf[i+n]))
+ {
+ keys[n] = &buf[i+n];
+ n++;
+ }
+ P(write_merged)(out, keys, NULL, n, NULL);
+ merged += n - 1;
+ i += n - 1;
continue;
}
#endif
static u64
P(internal_estimate)(struct sort_context *ctx, struct sort_bucket *b UNUSED)
{
- return ctx->big_buf_half_size;
+ return P(internal_num_keys)(ctx) * sizeof(P(key)) - 1; // -1 since if the buffer is full, we don't recognize EOF
}