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       P(mwt_node) new;
  22       if (tree[2*i].i < 0)
  23         new = tree[2*i+1];
  24       else if (tree[2*i+1].i < 0)
  25         new = tree[2*i];
  26       else
  27         {
  28           int cmp = P(compare)(&keys[tree[2*i].i], &keys[tree[2*i+1].i]);
  29           if (cmp <= 0)
  30             new = tree[2*i];
  31           else
  32             new = tree[2*i+1];
  33 #ifdef SORT_UNIFY
  34           if (!cmp)
  35             new.eq = 1;
  36 #endif
  37         }
  38 #ifdef SORT_UNIFY_XXX           // FIXME
  39       /* If we are not unifying, the keys are usually distinct, so this check is pointless */
  40       if (!memcmp(&tree[i], &new, sizeof(new)))
  41         break;
  42 #endif
  43       tree[i] = new;
  44     }
  45 }
  46
  47 static inline void P(set_tree)(P(key) *keys, P(mwt_node) *tree, uns i, int val)
  48 {
  49   tree[i].i = val;
  50   P(update_tree)(keys, tree, i);
  51 }
  52
  53 static void P(multiway_merge)(struct sort_context *ctx UNUSED, struct sort_bucket **ins, struct sort_bucket *out)
  54 {
  55   uns num_ins = 0;
  56   while (ins[num_ins])
  57     num_ins++;
  58
  59   uns n2 = 1;
  60   while (n2 < num_ins)
  61     n2 *= 2;
  62
  63   struct fastbuf *fout = sbuck_write(out);
  64   struct fastbuf *fins[num_ins];
  65   P(key) keys[num_ins];
  66   P(mwt_node) tree[2*n2];               // A complete binary tree, leaves are input streams, each internal vertex contains a minimum of its sons
  67   for (uns i=1; i<2*n2; i++)
  68     {
  69       tree[i].i = -1;
  70 #ifdef SORT_UNIFY
  71       tree[i].eq = 0;
  72 #endif
  73     }
  74
  75   for (uns i=0; i<num_ins; i++)
  76     {
  77       fins[i] = sbuck_read(ins[i]);
  78       if (P(read_key)(fins[i], &keys[i]))
  79         P(set_tree)(keys, tree, n2+i, i);
  80     }
  81
  82 #ifdef SORT_UNIFY
  83
  84   uns hits[num_ins];
  85   P(key) *mkeys[num_ins], *key;
  86   struct fastbuf *mfb[num_ins];
  87
  88   while (likely(tree[1].i >= 0))
  89     {
  90       int i = tree[1].i;
  91       if (!tree[1].eq && 0)     // FIXME: This does not work for some reason
  92         {
  93           /* The key is unique, so let's go through the fast path */
  94           P(copy_data)(&keys[i], fins[i], fout);
  95           if (unlikely(!P(read_key)(fins[i], &keys[i])))
  96             tree[n2+i].i = -1;
  97           P(update_tree)(keys, tree, n2+i);
  98           continue;
  99         }
 100
 101       uns m = 0;
 102       key = &keys[i];
 103       do
 104         {
 105           hits[m] = i;
 106           mkeys[m] = &keys[i];
 107           mfb[m] = fins[i];
 108           m++;
 109           P(set_tree)(keys, tree, n2+i, -1);
 110           i = tree[1].i;
 111           if (unlikely(i < 0))
 112             break;
 113         }
 114       while (!P(compare)(key, &keys[i]));
 115
 116       P(copy_merged)(mkeys, mfb, m, fout);
 117
 118       for (uns j=0; j<m; j++)
 119         {
 120           i = hits[j];
 121           if (likely(P(read_key)(fins[i], &keys[i])))
 122             P(set_tree)(keys, tree, n2+i, i);
 123         }
 124     }
 125
 126 #else
 127
 128   /* Simplified version which does not support any unification */
 129   while (likely(tree[1].i >= 0))
 130     {
 131       uns i = tree[1].i;
 132       P(key) UNUSED key = keys[i];
 133       P(copy_data)(&keys[i], fins[i], fout);
 134       if (unlikely(!P(read_key)(fins[i], &keys[i])))
 135         tree[n2+i].i = -1;
 136       P(update_tree)(keys, tree, n2+i);
 137 #ifdef SORT_ASSERT_UNIQUE
 138       ASSERT(tree[1].i < 0 || P(compare)(&key, &keys[tree[1].i]) < 0);
 139 #endif
 140     }
 141
 142 #endif
 143
 144   out->runs++;
 145 }