2 * UCW Library -- Universal Sorter: Multi-Way Merge Module
4 * (c) 2007 Martin Mares <mj@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
10 static inline void P(update_tree)(P(key) *keys, int *tree, uns i)
15 tree[i] = tree[2*i+1];
16 else if (tree[2*i+1] < 0)
18 else if (P(compare)(&keys[tree[2*i]], &keys[tree[2*i+1]]) <= 0)
21 tree[i] = tree[2*i+1];
25 static void P(multiway_merge)(struct sort_context *ctx UNUSED, struct sort_bucket **ins, uns num_ins, struct sort_bucket *out)
31 struct fastbuf *fout = sbuck_write(out);
32 struct fastbuf *fins[num_ins];
33 P(key) keys[num_ins]; // FIXME: Tune num_ins according to L1 cache size
34 int tree[2*n2]; // A complete binary tree, leaves are input streams, each internal vertex contains a minimum of its sons
35 for (uns i=1; i<=n2; i++)
38 for (uns i=0; i<num_ins; i++)
40 fins[i] = sbuck_read(ins[i]);
41 if (P(read_key)(fins[i], &keys[i]))
44 P(update_tree)(keys, tree, n2+i);
51 P(copy_data)(&keys[i], fins[i], fout);
52 if (unlikely(!P(read_key)(fins[i], &keys[i])))
54 P(update_tree)(keys, tree, n2+i);
58 #ifdef SORT_ASSERT_UNIQUE
64 P(key) *mkeys[] = { kin1, kin2 };
65 struct fastbuf *mfb[] = { fin1, fin2 };
66 P(copy_merged)(mkeys, mfb, 2, fout1);
67 SWAP(kin1, kprev1, ktmp);
68 next1 = P(read_key)(fin1, kin1);
69 run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
70 SWAP(kin2, kprev2, ktmp);
71 next2 = P(read_key)(fin2, kin2);
72 run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);