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