include/tbb/concurrent_unordered_set.h

0001 /*
0002     Copyright (c) 2005-2020 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 /* Container implementations in this header are based on PPL implementations
0018    provided by Microsoft. */
0019
0020 #ifndef __TBB_concurrent_unordered_set_H
0021 #define __TBB_concurrent_unordered_set_H
0022
0023 #define __TBB_concurrent_unordered_set_H_include_area
0024 #include "internal/_warning_suppress_enable_notice.h"
0025
0026 #include "internal/_concurrent_unordered_impl.h"
0027
0028 namespace tbb
0029 {
0030
0031 namespace interface5 {
0032
0033 // Template class for hash set traits
0034 template<typename Key, typename Hash_compare, typename Allocator, bool Allow_multimapping>
0035 class concurrent_unordered_set_traits
0036 {
0037 protected:
0038     typedef Key value_type;
0039     typedef Key key_type;
0040     typedef Hash_compare hash_compare;
0041     typedef typename tbb::internal::allocator_rebind<Allocator, value_type>::type allocator_type;
0042 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
0043     typedef tbb::internal::node_handle<key_type, key_type,
0044                                   typename internal::split_ordered_list<key_type, allocator_type>::node,
0045                                   allocator_type> node_type;
0046 #endif // __TBB_UNORDERED_NODE_HANDLE_PRESENT
0047
0048     enum { allow_multimapping = Allow_multimapping };
0049
0050     concurrent_unordered_set_traits() : my_hash_compare() {}
0051     concurrent_unordered_set_traits(const hash_compare& hc) : my_hash_compare(hc) {}
0052
0053     static const Key& get_key(const value_type& value) {
0054         return value;
0055     }
0056
0057     hash_compare my_hash_compare; // the comparator predicate for keys
0058 };
0059
0060 template<typename Key, typename Hasher, typename Key_equality, typename Allocator>
0061 class concurrent_unordered_multiset;
0062
0063 template <typename Key, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>, typename Allocator = tbb::tbb_allocator<Key> >
0064 class concurrent_unordered_set : public internal::concurrent_unordered_base< concurrent_unordered_set_traits<Key, internal::hash_compare<Key, Hasher, Key_equality>, Allocator, false> >
0065 {
0066     // Base type definitions
0067     typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
0068     typedef concurrent_unordered_set_traits<Key, hash_compare, Allocator, false> traits_type;
0069     typedef internal::concurrent_unordered_base< traits_type > base_type;
0070 #if __TBB_EXTRA_DEBUG
0071 public:
0072 #endif
0073     using traits_type::allow_multimapping;
0074 public:
0075     using base_type::insert;
0076
0077     // Type definitions
0078     typedef Key key_type;
0079     typedef typename base_type::value_type value_type;
0080     typedef Key mapped_type;
0081     typedef Hasher hasher;
0082     typedef Key_equality key_equal;
0083     typedef hash_compare key_compare;
0084
0085     typedef typename base_type::allocator_type allocator_type;
0086     typedef typename base_type::pointer pointer;
0087     typedef typename base_type::const_pointer const_pointer;
0088     typedef typename base_type::reference reference;
0089     typedef typename base_type::const_reference const_reference;
0090
0091     typedef typename base_type::size_type size_type;
0092     typedef typename base_type::difference_type difference_type;
0093
0094     typedef typename base_type::iterator iterator;
0095     typedef typename base_type::const_iterator const_iterator;
0096     typedef typename base_type::iterator local_iterator;
0097     typedef typename base_type::const_iterator const_local_iterator;
0098 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
0099     typedef typename base_type::node_type node_type;
0100 #endif /*__TBB_UNORDERED_NODE_HANDLE_PRESENT*/
0101
0102     // Construction/destruction/copying
0103     explicit concurrent_unordered_set(size_type n_of_buckets = base_type::initial_bucket_number, const hasher& a_hasher = hasher(),
0104         const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
0105         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
0106     {}
0107
0108     concurrent_unordered_set(size_type n_of_buckets, const allocator_type& a)
0109         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
0110     {}
0111
0112     concurrent_unordered_set(size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
0113         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
0114     {}
0115
0116     explicit concurrent_unordered_set(const Allocator& a) : base_type(base_type::initial_bucket_number, key_compare(), a)
0117     {}
0118
0119     template <typename Iterator>
0120     concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets = base_type::initial_bucket_number,
0121         const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
0122         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
0123     {
0124         insert(first, last);
0125     }
0126
0127     template <typename Iterator>
0128     concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type& a)
0129         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
0130     {
0131         insert(first, last);
0132     }
0133
0134     template <typename Iterator>
0135     concurrent_unordered_set(Iterator first, Iterator last, size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
0136         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
0137     {
0138         insert(first, last);
0139     }
0140
0141 #if __TBB_INITIALIZER_LISTS_PRESENT
0142     //! Constructor from initializer_list
0143     concurrent_unordered_set(std::initializer_list<value_type> il, size_type n_of_buckets = base_type::initial_bucket_number, const hasher& a_hasher = hasher(),
0144         const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
0145         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
0146     {
0147         insert(il.begin(),il.end());
0148     }
0149
0150     concurrent_unordered_set(std::initializer_list<value_type> il, size_type n_of_buckets, const allocator_type& a)
0151         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
0152     {
0153         insert(il.begin(), il.end());
0154     }
0155
0156     concurrent_unordered_set(std::initializer_list<value_type> il, size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
0157         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
0158     {
0159         insert(il.begin(), il.end());
0160     }
0161
0162 #endif //# __TBB_INITIALIZER_LISTS_PRESENT
0163
0164 #if __TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
0165     concurrent_unordered_set(const concurrent_unordered_set& table)
0166         : base_type(table)
0167     {}
0168
0169     concurrent_unordered_set& operator=(const concurrent_unordered_set& table)
0170     {
0171         return static_cast<concurrent_unordered_set&>(base_type::operator=(table));
0172     }
0173
0174     concurrent_unordered_set(concurrent_unordered_set&& table)
0175         : base_type(std::move(table))
0176     {}
0177
0178     concurrent_unordered_set& operator=(concurrent_unordered_set&& table)
0179     {
0180         return static_cast<concurrent_unordered_set&>(base_type::operator=(std::move(table)));
0181     }
0182 #endif //__TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
0183
0184 #if __TBB_CPP11_RVALUE_REF_PRESENT
0185     concurrent_unordered_set(concurrent_unordered_set&& table, const Allocator& a)
0186         : base_type(std::move(table), a)
0187     {}
0188 #endif /*__TBB_CPP11_RVALUE_REF_PRESENT*/
0189
0190 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
0191     template<typename Hash, typename Equality>
0192     void merge(concurrent_unordered_set<Key, Hash, Equality, Allocator>& source)
0193               { this->internal_merge(source); }
0194
0195     template<typename Hash, typename Equality>
0196     void merge(concurrent_unordered_set<Key, Hash, Equality, Allocator>&& source)
0197               { this->internal_merge(source); }
0198
0199     template<typename Hash, typename Equality>
0200     void merge(concurrent_unordered_multiset<Key, Hash, Equality, Allocator>& source)
0201               { this->internal_merge(source); }
0202
0203     template<typename Hash, typename Equality>
0204     void merge(concurrent_unordered_multiset<Key, Hash, Equality, Allocator>&& source)
0205               { this->internal_merge(source); }
0206
0207 #endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
0208
0209     concurrent_unordered_set(const concurrent_unordered_set& table, const Allocator& a)
0210         : base_type(table, a)
0211     {}
0212
0213 };
0214
0215 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0216
0217 namespace internal {
0218 using namespace tbb::internal;
0219
0220 template <template<typename...> typename Set, typename T, typename... Args>
0221 using cu_set_t = Set <
0222     T,
0223     std::conditional_t< (sizeof...(Args)>0) && !is_allocator_v< pack_element_t<0, Args...> >,
0224                         pack_element_t<0, Args...>, tbb_hash<T> >,
0225     std::conditional_t< (sizeof...(Args)>1) && !is_allocator_v< pack_element_t<1, Args...> >,
0226                         pack_element_t<1, Args...>, std::equal_to<T> >,
0227     std::conditional_t< (sizeof...(Args)>0) && is_allocator_v< pack_element_t<sizeof...(Args)-1, Args...> >,
0228                         pack_element_t<sizeof...(Args)-1, Args...>, tbb_allocator<T> >
0229 >;
0230 }
0231
0232 // Deduction guide for the constructor from two iterators
0233 template<typename I>
0234 concurrent_unordered_set(I, I)
0235 -> internal::cu_set_t<concurrent_unordered_set, internal::iterator_value_t<I>>;
0236
0237 // Deduction guide for the constructor from two iterators and hasher/equality/allocator
0238 template<typename I, typename... Args>
0239 concurrent_unordered_set(I, I, size_t, Args...)
0240 -> internal::cu_set_t<concurrent_unordered_set, internal::iterator_value_t<I>, Args...>;
0241
0242 // Deduction guide for the constructor from an initializer_list
0243 template<typename T>
0244 concurrent_unordered_set(std::initializer_list<T>)
0245 -> internal::cu_set_t<concurrent_unordered_set, T>;
0246
0247 // Deduction guide for the constructor from an initializer_list and hasher/equality/allocator
0248 template<typename T, typename... Args>
0249 concurrent_unordered_set(std::initializer_list<T>, size_t, Args...)
0250 -> internal::cu_set_t<concurrent_unordered_set, T, Args...>;
0251
0252 #endif /*__TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
0253
0254 template <typename Key, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>,
0255          typename Allocator = tbb::tbb_allocator<Key> >
0256 class concurrent_unordered_multiset :
0257     public internal::concurrent_unordered_base< concurrent_unordered_set_traits<Key,
0258     internal::hash_compare<Key, Hasher, Key_equality>, Allocator, true> >
0259 {
0260     // Base type definitions
0261     typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
0262     typedef concurrent_unordered_set_traits<Key, hash_compare, Allocator, true> traits_type;
0263     typedef internal::concurrent_unordered_base< traits_type > base_type;
0264 #if __TBB_EXTRA_DEBUG
0265 public:
0266 #endif
0267     using traits_type::allow_multimapping;
0268 public:
0269     using base_type::insert;
0270
0271     // Type definitions
0272     typedef Key key_type;
0273     typedef typename base_type::value_type value_type;
0274     typedef Key mapped_type;
0275     typedef Hasher hasher;
0276     typedef Key_equality key_equal;
0277     typedef hash_compare key_compare;
0278
0279     typedef typename base_type::allocator_type allocator_type;
0280     typedef typename base_type::pointer pointer;
0281     typedef typename base_type::const_pointer const_pointer;
0282     typedef typename base_type::reference reference;
0283     typedef typename base_type::const_reference const_reference;
0284
0285     typedef typename base_type::size_type size_type;
0286     typedef typename base_type::difference_type difference_type;
0287
0288     typedef typename base_type::iterator iterator;
0289     typedef typename base_type::const_iterator const_iterator;
0290     typedef typename base_type::iterator local_iterator;
0291     typedef typename base_type::const_iterator const_local_iterator;
0292 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
0293     typedef typename base_type::node_type node_type;
0294 #endif // __TBB_UNORDERED_NODE_HANDLE_PRESENT
0295
0296     // Construction/destruction/copying
0297     explicit concurrent_unordered_multiset(size_type n_of_buckets = base_type::initial_bucket_number,
0298         const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
0299         const allocator_type& a = allocator_type())
0300         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
0301     {}
0302
0303     concurrent_unordered_multiset(size_type n_of_buckets, const allocator_type& a)
0304         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
0305     {}
0306
0307     concurrent_unordered_multiset(size_type n_of_buckets, const hasher& a_hasher,
0308         const allocator_type& a)
0309         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
0310     {}
0311
0312     explicit concurrent_unordered_multiset(const Allocator& a) : base_type(base_type::initial_bucket_number, key_compare(), a)
0313     {}
0314
0315     template <typename Iterator>
0316     concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets = base_type::initial_bucket_number,
0317         const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
0318         const allocator_type& a = allocator_type())
0319         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
0320     {
0321         insert(first, last);
0322     }
0323
0324     template <typename Iterator>
0325     concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type& a)
0326         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
0327     {
0328         insert(first, last);
0329     }
0330
0331     template <typename Iterator>
0332     concurrent_unordered_multiset(Iterator first, Iterator last, size_type n_of_buckets, const hasher& a_hasher,
0333         const allocator_type& a)
0334         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
0335     {
0336         insert(first, last);
0337     }
0338
0339 #if __TBB_INITIALIZER_LISTS_PRESENT
0340     //! Constructor from initializer_list
0341     concurrent_unordered_multiset(std::initializer_list<value_type> il, size_type n_of_buckets = base_type::initial_bucket_number,
0342         const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
0343         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
0344     {
0345         insert(il.begin(),il.end());
0346     }
0347
0348     concurrent_unordered_multiset(std::initializer_list<value_type> il, size_type n_of_buckets, const allocator_type& a)
0349         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
0350     {
0351         insert(il.begin(), il.end());
0352     }
0353
0354     concurrent_unordered_multiset(std::initializer_list<value_type> il, size_type n_of_buckets, const hasher& a_hasher,
0355         const allocator_type& a)
0356         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
0357     {
0358         insert(il.begin(), il.end());
0359     }
0360
0361 #endif //# __TBB_INITIALIZER_LISTS_PRESENT
0362
0363
0364 #if __TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
0365     concurrent_unordered_multiset(const concurrent_unordered_multiset& table)
0366         : base_type(table)
0367     {}
0368
0369     concurrent_unordered_multiset& operator=(const concurrent_unordered_multiset& table)
0370     {
0371         return static_cast<concurrent_unordered_multiset&>(base_type::operator=(table));
0372     }
0373
0374     concurrent_unordered_multiset(concurrent_unordered_multiset&& table)
0375         : base_type(std::move(table))
0376     {}
0377
0378     concurrent_unordered_multiset& operator=(concurrent_unordered_multiset&& table)
0379     {
0380         return static_cast<concurrent_unordered_multiset&>(base_type::operator=(std::move(table)));
0381     }
0382 #endif //__TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
0383
0384 #if __TBB_CPP11_RVALUE_REF_PRESENT
0385     concurrent_unordered_multiset(concurrent_unordered_multiset&& table, const Allocator& a)
0386         : base_type(std::move(table), a)
0387     {
0388     }
0389 #endif /*__TBB_CPP11_RVALUE_REF_PRESENT*/
0390
0391 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
0392     template<typename Hash, typename Equality>
0393     void merge(concurrent_unordered_set<Key, Hash, Equality, Allocator>& source)
0394               { this->internal_merge(source); }
0395
0396     template<typename Hash, typename Equality>
0397     void merge(concurrent_unordered_set<Key, Hash, Equality, Allocator>&& source)
0398               { this->internal_merge(source); }
0399
0400     template<typename Hash, typename Equality>
0401     void merge(concurrent_unordered_multiset<Key, Hash, Equality, Allocator>& source)
0402               { this->internal_merge(source); }
0403
0404     template<typename Hash, typename Equality>
0405     void merge(concurrent_unordered_multiset<Key, Hash, Equality, Allocator>&& source)
0406               { this->internal_merge(source); }
0407
0408 #endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
0409
0410     concurrent_unordered_multiset(const concurrent_unordered_multiset& table, const Allocator& a)
0411         : base_type(table, a)
0412     {}
0413 };
0414
0415 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0416
0417 // Deduction guide for the constructor from two iterators
0418 template<typename I>
0419 concurrent_unordered_multiset(I, I)
0420 -> internal::cu_set_t<concurrent_unordered_multiset, internal::iterator_value_t<I>>;
0421
0422 // Deduction guide for the constructor from two iterators and hasher/equality/allocator
0423 template<typename I, typename... Args>
0424 concurrent_unordered_multiset(I, I, size_t, Args...)
0425 -> internal::cu_set_t<concurrent_unordered_multiset, internal::iterator_value_t<I>, Args...>;
0426
0427 // Deduction guide for the constructor from an initializer_list
0428 template<typename T>
0429 concurrent_unordered_multiset(std::initializer_list<T>)
0430 -> internal::cu_set_t<concurrent_unordered_multiset, T>;
0431
0432 // Deduction guide for the constructor from an initializer_list and hasher/equality/allocator
0433 template<typename T, typename... Args>
0434 concurrent_unordered_multiset(std::initializer_list<T>, size_t, Args...)
0435 -> internal::cu_set_t<concurrent_unordered_multiset, T, Args...>;
0436
0437 #endif /* __TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
0438 } // namespace interface5
0439
0440 using interface5::concurrent_unordered_set;
0441 using interface5::concurrent_unordered_multiset;
0442
0443 } // namespace tbb
0444
0445 #include "internal/_warning_suppress_disable_notice.h"
0446 #undef __TBB_concurrent_unordered_set_H_include_area
0447
0448 #endif// __TBB_concurrent_unordered_set_H