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