1 /*
2     Copyright (c) 2005-2021 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 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
167 
168 template <typename Key, typename Hash, typename KeyEqual, typename Allocator>
169 void swap( concurrent_unordered_set<Key, Hash, KeyEqual, Allocator>& lhs,
170            concurrent_unordered_set<Key, Hash, KeyEqual, Allocator>& rhs ) {
171     lhs.swap(rhs);
172 }
173 
174 template <typename Key, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>,
175           typename Allocator = tbb::tbb_allocator<Key>>
176 class concurrent_unordered_multiset
177     : public concurrent_unordered_base<concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, true>>
178 {
179     using traits_type = concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, true>;
180     using base_type = concurrent_unordered_base<traits_type>;
181 public:
182     using key_type = typename base_type::key_type;
183     using value_type = typename base_type::value_type;
184     using size_type = typename base_type::size_type;
185     using difference_type = typename base_type::difference_type;
186     using hasher = typename base_type::hasher;
187     using key_equal = typename base_type::key_equal;
188     using allocator_type = typename base_type::allocator_type;
189     using reference = typename base_type::reference;
190     using const_reference = typename base_type::const_reference;
191     using pointer = typename base_type::pointer;
192     using const_pointer = typename base_type::const_pointer;
193     using iterator = typename base_type::iterator;
194     using const_iterator = typename base_type::const_iterator;
195     using local_iterator = typename base_type::local_iterator;
196     using const_local_iterator = typename base_type::const_local_iterator;
197     using node_type = typename base_type::node_type;
198 
199     // Include constructors of base_type;
200     using base_type::base_type;
201 
202     // Required for implicit deduction guides
203     concurrent_unordered_multiset() = default;
204     concurrent_unordered_multiset( const concurrent_unordered_multiset& ) = default;
205     concurrent_unordered_multiset( const concurrent_unordered_multiset& other, const allocator_type& alloc ) : base_type(other, alloc) {}
206     concurrent_unordered_multiset( concurrent_unordered_multiset&& ) = default;
207     concurrent_unordered_multiset( concurrent_unordered_multiset&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
208     // Required to respect the rule of 5
209     concurrent_unordered_multiset& operator=( const concurrent_unordered_multiset& ) = default;
210     concurrent_unordered_multiset& operator=( concurrent_unordered_multiset&& ) = default;
211 
212     concurrent_unordered_multiset& operator=( std::initializer_list<value_type> il ) {
213         base_type::operator= (il);
214         return *this;
215     }
216 
217     template <typename OtherHash, typename OtherKeyEqual>
218     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
219         this->internal_merge(source);
220     }
221 
222     template <typename OtherHash, typename OtherKeyEqual>
223     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
224         this->internal_merge(std::move(source));
225     }
226 
227     template <typename OtherHash, typename OtherKeyEqual>
228     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
229         this->internal_merge(source);
230     }
231 
232     template <typename OtherHash, typename OtherKeyEqual>
233     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
234         this->internal_merge(std::move(source));
235     }
236 }; // class concurrent_unordered_multiset
237 
238 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
239 template <typename It,
240           typename Hash = std::hash<iterator_value_t<It>>,
241           typename KeyEq = std::equal_to<iterator_value_t<It>>,
242           typename Alloc = tbb::tbb_allocator<iterator_value_t<It>>,
243           typename = std::enable_if_t<is_input_iterator_v<It>>,
244           typename = std::enable_if_t<is_allocator_v<Alloc>>,
245           typename = std::enable_if_t<!is_allocator_v<Hash>>,
246           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
247           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
248 concurrent_unordered_multiset( It, It, std::size_t = {}, Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
249 -> concurrent_unordered_multiset<iterator_value_t<It>, Hash, KeyEq, Alloc>;
250 
251 template <typename T,
252           typename Hash = std::hash<T>,
253           typename KeyEq = std::equal_to<T>,
254           typename Alloc = tbb::tbb_allocator<T>,
255           typename = std::enable_if_t<is_allocator_v<Alloc>>,
256           typename = std::enable_if_t<!is_allocator_v<Hash>>,
257           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
258           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
259 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t = {},
260                           Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
261 -> concurrent_unordered_multiset<T, Hash, KeyEq, Alloc>;
262 
263 template <typename It, typename Alloc,
264           typename = std::enable_if_t<is_input_iterator_v<It>>,
265           typename = std::enable_if_t<is_allocator_v<Alloc>>>
266 concurrent_unordered_multiset( It, It, std::size_t, Alloc )
267 -> concurrent_unordered_multiset<iterator_value_t<It>, std::hash<iterator_value_t<It>>,
268                             std::equal_to<iterator_value_t<It>>, Alloc>;
269 
270 template <typename It, typename Hash, typename Alloc,
271           typename = std::enable_if_t<is_input_iterator_v<It>>,
272           typename = std::enable_if_t<is_allocator_v<Alloc>>,
273           typename = std::enable_if_t<!is_allocator_v<Hash>>,
274           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
275 concurrent_unordered_multiset( It, It, std::size_t, Hash, Alloc )
276 -> concurrent_unordered_multiset<iterator_value_t<It>, Hash, std::equal_to<iterator_value_t<It>>, Alloc>;
277 
278 template <typename T, typename Alloc,
279           typename = std::enable_if_t<is_allocator_v<Alloc>>>
280 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t, Alloc )
281 -> concurrent_unordered_multiset<T, std::hash<T>, std::equal_to<T>, Alloc>;
282 
283 template <typename T, typename Alloc,
284           typename = std::enable_if_t<is_allocator_v<Alloc>>>
285 concurrent_unordered_multiset( std::initializer_list<T>, Alloc )
286 -> concurrent_unordered_multiset<T, std::hash<T>, std::equal_to<T>, Alloc>;
287 
288 template <typename T, typename Hash, typename Alloc,
289           typename = std::enable_if_t<is_allocator_v<Alloc>>,
290           typename = std::enable_if_t<!is_allocator_v<Hash>>,
291           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
292 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t, Hash, Alloc )
293 -> concurrent_unordered_multiset<T, Hash, std::equal_to<T>, Alloc>;
294 
295 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
296 
297 template <typename Key, typename Hash, typename KeyEqual, typename Allocator>
298 void swap( concurrent_unordered_multiset<Key, Hash, KeyEqual, Allocator>& lhs,
299            concurrent_unordered_multiset<Key, Hash, KeyEqual, Allocator>& rhs ) {
300     lhs.swap(rhs);
301 }
302 
303 } // namespace d1
304 } // namespace detail
305 
306 inline namespace v1 {
307 
308 using detail::d1::concurrent_unordered_set;
309 using detail::d1::concurrent_unordered_multiset;
310 using detail::split;
311 
312 } // inline namespace v1
313 } // namespace tbb
314 
315 #endif // __TBB_concurrent_unordered_set_H
316