diff options
| author | François Dumont <fdumont@gcc.gnu.org> | 2019-12-10 21:49:55 +0000 |
|---|---|---|
| committer | François Dumont <fdumont@gcc.gnu.org> | 2019-12-10 21:49:55 +0000 |
| commit | 6004c17b4d1a2dd1e1936b2e705a5ccfb6e48ab2 (patch) | |
| tree | 5c61e9683f3dcec79f0b97b8dffce41f11ad16a9 /libstdc++-v3 | |
| parent | 5e72bcc1dd04034341c93f1cd0b0ac8fdf43e966 (diff) | |
libstdc++: Rework std::copy/copy_backward/move/move_backward/fill/fill_n algos
Enhance those algos overloads to generalize existing optimization for
__gnu_debug::_Safe_iterator w/o _GLIBCXX_DEBUG mode and for std::deque
iterators.
Also extend __copy_move_a2 ostreambuf_iterator overloads to std::vector and
std::deque iterators.
* include/bits/stl_algobase.h
(__copy_move_a1<>(_II, _II, _OI)): New.
(__copy_move_a1<>(_Deque_iterator<>, _Deque_iterator<>, _OI)): New.
(__copy_move_a1<>(_Deque_iterator<>, _Deque_iterator<>,
_Deque_iterator<>)): New.
(__copy_move_a1<>(_II, _II, _Deque_iterator<>)): New.
(__copy_move_a<>(_II, _II, _OI)): Adapt, call __copy_move_a1<>.
(__copy_move_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&,
_OI)): New.
(__copy_move_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&,
const _Safe_iterator<>&)): New.
(__copy_move_a<>(_II, _II, const _Safe_iterator<>&)): New.
(copy, move): Adapt, call __copy_move_a.
(__copy_move_backward_a1<>(_II, _II, _OI)): New,
call __copy_move_backward_a2.
(__copy_move_backward_a1<>(_Deque_iterator<>, _Deque_iterator<>, _OI)): New.
(__copy_move_backward_a1<>(_Deque_iterator<>, _Deque_iterator<>,
_Deque_iterator<>)): New.
(__copy_move_backward_a1<>(_II, _II, _Deque_iterator<>)): New.
(__copy_move_backward_a<>(_II, _II, _OI)): Adapt, call
__copy_move_backward_a1<>.
(__copy_move_backward_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&,
_OI)): New.
(__copy_move_backward_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&,
const _Safe_iterator<>&)): New.
(__copy_move_backward_a<>(_II, _II, const _Safe_iterator<>&)): New.
(copy_backward, move_backward): Adapt, call __copy_move_backward_a<>.
(__fill_a): Rename into...
(__fill_a1): ... this.
(__fill_a1(__normal_iterator<>, __normal_iterator<>, const _Tp&)): New.
(__fill_a1(const _Deque_iterator<>&, const _Deque_iterator<>&, _VTp)):
New.
(__fill_a(_FIte, _FIte, const _Tp&)): New, call __fill_a1.
(__fill_a(const _Safe_iterator<>&, const _Safe_iterator<>&,
const _Tp&)): New.
(fill): Adapt, remove __niter_base usage.
(__fill_n_a): Rename into...
(__fill_n_a1): ...this.
(__fill_n_a(const _Safe_iterator<>&, _Size, const _Tp&,
input_iterator_tag)): New.
(__fill_n_a(_OI, _Size, const _Tp&, output_iterator_tag)): New, call
__fill_n_a1.
(__fill_n_a(_OI, _Size, const _Tp&, random_access_iterator_tag)): New,
call __fill_a.
(__equal_aux): Rename into...
(__equal_aux1): ...this.
(__equal_aux1(_Deque_iterator<>, _Deque_iterator<>, _OI)): New.
(__equal_aux1(_Deque_iterator<>, _Deque_iterator<>,
_Deque_iterator<>)): New.
(__equal_aux1(_II, _II, _Deque_iterator<>)): New.
(__equal_aux(_II1, _II1, _II2)): New, call __equal_aux1.
(__equal_aux(const _Safe_iterator<>&, const _Safe_iterator<>&,
_OI)): New.
(__equal_aux(const _Safe_iterator<>&, const _Safe_iterator<>&,
const _Safe_iterator<>&)): New.
(__equal_aux(_II, _II, const _Safe_iterator<>&)): New.
(equal(_II1, _II1, _II2)): Adapt.
* include/bits/stl_deque.h
(fill, copy, copy_backward, move, move_backward): Remove.
* include/bits/deque.tcc: Include <bits/stl_algobase.h>.
(__fill_a1): New.
(__copy_move_dit): New.
(__copy_move_a1): New, use latter.
(__copy_move_a1(_II, _II, _Deque_iterator<>)): New.
(__copy_move_backward_dit): New.
(__copy_move_backward_a1): New, use latter.
(__copy_move_backward_a1(_II, _II, _Deque_iterator<>)): New.
(__equal_dit): New.
(__equal_aux1): New, use latter.
(__equal_aux1(_II, _II, _Deque_iterator<>)): New.
* include/std/numeric (__is_random_access_iter): Move...
* include/bits/stl_iterator_base_types.h (__is_random_access_iter): ...
here. Provide pre-C++11 definition.
* include/debug/debug.h (_Safe_iterator<>): New declaration.
* include/debug/safe_iterator.h (_Safe_iterator<>::_M_can_advance): Add
__strict parameter.
* include/debug/safe_iterator.tcc: Include <bits/stl_algobase.h>.
(_Safe_iterator<>::_M_can_advance): Adapt.
(std::__copy_move_a, std::__copy_move_backward_a, __fill_a): New.
(__fill_n_a, __equal_aux): New.
* include/debug/stl_iterator.h (__niter_base): Remove.
* include/debug/vector (__niter_base): Remove.
* testsuite/performance/25_algorithms/copy_backward_deque_iterators.cc:
Include <vector> and <list>. Add benches.
* testsuite/performance/25_algorithms/copy_deque_iterators.cc: Likewise.
* testsuite/performance/25_algorithms/equal_deque_iterators.cc: Likewise.
* testsuite/25_algorithms/copy/debug/1_neg.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/2.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/31.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/32.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/33.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/41.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/42.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/43.cc: New.
* testsuite/25_algorithms/copy/streambuf_iterators/char/4.cc (test02):
New.
* testsuite/25_algorithms/copy_backward/deque_iterators/2.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/1.cc: New.
* testsuite/25_algorithms/fill/deque_iterators/1.cc: New.
* testsuite/25_algorithms/move/deque_iterators/2.cc: New.
* testsuite/25_algorithms/move_backward/deque_iterators/2.cc: New.
From-SVN: r279201
Diffstat (limited to 'libstdc++-v3')
28 files changed, 1988 insertions, 259 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 3f5d01eabf0..2b8b9de8e07 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,107 @@ +2019-12-10 François Dumont <fdumont@gcc.gnu.org> + + * include/bits/stl_algobase.h + (__copy_move_a1<>(_II, _II, _OI)): New. + (__copy_move_a1<>(_Deque_iterator<>, _Deque_iterator<>, _OI)): New. + (__copy_move_a1<>(_Deque_iterator<>, _Deque_iterator<>, + _Deque_iterator<>)): New. + (__copy_move_a1<>(_II, _II, _Deque_iterator<>)): New. + (__copy_move_a<>(_II, _II, _OI)): Adapt, call __copy_move_a1<>. + (__copy_move_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&, + _OI)): New. + (__copy_move_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&, + const _Safe_iterator<>&)): New. + (__copy_move_a<>(_II, _II, const _Safe_iterator<>&)): New. + (copy, move): Adapt, call __copy_move_a. + (__copy_move_backward_a1<>(_II, _II, _OI)): New, + call __copy_move_backward_a2. + (__copy_move_backward_a1<>(_Deque_iterator<>, _Deque_iterator<>, _OI)): New. + (__copy_move_backward_a1<>(_Deque_iterator<>, _Deque_iterator<>, + _Deque_iterator<>)): New. + (__copy_move_backward_a1<>(_II, _II, _Deque_iterator<>)): New. + (__copy_move_backward_a<>(_II, _II, _OI)): Adapt, call + __copy_move_backward_a1<>. + (__copy_move_backward_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&, + _OI)): New. + (__copy_move_backward_a<>(const _Safe_iterator<>&, const _Safe_iterator<>&, + const _Safe_iterator<>&)): New. + (__copy_move_backward_a<>(_II, _II, const _Safe_iterator<>&)): New. + (copy_backward, move_backward): Adapt, call __copy_move_backward_a<>. + (__fill_a): Rename into... + (__fill_a1): ... this. + (__fill_a1(__normal_iterator<>, __normal_iterator<>, const _Tp&)): New. + (__fill_a1(const _Deque_iterator<>&, const _Deque_iterator<>&, _VTp)): + New. + (__fill_a(_FIte, _FIte, const _Tp&)): New, call __fill_a1. + (__fill_a(const _Safe_iterator<>&, const _Safe_iterator<>&, + const _Tp&)): New. + (fill): Adapt, remove __niter_base usage. + (__fill_n_a): Rename into... + (__fill_n_a1): ...this. + (__fill_n_a(const _Safe_iterator<>&, _Size, const _Tp&, + input_iterator_tag)): New. + (__fill_n_a(_OI, _Size, const _Tp&, output_iterator_tag)): New, call + __fill_n_a1. + (__fill_n_a(_OI, _Size, const _Tp&, random_access_iterator_tag)): New, + call __fill_a. + (__equal_aux): Rename into... + (__equal_aux1): ...this. + (__equal_aux1(_Deque_iterator<>, _Deque_iterator<>, _OI)): New. + (__equal_aux1(_Deque_iterator<>, _Deque_iterator<>, + _Deque_iterator<>)): New. + (__equal_aux1(_II, _II, _Deque_iterator<>)): New. + (__equal_aux(_II1, _II1, _II2)): New, call __equal_aux1. + (__equal_aux(const _Safe_iterator<>&, const _Safe_iterator<>&, + _OI)): New. + (__equal_aux(const _Safe_iterator<>&, const _Safe_iterator<>&, + const _Safe_iterator<>&)): New. + (__equal_aux(_II, _II, const _Safe_iterator<>&)): New. + (equal(_II1, _II1, _II2)): Adapt. + * include/bits/stl_deque.h + (fill, copy, copy_backward, move, move_backward): Remove. + * include/bits/deque.tcc: Include <bits/stl_algobase.h>. + (__fill_a1): New. + (__copy_move_dit): New. + (__copy_move_a1): New, use latter. + (__copy_move_a1(_II, _II, _Deque_iterator<>)): New. + (__copy_move_backward_dit): New. + (__copy_move_backward_a1): New, use latter. + (__copy_move_backward_a1(_II, _II, _Deque_iterator<>)): New. + (__equal_dit): New. + (__equal_aux1): New, use latter. + (__equal_aux1(_II, _II, _Deque_iterator<>)): New. + * include/std/numeric (__is_random_access_iter): Move... + * include/bits/stl_iterator_base_types.h (__is_random_access_iter): ... + here. Provide pre-C++11 definition. + * include/debug/debug.h (_Safe_iterator<>): New declaration. + * include/debug/safe_iterator.h (_Safe_iterator<>::_M_can_advance): Add + __strict parameter. + * include/debug/safe_iterator.tcc: Include <bits/stl_algobase.h>. + (_Safe_iterator<>::_M_can_advance): Adapt. + (std::__copy_move_a, std::__copy_move_backward_a, __fill_a): New. + (__fill_n_a, __equal_aux): New. + * include/debug/stl_iterator.h (__niter_base): Remove. + * include/debug/vector (__niter_base): Remove. + * testsuite/performance/25_algorithms/copy_backward_deque_iterators.cc: + Include <vector> and <list>. Add benches. + * testsuite/performance/25_algorithms/copy_deque_iterators.cc: Likewise. + * testsuite/performance/25_algorithms/equal_deque_iterators.cc: Likewise. + * testsuite/25_algorithms/copy/debug/1_neg.cc: New. + * testsuite/25_algorithms/copy/deque_iterators/2.cc: New. + * testsuite/25_algorithms/copy/deque_iterators/31.cc: New. + * testsuite/25_algorithms/copy/deque_iterators/32.cc: New. + * testsuite/25_algorithms/copy/deque_iterators/33.cc: New. + * testsuite/25_algorithms/copy/deque_iterators/41.cc: New. + * testsuite/25_algorithms/copy/deque_iterators/42.cc: New. + * testsuite/25_algorithms/copy/deque_iterators/43.cc: New. + * testsuite/25_algorithms/copy/streambuf_iterators/char/4.cc (test02): + New. + * testsuite/25_algorithms/copy_backward/deque_iterators/2.cc: New. + * testsuite/25_algorithms/equal/deque_iterators/1.cc: New. + * testsuite/25_algorithms/fill/deque_iterators/1.cc: New. + * testsuite/25_algorithms/move/deque_iterators/2.cc: New. + * testsuite/25_algorithms/move_backward/deque_iterators/2.cc: New. + 2019-12-10 Jonathan Wakely <jwakely@redhat.com> PR libstdc++/92886 diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc index 3f77b4f079c..ae5366d6208 100644 --- a/libstdc++-v3/include/bits/deque.tcc +++ b/libstdc++-v3/include/bits/deque.tcc @@ -56,6 +56,8 @@ #ifndef _DEQUE_TCC #define _DEQUE_TCC 1 +#include <bits/stl_algobase.h> + namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION @@ -967,155 +969,247 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); } +_GLIBCXX_END_NAMESPACE_CONTAINER + // Overload for deque::iterators, exploiting the "segmented-iterator // optimization". - template<typename _Tp> + template<typename _Tp, typename _VTp> void - fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, - const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) + __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first, + const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last, + const _VTp& __value) { - typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; + typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; + if (__first._M_node != __last._M_node) + { + std::__fill_a1(__first._M_cur, __first._M_last, __value); - for (typename _Self::_Map_pointer __node = __first._M_node + 1; - __node < __last._M_node; ++__node) - std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); + for (typename _Iter::_Map_pointer __node = __first._M_node + 1; + __node < __last._M_node; ++__node) + std::__fill_a1(*__node, *__node + _Iter::_S_buffer_size(), __value); + std::__fill_a1(__last._M_first, __last._M_cur, __value); + } + else + std::__fill_a1(__first._M_cur, __last._M_cur, __value); + } + + template<bool _IsMove, + typename _Tp, typename _Ref, typename _Ptr, typename _OI> + _OI + __copy_move_dit(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, + _OI __result) + { + typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; if (__first._M_node != __last._M_node) { - std::fill(__first._M_cur, __first._M_last, __value); - std::fill(__last._M_first, __last._M_cur, __value); + __result + = std::__copy_move_a1<_IsMove>(__first._M_cur, __first._M_last, + __result); + + for (typename _Iter::_Map_pointer __node = __first._M_node + 1; + __node != __last._M_node; ++__node) + __result + = std::__copy_move_a1<_IsMove>(*__node, + *__node + _Iter::_S_buffer_size(), + __result); + + return std::__copy_move_a1<_IsMove>(__last._M_first, __last._M_cur, + __result); } - else - std::fill(__first._M_cur, __last._M_cur, __value); + + return std::__copy_move_a1<_IsMove>(__first._M_cur, __last._M_cur, + __result); } - template<typename _Tp> - _Deque_iterator<_Tp, _Tp&, _Tp*> - copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, - _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, - _Deque_iterator<_Tp, _Tp&, _Tp*> __result) + template<bool _IsMove, + typename _Tp, typename _Ref, typename _Ptr, typename _OI> + _OI + __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, + _OI __result) + { return __copy_move_dit<_IsMove>(__first, __last, __result); } + + template<bool _IsMove, + typename _ITp, typename _IRef, typename _IPtr, typename _OTp> + _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> + __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first, + _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last, + _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result) + { return __copy_move_dit<_IsMove>(__first, __last, __result); } + + template<bool _IsMove, typename _II, typename _Tp> + typename __gnu_cxx::__enable_if< + __is_random_access_iter<_II>::__value, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type + __copy_move_a1(_II __first, _II __last, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) { - typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; - typedef typename _Self::difference_type difference_type; + typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; + typedef typename _Iter::difference_type difference_type; difference_type __len = __last - __first; while (__len > 0) { const difference_type __clen - = std::min(__len, std::min(__first._M_last - __first._M_cur, - __result._M_last - __result._M_cur)); - std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur); + = std::min(__len, __result._M_last - __result._M_cur); + std::__copy_move_a1<_IsMove>(__first, __first + __clen, + __result._M_cur); + __first += __clen; __result += __clen; __len -= __clen; } + return __result; } - template<typename _Tp> - _Deque_iterator<_Tp, _Tp&, _Tp*> - copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, - _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, - _Deque_iterator<_Tp, _Tp&, _Tp*> __result) + template<bool _IsMove, + typename _Tp, typename _Ref, typename _Ptr, typename _OI> + _OI + __copy_move_backward_dit( + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, + _OI __result) + { + typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; + if (__first._M_node != __last._M_node) + { + __result = std::__copy_move_backward_a1<_IsMove>( + __last._M_first, __last._M_cur, __result); + + for (typename _Iter::_Map_pointer __node = __last._M_node - 1; + __node != __first._M_node; --__node) + __result = std::__copy_move_backward_a1<_IsMove>( + *__node, *__node + _Iter::_S_buffer_size(), __result); + + return std::__copy_move_backward_a1<_IsMove>( + __first._M_cur, __first._M_last, __result); + } + + return std::__copy_move_backward_a1<_IsMove>( + __first._M_cur, __last._M_cur, __result); + } + + template<bool _IsMove, + typename _Tp, typename _Ref, typename _Ptr, typename _OI> + _OI + __copy_move_backward_a1( + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, + _OI __result) + { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); } + + template<bool _IsMove, + typename _ITp, typename _IRef, typename _IPtr, typename _OTp> + _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> + __copy_move_backward_a1( + _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first, + _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last, + _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result) + { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); } + + template<bool _IsMove, typename _II, typename _Tp> + typename __gnu_cxx::__enable_if< + __is_random_access_iter<_II>::__value, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type + __copy_move_backward_a1(_II __first, _II __last, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) { - typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; - typedef typename _Self::difference_type difference_type; + typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; + typedef typename _Iter::difference_type difference_type; difference_type __len = __last - __first; while (__len > 0) { - difference_type __llen = __last._M_cur - __last._M_first; - _Tp* __lend = __last._M_cur; - difference_type __rlen = __result._M_cur - __result._M_first; _Tp* __rend = __result._M_cur; - - if (!__llen) - { - __llen = _Self::_S_buffer_size(); - __lend = *(__last._M_node - 1) + __llen; - } if (!__rlen) { - __rlen = _Self::_S_buffer_size(); + __rlen = _Iter::_S_buffer_size(); __rend = *(__result._M_node - 1) + __rlen; } - const difference_type __clen = std::min(__len, - std::min(__llen, __rlen)); - std::copy_backward(__lend - __clen, __lend, __rend); + const difference_type __clen = std::min(__len, __rlen); + std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend); + __last -= __clen; __result -= __clen; __len -= __clen; } + return __result; } -#if __cplusplus >= 201103L - template<typename _Tp> - _Deque_iterator<_Tp, _Tp&, _Tp*> - move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, - _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, - _Deque_iterator<_Tp, _Tp&, _Tp*> __result) + template<typename _Tp, typename _Ref, typename _Ptr, typename _II> + bool + __equal_dit( + const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1, + const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1, + _II __first2) { - typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; - typedef typename _Self::difference_type difference_type; - - difference_type __len = __last - __first; - while (__len > 0) + typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; + if (__first1._M_node != __last1._M_node) { - const difference_type __clen - = std::min(__len, std::min(__first._M_last - __first._M_cur, - __result._M_last - __result._M_cur)); - std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur); - __first += __clen; - __result += __clen; - __len -= __clen; + if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2)) + return false; + + __first2 += __first1._M_last - __first1._M_cur; + for (typename _Iter::_Map_pointer __node = __first1._M_node + 1; + __node != __last1._M_node; + __first2 += _Iter::_S_buffer_size(), ++__node) + if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(), + __first2)) + return false; + + return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2); } - return __result; + + return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2); } - template<typename _Tp> - _Deque_iterator<_Tp, _Tp&, _Tp*> - move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, - _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, - _Deque_iterator<_Tp, _Tp&, _Tp*> __result) + template<typename _Tp, typename _Ref, typename _Ptr, typename _II> + typename __gnu_cxx::__enable_if< + __is_random_access_iter<_II>::__value, bool>::__type + __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1, + _II __first2) + { return std::__equal_dit(__first1, __last1, __first2); } + + template<typename _Tp1, typename _Ref1, typename _Ptr1, + typename _Tp2, typename _Ref2, typename _Ptr2> + bool + __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2) + { return std::__equal_dit(__first1, __last1, __first2); } + + template<typename _II, typename _Tp, typename _Ref, typename _Ptr> + typename __gnu_cxx::__enable_if< + __is_random_access_iter<_II>::__value, bool>::__type + __equal_aux1(_II __first1, _II __last1, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2) { - typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; - typedef typename _Self::difference_type difference_type; + typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; + typedef typename _Iter::difference_type difference_type; - difference_type __len = __last - __first; + difference_type __len = __last1 - __first1; while (__len > 0) { - difference_type __llen = __last._M_cur - __last._M_first; - _Tp* __lend = __last._M_cur; - - difference_type __rlen = __result._M_cur - __result._M_first; - _Tp* __rend = __result._M_cur; - - if (!__llen) - { - __llen = _Self::_S_buffer_size(); - __lend = *(__last._M_node - 1) + __llen; - } - if (!__rlen) - { - __rlen = _Self::_S_buffer_size(); - __rend = *(__result._M_node - 1) + __rlen; - } + const difference_type __clen + = std::min(__len, __first2._M_last - __first2._M_cur); + if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur)) + return false; - const difference_type __clen = std::min(__len, - std::min(__llen, __rlen)); - std::move_backward(__lend - __clen, __lend, __rend); - __last -= __clen; - __result -= __clen; + __first1 += __clen; __len -= __clen; + __first2 += __clen; } - return __result; + + return true; } -#endif -_GLIBCXX_END_NAMESPACE_CONTAINER _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index a2fd306e6d0..40d056ae8d5 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -454,22 +454,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } }; - template<bool _IsMove, typename _II, typename _OI> - _GLIBCXX20_CONSTEXPR - inline _OI - __copy_move_a(_II __first, _II __last, _OI __result) - { - typedef typename iterator_traits<_II>::value_type _ValueTypeI; - typedef typename iterator_traits<_OI>::value_type _ValueTypeO; - typedef typename iterator_traits<_II>::iterator_category _Category; - const bool __simple = (__is_trivially_copyable(_ValueTypeI) - && __is_pointer<_II>::__value - && __is_pointer<_OI>::__value - && __are_same<_ValueTypeI, _ValueTypeO>::__value); - return std::__copy_move<_IsMove, __simple, - _Category>::__copy_m(__first, __last, __result); - } - // Helpers for streambuf iterators (either istream or ostream). // NB: avoid including <iosfwd>, relatively large. template<typename _CharT> @@ -504,12 +488,82 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION inline _OI __copy_move_a2(_II __first, _II __last, _OI __result) { + typedef typename iterator_traits<_II>::value_type _ValueTypeI; + typedef typename iterator_traits<_OI>::value_type _ValueTypeO; + typedef typename iterator_traits<_II>::iterator_category _Category; + const bool __simple = (__is_trivially_copyable(_ValueTypeI) + && __is_pointer<_II>::__value + && __is_pointer<_OI>::__value + && __are_same<_ValueTypeI, _ValueTypeO>::__value); + return std::__copy_move<_IsMove, __simple, + _Category>::__copy_m(__first, __last, __result); + } + +_GLIBCXX_BEGIN_NAMESPACE_CONTAINER + + template<typename _Tp, typename _Ref, typename _Ptr> + struct _Deque_iterator; + +_GLIBCXX_END_NAMESPACE_CONTAINER + + template<bool _IsMove, + typename _Tp, typename _Ref, typename _Ptr, typename _OI> + _OI + __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, + _OI); + + template<bool _IsMove, + typename _ITp, typename _IRef, typename _IPtr, typename _OTp> + _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> + __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, + _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, + _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>); + + template<bool _IsMove, typename _II, typename _Tp> + typename __gnu_cxx::__enable_if< + __is_random_access_iter<_II>::__value, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type + __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>); + + template<bool _IsMove, typename _II, typename _OI> + _GLIBCXX20_CONSTEXPR + inline _OI + __copy_move_a1(_II __first, _II __last, _OI __result) + { return std::__copy_move_a2<_IsMove>(__first, __last, __result); } + + template<bool _IsMove, typename _II, typename _OI> + _GLIBCXX20_CONSTEXPR + inline _OI + __copy_move_a(_II __first, _II __last, _OI __result) + { return std::__niter_wrap(__result, - std::__copy_move_a<_IsMove>(std::__niter_base(__first), - std::__niter_base(__last), - std::__niter_base(__result))); + std::__copy_move_a1<_IsMove>(std::__niter_base(__first), + std::__niter_base(__last), + std::__niter_base(__result))); } + template<bool _IsMove, + typename _Ite, typename _Seq, typename _Cat, typename _OI> + _OI + __copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, + _OI); + + template<bool _IsMove, + typename _II, typename _Ite, typename _Seq, typename _Cat> + __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> + __copy_move_a(_II, _II, + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&); + + template<bool _IsMove, + typename _IIte, typename _ISeq, typename _ICat, + typename _OIte, typename _OSeq, typename _OCat> + ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat> + __copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, + const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, + const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&); + /** * @brief Copies the range [first,last) into result. * @ingroup mutating_algorithms @@ -538,7 +592,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_II>::value_type>) __glibcxx_requires_can_increment_range(__first, __last, __result); - return std::__copy_move_a2<__is_move_iterator<_II>::__value> + return std::__copy_move_a<__is_move_iterator<_II>::__value> (std::__miter_base(__first), std::__miter_base(__last), __result); } @@ -571,8 +625,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_II>::value_type>) __glibcxx_requires_can_increment_range(__first, __last, __result); - return std::__copy_move_a2<true>(std::__miter_base(__first), - std::__miter_base(__last), __result); + return std::__copy_move_a<true>(std::__miter_base(__first), + std::__miter_base(__last), __result); } #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp) @@ -580,7 +634,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp) #endif - template<bool, bool, typename> + template<bool _IsMove, bool _IsSimple, typename _Category> struct __copy_move_backward { template<typename _BI1, typename _BI2> @@ -669,7 +723,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<bool _IsMove, typename _BI1, typename _BI2> _GLIBCXX20_CONSTEXPR inline _BI2 - __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result) + __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result) { typedef typename iterator_traits<_BI1>::value_type _ValueType1; typedef typename iterator_traits<_BI2>::value_type _ValueType2; @@ -694,14 +748,65 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<bool _IsMove, typename _BI1, typename _BI2> _GLIBCXX20_CONSTEXPR inline _BI2 - __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result) + __copy_move_backward_a1(_BI1 __first, _BI1 __last, _BI2 __result) + { return std::__copy_move_backward_a2<_IsMove>(__first, __last, __result); } + + template<bool _IsMove, + typename _Tp, typename _Ref, typename _Ptr, typename _OI> + _OI + __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, + _OI); + + template<bool _IsMove, + typename _ITp, typename _IRef, typename _IPtr, typename _OTp> + _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> + __copy_move_backward_a1( + _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, + _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, + _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>); + + template<bool _IsMove, typename _II, typename _Tp> + typename __gnu_cxx::__enable_if< + __is_random_access_iter<_II>::__value, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type + __copy_move_backward_a1(_II, _II, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>); + + template<bool _IsMove, typename _II, typename _OI> + _GLIBCXX20_CONSTEXPR + inline _OI + __copy_move_backward_a(_II __first, _II __last, _OI __result) { return std::__niter_wrap(__result, - std::__copy_move_backward_a<_IsMove> + std::__copy_move_backward_a1<_IsMove> (std::__niter_base(__first), std::__niter_base(__last), std::__niter_base(__result))); } + template<bool _IsMove, + typename _Ite, typename _Seq, typename _Cat, typename _OI> + _OI + __copy_move_backward_a( + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, + _OI); + + template<bool _IsMove, + typename _II, typename _Ite, typename _Seq, typename _Cat> + __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> + __copy_move_backward_a(_II, _II, + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&); + + template<bool _IsMove, + typename _IIte, typename _ISeq, typename _ICat, + typename _OIte, typename _OSeq, typename _OCat> + ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat> + __copy_move_backward_a( + const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, + const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, + const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&); + /** * @brief Copies the range [first,last) into result. * @ingroup mutating_algorithms @@ -733,7 +838,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_BI2>::value_type>) __glibcxx_requires_can_decrement_range(__first, __last, __result); - return std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value> + return std::__copy_move_backward_a<__is_move_iterator<_BI1>::__value> (std::__miter_base(__first), std::__miter_base(__last), __result); } @@ -769,9 +874,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_BI2>::value_type>) __glibcxx_requires_can_decrement_range(__first, __last, __result); - return std::__copy_move_backward_a2<true>(std::__miter_base(__first), - std::__miter_base(__last), - __result); + return std::__copy_move_backward_a<true>(std::__miter_base(__first), + std::__miter_base(__last), + __result); } #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp) @@ -783,8 +888,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX20_CONSTEXPR inline typename __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type - __fill_a(_ForwardIterator __first, _ForwardIterator __last, - const _Tp& __value) + __fill_a1(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __value) { for (; __first != __last; ++__first) *__first = __value; @@ -794,8 +899,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX20_CONSTEXPR inline typename __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type - __fill_a(_ForwardIterator __first, _ForwardIterator __last, - const _Tp& __value) + __fill_a1(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __value) { const _Tp __tmp = __value; for (; __first != __last; ++__first) @@ -806,13 +911,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Tp> inline typename __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type - __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c) + __fill_a1(_Tp* __first, _Tp* __last, const _Tp& __c) { const _Tp __tmp = __c; if (const size_t __len = __last - __first) __builtin_memset(__first, static_cast<unsigned char>(__tmp), __len); } + template<typename _Ite, typename _Cont, typename _Tp> + _GLIBCXX20_CONSTEXPR + inline void + __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first, + ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last, + const _Tp& __value) + { std::__fill_a1(__first.base(), __last.base(), __value); } + + template<typename _Tp, typename _VTp> + void + __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&, + const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&, + const _VTp&); + + template<typename _FIte, typename _Tp> + _GLIBCXX20_CONSTEXPR + inline void + __fill_a(_FIte __first, _FIte __last, const _Tp& __value) + { std::__fill_a1(__first, __last, __value); } + + template<typename _Ite, typename _Seq, typename _Cat, typename _Tp> + void + __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, + const _Tp&); + /** * @brief Fills the range [first,last) with copies of value. * @ingroup mutating_algorithms @@ -835,8 +966,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _ForwardIterator>) __glibcxx_requires_valid_range(__first, __last); - std::__fill_a(std::__niter_base(__first), std::__niter_base(__last), - __value); + std::__fill_a(__first, __last, __value); } // Used by fill_n, generate_n, etc. to convert _Size to an integral type: @@ -893,11 +1023,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX20_CONSTEXPR inline typename __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type - __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) + __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value) { -#if __cplusplus >= 201103L - static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); -#endif for (; __n > 0; --__n, (void) ++__first) *__first = __value; return __first; @@ -907,24 +1034,60 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX20_CONSTEXPR inline typename __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type - __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) + __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value) { -#if __cplusplus >= 201103L - static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); -#endif const _Tp __tmp = __value; for (; __n > 0; --__n, (void) ++__first) *__first = __tmp; return __first; } - template<typename _Size, typename _Tp> + template<typename _Ite, typename _Seq, typename _Cat, typename _Size, + typename _Tp> + ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> + __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first, + _Size __n, const _Tp& __value, + std::input_iterator_tag); + + template<typename _OutputIterator, typename _Size, typename _Tp> _GLIBCXX20_CONSTEXPR - inline typename - __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type - __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c) + inline _OutputIterator + __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value, + std::output_iterator_tag) + { +#if __cplusplus >= 201103L + static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); +#endif + return __fill_n_a1(__first, __n, __value); + } + + template<typename _OutputIterator, typename _Size, typename _Tp> + _GLIBCXX20_CONSTEXPR + inline _OutputIterator + __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value, + std::input_iterator_tag) + { +#if __cplusplus >= 201103L + static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); +#endif + return __fill_n_a1(__first, __n, __value); + } + + template<typename _OutputIterator, typename _Size, typename _Tp> + _GLIBCXX20_CONSTEXPR + inline _OutputIterator + __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value, + std::random_access_iterator_tag) { - std::__fill_a(__first, __first + __n, __c); +#if __cplusplus >= 201103L + static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); +#endif + if (__n <= 0) + return __first; + + __glibcxx_requires_can_increment(__first, __n); + + std::__fill_a(__first, __first + __n, __value); return __first + __n; } @@ -953,10 +1116,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // concept requirements __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>) - return std::__niter_wrap(__first, - std::__fill_n_a(std::__niter_base(__first), - std::__size_to_integer(__n), - __value)); + return std::__fill_n_a(__first, std::__size_to_integer(__n), __value, + std::__iterator_category(__first)); } template<bool _BoolType> @@ -988,10 +1149,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } }; + template<typename _Tp, typename _Ref, typename _Ptr, typename _II> + typename __gnu_cxx::__enable_if< + __is_random_access_iter<_II>::__value, bool>::__type + __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, + _II); + + template<typename _Tp1, typename _Ref1, typename _Ptr1, + typename _Tp2, typename _Ref2, typename _Ptr2> + bool + __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>); + + template<typename _II, typename _Tp, typename _Ref, typename _Ptr> + typename __gnu_cxx::__enable_if< + __is_random_access_iter<_II>::__value, bool>::__type + __equal_aux1(_II, _II, + _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>); + template<typename _II1, typename _II2> _GLIBCXX20_CONSTEXPR inline bool - __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2) + __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2) { typedef typename iterator_traits<_II1>::value_type _ValueType1; typedef typename iterator_traits<_II2>::value_type _ValueType2; @@ -1004,6 +1185,34 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return std::__equal<__simple>::equal(__first1, __last1, __first2); } + template<typename _II1, typename _II2> + _GLIBCXX20_CONSTEXPR + inline bool + __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2) + { + return std::__equal_aux1(std::__niter_base(__first1), + std::__niter_base(__last1), + std::__niter_base(__first2)); + } + + template<typename _II1, typename _Seq1, typename _Cat1, typename _II2> + bool + __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, + const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, + _II2); + + template<typename _II1, typename _II2, typename _Seq2, typename _Cat2> + bool + __equal_aux(_II1, _II1, + const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&); + + template<typename _II1, typename _Seq1, typename _Cat1, + typename _II2, typename _Seq2, typename _Cat2> + bool + __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, + const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, + const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&); + template<typename, typename> struct __lc_rai { @@ -1230,9 +1439,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO typename iterator_traits<_II2>::value_type>) __glibcxx_requires_can_increment_range(__first1, __last1, __first2); - return std::__equal_aux(std::__niter_base(__first1), - std::__niter_base(__last1), - std::__niter_base(__first2)); + return std::__equal_aux(__first1, __last1, __first2); } /** diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h index 676768c0159..dcb68da4b61 100644 --- a/libstdc++-v3/include/bits/stl_deque.h +++ b/libstdc++-v3/include/bits/stl_deque.h @@ -373,77 +373,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return __x + __n; } }; - template<typename _Tp> - void - fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&, - const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&); - - template<typename _Tp> - _Deque_iterator<_Tp, _Tp&, _Tp*> - copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>, - _Deque_iterator<_Tp, const _Tp&, const _Tp*>, - _Deque_iterator<_Tp, _Tp&, _Tp*>); - - template<typename _Tp> - inline _Deque_iterator<_Tp, _Tp&, _Tp*> - copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first, - _Deque_iterator<_Tp, _Tp&, _Tp*> __last, - _Deque_iterator<_Tp, _Tp&, _Tp*> __result) - { return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first), - _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last), - __result); } - - template<typename _Tp> - _Deque_iterator<_Tp, _Tp&, _Tp*> - copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>, - _Deque_iterator<_Tp, const _Tp&, const _Tp*>, - _Deque_iterator<_Tp, _Tp&, _Tp*>); - - template<typename _Tp> - inline _Deque_iterator<_Tp, _Tp&, _Tp*> - copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first, - _Deque_iterator<_Tp, _Tp&, _Tp*> __last, - _Deque_iterator<_Tp, _Tp&, _Tp*> __result) - { return std::copy_backward(_Deque_iterator<_Tp, - const _Tp&, const _Tp*>(__first), - _Deque_iterator<_Tp, - const _Tp&, const _Tp*>(__last), - __result); } - -#if __cplusplus >= 201103L - template<typename _Tp> - _Deque_iterator<_Tp, _Tp&, _Tp*> - move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>, - _Deque_iterator<_Tp, const _Tp&, const _Tp*>, - _Deque_iterator<_Tp, _Tp&, _Tp*>); - - template<typename _Tp> - inline _Deque_iterator<_Tp, _Tp&, _Tp*> - move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first, - _Deque_iterator<_Tp, _Tp&, _Tp*> __last, - _Deque_iterator<_Tp, _Tp&, _Tp*> __result) - { return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first), - _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last), - __result); } - - template<typename _Tp> - _Deque_iterator<_Tp, _Tp&, _Tp*> - move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>, - _Deque_iterator<_Tp, const _Tp&, const _Tp*>, - _Deque_iterator<_Tp, _Tp&, _Tp*>); - - template<typename _Tp> - inline _Deque_iterator<_Tp, _Tp&, _Tp*> - move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first, - _Deque_iterator<_Tp, _Tp&, _Tp*> __last, - _Deque_iterator<_Tp, _Tp&, _Tp*> __result) - { return std::move_backward(_Deque_iterator<_Tp, - const _Tp&, const _Tp*>(__first), - _Deque_iterator<_Tp, - const _Tp&, const _Tp*>(__last), - __result); } -#endif - /** * Deque base class. This class provides the unified face for %deque's * allocation. This class's constructor and destructor allocate and diff --git a/libstdc++-v3/include/bits/stl_iterator_base_types.h b/libstdc++-v3/include/bits/stl_iterator_base_types.h index 3fad5869b40..b29a76543f4 100644 --- a/libstdc++-v3/include/bits/stl_iterator_base_types.h +++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h @@ -249,10 +249,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using _RequireInputIter = __enable_if_t<is_convertible<__iterator_category_t<_InIter>, input_iterator_tag>::value>; + + template<typename _It, + typename _Cat = __iterator_category_t<_It>> + struct __is_random_access_iter + : is_base_of<random_access_iterator_tag, _Cat> + { + typedef is_base_of<random_access_iterator_tag, _Cat> _Base; + enum { __value = _Base::value }; + }; +#else + template<typename _It, typename _Traits = iterator_traits<_It>, + typename _Cat = typename _Traits::iterator_category> + struct __is_random_access_iter + { enum { __value = __is_base_of(random_access_iterator_tag, _Cat) }; }; #endif _GLIBCXX_END_NAMESPACE_VERSION } // namespace #endif /* _STL_ITERATOR_BASE_TYPES_H */ - diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h index d851b4ae6dd..8d3a8606ccd 100644 --- a/libstdc++-v3/include/debug/debug.h +++ b/libstdc++-v3/include/debug/debug.h @@ -56,6 +56,9 @@ namespace std namespace __gnu_debug { using namespace std::__debug; + + template<typename _Ite, typename _Seq, typename _Cat> + struct _Safe_iterator; } #ifndef _GLIBCXX_DEBUG diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h index fa0d03f39dc..536690d6dcd 100644 --- a/libstdc++-v3/include/debug/safe_iterator.h +++ b/libstdc++-v3/include/debug/safe_iterator.h @@ -400,7 +400,7 @@ namespace __gnu_debug // Can we advance the iterator @p __n steps (@p __n may be negative) bool - _M_can_advance(difference_type __n) const; + _M_can_advance(difference_type __n, bool __strict = false) const; // Is the iterator range [*this, __rhs) valid? bool diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc index 1750bc473d2..1d98a882d56 100644 --- a/libstdc++-v3/include/debug/safe_iterator.tcc +++ b/libstdc++-v3/include/debug/safe_iterator.tcc @@ -29,6 +29,8 @@ #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC #define _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC 1 +#include <bits/stl_algobase.h> + namespace __gnu_debug { template<typename _Iterator, typename _Sequence, typename _Category> @@ -82,7 +84,7 @@ namespace __gnu_debug template<typename _Iterator, typename _Sequence, typename _Category> bool _Safe_iterator<_Iterator, _Sequence, _Category>:: - _M_can_advance(difference_type __n) const + _M_can_advance(difference_type __n, bool __strict) const { if (this->_M_singular()) return false; @@ -94,17 +96,17 @@ namespace __gnu_debug { std::pair<difference_type, _Distance_precision> __dist = _M_get_distance_from_begin(); - bool __ok = ((__dist.second == __dp_exact && __dist.first >= -__n) - || (__dist.second != __dp_exact && __dist.first > 0)); - return __ok; + return __dist.second == __dp_exact + ? __dist.first >= -__n + : !__strict && __dist.first > 0; } else { std::pair<difference_type, _Distance_precision> __dist = _M_get_distance_to_end(); - bool __ok = ((__dist.second == __dp_exact && __dist.first >= __n) - || (__dist.second != __dp_exact && __dist.first > 0)); - return __ok; + return __dist.second == __dp_exact + ? __dist.first >= __n + : !__strict && __dist.first > 0; } } @@ -228,4 +230,241 @@ namespace __gnu_debug } } // namespace __gnu_debug +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + template<bool _IsMove, + typename _Ite, typename _Seq, typename _Cat, typename _OI> + _OI + __copy_move_a( + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first, + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last, + _OI __result) + { + typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + __glibcxx_check_can_increment(__result, __dist.first); + + if (__dist.second > ::__gnu_debug::__dp_equality) + return std::__copy_move_a<_IsMove>(__first.base(), __last.base(), + __result); + + return std::__copy_move_a1<_IsMove>(__first, __last, __result); + } + + template<bool _IsMove, + typename _II, typename _Ite, typename _Seq, typename _Cat> + __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> + __copy_move_a(_II __first, _II __last, + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __result) + { + typename ::__gnu_debug::_Distance_traits<_II>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + __glibcxx_check_can_increment(__result, __dist.first); + + if (__dist.second > ::__gnu_debug::__dp_sign + && __result._M_can_advance(__dist.first, true)) + return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>( + std::__copy_move_a<_IsMove>(__first, __last, __result.base()), + __result._M_sequence); + + return std::__copy_move_a1<_IsMove>(__first, __last, __result); + } + + template<bool _IsMove, + typename _IIte, typename _ISeq, typename _ICat, + typename _OIte, typename _OSeq, typename _OCat> + ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat> + __copy_move_a( + const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __first, + const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __last, + const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>& __result) + { + typename ::__gnu_debug::_Distance_traits<_IIte>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + __glibcxx_check_can_increment(__result, __dist.first); + + if (__dist.second > ::__gnu_debug::__dp_equality) + { + if (__dist.second > ::__gnu_debug::__dp_sign + && __result._M_can_advance(__dist.first, true)) + return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>( + std::__copy_move_a<_IsMove>(__first.base(), __last.base(), + __result.base()), + __result._M_sequence); + + return std::__copy_move_a<_IsMove>(__first.base(), __last.base(), + __result); + } + + return std::__copy_move_a1<_IsMove>(__first, __last, __result); + } + + template<bool _IsMove, + typename _Ite, typename _Seq, typename _Cat, typename _OI> + _OI + __copy_move_backward_a( + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first, + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last, + _OI __result) + { + typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + __glibcxx_check_can_increment(__result, -__dist.first); + + if (__dist.second > ::__gnu_debug::__dp_equality) + return std::__copy_move_backward_a<_IsMove>( + __first.base(), __last.base(), __result); + + return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result); + } + + template<bool _IsMove, + typename _II, typename _Ite, typename _Seq, typename _Cat> + __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> + __copy_move_backward_a(_II __first, _II __last, + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __result) + { + typename ::__gnu_debug::_Distance_traits<_II>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + __glibcxx_check_can_increment(__result, -__dist.first); + + if (__dist.second > ::__gnu_debug::__dp_sign + && __result._M_can_advance(-__dist.first, true)) + return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>( + std::__copy_move_backward_a<_IsMove>(__first, __last, + __result.base()), + __result._M_sequence); + + return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result); + } + + template<bool _IsMove, + typename _IIte, typename _ISeq, typename _ICat, + typename _OIte, typename _OSeq, typename _OCat> + ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat> + __copy_move_backward_a( + const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __first, + const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __last, + const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>& __result) + { + typename ::__gnu_debug::_Distance_traits<_IIte>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + __glibcxx_check_can_increment(__result, -__dist.first); + + if (__dist.second > ::__gnu_debug::__dp_equality) + { + if (__dist.second > ::__gnu_debug::__dp_sign + && __result._M_can_advance(-__dist.first, true)) + return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>( + std::__copy_move_backward_a<_IsMove>(__first.base(), __last.base(), + __result.base()), + __result._M_sequence); + + return std::__copy_move_backward_a<_IsMove>( + __first.base(), __last.base(), __result); + } + + return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result); + } + + template<typename _Ite, typename _Seq, typename _Cat, typename _Tp> + void + __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first, + const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last, + const _Tp& __value) + { + typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist; + __glibcxx_check_valid_range2(__first, __last, __dist); + + if (__dist.second > ::__gnu_debug::__dp_equality) + std::__fill_a(__first.base(), __last.base(), __value); + + std::__fill_a1(__first, __last, __value); + } + + template<typename _Ite, typename _Seq, typename _Cat, typename _Size, + typename _Tp> + ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> + __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first, + _Size __n, const _Tp& __value, + std::input_iterator_tag) + { +#if __cplusplus >= 201103L + static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); +#endif + + if (__n <= 0) + return __first; + + __glibcxx_check_can_increment(__first, __n); + if (__first._M_can_advance(__n, true)) + return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>( + std::__fill_n_a(__first.base(), __n, __value, _Cat()), + __first._M_sequence); + + return std::__fill_n_a1(__first, __n, __value); + } + + template<typename _II1, typename _Seq1, typename _Cat1, typename _II2> + bool + __equal_aux( + const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __first1, + const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __last1, + _II2 __first2) + { + typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist; + __glibcxx_check_valid_range2(__first1, __last1, __dist); + __glibcxx_check_can_increment(__first2, __dist.first); + + if (__dist.second > ::__gnu_debug::__dp_equality) + return std::__equal_aux(__first1.base(), __last1.base(), __first2); + + return std::__equal_aux1(__first1, __last1, __first2); + } + + template<typename _II1, typename _II2, typename _Seq2, typename _Cat2> + bool + __equal_aux(_II1 __first1, _II1 __last1, + const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>& __first2) + { + typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist; + __glibcxx_check_valid_range2(__first1, __last1, __dist); + __glibcxx_check_can_increment(__first2, __dist.first); + + if (__dist.second > ::__gnu_debug::__dp_sign + && __first2._M_can_advance(__dist.first, true)) + return std::__equal_aux(__first1, __last1, __first2.base()); + + return std::__equal_aux1(__first1, __last1, __first2); + } + + template<typename _II1, typename _Seq1, typename _Cat1, + typename _II2, typename _Seq2, typename _Cat2> + bool + __equal_aux( + const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __first1, + const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __last1, + const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>& __first2) + { + typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist; + __glibcxx_check_valid_range2(__first1, __last1, __dist); + __glibcxx_check_can_increment(__first2, __dist.first); + + if (__dist.second > ::__gnu_debug::__dp_equality) + { + if (__dist.second > ::__gnu_debug::__dp_sign && + __first2._M_can_advance(__dist.first, true)) + return std::__equal_aux(__first1.base(), __last1.base(), + __first2.base()); + return std::__equal_aux(__first1.base(), __last1.base(), __first2); + } + + return __equal_aux1(__first1, __last1, __first2); + } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std + #endif diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h index 3b9ee5d9beb..8a7c19428a6 100644 --- a/libstdc++-v3/include/debug/stl_iterator.h +++ b/libstdc++-v3/include/debug/stl_iterator.h @@ -115,17 +115,4 @@ namespace __gnu_debug #endif } -namespace std -{ -_GLIBCXX_BEGIN_NAMESPACE_VERSION - - template<typename _Iterator, typename _Container, typename _Sequence> - _Iterator - __niter_base(const __gnu_debug::_Safe_iterator< - __gnu_cxx::__normal_iterator<_Iterator, _Container>, - _Sequence, std::random_access_iterator_tag>&); - -_GLIBCXX_END_NAMESPACE_VERSION -} - #endif diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector index 56b5e140fd3..8138600f143 100644 --- a/libstdc++-v3/include/debug/vector +++ b/libstdc++-v3/include/debug/vector @@ -794,13 +794,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION }; #endif - template<typename _Iterator, typename _Container, typename _Sequence> - _Iterator - __niter_base(const __gnu_debug::_Safe_iterator< - __gnu_cxx::__normal_iterator<_Iterator, _Container>, - _Sequence, std::random_access_iterator_tag>& __it) - { return std::__niter_base(__it.base()); } - #if __cplusplus >= 201703L namespace __detail::__variant { diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric index a164a9e6430..0135db889c6 100644 --- a/libstdc++-v3/include/std/numeric +++ b/libstdc++-v3/include/std/numeric @@ -229,12 +229,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// @addtogroup numeric_ops /// @{ - /// @cond undocumented - template<typename _It, typename _Cat = __iterator_category_t<_It>> - using __is_random_access_iter - = is_base_of<random_access_iterator_tag, _Cat>; - /// @endcond - /** * @brief Calculate reduction of values in a range. * diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/debug/1_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy/debug/1_neg.cc new file mode 100644 index 00000000000..f5a396e811d --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/copy/debug/1_neg.cc @@ -0,0 +1,41 @@ +// Copyright (C) 2019 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/>. + +// 25.2.1 [lib.alg.copy] Copy. + +// { dg-do run { xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include <algorithm> +#include <list> +#include <vector> + +void +test01() +{ + std::list<int> l(10, 1); + std::vector<int> v(5, 0); + + std::copy(++l.begin(), --l.end(), v.begin()); +} + +int +main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/2.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/2.cc new file mode 100644 index 00000000000..7b0dc3d2126 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/2.cc @@ -0,0 +1,109 @@ +// Copyright (C) 2019 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 <algorithm> +#include <vector> +#include <list> +#include <deque> + +#include <testsuite_hooks.h> + +void test01() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) + d.push_back(i); + + deque<int> dest(d.size(), 0); + + copy(d.begin(), d.end(), dest.begin()); + + VERIFY( equal(dest.begin(), dest.end(), d.begin()) ); +} + +void test02() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != 4 * _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) + d.push_back(i); + + deque<int> dest(d.size(), 0); + + const deque<int>& cd = d; + copy(cd.begin(), cd.end(), dest.begin()); + + VERIFY( equal(dest.begin(), dest.end(), cd.begin()) ); +} + +void test03() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + d.pop_front(); + d.pop_back(); + + vector<int> dest(d.size(), 0); + + copy(d.begin(), d.end(), dest.begin()); + VERIFY( equal(dest.begin(), dest.end(), d.begin()) ); +} + +void test04() +{ + using namespace std; + + vector<int> v; + for (int i = 0; i != 1024; ++i) + v.push_back(i); + + deque<int> dest(v.size() - 10, 0); + + std::copy(v.begin() + 5, v.end() - 5, dest.begin()); + VERIFY( std::equal(dest.begin(), dest.end(), v.begin() + 5) ); +} + +void test05() +{ + using namespace std; + + std::list<int> l; + for (int i = 0; i != 1024; ++i) + l.push_back(i); + + std::deque<int> dest(l.size(), 0); + + std::copy(l.begin(), l.end(), dest.begin()); + VERIFY( std::equal(dest.begin(), dest.end(), l.begin()) ); +} + +int main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/31.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/31.cc new file mode 100644 index 00000000000..ae2c33b1d10 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/31.cc @@ -0,0 +1,43 @@ +// Copyright (C) 2019 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/>. +// +// { dg-do run { xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include <algorithm> +#include <deque> +#include <vector> + +#include <testsuite_hooks.h> + +void test01() +{ + std::deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + std::vector<int> dest(d.size(), 0); + + const std::deque<int>& cd = d; + std::copy(cd.begin() + 10, cd.begin() + 5, dest.begin()); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/32.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/32.cc new file mode 100644 index 00000000000..8028bd6b542 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/32.cc @@ -0,0 +1,43 @@ +// Copyright (C) 2019 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/>. +// +// { dg-do run { xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include <algorithm> +#include <deque> +#include <vector> + +#include <testsuite_hooks.h> + +void test01() +{ + std::deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + std::vector<int> dest(d.size() / 2, 0); + + const std::deque<int>& cd = d; + std::copy(cd.begin(), cd.end(), dest.begin()); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/33.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/33.cc new file mode 100644 index 00000000000..1633fafd20c --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/33.cc @@ -0,0 +1,57 @@ +// Copyright (C) 2019 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/>. +// +// { dg-do run { xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include <algorithm> +#include <deque> +#include <list> + +#include <testsuite_hooks.h> + +void test01() +{ + std::deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + std::list<int> dest(d.size(), 0); + + const std::deque<int>& cd = d; + std::copy(cd.begin(), cd.end(), dest.begin()); +} + +void test02() +{ + std::deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + std::list<int> dest(d.size() / 2, 0); + std::list<int>::iterator lit = dest.begin(); + + const std::deque<int>& cd = d; + std::copy(cd.begin(), cd.end(), ++lit); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/41.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/41.cc new file mode 100644 index 00000000000..0c9d949807a --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/41.cc @@ -0,0 +1,42 @@ +// Copyright (C) 2019 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/>. +// +// { dg-do run { xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include <algorithm> +#include <deque> +#include <vector> + +#include <testsuite_hooks.h> + +void test01() +{ + std::deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + std::vector<int> dest(d.size(), 0); + + std::copy(d.begin() + 10, d.begin() + 5, dest.begin()); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/42.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/42.cc new file mode 100644 index 00000000000..c7e0c1f49fd --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/42.cc @@ -0,0 +1,42 @@ +// Copyright (C) 2019 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/>. +// +// { dg-do run { xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include <algorithm> +#include <deque> +#include <vector> + +#include <testsuite_hooks.h> + +void test01() +{ + std::deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + std::vector<int> dest(d.size() / 2, 0); + + std::copy(d.begin(), d.end(), dest.begin()); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/43.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/43.cc new file mode 100644 index 00000000000..2f29afae09f --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/43.cc @@ -0,0 +1,55 @@ +// Copyright (C) 2019 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/>. +// +// { dg-do run { xfail *-*-* } } +// { dg-require-debug-mode "" } + +#include <algorithm> +#include <deque> +#include <list> + +#include <testsuite_hooks.h> + +void test01() +{ + std::deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + std::list<int> dest(d.size(), 0); + + std::copy(d.begin(), d.end(), dest.begin()); +} + +void test02() +{ + std::deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + std::list<int> dest(d.size() / 2, 0); + std::list<int>::iterator lit = dest.begin(); + + std::copy(d.begin(), d.end(), ++lit); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/streambuf_iterators/char/4.cc b/libstdc++-v3/testsuite/25_algorithms/copy/streambuf_iterators/char/4.cc index 0709a4077ac..3fd4e271521 100644 --- a/libstdc++-v3/testsuite/25_algorithms/copy/streambuf_iterators/char/4.cc +++ b/libstdc++-v3/testsuite/25_algorithms/copy/streambuf_iterators/char/4.cc @@ -21,6 +21,8 @@ #include <fstream> #include <algorithm> #include <cstring> +#include <vector> + #include <testsuite_hooks.h> // { dg-require-fileio "" } @@ -33,7 +35,7 @@ void test01() typedef istreambuf_iterator<char> in_iterator_type; ifstream fbuf_ref("istream_unformatted-1.txt"), - fbuf("istream_unformatted-1.txt"); + fbuf("istream_unformatted-1.txt"); char buffer_ref[16500], buffer[16500]; @@ -50,8 +52,33 @@ void test01() VERIFY( !memcmp(buffer, buffer_ref, 16500) ); } +void test02() +{ + using namespace std; + + typedef istreambuf_iterator<char> in_iterator_type; + + ifstream fbuf_ref("istream_unformatted-1.txt"), + fbuf("istream_unformatted-1.txt"); + + char buffer_ref[16500]; + std::vector<char> buffer(16500, 'a'); + + fbuf_ref.read(buffer_ref, 16500); + + in_iterator_type beg(fbuf); + in_iterator_type end; + copy(beg, end, buffer.begin()); + + VERIFY( fbuf_ref.good() ); + VERIFY( fbuf.good() ); + + VERIFY( !memcmp(buffer.data(), buffer_ref, 16500) ); +} + int main() { test01(); + test02(); return 0; } diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/2.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/2.cc new file mode 100644 index 00000000000..ccde5279859 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/2.cc @@ -0,0 +1,109 @@ +// Copyright (C) 2019 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 <algorithm> +#include <vector> +#include <list> +#include <deque> + +#include <testsuite_hooks.h> + +void test01() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) + d.push_back(i); + + deque<int> dest(d.size(), 0); + + copy_backward(d.begin(), d.end(), dest.end()); + + VERIFY( equal(dest.begin(), dest.end(), d.begin()) ); +} + +void test02() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != 4 * _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) + d.push_back(i); + + deque<int> dest(d.size(), 0); + + const deque<int>& cd = d; + copy_backward(cd.begin(), cd.end(), dest.end()); + + VERIFY( equal(dest.begin(), dest.end(), cd.begin()) ); +} + +void test03() +{ + using namespace std; + + std::deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + d.pop_front(); + d.pop_back(); + + std::vector<int> dest(d.size(), 0); + + std::copy_backward(d.begin(), d.end(), dest.end()); + VERIFY( std::equal(dest.begin(), dest.end(), d.begin()) ); +} + +void test04() +{ + using namespace std; + + std::vector<int> v; + for (int i = 0; i != 1024; ++i) + v.push_back(i); + + std::deque<int> dest(v.size() - 10, 0); + + std::copy_backward(v.begin() + 5, v.end() - 5, dest.end()); + VERIFY( std::equal(v.begin() + 5, v.end() - 5, dest.begin()) ); +} + +void test05() +{ + using namespace std; + + std::list<int> l; + for (int i = 0; i != 1024; ++i) + l.push_back(i); + + std::deque<int> dest(l.size(), 0); + + std::copy_backward(l.begin(), l.end(), dest.end()); + VERIFY( std::equal(dest.begin(), dest.end(), l.begin()) ); +} + +int main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/1.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/1.cc new file mode 100644 index 00000000000..b99cf1df538 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/1.cc @@ -0,0 +1,122 @@ +// Copyright (C) 2019 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 <algorithm> +#include <vector> +#include <deque> + +#include <ext/new_allocator.h> +#include <ext/malloc_allocator.h> + +#include <testsuite_hooks.h> + +void test01() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) + d.push_back(i); + + const deque<int>& cd = d; + + VERIFY( equal(cd.begin(), cd.end(), cd.begin()) ); + VERIFY( equal(cd.begin(), cd.end(), d.begin()) ); + VERIFY( equal(d.begin(), d.end(), d.begin()) ); + VERIFY( equal(d.begin(), d.end(), cd.begin()) ); +} + +void test02() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i % 10); + + VERIFY( equal(d.begin(), d.begin() + 10, d.begin() + 20) ); + VERIFY( equal(d.begin() + 10, d.end() - 10, d.begin()) ); + + const deque<int>& cd = d; + + VERIFY( equal(cd.begin(), cd.begin() + 10, cd.begin() + 20) ); + VERIFY( equal(cd.begin() + 10, cd.end() - 10, d.begin()) ); + VERIFY( equal(d.begin() + 10, d.end() - 10, cd.begin()) ); +} + +void test03() +{ + using namespace std; + + deque<int> d1; + for (int i = 0; i != 1024; ++i) + d1.push_back(i % 10); + + deque<int> d2(d1); + for (int i = 0; i != 10; ++i) + d2.pop_front(); + + VERIFY( equal(d1.begin(), d1.begin() + 10, d2.begin()) ); + VERIFY( equal(d1.begin() + 10, d1.end() - 10, d2.begin()) ); + + const deque<int>& cd1 = d1; + const deque<int>& cd2 = d2; + + VERIFY( equal(cd1.begin(), cd1.begin() + 10, cd2.begin() + 20) ); + VERIFY( equal(cd1.begin() + 10, cd1.end() - 10, d2.begin()) ); + VERIFY( equal(cd2.begin() + 10, cd2.end() - 10, cd1.begin()) ); +} + +void test04() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + vector<int> v(d.begin(), d.end()); + + VERIFY( equal(d.begin(), d.end(), v.begin()) ); + VERIFY( equal(v.begin(), v.end(), d.begin()) ); + + const deque<int>& cd = d; + + VERIFY( equal(cd.begin(), cd.end(), v.begin()) ); + VERIFY( equal(v.begin(), v.end(), cd.begin()) ); +} + +void test05() +{ + using namespace std; + + int a[] { 0, 1, 2, 3, 4 }; + deque<int, __gnu_cxx::new_allocator<int> > d1(a, a + 5); + deque<int, __gnu_cxx::malloc_allocator<int> > d2(a, a + 5); + + VERIFY( equal(d1.begin(), d1.end(), d2.begin()) ); +} + +int main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/fill/deque_iterators/1.cc b/libstdc++-v3/testsuite/25_algorithms/fill/deque_iterators/1.cc new file mode 100644 index 00000000000..604ccb67fcd --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/fill/deque_iterators/1.cc @@ -0,0 +1,58 @@ +// Copyright (C) 2019 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 <algorithm> +#include <deque> + +#include <testsuite_hooks.h> + +void test01() +{ + using namespace std; + + deque<char> d1; + for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(char)); ++i) + d1.push_back((char)i); + + deque<char> d2(d1.size(), '\0'); + + fill(d1.begin(), d1.end(), '\0'); + + VERIFY( equal(d1.begin(), d1.end(), d2.begin()) ); +} + +void test02() +{ + using namespace std; + + deque<char> d1; + for (int i = 0; i != 4 * _GLIBCXX_STD_C::__deque_buf_size(sizeof(char)); ++i) + d1.push_back(i); + + deque<char> d2(d1.size(), '\0'); + + fill(d1.begin(), d1.end(), '\0'); + + VERIFY( equal(d1.begin(), d1.end(), d2.begin()) ); +} + +int main() +{ + test01(); + test02(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/2.cc b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/2.cc new file mode 100644 index 00000000000..1f7930036d1 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/2.cc @@ -0,0 +1,101 @@ +// { dg-do run { target c++11 } } +// Copyright (C) 2019 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 <algorithm> +#include <vector> +#include <list> +#include <deque> + +#include <testsuite_hooks.h> + +void test01() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) + d.push_back(i); + + deque<int> dest(d.size(), 0); + + move(d.begin(), d.end(), dest.begin()); + + VERIFY( equal(dest.begin(), dest.end(), d.begin()) ); +} + +void test02() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != 4 * _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) + d.push_back(i); + + deque<int> dest(d.size(), 0); + + const deque<int>& cd = d; + move(cd.begin(), cd.end(), dest.begin()); + + VERIFY( equal(dest.begin(), dest.end(), cd.begin()) ); +} + +void test03() +{ + std::deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + std::vector<int> dest(d.size(), 0); + + std::move(d.begin(), d.end(), dest.begin()); + VERIFY( std::equal(dest.begin(), dest.end(), d.begin()) ); +} + +void test04() +{ + std::vector<int> v; + for (int i = 0; i != 1024; ++i) + v.push_back(i); + + std::deque<int> dest(v.size() - 10, 0); + + std::move(v.begin() + 5, v.end() - 5, dest.begin()); + VERIFY( std::equal(dest.begin(), dest.end(), v.begin() + 5) ); +} + +void test05() +{ + std::list<int> l; + for (int i = 0; i != 1024; ++i) + l.push_back(i); + + std::deque<int> dest(l.size(), 0); + + std::move(l.begin(), l.end(), dest.begin()); + VERIFY( std::equal(dest.begin(), dest.end(), l.begin()) ); +} + +int main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/2.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/2.cc new file mode 100644 index 00000000000..82fff3e20c8 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/2.cc @@ -0,0 +1,101 @@ +// { dg-do run { target c++11 } } +// Copyright (C) 2019 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 <algorithm> +#include <vector> +#include <list> +#include <deque> + +#include <testsuite_hooks.h> + +void test01() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) + d.push_back(i); + + deque<int> dest(d.size(), 0); + + move_backward(d.begin(), d.end(), dest.end()); + + VERIFY( equal(dest.begin(), dest.end(), d.begin()) ); +} + +void test02() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != 4 * _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) + d.push_back(i); + + deque<int> dest(d.size(), 0); + + const deque<int>& cd = d; + move_backward(cd.begin(), cd.end(), dest.end()); + + VERIFY( equal(dest.begin(), dest.end(), cd.begin()) ); +} + +void test03() +{ + std::deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + std::vector<int> dest(d.size(), 0); + + std::move_backward(d.begin(), d.end(), dest.end()); + VERIFY( std::equal(dest.begin(), dest.end(), d.begin()) ); +} + +void test04() +{ + std::vector<int> v; + for (int i = 0; i != 1024; ++i) + v.push_back(i); + + std::deque<int> dest(v.size() - 10, 0); + + std::move_backward(v.begin() + 5, v.end() - 5, dest.end()); + VERIFY( std::equal(dest.begin(), dest.end(), v.begin() + 5) ); +} + +void test05() +{ + std::list<int> l; + for (int i = 0; i != 1024; ++i) + l.push_back(i); + + std::deque<int> dest(l.size(), 0); + + std::move_backward(l.begin(), l.end(), dest.end()); + VERIFY( std::equal(dest.begin(), dest.end(), l.begin()) ); +} + +int main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); + return 0; +} diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/copy_backward_deque_iterators.cc b/libstdc++-v3/testsuite/performance/25_algorithms/copy_backward_deque_iterators.cc index 461dfc044ad..716907c1a96 100644 --- a/libstdc++-v3/testsuite/performance/25_algorithms/copy_backward_deque_iterators.cc +++ b/libstdc++-v3/testsuite/performance/25_algorithms/copy_backward_deque_iterators.cc @@ -16,6 +16,9 @@ // <http://www.gnu.org/licenses/>. #include <deque> +#include <vector> +#include <list> + #include <testsuite_performance.h> int main() @@ -34,7 +37,71 @@ int main() for (int j = 0; j < 3000; ++j) std::copy_backward(data.begin(), data.begin() + j, d.end()); stop_counters(time, resource); - report_performance(__FILE__, "", time, resource); + report_performance(__FILE__, "deque 2 deque", time, resource); + clear_counters(time, resource); + + std::vector<int> v(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::copy_backward(data.begin(), data.begin() + j, v.end()); + stop_counters(time, resource); + report_performance(__FILE__, "deque 2 vector", time, resource); + clear_counters(time, resource); + + d.assign(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::copy_backward(v.begin(), v.begin() + j, d.end()); + stop_counters(time, resource); + report_performance(__FILE__, "vector 2 deque", time, resource); + clear_counters(time, resource); + + std::vector<char> cv(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::copy_backward(data.begin(), data.begin() + j, cv.end()); + stop_counters(time, resource); + report_performance(__FILE__, "int deque 2 char vector", time, resource); + clear_counters(time, resource); + + d.assign(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::copy_backward(cv.begin(), cv.begin() + j, d.end()); + stop_counters(time, resource); + report_performance(__FILE__, "char vector 2 int deque", time, resource); + clear_counters(time, resource); + + std::list<int> l(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::copy_backward(data.begin(), data.begin() + j, l.end()); + stop_counters(time, resource); + report_performance(__FILE__, "deque 2 list", time, resource); + clear_counters(time, resource); + + d.assign(3000, 1); + + std::list<int>::iterator lit; + start_counters(time, resource); + for (int i = 0; i < 200; ++i) + { + lit = l.begin(); + for (int j = 0; j < 3000; ++j, ++lit) + std::copy_backward(l.begin(), lit, d.end()); + } + stop_counters(time, resource); + report_performance(__FILE__, "list 2 deque", time, resource); return 0; } diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/copy_deque_iterators.cc b/libstdc++-v3/testsuite/performance/25_algorithms/copy_deque_iterators.cc index 35d5d79dec9..0bb2c55a950 100644 --- a/libstdc++-v3/testsuite/performance/25_algorithms/copy_deque_iterators.cc +++ b/libstdc++-v3/testsuite/performance/25_algorithms/copy_deque_iterators.cc @@ -16,6 +16,9 @@ // <http://www.gnu.org/licenses/>. #include <deque> +#include <vector> +#include <list> + #include <testsuite_performance.h> int main() @@ -34,7 +37,71 @@ int main() for (int j = 0; j < 3000; ++j) std::copy(data.begin(), data.begin() + j, d.begin()); stop_counters(time, resource); - report_performance(__FILE__, "", time, resource); + report_performance(__FILE__, "deque 2 deque", time, resource); + clear_counters(time, resource); + + std::vector<int> v(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::copy(data.begin(), data.begin() + j, v.begin()); + stop_counters(time, resource); + report_performance(__FILE__, "deque 2 vector", time, resource); + clear_counters(time, resource); + + d.assign(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::copy(v.begin(), v.begin() + j, d.begin()); + stop_counters(time, resource); + report_performance(__FILE__, "vector 2 deque", time, resource); + clear_counters(time, resource); + + std::vector<char> cv(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::copy(data.begin(), data.begin() + j, cv.begin()); + stop_counters(time, resource); + report_performance(__FILE__, "int deque 2 char vector", time, resource); + clear_counters(time, resource); + + d.assign(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::copy(cv.begin(), cv.begin() + j, d.begin()); + stop_counters(time, resource); + report_performance(__FILE__, "char vector 2 int deque", time, resource); + clear_counters(time, resource); + + std::list<int> l(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::copy(data.begin(), data.begin() + j, l.begin()); + stop_counters(time, resource); + report_performance(__FILE__, "deque 2 list", time, resource); + clear_counters(time, resource); + + d.assign(3000, 1); + + std::list<int>::iterator lit; + start_counters(time, resource); + for (int i = 0; i < 200; ++i) + { + lit = l.begin(); + for (int j = 0; j < 3000; ++j, ++lit) + std::copy(l.begin(), lit, d.begin()); + } + stop_counters(time, resource); + report_performance(__FILE__, "list 2 deque", time, resource); return 0; } diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/equal_deque_iterators.cc b/libstdc++-v3/testsuite/performance/25_algorithms/equal_deque_iterators.cc new file mode 100644 index 00000000000..66c4601c5f6 --- /dev/null +++ b/libstdc++-v3/testsuite/performance/25_algorithms/equal_deque_iterators.cc @@ -0,0 +1,82 @@ +// Copyright (C) 2019 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 <deque> +#include <vector> + +#include <testsuite_performance.h> + +int main() +{ + using namespace __gnu_test; + + time_counter time; + resource_counter resource; + + const std::deque<int> data(3000, 1); + + std::deque<int> d(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::equal(data.begin(), data.begin() + j, d.begin()); + stop_counters(time, resource); + report_performance(__FILE__, "deque vs deque", time, resource); + clear_counters(time, resource); + + std::vector<int> v(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::equal(data.begin(), data.begin() + j, v.begin()); + stop_counters(time, resource); + report_performance(__FILE__, "deque vs vector", time, resource); + clear_counters(time, resource); + + d.assign(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::equal(v.begin(), v.begin() + j, d.begin()); + stop_counters(time, resource); + report_performance(__FILE__, "vector vs deque", time, resource); + clear_counters(time, resource); + + std::vector<char> cv(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::equal(data.begin(), data.begin() + j, cv.begin()); + stop_counters(time, resource); + report_performance(__FILE__, "int deque vs char vector", time, resource); + clear_counters(time, resource); + + d.assign(3000, 1); + + start_counters(time, resource); + for (int i = 0; i < 1000; ++i) + for (int j = 0; j < 3000; ++j) + std::equal(cv.begin(), cv.begin() + j, d.begin()); + stop_counters(time, resource); + report_performance(__FILE__, "char vector vs int deque", time, resource); + + return 0; +} |