[PATCH][libstdc++-v3 parallel mode] Avoid taking address of dereferenced random access iterator

[Johannes Singler <singler at kit dot edu>]

The attached patch patch solves a conformance problem of the parallel 
mode helper routine multiseq_partition.  I have added a test case for 
that.  multiseq_selection has similar problems, but is unused, so I plan 
to remove that completely (which might ask for renaming of the file and 
the test).

Should I use unique_ptr (or alloca, or something similar) here for a 
better exception safety (this routine is not parallel itself)?
Is it the appropriate place for the "unit test"?  It is used in the 
parallel sort.

Tested x86_64-unknown-linux-gnu: No regressions


2011-03-10  Johannes Singler  <singler@kit.edu>

        * include/parallel/multiseq_selection.h (multiseq_partition):
        Copy-construct _ValueType element on demand on heap, do not
        take address of dereferenced random access iterator.
        Remove unused code that has the same problem.
        * testsuite/25_algorithms/sort/multiseq_selection.cc:
        New unit test for multiseq_partition.

Johannes

Index: include/parallel/multiseq_selection.h
===================================================================
--- include/parallel/multiseq_selection.h	(revision 170753)
+++ include/parallel/multiseq_selection.h	(working copy)
@@ -229,15 +229,15 @@
         {
           __n /= 2;
 
-          _SeqNumber __lmax_seq = -1;  // to avoid warning
-          const _ValueType* __lmax = 0; // impossible to avoid the warning?
+          _SeqNumber __lmax_seq = -1;  // initialize to avoid warning
+          _ValueType* __lmax = 0;
           for (_SeqNumber __i = 0; __i < __m; __i++)
             {
               if (__a[__i] > 0)
                 {
                   if (!__lmax)
                     {
-                      __lmax = &(__S(__i)[__a[__i] - 1]);
+                      __lmax = new _ValueType(__S(__i)[__a[__i] - 1]);
                       __lmax_seq = __i;
                     }
                   else
@@ -245,7 +245,7 @@
                       // Max, favor rear sequences.
                       if (!__comp(__S(__i)[__a[__i] - 1], *__lmax))
                         {
-                          __lmax = &(__S(__i)[__a[__i] - 1]);
+                          *__lmax = __S(__i)[__a[__i] - 1];
                           __lmax_seq = __i;
                         }
                     }
@@ -321,45 +321,13 @@
                         __S(__source)[__a[__source] - 1], __source));
                 }
             }
+          delete __lmax;
         }
 
       // Postconditions:
       // __a[__i] == __b[__i] in most cases, except when __a[__i] has been
       // clamped because of having reached the boundary
 
-      // Now return the result, calculate the offset.
-
-      // Compare the keys on both edges of the border.
-
-      // Maximum of left edge, minimum of right edge.
-      _ValueType* __maxleft = 0;
-      _ValueType* __minright = 0;
-      for (_SeqNumber __i = 0; __i < __m; __i++)
-        {
-          if (__a[__i] > 0)
-            {
-              if (!__maxleft)
-                __maxleft = &(__S(__i)[__a[__i] - 1]);
-              else
-                {
-                  // Max, favor rear sequences.
-                  if (!__comp(__S(__i)[__a[__i] - 1], *__maxleft))
-                    __maxleft = &(__S(__i)[__a[__i] - 1]);
-                }
-            }
-          if (__b[__i] < __ns[__i])
-            {
-              if (!__minright)
-                __minright = &(__S(__i)[__b[__i]]);
-              else
-                {
-                  // Min, favor fore sequences.
-                  if (__comp(__S(__i)[__b[__i]], *__minright))
-                    __minright = &(__S(__i)[__b[__i]]);
-                }
-            }
-        }
-
       _SeqNumber __seq = 0;
       for (_SeqNumber __i = 0; __i < __m; __i++)
         __begin_offsets[__i] = __S(__i) + __a[__i];
Index: testsuite/25_algorithms/sort/multiseq_selection.cc
===================================================================
--- testsuite/25_algorithms/sort/multiseq_selection.cc	(revision 0)
+++ testsuite/25_algorithms/sort/multiseq_selection.cc	(revision 0)
@@ -0,0 +1,116 @@
+// { dg-require-parallel-mode "" }
+// { dg-options "-fopenmp" { target *-*-* } }
+
+// Copyright (C) 2011 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <parallel/algorithm>
+
+#include <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+template<typename RanSeqs, typename RankType, typename RankIterator,
+         class Compare>
+bool check_border(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank,
+                  RankIterator border, Compare comp)
+{
+    int m = end_seqs - begin_seqs;  //number of sequences
+
+    //check bounds
+    for (int i = 0; i < m; ++i)
+        if (border[i] < begin_seqs[i].first ||
+            border[i] > begin_seqs[i].second)
+            return false;   //out of bounds
+
+    //check consistency pairwise
+    for (int i = 0; i < m; ++i) //left side of border of i-th sequence
+    {
+        for (int j = 0; j < m; ++j) //right side the border of j-th sequence
+        {
+            if (border[j] != (begin_seqs[j].second) &&
+                border[i] != begin_seqs[i].first &&
+                comp(*(border[j]), *(border[i] - 1)))
+            return false;
+                //an element on the right is less than an element on the left
+        }
+    }
+
+    //check rank
+    int num_less_elements = 0;
+    for (int i = 0; i < m; ++i)
+        num_less_elements += (border[i] - begin_seqs[i].first);
+
+    return num_less_elements == rank;
+}
+
+//iterator wrapper that returns by value instead of by (const) reference
+template<typename RAI>
+struct by_value_iterator : public RAI
+{
+    typedef typename std::iterator_traits<RAI>::value_type value_type;
+    typedef typename std::iterator_traits<RAI>::difference_type
+                                                      difference_type;
+
+    by_value_iterator() { }
+    by_value_iterator(const RAI& rai) : RAI(rai) { }
+
+    value_type operator*() const
+    {
+        return RAI::operator*();   //not by reference, but by value
+    }
+
+    //minimal operations for this test case
+
+    by_value_iterator operator+(difference_type add) const
+    {
+        return by_value_iterator(RAI::operator+(add));
+    }
+};
+
+void
+test01()
+{
+    std::vector<int> A, B, C;
+    A.push_back(1); A.push_back(5); A.push_back(7); A.push_back(8);
+        A.push_back(9);
+    B.push_back(3); B.push_back(4); C.push_back(2);
+    C.push_back(6); C.push_back(10);
+
+    typedef by_value_iterator<typename std::vector<int>::const_iterator> nai;
+    typedef std::pair<nai, nai> sequence_limits;
+    sequence_limits sl[3];
+    sl[0] = sequence_limits(nai(A.begin()), nai(A.end()));
+    sl[1] = sequence_limits(nai(B.begin()), nai(B.end()));
+    sl[2] = sequence_limits(nai(C.begin()), nai(C.end()));
+    int total = A.size() + B.size() + C.size();
+
+    nai border[3];
+    for (int rank = 0; rank <= total; ++rank)
+    {
+        __gnu_parallel::
+                multiseq_partition(sl, sl + 3, rank, border, std::less<int>());
+        VERIFY(check_border(sl, sl + 3, rank, border, std::less<int>()));
+    }
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}