From 12d19573453bd32d537a3952837a326c9a56f2ce Mon Sep 17 00:00:00 2001 From: paolo Date: Mon, 24 Aug 2009 14:07:34 +0000 Subject: [PATCH 1/1] 2009-08-24 Chris Jefferson * include/stl_algo.h (__unguarded_partition_pivot, __move_median_first): New. (__insertion_sort, __unguarded_insertion_sort): Adjust for move-only types. (__unguarded_linear_insert): Assume always inserting value at __last. (__unguarded_partition): Take pivot by reference. (__introsort_loop, __introselect) : Use __unguarded_partition_pivot. * testsuite/25_algorithms/nth_element/moveable.cc : Enable. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@151055 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 11 ++ libstdc++-v3/include/bits/stl_algo.h | 169 +++++++++++++-------- .../25_algorithms/nth_element/moveable.cc | 1 - 3 files changed, 116 insertions(+), 65 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 56bbffa57ab..f60c2b48f1d 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,14 @@ +2009-08-24 Chris Jefferson + + * include/stl_algo.h (__unguarded_partition_pivot, + __move_median_first): New. + (__insertion_sort, __unguarded_insertion_sort): Adjust for move-only + types. + (__unguarded_linear_insert): Assume always inserting value at __last. + (__unguarded_partition): Take pivot by reference. + (__introsort_loop, __introselect) : Use __unguarded_partition_pivot. + * testsuite/25_algorithms/nth_element/moveable.cc : Enable. + 2009-08-23 Ralf Wildenhues * libsupc++/Makefile.am (LTCOMPILE): Expand $(LIBTOOLFLAGS) diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 6418ebf6db4..a745295e9b0 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -136,6 +136,56 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __b; } + /// Swaps the median value of *__a, *__b and *__c to *__a + template + void + __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c) + { + // concept requirements + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_Iterator>::value_type>) + + if (*__a < *__b) + { + if (*__b < *__c) + std::iter_swap(__a, __b); + else if (*__a < *__c) + std::iter_swap(__a, __c); + } + else if (*__a < *__c) + return; + else if (*__b < *__c) + std::iter_swap(__a, __c); + else + std::iter_swap(__a, __b); + } + + /// Swaps the median value of *__a, *__b and *__c under __comp to *__a + template + void + __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c, + _Compare __comp) + { + // concept requirements + __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, + typename iterator_traits<_Iterator>::value_type, + typename iterator_traits<_Iterator>::value_type>) + + if (__comp(*__a, *__b)) + { + if (__comp(*__b, *__c)) + std::iter_swap(__a, __b); + else if (__comp(*__a, *__c)) + std::iter_swap(__a, __c); + } + else if (__comp(*__a, *__c)) + return; + else if (__comp(*__b, *__c)) + std::iter_swap(__a, __c); + else + std::iter_swap(__a, __b); + } + // for_each /// This is an overload used by find() for the Input Iterator case. @@ -2058,36 +2108,40 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /// This is a helper function for the sort routine. - template + template void - __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val) + __unguarded_linear_insert(_RandomAccessIterator __last) { + typename iterator_traits<_RandomAccessIterator>::value_type + __val = _GLIBCXX_MOVE(*__last); _RandomAccessIterator __next = __last; --__next; while (__val < *__next) { - *__last = *__next; + *__last = _GLIBCXX_MOVE(*__next); __last = __next; --__next; } - *__last = __val; + *__last = _GLIBCXX_MOVE(__val); } /// This is a helper function for the sort routine. - template + template void - __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val, + __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp) { + typename iterator_traits<_RandomAccessIterator>::value_type + __val = _GLIBCXX_MOVE(*__last); _RandomAccessIterator __next = __last; --__next; while (__comp(__val, *__next)) { - *__last = *__next; + *__last = _GLIBCXX_MOVE(*__next); __last = __next; --__next; } - *__last = __val; + *__last = _GLIBCXX_MOVE(__val); } /// This is a helper function for the sort routine. @@ -2101,15 +2155,15 @@ _GLIBCXX_BEGIN_NAMESPACE(std) for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) { - typename iterator_traits<_RandomAccessIterator>::value_type - __val = *__i; - if (__val < *__first) + if (*__i < *__first) { - std::copy_backward(__first, __i, __i + 1); - *__first = __val; + typename iterator_traits<_RandomAccessIterator>::value_type + __val = _GLIBCXX_MOVE(*__i); + _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); + *__first = _GLIBCXX_MOVE(__val); } else - std::__unguarded_linear_insert(__i, __val); + std::__unguarded_linear_insert(__i); } } @@ -2123,15 +2177,15 @@ _GLIBCXX_BEGIN_NAMESPACE(std) for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) { - typename iterator_traits<_RandomAccessIterator>::value_type - __val = *__i; - if (__comp(__val, *__first)) + if (__comp(*__i, *__first)) { - std::copy_backward(__first, __i, __i + 1); - *__first = __val; + typename iterator_traits<_RandomAccessIterator>::value_type + __val = _GLIBCXX_MOVE(*__i); + _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); + *__first = _GLIBCXX_MOVE(__val); } else - std::__unguarded_linear_insert(__i, __val, __comp); + std::__unguarded_linear_insert(__i, __comp); } } @@ -2145,7 +2199,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType; for (_RandomAccessIterator __i = __first; __i != __last; ++__i) - std::__unguarded_linear_insert(__i, _ValueType(*__i)); + std::__unguarded_linear_insert(__i); } /// This is a helper function for the sort routine. @@ -2158,7 +2212,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType; for (_RandomAccessIterator __i = __first; __i != __last; ++__i) - std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp); + std::__unguarded_linear_insert(__i, __comp); } /** @@ -2202,7 +2256,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) template _RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Tp __pivot) + _RandomAccessIterator __last, const _Tp& __pivot) { while (true) { @@ -2223,7 +2277,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Tp __pivot, _Compare __comp) + const _Tp& __pivot, _Compare __comp) { while (true) { @@ -2239,6 +2293,29 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } + /// This is a helper function... + template + inline _RandomAccessIterator + __unguarded_partition_pivot(_RandomAccessIterator __first, + _RandomAccessIterator __last) + { + _RandomAccessIterator __mid = __first + (__last - __first) / 2; + std::__move_median_first(__first, __mid, (__last - 1)); + return std::__unguarded_partition(__first + 1, __last, *__first); + } + + + /// This is a helper function... + template + inline _RandomAccessIterator + __unguarded_partition_pivot(_RandomAccessIterator __first, + _RandomAccessIterator __last, _Compare __comp) + { + _RandomAccessIterator __mid = __first + (__last - __first) / 2; + std::__move_median_first(__first, __mid, (__last - 1), __comp); + return std::__unguarded_partition(__first + 1, __last, *__first, __comp); + } + /// This is a helper function for the sort routine. template void @@ -2246,9 +2323,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _RandomAccessIterator __last, _Size __depth_limit) { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; - while (__last - __first > int(_S_threshold)) { if (__depth_limit == 0) @@ -2258,14 +2332,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } --__depth_limit; _RandomAccessIterator __cut = - std::__unguarded_partition(__first, __last, - _ValueType(std::__median(*__first, - *(__first - + (__last - - __first) - / 2), - *(__last - - 1)))); + std::__unguarded_partition_pivot(__first, __last); std::__introsort_loop(__cut, __last, __depth_limit); __last = __cut; } @@ -2278,9 +2345,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp) { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; - while (__last - __first > int(_S_threshold)) { if (__depth_limit == 0) @@ -2290,15 +2354,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } --__depth_limit; _RandomAccessIterator __cut = - std::__unguarded_partition(__first, __last, - _ValueType(std::__median(*__first, - *(__first - + (__last - - __first) - / 2), - *(__last - 1), - __comp)), - __comp); + std::__unguarded_partition_pivot(__first, __last, __comp); std::__introsort_loop(__cut, __last, __depth_limit, __comp); __last = __cut; } @@ -2349,14 +2405,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } --__depth_limit; _RandomAccessIterator __cut = - std::__unguarded_partition(__first, __last, - _ValueType(std::__median(*__first, - *(__first - + (__last - - __first) - / 2), - *(__last - - 1)))); + std::__unguarded_partition_pivot(__first, __last); if (__cut <= __nth) __first = __cut; else @@ -2385,15 +2434,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } --__depth_limit; _RandomAccessIterator __cut = - std::__unguarded_partition(__first, __last, - _ValueType(std::__median(*__first, - *(__first - + (__last - - __first) - / 2), - *(__last - 1), - __comp)), - __comp); + std::__unguarded_partition_pivot(__first, __last, __comp); if (__cut <= __nth) __first = __cut; else diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc b/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc index cb729492bf2..005f6ec7cbc 100644 --- a/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc +++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc @@ -1,4 +1,3 @@ -// { dg-require-rvalref "" } // { dg-options "-std=gnu++0x" } // Copyright (C) 2005, 2007, 2009 Free Software Foundation, Inc. -- 2.11.0