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 // TODO(b/402804213): Clean up these macros when no longer needed. 25 #define ABSL_INTERNAL_SINGLE_ARG(...) __VA_ARGS__ 26 27 #define ABSL_INTERNAL_IF_true(if_satisfied, ...) if_satisfied 28 #define ABSL_INTERNAL_IF_false(if_satisfied, ...) __VA_ARGS__ 29 30 #define ABSL_INTERNAL_IF_true_AND_true ABSL_INTERNAL_IF_true 31 #define ABSL_INTERNAL_IF_false_AND_false ABSL_INTERNAL_IF_false 32 #define ABSL_INTERNAL_IF_true_AND_false ABSL_INTERNAL_IF_false_AND_false 33 #define ABSL_INTERNAL_IF_false_AND_true ABSL_INTERNAL_IF_false_AND_false 34 35 #define ABSL_INTERNAL_IF_true_OR_true ABSL_INTERNAL_IF_true 36 #define ABSL_INTERNAL_IF_false_OR_false ABSL_INTERNAL_IF_false 37 #define ABSL_INTERNAL_IF_true_OR_false ABSL_INTERNAL_IF_true_OR_true 38 #define ABSL_INTERNAL_IF_false_OR_true ABSL_INTERNAL_IF_true_OR_true 39 40 #define ABSL_INTERNAL_IF_true_NOR_true ABSL_INTERNAL_IF_false_AND_false 41 #define ABSL_INTERNAL_IF_false_NOR_false ABSL_INTERNAL_IF_true_AND_true 42 #define ABSL_INTERNAL_IF_true_NOR_false ABSL_INTERNAL_IF_false_AND_true 43 #define ABSL_INTERNAL_IF_false_NOR_true ABSL_INTERNAL_IF_true_AND_false 44 45 #define ABSL_INTERNAL_COMMA , 46 47 namespace absl { 48 ABSL_NAMESPACE_BEGIN 49 namespace container_internal { 50 51 // TODO(b/402804213): Clean up these traits when no longer needed or 52 // deduplicate them with absl::functional_internal::EnableIf. 53 template <class Cond> 54 using EnableIf = std::enable_if_t<Cond::value, int>; 55 56 template <bool Value, class T> 57 using HasValue = std::conditional_t<Value, T, absl::negation<T>>; 58 59 template <class T> 60 struct IfRRef { 61 template <class Other> 62 using AddPtr = Other; 63 }; 64 65 template <class T> 66 struct IfRRef<T&&> { 67 template <class Other> 68 using AddPtr = Other*; 69 }; 70 71 template <class, class = void> 72 struct IsTransparent : std::false_type {}; 73 template <class T> 74 struct IsTransparent<T, absl::void_t<typename T::is_transparent>> 75 : std::true_type {}; 76 77 template <bool is_transparent> 78 struct KeyArg { 79 // Transparent. Forward `K`. 80 template <typename K, typename key_type> 81 using type = K; 82 }; 83 84 template <> 85 struct KeyArg<false> { 86 // Not transparent. Always use `key_type`. 87 template <typename K, typename key_type> 88 using type = key_type; 89 }; 90 91 // The node_handle concept from C++17. 92 // We specialize node_handle for sets and maps. node_handle_base holds the 93 // common API of both. 94 template <typename PolicyTraits, typename Alloc> 95 class node_handle_base { 96 protected: 97 using slot_type = typename PolicyTraits::slot_type; 98 99 public: 100 using allocator_type = Alloc; 101 102 constexpr node_handle_base() = default; 103 node_handle_base(node_handle_base&& other) noexcept { 104 *this = std::move(other); 105 } 106 ~node_handle_base() { destroy(); } 107 node_handle_base& operator=(node_handle_base&& other) noexcept { 108 destroy(); 109 if (!other.empty()) { 110 alloc_ = other.alloc_; 111 PolicyTraits::transfer(alloc(), slot(), other.slot()); 112 other.reset(); 113 } 114 return *this; 115 } 116 117 bool empty() const noexcept { return !alloc_; } 118 explicit operator bool() const noexcept { return !empty(); } 119 allocator_type get_allocator() const { return *alloc_; } 120 121 protected: 122 friend struct CommonAccess; 123 124 struct transfer_tag_t {}; 125 node_handle_base(transfer_tag_t, const allocator_type& a, slot_type* s) 126 : alloc_(a) { 127 PolicyTraits::transfer(alloc(), slot(), s); 128 } 129 130 struct construct_tag_t {}; 131 template <typename... Args> 132 node_handle_base(construct_tag_t, const allocator_type& a, Args&&... args) 133 : alloc_(a) { 134 PolicyTraits::construct(alloc(), slot(), std::forward<Args>(args)...); 135 } 136 137 void destroy() { 138 if (!empty()) { 139 PolicyTraits::destroy(alloc(), slot()); 140 reset(); 141 } 142 } 143 144 void reset() { 145 assert(alloc_.has_value()); 146 alloc_ = absl::nullopt; 147 } 148 149 slot_type* slot() const { 150 assert(!empty()); 151 return reinterpret_cast<slot_type*>(std::addressof(slot_space_)); 152 } 153 allocator_type* alloc() { return std::addressof(*alloc_); } 154 155 private: 156 absl::optional<allocator_type> alloc_ = {}; 157 alignas(slot_type) mutable unsigned char slot_space_[sizeof(slot_type)] = {}; 158 }; 159 160 // For sets. 161 template <typename Policy, typename PolicyTraits, typename Alloc, 162 typename = void> 163 class node_handle : public node_handle_base<PolicyTraits, Alloc> { 164 using Base = node_handle_base<PolicyTraits, Alloc>; 165 166 public: 167 using value_type = typename PolicyTraits::value_type; 168 169 constexpr node_handle() {} 170 171 value_type& value() const { return PolicyTraits::element(this->slot()); } 172 173 private: 174 friend struct CommonAccess; 175 176 using Base::Base; 177 }; 178 179 // For maps. 180 template <typename Policy, typename PolicyTraits, typename Alloc> 181 class node_handle<Policy, PolicyTraits, Alloc, 182 absl::void_t<typename Policy::mapped_type>> 183 : public node_handle_base<PolicyTraits, Alloc> { 184 using Base = node_handle_base<PolicyTraits, Alloc>; 185 using slot_type = typename PolicyTraits::slot_type; 186 187 public: 188 using key_type = typename Policy::key_type; 189 using mapped_type = typename Policy::mapped_type; 190 191 constexpr node_handle() {} 192 193 // When C++17 is available, we can use std::launder to provide mutable 194 // access to the key. Otherwise, we provide const access. 195 auto key() const 196 -> decltype(PolicyTraits::mutable_key(std::declval<slot_type*>())) { 197 return PolicyTraits::mutable_key(this->slot()); 198 } 199 200 mapped_type& mapped() const { 201 return PolicyTraits::value(&PolicyTraits::element(this->slot())); 202 } 203 204 private: 205 friend struct CommonAccess; 206 207 using Base::Base; 208 }; 209 210 // Provide access to non-public node-handle functions. 211 struct CommonAccess { 212 template <typename Node> 213 static auto GetSlot(const Node& node) -> decltype(node.slot()) { 214 return node.slot(); 215 } 216 217 template <typename Node> 218 static void Destroy(Node* node) { 219 node->destroy(); 220 } 221 222 template <typename Node> 223 static void Reset(Node* node) { 224 node->reset(); 225 } 226 227 template <typename T, typename... Args> 228 static T Transfer(Args&&... args) { 229 return T(typename T::transfer_tag_t{}, std::forward<Args>(args)...); 230 } 231 232 template <typename T, typename... Args> 233 static T Construct(Args&&... args) { 234 return T(typename T::construct_tag_t{}, std::forward<Args>(args)...); 235 } 236 }; 237 238 // Implement the insert_return_type<> concept of C++17. 239 template <class Iterator, class NodeType> 240 struct InsertReturnType { 241 Iterator position; 242 bool inserted; 243 NodeType node; 244 }; 245 246 } // namespace container_internal 247 ABSL_NAMESPACE_END 248 } // namespace absl 249 250 #endif // ABSL_CONTAINER_INTERNAL_COMMON_H_ 251