lib/sorter/s-fixint.h

   1 /*
   2  *      UCW Library -- Universal Sorter: Fixed-Size Internal Sorting Module
   3  *
   4  *      (c) 2007 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #include "lib/stkstring.h"
  11
  12 #define ASORT_PREFIX(x) SORT_PREFIX(array_##x)
  13 #define ASORT_KEY_TYPE P(key)
  14 #define ASORT_ELT(i) ary[i]
  15 #define ASORT_LT(x,y) (P(compare)(&(x), &(y)) < 0)
  16 #define ASORT_EXTRA_ARGS , P(key) *ary
  17 #include "lib/arraysort.h"
  18
  19 /*
  20  *  This is a more efficient implementation of the internal sorter,
  21  *  which runs under the following assumptions:
  22  *
  23  *     - the keys have fixed (and small) size
  24  *     - no data are present after the key
  25  *     - unification does not require any workspace
  26  */
  27
  28 static size_t P(internal_workspace)(void)
  29 {
  30   size_t workspace = 0;
  31 #ifdef CONFIG_UNIFY
  32   workspace = sizeof(P(key) *);
  33 #endif
  34 #if 0           // FIXME: Workspace for radix-sort if needed
  35   workspace = MAX(workspace, sizeof(P(key)));
  36 #endif
  37   return workspace;
  38 }
  39
  40 static uns P(internal_num_keys)(struct sort_context *ctx)
  41 {
  42   size_t bufsize = ctx->big_buf_size;
  43   size_t workspace = P(internal_workspace)();
  44   if (workspace)
  45     bufsize -= CPU_PAGE_SIZE;
  46   u64 maxkeys = bufsize / (sizeof(P(key)) + workspace);
  47   return MIN(maxkeys, ~0U);                                     // The number of records must fit in uns
  48 }
  49
  50 static int P(internal)(struct sort_context *ctx, struct sort_bucket *bin, struct sort_bucket *bout, struct sort_bucket *bout_only)
  51 {
  52   sorter_alloc_buf(ctx);
  53   struct fastbuf *in = sbuck_read(bin);
  54   P(key) *buf = ctx->big_buf;
  55   uns maxkeys = P(internal_num_keys)(ctx);
  56
  57   SORT_XTRACE(4, "s-fixint: Reading (maxkeys=%u)", maxkeys);
  58   uns n = 0;
  59   while (n < maxkeys && P(read_key)(in, &buf[n]))
  60     n++;
  61   if (!n)
  62     return 0;
  63   void *workspace UNUSED = ALIGN_PTR(&buf[n], CPU_PAGE_SIZE);
  64
  65   SORT_XTRACE(3, "s-fixint: Sorting %u items (%s items, %s workspace)",
  66         n,
  67         stk_fsize(n * sizeof(P(key))),
  68         stk_fsize(n * P(internal_workspace)()));
  69   timestamp_t timer;
  70   init_timer(&timer);
  71   P(array_sort)(n, buf);
  72   ctx->total_int_time += get_timer(&timer);
  73
  74   SORT_XTRACE(4, "s-fixint: Writing");
  75   if (n < maxkeys)
  76     bout = bout_only;
  77   struct fastbuf *out = sbuck_write(bout);
  78   bout->runs++;
  79   uns merged UNUSED = 0;
  80   for (uns i=0; i<n; i++)
  81     {
  82 #ifdef SORT_UNIFY
  83       if (i < n-1 && !P(compare)(&buf[i], &buf[i+1]))
  84         {
  85           P(key) **keys = workspace;
  86           uns n = 2;
  87           keys[0] = &buf[i];
  88           keys[1] = &buf[i+1];
  89           while (!P(compare)(&buf[i], &buf[i+n]))
  90             {
  91               keys[n] = &buf[i+n];
  92               n++;
  93             }
  94           P(write_merged)(out, keys, NULL, n, NULL);
  95           merged += n - 1;
  96           i += n - 1;
  97           continue;
  98         }
  99 #endif
 100 #ifdef SORT_ASSERT_UNIQUE
 101       ASSERT(i == n-1 || P(compare)(&buf[i], &buf[i+1]) < 0);
 102 #endif
 103       P(write_key)(out, &buf[i]);
 104     }
 105 #ifdef SORT_UNIFY
 106   SORT_XTRACE(3, "Merging reduced %d records", merged);
 107 #endif
 108
 109   return (n == maxkeys);
 110 }
 111
 112 static u64
 113 P(internal_estimate)(struct sort_context *ctx, struct sort_bucket *b UNUSED)
 114 {
 115   return P(internal_num_keys)(ctx) * sizeof(P(key)) - 1;        // -1 since if the buffer is full, we don't recognize EOF
 116 }