1 /*
2     Copyright (c) 2005-2022 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_set_H
18 #define __TBB_concurrent_unordered_set_H
19 
20 #include "detail/_namespace_injection.h"
21 #include "detail/_concurrent_unordered_base.h"
22 #include "tbb_allocator.h"
23 
24 namespace tbb {
25 namespace detail {
26 namespace d1 {
27 
28 template <typename Key, typename Hash, typename KeyEqual, typename Allocator, bool AllowMultimapping>
29 struct concurrent_unordered_set_traits {
30     using key_type = Key;
31     using value_type = key_type;
32     using allocator_type = Allocator;
33     using hash_compare_type = hash_compare<key_type, Hash, KeyEqual>;
34     static constexpr bool allow_multimapping = AllowMultimapping;
35 
36     static constexpr const key_type& get_key( const value_type& value ) {
37         return value;
38     }
39 }; // class concurrent_unordered_set_traits
40 
41 template <typename Key, typename Hash, typename KeyEqual, typename Allocator>
42 class concurrent_unordered_multiset;
43 
44 template <typename Key, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>,
45           typename Allocator = tbb::tbb_allocator<Key>>
46 class concurrent_unordered_set
47     : public concurrent_unordered_base<concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, false>>
48 {
49     using traits_type = concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, false>;
50     using base_type = concurrent_unordered_base<traits_type>;
51 public:
52     using key_type = typename base_type::key_type;
53     using value_type = typename base_type::value_type;
54     using size_type = typename base_type::size_type;
55     using difference_type = typename base_type::difference_type;
56     using hasher = typename base_type::hasher;
57     using key_equal = typename base_type::key_equal;
58     using allocator_type = typename base_type::allocator_type;
59     using reference = typename base_type::reference;
60     using const_reference = typename base_type::const_reference;
61     using pointer = typename base_type::pointer;
62     using const_pointer = typename base_type::const_pointer;
63     using iterator = typename base_type::iterator;
64     using const_iterator = typename base_type::const_iterator;
65     using local_iterator = typename base_type::local_iterator;
66     using const_local_iterator = typename base_type::const_local_iterator;
67     using node_type = typename base_type::node_type;
68 
69     // Include constructors of base_type;
70     using base_type::base_type;
71 
72     // Required for implicit deduction guides
73     concurrent_unordered_set() = default;
74     concurrent_unordered_set( const concurrent_unordered_set& ) = default;
75     concurrent_unordered_set( const concurrent_unordered_set& other, const allocator_type& alloc ) : base_type(other, alloc) {}
76     concurrent_unordered_set( concurrent_unordered_set&& ) = default;
77     concurrent_unordered_set( concurrent_unordered_set&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
78     // Required to respect the rule of 5
79     concurrent_unordered_set& operator=( const concurrent_unordered_set& ) = default;
80     concurrent_unordered_set& operator=( concurrent_unordered_set&& ) = default;
81 
82     concurrent_unordered_set& operator=( std::initializer_list<value_type> il ) {
83         base_type::operator= (il);
84         return *this;
85     }
86 
87     template <typename OtherHash, typename OtherKeyEqual>
88     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
89         this->internal_merge(source);
90     }
91 
92     template <typename OtherHash, typename OtherKeyEqual>
93     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
94         this->internal_merge(std::move(source));
95     }
96 
97     template <typename OtherHash, typename OtherKeyEqual>
98     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
99         this->internal_merge(source);
100     }
101 
102     template <typename OtherHash, typename OtherKeyEqual>
103     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
104         this->internal_merge(std::move(source));
105     }
106 }; // class concurrent_unordered_set
107 
108 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
109 
110 template <typename It,
111           typename Hash = std::hash<iterator_value_t<It>>,
112           typename KeyEq = std::equal_to<iterator_value_t<It>>,
113           typename Alloc = tbb::tbb_allocator<iterator_value_t<It>>,
114           typename = std::enable_if_t<is_input_iterator_v<It>>,
115           typename = std::enable_if_t<is_allocator_v<Alloc>>,
116           typename = std::enable_if_t<!is_allocator_v<Hash>>,
117           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
118           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
119 concurrent_unordered_set( It, It, std::size_t = {}, Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
120 -> concurrent_unordered_set<iterator_value_t<It>, Hash, KeyEq, Alloc>;
121 
122 template <typename T,
123           typename Hash = std::hash<T>,
124           typename KeyEq = std::equal_to<T>,
125           typename Alloc = tbb::tbb_allocator<T>,
126           typename = std::enable_if_t<is_allocator_v<Alloc>>,
127           typename = std::enable_if_t<!is_allocator_v<Hash>>,
128           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
129           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
130 concurrent_unordered_set( std::initializer_list<T>, std::size_t = {},
131                           Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
132 -> concurrent_unordered_set<T, Hash, KeyEq, Alloc>;
133 
134 template <typename It, typename Alloc,
135           typename = std::enable_if_t<is_input_iterator_v<It>>,
136           typename = std::enable_if_t<is_allocator_v<Alloc>>>
137 concurrent_unordered_set( It, It, std::size_t, Alloc )
138 -> concurrent_unordered_set<iterator_value_t<It>, std::hash<iterator_value_t<It>>,
139                             std::equal_to<iterator_value_t<It>>, Alloc>;
140 
141 template <typename It, typename Hash, typename Alloc,
142           typename = std::enable_if_t<is_input_iterator_v<It>>,
143           typename = std::enable_if_t<is_allocator_v<Alloc>>,
144           typename = std::enable_if_t<!is_allocator_v<Hash>>,
145           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
146 concurrent_unordered_set( It, It, std::size_t, Hash, Alloc )
147 -> concurrent_unordered_set<iterator_value_t<It>, Hash, std::equal_to<iterator_value_t<It>>, Alloc>;
148 
149 template <typename T, typename Alloc,
150           typename = std::enable_if_t<is_allocator_v<Alloc>>>
151 concurrent_unordered_set( std::initializer_list<T>, std::size_t, Alloc )
152 -> concurrent_unordered_set<T, std::hash<T>, std::equal_to<T>, Alloc>;
153 
154 template <typename T, typename Alloc,
155           typename = std::enable_if_t<is_allocator_v<Alloc>>>
156 concurrent_unordered_set( std::initializer_list<T>, Alloc )
157 -> concurrent_unordered_set<T, std::hash<T>, std::equal_to<T>, Alloc>;
158 
159 template <typename T, typename Hash, typename Alloc,
160           typename = std::enable_if_t<is_allocator_v<Alloc>>,
161           typename = std::enable_if_t<!is_allocator_v<Hash>>,
162           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
163 concurrent_unordered_set( std::initializer_list<T>, std::size_t, Hash, Alloc )
164 -> concurrent_unordered_set<T, Hash, std::equal_to<T>, Alloc>;
165 
166 #if __APPLE__ && __TBB_CLANG_VERSION == 100000
167 // An explicit deduction guide is required for copy/move constructor with allocator for APPLE LLVM 10.0.0
168 // due to an issue with generating an implicit deduction guide for these constructors under several strange surcumstances.
169 // Currently the issue takes place because the last template parameter for Traits is boolean, it should not affect the deduction guides
170 // The issue reproduces only on this version of the compiler
171 template <typename T, typename Hash, typename KeyEq, typename Alloc>
172 concurrent_unordered_set( concurrent_unordered_set<T, Hash, KeyEq, Alloc>, Alloc )
173 -> concurrent_unordered_set<T, Hash, KeyEq, Alloc>;
174 #endif
175 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
176 
177 template <typename Key, typename Hash, typename KeyEqual, typename Allocator>
178 void swap( concurrent_unordered_set<Key, Hash, KeyEqual, Allocator>& lhs,
179            concurrent_unordered_set<Key, Hash, KeyEqual, Allocator>& rhs ) {
180     lhs.swap(rhs);
181 }
182 
183 template <typename Key, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>,
184           typename Allocator = tbb::tbb_allocator<Key>>
185 class concurrent_unordered_multiset
186     : public concurrent_unordered_base<concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, true>>
187 {
188     using traits_type = concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, true>;
189     using base_type = concurrent_unordered_base<traits_type>;
190 public:
191     using key_type = typename base_type::key_type;
192     using value_type = typename base_type::value_type;
193     using size_type = typename base_type::size_type;
194     using difference_type = typename base_type::difference_type;
195     using hasher = typename base_type::hasher;
196     using key_equal = typename base_type::key_equal;
197     using allocator_type = typename base_type::allocator_type;
198     using reference = typename base_type::reference;
199     using const_reference = typename base_type::const_reference;
200     using pointer = typename base_type::pointer;
201     using const_pointer = typename base_type::const_pointer;
202     using iterator = typename base_type::iterator;
203     using const_iterator = typename base_type::const_iterator;
204     using local_iterator = typename base_type::local_iterator;
205     using const_local_iterator = typename base_type::const_local_iterator;
206     using node_type = typename base_type::node_type;
207 
208     // Include constructors of base_type;
209     using base_type::base_type;
210 
211     // Required for implicit deduction guides
212     concurrent_unordered_multiset() = default;
213     concurrent_unordered_multiset( const concurrent_unordered_multiset& ) = default;
214     concurrent_unordered_multiset( const concurrent_unordered_multiset& other, const allocator_type& alloc ) : base_type(other, alloc) {}
215     concurrent_unordered_multiset( concurrent_unordered_multiset&& ) = default;
216     concurrent_unordered_multiset( concurrent_unordered_multiset&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
217     // Required to respect the rule of 5
218     concurrent_unordered_multiset& operator=( const concurrent_unordered_multiset& ) = default;
219     concurrent_unordered_multiset& operator=( concurrent_unordered_multiset&& ) = default;
220 
221     concurrent_unordered_multiset& operator=( std::initializer_list<value_type> il ) {
222         base_type::operator= (il);
223         return *this;
224     }
225 
226     template <typename OtherHash, typename OtherKeyEqual>
227     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
228         this->internal_merge(source);
229     }
230 
231     template <typename OtherHash, typename OtherKeyEqual>
232     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
233         this->internal_merge(std::move(source));
234     }
235 
236     template <typename OtherHash, typename OtherKeyEqual>
237     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
238         this->internal_merge(source);
239     }
240 
241     template <typename OtherHash, typename OtherKeyEqual>
242     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
243         this->internal_merge(std::move(source));
244     }
245 }; // class concurrent_unordered_multiset
246 
247 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
248 template <typename It,
249           typename Hash = std::hash<iterator_value_t<It>>,
250           typename KeyEq = std::equal_to<iterator_value_t<It>>,
251           typename Alloc = tbb::tbb_allocator<iterator_value_t<It>>,
252           typename = std::enable_if_t<is_input_iterator_v<It>>,
253           typename = std::enable_if_t<is_allocator_v<Alloc>>,
254           typename = std::enable_if_t<!is_allocator_v<Hash>>,
255           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
256           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
257 concurrent_unordered_multiset( It, It, std::size_t = {}, Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
258 -> concurrent_unordered_multiset<iterator_value_t<It>, Hash, KeyEq, Alloc>;
259 
260 template <typename T,
261           typename Hash = std::hash<T>,
262           typename KeyEq = std::equal_to<T>,
263           typename Alloc = tbb::tbb_allocator<T>,
264           typename = std::enable_if_t<is_allocator_v<Alloc>>,
265           typename = std::enable_if_t<!is_allocator_v<Hash>>,
266           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
267           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
268 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t = {},
269                           Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
270 -> concurrent_unordered_multiset<T, Hash, KeyEq, Alloc>;
271 
272 template <typename It, typename Alloc,
273           typename = std::enable_if_t<is_input_iterator_v<It>>,
274           typename = std::enable_if_t<is_allocator_v<Alloc>>>
275 concurrent_unordered_multiset( It, It, std::size_t, Alloc )
276 -> concurrent_unordered_multiset<iterator_value_t<It>, std::hash<iterator_value_t<It>>,
277                             std::equal_to<iterator_value_t<It>>, Alloc>;
278 
279 template <typename It, typename Hash, typename Alloc,
280           typename = std::enable_if_t<is_input_iterator_v<It>>,
281           typename = std::enable_if_t<is_allocator_v<Alloc>>,
282           typename = std::enable_if_t<!is_allocator_v<Hash>>,
283           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
284 concurrent_unordered_multiset( It, It, std::size_t, Hash, Alloc )
285 -> concurrent_unordered_multiset<iterator_value_t<It>, Hash, std::equal_to<iterator_value_t<It>>, Alloc>;
286 
287 template <typename T, typename Alloc,
288           typename = std::enable_if_t<is_allocator_v<Alloc>>>
289 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t, Alloc )
290 -> concurrent_unordered_multiset<T, std::hash<T>, std::equal_to<T>, Alloc>;
291 
292 template <typename T, typename Alloc,
293           typename = std::enable_if_t<is_allocator_v<Alloc>>>
294 concurrent_unordered_multiset( std::initializer_list<T>, Alloc )
295 -> concurrent_unordered_multiset<T, std::hash<T>, std::equal_to<T>, Alloc>;
296 
297 template <typename T, typename Hash, typename Alloc,
298           typename = std::enable_if_t<is_allocator_v<Alloc>>,
299           typename = std::enable_if_t<!is_allocator_v<Hash>>,
300           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
301 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t, Hash, Alloc )
302 -> concurrent_unordered_multiset<T, Hash, std::equal_to<T>, Alloc>;
303 
304 #if __APPLE__ && __TBB_CLANG_VERSION == 100000
305 // An explicit deduction guide is required for copy/move constructor with allocator for APPLE LLVM 10.0.0
306 // due to an issue with generating an implicit deduction guide for these constructors under several strange surcumstances.
307 // Currently the issue takes place because the last template parameter for Traits is boolean, it should not affect the deduction guides
308 // The issue reproduces only on this version of the compiler
309 template <typename T, typename Hash, typename KeyEq, typename Alloc>
310 concurrent_unordered_multiset( concurrent_unordered_multiset<T, Hash, KeyEq, Alloc>, Alloc )
311 -> concurrent_unordered_multiset<T, Hash, KeyEq, Alloc>;
312 #endif
313 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
314 
315 template <typename Key, typename Hash, typename KeyEqual, typename Allocator>
316 void swap( concurrent_unordered_multiset<Key, Hash, KeyEqual, Allocator>& lhs,
317            concurrent_unordered_multiset<Key, Hash, KeyEqual, Allocator>& rhs ) {
318     lhs.swap(rhs);
319 }
320 
321 } // namespace d1
322 } // namespace detail
323 
324 inline namespace v1 {
325 
326 using detail::d1::concurrent_unordered_set;
327 using detail::d1::concurrent_unordered_multiset;
328 using detail::split;
329 
330 } // inline namespace v1
331 } // namespace tbb
332 
333 #endif // __TBB_concurrent_unordered_set_H
334