oneapi/tbb/concurrent_set.h

0001 /*
0002     Copyright (c) 2019-2021 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_set_H
0018 #define __TBB_concurrent_set_H
0019
0020 #include "detail/_namespace_injection.h"
0021 #include "detail/_concurrent_skip_list.h"
0022 #include "tbb_allocator.h"
0023 #include <functional>
0024 #include <utility>
0025
0026 namespace tbb {
0027 namespace detail {
0028 namespace d2 {
0029
0030 template<typename Key, typename KeyCompare, typename RandomGenerator, typename Allocator, bool AllowMultimapping>
0031 struct set_traits {
0032     static constexpr std::size_t max_level = RandomGenerator::max_level;
0033     using random_level_generator_type = RandomGenerator;
0034     using key_type = Key;
0035     using value_type = key_type;
0036     using compare_type = KeyCompare;
0037     using value_compare = compare_type;
0038     using reference = value_type&;
0039     using const_reference = const value_type&;
0040     using allocator_type = Allocator;
0041
0042     static constexpr bool allow_multimapping = AllowMultimapping;
0043
0044     static const key_type& get_key(const_reference val) {
0045         return val;
0046     }
0047
0048     static value_compare value_comp(compare_type comp) { return comp; }
0049 }; // struct set_traits
0050
0051 template <typename Key, typename Compare, typename Allocator>
0052 class concurrent_multiset;
0053
0054 template <typename Key, typename Compare = std::less<Key>, typename Allocator = tbb::tbb_allocator<Key>>
0055 class concurrent_set : public concurrent_skip_list<set_traits<Key, Compare, concurrent_geometric_level_generator<32>, Allocator, false>> {
0056     using base_type = concurrent_skip_list<set_traits<Key, Compare, concurrent_geometric_level_generator<32>, Allocator, false>>;
0057 public:
0058     using key_type = Key;
0059     using value_type = typename base_type::value_type;
0060     using size_type = typename base_type::size_type;
0061     using difference_type = typename base_type::difference_type;
0062     using key_compare = Compare;
0063     using value_compare = typename base_type::value_compare;
0064     using allocator_type = Allocator;
0065
0066     using reference = typename base_type::reference;
0067     using const_reference = typename base_type::const_reference;
0068     using pointer = typename base_type::pointer;
0069     using const_pointer = typename base_type::const_pointer;
0070
0071     using iterator = typename base_type::iterator;
0072     using const_iterator = typename base_type::const_iterator;
0073
0074     using node_type = typename base_type::node_type;
0075
0076     // Include constructors of base_type
0077     using base_type::base_type;
0078
0079     // Required for implicit deduction guides
0080     concurrent_set() = default;
0081     concurrent_set( const concurrent_set& ) = default;
0082     concurrent_set( const concurrent_set& other, const allocator_type& alloc ) : base_type(other, alloc) {}
0083     concurrent_set( concurrent_set&& ) = default;
0084     concurrent_set( concurrent_set&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
0085     // Required to respect the rule of 5
0086     concurrent_set& operator=( const concurrent_set& ) = default;
0087     concurrent_set& operator=( concurrent_set&& ) = default;
0088
0089     concurrent_set& operator=( std::initializer_list<value_type> il ) {
0090         base_type::operator= (il);
0091         return *this;
0092     }
0093
0094     template<typename OtherCompare>
0095     void merge(concurrent_set<key_type, OtherCompare, Allocator>& source) {
0096         this->internal_merge(source);
0097     }
0098
0099     template<typename OtherCompare>
0100     void merge(concurrent_set<key_type, OtherCompare, Allocator>&& source) {
0101         this->internal_merge(std::move(source));
0102     }
0103
0104     template<typename OtherCompare>
0105     void merge(concurrent_multiset<key_type, OtherCompare, Allocator>& source) {
0106         this->internal_merge(source);
0107     }
0108
0109     template<typename OtherCompare>
0110     void merge(concurrent_multiset<key_type, OtherCompare, Allocator>&& source) {
0111         this->internal_merge(std::move(source));
0112     }
0113 }; // class concurrent_set
0114
0115 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0116
0117 template <typename It,
0118           typename Comp = std::less<iterator_value_t<It>>,
0119           typename Alloc = tbb::tbb_allocator<iterator_value_t<It>>,
0120           typename = std::enable_if_t<is_input_iterator_v<It>>,
0121           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0122           typename = std::enable_if_t<!is_allocator_v<Comp>>>
0123 concurrent_set( It, It, Comp = Comp(), Alloc = Alloc() )
0124 -> concurrent_set<iterator_value_t<It>, Comp, Alloc>;
0125
0126 template <typename Key,
0127           typename Comp = std::less<Key>,
0128           typename Alloc = tbb::tbb_allocator<Key>,
0129           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0130           typename = std::enable_if_t<!is_allocator_v<Comp>>>
0131 concurrent_set( std::initializer_list<Key>, Comp = Comp(), Alloc = Alloc() )
0132 -> concurrent_set<Key, Comp, 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_set( It, It, Alloc )
0138 -> concurrent_set<iterator_value_t<It>,
0139                   std::less<iterator_value_t<It>>, Alloc>;
0140
0141 template <typename Key, typename Alloc,
0142           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0143 concurrent_set( std::initializer_list<Key>, Alloc )
0144 -> concurrent_set<Key, std::less<Key>, Alloc>;
0145
0146 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0147
0148 template <typename Key, typename Compare, typename Allocator>
0149 void swap( concurrent_set<Key, Compare, Allocator>& lhs,
0150            concurrent_set<Key, Compare, Allocator>& rhs )
0151 {
0152     lhs.swap(rhs);
0153 }
0154
0155 template <typename Key, typename Compare = std::less<Key>, typename Allocator = tbb::tbb_allocator<Key>>
0156 class concurrent_multiset : public concurrent_skip_list<set_traits<Key, Compare, concurrent_geometric_level_generator<32>, Allocator, true>> {
0157     using base_type = concurrent_skip_list<set_traits<Key, Compare, concurrent_geometric_level_generator<32>, Allocator, true>>;
0158 public:
0159     using key_type = Key;
0160     using value_type = typename base_type::value_type;
0161     using size_type = typename base_type::size_type;
0162     using difference_type = typename base_type::difference_type;
0163     using key_compare = Compare;
0164     using value_compare = typename base_type::value_compare;
0165     using allocator_type = Allocator;
0166
0167     using reference = typename base_type::reference;
0168     using const_reference = typename base_type::const_reference;
0169     using pointer = typename base_type::pointer;
0170     using const_pointer = typename base_type::const_pointer;
0171
0172     using iterator = typename base_type::iterator;
0173     using const_iterator = typename base_type::const_iterator;
0174
0175     using node_type = typename base_type::node_type;
0176
0177     // Include constructors of base_type;
0178     using base_type::base_type;
0179
0180     // Required for implicit deduction guides
0181     concurrent_multiset() = default;
0182     concurrent_multiset( const concurrent_multiset& ) = default;
0183     concurrent_multiset( const concurrent_multiset& other, const allocator_type& alloc ) : base_type(other, alloc) {}
0184     concurrent_multiset( concurrent_multiset&& ) = default;
0185     concurrent_multiset( concurrent_multiset&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
0186     // Required to respect the rule of 5
0187     concurrent_multiset& operator=( const concurrent_multiset& ) = default;
0188     concurrent_multiset& operator=( concurrent_multiset&& ) = default;
0189
0190     concurrent_multiset& operator=( std::initializer_list<value_type> il ) {
0191         base_type::operator= (il);
0192         return *this;
0193     }
0194
0195     template<typename OtherCompare>
0196     void merge(concurrent_set<key_type, OtherCompare, Allocator>& source) {
0197         this->internal_merge(source);
0198     }
0199
0200     template<typename OtherCompare>
0201     void merge(concurrent_set<key_type, OtherCompare, Allocator>&& source) {
0202         this->internal_merge(std::move(source));
0203     }
0204
0205     template<typename OtherCompare>
0206     void merge(concurrent_multiset<key_type, OtherCompare, Allocator>& source) {
0207         this->internal_merge(source);
0208     }
0209
0210     template<typename OtherCompare>
0211     void merge(concurrent_multiset<key_type, OtherCompare, Allocator>&& source) {
0212         this->internal_merge(std::move(source));
0213     }
0214 }; // class concurrent_multiset
0215
0216 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0217
0218 template <typename It,
0219           typename Comp = std::less<iterator_value_t<It>>,
0220           typename Alloc = tbb::tbb_allocator<iterator_value_t<It>>,
0221           typename = std::enable_if_t<is_input_iterator_v<It>>,
0222           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0223           typename = std::enable_if_t<!is_allocator_v<Comp>>>
0224 concurrent_multiset( It, It, Comp = Comp(), Alloc = Alloc() )
0225 -> concurrent_multiset<iterator_value_t<It>, Comp, Alloc>;
0226
0227 template <typename Key,
0228           typename Comp = std::less<Key>,
0229           typename Alloc = tbb::tbb_allocator<Key>,
0230           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0231           typename = std::enable_if_t<!is_allocator_v<Comp>>>
0232 concurrent_multiset( std::initializer_list<Key>, Comp = Comp(), Alloc = Alloc() )
0233 -> concurrent_multiset<Key, Comp, Alloc>;
0234
0235 template <typename It, typename Alloc,
0236           typename = std::enable_if_t<is_input_iterator_v<It>>,
0237           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0238 concurrent_multiset( It, It, Alloc )
0239 -> concurrent_multiset<iterator_value_t<It>, std::less<iterator_value_t<It>>, Alloc>;
0240
0241 template <typename Key, typename Alloc,
0242           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0243 concurrent_multiset( std::initializer_list<Key>, Alloc )
0244 -> concurrent_multiset<Key, std::less<Key>, Alloc>;
0245
0246 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0247
0248 template <typename Key, typename Compare, typename Allocator>
0249 void swap( concurrent_multiset<Key, Compare, Allocator>& lhs,
0250            concurrent_multiset<Key, Compare, Allocator>& rhs )
0251 {
0252     lhs.swap(rhs);
0253 }
0254
0255 } // namespace d2
0256 } // namespace detail
0257
0258 inline namespace v1 {
0259
0260 using detail::d2::concurrent_set;
0261 using detail::d2::concurrent_multiset;
0262 using detail::split;
0263
0264 } // inline namespace v1
0265 } // namespace tbb
0266
0267 #endif // __TBB_concurrent_set_H