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 
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 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
227 
228 template <typename Key, typename T, typename Hash, typename KeyEqual, typename Allocator>
229 void swap( concurrent_unordered_map<Key, T, Hash, KeyEqual, Allocator>& lhs,
230            concurrent_unordered_map<Key, T, Hash, KeyEqual, Allocator>& rhs ) {
231     lhs.swap(rhs);
232 }
233 
234 template <typename Key, typename T, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>,
235           typename Allocator = tbb::tbb_allocator<std::pair<const Key, T>> >
236 class concurrent_unordered_multimap
237     : public concurrent_unordered_base<concurrent_unordered_map_traits<Key, T, Hash, KeyEqual, Allocator, true>>
238 {
239     using traits_type = concurrent_unordered_map_traits<Key, T, Hash, KeyEqual, Allocator, true>;
240     using base_type = concurrent_unordered_base<traits_type>;
241 public:
242     using key_type = typename base_type::key_type;
243     using mapped_type = T;
244     using value_type = typename base_type::value_type;
245     using size_type = typename base_type::size_type;
246     using difference_type = typename base_type::difference_type;
247     using hasher = typename base_type::hasher;
248     using key_equal = typename base_type::key_equal;
249     using allocator_type = typename base_type::allocator_type;
250     using reference = typename base_type::reference;
251     using const_reference = typename base_type::const_reference;
252     using pointer = typename base_type::pointer;
253     using const_pointer = typename base_type::const_pointer;
254     using iterator = typename base_type::iterator;
255     using const_iterator = typename base_type::const_iterator;
256     using local_iterator = typename base_type::local_iterator;
257     using const_local_iterator = typename base_type::const_local_iterator;
258     using node_type = typename base_type::node_type;
259 
260     // Include constructors of base type
261     using base_type::base_type;
262     using base_type::insert;
263 
264     // Required for implicit deduction guides
265     concurrent_unordered_multimap() = default;
266     concurrent_unordered_multimap( const concurrent_unordered_multimap& ) = default;
267     concurrent_unordered_multimap( const concurrent_unordered_multimap& other, const allocator_type& alloc ) : base_type(other, alloc) {}
268     concurrent_unordered_multimap( concurrent_unordered_multimap&& ) = default;
269     concurrent_unordered_multimap( concurrent_unordered_multimap&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
270     // Required to respect the rule of 5
271     concurrent_unordered_multimap& operator=( const concurrent_unordered_multimap& ) = default;
272     concurrent_unordered_multimap& operator=( concurrent_unordered_multimap&& ) = default;
273 
274     concurrent_unordered_multimap& operator=( std::initializer_list<value_type> il ) {
275         base_type::operator= (il);
276         return *this;
277     }
278 
279     template <typename P>
280     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
281                             std::pair<iterator, bool>>::type insert( P&& value ) {
282         return this->emplace(std::forward<P>(value));
283     }
284 
285     template<typename P>
286     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
287                             iterator>::type insert( const_iterator hint, P&& value ) {
288         return this->emplace_hint(hint, std::forward<P&&>(value));
289     }
290 
291     template <typename OtherHash, typename OtherKeyEqual>
292     void merge( concurrent_unordered_map<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
293         this->internal_merge(source);
294     }
295 
296     template <typename OtherHash, typename OtherKeyEqual>
297     void merge( concurrent_unordered_map<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
298         this->internal_merge(std::move(source));
299     }
300 
301     template <typename OtherHash, typename OtherKeyEqual>
302     void merge( concurrent_unordered_multimap<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_multimap<key_type, mapped_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
308         this->internal_merge(std::move(source));
309     }
310 }; // class concurrent_unordered_multimap
311 
312 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
313 
314 template <typename It,
315           typename Hash = std::hash<iterator_key_t<It>>,
316           typename KeyEq = std::equal_to<iterator_key_t<It>>,
317           typename Alloc = tbb::tbb_allocator<iterator_alloc_pair_t<It>>,
318           typename = std::enable_if_t<is_input_iterator_v<It>>,
319           typename = std::enable_if_t<is_allocator_v<Alloc>>,
320           typename = std::enable_if_t<!is_allocator_v<Hash>>,
321           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
322           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
323 concurrent_unordered_multimap( It, It, std::size_t = {}, Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
324 -> concurrent_unordered_multimap<iterator_key_t<It>, iterator_mapped_t<It>, Hash, KeyEq, Alloc>;
325 
326 template <typename Key, typename T,
327           typename Hash = std::hash<std::remove_const_t<Key>>,
328           typename KeyEq = std::equal_to<std::remove_const_t<Key>>,
329           typename Alloc = tbb::tbb_allocator<std::pair<const Key, T>>,
330           typename = std::enable_if_t<is_allocator_v<Alloc>>,
331           typename = std::enable_if_t<!is_allocator_v<Hash>>,
332           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
333           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
334 concurrent_unordered_multimap( std::initializer_list<std::pair<Key, T>>, std::size_t = {},
335                                Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
336 -> concurrent_unordered_multimap<std::remove_const_t<Key>, T, Hash, KeyEq, Alloc>;
337 
338 template <typename It, typename Alloc,
339           typename = std::enable_if_t<is_input_iterator_v<It>>,
340           typename = std::enable_if_t<is_allocator_v<Alloc>>>
341 concurrent_unordered_multimap( It, It, std::size_t, Alloc )
342 -> concurrent_unordered_multimap<iterator_key_t<It>, iterator_mapped_t<It>,
343                                  std::hash<iterator_key_t<It>>,
344                                  std::equal_to<iterator_key_t<It>>, Alloc>;
345 
346 template <typename It, typename Hash, typename Alloc,
347           typename = std::enable_if_t<is_input_iterator_v<It>>,
348           typename = std::enable_if_t<is_allocator_v<Alloc>>,
349           typename = std::enable_if_t<!is_allocator_v<Hash>>,
350           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
351 concurrent_unordered_multimap( It, It, std::size_t, Hash, Alloc )
352 -> concurrent_unordered_multimap<iterator_key_t<It>, iterator_mapped_t<It>, Hash,
353                                  std::equal_to<iterator_key_t<It>>, Alloc>;
354 
355 template <typename Key, typename T, typename Alloc,
356           typename = std::enable_if_t<is_allocator_v<Alloc>>>
357 concurrent_unordered_multimap( std::initializer_list<std::pair<Key, T>>, std::size_t, Alloc )
358 -> concurrent_unordered_multimap<std::remove_const_t<Key>, T, std::hash<std::remove_const_t<Key>>,
359                                  std::equal_to<std::remove_const_t<Key>>, Alloc>;
360 
361 template <typename Key, typename T, typename Alloc,
362           typename = std::enable_if_t<is_allocator_v<Alloc>>>
363 concurrent_unordered_multimap( std::initializer_list<std::pair<Key, T>>, Alloc )
364 -> concurrent_unordered_multimap<std::remove_const_t<Key>, T, std::hash<std::remove_const_t<Key>>,
365                                  std::equal_to<std::remove_const_t<Key>>, Alloc>;
366 
367 template <typename Key, typename T, typename Hash, typename Alloc,
368           typename = std::enable_if_t<is_allocator_v<Alloc>>,
369           typename = std::enable_if_t<!is_allocator_v<Hash>>,
370           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
371 concurrent_unordered_multimap( std::initializer_list<std::pair<Key, T>>, std::size_t, Hash, Alloc )
372 -> concurrent_unordered_multimap<std::remove_const_t<Key>, T, Hash,
373                                  std::equal_to<std::remove_const_t<Key>>, Alloc>;
374 
375 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
376 
377 template <typename Key, typename T, typename Hash, typename KeyEqual, typename Allocator>
378 void swap( concurrent_unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& lhs,
379            concurrent_unordered_multimap<Key, T, Hash, KeyEqual, Allocator>& rhs ) {
380     lhs.swap(rhs);
381 }
382 
383 } // namespace d1
384 } // namespace detail
385 
386 inline namespace v1 {
387 
388 using detail::d1::concurrent_unordered_map;
389 using detail::d1::concurrent_unordered_multimap;
390 using detail::split;
391 
392 } // inline namespace v1
393 } // namespace tbb
394 
395 #endif // __TBB_concurrent_unordered_map_H
396