133 lines · c
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___CXX03___ALGORITHM_COPY_BACKWARD_H10#define _LIBCPP___CXX03___ALGORITHM_COPY_BACKWARD_H11 12#include <__cxx03/__algorithm/copy_move_common.h>13#include <__cxx03/__algorithm/iterator_operations.h>14#include <__cxx03/__algorithm/min.h>15#include <__cxx03/__config>16#include <__cxx03/__iterator/segmented_iterator.h>17#include <__cxx03/__type_traits/common_type.h>18#include <__cxx03/__type_traits/is_constructible.h>19#include <__cxx03/__utility/move.h>20#include <__cxx03/__utility/pair.h>21 22#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)23# pragma GCC system_header24#endif25 26_LIBCPP_PUSH_MACROS27#include <__cxx03/__undef_macros>28 29_LIBCPP_BEGIN_NAMESPACE_STD30 31template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>32_LIBCPP_HIDE_FROM_ABI pair<_InIter, _OutIter> __copy_backward(_InIter __first, _Sent __last, _OutIter __result);33 34template <class _AlgPolicy>35struct __copy_backward_impl {36 template <class _InIter, class _Sent, class _OutIter>37 _LIBCPP_HIDE_FROM_ABI pair<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const {38 auto __last_iter = _IterOps<_AlgPolicy>::next(__first, __last);39 auto __original_last_iter = __last_iter;40 41 while (__first != __last_iter) {42 *--__result = *--__last_iter;43 }44 45 return std::make_pair(std::move(__original_last_iter), std::move(__result));46 }47 48 template <class _InIter, class _OutIter, __enable_if_t<__is_segmented_iterator<_InIter>::value, int> = 0>49 _LIBCPP_HIDE_FROM_ABI pair<_InIter, _OutIter> operator()(_InIter __first, _InIter __last, _OutIter __result) const {50 using _Traits = __segmented_iterator_traits<_InIter>;51 auto __sfirst = _Traits::__segment(__first);52 auto __slast = _Traits::__segment(__last);53 if (__sfirst == __slast) {54 auto __iters =55 std::__copy_backward<_AlgPolicy>(_Traits::__local(__first), _Traits::__local(__last), std::move(__result));56 return std::make_pair(__last, __iters.second);57 }58 59 __result =60 std::__copy_backward<_AlgPolicy>(_Traits::__begin(__slast), _Traits::__local(__last), std::move(__result))61 .second;62 --__slast;63 while (__sfirst != __slast) {64 __result =65 std::__copy_backward<_AlgPolicy>(_Traits::__begin(__slast), _Traits::__end(__slast), std::move(__result))66 .second;67 --__slast;68 }69 __result = std::__copy_backward<_AlgPolicy>(_Traits::__local(__first), _Traits::__end(__slast), std::move(__result))70 .second;71 return std::make_pair(__last, std::move(__result));72 }73 74 template <class _InIter,75 class _OutIter,76 __enable_if_t<__has_random_access_iterator_category<_InIter>::value &&77 !__is_segmented_iterator<_InIter>::value && __is_segmented_iterator<_OutIter>::value,78 int> = 0>79 _LIBCPP_HIDE_FROM_ABI pair<_InIter, _OutIter> operator()(_InIter __first, _InIter __last, _OutIter __result) const {80 using _Traits = __segmented_iterator_traits<_OutIter>;81 auto __orig_last = __last;82 auto __segment_iterator = _Traits::__segment(__result);83 84 // When the range contains no elements, __result might not be a valid iterator85 if (__first == __last)86 return std::make_pair(__first, __result);87 88 auto __local_last = _Traits::__local(__result);89 while (true) {90 using _DiffT = typename common_type<__iter_diff_t<_InIter>, __iter_diff_t<_OutIter> >::type;91 92 auto __local_first = _Traits::__begin(__segment_iterator);93 auto __size = std::min<_DiffT>(__local_last - __local_first, __last - __first);94 auto __iter = std::__copy_backward<_AlgPolicy>(__last - __size, __last, __local_last).second;95 __last -= __size;96 97 if (__first == __last)98 return std::make_pair(std::move(__orig_last), _Traits::__compose(__segment_iterator, std::move(__iter)));99 --__segment_iterator;100 __local_last = _Traits::__end(__segment_iterator);101 }102 }103 104 // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.105 template <class _In, class _Out, __enable_if_t<__can_lower_copy_assignment_to_memmove<_In, _Out>::value, int> = 0>106 _LIBCPP_HIDE_FROM_ABI pair<_In*, _Out*> operator()(_In* __first, _In* __last, _Out* __result) const {107 return std::__copy_backward_trivial_impl(__first, __last, __result);108 }109};110 111template <class _AlgPolicy, class _BidirectionalIterator1, class _Sentinel, class _BidirectionalIterator2>112_LIBCPP_HIDE_FROM_ABI pair<_BidirectionalIterator1, _BidirectionalIterator2>113__copy_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result) {114 return std::__copy_move_unwrap_iters<__copy_backward_impl<_AlgPolicy> >(115 std::move(__first), std::move(__last), std::move(__result));116}117 118template <class _BidirectionalIterator1, class _BidirectionalIterator2>119inline _LIBCPP_HIDE_FROM_ABI _BidirectionalIterator2120copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) {121 static_assert(std::is_copy_constructible<_BidirectionalIterator1>::value &&122 std::is_copy_constructible<_BidirectionalIterator1>::value,123 "Iterators must be copy constructible.");124 125 return std::__copy_backward<_ClassicAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)).second;126}127 128_LIBCPP_END_NAMESPACE_STD129 130_LIBCPP_POP_MACROS131 132#endif // _LIBCPP___CXX03___ALGORITHM_COPY_BACKWARD_H133