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 /*
  11  * We use a binary tree to keep track of the current minimum. The tree is
  12  * represented by an array (in the same way as binary heaps usually are),
  13  * leaves correspond to input streams and each internal vertex remembers
  14  * the leaf in its subtree, which has the lowest key.
  15  */
  16
  17 typedef struct P(mwt) {
  18   int i;                // Minimum of the subtree
  19 #ifdef SORT_UNIFY
  20   int eq;               // Did we encounter equality anywhere in the subtree?
  21 #endif
  22 } P(mwt);
  23
  24 static inline void P(update_tree)(P(key) *keys, P(mwt) *tree, uns i)
  25 {
  26   while (i /= 2)
  27     {
  28       if (tree[2*i].i < 0)
  29         tree[i] = tree[2*i+1];
  30       else if (tree[2*i+1].i < 0)
  31         tree[i] = tree[2*i];
  32       else
  33         {
  34           int cmp = P(compare)(&keys[tree[2*i].i], &keys[tree[2*i+1].i]);
  35           tree[i] = (cmp <= 0) ? tree[2*i] : tree[2*i+1];
  36 #ifdef SORT_UNIFY
  37           if (!cmp)
  38             tree[i].eq = 1;
  39 #endif
  40         }
  41       /*
  42        * It is very tempting to stop as soon as the current node does not
  43        * change, but it is wrong, because even if the stream index stored in
  44        * the tree is the same, the actual key value can differ.
  45        */
  46     }
  47 #if defined(__GNUC__) && (__GNUC__ * 1000 + __GNUC_MINOR__ < 4002)
  48   /*
  49    * This function sometimes triggers optimizer bugs in GCC 4.1.1 and
  50    * possibly also earlier versions, leading to an assumption that tree[1]
  51    * does not change during this function. We add an explicit memory barrier
  52    * as a work-around. Ugh.
  53    */
  54   asm volatile ("" : : : "memory");
  55 #endif
  56 }
  57
  58 static inline void P(set_tree)(P(key) *keys, P(mwt) *tree, uns i, int val)
  59 {
  60   tree[i].i = val;
  61   P(update_tree)(keys, tree, i);
  62 }
  63
  64 static void P(multiway_merge)(struct sort_context *ctx UNUSED, struct sort_bucket **ins, struct sort_bucket *out)
  65 {
  66   uns num_ins = 0;
  67   while (ins[num_ins])
  68     num_ins++;
  69
  70   uns n2 = 1;
  71   while (n2 < num_ins)
  72     n2 *= 2;
  73
  74   struct fastbuf *fout = sbuck_write(out);
  75   struct fastbuf *fins[num_ins];
  76   P(key) keys[num_ins];
  77   P(mwt) tree[2*n2];
  78   for (uns i=1; i<2*n2; i++)
  79     tree[i] = (P(mwt)) { .i = -1 };
  80
  81   for (uns i=0; i<num_ins; i++)
  82     {
  83       fins[i] = sbuck_read(ins[i]);
  84       if (P(read_key)(fins[i], &keys[i]))
  85         P(set_tree)(keys, tree, n2+i, i);
  86     }
  87
  88 #ifdef SORT_UNIFY
  89
  90   uns hits[num_ins];
  91   P(key) *mkeys[num_ins], *key;
  92   struct fastbuf *mfb[num_ins];
  93
  94   while (likely(tree[1].i >= 0))
  95     {
  96       int i = tree[1].i;
  97       if (!tree[1].eq)
  98         {
  99           /* The key is unique, so let's go through the fast path */
 100           P(copy_data)(&keys[i], fins[i], fout);
 101           if (unlikely(!P(read_key)(fins[i], &keys[i])))
 102             tree[n2+i].i = -1;
 103           P(update_tree)(keys, tree, n2+i);
 104           continue;
 105         }
 106
 107       uns m = 0;
 108       key = &keys[i];
 109       do
 110         {
 111           hits[m] = i;
 112           mkeys[m] = &keys[i];
 113           mfb[m] = fins[i];
 114           m++;
 115           P(set_tree)(keys, tree, n2+i, -1);
 116           i = tree[1].i;
 117           if (unlikely(i < 0))
 118             break;
 119         }
 120       while (!P(compare)(key, &keys[i]));
 121
 122       P(copy_merged)(mkeys, mfb, m, fout);
 123
 124       for (uns j=0; j<m; j++)
 125         {
 126           i = hits[j];
 127           if (likely(P(read_key)(fins[i], &keys[i])))
 128             P(set_tree)(keys, tree, n2+i, i);
 129         }
 130     }
 131
 132 #else
 133
 134   /* Simplified version which does not support any unification */
 135   while (likely(tree[1].i >= 0))
 136     {
 137       uns i = tree[1].i;
 138       P(key) UNUSED key = keys[i];
 139       P(copy_data)(&keys[i], fins[i], fout);
 140       if (unlikely(!P(read_key)(fins[i], &keys[i])))
 141         tree[n2+i].i = -1;
 142       P(update_tree)(keys, tree, n2+i);
 143 #ifdef SORT_ASSERT_UNIQUE
 144       ASSERT(tree[1].i < 0 || P(compare)(&key, &keys[tree[1].i]) < 0);
 145 #endif
 146     }
 147
 148 #endif
 149
 150   out->runs++;
 151 }