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 | |
25 | namespace tbb |
26 | { |
27 | |
28 | namespace interface5 { |
29 | |
30 | // Template class for hash map traits |
31 | template<typename Key, typename T, typename Hash_compare, typename Allocator, bool Allow_multimapping> |
32 | class concurrent_unordered_map_traits |
33 | { |
34 | protected: |
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 | |
58 | template<typename Key, typename T, typename Hasher, typename Key_equality, typename Allocator> |
59 | class concurrent_unordered_multimap; |
60 | |
61 | template <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> > > |
63 | class 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 |
72 | public: |
73 | #endif |
74 | using traits_type::allow_multimapping; |
75 | public: |
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 | |
261 | namespace internal { |
262 | using namespace tbb::internal; |
263 | |
264 | template<template<typename...> typename Map, typename Key, typename Element, typename... Args> |
265 | using 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 |
277 | template<typename I> |
278 | concurrent_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 |
282 | template<typename I, typename... Args> |
283 | concurrent_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 |
287 | template<typename Key, typename Element> |
288 | concurrent_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 |
292 | template<typename Key, typename Element, typename... Args> |
293 | concurrent_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 | |
298 | template < 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> > > |
300 | class 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 |
309 | public: |
310 | #endif |
311 | using traits_type::allow_multimapping; |
312 | public: |
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 |
459 | template<typename I> |
460 | concurrent_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 |
464 | template<typename I, typename... Args> |
465 | concurrent_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 |
469 | template<typename Key, typename Element> |
470 | concurrent_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 |
474 | template<typename Key, typename Element, typename... Args> |
475 | concurrent_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 | |
481 | using interface5::concurrent_unordered_map; |
482 | using interface5::concurrent_unordered_multimap; |
483 | |
484 | } // namespace tbb |
485 | |
486 | #endif// __TBB_concurrent_unordered_map_H |
487 | |