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_LT(x,y) (P(compare)(&(x), &(y)) < 0)
  15 #define ASORT_PAGE_ALIGNED
  16 #ifdef SORT_INTERNAL_RADIX
  17 #  define ASORT_HASH(x) P(hash)(&(x))
  18 #    ifdef SORT_LONG_HASH
  19 #      define ASORT_LONG_HASH
  20 #    endif
  21 #endif
  22 #include "lib/sorter/array.h"
  23
  24 /*
  25  *  This is a more efficient implementation of the internal sorter,
  26  *  which runs under the following assumptions:
  27  *
  28  *     - the keys have fixed (and small) size
  29  *     - no data are present after the key
  30  *     - unification does not require any workspace
  31  */
  32
  33 static size_t P(internal_workspace)(void)
  34 {
  35   size_t workspace = 0;
  36 #ifdef SORT_UNIFY
  37   workspace = sizeof(P(key) *);
  38 #endif
  39 #ifdef SORT_INTERNAL_RADIX
  40   workspace = MAX(workspace, sizeof(P(key)));
  41 #endif
  42   return workspace;
  43 }
  44
  45 static uns P(internal_num_keys)(struct sort_context *ctx)
  46 {
  47   size_t bufsize = ctx->big_buf_size;
  48   size_t workspace = P(internal_workspace)();
  49   if (workspace)
  50     bufsize -= CPU_PAGE_SIZE;
  51   u64 maxkeys = bufsize / (sizeof(P(key)) + workspace);
  52   return MIN(maxkeys, ~0U);                                     // The number of records must fit in uns
  53 }
  54
  55 static int P(internal)(struct sort_context *ctx, struct sort_bucket *bin, struct sort_bucket *bout, struct sort_bucket *bout_only)
  56 {
  57   sorter_alloc_buf(ctx);
  58   struct fastbuf *in = sbuck_read(bin);
  59   P(key) *buf = ctx->big_buf;
  60   uns maxkeys = P(internal_num_keys)(ctx);
  61
  62   SORT_XTRACE(4, "s-fixint: Reading (maxkeys=%u, hash_bits=%d)", maxkeys, bin->hash_bits);
  63   uns n = 0;
  64   while (n < maxkeys && P(read_key)(in, &buf[n]))
  65     n++;
  66   if (!n)
  67     return 0;
  68   void *workspace UNUSED = ALIGN_PTR(&buf[n], CPU_PAGE_SIZE);
  69
  70   SORT_XTRACE(3, "s-fixint: Sorting %u items (%s items, %s workspace)",
  71         n,
  72         stk_fsize(n * sizeof(P(key))),
  73         stk_fsize(n * P(internal_workspace)()));
  74   timestamp_t timer;
  75   init_timer(&timer);
  76   buf = P(array_sort)(buf, n,
  77 #ifdef SORT_INTERNAL_RADIX
  78     workspace, bin->hash_bits
  79 #else
  80     NULL, 0
  81 #endif
  82     );
  83   ctx->total_int_time += get_timer(&timer);
  84
  85   SORT_XTRACE(4, "s-fixint: Writing");
  86   if (n < maxkeys)
  87     bout = bout_only;
  88   struct fastbuf *out = sbuck_write(bout);
  89   bout->runs++;
  90   uns merged UNUSED = 0;
  91   for (uns i=0; i<n; i++)
  92     {
  93 #ifdef SORT_UNIFY
  94       if (i < n-1 && !P(compare)(&buf[i], &buf[i+1]))
  95         {
  96           P(key) **keys = workspace;
  97           uns n = 2;
  98           keys[0] = &buf[i];
  99           keys[1] = &buf[i+1];
 100           while (!P(compare)(&buf[i], &buf[i+n]))
 101             {
 102               keys[n] = &buf[i+n];
 103               n++;
 104             }
 105           P(write_merged)(out, keys, NULL, n, NULL);
 106           merged += n - 1;
 107           i += n - 1;
 108           continue;
 109         }
 110 #endif
 111 #ifdef SORT_ASSERT_UNIQUE
 112       ASSERT(i == n-1 || P(compare)(&buf[i], &buf[i+1]) < 0);
 113 #endif
 114       P(write_key)(out, &buf[i]);
 115     }
 116 #ifdef SORT_UNIFY
 117   SORT_XTRACE(3, "Merging reduced %d records", merged);
 118 #endif
 119
 120   return (n == maxkeys);
 121 }
 122
 123 static u64
 124 P(internal_estimate)(struct sort_context *ctx, struct sort_bucket *b UNUSED)
 125 {
 126   return P(internal_num_keys)(ctx) * sizeof(P(key)) - 1;        // -1 since if the buffer is full, we don't recognize EOF
 127 }