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-exception 7 // 8 //===----------------------------------------------------------------------===// 9 #ifndef _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H 10 #define _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H 11 12 #include <__config> 13 #include <__iterator/concepts.h> // indirectly_readable 14 #include <__iterator/iterator_traits.h> // iter_reference_t 15 #include <__memory/addressof.h> 16 #include <__utility/forward.h> 17 #include <concepts> // constructible_from 18 #include <optional> 19 #include <type_traits> 20 21 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 22 #pragma GCC system_header 23 #endif 24 25 _LIBCPP_BEGIN_NAMESPACE_STD 26 27 #if !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 28 29 namespace ranges { 30 // __non_propagating_cache is a helper type that allows storing an optional value in it, 31 // but which does not copy the source's value when it is copy constructed/assigned to, 32 // and which resets the source's value when it is moved-from. 33 // 34 // This type is used as an implementation detail of some views that need to cache the 35 // result of `begin()` in order to provide an amortized O(1) begin() method. Typically, 36 // we don't want to propagate the value of the cache upon copy because the cached iterator 37 // may refer to internal details of the source view. 38 template<class _Tp> 39 requires is_object_v<_Tp> 40 class _LIBCPP_TEMPLATE_VIS __non_propagating_cache { 41 struct __from_tag { }; 42 struct __forward_tag { }; 43 44 // This helper class is needed to perform copy and move elision when 45 // constructing the contained type from an iterator. 46 struct __wrapper { 47 template<class ..._Args> 48 constexpr explicit __wrapper(__forward_tag, _Args&& ...__args) : __t_(_VSTD::forward<_Args>(__args)...) { } 49 template<class _Fn> 50 constexpr explicit __wrapper(__from_tag, _Fn const& __f) : __t_(__f()) { } 51 _Tp __t_; 52 }; 53 54 optional<__wrapper> __value_ = nullopt; 55 56 public: 57 _LIBCPP_HIDE_FROM_ABI __non_propagating_cache() = default; 58 59 _LIBCPP_HIDE_FROM_ABI 60 constexpr __non_propagating_cache(__non_propagating_cache const&) noexcept 61 : __value_(nullopt) 62 { } 63 64 _LIBCPP_HIDE_FROM_ABI 65 constexpr __non_propagating_cache(__non_propagating_cache&& __other) noexcept 66 : __value_(nullopt) 67 { 68 __other.__value_.reset(); 69 } 70 71 _LIBCPP_HIDE_FROM_ABI 72 constexpr __non_propagating_cache& operator=(__non_propagating_cache const& __other) noexcept { 73 if (this != _VSTD::addressof(__other)) { 74 __value_.reset(); 75 } 76 return *this; 77 } 78 79 _LIBCPP_HIDE_FROM_ABI 80 constexpr __non_propagating_cache& operator=(__non_propagating_cache&& __other) noexcept { 81 __value_.reset(); 82 __other.__value_.reset(); 83 return *this; 84 } 85 86 _LIBCPP_HIDE_FROM_ABI 87 constexpr _Tp& operator*() { return __value_->__t_; } 88 _LIBCPP_HIDE_FROM_ABI 89 constexpr _Tp const& operator*() const { return __value_->__t_; } 90 91 _LIBCPP_HIDE_FROM_ABI 92 constexpr bool __has_value() const { return __value_.has_value(); } 93 94 template<class _Fn> 95 _LIBCPP_HIDE_FROM_ABI 96 constexpr _Tp& __emplace_from(_Fn const& __f) { 97 return __value_.emplace(__from_tag{}, __f).__t_; 98 } 99 100 template<class ..._Args> 101 _LIBCPP_HIDE_FROM_ABI 102 constexpr _Tp& __emplace(_Args&& ...__args) { 103 return __value_.emplace(__forward_tag{}, _VSTD::forward<_Args>(__args)...).__t_; 104 } 105 }; 106 107 struct __empty_cache { }; 108 } // namespace ranges 109 110 #endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 111 112 _LIBCPP_END_NAMESPACE_STD 113 114 #endif // _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H 115