lib/sorter/s-multiway.h

   1 /*
   2  *      UCW Library -- Universal Sorter: Multi-Way Merge 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 static inline void P(update_tree)(P(key) *keys, int *tree, uns i)
  11 {
  12   while (i /= 2)
  13     {
  14       if (tree[2*i] < 0)
  15         tree[i] = tree[2*i+1];
  16       else if (tree[2*i+1] < 0)
  17         tree[i] = tree[2*i];
  18       else if (P(compare)(&keys[tree[2*i]], &keys[tree[2*i+1]]) <= 0)
  19         tree[i] = tree[2*i];
  20       else
  21         tree[i] = tree[2*i+1];
  22     }
  23 }
  24
  25 static void P(multiway_merge)(struct sort_context *ctx UNUSED, struct sort_bucket **ins, uns num_ins, struct sort_bucket *out)
  26 {
  27   uns n2 = 1;
  28   while (n2 < num_ins)
  29     n2 *= 2;
  30
  31   struct fastbuf *fout = sbuck_write(out);
  32   struct fastbuf *fins[num_ins];
  33   P(key) keys[num_ins];         // FIXME: Tune num_ins according to L1 cache size
  34   int tree[2*n2];               // A complete binary tree, leaves are input streams, each internal vertex contains a minimum of its sons
  35   for (uns i=1; i<=n2; i++)
  36     tree[i] = -1;
  37
  38   for (uns i=0; i<num_ins; i++)
  39     {
  40       fins[i] = sbuck_read(ins[i]);
  41       if (P(read_key)(fins[i], &keys[i]))
  42         {
  43           tree[n2+i] = i;
  44           P(update_tree)(keys, tree, n2+i);
  45         }
  46     }
  47
  48   while (tree[1] >= 0)
  49     {
  50       uns i = tree[1];
  51       P(copy_data)(&keys[i], fins[i], fout);
  52       if (unlikely(!P(read_key)(fins[i], &keys[i])))
  53         tree[n2+i] = -1;
  54       P(update_tree)(keys, tree, n2+i);
  55     }
  56
  57 #if 0
  58 #ifdef SORT_ASSERT_UNIQUE
  59   ASSERT(comp != 0);
  60 #endif
  61 #ifdef SORT_UNIFY
  62   if (comp == 0)
  63     {
  64       P(key) *mkeys[] = { kin1, kin2 };
  65       struct fastbuf *mfb[] = { fin1, fin2 };
  66       P(copy_merged)(mkeys, mfb, 2, fout1);
  67       SWAP(kin1, kprev1, ktmp);
  68       next1 = P(read_key)(fin1, kin1);
  69       run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
  70       SWAP(kin2, kprev2, ktmp);
  71       next2 = P(read_key)(fin2, kin2);
  72       run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
  73       kout = kprev2;
  74     }
  75 #endif
  76 #endif
  77
  78   out->runs++;
  79 }