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)(struct sort_context *ctx, struct sort_bucket *bin, struct sort_bucket *bout, struct sort_bucket *bout_only)
  18 {
  19   sorter_alloc_buf(ctx);
  20   struct fastbuf *in = sbuck_read(bin);
  21   P(key) *buf = ctx->big_buf;
  22   size_t bufsize = ctx->big_buf_half_size;
  23 #ifdef CPU_64BIT_POINTERS
  24   bufsize = MIN((u64)bufsize, (u64)~0U * sizeof(P(key)));       // The number of records must fit in uns
  25 #endif
  26   uns maxkeys = bufsize / sizeof(P(key));
  27
  28   SORT_XTRACE(3, "s-fixint: Reading (maxkeys=%u)", maxkeys);
  29   uns n = 0;
  30   while (n < maxkeys && P(read_key)(in, &buf[n]))
  31     n++;
  32
  33   SORT_XTRACE(3, "s-fixint: Sorting %u items", n);
  34   P(array_sort)(n, buf);
  35
  36   SORT_XTRACE(3, "s-fixint: Writing");
  37   struct fastbuf *out = sbuck_write((n < maxkeys) ? bout_only : bout);
  38   bout->runs++;
  39   uns merged UNUSED = 0;
  40   for (uns i=0; i<n; i++)
  41     {
  42 #ifdef SORT_UNIFY
  43       if (i < n-1 && !P(compare)(&buf[i], &buf[i+1]))
  44         {
  45           ASSERT(0);                    /* FIXME: Implement */
  46           continue;
  47         }
  48 #endif
  49 #ifdef SORT_ASSERT_UNIQUE
  50       ASSERT(i == n-1 || P(compare)(&buf[i], &buf[i+1]) < 0);
  51 #endif
  52       P(write_key)(out, &buf[i]);
  53     }
  54 #ifdef SORT_UNIFY
  55   SORT_XTRACE(3, "Merging reduced %d records", merged);
  56 #endif
  57
  58   return (n == maxkeys);
  59 }
  60
  61 static u64
  62 P(internal_estimate)(struct sort_context *ctx, struct sort_bucket *b UNUSED)
  63 {
  64   return ctx->big_buf_half_size - 1;    // -1 since if the buffer is full, we don't recognize EOF
  65 }