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 <sing...@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;
+}
