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