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