From adfdae18c850affec9f3cdbbe7d4555b7f1d552e Mon Sep 17 00:00:00 2001 From: Marshall Clow Date: Wed, 29 Jul 2015 16:25:45 +0000 Subject: [PATCH] Fix a self-move bug in inplace_merge. Thanks to Ted and Dexon for the report and the suggested fix. llvm-svn: 243530 --- libcxx/include/algorithm | 40 ++++++++++++++---- .../alg.sorting/alg.merge/inplace_merge.pass.cpp | 31 +++++++++++++- .../alg.merge/inplace_merge_comp.pass.cpp | 48 ++++++++++++++++++---- 3 files changed, 101 insertions(+), 18 deletions(-) diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 459071f..7b0c53e 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -4361,6 +4361,34 @@ merge(_InputIterator1 __first1, _InputIterator1 __last1, // inplace_merge +template +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 void __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, @@ -4376,11 +4404,7 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator 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(__buff), - move_iterator(__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(_BidirectionalIterator __first, _BidirectionalIterator ::new(__p) value_type(_VSTD::move(*__i)); typedef reverse_iterator<_BidirectionalIterator> _RBi; typedef reverse_iterator _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)); } } diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp index 01db088..9065b99 100644 --- a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp @@ -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 void test_one(unsigned N, unsigned M) { + typedef typename std::iterator_traits::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 >(); test >(); test(); + +#ifndef TEST_STD_VER >= 11 + test >(); + test >(); + test(); +#endif // TEST_STD_VER >= 11 } diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp index b54efb6..a9b14fc 100644 --- a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp @@ -18,7 +18,10 @@ #include #include #include -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + +#include "test_macros.h" + +#ifndef TEST_STD_VER >= 11 #include 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::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()); - std::sort(ia+M, ia+N, std::greater()); - binary_counting_predicate, int, int> pred((std::greater())); + std::sort(ia, ia+M, std::greater()); + std::sort(ia+M, ia+N, std::greater()); + binary_counting_predicate, value_type, value_type> pred((std::greater())); 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())); + assert(std::is_sorted(ia, ia+N, std::greater())); assert(pred.count() <= (N-1)); } delete [] ia; @@ -93,7 +119,11 @@ int main() test >(); test(); -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES +#ifndef TEST_STD_VER >= 11 + test >(); + test >(); + test(); + { 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 } -- 2.7.4