134 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_MOVE_BACKWARD_H10#define _LIBCPP___CXX03___ALGORITHM_MOVE_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 _BidirectionalIterator1, class _Sentinel, class _BidirectionalIterator2>32_LIBCPP_HIDE_FROM_ABI pair<_BidirectionalIterator1, _BidirectionalIterator2>33__move_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result);34 35template <class _AlgPolicy>36struct __move_backward_impl {37 template <class _InIter, class _Sent, class _OutIter>38 _LIBCPP_HIDE_FROM_ABI pair<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const {39 auto __last_iter = _IterOps<_AlgPolicy>::next(__first, __last);40 auto __original_last_iter = __last_iter;41 42 while (__first != __last_iter) {43 *--__result = _IterOps<_AlgPolicy>::__iter_move(--__last_iter);44 }45 46 return std::make_pair(std::move(__original_last_iter), std::move(__result));47 }48 49 template <class _InIter, class _OutIter, __enable_if_t<__is_segmented_iterator<_InIter>::value, int> = 0>50 _LIBCPP_HIDE_FROM_ABI pair<_InIter, _OutIter> operator()(_InIter __first, _InIter __last, _OutIter __result) const {51 using _Traits = __segmented_iterator_traits<_InIter>;52 auto __sfirst = _Traits::__segment(__first);53 auto __slast = _Traits::__segment(__last);54 if (__sfirst == __slast) {55 auto __iters =56 std::__move_backward<_AlgPolicy>(_Traits::__local(__first), _Traits::__local(__last), std::move(__result));57 return std::make_pair(__last, __iters.second);58 }59 60 __result =61 std::__move_backward<_AlgPolicy>(_Traits::__begin(__slast), _Traits::__local(__last), std::move(__result))62 .second;63 --__slast;64 while (__sfirst != __slast) {65 __result =66 std::__move_backward<_AlgPolicy>(_Traits::__begin(__slast), _Traits::__end(__slast), std::move(__result))67 .second;68 --__slast;69 }70 __result = std::__move_backward<_AlgPolicy>(_Traits::__local(__first), _Traits::__end(__slast), std::move(__result))71 .second;72 return std::make_pair(__last, std::move(__result));73 }74 75 template <class _InIter,76 class _OutIter,77 __enable_if_t<__has_random_access_iterator_category<_InIter>::value &&78 !__is_segmented_iterator<_InIter>::value && __is_segmented_iterator<_OutIter>::value,79 int> = 0>80 _LIBCPP_HIDE_FROM_ABI pair<_InIter, _OutIter> operator()(_InIter __first, _InIter __last, _OutIter __result) const {81 using _Traits = __segmented_iterator_traits<_OutIter>;82 using _DiffT = typename common_type<__iter_diff_t<_InIter>, __iter_diff_t<_OutIter> >::type;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 __orig_last = __last;89 90 auto __local_last = _Traits::__local(__result);91 auto __segment_iterator = _Traits::__segment(__result);92 while (true) {93 auto __local_first = _Traits::__begin(__segment_iterator);94 auto __size = std::min<_DiffT>(__local_last - __local_first, __last - __first);95 auto __iter = std::__move_backward<_AlgPolicy>(__last - __size, __last, __local_last).second;96 __last -= __size;97 98 if (__first == __last)99 return std::make_pair(std::move(__orig_last), _Traits::__compose(__segment_iterator, std::move(__iter)));100 101 __local_last = _Traits::__end(--__segment_iterator);102 }103 }104 105 // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.106 template <class _In, class _Out, __enable_if_t<__can_lower_move_assignment_to_memmove<_In, _Out>::value, int> = 0>107 _LIBCPP_HIDE_FROM_ABI pair<_In*, _Out*> operator()(_In* __first, _In* __last, _Out* __result) const {108 return std::__copy_backward_trivial_impl(__first, __last, __result);109 }110};111 112template <class _AlgPolicy, class _BidirectionalIterator1, class _Sentinel, class _BidirectionalIterator2>113_LIBCPP_HIDE_FROM_ABI pair<_BidirectionalIterator1, _BidirectionalIterator2>114__move_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result) {115 static_assert(std::is_copy_constructible<_BidirectionalIterator1>::value &&116 std::is_copy_constructible<_BidirectionalIterator1>::value,117 "Iterators must be copy constructible.");118 119 return std::__copy_move_unwrap_iters<__move_backward_impl<_AlgPolicy> >(120 std::move(__first), std::move(__last), std::move(__result));121}122 123template <class _BidirectionalIterator1, class _BidirectionalIterator2>124inline _LIBCPP_HIDE_FROM_ABI _BidirectionalIterator2125move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) {126 return std::__move_backward<_ClassicAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)).second;127}128 129_LIBCPP_END_NAMESPACE_STD130 131_LIBCPP_POP_MACROS132 133#endif // _LIBCPP___CXX03___ALGORITHM_MOVE_BACKWARD_H134