oneapi/tbb/concurrent_unordered_set.h

0001 /*
0002     Copyright (c) 2005-2022 Intel Corporation
0003
0004     Licensed under the Apache License, Version 2.0 (the "License");
0005     you may not use this file except in compliance with the License.
0006     You may obtain a copy of the License at
0007
0008         http://www.apache.org/licenses/LICENSE-2.0
0009
0010     Unless required by applicable law or agreed to in writing, software
0011     distributed under the License is distributed on an "AS IS" BASIS,
0012     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013     See the License for the specific language governing permissions and
0014     limitations under the License.
0015 */
0016
0017 #ifndef __TBB_concurrent_unordered_set_H
0018 #define __TBB_concurrent_unordered_set_H
0019
0020 #include "detail/_namespace_injection.h"
0021 #include "detail/_concurrent_unordered_base.h"
0022 #include "tbb_allocator.h"
0023
0024 namespace tbb {
0025 namespace detail {
0026 namespace d1 {
0027
0028 template <typename Key, typename Hash, typename KeyEqual, typename Allocator, bool AllowMultimapping>
0029 struct concurrent_unordered_set_traits {
0030     using key_type = Key;
0031     using value_type = key_type;
0032     using allocator_type = Allocator;
0033     using hash_compare_type = hash_compare<key_type, Hash, KeyEqual>;
0034     static constexpr bool allow_multimapping = AllowMultimapping;
0035
0036     static constexpr const key_type& get_key( const value_type& value ) {
0037         return value;
0038     }
0039 }; // class concurrent_unordered_set_traits
0040
0041 template <typename Key, typename Hash, typename KeyEqual, typename Allocator>
0042 class concurrent_unordered_multiset;
0043
0044 template <typename Key, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>,
0045           typename Allocator = tbb::tbb_allocator<Key>>
0046 class concurrent_unordered_set
0047     : public concurrent_unordered_base<concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, false>>
0048 {
0049     using traits_type = concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, false>;
0050     using base_type = concurrent_unordered_base<traits_type>;
0051 public:
0052     using key_type = typename base_type::key_type;
0053     using value_type = typename base_type::value_type;
0054     using size_type = typename base_type::size_type;
0055     using difference_type = typename base_type::difference_type;
0056     using hasher = typename base_type::hasher;
0057     using key_equal = typename base_type::key_equal;
0058     using allocator_type = typename base_type::allocator_type;
0059     using reference = typename base_type::reference;
0060     using const_reference = typename base_type::const_reference;
0061     using pointer = typename base_type::pointer;
0062     using const_pointer = typename base_type::const_pointer;
0063     using iterator = typename base_type::iterator;
0064     using const_iterator = typename base_type::const_iterator;
0065     using local_iterator = typename base_type::local_iterator;
0066     using const_local_iterator = typename base_type::const_local_iterator;
0067     using node_type = typename base_type::node_type;
0068
0069     // Include constructors of base_type;
0070     using base_type::base_type;
0071
0072     // Required for implicit deduction guides
0073     concurrent_unordered_set() = default;
0074     concurrent_unordered_set( const concurrent_unordered_set& ) = default;
0075     concurrent_unordered_set( const concurrent_unordered_set& other, const allocator_type& alloc ) : base_type(other, alloc) {}
0076     concurrent_unordered_set( concurrent_unordered_set&& ) = default;
0077     concurrent_unordered_set( concurrent_unordered_set&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
0078     // Required to respect the rule of 5
0079     concurrent_unordered_set& operator=( const concurrent_unordered_set& ) = default;
0080     concurrent_unordered_set& operator=( concurrent_unordered_set&& ) = default;
0081
0082     concurrent_unordered_set& operator=( std::initializer_list<value_type> il ) {
0083         base_type::operator= (il);
0084         return *this;
0085     }
0086
0087     template <typename OtherHash, typename OtherKeyEqual>
0088     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
0089         this->internal_merge(source);
0090     }
0091
0092     template <typename OtherHash, typename OtherKeyEqual>
0093     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
0094         this->internal_merge(std::move(source));
0095     }
0096
0097     template <typename OtherHash, typename OtherKeyEqual>
0098     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
0099         this->internal_merge(source);
0100     }
0101
0102     template <typename OtherHash, typename OtherKeyEqual>
0103     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
0104         this->internal_merge(std::move(source));
0105     }
0106 }; // class concurrent_unordered_set
0107
0108 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0109
0110 template <typename It,
0111           typename Hash = std::hash<iterator_value_t<It>>,
0112           typename KeyEq = std::equal_to<iterator_value_t<It>>,
0113           typename Alloc = tbb::tbb_allocator<iterator_value_t<It>>,
0114           typename = std::enable_if_t<is_input_iterator_v<It>>,
0115           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0116           typename = std::enable_if_t<!is_allocator_v<Hash>>,
0117           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
0118           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
0119 concurrent_unordered_set( It, It, std::size_t = {}, Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
0120 -> concurrent_unordered_set<iterator_value_t<It>, Hash, KeyEq, Alloc>;
0121
0122 template <typename T,
0123           typename Hash = std::hash<T>,
0124           typename KeyEq = std::equal_to<T>,
0125           typename Alloc = tbb::tbb_allocator<T>,
0126           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0127           typename = std::enable_if_t<!is_allocator_v<Hash>>,
0128           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
0129           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
0130 concurrent_unordered_set( std::initializer_list<T>, std::size_t = {},
0131                           Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
0132 -> concurrent_unordered_set<T, Hash, KeyEq, Alloc>;
0133
0134 template <typename It, typename Alloc,
0135           typename = std::enable_if_t<is_input_iterator_v<It>>,
0136           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0137 concurrent_unordered_set( It, It, std::size_t, Alloc )
0138 -> concurrent_unordered_set<iterator_value_t<It>, std::hash<iterator_value_t<It>>,
0139                             std::equal_to<iterator_value_t<It>>, Alloc>;
0140
0141 template <typename It, typename Hash, typename Alloc,
0142           typename = std::enable_if_t<is_input_iterator_v<It>>,
0143           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0144           typename = std::enable_if_t<!is_allocator_v<Hash>>,
0145           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
0146 concurrent_unordered_set( It, It, std::size_t, Hash, Alloc )
0147 -> concurrent_unordered_set<iterator_value_t<It>, Hash, std::equal_to<iterator_value_t<It>>, Alloc>;
0148
0149 template <typename T, typename Alloc,
0150           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0151 concurrent_unordered_set( std::initializer_list<T>, std::size_t, Alloc )
0152 -> concurrent_unordered_set<T, std::hash<T>, std::equal_to<T>, Alloc>;
0153
0154 template <typename T, typename Alloc,
0155           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0156 concurrent_unordered_set( std::initializer_list<T>, Alloc )
0157 -> concurrent_unordered_set<T, std::hash<T>, std::equal_to<T>, Alloc>;
0158
0159 template <typename T, typename Hash, typename Alloc,
0160           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0161           typename = std::enable_if_t<!is_allocator_v<Hash>>,
0162           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
0163 concurrent_unordered_set( std::initializer_list<T>, std::size_t, Hash, Alloc )
0164 -> concurrent_unordered_set<T, Hash, std::equal_to<T>, Alloc>;
0165
0166 #if __APPLE__ && __TBB_CLANG_VERSION == 100000
0167 // An explicit deduction guide is required for copy/move constructor with allocator for APPLE LLVM 10.0.0
0168 // due to an issue with generating an implicit deduction guide for these constructors under several strange surcumstances.
0169 // Currently the issue takes place because the last template parameter for Traits is boolean, it should not affect the deduction guides
0170 // The issue reproduces only on this version of the compiler
0171 template <typename T, typename Hash, typename KeyEq, typename Alloc>
0172 concurrent_unordered_set( concurrent_unordered_set<T, Hash, KeyEq, Alloc>, Alloc )
0173 -> concurrent_unordered_set<T, Hash, KeyEq, Alloc>;
0174 #endif
0175 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0176
0177 template <typename Key, typename Hash, typename KeyEqual, typename Allocator>
0178 void swap( concurrent_unordered_set<Key, Hash, KeyEqual, Allocator>& lhs,
0179            concurrent_unordered_set<Key, Hash, KeyEqual, Allocator>& rhs ) {
0180     lhs.swap(rhs);
0181 }
0182
0183 template <typename Key, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>,
0184           typename Allocator = tbb::tbb_allocator<Key>>
0185 class concurrent_unordered_multiset
0186     : public concurrent_unordered_base<concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, true>>
0187 {
0188     using traits_type = concurrent_unordered_set_traits<Key, Hash, KeyEqual, Allocator, true>;
0189     using base_type = concurrent_unordered_base<traits_type>;
0190 public:
0191     using key_type = typename base_type::key_type;
0192     using value_type = typename base_type::value_type;
0193     using size_type = typename base_type::size_type;
0194     using difference_type = typename base_type::difference_type;
0195     using hasher = typename base_type::hasher;
0196     using key_equal = typename base_type::key_equal;
0197     using allocator_type = typename base_type::allocator_type;
0198     using reference = typename base_type::reference;
0199     using const_reference = typename base_type::const_reference;
0200     using pointer = typename base_type::pointer;
0201     using const_pointer = typename base_type::const_pointer;
0202     using iterator = typename base_type::iterator;
0203     using const_iterator = typename base_type::const_iterator;
0204     using local_iterator = typename base_type::local_iterator;
0205     using const_local_iterator = typename base_type::const_local_iterator;
0206     using node_type = typename base_type::node_type;
0207
0208     // Include constructors of base_type;
0209     using base_type::base_type;
0210
0211     // Required for implicit deduction guides
0212     concurrent_unordered_multiset() = default;
0213     concurrent_unordered_multiset( const concurrent_unordered_multiset& ) = default;
0214     concurrent_unordered_multiset( const concurrent_unordered_multiset& other, const allocator_type& alloc ) : base_type(other, alloc) {}
0215     concurrent_unordered_multiset( concurrent_unordered_multiset&& ) = default;
0216     concurrent_unordered_multiset( concurrent_unordered_multiset&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
0217     // Required to respect the rule of 5
0218     concurrent_unordered_multiset& operator=( const concurrent_unordered_multiset& ) = default;
0219     concurrent_unordered_multiset& operator=( concurrent_unordered_multiset&& ) = default;
0220
0221     concurrent_unordered_multiset& operator=( std::initializer_list<value_type> il ) {
0222         base_type::operator= (il);
0223         return *this;
0224     }
0225
0226     template <typename OtherHash, typename OtherKeyEqual>
0227     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
0228         this->internal_merge(source);
0229     }
0230
0231     template <typename OtherHash, typename OtherKeyEqual>
0232     void merge( concurrent_unordered_set<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
0233         this->internal_merge(std::move(source));
0234     }
0235
0236     template <typename OtherHash, typename OtherKeyEqual>
0237     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>& source ) {
0238         this->internal_merge(source);
0239     }
0240
0241     template <typename OtherHash, typename OtherKeyEqual>
0242     void merge( concurrent_unordered_multiset<key_type, OtherHash, OtherKeyEqual, allocator_type>&& source ) {
0243         this->internal_merge(std::move(source));
0244     }
0245 }; // class concurrent_unordered_multiset
0246
0247 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0248 template <typename It,
0249           typename Hash = std::hash<iterator_value_t<It>>,
0250           typename KeyEq = std::equal_to<iterator_value_t<It>>,
0251           typename Alloc = tbb::tbb_allocator<iterator_value_t<It>>,
0252           typename = std::enable_if_t<is_input_iterator_v<It>>,
0253           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0254           typename = std::enable_if_t<!is_allocator_v<Hash>>,
0255           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
0256           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
0257 concurrent_unordered_multiset( It, It, std::size_t = {}, Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
0258 -> concurrent_unordered_multiset<iterator_value_t<It>, Hash, KeyEq, Alloc>;
0259
0260 template <typename T,
0261           typename Hash = std::hash<T>,
0262           typename KeyEq = std::equal_to<T>,
0263           typename Alloc = tbb::tbb_allocator<T>,
0264           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0265           typename = std::enable_if_t<!is_allocator_v<Hash>>,
0266           typename = std::enable_if_t<!is_allocator_v<KeyEq>>,
0267           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
0268 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t = {},
0269                           Hash = Hash(), KeyEq = KeyEq(), Alloc = Alloc() )
0270 -> concurrent_unordered_multiset<T, Hash, KeyEq, Alloc>;
0271
0272 template <typename It, typename Alloc,
0273           typename = std::enable_if_t<is_input_iterator_v<It>>,
0274           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0275 concurrent_unordered_multiset( It, It, std::size_t, Alloc )
0276 -> concurrent_unordered_multiset<iterator_value_t<It>, std::hash<iterator_value_t<It>>,
0277                             std::equal_to<iterator_value_t<It>>, Alloc>;
0278
0279 template <typename It, typename Hash, typename Alloc,
0280           typename = std::enable_if_t<is_input_iterator_v<It>>,
0281           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0282           typename = std::enable_if_t<!is_allocator_v<Hash>>,
0283           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
0284 concurrent_unordered_multiset( It, It, std::size_t, Hash, Alloc )
0285 -> concurrent_unordered_multiset<iterator_value_t<It>, Hash, std::equal_to<iterator_value_t<It>>, Alloc>;
0286
0287 template <typename T, typename Alloc,
0288           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0289 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t, Alloc )
0290 -> concurrent_unordered_multiset<T, std::hash<T>, std::equal_to<T>, Alloc>;
0291
0292 template <typename T, typename Alloc,
0293           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0294 concurrent_unordered_multiset( std::initializer_list<T>, Alloc )
0295 -> concurrent_unordered_multiset<T, std::hash<T>, std::equal_to<T>, Alloc>;
0296
0297 template <typename T, typename Hash, typename Alloc,
0298           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0299           typename = std::enable_if_t<!is_allocator_v<Hash>>,
0300           typename = std::enable_if_t<!std::is_integral_v<Hash>>>
0301 concurrent_unordered_multiset( std::initializer_list<T>, std::size_t, Hash, Alloc )
0302 -> concurrent_unordered_multiset<T, Hash, std::equal_to<T>, Alloc>;
0303
0304 #if __APPLE__ && __TBB_CLANG_VERSION == 100000
0305 // An explicit deduction guide is required for copy/move constructor with allocator for APPLE LLVM 10.0.0
0306 // due to an issue with generating an implicit deduction guide for these constructors under several strange surcumstances.
0307 // Currently the issue takes place because the last template parameter for Traits is boolean, it should not affect the deduction guides
0308 // The issue reproduces only on this version of the compiler
0309 template <typename T, typename Hash, typename KeyEq, typename Alloc>
0310 concurrent_unordered_multiset( concurrent_unordered_multiset<T, Hash, KeyEq, Alloc>, Alloc )
0311 -> concurrent_unordered_multiset<T, Hash, KeyEq, Alloc>;
0312 #endif
0313 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0314
0315 template <typename Key, typename Hash, typename KeyEqual, typename Allocator>
0316 void swap( concurrent_unordered_multiset<Key, Hash, KeyEqual, Allocator>& lhs,
0317            concurrent_unordered_multiset<Key, Hash, KeyEqual, Allocator>& rhs ) {
0318     lhs.swap(rhs);
0319 }
0320
0321 } // namespace d1
0322 } // namespace detail
0323
0324 inline namespace v1 {
0325
0326 using detail::d1::concurrent_unordered_set;
0327 using detail::d1::concurrent_unordered_multiset;
0328 using detail::split;
0329
0330 } // inline namespace v1
0331 } // namespace tbb
0332
0333 #endif // __TBB_concurrent_unordered_set_H