From 1a31ce20f0240d0aa16e277b557cc517c26c1fdd Mon Sep 17 00:00:00 2001 From: paolo Date: Tue, 3 Nov 2009 18:16:34 +0000 Subject: [PATCH] 2009-11-03 David Krauss Paolo Carlini PR libstdc++/41351 * include/bits/stl_algo.h (__rotate(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, random_access_iterator_tag)): Rewrite to use only std::swap in general and std::copy/std::copy_backward when safe. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@153860 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 9 +++++ libstdc++-v3/include/bits/stl_algo.h | 71 +++++++++++++++++++++--------------- 2 files changed, 50 insertions(+), 30 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 589671b..494e24e 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,12 @@ +2009-11-03 David Krauss + Paolo Carlini + + PR libstdc++/41351 + * include/bits/stl_algo.h (__rotate(_RandomAccessIterator, + _RandomAccessIterator, _RandomAccessIterator, + random_access_iterator_tag)): Rewrite to use only std::swap in + general and std::copy/std::copy_backward when safe. + 2009-11-02 Benjamin Kosnik * include/std/future: Use base class with nested types. diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 70cde1a..9b6f2af 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -1647,53 +1647,64 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; - const _Distance __n = __last - __first; - const _Distance __k = __middle - __first; - const _Distance __l = __n - __k; + _Distance __n = __last - __first; + _Distance __k = __middle - __first; - if (__k == __l) + if (__k == __n - __k) { std::swap_ranges(__first, __middle, __middle); return; } - const _Distance __d = std::__gcd(__n, __k); + _RandomAccessIterator __p = __first; - for (_Distance __i = 0; __i < __d; __i++) + for (;;) { - _ValueType __tmp = _GLIBCXX_MOVE(*__first); - _RandomAccessIterator __p = __first; - - if (__k < __l) + if (__k < __n - __k) { - for (_Distance __j = 0; __j < __l / __d; __j++) + if (__is_pod(_ValueType) && __k == 1) + { + _ValueType __t = _GLIBCXX_MOVE(*__p); + _GLIBCXX_MOVE3(__p + 1, __p + __n, __p); + *(__p + __n - 1) = _GLIBCXX_MOVE(__t); + return; + } + _RandomAccessIterator __q = __p + __k; + for (_Distance __i = 0; __i < __n - __k; ++ __i) { - if (__p > __first + __l) - { - *__p = _GLIBCXX_MOVE(*(__p - __l)); - __p -= __l; - } - - *__p = _GLIBCXX_MOVE(*(__p + __k)); - __p += __k; + std::iter_swap(__p, __q); + ++__p; + ++__q; } + __n %= __k; + if (__n == 0) + return; + std::swap(__n, __k); + __k = __n - __k; } else { - for (_Distance __j = 0; __j < __k / __d - 1; __j ++) + __k = __n - __k; + if (__is_pod(_ValueType) && __k == 1) { - if (__p < __last - __k) - { - *__p = _GLIBCXX_MOVE(*(__p + __k)); - __p += __k; - } - *__p = _GLIBCXX_MOVE(*(__p - __l)); - __p -= __l; + _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1)); + _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n); + *__p = _GLIBCXX_MOVE(__t); + return; } + _RandomAccessIterator __q = __p + __n; + __p = __q - __k; + for (_Distance __i = 0; __i < __n - __k; ++ __i) + { + --__p; + --__q; + std::iter_swap(__p, __q); + } + __n %= __k; + if (__n == 0) + return; + std::swap(__n, __k); } - - *__p = _GLIBCXX_MOVE(__tmp); - ++__first; } } -- 2.7.4