X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Fsorter%2Fs-multiway.h;h=83e928f2621c6a8ba07adeb244b0b3ad63a5a5e3;hb=1a3cd3005f2a5cda8dbdaaf8f153ae5703845876;hp=c22af45e65524bdc8e43a8cc04c03e31731d2e24;hpb=c3b8ffdcab64f99a1a58da14673226e3c466b715;p=libucw.git

diff --git a/lib/sorter/s-multiway.h b/lib/sorter/s-multiway.h
index c22af45e..83e928f2 100644
--- a/lib/sorter/s-multiway.h
+++ b/lib/sorter/s-multiway.h
@@ -7,14 +7,21 @@
  *	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)
     {
@@ -37,18 +44,15 @@ static inline void P(update_tree)(P(key) *keys, P(mwt_node) *tree, uns i)
        * 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);
@@ -67,9 +71,9 @@ static void P(multiway_merge)(struct sort_context *ctx UNUSED, struct sort_bucke
   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++)
     {