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 #define ASORT_PREFIX(x) SORT_PREFIX(array_##x)
  11 #define ASORT_KEY_TYPE P(key)
  12 #define ASORT_ELT(i) ary[i]
  13 #define ASORT_LT(x,y) (P(compare)(&(x), &(y)) < 0)
  14 #define ASORT_EXTRA_ARGS , P(key) *ary
  15 #include "lib/arraysort.h"
  16
  17 static int P(internal_num_keys)(struct sort_context *ctx)
  18 {
  19   size_t bufsize = ctx->big_buf_half_size;
  20 #ifdef SORT_UNIFY
  21   // When we promise unification, we have to reduce the number of records
  22   // to be sure that both pointers and merged records fit in the 2nd half
  23   // of the big_buf. So we eat as much memory as s-internal.h, but still
  24   // we are faster.
  25   u64 maxkeys = bufsize / (sizeof(P(key)) + sizeof(void *));
  26 #else
  27   u64 maxkeys = bufsize / sizeof(P(key));
  28 #endif
  29   return MIN(maxkeys, ~0U);                                     // The number of records must fit in uns
  30 }
  31
  32 static int P(internal)(struct sort_context *ctx, struct sort_bucket *bin, struct sort_bucket *bout, struct sort_bucket *bout_only)
  33 {
  34   sorter_alloc_buf(ctx);
  35   struct fastbuf *in = sbuck_read(bin);
  36   P(key) *buf = ctx->big_buf;
  37   uns maxkeys = P(internal_num_keys)(ctx);
  38
  39   SORT_XTRACE(3, "s-fixint: Reading (maxkeys=%u)", maxkeys);
  40   uns n = 0;
  41   while (n < maxkeys && P(read_key)(in, &buf[n]))
  42     n++;
  43   if (!n)
  44     return 0;
  45
  46   SORT_XTRACE(3, "s-fixint: Sorting %u items", n);
  47   timestamp_t timer;
  48   init_timer(&timer);
  49   P(array_sort)(n, buf);
  50   ctx->total_int_time += get_timer(&timer);
  51
  52   SORT_XTRACE(3, "s-fixint: Writing");
  53   if (n < maxkeys)
  54     bout = bout_only;
  55   struct fastbuf *out = sbuck_write(bout);
  56   bout->runs++;
  57   uns merged UNUSED = 0;
  58   for (uns i=0; i<n; i++)
  59     {
  60 #ifdef SORT_UNIFY
  61       if (i < n-1 && !P(compare)(&buf[i], &buf[i+1]))
  62         {
  63           P(key) **keys = ctx->big_buf_half;
  64           uns n = 2;
  65           keys[0] = &buf[i];
  66           keys[1] = &buf[i+1];
  67           while (!P(compare)(&buf[i], &buf[i+n]))
  68             {
  69               keys[n] = &buf[i+n];
  70               n++;
  71             }
  72           P(write_merged)(out, keys, NULL, n, keys+n);
  73           merged += n - 1;
  74           i += n - 1;
  75           continue;
  76         }
  77 #endif
  78 #ifdef SORT_ASSERT_UNIQUE
  79       ASSERT(i == n-1 || P(compare)(&buf[i], &buf[i+1]) < 0);
  80 #endif
  81       P(write_key)(out, &buf[i]);
  82     }
  83 #ifdef SORT_UNIFY
  84   SORT_XTRACE(3, "Merging reduced %d records", merged);
  85 #endif
  86
  87   return (n == maxkeys);
  88 }
  89
  90 static u64
  91 P(internal_estimate)(struct sort_context *ctx, struct sort_bucket *b UNUSED)
  92 {
  93   return P(internal_num_keys)(ctx) * sizeof(P(key)) - 1;        // -1 since if the buffer is full, we don't recognize EOF
  94 }