1 /*
2     Copyright (c) 2005-2020 Intel Corporation
3 
4     Licensed under the Apache License, Version 2.0 (the "License");
5     you may not use this file except in compliance with the License.
6     You may obtain a copy of the License at
7 
8         http://www.apache.org/licenses/LICENSE-2.0
9 
10     Unless required by applicable law or agreed to in writing, software
11     distributed under the License is distributed on an "AS IS" BASIS,
12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13     See the License for the specific language governing permissions and
14     limitations under the License.
15 */
16 
17 #ifndef __TBB_concurrent_unordered_map_H
18 #define __TBB_concurrent_unordered_map_H
19 
20 #include "detail/_namespace_injection.h"
21 #include "detail/_concurrent_unordered_base.h"
22 #include "tbb_allocator.h"
23 #include <functional>
24 
25 namespace tbb {
26 namespace detail {
27 namespace d1 {
28 
29 template <typename Key, typename T, typename Hash, typename KeyEqual, typename Allocator, bool AllowMultimapping>
30 struct concurrent_unordered_map_traits {
31     using value_type = std::pair<const Key, T>;
32     using key_type = Key;
33     using allocator_type = Allocator;
34     using hash_compare_type = hash_compare<Key, Hash, KeyEqual>;
35     static constexpr bool allow_multimapping = AllowMultimapping;
36 
37     static constexpr const key_type& get_key( const value_type& value ) {
38         return value.first;
39     }
40 }; // struct concurrent_unordered_map_traits
41 
42 template <typename Key, typename T, typename Hash, typename KeyEqual, typename Allocator>
43 class concurrent_unordered_multimap;
44 
45 template <typename Key, typename T, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>,
46           typename Allocator = tbb::tbb_allocator<std::pair<const Key, T>> >
47 class concurrent_unordered_map
48     : public concurrent_unordered_base<concurrent_unordered_map_traits<Key, T, Hash, KeyEqual, Allocator, false>>
49 {
50     using traits_type = concurrent_unordered_map_traits<Key, T, Hash, KeyEqual, Allocator, false>;
51     using base_type = concurrent_unordered_base<traits_type>;
52 public:
53     using key_type = typename base_type::key_type;
54     using mapped_type = T;
55     using value_type = typename base_type::value_type;
56     using size_type = typename base_type::size_type;
57     using difference_type = typename base_type::difference_type;
58     using hasher = typename base_type::hasher;
59     using key_equal = typename base_type::key_equal;
60     using allocator_type = typename base_type::allocator_type;
61     using reference = typename base_type::reference;
62     using const_reference = typename base_type::const_reference;
63     using pointer = typename base_type::pointer;
64     using const_pointer = typename base_type::const_pointer;
65     using iterator = typename base_type::iterator;
66     using const_iterator = typename base_type::const_iterator;
67     using local_iterator = typename base_type::local_iterator;
68     using const_local_iterator = typename base_type::const_local_iterator;
69     using node_type = typename base_type::node_type;
70 
71     // Include constructors of base type
72     using base_type::base_type;
73     using base_type::operator=;
74 
75     // Observers
76     mapped_type& operator[]( const key_type& key ) {
77         iterator where = this->find(key);
78 
79         if (where == this->end()) {
80             where = this->emplace(std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>()).first;
81         }
82         return where->second;
83     }
84 
85     mapped_type& operator[]( key_type&& key ) {
86         iterator where = this->find(key);
87 
88         if (where == this->end()) {
89             where = this->emplace(std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>()).first;
90         }
91         return where->second;
92     }
93 
94     mapped_type& at( const key_type& key ) {
95         iterator where = this->find(key);
96 
97         if (where == this->end()) {
98             throw_exception(exception_id::invalid_key);
99         }
100         return where->second;
101     }
102 
103     const mapped_type& at( const key_type& key ) const {
104         const_iterator where = this->find(key);
105 
106         if (where == this->end()) {
107             throw_exception(exception_id::out_of_range);
108         }
109         return where->second;
110     }
111 
112     using base_type::insert;
113 
114     template<typename P>
115     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
116                             std::pair<iterator, bool>>::type insert( P&& value ) {
117         return this->emplace(std::forward<P>(value));
118     }
119 
120     template<typename P>
121     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
122                             iterator>::type insert( const_iterator hint, P&& value ) {
123         return this->emplace_hint(hint, std::forward<P>(value));
124     }
125 
126     template <typename OtherHash, typename OtherKeyEqual>
127     void merge( concurrent_unordered_map<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
128         this->internal_merge(source);
129     }
130 
131     template <typename OtherHash, typename OtherKeyEqual>
132     void merge( concurrent_unordered_map<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
133         this->internal_merge(std::move(source));
134     }
135 
136     template <typename OtherHash, typename OtherKeyEqual>
137     void merge( concurrent_unordered_multimap<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
138         this->internal_merge(source);
139     }
140 
141     template <typename OtherHash, typename OtherKeyEqual>
142     void merge( concurrent_unordered_multimap<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
143         this->internal_merge(std::move(source));
144     }
145 }; // class concurrent_unordered_map
146 
147 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
148 
149 template <typename Key, typename Mapped>
150 using cu_map_def_allocator = tbb::tbb_allocator<std::pair<const Key, Mapped>>;
151 
152 template <template <typename...> class Map, typename Key, typename Mapped, typename... Args>
153 using cu_map_type = Map<Key, Mapped,
154                         std::conditional_t<(sizeof...(Args) > 0) && !is_allocator_v<pack_element_t<0, Args...>>,
155                                            pack_element_t<0, Args...>, std::hash<Key>>,
156                         std::conditional_t<(sizeof...(Args) > 1) && !is_allocator_v<pack_element_t<1, Args...>>,
157                                            pack_element_t<1, Args...>, std::equal_to<Key>>,
158                         std::conditional_t<(sizeof...(Args) > 0) && is_allocator_v<pack_element_t<sizeof...(Args) - 1, Args...>>,
159                                            pack_element_t<sizeof...(Args) - 1, Args...>,
160                                            cu_map_def_allocator<Key, Mapped>>>;
161 
162 // Deduction guide for copy constructor with additional allocator parameter
163 // TODO: Investigate why implicit deduction guides are not generated
164 //       for concurrent_unordered_map( const concurrent_unordered_map&, Allocator).
165 template <typename Key, typename Val, typename Hash, typename KeyEq, typename Allocator>
166 concurrent_unordered_map( const concurrent_unordered_map<Key, Val, Hash, KeyEq, Allocator>&, const Allocator& )
167 -> concurrent_unordered_map<Key, Val, Hash, KeyEq, Allocator>;
168 
169 // Deduction guide for the constructor from two iterators
170 template <typename I>
171 concurrent_unordered_map( I, I )
172 -> cu_map_type<concurrent_unordered_map, iterator_key_t<I>, iterator_mapped_t<I>>;
173 
174 // Deduction guide for the constructor from two iterators and hasher/equal/allocator
175 template <typename I, typename... Args>
176 concurrent_unordered_map( I, I, std::size_t, Args... )
177 -> cu_map_type<concurrent_unordered_map, iterator_key_t<I>, iterator_mapped_t<I>, Args...>;
178 
179 // Deduction guide for the constructor from an initializer_list
180 template <typename Key, typename Mapped>
181 concurrent_unordered_map( std::initializer_list<std::pair<const Key, Mapped>> )
182 -> cu_map_type<concurrent_unordered_map, Key, Mapped>;
183 
184 // Deduction guide for the constructor from an initializer_list and hasher/equal/allocator
185 template <typename Key, typename Mapped, typename... Args>
186 concurrent_unordered_map( std::initializer_list<std::pair<const Key, Mapped>>, std::size_t, Args... )
187 -> cu_map_type<concurrent_unordered_map, Key, Mapped, Args...>;
188 
189 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
190 
191 template <typename Key, typename T, typename Hash, typename KeyEqual, typename Allocator>
192 void swap( concurrent_unordered_map<Key, T, Hash, KeyEqual, Allocator>& lhs,
193            concurrent_unordered_map<Key, T, Hash, KeyEqual, Allocator>& rhs ) {
194     lhs.swap(rhs);
195 }
196 
197 template <typename Key, typename T, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>,
198           typename Allocator = tbb::tbb_allocator<std::pair<const Key, T>> >
199 class concurrent_unordered_multimap
200     : public concurrent_unordered_base<concurrent_unordered_map_traits<Key, T, Hash, KeyEqual, Allocator, true>>
201 {
202     using traits_type = concurrent_unordered_map_traits<Key, T, Hash, KeyEqual, Allocator, true>;
203     using base_type = concurrent_unordered_base<traits_type>;
204 public:
205     using key_type = typename base_type::key_type;
206     using mapped_type = T;
207     using value_type = typename base_type::value_type;
208     using size_type = typename base_type::size_type;
209     using difference_type = typename base_type::difference_type;
210     using hasher = typename base_type::hasher;
211     using key_equal = typename base_type::key_equal;
212     using allocator_type = typename base_type::allocator_type;
213     using reference = typename base_type::reference;
214     using const_reference = typename base_type::const_reference;
215     using pointer = typename base_type::pointer;
216     using const_pointer = typename base_type::const_pointer;
217     using iterator = typename base_type::iterator;
218     using const_iterator = typename base_type::const_iterator;
219     using local_iterator = typename base_type::local_iterator;
220     using const_local_iterator = typename base_type::const_local_iterator;
221     using node_type = typename base_type::node_type;
222 
223     // Include constructors of base type
224     using base_type::base_type;
225     using base_type::operator=;
226     using base_type::insert;
227 
228     template <typename P>
229     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
230                             std::pair<iterator, bool>>::type insert( P&& value ) {
231         return this->emplace(std::forward<P>(value));
232     }
233 
234     template<typename P>
235     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
236                             iterator>::type insert( const_iterator hint, P&& value ) {
237         return this->emplace_hint(hint, std::forward<P&&>(value));
238     }
239 
240     template <typename OtherHash, typename OtherKeyEqual>
241     void merge( concurrent_unordered_map<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
242         this->internal_merge(source);
243     }
244 
245     template <typename OtherHash, typename OtherKeyEqual>
246     void merge( concurrent_unordered_map<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
247         this->internal_merge(std::move(source));
248     }
249 
250     template <typename OtherHash, typename OtherKeyEqual>
251     void merge( concurrent_unordered_multimap<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
252         this->internal_merge(source);
253     }
254 
255     template <typename OtherHash, typename OtherKeyEqual>
256     void merge( concurrent_unordered_multimap<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
257         this->internal_merge(std::move(source));
258     }
259 }; // class concurrent_unordered_multimap
260 
261 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
262 
263 // Deduction guide for copy constructor with additional allocator parameter
264 // TODO: Investigate why implicit deduction guides are not generated
265 //       for concurrent_unordered_multimap( const concurrent_unordered_multimap&, Allocator).
266 template <typename Key, typename Val, typename Hash, typename KeyEq, typename Allocator>
267 concurrent_unordered_multimap( const concurrent_unordered_multimap<Key, Val, Hash, KeyEq, Allocator>&, const Allocator& )
268 -> concurrent_unordered_multimap<Key, Val, Hash, KeyEq, Allocator>;
269 
270 // Deduction guide for the constructor from two iterators
271 template <typename I>
272 concurrent_unordered_multimap( I, I )
273 -> cu_map_type<concurrent_unordered_multimap, iterator_key_t<I>, iterator_mapped_t<I>>;
274 
275 // Deduction guide for the constructor from two iterators and hasher/equal/allocator
276 template <typename I, typename... Args>
277 concurrent_unordered_multimap( I, I, std::size_t, Args... )
278 -> cu_map_type<concurrent_unordered_multimap, iterator_key_t<I>, iterator_mapped_t<I>, Args...>;
279 
280 // Deduction guide for the constructor from an initializer_list
281 template <typename Key, typename Mapped>
282 concurrent_unordered_multimap( std::initializer_list<std::pair<const Key, Mapped>> )
283 -> cu_map_type<concurrent_unordered_multimap, Key, Mapped>;
284 
285 // Deduction guide for the constructor from an initializer_list and hasher/equal/allocator
286 template <typename Key, typename Mapped, typename... Args>
287 concurrent_unordered_multimap( std::initializer_list<std::pair<const Key, Mapped>>, std::size_t, Args... )
288 -> cu_map_type<concurrent_unordered_multimap, Key, Mapped, Args...>;
289 
290 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
291 
292 template <typename Key, typename T, typename Hash, typename KeyEqual, typename Allocator>
293 void swap( concurrent_unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& lhs,
294            concurrent_unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& rhs ) {
295     lhs.swap(rhs);
296 }
297 
298 } // namespace d1
299 } // namespace detail
300 
301 inline namespace v1 {
302 
303 using detail::d1::concurrent_unordered_map;
304 using detail::d1::concurrent_unordered_multimap;
305 using detail::split;
306 
307 } // inline namespace v1
308 } // namespace tbb
309 
310 #endif // __TBB_concurrent_unordered_map_H
311