raw_hash_map.h (17405B)
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_RAW_HASH_MAP_H_ 16 #define ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_ 17 18 #include <tuple> 19 #include <type_traits> 20 #include <utility> 21 22 #include "absl/base/attributes.h" 23 #include "absl/base/config.h" 24 #include "absl/base/internal/throw_delegate.h" 25 #include "absl/container/internal/common_policy_traits.h" 26 #include "absl/container/internal/container_memory.h" 27 #include "absl/container/internal/raw_hash_set.h" // IWYU pragma: export 28 #include "absl/meta/type_traits.h" 29 30 namespace absl { 31 ABSL_NAMESPACE_BEGIN 32 namespace container_internal { 33 34 template <class Policy, class Hash, class Eq, class Alloc> 35 class raw_hash_map : public raw_hash_set<Policy, Hash, Eq, Alloc> { 36 // P is Policy. It's passed as a template argument to support maps that have 37 // incomplete types as values, as in unordered_map<K, IncompleteType>. 38 // MappedReference<> may be a non-reference type. 39 template <class P> 40 using MappedReference = decltype(P::value( 41 std::addressof(std::declval<typename raw_hash_map::reference>()))); 42 43 // MappedConstReference<> may be a non-reference type. 44 template <class P> 45 using MappedConstReference = decltype(P::value( 46 std::addressof(std::declval<typename raw_hash_map::const_reference>()))); 47 48 template <class K> 49 using key_arg = 50 typename KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>:: 51 template type<K, typename Policy::key_type>; 52 53 // NOTE: The mess here is to shorten the code for the (very repetitive) 54 // function overloads, and to allow the lifetime-bound overloads to dispatch 55 // to the non-lifetime-bound overloads, to ensure there is a single source of 56 // truth for each overload set. 57 // 58 // Enabled if an assignment from the given type would require the 59 // source object to remain alive for the life of the element. 60 // 61 // TODO(b/402804213): Remove these traits and simplify the overloads whenever 62 // we have a better mechanism available to handle lifetime analysis. 63 template <class K, bool Value, typename = void> 64 using LifetimeBoundK = HasValue< 65 Value, std::conditional_t<policy_trait_element_is_owner<Policy>::value, 66 std::false_type, 67 type_traits_internal::IsLifetimeBoundAssignment< 68 typename Policy::key_type, K>>>; 69 template <class V, bool Value, typename = void> 70 using LifetimeBoundV = 71 HasValue<Value, type_traits_internal::IsLifetimeBoundAssignment< 72 typename Policy::mapped_type, V>>; 73 template <class K, bool KValue, class V, bool VValue, typename... Dummy> 74 using LifetimeBoundKV = 75 absl::conjunction<LifetimeBoundK<K, KValue, absl::void_t<Dummy...>>, 76 LifetimeBoundV<V, VValue>>; 77 78 public: 79 using key_type = typename Policy::key_type; 80 using mapped_type = typename Policy::mapped_type; 81 82 static_assert(!std::is_reference<key_type>::value, ""); 83 84 // TODO(b/187807849): Evaluate whether to support reference mapped_type and 85 // remove this assertion if/when it is supported. 86 static_assert(!std::is_reference<mapped_type>::value, ""); 87 88 using iterator = typename raw_hash_map::raw_hash_set::iterator; 89 using const_iterator = typename raw_hash_map::raw_hash_set::const_iterator; 90 91 raw_hash_map() {} 92 using raw_hash_map::raw_hash_set::raw_hash_set; 93 94 // The last two template parameters ensure that both arguments are rvalues 95 // (lvalue arguments are handled by the overloads below). This is necessary 96 // for supporting bitfield arguments. 97 // 98 // union { int n : 1; }; 99 // flat_hash_map<int, int> m; 100 // m.insert_or_assign(n, n); 101 // 102 // TODO(b/402804213): Remove these macros whenever we have a better mechanism 103 // available to handle lifetime analysis. 104 #define ABSL_INTERNAL_X(Func, Callee, KQual, VQual, KValue, VValue, Tail, ...) \ 105 template < \ 106 typename K = key_type, class V = mapped_type, \ 107 ABSL_INTERNAL_IF_##KValue##_NOR_##VValue( \ 108 int = (EnableIf<LifetimeBoundKV<K, KValue, V, VValue, \ 109 IfRRef<int KQual>::AddPtr<K>, \ 110 IfRRef<int VQual>::AddPtr<V>>>()), \ 111 ABSL_INTERNAL_SINGLE_ARG( \ 112 int &..., \ 113 decltype(EnableIf<LifetimeBoundKV<K, KValue, V, VValue>>()) = \ 114 0))> \ 115 decltype(auto) Func( \ 116 __VA_ARGS__ key_arg<K> KQual k ABSL_INTERNAL_IF_##KValue( \ 117 ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this)), \ 118 V VQual v ABSL_INTERNAL_IF_##VValue(ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY( \ 119 this))) ABSL_ATTRIBUTE_LIFETIME_BOUND { \ 120 return ABSL_INTERNAL_IF_##KValue##_OR_##VValue( \ 121 (this->template Func<K, V, 0>), Callee)( \ 122 std::forward<decltype(k)>(k), std::forward<decltype(v)>(v)) Tail; \ 123 } \ 124 static_assert(true, "This is to force a semicolon.") 125 126 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 127 false, false, ABSL_INTERNAL_SINGLE_ARG()); 128 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 129 false, true, ABSL_INTERNAL_SINGLE_ARG()); 130 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 131 true, false, ABSL_INTERNAL_SINGLE_ARG()); 132 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 133 true, true, ABSL_INTERNAL_SINGLE_ARG()); 134 135 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, false, 136 false, ABSL_INTERNAL_SINGLE_ARG()); 137 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, false, 138 true, ABSL_INTERNAL_SINGLE_ARG()); 139 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, true, 140 false, ABSL_INTERNAL_SINGLE_ARG()); 141 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, true, 142 true, ABSL_INTERNAL_SINGLE_ARG()); 143 144 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, false, 145 false, ABSL_INTERNAL_SINGLE_ARG()); 146 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, false, 147 true, ABSL_INTERNAL_SINGLE_ARG()); 148 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, true, 149 false, ABSL_INTERNAL_SINGLE_ARG()); 150 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, true, 151 true, ABSL_INTERNAL_SINGLE_ARG()); 152 153 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, false, false, 154 ABSL_INTERNAL_SINGLE_ARG()); 155 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, false, true, 156 ABSL_INTERNAL_SINGLE_ARG()); 157 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, true, false, 158 ABSL_INTERNAL_SINGLE_ARG()); 159 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, true, true, 160 ABSL_INTERNAL_SINGLE_ARG()); 161 162 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 163 false, false, .first, const_iterator ABSL_INTERNAL_COMMA); 164 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 165 false, true, .first, const_iterator ABSL_INTERNAL_COMMA); 166 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 167 true, false, .first, const_iterator ABSL_INTERNAL_COMMA); 168 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, const &, 169 true, true, .first, const_iterator ABSL_INTERNAL_COMMA); 170 171 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, false, 172 false, .first, const_iterator ABSL_INTERNAL_COMMA); 173 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, false, 174 true, .first, const_iterator ABSL_INTERNAL_COMMA); 175 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, true, 176 false, .first, const_iterator ABSL_INTERNAL_COMMA); 177 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, const &, &&, true, 178 true, .first, const_iterator ABSL_INTERNAL_COMMA); 179 180 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, false, 181 false, .first, const_iterator ABSL_INTERNAL_COMMA); 182 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, false, 183 true, .first, const_iterator ABSL_INTERNAL_COMMA); 184 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, true, 185 false, .first, const_iterator ABSL_INTERNAL_COMMA); 186 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, const &, true, 187 true, .first, const_iterator ABSL_INTERNAL_COMMA); 188 189 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, false, false, 190 .first, const_iterator ABSL_INTERNAL_COMMA); 191 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, false, true, 192 .first, const_iterator ABSL_INTERNAL_COMMA); 193 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, true, false, 194 .first, const_iterator ABSL_INTERNAL_COMMA); 195 ABSL_INTERNAL_X(insert_or_assign, insert_or_assign_impl, &&, &&, true, true, 196 .first, const_iterator ABSL_INTERNAL_COMMA); 197 #undef ABSL_INTERNAL_X 198 199 // All `try_emplace()` overloads make the same guarantees regarding rvalue 200 // arguments as `std::unordered_map::try_emplace()`, namely that these 201 // functions will not move from rvalue arguments if insertions do not happen. 202 template <class K = key_type, int = EnableIf<LifetimeBoundK<K, false, K *>>(), 203 class... Args, 204 typename std::enable_if< 205 !std::is_convertible<K, const_iterator>::value, int>::type = 0> 206 std::pair<iterator, bool> try_emplace(key_arg<K> &&k, Args &&...args) 207 ABSL_ATTRIBUTE_LIFETIME_BOUND { 208 return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...); 209 } 210 211 template <class K = key_type, class... Args, 212 EnableIf<LifetimeBoundK<K, true, K *>> = 0, 213 typename std::enable_if< 214 !std::is_convertible<K, const_iterator>::value, int>::type = 0> 215 std::pair<iterator, bool> try_emplace( 216 key_arg<K> &&k ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this), 217 Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 218 return this->template try_emplace<K, 0>(std::forward<K>(k), 219 std::forward<Args>(args)...); 220 } 221 222 template <class K = key_type, int = EnableIf<LifetimeBoundK<K, false>>(), 223 class... Args, 224 typename std::enable_if< 225 !std::is_convertible<K, const_iterator>::value, int>::type = 0> 226 std::pair<iterator, bool> try_emplace(const key_arg<K> &k, Args &&...args) 227 ABSL_ATTRIBUTE_LIFETIME_BOUND { 228 return try_emplace_impl(k, std::forward<Args>(args)...); 229 } 230 template <class K = key_type, class... Args, 231 EnableIf<LifetimeBoundK<K, true>> = 0, 232 typename std::enable_if< 233 !std::is_convertible<K, const_iterator>::value, int>::type = 0> 234 std::pair<iterator, bool> try_emplace( 235 const key_arg<K> &k ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this), 236 Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 237 return this->template try_emplace<K, 0>(k, std::forward<Args>(args)...); 238 } 239 240 template <class K = key_type, int = EnableIf<LifetimeBoundK<K, false, K *>>(), 241 class... Args> 242 iterator try_emplace(const_iterator, key_arg<K> &&k, 243 Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 244 return try_emplace(std::forward<K>(k), std::forward<Args>(args)...).first; 245 } 246 template <class K = key_type, class... Args, 247 EnableIf<LifetimeBoundK<K, true, K *>> = 0> 248 iterator try_emplace(const_iterator hint, 249 key_arg<K> &&k ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this), 250 Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 251 return this->template try_emplace<K, 0>(hint, std::forward<K>(k), 252 std::forward<Args>(args)...); 253 } 254 255 template <class K = key_type, int = EnableIf<LifetimeBoundK<K, false>>(), 256 class... Args> 257 iterator try_emplace(const_iterator, const key_arg<K> &k, 258 Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 259 return try_emplace(k, std::forward<Args>(args)...).first; 260 } 261 template <class K = key_type, class... Args, 262 EnableIf<LifetimeBoundK<K, true>> = 0> 263 iterator try_emplace(const_iterator hint, 264 const key_arg<K> &k 265 ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this), 266 Args &&...args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 267 return this->template try_emplace<K, 0>(hint, std::forward<K>(k), 268 std::forward<Args>(args)...); 269 } 270 271 template <class K = key_type, class P = Policy> 272 MappedReference<P> at(const key_arg<K>& key) ABSL_ATTRIBUTE_LIFETIME_BOUND { 273 auto it = this->find(key); 274 if (it == this->end()) { 275 base_internal::ThrowStdOutOfRange( 276 "absl::container_internal::raw_hash_map<>::at"); 277 } 278 return Policy::value(&*it); 279 } 280 281 template <class K = key_type, class P = Policy> 282 MappedConstReference<P> at(const key_arg<K>& key) const 283 ABSL_ATTRIBUTE_LIFETIME_BOUND { 284 auto it = this->find(key); 285 if (it == this->end()) { 286 base_internal::ThrowStdOutOfRange( 287 "absl::container_internal::raw_hash_map<>::at"); 288 } 289 return Policy::value(&*it); 290 } 291 292 template <class K = key_type, class P = Policy, 293 int = EnableIf<LifetimeBoundK<K, false, K *>>()> 294 MappedReference<P> operator[](key_arg<K> &&key) 295 ABSL_ATTRIBUTE_LIFETIME_BOUND { 296 // It is safe to use unchecked_deref here because try_emplace 297 // will always return an iterator pointing to a valid item in the table, 298 // since it inserts if nothing is found for the given key. 299 return Policy::value( 300 &this->unchecked_deref(try_emplace(std::forward<K>(key)).first)); 301 } 302 template <class K = key_type, class P = Policy, int &..., 303 EnableIf<LifetimeBoundK<K, true, K *>> = 0> 304 MappedReference<P> operator[]( 305 key_arg<K> &&key ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this)) 306 ABSL_ATTRIBUTE_LIFETIME_BOUND { 307 return this->template operator[]<K, P, 0>(std::forward<K>(key)); 308 } 309 310 template <class K = key_type, class P = Policy, 311 int = EnableIf<LifetimeBoundK<K, false>>()> 312 MappedReference<P> operator[](const key_arg<K> &key) 313 ABSL_ATTRIBUTE_LIFETIME_BOUND { 314 // It is safe to use unchecked_deref here because try_emplace 315 // will always return an iterator pointing to a valid item in the table, 316 // since it inserts if nothing is found for the given key. 317 return Policy::value(&this->unchecked_deref(try_emplace(key).first)); 318 } 319 template <class K = key_type, class P = Policy, int &..., 320 EnableIf<LifetimeBoundK<K, true>> = 0> 321 MappedReference<P> operator[]( 322 const key_arg<K> &key ABSL_INTERNAL_ATTRIBUTE_CAPTURED_BY(this)) 323 ABSL_ATTRIBUTE_LIFETIME_BOUND { 324 return this->template operator[]<K, P, 0>(key); 325 } 326 327 private: 328 template <class K, class V> 329 std::pair<iterator, bool> insert_or_assign_impl(K&& k, V&& v) 330 ABSL_ATTRIBUTE_LIFETIME_BOUND { 331 auto res = this->find_or_prepare_insert(k); 332 if (res.second) { 333 this->emplace_at(res.first, std::forward<K>(k), std::forward<V>(v)); 334 } else { 335 Policy::value(&*res.first) = std::forward<V>(v); 336 } 337 return res; 338 } 339 340 template <class K = key_type, class... Args> 341 std::pair<iterator, bool> try_emplace_impl(K&& k, Args&&... args) 342 ABSL_ATTRIBUTE_LIFETIME_BOUND { 343 auto res = this->find_or_prepare_insert(k); 344 if (res.second) { 345 this->emplace_at(res.first, std::piecewise_construct, 346 std::forward_as_tuple(std::forward<K>(k)), 347 std::forward_as_tuple(std::forward<Args>(args)...)); 348 } 349 return res; 350 } 351 }; 352 353 } // namespace container_internal 354 ABSL_NAMESPACE_END 355 } // namespace absl 356 357 #endif // ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_