311 lines · c
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03___MEMORY_UNINITIALIZED_ALGORITHMS_H11#define _LIBCPP___CXX03___MEMORY_UNINITIALIZED_ALGORITHMS_H12 13#include <__cxx03/__algorithm/copy.h>14#include <__cxx03/__algorithm/move.h>15#include <__cxx03/__algorithm/unwrap_iter.h>16#include <__cxx03/__algorithm/unwrap_range.h>17#include <__cxx03/__config>18#include <__cxx03/__iterator/iterator_traits.h>19#include <__cxx03/__iterator/reverse_iterator.h>20#include <__cxx03/__memory/addressof.h>21#include <__cxx03/__memory/allocator_traits.h>22#include <__cxx03/__memory/construct_at.h>23#include <__cxx03/__memory/pointer_traits.h>24#include <__cxx03/__memory/voidify.h>25#include <__cxx03/__type_traits/extent.h>26#include <__cxx03/__type_traits/is_array.h>27#include <__cxx03/__type_traits/is_constant_evaluated.h>28#include <__cxx03/__type_traits/is_trivially_assignable.h>29#include <__cxx03/__type_traits/is_trivially_constructible.h>30#include <__cxx03/__type_traits/is_trivially_relocatable.h>31#include <__cxx03/__type_traits/is_unbounded_array.h>32#include <__cxx03/__type_traits/negation.h>33#include <__cxx03/__type_traits/remove_const.h>34#include <__cxx03/__type_traits/remove_extent.h>35#include <__cxx03/__utility/exception_guard.h>36#include <__cxx03/__utility/move.h>37#include <__cxx03/__utility/pair.h>38#include <__cxx03/new>39 40#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)41# pragma GCC system_header42#endif43 44_LIBCPP_PUSH_MACROS45#include <__cxx03/__undef_macros>46 47_LIBCPP_BEGIN_NAMESPACE_STD48 49struct __always_false {50 template <class... _Args>51 _LIBCPP_HIDE_FROM_ABI bool operator()(_Args&&...) const _NOEXCEPT {52 return false;53 }54};55 56// uninitialized_copy57 58template <class _ValueType, class _InputIterator, class _Sentinel1, class _ForwardIterator, class _EndPredicate>59inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> __uninitialized_copy(60 _InputIterator __ifirst, _Sentinel1 __ilast, _ForwardIterator __ofirst, _EndPredicate __stop_copying) {61 _ForwardIterator __idx = __ofirst;62#ifndef _LIBCPP_HAS_NO_EXCEPTIONS63 try {64#endif65 for (; __ifirst != __ilast && !__stop_copying(__idx); ++__ifirst, (void)++__idx)66 ::new (std::__voidify(*__idx)) _ValueType(*__ifirst);67#ifndef _LIBCPP_HAS_NO_EXCEPTIONS68 } catch (...) {69 std::__destroy(__ofirst, __idx);70 throw;71 }72#endif73 74 return pair<_InputIterator, _ForwardIterator>(std::move(__ifirst), std::move(__idx));75}76 77template <class _InputIterator, class _ForwardIterator>78_LIBCPP_HIDE_FROM_ABI _ForwardIterator79uninitialized_copy(_InputIterator __ifirst, _InputIterator __ilast, _ForwardIterator __ofirst) {80 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;81 auto __result = std::__uninitialized_copy<_ValueType>(82 std::move(__ifirst), std::move(__ilast), std::move(__ofirst), __always_false());83 return std::move(__result.second);84}85 86// uninitialized_copy_n87 88template <class _ValueType, class _InputIterator, class _Size, class _ForwardIterator, class _EndPredicate>89inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator>90__uninitialized_copy_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst, _EndPredicate __stop_copying) {91 _ForwardIterator __idx = __ofirst;92#ifndef _LIBCPP_HAS_NO_EXCEPTIONS93 try {94#endif95 for (; __n > 0 && !__stop_copying(__idx); ++__ifirst, (void)++__idx, (void)--__n)96 ::new (std::__voidify(*__idx)) _ValueType(*__ifirst);97#ifndef _LIBCPP_HAS_NO_EXCEPTIONS98 } catch (...) {99 std::__destroy(__ofirst, __idx);100 throw;101 }102#endif103 104 return pair<_InputIterator, _ForwardIterator>(std::move(__ifirst), std::move(__idx));105}106 107template <class _InputIterator, class _Size, class _ForwardIterator>108inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator109uninitialized_copy_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst) {110 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;111 auto __result =112 std::__uninitialized_copy_n<_ValueType>(std::move(__ifirst), __n, std::move(__ofirst), __always_false());113 return std::move(__result.second);114}115 116// uninitialized_fill117 118template <class _ValueType, class _ForwardIterator, class _Sentinel, class _Tp>119inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator120__uninitialized_fill(_ForwardIterator __first, _Sentinel __last, const _Tp& __x) {121 _ForwardIterator __idx = __first;122#ifndef _LIBCPP_HAS_NO_EXCEPTIONS123 try {124#endif125 for (; __idx != __last; ++__idx)126 ::new (std::__voidify(*__idx)) _ValueType(__x);127#ifndef _LIBCPP_HAS_NO_EXCEPTIONS128 } catch (...) {129 std::__destroy(__first, __idx);130 throw;131 }132#endif133 134 return __idx;135}136 137template <class _ForwardIterator, class _Tp>138inline _LIBCPP_HIDE_FROM_ABI void139uninitialized_fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __x) {140 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;141 (void)std::__uninitialized_fill<_ValueType>(__first, __last, __x);142}143 144// uninitialized_fill_n145 146template <class _ValueType, class _ForwardIterator, class _Size, class _Tp>147inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator148__uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) {149 _ForwardIterator __idx = __first;150#ifndef _LIBCPP_HAS_NO_EXCEPTIONS151 try {152#endif153 for (; __n > 0; ++__idx, (void)--__n)154 ::new (std::__voidify(*__idx)) _ValueType(__x);155#ifndef _LIBCPP_HAS_NO_EXCEPTIONS156 } catch (...) {157 std::__destroy(__first, __idx);158 throw;159 }160#endif161 162 return __idx;163}164 165template <class _ForwardIterator, class _Size, class _Tp>166inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator167uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) {168 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;169 return std::__uninitialized_fill_n<_ValueType>(__first, __n, __x);170}171 172// Destroy all elements in [__first, __last) from left to right using allocator destruction.173template <class _Alloc, class _Iter, class _Sent>174_LIBCPP_HIDE_FROM_ABI void __allocator_destroy(_Alloc& __alloc, _Iter __first, _Sent __last) {175 for (; __first != __last; ++__first)176 allocator_traits<_Alloc>::destroy(__alloc, std::__to_address(__first));177}178 179template <class _Alloc, class _Iter>180class _AllocatorDestroyRangeReverse {181public:182 _LIBCPP_HIDE_FROM_ABI _AllocatorDestroyRangeReverse(_Alloc& __alloc, _Iter& __first, _Iter& __last)183 : __alloc_(__alloc), __first_(__first), __last_(__last) {}184 185 _LIBCPP_HIDE_FROM_ABI void operator()() const {186 std::__allocator_destroy(__alloc_, std::reverse_iterator<_Iter>(__last_), std::reverse_iterator<_Iter>(__first_));187 }188 189private:190 _Alloc& __alloc_;191 _Iter& __first_;192 _Iter& __last_;193};194 195// Copy-construct [__first1, __last1) in [__first2, __first2 + N), where N is distance(__first1, __last1).196//197// The caller has to ensure that __first2 can hold at least N uninitialized elements. If an exception is thrown the198// already copied elements are destroyed in reverse order of their construction.199template <class _Alloc, class _Iter1, class _Sent1, class _Iter2>200_LIBCPP_HIDE_FROM_ABI _Iter2201__uninitialized_allocator_copy_impl(_Alloc& __alloc, _Iter1 __first1, _Sent1 __last1, _Iter2 __first2) {202 auto __destruct_first = __first2;203 auto __guard =204 std::__make_exception_guard(_AllocatorDestroyRangeReverse<_Alloc, _Iter2>(__alloc, __destruct_first, __first2));205 while (__first1 != __last1) {206 allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__first2), *__first1);207 ++__first1;208 ++__first2;209 }210 __guard.__complete();211 return __first2;212}213 214template <class _Alloc, class _Type>215struct __allocator_has_trivial_copy_construct : _Not<__has_construct<_Alloc, _Type*, const _Type&> > {};216 217template <class _Type>218struct __allocator_has_trivial_copy_construct<allocator<_Type>, _Type> : true_type {};219 220template <class _Alloc,221 class _In,222 class _RawTypeIn = __remove_const_t<_In>,223 class _Out,224 __enable_if_t<225 // using _RawTypeIn because of the allocator<T const> extension226 is_trivially_copy_constructible<_RawTypeIn>::value && is_trivially_copy_assignable<_RawTypeIn>::value &&227 is_same<__remove_const_t<_In>, __remove_const_t<_Out> >::value &&228 __allocator_has_trivial_copy_construct<_Alloc, _RawTypeIn>::value,229 int> = 0>230_LIBCPP_HIDE_FROM_ABI _Out* __uninitialized_allocator_copy_impl(_Alloc&, _In* __first1, _In* __last1, _Out* __first2) {231 // TODO: Remove the const_cast once we drop support for std::allocator<T const>232 if (__libcpp_is_constant_evaluated()) {233 while (__first1 != __last1) {234 std::__construct_at(std::__to_address(__first2), *__first1);235 ++__first1;236 ++__first2;237 }238 return __first2;239 } else {240 return std::copy(__first1, __last1, const_cast<_RawTypeIn*>(__first2));241 }242}243 244template <class _Alloc, class _Iter1, class _Sent1, class _Iter2>245_LIBCPP_HIDE_FROM_ABI _Iter2246__uninitialized_allocator_copy(_Alloc& __alloc, _Iter1 __first1, _Sent1 __last1, _Iter2 __first2) {247 auto __unwrapped_range = std::__unwrap_range(__first1, __last1);248 auto __result = std::__uninitialized_allocator_copy_impl(249 __alloc, __unwrapped_range.first, __unwrapped_range.second, std::__unwrap_iter(__first2));250 return std::__rewrap_iter(__first2, __result);251}252 253template <class _Alloc, class _Type>254struct __allocator_has_trivial_move_construct : _Not<__has_construct<_Alloc, _Type*, _Type&&> > {};255 256template <class _Type>257struct __allocator_has_trivial_move_construct<allocator<_Type>, _Type> : true_type {};258 259template <class _Alloc, class _Tp>260struct __allocator_has_trivial_destroy : _Not<__has_destroy<_Alloc, _Tp*> > {};261 262template <class _Tp, class _Up>263struct __allocator_has_trivial_destroy<allocator<_Tp>, _Up> : true_type {};264 265// __uninitialized_allocator_relocate relocates the objects in [__first, __last) into __result.266// Relocation means that the objects in [__first, __last) are placed into __result as-if by move-construct and destroy,267// except that the move constructor and destructor may never be called if they are known to be equivalent to a memcpy.268//269// Preconditions: __result doesn't contain any objects and [__first, __last) contains objects270// Postconditions: __result contains the objects from [__first, __last) and271// [__first, __last) doesn't contain any objects272//273// The strong exception guarantee is provided if any of the following are true:274// - is_nothrow_move_constructible<_Tp>275// - is_copy_constructible<_Tp>276// - __libcpp_is_trivially_relocatable<_Tp>277template <class _Alloc, class _Tp>278_LIBCPP_HIDE_FROM_ABI void279__uninitialized_allocator_relocate(_Alloc& __alloc, _Tp* __first, _Tp* __last, _Tp* __result) {280 static_assert(__is_cpp17_move_insertable<_Alloc>::value,281 "The specified type does not meet the requirements of Cpp17MoveInsertable");282 if (__libcpp_is_constant_evaluated() || !__libcpp_is_trivially_relocatable<_Tp>::value ||283 !__allocator_has_trivial_move_construct<_Alloc, _Tp>::value ||284 !__allocator_has_trivial_destroy<_Alloc, _Tp>::value) {285 auto __destruct_first = __result;286 auto __guard =287 std::__make_exception_guard(_AllocatorDestroyRangeReverse<_Alloc, _Tp*>(__alloc, __destruct_first, __result));288 auto __iter = __first;289 while (__iter != __last) {290#ifndef _LIBCPP_HAS_NO_EXCEPTIONS291 allocator_traits<_Alloc>::construct(__alloc, __result, std::move_if_noexcept(*__iter));292#else293 allocator_traits<_Alloc>::construct(__alloc, __result, std::move(*__iter));294#endif295 ++__iter;296 ++__result;297 }298 __guard.__complete();299 std::__allocator_destroy(__alloc, __first, __last);300 } else {301 // Casting to void* to suppress clang complaining that this is technically UB.302 __builtin_memcpy(static_cast<void*>(__result), __first, sizeof(_Tp) * (__last - __first));303 }304}305 306_LIBCPP_END_NAMESPACE_STD307 308_LIBCPP_POP_MACROS309 310#endif // _LIBCPP___CXX03___MEMORY_UNINITIALIZED_ALGORITHMS_H311