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 typedef struct P(mwt_node) {
  11   int i;
  12 #ifdef SORT_UNIFY
  13   int eq;
  14 #endif
  15 } P(mwt_node);
  16
  17 static inline void P(update_tree)(P(key) *keys, P(mwt_node) *tree, uns i)
  18 {
  19   while (i /= 2)
  20     {
  21       if (tree[2*i].i < 0)
  22         tree[i] = tree[2*i+1];
  23       else if (tree[2*i+1].i < 0)
  24         tree[i] = tree[2*i];
  25       else
  26         {
  27           int cmp = P(compare)(&keys[tree[2*i].i], &keys[tree[2*i+1].i]);
  28           tree[i] = (cmp <= 0) ? tree[2*i] : tree[2*i+1];
  29 #ifdef SORT_UNIFY
  30           if (!cmp)
  31             tree[i].eq = 1;
  32 #endif
  33         }
  34       /*
  35        * It is very tempting to stop as soon as the current node does not
  36        * change, but it is wrong, because even if the stream index stored in
  37        * the tree is the same, the actual key value can differ.
  38        */
  39     }
  40   ASSERT(tree[1].i < 16);
  41 }
  42
  43 static inline void P(set_tree)(P(key) *keys, P(mwt_node) *tree, uns i, int val)
  44 {
  45   tree[i].i = val;
  46   P(update_tree)(keys, tree, i);
  47 }
  48
  49 static void P(multiway_merge)(struct sort_context *ctx UNUSED, struct sort_bucket **ins, struct sort_bucket *out)
  50 {
  51   uns num_ins = 0;
  52   while (ins[num_ins])
  53     num_ins++;
  54
  55   uns n2 = 1;
  56   while (n2 < num_ins)
  57     n2 *= 2;
  58
  59   struct fastbuf *fout = sbuck_write(out);
  60   struct fastbuf *fins[num_ins];
  61   P(key) keys[num_ins];
  62   P(mwt_node) tree[2*n2];               // A complete binary tree, leaves are input streams, each internal vertex contains a minimum of its sons
  63   for (uns i=1; i<2*n2; i++)
  64     tree[i] = (P(mwt_node)) { .i = -1 };
  65
  66   for (uns i=0; i<num_ins; i++)
  67     {
  68       fins[i] = sbuck_read(ins[i]);
  69       if (P(read_key)(fins[i], &keys[i]))
  70         P(set_tree)(keys, tree, n2+i, i);
  71     }
  72
  73 #ifdef SORT_UNIFY
  74
  75   uns hits[num_ins];
  76   P(key) *mkeys[num_ins], *key;
  77   struct fastbuf *mfb[num_ins];
  78
  79   while (likely(tree[1].i >= 0))
  80     {
  81       int i = tree[1].i;
  82       if (!tree[1].eq)
  83         {
  84           /* The key is unique, so let's go through the fast path */
  85           P(copy_data)(&keys[i], fins[i], fout);
  86           if (unlikely(!P(read_key)(fins[i], &keys[i])))
  87             tree[n2+i].i = -1;
  88           P(update_tree)(keys, tree, n2+i);
  89           continue;
  90         }
  91
  92       uns m = 0;
  93       key = &keys[i];
  94       do
  95         {
  96           hits[m] = i;
  97           mkeys[m] = &keys[i];
  98           mfb[m] = fins[i];
  99           m++;
 100           P(set_tree)(keys, tree, n2+i, -1);
 101           i = tree[1].i;
 102           if (unlikely(i < 0))
 103             break;
 104         }
 105       while (!P(compare)(key, &keys[i]));
 106
 107       P(copy_merged)(mkeys, mfb, m, fout);
 108
 109       for (uns j=0; j<m; j++)
 110         {
 111           i = hits[j];
 112           if (likely(P(read_key)(fins[i], &keys[i])))
 113             P(set_tree)(keys, tree, n2+i, i);
 114         }
 115     }
 116
 117 #else
 118
 119   /* Simplified version which does not support any unification */
 120   while (likely(tree[1].i >= 0))
 121     {
 122       uns i = tree[1].i;
 123       P(key) UNUSED key = keys[i];
 124       P(copy_data)(&keys[i], fins[i], fout);
 125       if (unlikely(!P(read_key)(fins[i], &keys[i])))
 126         tree[n2+i].i = -1;
 127       P(update_tree)(keys, tree, n2+i);
 128 #ifdef SORT_ASSERT_UNIQUE
 129       ASSERT(tree[1].i < 0 || P(compare)(&key, &keys[tree[1].i]) < 0);
 130 #endif
 131     }
 132
 133 #endif
 134
 135   out->runs++;
 136 }