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
25namespace tbb
26{
27
28namespace interface5 {
29
30// Template class for hash set traits
31template<typename Key, typename Hash_compare, typename Allocator, bool Allow_multimapping>
32class concurrent_unordered_set_traits
33{
34protected:
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
57template<typename Key, typename Hasher, typename Key_equality, typename Allocator>
58class concurrent_unordered_multiset;
59
60template <typename Key, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>, typename Allocator = tbb::tbb_allocator<Key> >
61class 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
68public:
69#endif
70 using traits_type::allow_multimapping;
71public:
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
214namespace internal {
215using namespace tbb::internal;
216
217template <template<typename...> typename Set, typename T, typename... Args>
218using 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
230template<typename I>
231concurrent_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
235template<typename I, typename... Args>
236concurrent_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
240template<typename T>
241concurrent_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
245template<typename T, typename... Args>
246concurrent_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
251template <typename Key, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>,
252 typename Allocator = tbb::tbb_allocator<Key> >
253class 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
262public:
263#endif
264 using traits_type::allow_multimapping;
265public:
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
415template<typename I>
416concurrent_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
420template<typename I, typename... Args>
421concurrent_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
425template<typename T>
426concurrent_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
430template<typename T, typename... Args>
431concurrent_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
437using interface5::concurrent_unordered_set;
438using interface5::concurrent_unordered_multiset;
439
440} // namespace tbb
441
442#endif// __TBB_concurrent_unordered_set_H
443