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     using base_type::operator=;
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     template <typename OtherHash, typename OtherKeyEqual>
83     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
84         this->internal_merge(source);
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(std::move(source));
90     }
91 
92     template <typename OtherHash, typename OtherKeyEqual>
93     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
94         this->internal_merge(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(std::move(source));
100     }
101 }; // class concurrent_unordered_set
102 
103 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
104 
105 template <typename It,
106           typename Hash = std::hash<iterator_value_t<It>>,
107           typename KeyEq = std::equal_to<iterator_value_t<It>>,
108           typename Alloc = tbb::tbb_allocator<iterator_value_t<It>>,
109           typename = std::enable_if_t<is_input_iterator_v<It>>,
110           typename = std::enable_if_t<is_allocator_v<Alloc>>,
111           typename = std::enable_if_t<!is_allocator_v<Hash>>,
112           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
113           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
114 concurrent_unordered_set( It, It, std::size_t = {}, Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
115 -> concurrent_unordered_set<iterator_value_t<It>, Hash, KeyEq, Alloc>;
116 
117 template <typename T,
118           typename Hash = std::hash<T>,
119           typename KeyEq = std::equal_to<T>,
120           typename Alloc = tbb::tbb_allocator<T>,
121           typename = std::enable_if_t<is_allocator_v<Alloc>>,
122           typename = std::enable_if_t<!is_allocator_v<Hash>>,
123           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
124           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
125 concurrent_unordered_set( std::initializer_list<T>, std::size_t = {},
126                           Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
127 -> concurrent_unordered_set<T, Hash, KeyEq, Alloc>;
128 
129 template <typename It, typename Alloc,
130           typename = std::enable_if_t<is_input_iterator_v<It>>,
131           typename = std::enable_if_t<is_allocator_v<Alloc>>>
132 concurrent_unordered_set( It, It, std::size_t, Alloc )
133 -> concurrent_unordered_set<iterator_value_t<It>, std::hash<iterator_value_t<It>>,
134                             std::equal_to<iterator_value_t<It>>, Alloc>;
135 
136 template <typename It, typename Hash, typename Alloc,
137           typename = std::enable_if_t<is_input_iterator_v<It>>,
138           typename = std::enable_if_t<is_allocator_v<Alloc>>,
139           typename = std::enable_if_t<!is_allocator_v<Hash>>,
140           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
141 concurrent_unordered_set( It, It, std::size_t, Hash, Alloc )
142 -> concurrent_unordered_set<iterator_value_t<It>, Hash, std::equal_to<iterator_value_t<It>>, Alloc>;
143 
144 template <typename T, typename Alloc,
145           typename = std::enable_if_t<is_allocator_v<Alloc>>>
146 concurrent_unordered_set( std::initializer_list<T>, std::size_t, Alloc )
147 -> concurrent_unordered_set<T, std::hash<T>, std::equal_to<T>, 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>, Alloc )
152 -> concurrent_unordered_set<T, std::hash<T>, std::equal_to<T>, Alloc>;
153 
154 template <typename T, typename Hash, typename Alloc,
155           typename = std::enable_if_t<is_allocator_v<Alloc>>,
156           typename = std::enable_if_t<!is_allocator_v<Hash>>,
157           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
158 concurrent_unordered_set( std::initializer_list<T>, std::size_t, Hash, Alloc )
159 -> concurrent_unordered_set<T, Hash, std::equal_to<T>, Alloc>;
160 
161 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
162 
163 template <typename Key, typename Hash, typename KeyEqual, typename Allocator>
164 void swap( concurrent_unordered_set<Key, Hash, KeyEqual, Allocator>& lhs,
165            concurrent_unordered_set<Key, Hash, KeyEqual, Allocator>& rhs ) {
166     lhs.swap(rhs);
167 }
168 
169 template <typename Key, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>,
170           typename Allocator = tbb::tbb_allocator<Key>>
171 class concurrent_unordered_multiset
172     : public concurrent_unordered_base<concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, true>>
173 {
174     using traits_type = concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, true>;
175     using base_type = concurrent_unordered_base<traits_type>;
176 public:
177     using key_type = typename base_type::key_type;
178     using value_type = typename base_type::value_type;
179     using size_type = typename base_type::size_type;
180     using difference_type = typename base_type::difference_type;
181     using hasher = typename base_type::hasher;
182     using key_equal = typename base_type::key_equal;
183     using allocator_type = typename base_type::allocator_type;
184     using reference = typename base_type::reference;
185     using const_reference = typename base_type::const_reference;
186     using pointer = typename base_type::pointer;
187     using const_pointer = typename base_type::const_pointer;
188     using iterator = typename base_type::iterator;
189     using const_iterator = typename base_type::const_iterator;
190     using local_iterator = typename base_type::local_iterator;
191     using const_local_iterator = typename base_type::const_local_iterator;
192     using node_type = typename base_type::node_type;
193 
194     // Include constructors of base_type;
195     using base_type::base_type;
196     using base_type::operator=;
197 
198     // Required for implicit deduction guides
199     concurrent_unordered_multiset() = default;
200     concurrent_unordered_multiset( const concurrent_unordered_multiset& ) = default;
201     concurrent_unordered_multiset( const concurrent_unordered_multiset& other, const allocator_type& alloc ) : base_type(other, alloc) {}
202     concurrent_unordered_multiset( concurrent_unordered_multiset&& ) = default;
203     concurrent_unordered_multiset( concurrent_unordered_multiset&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
204     // Required to respect the rule of 5
205     concurrent_unordered_multiset& operator=( const concurrent_unordered_multiset& ) = default;
206     concurrent_unordered_multiset& operator=( concurrent_unordered_multiset&& ) = default;
207 
208     template <typename OtherHash, typename OtherKeyEqual>
209     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
210         this->internal_merge(source);
211     }
212 
213     template <typename OtherHash, typename OtherKeyEqual>
214     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
215         this->internal_merge(std::move(source));
216     }
217 
218     template <typename OtherHash, typename OtherKeyEqual>
219     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
220         this->internal_merge(source);
221     }
222 
223     template <typename OtherHash, typename OtherKeyEqual>
224     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
225         this->internal_merge(std::move(source));
226     }
227 }; // class concurrent_unordered_multiset
228 
229 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
230 template <typename It,
231           typename Hash = std::hash<iterator_value_t<It>>,
232           typename KeyEq = std::equal_to<iterator_value_t<It>>,
233           typename Alloc = tbb::tbb_allocator<iterator_value_t<It>>,
234           typename = std::enable_if_t<is_input_iterator_v<It>>,
235           typename = std::enable_if_t<is_allocator_v<Alloc>>,
236           typename = std::enable_if_t<!is_allocator_v<Hash>>,
237           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
238           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
239 concurrent_unordered_multiset( It, It, std::size_t = {}, Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
240 -> concurrent_unordered_multiset<iterator_value_t<It>, Hash, KeyEq, Alloc>;
241 
242 template <typename T,
243           typename Hash = std::hash<T>,
244           typename KeyEq = std::equal_to<T>,
245           typename Alloc = tbb::tbb_allocator<T>,
246           typename = std::enable_if_t<is_allocator_v<Alloc>>,
247           typename = std::enable_if_t<!is_allocator_v<Hash>>,
248           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
249           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
250 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t = {},
251                           Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
252 -> concurrent_unordered_multiset<T, Hash, KeyEq, Alloc>;
253 
254 template <typename It, typename Alloc,
255           typename = std::enable_if_t<is_input_iterator_v<It>>,
256           typename = std::enable_if_t<is_allocator_v<Alloc>>>
257 concurrent_unordered_multiset( It, It, std::size_t, Alloc )
258 -> concurrent_unordered_multiset<iterator_value_t<It>, std::hash<iterator_value_t<It>>,
259                             std::equal_to<iterator_value_t<It>>, Alloc>;
260 
261 template <typename It, typename Hash, typename Alloc,
262           typename = std::enable_if_t<is_input_iterator_v<It>>,
263           typename = std::enable_if_t<is_allocator_v<Alloc>>,
264           typename = std::enable_if_t<!is_allocator_v<Hash>>,
265           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
266 concurrent_unordered_multiset( It, It, std::size_t, Hash, Alloc )
267 -> concurrent_unordered_multiset<iterator_value_t<It>, Hash, std::equal_to<iterator_value_t<It>>, Alloc>;
268 
269 template <typename T, typename Alloc,
270           typename = std::enable_if_t<is_allocator_v<Alloc>>>
271 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t, Alloc )
272 -> concurrent_unordered_multiset<T, std::hash<T>, std::equal_to<T>, Alloc>;
273 
274 template <typename T, typename Alloc,
275           typename = std::enable_if_t<is_allocator_v<Alloc>>>
276 concurrent_unordered_multiset( std::initializer_list<T>, Alloc )
277 -> concurrent_unordered_multiset<T, std::hash<T>, std::equal_to<T>, Alloc>;
278 
279 template <typename T, typename Hash, typename Alloc,
280           typename = std::enable_if_t<is_allocator_v<Alloc>>,
281           typename = std::enable_if_t<!is_allocator_v<Hash>>,
282           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
283 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t, Hash, Alloc )
284 -> concurrent_unordered_multiset<T, Hash, std::equal_to<T>, Alloc>;
285 
286 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
287 
288 template <typename Key, typename Hash, typename KeyEqual, typename Allocator>
289 void swap( concurrent_unordered_multiset<Key, Hash, KeyEqual, Allocator>& lhs,
290            concurrent_unordered_multiset<Key, Hash, KeyEqual, Allocator>& rhs ) {
291     lhs.swap(rhs);
292 }
293 
294 } // namespace d1
295 } // namespace detail
296 
297 inline namespace v1 {
298 
299 using detail::d1::concurrent_unordered_set;
300 using detail::d1::concurrent_unordered_multiset;
301 using detail::split;
302 
303 } // inline namespace v1
304 } // namespace tbb
305 
306 #endif // __TBB_concurrent_unordered_set_H
307