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/container_memory.h" 26 #include "absl/container/internal/raw_hash_set.h" // IWYU pragma: export 27 28 namespace absl { 29 ABSL_NAMESPACE_BEGIN 30 namespace container_internal { 31 32 template <class Policy, class Hash, class Eq, class Alloc> 33 class raw_hash_map : public raw_hash_set<Policy, Hash, Eq, Alloc> { 34 // P is Policy. It's passed as a template argument to support maps that have 35 // incomplete types as values, as in unordered_map<K, IncompleteType>. 36 // MappedReference<> may be a non-reference type. 37 template <class P> 38 using MappedReference = decltype(P::value( 39 std::addressof(std::declval<typename raw_hash_map::reference>()))); 40 41 // MappedConstReference<> may be a non-reference type. 42 template <class P> 43 using MappedConstReference = decltype(P::value( 44 std::addressof(std::declval<typename raw_hash_map::const_reference>()))); 45 46 using KeyArgImpl = 47 KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>; 48 49 public: 50 using key_type = typename Policy::key_type; 51 using mapped_type = typename Policy::mapped_type; 52 template <class K> 53 using key_arg = typename KeyArgImpl::template type<K, key_type>; 54 55 static_assert(!std::is_reference<key_type>::value, ""); 56 57 // TODO(b/187807849): Evaluate whether to support reference mapped_type and 58 // remove this assertion if/when it is supported. 59 static_assert(!std::is_reference<mapped_type>::value, ""); 60 61 using iterator = typename raw_hash_map::raw_hash_set::iterator; 62 using const_iterator = typename raw_hash_map::raw_hash_set::const_iterator; 63 raw_hash_map()64 raw_hash_map() {} 65 using raw_hash_map::raw_hash_set::raw_hash_set; 66 67 // The last two template parameters ensure that both arguments are rvalues 68 // (lvalue arguments are handled by the overloads below). This is necessary 69 // for supporting bitfield arguments. 70 // 71 // union { int n : 1; }; 72 // flat_hash_map<int, int> m; 73 // m.insert_or_assign(n, n); 74 template <class K = key_type, class V = mapped_type, K* = nullptr, 75 V* = nullptr> insert_or_assign(key_arg<K> && k,V && v)76 std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, V&& v) 77 ABSL_ATTRIBUTE_LIFETIME_BOUND { 78 return insert_or_assign_impl(std::forward<K>(k), std::forward<V>(v)); 79 } 80 81 template <class K = key_type, class V = mapped_type, K* = nullptr> insert_or_assign(key_arg<K> && k,const V & v)82 std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, const V& v) 83 ABSL_ATTRIBUTE_LIFETIME_BOUND { 84 return insert_or_assign_impl(std::forward<K>(k), v); 85 } 86 87 template <class K = key_type, class V = mapped_type, V* = nullptr> insert_or_assign(const key_arg<K> & k,V && v)88 std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, V&& v) 89 ABSL_ATTRIBUTE_LIFETIME_BOUND { 90 return insert_or_assign_impl(k, std::forward<V>(v)); 91 } 92 93 template <class K = key_type, class V = mapped_type> insert_or_assign(const key_arg<K> & k,const V & v)94 std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, const V& v) 95 ABSL_ATTRIBUTE_LIFETIME_BOUND { 96 return insert_or_assign_impl(k, v); 97 } 98 99 template <class K = key_type, class V = mapped_type, K* = nullptr, 100 V* = nullptr> insert_or_assign(const_iterator,key_arg<K> && k,V && v)101 iterator insert_or_assign(const_iterator, key_arg<K>&& k, 102 V&& v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 103 return insert_or_assign(std::forward<K>(k), std::forward<V>(v)).first; 104 } 105 106 template <class K = key_type, class V = mapped_type, K* = nullptr> insert_or_assign(const_iterator,key_arg<K> && k,const V & v)107 iterator insert_or_assign(const_iterator, key_arg<K>&& k, 108 const V& v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 109 return insert_or_assign(std::forward<K>(k), v).first; 110 } 111 112 template <class K = key_type, class V = mapped_type, V* = nullptr> insert_or_assign(const_iterator,const key_arg<K> & k,V && v)113 iterator insert_or_assign(const_iterator, const key_arg<K>& k, 114 V&& v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 115 return insert_or_assign(k, std::forward<V>(v)).first; 116 } 117 118 template <class K = key_type, class V = mapped_type> insert_or_assign(const_iterator,const key_arg<K> & k,const V & v)119 iterator insert_or_assign(const_iterator, const key_arg<K>& k, 120 const V& v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 121 return insert_or_assign(k, v).first; 122 } 123 124 // All `try_emplace()` overloads make the same guarantees regarding rvalue 125 // arguments as `std::unordered_map::try_emplace()`, namely that these 126 // functions will not move from rvalue arguments if insertions do not happen. 127 template <class K = key_type, class... Args, 128 typename std::enable_if< 129 !std::is_convertible<K, const_iterator>::value, int>::type = 0, 130 K* = nullptr> try_emplace(key_arg<K> && k,Args &&...args)131 std::pair<iterator, bool> try_emplace(key_arg<K>&& k, Args&&... args) 132 ABSL_ATTRIBUTE_LIFETIME_BOUND { 133 return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...); 134 } 135 136 template <class K = key_type, class... Args, 137 typename std::enable_if< 138 !std::is_convertible<K, const_iterator>::value, int>::type = 0> try_emplace(const key_arg<K> & k,Args &&...args)139 std::pair<iterator, bool> try_emplace(const key_arg<K>& k, Args&&... args) 140 ABSL_ATTRIBUTE_LIFETIME_BOUND { 141 return try_emplace_impl(k, std::forward<Args>(args)...); 142 } 143 144 template <class K = key_type, class... Args, K* = nullptr> try_emplace(const_iterator,key_arg<K> && k,Args &&...args)145 iterator try_emplace(const_iterator, key_arg<K>&& k, 146 Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 147 return try_emplace(std::forward<K>(k), std::forward<Args>(args)...).first; 148 } 149 150 template <class K = key_type, class... Args> try_emplace(const_iterator,const key_arg<K> & k,Args &&...args)151 iterator try_emplace(const_iterator, const key_arg<K>& k, 152 Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 153 return try_emplace(k, std::forward<Args>(args)...).first; 154 } 155 156 template <class K = key_type, class P = Policy> at(const key_arg<K> & key)157 MappedReference<P> at(const key_arg<K>& key) ABSL_ATTRIBUTE_LIFETIME_BOUND { 158 auto it = this->find(key); 159 if (it == this->end()) { 160 base_internal::ThrowStdOutOfRange( 161 "absl::container_internal::raw_hash_map<>::at"); 162 } 163 return Policy::value(&*it); 164 } 165 166 template <class K = key_type, class P = Policy> at(const key_arg<K> & key)167 MappedConstReference<P> at(const key_arg<K>& key) const 168 ABSL_ATTRIBUTE_LIFETIME_BOUND { 169 auto it = this->find(key); 170 if (it == this->end()) { 171 base_internal::ThrowStdOutOfRange( 172 "absl::container_internal::raw_hash_map<>::at"); 173 } 174 return Policy::value(&*it); 175 } 176 177 template <class K = key_type, class P = Policy, K* = nullptr> 178 MappedReference<P> operator[](key_arg<K>&& key) 179 ABSL_ATTRIBUTE_LIFETIME_BOUND { 180 // It is safe to use unchecked_deref here because try_emplace 181 // will always return an iterator pointing to a valid item in the table, 182 // since it inserts if nothing is found for the given key. 183 return Policy::value( 184 &this->unchecked_deref(try_emplace(std::forward<K>(key)).first)); 185 } 186 187 template <class K = key_type, class P = Policy> 188 MappedReference<P> operator[](const key_arg<K>& key) 189 ABSL_ATTRIBUTE_LIFETIME_BOUND { 190 // It is safe to use unchecked_deref here because try_emplace 191 // will always return an iterator pointing to a valid item in the table, 192 // since it inserts if nothing is found for the given key. 193 return Policy::value(&this->unchecked_deref(try_emplace(key).first)); 194 } 195 196 private: 197 template <class K, class V> insert_or_assign_impl(K && k,V && v)198 std::pair<iterator, bool> insert_or_assign_impl(K&& k, V&& v) 199 ABSL_ATTRIBUTE_LIFETIME_BOUND { 200 auto res = this->find_or_prepare_insert(k); 201 if (res.second) { 202 this->emplace_at(res.first, std::forward<K>(k), std::forward<V>(v)); 203 } else { 204 Policy::value(&*res.first) = std::forward<V>(v); 205 } 206 return res; 207 } 208 209 template <class K = key_type, class... Args> try_emplace_impl(K && k,Args &&...args)210 std::pair<iterator, bool> try_emplace_impl(K&& k, Args&&... args) 211 ABSL_ATTRIBUTE_LIFETIME_BOUND { 212 auto res = this->find_or_prepare_insert(k); 213 if (res.second) { 214 this->emplace_at(res.first, std::piecewise_construct, 215 std::forward_as_tuple(std::forward<K>(k)), 216 std::forward_as_tuple(std::forward<Args>(args)...)); 217 } 218 return res; 219 } 220 }; 221 222 } // namespace container_internal 223 ABSL_NAMESPACE_END 224 } // namespace absl 225 226 #endif // ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_ 227