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