1 // Copyright 2018 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef ABSL_CONTAINER_INTERNAL_COMMON_H_ 16 #define ABSL_CONTAINER_INTERNAL_COMMON_H_ 17 18 #include <cassert> 19 #include <type_traits> 20 21 #include "absl/meta/type_traits.h" 22 #include "absl/types/optional.h" 23 24 namespace absl { 25 ABSL_NAMESPACE_BEGIN 26 namespace container_internal { 27 28 template <class, class = void> 29 struct IsTransparent : std::false_type {}; 30 template <class T> 31 struct IsTransparent<T, absl::void_t<typename T::is_transparent>> 32 : std::true_type {}; 33 34 template <bool is_transparent> 35 struct KeyArg { 36 // Transparent. Forward `K`. 37 template <typename K, typename key_type> 38 using type = K; 39 }; 40 41 template <> 42 struct KeyArg<false> { 43 // Not transparent. Always use `key_type`. 44 template <typename K, typename key_type> 45 using type = key_type; 46 }; 47 48 // The node_handle concept from C++17. 49 // We specialize node_handle for sets and maps. node_handle_base holds the 50 // common API of both. 51 template <typename PolicyTraits, typename Alloc> 52 class node_handle_base { 53 protected: 54 using slot_type = typename PolicyTraits::slot_type; 55 56 public: 57 using allocator_type = Alloc; 58 59 constexpr node_handle_base() = default; 60 node_handle_base(node_handle_base&& other) noexcept { 61 *this = std::move(other); 62 } 63 ~node_handle_base() { destroy(); } 64 node_handle_base& operator=(node_handle_base&& other) noexcept { 65 destroy(); 66 if (!other.empty()) { 67 alloc_ = other.alloc_; 68 PolicyTraits::transfer(alloc(), slot(), other.slot()); 69 other.reset(); 70 } 71 return *this; 72 } 73 74 bool empty() const noexcept { return !alloc_; } 75 explicit operator bool() const noexcept { return !empty(); } 76 allocator_type get_allocator() const { return *alloc_; } 77 78 protected: 79 friend struct CommonAccess; 80 81 struct transfer_tag_t {}; 82 node_handle_base(transfer_tag_t, const allocator_type& a, slot_type* s) 83 : alloc_(a) { 84 PolicyTraits::transfer(alloc(), slot(), s); 85 } 86 87 struct construct_tag_t {}; 88 template <typename... Args> 89 node_handle_base(construct_tag_t, const allocator_type& a, Args&&... args) 90 : alloc_(a) { 91 PolicyTraits::construct(alloc(), slot(), std::forward<Args>(args)...); 92 } 93 94 void destroy() { 95 if (!empty()) { 96 PolicyTraits::destroy(alloc(), slot()); 97 reset(); 98 } 99 } 100 101 void reset() { 102 assert(alloc_.has_value()); 103 alloc_ = absl::nullopt; 104 } 105 106 slot_type* slot() const { 107 assert(!empty()); 108 return reinterpret_cast<slot_type*>(std::addressof(slot_space_)); 109 } 110 allocator_type* alloc() { return std::addressof(*alloc_); } 111 112 private: 113 absl::optional<allocator_type> alloc_ = {}; 114 alignas(slot_type) mutable unsigned char slot_space_[sizeof(slot_type)] = {}; 115 }; 116 117 // For sets. 118 template <typename Policy, typename PolicyTraits, typename Alloc, 119 typename = void> 120 class node_handle : public node_handle_base<PolicyTraits, Alloc> { 121 using Base = node_handle_base<PolicyTraits, Alloc>; 122 123 public: 124 using value_type = typename PolicyTraits::value_type; 125 126 constexpr node_handle() {} 127 128 value_type& value() const { return PolicyTraits::element(this->slot()); } 129 130 private: 131 friend struct CommonAccess; 132 133 using Base::Base; 134 }; 135 136 // For maps. 137 template <typename Policy, typename PolicyTraits, typename Alloc> 138 class node_handle<Policy, PolicyTraits, Alloc, 139 absl::void_t<typename Policy::mapped_type>> 140 : public node_handle_base<PolicyTraits, Alloc> { 141 using Base = node_handle_base<PolicyTraits, Alloc>; 142 using slot_type = typename PolicyTraits::slot_type; 143 144 public: 145 using key_type = typename Policy::key_type; 146 using mapped_type = typename Policy::mapped_type; 147 148 constexpr node_handle() {} 149 150 // When C++17 is available, we can use std::launder to provide mutable 151 // access to the key. Otherwise, we provide const access. 152 auto key() const 153 -> decltype(PolicyTraits::mutable_key(std::declval<slot_type*>())) { 154 return PolicyTraits::mutable_key(this->slot()); 155 } 156 157 mapped_type& mapped() const { 158 return PolicyTraits::value(&PolicyTraits::element(this->slot())); 159 } 160 161 private: 162 friend struct CommonAccess; 163 164 using Base::Base; 165 }; 166 167 // Provide access to non-public node-handle functions. 168 struct CommonAccess { 169 template <typename Node> 170 static auto GetSlot(const Node& node) -> decltype(node.slot()) { 171 return node.slot(); 172 } 173 174 template <typename Node> 175 static void Destroy(Node* node) { 176 node->destroy(); 177 } 178 179 template <typename Node> 180 static void Reset(Node* node) { 181 node->reset(); 182 } 183 184 template <typename T, typename... Args> 185 static T Transfer(Args&&... args) { 186 return T(typename T::transfer_tag_t{}, std::forward<Args>(args)...); 187 } 188 189 template <typename T, typename... Args> 190 static T Construct(Args&&... args) { 191 return T(typename T::construct_tag_t{}, std::forward<Args>(args)...); 192 } 193 }; 194 195 // Implement the insert_return_type<> concept of C++17. 196 template <class Iterator, class NodeType> 197 struct InsertReturnType { 198 Iterator position; 199 bool inserted; 200 NodeType node; 201 }; 202 203 } // namespace container_internal 204 ABSL_NAMESPACE_END 205 } // namespace absl 206 207 #endif // ABSL_CONTAINER_INTERNAL_COMMON_H_ 208