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   /*
  48    * This function sometimes triggers optimizer bugs in GCC versions up to 4.2.1,
  49    * leading to an assumption that tree[1] does not change during this function.
  50    * We add an explicit memory barrier as a work-around. Ugh. See GCC Bug #33262.
  51    */
  52   asm volatile ("" : : : "memory");
  53 }
  54
  55 static inline void P(set_tree)(P(key) *keys, P(mwt) *tree, uns i, int val)
  56 {
  57   tree[i].i = val;
  58   P(update_tree)(keys, tree, i);
  59 }
  60
  61 static void P(multiway_merge)(struct sort_context *ctx UNUSED, struct sort_bucket **ins, struct sort_bucket *out)
  62 {
  63   uns num_ins = 0;
  64   while (ins[num_ins])
  65     num_ins++;
  66
  67   uns n2 = 1;
  68   while (n2 < num_ins)
  69     n2 *= 2;
  70
  71   struct fastbuf *fout = sbuck_write(out);
  72   struct fastbuf *fins[num_ins];
  73   P(key) keys[num_ins];
  74   P(mwt) tree[2*n2];
  75   for (uns i=1; i<2*n2; i++)
  76     tree[i] = (P(mwt)) { .i = -1 };
  77
  78   for (uns i=0; i<num_ins; i++)
  79     {
  80       fins[i] = sbuck_read(ins[i]);
  81       if (P(read_key)(fins[i], &keys[i]))
  82         P(set_tree)(keys, tree, n2+i, i);
  83     }
  84
  85 #ifdef SORT_UNIFY
  86
  87   uns hits[num_ins];
  88   P(key) *mkeys[num_ins], *key;
  89   struct fastbuf *mfb[num_ins];
  90
  91   while (likely(tree[1].i >= 0))
  92     {
  93       int i = tree[1].i;
  94       if (!tree[1].eq)
  95         {
  96           /* The key is unique, so let's go through the fast path */
  97           P(copy_data)(&keys[i], fins[i], fout);
  98           if (unlikely(!P(read_key)(fins[i], &keys[i])))
  99             tree[n2+i].i = -1;
 100           P(update_tree)(keys, tree, n2+i);
 101           continue;
 102         }
 103
 104       uns m = 0;
 105       key = &keys[i];
 106       do
 107         {
 108           hits[m] = i;
 109           mkeys[m] = &keys[i];
 110           mfb[m] = fins[i];
 111           m++;
 112           P(set_tree)(keys, tree, n2+i, -1);
 113           i = tree[1].i;
 114           if (unlikely(i < 0))
 115             break;
 116         }
 117       while (!P(compare)(key, &keys[i]));
 118
 119       P(copy_merged)(mkeys, mfb, m, fout);
 120
 121       for (uns j=0; j<m; j++)
 122         {
 123           i = hits[j];
 124           if (likely(P(read_key)(fins[i], &keys[i])))
 125             P(set_tree)(keys, tree, n2+i, i);
 126         }
 127     }
 128
 129 #else
 130
 131   /* Simplified version which does not support any unification */
 132   while (likely(tree[1].i >= 0))
 133     {
 134       uns i = tree[1].i;
 135       P(key) UNUSED key = keys[i];
 136       P(copy_data)(&keys[i], fins[i], fout);
 137       if (unlikely(!P(read_key)(fins[i], &keys[i])))
 138         tree[n2+i].i = -1;
 139       P(update_tree)(keys, tree, n2+i);
 140 #ifdef SORT_ASSERT_UNIQUE
 141       ASSERT(tree[1].i < 0 || P(compare)(&key, &keys[tree[1].i]) < 0);
 142 #endif
 143     }
 144
 145 #endif
 146
 147   out->runs++;
 148 }