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_CONTAINER_H_ 16 #define ABSL_CONTAINER_INTERNAL_CONTAINER_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 move_tag_t {}; 88 node_handle_base(move_tag_t, const allocator_type& a, slot_type* s) 89 : alloc_(a) { 90 PolicyTraits::construct(alloc(), slot(), s); 91 } 92 93 void destroy() { 94 if (!empty()) { 95 PolicyTraits::destroy(alloc(), slot()); 96 reset(); 97 } 98 } 99 100 void reset() { 101 assert(alloc_.has_value()); 102 alloc_ = absl::nullopt; 103 } 104 105 slot_type* slot() const { 106 assert(!empty()); 107 return reinterpret_cast<slot_type*>(std::addressof(slot_space_)); 108 } 109 allocator_type* alloc() { return std::addressof(*alloc_); } 110 111 private: 112 absl::optional<allocator_type> alloc_ = {}; 113 alignas(slot_type) mutable unsigned char slot_space_[sizeof(slot_type)] = {}; 114 }; 115 116 // For sets. 117 template <typename Policy, typename PolicyTraits, typename Alloc, 118 typename = void> 119 class node_handle : public node_handle_base<PolicyTraits, Alloc> { 120 using Base = node_handle_base<PolicyTraits, Alloc>; 121 122 public: 123 using value_type = typename PolicyTraits::value_type; 124 125 constexpr node_handle() {} 126 127 value_type& value() const { return PolicyTraits::element(this->slot()); } 128 129 private: 130 friend struct CommonAccess; 131 132 using Base::Base; 133 }; 134 135 // For maps. 136 template <typename Policy, typename PolicyTraits, typename Alloc> 137 class node_handle<Policy, PolicyTraits, Alloc, 138 absl::void_t<typename Policy::mapped_type>> 139 : public node_handle_base<PolicyTraits, Alloc> { 140 using Base = node_handle_base<PolicyTraits, Alloc>; 141 using slot_type = typename PolicyTraits::slot_type; 142 143 public: 144 using key_type = typename Policy::key_type; 145 using mapped_type = typename Policy::mapped_type; 146 147 constexpr node_handle() {} 148 149 // When C++17 is available, we can use std::launder to provide mutable 150 // access to the key. Otherwise, we provide const access. 151 auto key() const 152 -> decltype(PolicyTraits::mutable_key(std::declval<slot_type*>())) { 153 return PolicyTraits::mutable_key(this->slot()); 154 } 155 156 mapped_type& mapped() const { 157 return PolicyTraits::value(&PolicyTraits::element(this->slot())); 158 } 159 160 private: 161 friend struct CommonAccess; 162 163 using Base::Base; 164 }; 165 166 // Provide access to non-public node-handle functions. 167 struct CommonAccess { 168 template <typename Node> 169 static auto GetSlot(const Node& node) -> decltype(node.slot()) { 170 return node.slot(); 171 } 172 173 template <typename Node> 174 static void Destroy(Node* node) { 175 node->destroy(); 176 } 177 178 template <typename Node> 179 static void Reset(Node* node) { 180 node->reset(); 181 } 182 183 template <typename T, typename... Args> 184 static T Transfer(Args&&... args) { 185 return T(typename T::transfer_tag_t{}, std::forward<Args>(args)...); 186 } 187 188 template <typename T, typename... Args> 189 static T Move(Args&&... args) { 190 return T(typename T::move_tag_t{}, std::forward<Args>(args)...); 191 } 192 }; 193 194 // Implement the insert_return_type<> concept of C++17. 195 template <class Iterator, class NodeType> 196 struct InsertReturnType { 197 Iterator position; 198 bool inserted; 199 NodeType node; 200 }; 201 202 } // namespace container_internal 203 ABSL_NAMESPACE_END 204 } // namespace absl 205 206 #endif // ABSL_CONTAINER_INTERNAL_CONTAINER_H_ 207