* of the GNU Lesser General Public License.
*/
-typedef struct P(mwt_node) {
- int i;
+/*
+ * We use a binary tree to keep track of the current minimum. The tree is
+ * represented by an array (in the same way as binary heaps usually are),
+ * leaves correspond to input streams and each internal vertex remembers
+ * the leaf in its subtree, which has the lowest key.
+ */
+
+typedef struct P(mwt) {
+ int i; // Minimum of the subtree
#ifdef SORT_UNIFY
- int eq;
+ int eq; // Did we encounter equality anywhere in the subtree?
#endif
-} P(mwt_node);
+} P(mwt);
-static inline void P(update_tree)(P(key) *keys, P(mwt_node) *tree, uns i)
+static inline void P(update_tree)(P(key) *keys, P(mwt) *tree, uns i)
{
while (i /= 2)
{
* the tree is the same, the actual key value can differ.
*/
}
-#if defined(__GNUC__) && (__GNUC__ * 1000 + __GNUC_MINOR__ < 4002)
/*
- * This function sometimes triggers optimizer bugs in GCC 4.1.1 and
- * possibly also earlier versions, leading to an assumption that tree[1]
- * does not change during this function. We add an explicit memory barrier
- * as a work-around. Ugh.
+ * This function sometimes triggers optimizer bugs in GCC versions up to 4.2.1,
+ * leading to an assumption that tree[1] does not change during this function.
+ * We add an explicit memory barrier as a work-around. Ugh. See GCC Bug #33262.
*/
asm volatile ("" : : : "memory");
-#endif
}
-static inline void P(set_tree)(P(key) *keys, P(mwt_node) *tree, uns i, int val)
+static inline void P(set_tree)(P(key) *keys, P(mwt) *tree, uns i, int val)
{
tree[i].i = val;
P(update_tree)(keys, tree, i);
struct fastbuf *fout = sbuck_write(out);
struct fastbuf *fins[num_ins];
P(key) keys[num_ins];
- P(mwt_node) tree[2*n2]; // A complete binary tree, leaves are input streams, each internal vertex contains a minimum of its sons
+ P(mwt) tree[2*n2];
for (uns i=1; i<2*n2; i++)
- tree[i] = (P(mwt_node)) { .i = -1 };
+ tree[i] = (P(mwt)) { .i = -1 };
for (uns i=0; i<num_ins; i++)
{