Hans, I think this fix should be merged into 3.7. Marshall, do you agree?
> On 2015-Jul-29, at 09:25, Marshall Clow <[email protected]> wrote: > > Author: marshall > Date: Wed Jul 29 11:25:45 2015 > New Revision: 243530 > > URL: http://llvm.org/viewvc/llvm-project?rev=243530&view=rev > Log: > Fix a self-move bug in inplace_merge. Thanks to Ted and Dexon for the report > and the suggested fix. > > Modified: > libcxx/trunk/include/algorithm > > libcxx/trunk/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp > > libcxx/trunk/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp > > Modified: libcxx/trunk/include/algorithm > URL: > http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?rev=243530&r1=243529&r2=243530&view=diff > ============================================================================== > --- libcxx/trunk/include/algorithm (original) > +++ libcxx/trunk/include/algorithm Wed Jul 29 11:25:45 2015 > @@ -4361,6 +4361,34 @@ merge(_InputIterator1 __first1, _InputIt > > // inplace_merge > > +template <class _Compare, class _InputIterator1, class _InputIterator2, > + class _OutputIterator> > +void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1, > + _InputIterator2 __first2, _InputIterator2 __last2, > + _OutputIterator __result, _Compare __comp) > +{ > + for (; __first1 != __last1; ++__result) > + { > + if (__first2 == __last2) > + { > + _VSTD::move(__first1, __last1, __result); > + return; > + } > + > + if (__comp(*__first2, *__first1)) > + { > + *__result = _VSTD::move(*__first2); > + ++__first2; > + } > + else > + { > + *__result = _VSTD::move(*__first1); > + ++__first1; > + } > + } > + // __first2 through __last2 are already in the right spot. > +} > + > template <class _Compare, class _BidirectionalIterator> > void > __buffered_inplace_merge(_BidirectionalIterator __first, > _BidirectionalIterator __middle, _BidirectionalIterator __last, > @@ -4376,11 +4404,7 @@ __buffered_inplace_merge(_BidirectionalI > value_type* __p = __buff; > for (_BidirectionalIterator __i = __first; __i != __middle; > __d.__incr((value_type*)0), (void) ++__i, ++__p) > ::new(__p) value_type(_VSTD::move(*__i)); > - __merge<_Compare>(move_iterator<value_type*>(__buff), > - move_iterator<value_type*>(__p), > - move_iterator<_BidirectionalIterator>(__middle), > - move_iterator<_BidirectionalIterator>(__last), > - __first, __comp); > + __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp); > } > else > { > @@ -4389,9 +4413,9 @@ __buffered_inplace_merge(_BidirectionalI > ::new(__p) value_type(_VSTD::move(*__i)); > typedef reverse_iterator<_BidirectionalIterator> _RBi; > typedef reverse_iterator<value_type*> _Rv; > - __merge(move_iterator<_RBi>(_RBi(__middle)), > move_iterator<_RBi>(_RBi(__first)), > - move_iterator<_Rv>(_Rv(__p)), > move_iterator<_Rv>(_Rv(__buff)), > - _RBi(__last), __negate<_Compare>(__comp)); > + __half_inplace_merge(_Rv(__p), _Rv(__buff), > + _RBi(__middle), _RBi(__first), > + _RBi(__last), __negate<_Compare>(__comp)); > } > } > > > Modified: > libcxx/trunk/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp > URL: > http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp?rev=243530&r1=243529&r2=243530&view=diff > ============================================================================== > --- > libcxx/trunk/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp > (original) > +++ > libcxx/trunk/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp > Wed Jul 29 11:25:45 2015 > @@ -20,12 +20,35 @@ > > #include "test_iterators.h" > > +#ifndef TEST_STD_VER >= 11 > +struct S { > + S() : i_(0) {} > + S(int i) : i_(i) {} > + > + S(const S& rhs) : i_(rhs.i_) {} > + S( S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; } > + > + S& operator =(const S& rhs) { i_ = rhs.i_; return *this; } > + S& operator =( S&& rhs) { i_ = rhs.i_; rhs.i_ = -2; assert(this != > &rhs); return *this; } > + S& operator =(int i) { i_ = i; return *this; } > + > + bool operator <(const S& rhs) const { return i_ < rhs.i_; } > + bool operator ==(const S& rhs) const { return i_ == rhs.i_; } > + bool operator ==(int i) const { return i_ == i; } > + > + void set(int i) { i_ = i; } > + > + int i_; > + }; > +#endif > + > template <class Iter> > void > test_one(unsigned N, unsigned M) > { > + typedef typename std::iterator_traits<Iter>::value_type value_type; > assert(M <= N); > - int* ia = new int[N]; > + value_type* ia = new value_type[N]; > for (unsigned i = 0; i < N; ++i) > ia[i] = i; > std::random_shuffle(ia, ia+N); > @@ -76,4 +99,10 @@ int main() > test<bidirectional_iterator<int*> >(); > test<random_access_iterator<int*> >(); > test<int*>(); > + > +#ifndef TEST_STD_VER >= 11 > + test<bidirectional_iterator<S*> >(); > + test<random_access_iterator<S*> >(); > + test<S*>(); > +#endif // TEST_STD_VER >= 11 > } > > Modified: > libcxx/trunk/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp > URL: > http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp?rev=243530&r1=243529&r2=243530&view=diff > ============================================================================== > --- > libcxx/trunk/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp > (original) > +++ > libcxx/trunk/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp > Wed Jul 29 11:25:45 2015 > @@ -18,7 +18,10 @@ > #include <algorithm> > #include <functional> > #include <cassert> > -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES > + > +#include "test_macros.h" > + > +#ifndef TEST_STD_VER >= 11 > #include <memory> > > struct indirect_less > @@ -28,7 +31,29 @@ struct indirect_less > {return *x < *y;} > }; > > -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES > +struct S { > + S() : i_(0) {} > + S(int i) : i_(i) {} > + > + S(const S& rhs) : i_(rhs.i_) {} > + S( S&& rhs) : i_(rhs.i_) { rhs.i_ = -1; } > + > + S& operator =(const S& rhs) { i_ = rhs.i_; return *this; } > + S& operator =( S&& rhs) { i_ = rhs.i_; rhs.i_ = -2; assert(this != > &rhs); return *this; } > + S& operator =(int i) { i_ = i; return *this; } > + > + bool operator <(const S& rhs) const { return i_ < rhs.i_; } > + bool operator >(const S& rhs) const { return i_ > rhs.i_; } > + bool operator ==(const S& rhs) const { return i_ == rhs.i_; } > + bool operator ==(int i) const { return i_ == i; } > + > + void set(int i) { i_ = i; } > + > + int i_; > + }; > + > + > +#endif // TEST_STD_VER >= 11 > > #include "test_iterators.h" > #include "counting_predicates.hpp" > @@ -38,19 +63,20 @@ void > test_one(unsigned N, unsigned M) > { > assert(M <= N); > - int* ia = new int[N]; > + typedef typename std::iterator_traits<Iter>::value_type value_type; > + value_type* ia = new value_type[N]; > for (unsigned i = 0; i < N; ++i) > ia[i] = i; > std::random_shuffle(ia, ia+N); > - std::sort(ia, ia+M, std::greater<int>()); > - std::sort(ia+M, ia+N, std::greater<int>()); > - binary_counting_predicate<std::greater<int>, int, int> > pred((std::greater<int>())); > + std::sort(ia, ia+M, std::greater<value_type>()); > + std::sort(ia+M, ia+N, std::greater<value_type>()); > + binary_counting_predicate<std::greater<value_type>, value_type, > value_type> pred((std::greater<value_type>())); > std::inplace_merge(Iter(ia), Iter(ia+M), Iter(ia+N), std::ref(pred)); > if(N > 0) > { > assert(ia[0] == N-1); > assert(ia[N-1] == 0); > - assert(std::is_sorted(ia, ia+N, std::greater<int>())); > + assert(std::is_sorted(ia, ia+N, std::greater<value_type>())); > assert(pred.count() <= (N-1)); > } > delete [] ia; > @@ -93,7 +119,11 @@ int main() > test<random_access_iterator<int*> >(); > test<int*>(); > > -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES > +#ifndef TEST_STD_VER >= 11 > + test<bidirectional_iterator<S*> >(); > + test<random_access_iterator<S*> >(); > + test<S*>(); > + > { > unsigned N = 100; > unsigned M = 50; > @@ -112,5 +142,5 @@ int main() > } > delete [] ia; > } > -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES > +#endif // TEST_STD_VER >= 11 > } > > > _______________________________________________ > cfe-commits mailing list > [email protected] > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
