1 /*
2     Copyright (c) 2005-2021 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     // Required for implicit deduction guides
76     concurrent_unordered_map() = default;
77     concurrent_unordered_map( const concurrent_unordered_map& ) = default;
78     concurrent_unordered_map( const concurrent_unordered_map& other, const allocator_type& alloc ) : base_type(other, alloc) {}
79     concurrent_unordered_map( concurrent_unordered_map&& ) = default;
80     concurrent_unordered_map( concurrent_unordered_map&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
81     // Required to respect the rule of 5
82     concurrent_unordered_map& operator=( const concurrent_unordered_map& ) = default;
83     concurrent_unordered_map& operator=( concurrent_unordered_map&& ) = default;
84 
85     // Observers
86     mapped_type& operator[]( const key_type& key ) {
87         iterator where = this->find(key);
88 
89         if (where == this->end()) {
90             where = this->emplace(std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>()).first;
91         }
92         return where->second;
93     }
94 
95     mapped_type& operator[]( key_type&& key ) {
96         iterator where = this->find(key);
97 
98         if (where == this->end()) {
99             where = this->emplace(std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>()).first;
100         }
101         return where->second;
102     }
103 
104     mapped_type& at( const key_type& key ) {
105         iterator where = this->find(key);
106 
107         if (where == this->end()) {
108             throw_exception(exception_id::invalid_key);
109         }
110         return where->second;
111     }
112 
113     const mapped_type& at( const key_type& key ) const {
114         const_iterator where = this->find(key);
115 
116         if (where == this->end()) {
117             throw_exception(exception_id::out_of_range);
118         }
119         return where->second;
120     }
121 
122     using base_type::insert;
123 
124     template<typename P>
125     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
126                             std::pair<iterator, bool>>::type insert( P&& value ) {
127         return this->emplace(std::forward<P>(value));
128     }
129 
130     template<typename P>
131     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
132                             iterator>::type insert( const_iterator hint, P&& value ) {
133         return this->emplace_hint(hint, std::forward<P>(value));
134     }
135 
136     template <typename OtherHash, typename OtherKeyEqual>
137     void merge( concurrent_unordered_map<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_map<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
143         this->internal_merge(std::move(source));
144     }
145 
146     template <typename OtherHash, typename OtherKeyEqual>
147     void merge( concurrent_unordered_multimap<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
148         this->internal_merge(source);
149     }
150 
151     template <typename OtherHash, typename OtherKeyEqual>
152     void merge( concurrent_unordered_multimap<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
153         this->internal_merge(std::move(source));
154     }
155 }; // class concurrent_unordered_map
156 
157 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
158 template <typename It,
159           typename Hash = std::hash<iterator_key_t<It>>,
160           typename KeyEq = std::equal_to<iterator_key_t<It>>,
161           typename Alloc = tbb::tbb_allocator<iterator_alloc_pair_t<It>>,
162           typename = std::enable_if_t<is_input_iterator_v<It>>,
163           typename = std::enable_if_t<is_allocator_v<Alloc>>,
164           typename = std::enable_if_t<!is_allocator_v<Hash>>,
165           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
166           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
167 concurrent_unordered_map( It, It, std::size_t =  {},
168                           Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
169 -> concurrent_unordered_map<iterator_key_t<It>, iterator_mapped_t<It>, Hash, KeyEq, Alloc>;
170 
171 template <typename Key, typename T,
172           typename Hash = std::hash<std::remove_const_t<Key>>,
173           typename KeyEq = std::equal_to<std::remove_const_t<Key>>,
174           typename Alloc = tbb::tbb_allocator<std::pair<const Key, T>>,
175           typename = std::enable_if_t<is_allocator_v<Alloc>>,
176           typename = std::enable_if_t<!is_allocator_v<Hash>>,
177           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
178           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
179 concurrent_unordered_map( std::initializer_list<std::pair<Key, T>>, std::size_t = {},
180                           Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
181 -> concurrent_unordered_map<std::remove_const_t<Key>, T, Hash, KeyEq, Alloc>;
182 
183 template <typename It, typename Alloc,
184           typename = std::enable_if_t<is_input_iterator_v<It>>,
185           typename = std::enable_if_t<is_allocator_v<Alloc>>>
186 concurrent_unordered_map( It, It, std::size_t, Alloc )
187 -> concurrent_unordered_map<iterator_key_t<It>, iterator_mapped_t<It>,
188                             std::hash<iterator_key_t<It>>,
189                             std::equal_to<iterator_key_t<It>>, Alloc>;
190 
191 // TODO: investigate if a deduction guide for concurrent_unordered_map(It, It, Alloc) is needed
192 
193 template <typename It, typename Hash, typename Alloc,
194           typename = std::enable_if_t<is_input_iterator_v<It>>,
195           typename = std::enable_if_t<is_allocator_v<Alloc>>,
196           typename = std::enable_if_t<!is_allocator_v<Hash>>,
197           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
198 concurrent_unordered_map( It, It, std::size_t, Hash, Alloc )
199 -> concurrent_unordered_map<iterator_key_t<It>, iterator_mapped_t<It>,
200                             Hash, std::equal_to<iterator_key_t<It>>, Alloc>;
201 
202 template <typename Key, typename T, typename Alloc,
203           typename = std::enable_if_t<is_allocator_v<Alloc>>>
204 concurrent_unordered_map( std::initializer_list<std::pair<Key, T>>, std::size_t, Alloc )
205 -> concurrent_unordered_map<std::remove_const_t<Key>, T, std::hash<std::remove_const_t<Key>>,
206                             std::equal_to<std::remove_const_t<Key>>, Alloc>;
207 
208 template <typename Key, typename T, typename Alloc,
209           typename = std::enable_if_t<is_allocator_v<Alloc>>>
210 concurrent_unordered_map( std::initializer_list<std::pair<Key, T>>, Alloc )
211 -> concurrent_unordered_map<std::remove_const_t<Key>, T, std::hash<std::remove_const_t<Key>>,
212                             std::equal_to<std::remove_const_t<Key>>, Alloc>;
213 
214 template <typename Key, typename T, typename Hash, typename Alloc,
215           typename = std::enable_if_t<is_allocator_v<Alloc>>,
216           typename = std::enable_if_t<!is_allocator_v<Hash>>,
217           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
218 concurrent_unordered_map( std::initializer_list<std::pair<Key, T>>, std::size_t, Hash, Alloc )
219 -> concurrent_unordered_map<std::remove_const_t<Key>, T, Hash,
220                             std::equal_to<std::remove_const_t<Key>>, Alloc>;
221 
222 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
223 
224 template <typename Key, typename T, typename Hash, typename KeyEqual, typename Allocator>
225 void swap( concurrent_unordered_map<Key, T, Hash, KeyEqual, Allocator>& lhs,
226            concurrent_unordered_map<Key, T, Hash, KeyEqual, Allocator>& rhs ) {
227     lhs.swap(rhs);
228 }
229 
230 template <typename Key, typename T, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>,
231           typename Allocator = tbb::tbb_allocator<std::pair<const Key, T>> >
232 class concurrent_unordered_multimap
233     : public concurrent_unordered_base<concurrent_unordered_map_traits<Key, T, Hash, KeyEqual, Allocator, true>>
234 {
235     using traits_type = concurrent_unordered_map_traits<Key, T, Hash, KeyEqual, Allocator, true>;
236     using base_type = concurrent_unordered_base<traits_type>;
237 public:
238     using key_type = typename base_type::key_type;
239     using mapped_type = T;
240     using value_type = typename base_type::value_type;
241     using size_type = typename base_type::size_type;
242     using difference_type = typename base_type::difference_type;
243     using hasher = typename base_type::hasher;
244     using key_equal = typename base_type::key_equal;
245     using allocator_type = typename base_type::allocator_type;
246     using reference = typename base_type::reference;
247     using const_reference = typename base_type::const_reference;
248     using pointer = typename base_type::pointer;
249     using const_pointer = typename base_type::const_pointer;
250     using iterator = typename base_type::iterator;
251     using const_iterator = typename base_type::const_iterator;
252     using local_iterator = typename base_type::local_iterator;
253     using const_local_iterator = typename base_type::const_local_iterator;
254     using node_type = typename base_type::node_type;
255 
256     // Include constructors of base type
257     using base_type::base_type;
258     using base_type::operator=;
259     using base_type::insert;
260 
261     // Required for implicit deduction guides
262     concurrent_unordered_multimap() = default;
263     concurrent_unordered_multimap( const concurrent_unordered_multimap& ) = default;
264     concurrent_unordered_multimap( const concurrent_unordered_multimap& other, const allocator_type& alloc ) : base_type(other, alloc) {}
265     concurrent_unordered_multimap( concurrent_unordered_multimap&& ) = default;
266     concurrent_unordered_multimap( concurrent_unordered_multimap&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
267     // Required to respect the rule of 5
268     concurrent_unordered_multimap& operator=( const concurrent_unordered_multimap& ) = default;
269     concurrent_unordered_multimap& operator=( concurrent_unordered_multimap&& ) = default;
270 
271     template <typename P>
272     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
273                             std::pair<iterator, bool>>::type insert( P&& value ) {
274         return this->emplace(std::forward<P>(value));
275     }
276 
277     template<typename P>
278     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
279                             iterator>::type insert( const_iterator hint, P&& value ) {
280         return this->emplace_hint(hint, std::forward<P&&>(value));
281     }
282 
283     template <typename OtherHash, typename OtherKeyEqual>
284     void merge( concurrent_unordered_map<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
285         this->internal_merge(source);
286     }
287 
288     template <typename OtherHash, typename OtherKeyEqual>
289     void merge( concurrent_unordered_map<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
290         this->internal_merge(std::move(source));
291     }
292 
293     template <typename OtherHash, typename OtherKeyEqual>
294     void merge( concurrent_unordered_multimap<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
295         this->internal_merge(source);
296     }
297 
298     template <typename OtherHash, typename OtherKeyEqual>
299     void merge( concurrent_unordered_multimap<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
300         this->internal_merge(std::move(source));
301     }
302 }; // class concurrent_unordered_multimap
303 
304 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
305 
306 template <typename It,
307           typename Hash = std::hash<iterator_key_t<It>>,
308           typename KeyEq = std::equal_to<iterator_key_t<It>>,
309           typename Alloc = tbb::tbb_allocator<iterator_alloc_pair_t<It>>,
310           typename = std::enable_if_t<is_input_iterator_v<It>>,
311           typename = std::enable_if_t<is_allocator_v<Alloc>>,
312           typename = std::enable_if_t<!is_allocator_v<Hash>>,
313           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
314           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
315 concurrent_unordered_multimap( It, It, std::size_t = {}, Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
316 -> concurrent_unordered_multimap<iterator_key_t<It>, iterator_mapped_t<It>, Hash, KeyEq, Alloc>;
317 
318 template <typename Key, typename T,
319           typename Hash = std::hash<std::remove_const_t<Key>>,
320           typename KeyEq = std::equal_to<std::remove_const_t<Key>>,
321           typename Alloc = tbb::tbb_allocator<std::pair<const Key, T>>,
322           typename = std::enable_if_t<is_allocator_v<Alloc>>,
323           typename = std::enable_if_t<!is_allocator_v<Hash>>,
324           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
325           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
326 concurrent_unordered_multimap( std::initializer_list<std::pair<Key, T>>, std::size_t = {},
327                                Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
328 -> concurrent_unordered_multimap<std::remove_const_t<Key>, T, Hash, KeyEq, Alloc>;
329 
330 template <typename It, typename Alloc,
331           typename = std::enable_if_t<is_input_iterator_v<It>>,
332           typename = std::enable_if_t<is_allocator_v<Alloc>>>
333 concurrent_unordered_multimap( It, It, std::size_t, Alloc )
334 -> concurrent_unordered_multimap<iterator_key_t<It>, iterator_mapped_t<It>,
335                                  std::hash<iterator_key_t<It>>,
336                                  std::equal_to<iterator_key_t<It>>, Alloc>;
337 
338 template <typename It, typename Hash, typename Alloc,
339           typename = std::enable_if_t<is_input_iterator_v<It>>,
340           typename = std::enable_if_t<is_allocator_v<Alloc>>,
341           typename = std::enable_if_t<!is_allocator_v<Hash>>,
342           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
343 concurrent_unordered_multimap( It, It, std::size_t, Hash, Alloc )
344 -> concurrent_unordered_multimap<iterator_key_t<It>, iterator_mapped_t<It>, Hash,
345                                  std::equal_to<iterator_key_t<It>>, Alloc>;
346 
347 template <typename Key, typename T, typename Alloc,
348           typename = std::enable_if_t<is_allocator_v<Alloc>>>
349 concurrent_unordered_multimap( std::initializer_list<std::pair<Key, T>>, std::size_t, Alloc )
350 -> concurrent_unordered_multimap<std::remove_const_t<Key>, T, std::hash<std::remove_const_t<Key>>,
351                                  std::equal_to<std::remove_const_t<Key>>, Alloc>;
352 
353 template <typename Key, typename T, typename Alloc,
354           typename = std::enable_if_t<is_allocator_v<Alloc>>>
355 concurrent_unordered_multimap( std::initializer_list<std::pair<Key, T>>, Alloc )
356 -> concurrent_unordered_multimap<std::remove_const_t<Key>, T, std::hash<std::remove_const_t<Key>>,
357                                  std::equal_to<std::remove_const_t<Key>>, Alloc>;
358 
359 template <typename Key, typename T, typename Hash, typename Alloc,
360           typename = std::enable_if_t<is_allocator_v<Alloc>>,
361           typename = std::enable_if_t<!is_allocator_v<Hash>>,
362           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
363 concurrent_unordered_multimap( std::initializer_list<std::pair<Key, T>>, std::size_t, Hash, Alloc )
364 -> concurrent_unordered_multimap<std::remove_const_t<Key>, T, Hash,
365                                  std::equal_to<std::remove_const_t<Key>>, Alloc>;
366 
367 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
368 
369 template <typename Key, typename T, typename Hash, typename KeyEqual, typename Allocator>
370 void swap( concurrent_unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& lhs,
371            concurrent_unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& rhs ) {
372     lhs.swap(rhs);
373 }
374 
375 } // namespace d1
376 } // namespace detail
377 
378 inline namespace v1 {
379 
380 using detail::d1::concurrent_unordered_map;
381 using detail::d1::concurrent_unordered_multimap;
382 using detail::split;
383 
384 } // inline namespace v1
385 } // namespace tbb
386 
387 #endif // __TBB_concurrent_unordered_map_H
388