1/*
2 Copyright (c) 2005-2019 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/* Container implementations in this header are based on PPL implementations
18 provided by Microsoft. */
19
20#ifndef __TBB_concurrent_unordered_map_H
21#define __TBB_concurrent_unordered_map_H
22
23#include "internal/_concurrent_unordered_impl.h"
24
25namespace tbb
26{
27
28namespace interface5 {
29
30// Template class for hash map traits
31template<typename Key, typename T, typename Hash_compare, typename Allocator, bool Allow_multimapping>
32class concurrent_unordered_map_traits
33{
34protected:
35 typedef std::pair<const Key, T> value_type;
36 typedef Key key_type;
37 typedef Hash_compare hash_compare;
38 typedef typename tbb::internal::allocator_rebind<Allocator, value_type>::type allocator_type;
39#if __TBB_UNORDERED_NODE_HANDLE_PRESENT
40 typedef tbb::internal::node_handle<key_type, value_type,
41 typename internal::split_ordered_list<value_type, allocator_type>::node,
42 allocator_type> node_type;
43#endif // __TBB_UNORDERED_NODE_HANDLE_PRESENT
44
45 enum { allow_multimapping = Allow_multimapping };
46
47 concurrent_unordered_map_traits() : my_hash_compare() {}
48 concurrent_unordered_map_traits(const hash_compare& hc) : my_hash_compare(hc) {}
49
50 template<class Type1, class Type2>
51 static const Key& get_key(const std::pair<Type1, Type2>& value) {
52 return (value.first);
53 }
54
55 hash_compare my_hash_compare; // the comparator predicate for keys
56};
57
58template<typename Key, typename T, typename Hasher, typename Key_equality, typename Allocator>
59class concurrent_unordered_multimap;
60
61template <typename Key, typename T, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>,
62 typename Allocator = tbb::tbb_allocator<std::pair<const Key, T> > >
63class concurrent_unordered_map :
64 public internal::concurrent_unordered_base< concurrent_unordered_map_traits<Key, T,
65 internal::hash_compare<Key, Hasher, Key_equality>, Allocator, false> >
66{
67 // Base type definitions
68 typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
69 typedef concurrent_unordered_map_traits<Key, T, hash_compare, Allocator, false> traits_type;
70 typedef internal::concurrent_unordered_base< traits_type > base_type;
71#if __TBB_EXTRA_DEBUG
72public:
73#endif
74 using traits_type::allow_multimapping;
75public:
76 using base_type::end;
77 using base_type::find;
78 using base_type::insert;
79
80 // Type definitions
81 typedef Key key_type;
82 typedef typename base_type::value_type value_type;
83 typedef T mapped_type;
84 typedef Hasher hasher;
85 typedef Key_equality key_equal;
86 typedef hash_compare key_compare;
87
88 typedef typename base_type::allocator_type allocator_type;
89 typedef typename base_type::pointer pointer;
90 typedef typename base_type::const_pointer const_pointer;
91 typedef typename base_type::reference reference;
92 typedef typename base_type::const_reference const_reference;
93
94 typedef typename base_type::size_type size_type;
95 typedef typename base_type::difference_type difference_type;
96
97 typedef typename base_type::iterator iterator;
98 typedef typename base_type::const_iterator const_iterator;
99 typedef typename base_type::iterator local_iterator;
100 typedef typename base_type::const_iterator const_local_iterator;
101#if __TBB_UNORDERED_NODE_HANDLE_PRESENT
102 typedef typename base_type::node_type node_type;
103#endif // __TBB_UNORDERED_NODE_HANDLE_PRESENT
104
105 // Construction/destruction/copying
106 explicit concurrent_unordered_map(size_type n_of_buckets = base_type::initial_bucket_number,
107 const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
108 const allocator_type& a = allocator_type())
109 : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
110 {}
111
112 concurrent_unordered_map(size_type n_of_buckets, const allocator_type& a)
113 : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
114 {}
115
116 concurrent_unordered_map(size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
117 : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
118 {}
119
120 explicit concurrent_unordered_map(const Allocator& a) : base_type(base_type::initial_bucket_number, key_compare(), a)
121 {}
122
123 template <typename Iterator>
124 concurrent_unordered_map(Iterator first, Iterator last, size_type n_of_buckets = base_type::initial_bucket_number,
125 const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
126 const allocator_type& a = allocator_type())
127 : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
128 {
129 insert(first, last);
130 }
131
132 template <typename Iterator>
133 concurrent_unordered_map(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type& a)
134 : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
135 {
136 insert(first, last);
137 }
138
139 template <typename Iterator>
140 concurrent_unordered_map(Iterator first, Iterator last, size_type n_of_buckets, const hasher& a_hasher,
141 const allocator_type& a)
142 : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
143 {
144 insert(first, last);
145 }
146
147#if __TBB_INITIALIZER_LISTS_PRESENT
148 //! Constructor from initializer_list
149 concurrent_unordered_map(std::initializer_list<value_type> il, size_type n_of_buckets = base_type::initial_bucket_number,
150 const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
151 const allocator_type& a = allocator_type())
152 : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
153 {
154 insert(il.begin(),il.end());
155 }
156
157 concurrent_unordered_map(std::initializer_list<value_type> il, size_type n_of_buckets, const allocator_type& a)
158 : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
159 {
160 insert(il.begin(), il.end());
161 }
162
163 concurrent_unordered_map(std::initializer_list<value_type> il, size_type n_of_buckets, const hasher& a_hasher,
164 const allocator_type& a)
165 : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
166 {
167 insert(il.begin(), il.end());
168 }
169
170#endif //# __TBB_INITIALIZER_LISTS_PRESENT
171
172
173#if __TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
174 concurrent_unordered_map(const concurrent_unordered_map& table)
175 : base_type(table)
176 {}
177
178 concurrent_unordered_map& operator=(const concurrent_unordered_map& table)
179 {
180 return static_cast<concurrent_unordered_map&>(base_type::operator=(table));
181 }
182
183 concurrent_unordered_map(concurrent_unordered_map&& table)
184 : base_type(std::move(table))
185 {}
186
187 concurrent_unordered_map& operator=(concurrent_unordered_map&& table)
188 {
189 return static_cast<concurrent_unordered_map&>(base_type::operator=(std::move(table)));
190 }
191#endif //__TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
192
193#if __TBB_CPP11_RVALUE_REF_PRESENT
194 concurrent_unordered_map(concurrent_unordered_map&& table, const Allocator& a) : base_type(std::move(table), a)
195 {}
196#endif /*__TBB_CPP11_RVALUE_REF_PRESENT*/
197
198#if __TBB_UNORDERED_NODE_HANDLE_PRESENT
199 template<typename Hash, typename Equality>
200 void merge(concurrent_unordered_map<Key, T, Hash, Equality, Allocator>& source)
201 { this->internal_merge(source); }
202
203 template<typename Hash, typename Equality>
204 void merge(concurrent_unordered_map<Key, T, Hash, Equality, Allocator>&& source)
205 { this->internal_merge(source); }
206
207 template<typename Hash, typename Equality>
208 void merge(concurrent_unordered_multimap<Key, T, Hash, Equality, Allocator>& source)
209 { this->internal_merge(source); }
210
211 template<typename Hash, typename Equality>
212 void merge(concurrent_unordered_multimap<Key, T, Hash, Equality, Allocator>&& source)
213 { this->internal_merge(source); }
214
215#endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
216
217 concurrent_unordered_map(const concurrent_unordered_map& table, const Allocator& a)
218 : base_type(table, a)
219 {}
220
221 // Observers
222 mapped_type& operator[](const key_type& key)
223 {
224 iterator where = find(key);
225
226 if (where == end())
227 {
228 where = insert(std::pair<key_type, mapped_type>(key, mapped_type())).first;
229 }
230
231 return ((*where).second);
232 }
233
234 mapped_type& at(const key_type& key)
235 {
236 iterator where = find(key);
237
238 if (where == end())
239 {
240 tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
241 }
242
243 return ((*where).second);
244 }
245
246 const mapped_type& at(const key_type& key) const
247 {
248 const_iterator where = find(key);
249
250 if (where == end())
251 {
252 tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
253 }
254
255 return ((*where).second);
256 }
257};
258
259#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
260
261namespace internal {
262using namespace tbb::internal;
263
264template<template<typename...> typename Map, typename Key, typename Element, typename... Args>
265using cu_map_t = Map<
266 Key, Element,
267 std::conditional_t< (sizeof...(Args)>0) && !is_allocator_v< pack_element_t<0, Args...> >,
268 pack_element_t<0, Args...>, tbb_hash<Key> >,
269 std::conditional_t< (sizeof...(Args)>1) && !is_allocator_v< pack_element_t<1, Args...> >,
270 pack_element_t<1, Args...>, std::equal_to<Key> >,
271 std::conditional_t< (sizeof...(Args)>0) && is_allocator_v< pack_element_t<sizeof...(Args)-1, Args...> >,
272 pack_element_t<sizeof...(Args)-1, Args...>, tbb_allocator<std::pair<const Key, Element> > >
273>;
274}
275
276// Deduction guide for the constructor from two iterators
277template<typename I>
278concurrent_unordered_map (I, I)
279-> internal::cu_map_t<concurrent_unordered_map, internal::iterator_key_t<I>, internal::iterator_mapped_t<I>>;
280
281// Deduction guide for the constructor from two iterators and hasher/equality/allocator
282template<typename I, typename... Args>
283concurrent_unordered_map(I, I, size_t, Args...)
284-> internal::cu_map_t<concurrent_unordered_map, internal::iterator_key_t<I>, internal::iterator_mapped_t<I>, Args...>;
285
286// Deduction guide for the constructor from an initializer_list
287template<typename Key, typename Element>
288concurrent_unordered_map(std::initializer_list<std::pair<const Key, Element>>)
289-> internal::cu_map_t<concurrent_unordered_map, Key, Element>;
290
291// Deduction guide for the constructor from an initializer_list and hasher/equality/allocator
292template<typename Key, typename Element, typename... Args>
293concurrent_unordered_map(std::initializer_list<std::pair<const Key, Element>>, size_t, Args...)
294-> internal::cu_map_t<concurrent_unordered_map, Key, Element, Args...>;
295
296#endif /* __TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
297
298template < typename Key, typename T, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>,
299 typename Allocator = tbb::tbb_allocator<std::pair<const Key, T> > >
300class concurrent_unordered_multimap :
301 public internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T,
302 internal::hash_compare<Key, Hasher, Key_equality>, Allocator, true> >
303{
304 // Base type definitions
305 typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
306 typedef concurrent_unordered_map_traits<Key, T, hash_compare, Allocator, true> traits_type;
307 typedef internal::concurrent_unordered_base<traits_type> base_type;
308#if __TBB_EXTRA_DEBUG
309public:
310#endif
311 using traits_type::allow_multimapping;
312public:
313 using base_type::insert;
314
315 // Type definitions
316 typedef Key key_type;
317 typedef typename base_type::value_type value_type;
318 typedef T mapped_type;
319 typedef Hasher hasher;
320 typedef Key_equality key_equal;
321 typedef hash_compare key_compare;
322
323 typedef typename base_type::allocator_type allocator_type;
324 typedef typename base_type::pointer pointer;
325 typedef typename base_type::const_pointer const_pointer;
326 typedef typename base_type::reference reference;
327 typedef typename base_type::const_reference const_reference;
328
329 typedef typename base_type::size_type size_type;
330 typedef typename base_type::difference_type difference_type;
331
332 typedef typename base_type::iterator iterator;
333 typedef typename base_type::const_iterator const_iterator;
334 typedef typename base_type::iterator local_iterator;
335 typedef typename base_type::const_iterator const_local_iterator;
336#if __TBB_UNORDERED_NODE_HANDLE_PRESENT
337 typedef typename base_type::node_type node_type;
338#endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
339
340 // Construction/destruction/copying
341 explicit concurrent_unordered_multimap(size_type n_of_buckets = base_type::initial_bucket_number,
342 const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
343 const allocator_type& a = allocator_type())
344 : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
345 {}
346
347 concurrent_unordered_multimap(size_type n_of_buckets, const allocator_type& a)
348 : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
349 {}
350
351 concurrent_unordered_multimap(size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
352 : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
353 {}
354
355 explicit concurrent_unordered_multimap(const Allocator& a) : base_type(base_type::initial_bucket_number, key_compare(), a)
356 {}
357
358 template <typename Iterator>
359 concurrent_unordered_multimap(Iterator first, Iterator last, size_type n_of_buckets = base_type::initial_bucket_number,
360 const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
361 const allocator_type& a = allocator_type())
362 : base_type(n_of_buckets,key_compare(a_hasher,a_keyeq), a)
363 {
364 insert(first, last);
365 }
366
367 template <typename Iterator>
368 concurrent_unordered_multimap(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type& a)
369 : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
370 {
371 insert(first, last);
372 }
373
374 template <typename Iterator>
375 concurrent_unordered_multimap(Iterator first, Iterator last, size_type n_of_buckets, const hasher& a_hasher,
376 const allocator_type& a)
377 : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
378 {
379 insert(first, last);
380 }
381
382#if __TBB_INITIALIZER_LISTS_PRESENT
383 //! Constructor from initializer_list
384 concurrent_unordered_multimap(std::initializer_list<value_type> il, size_type n_of_buckets = base_type::initial_bucket_number,
385 const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
386 const allocator_type& a = allocator_type())
387 : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
388 {
389 insert(il.begin(),il.end());
390 }
391
392 concurrent_unordered_multimap(std::initializer_list<value_type> il, size_type n_of_buckets, const allocator_type& a)
393 : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
394 {
395 insert(il.begin(), il.end());
396 }
397
398 concurrent_unordered_multimap(std::initializer_list<value_type> il, size_type n_of_buckets, const hasher& a_hasher,
399 const allocator_type& a)
400 : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
401 {
402 insert(il.begin(), il.end());
403 }
404
405#endif //# __TBB_INITIALIZER_LISTS_PRESENT
406
407#if __TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
408 concurrent_unordered_multimap(const concurrent_unordered_multimap& table)
409 : base_type(table)
410 {}
411
412 concurrent_unordered_multimap& operator=(const concurrent_unordered_multimap& table)
413 {
414 return static_cast<concurrent_unordered_multimap&>(base_type::operator=(table));
415 }
416
417 concurrent_unordered_multimap(concurrent_unordered_multimap&& table)
418 : base_type(std::move(table))
419 {}
420
421 concurrent_unordered_multimap& operator=(concurrent_unordered_multimap&& table)
422 {
423 return static_cast<concurrent_unordered_multimap&>(base_type::operator=(std::move(table)));
424 }
425#endif //__TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
426
427#if __TBB_CPP11_RVALUE_REF_PRESENT
428 concurrent_unordered_multimap(concurrent_unordered_multimap&& table, const Allocator& a) : base_type(std::move(table), a)
429 {}
430#endif /*__TBB_CPP11_RVALUE_REF_PRESENT*/
431
432#if __TBB_UNORDERED_NODE_HANDLE_PRESENT
433 template<typename Hash, typename Equality>
434 void merge(concurrent_unordered_map<Key, T, Hash, Equality, Allocator>& source)
435 { this->internal_merge(source); }
436
437 template<typename Hash, typename Equality>
438 void merge(concurrent_unordered_map<Key, T, Hash, Equality, Allocator>&& source)
439 { this->internal_merge(source); }
440
441 template<typename Hash, typename Equality>
442 void merge(concurrent_unordered_multimap<Key, T, Hash, Equality, Allocator>& source)
443 { this->internal_merge(source); }
444
445 template<typename Hash, typename Equality>
446 void merge(concurrent_unordered_multimap<Key, T, Hash, Equality, Allocator>&& source)
447 { this->internal_merge(source); }
448
449#endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
450
451 concurrent_unordered_multimap(const concurrent_unordered_multimap& table, const Allocator& a)
452 : base_type(table, a)
453 {}
454};
455
456#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
457
458// Deduction guide for the constructor from two iterators
459template<typename I>
460concurrent_unordered_multimap (I, I)
461-> internal::cu_map_t<concurrent_unordered_multimap, internal::iterator_key_t<I>, internal::iterator_mapped_t<I>>;
462
463// Deduction guide for the constructor from two iterators and hasher/equality/allocator
464template<typename I, typename... Args>
465concurrent_unordered_multimap(I, I, size_t, Args...)
466-> internal::cu_map_t<concurrent_unordered_multimap, internal::iterator_key_t<I>, internal::iterator_mapped_t<I>, Args...>;
467
468// Deduction guide for the constructor from an initializer_list
469template<typename Key, typename Element>
470concurrent_unordered_multimap(std::initializer_list<std::pair<const Key, Element>>)
471-> internal::cu_map_t<concurrent_unordered_multimap, Key, Element>;
472
473// Deduction guide for the constructor from an initializer_list and hasher/equality/allocator
474template<typename Key, typename Element, typename... Args>
475concurrent_unordered_multimap(std::initializer_list<std::pair<const Key, Element>>, size_t, Args...)
476-> internal::cu_map_t<concurrent_unordered_multimap, Key, Element, Args...>;
477
478#endif /* __TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
479} // namespace interface5
480
481using interface5::concurrent_unordered_map;
482using interface5::concurrent_unordered_multimap;
483
484} // namespace tbb
485
486#endif// __TBB_concurrent_unordered_map_H
487