diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -1,4 +1,6 @@ set(files + __algorithm/copy.h + __algorithm/unwrap_iter.h __availability __bit_reference __bits diff --git a/libcxx/include/__algorithm/copy.h b/libcxx/include/__algorithm/copy.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/copy.h @@ -0,0 +1,89 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_COPY_H +#define _LIBCPP___ALGORITHM_COPY_H + +#include <__config> +#include <__algorithm/unwrap_iter.h> +#include +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace __copy_impl { + template + _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 + std::pair<_InputIterator, _OutputIterator> + __copy_constexpr(_InputIterator __first, _Sentinel __last, _OutputIterator __result) + { + for (; __first != __last; ++__first, (void) ++__result) + *__result = *__first; + return {__first, __result}; + } + + template + _LIBCPP_INLINE_VISIBILITY + std::pair<_InputIterator, _OutputIterator> + __copy_runtime(_InputIterator __first, _Sentinel __last, _OutputIterator __result) + { + return __copy_impl::__copy_constexpr(__first, __last, __result); + } + + template ::type, _Up>::value && + is_trivially_copy_assignable<_Up>::value + > > + _LIBCPP_INLINE_VISIBILITY + std::pair<_Tp*, _Up*> + __copy_runtime(_Tp* __first, _Tp* __last, _Up* __result) + { + const size_t __n = static_cast(__last - __first); + if (__n > 0) + _VSTD::memmove(__result, __first, __n * sizeof(_Up)); + return {__first + __n, __result + __n}; + } +} // end namespace __copy_impl + +template +_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +std::pair<_InputIterator, _OutputIterator> +__copy(_InputIterator __first, _Sentinel __last, _OutputIterator __result) +{ + if (__libcpp_is_constant_evaluated()) { + return __copy_impl::__copy_constexpr(__first, __last, __result); + } else { + return _VSTD::__rewrap_iters(std::make_pair(__first, __result), + __copy_impl::__copy_runtime(_VSTD::__unwrap_iter(__first), + _VSTD::__unwrap_iter(__last), + _VSTD::__unwrap_iter(__result))); + } +} + +template +_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_OutputIterator +copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) +{ + return _VSTD::__copy(_VSTD::move(__first), _VSTD::move(__last), _VSTD::move(__result)).second; +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_COPY_H diff --git a/libcxx/include/__algorithm/unwrap_iter.h b/libcxx/include/__algorithm/unwrap_iter.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/unwrap_iter.h @@ -0,0 +1,99 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_UNWRAP_ITER_H +#define _LIBCPP___ALGORITHM_UNWRAP_ITER_H + +#include <__config> +#include <__iterator/iterator_traits.h> // __is_cpp17_contiguous_iterator +#include <__memory/pointer_traits.h> // __to_address +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +// __unwrap_iter, __rewrap_iter + +// The job of __unwrap_iter is to lower contiguous iterators (such as +// vector::iterator) into pointers, to reduce the number of template +// instantiations and to enable pointer-based optimizations e.g. in std::copy. +// For iterators that are not contiguous, it must be a no-op. +// In debug mode, we don't do this. +// +// __unwrap_iter is non-constexpr for user-defined iterators whose +// `to_address` and/or `operator->` is non-constexpr. This is okay; but we +// try to avoid doing __unwrap_iter in constant-evaluated contexts anyway. +// +// Some algorithms (e.g. std::copy, but not std::sort) need to convert an +// "unwrapped" result back into a contiguous iterator. Since contiguous iterators +// are random-access, we can do this portably using iterator arithmetic; this +// is the job of __rewrap_iter. + +template ::value> +struct __unwrap_iter_impl { + static _LIBCPP_CONSTEXPR _Iter + __apply(_Iter __i) _NOEXCEPT { + return __i; + } +}; + +#if _LIBCPP_DEBUG_LEVEL < 2 + +template +struct __unwrap_iter_impl<_Iter, true> { + static _LIBCPP_CONSTEXPR decltype(_VSTD::__to_address(declval<_Iter>())) + __apply(_Iter __i) _NOEXCEPT { + return _VSTD::__to_address(__i); + } +}; + +#endif // _LIBCPP_DEBUG_LEVEL < 2 + +template > +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +decltype(_Impl::__apply(_VSTD::declval<_Iter>())) +__unwrap_iter(_Iter __i) _NOEXCEPT +{ + return _Impl::__apply(__i); +} + +template +_OrigIter __rewrap_iter(_OrigIter, _OrigIter __result) +{ + return __result; +} + +template +_OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result) +{ + // Precondition: __result is reachable from __first + // Precondition: _OrigIter is a contiguous iterator + return __first + (__result - _VSTD::__unwrap_iter(__first)); +} + +template +std::pair<_OrigIter1, _OrigIter2> +__rewrap_iters(std::pair<_OrigIter1, _OrigIter2> __its, + std::pair<_UnwrappedIter1, _UnwrappedIter2> __results) +{ + return std::pair<_OrigIter1, _OrigIter2>(_VSTD::__rewrap_iter(__its.first, __results.first), + _VSTD::__rewrap_iter(__its.second, __results.second)); +} + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_UNWRAP_ITER_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -657,6 +657,9 @@ #include #include +#include <__algorithm/copy.h> +#include <__algorithm/unwrap_iter.h> + #include <__debug> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -1639,116 +1642,6 @@ __value_, __equal_to<__v, _Tp>()); } -// __unwrap_iter, __rewrap_iter - -// The job of __unwrap_iter is to lower contiguous iterators (such as -// vector::iterator) into pointers, to reduce the number of template -// instantiations and to enable pointer-based optimizations e.g. in std::copy. -// For iterators that are not contiguous, it must be a no-op. -// In debug mode, we don't do this. -// -// __unwrap_iter is non-constexpr for user-defined iterators whose -// `to_address` and/or `operator->` is non-constexpr. This is okay; but we -// try to avoid doing __unwrap_iter in constant-evaluated contexts anyway. -// -// Some algorithms (e.g. std::copy, but not std::sort) need to convert an -// "unwrapped" result back into a contiguous iterator. Since contiguous iterators -// are random-access, we can do this portably using iterator arithmetic; this -// is the job of __rewrap_iter. - -template ::value> -struct __unwrap_iter_impl { - static _LIBCPP_CONSTEXPR _Iter - __apply(_Iter __i) _NOEXCEPT { - return __i; - } -}; - -#if _LIBCPP_DEBUG_LEVEL < 2 - -template -struct __unwrap_iter_impl<_Iter, true> { - static _LIBCPP_CONSTEXPR decltype(_VSTD::__to_address(declval<_Iter>())) - __apply(_Iter __i) _NOEXCEPT { - return _VSTD::__to_address(__i); - } -}; - -#endif // _LIBCPP_DEBUG_LEVEL < 2 - -template > -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -decltype(_Impl::__apply(_VSTD::declval<_Iter>())) -__unwrap_iter(_Iter __i) _NOEXCEPT -{ - return _Impl::__apply(__i); -} - -template -_OrigIter __rewrap_iter(_OrigIter, _OrigIter __result) -{ - return __result; -} - -template -_OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result) -{ - // Precondition: __result is reachable from __first - // Precondition: _OrigIter is a contiguous iterator - return __first + (__result - _VSTD::__unwrap_iter(__first)); -} - -// copy - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -__copy_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - for (; __first != __last; ++__first, (void) ++__result) - *__result = *__first; - return __result; -} - -template -inline _LIBCPP_INLINE_VISIBILITY -_OutputIterator -__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - return _VSTD::__copy_constexpr(__first, __last, __result); -} - -template -inline _LIBCPP_INLINE_VISIBILITY -typename enable_if -< - is_same::type, _Up>::value && - is_trivially_copy_assignable<_Up>::value, - _Up* ->::type -__copy(_Tp* __first, _Tp* __last, _Up* __result) -{ - const size_t __n = static_cast(__last - __first); - if (__n > 0) - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); - return __result + __n; -} - -template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - if (__libcpp_is_constant_evaluated()) { - return _VSTD::__copy_constexpr(__first, __last, __result); - } else { - return _VSTD::__rewrap_iter(__result, - _VSTD::__copy(_VSTD::__unwrap_iter(__first), - _VSTD::__unwrap_iter(__last), - _VSTD::__unwrap_iter(__result))); - } -} - // copy_backward template