include/tbb/concurrent_set.h

0001 /*
0002     Copyright (c) 2019-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 #ifndef __TBB_concurrent_set_H
0018 #define __TBB_concurrent_set_H
0019
0020 #define __TBB_concurrent_set_H_include_area
0021 #include "internal/_warning_suppress_enable_notice.h"
0022
0023 #if !TBB_PREVIEW_CONCURRENT_ORDERED_CONTAINERS
0024 #error Set TBB_PREVIEW_CONCURRENT_ORDERED_CONTAINERS to include concurrent_set.h
0025 #endif
0026
0027 #include "tbb/tbb_config.h"
0028
0029 // concurrent_set requires C++11 support
0030 #if __TBB_CONCURRENT_ORDERED_CONTAINERS_PRESENT
0031
0032 #include "internal/_concurrent_skip_list_impl.h"
0033
0034 namespace tbb {
0035 namespace interface10 {
0036
0037 // TODO: test this class
0038 template<typename Key, typename KeyCompare, typename RandomGenerator, size_t MAX_LEVELS, typename Allocator, bool AllowMultimapping>
0039 class set_traits {
0040 public:
0041     static constexpr size_t MAX_LEVEL = MAX_LEVELS;
0042     using random_level_generator_type = RandomGenerator;
0043     using key_type = Key;
0044     using value_type = key_type;
0045     using compare_type = KeyCompare;
0046     using value_compare = compare_type;
0047     using reference = value_type & ;
0048     using const_reference = const value_type&;
0049     using allocator_type = Allocator;
0050     using mutex_type = tbb::spin_mutex;
0051     using node_type = tbb::internal::node_handle<key_type, value_type, internal::skip_list_node<value_type, mutex_type>, allocator_type>;
0052
0053     static const bool allow_multimapping = AllowMultimapping;
0054
0055     static const key_type& get_key(const_reference val) {
0056         return val;
0057     }
0058
0059     static value_compare value_comp(compare_type comp) { return comp; }
0060 };
0061
0062 template <typename Key, typename Comp, typename Allocator>
0063 class concurrent_multiset;
0064
0065 template <typename Key, typename Comp = std::less<Key>, typename Allocator = tbb_allocator<Key>>
0066 class concurrent_set
0067     : public internal::concurrent_skip_list<set_traits<Key, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, false>> {
0068     using traits_type = set_traits<Key, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, false>;
0069     using base_type = internal::concurrent_skip_list<traits_type>;
0070 #if __TBB_EXTRA_DEBUG
0071 public:
0072 #endif
0073     using base_type::allow_multimapping;
0074 public:
0075     using key_type = Key;
0076     using value_type = typename traits_type::value_type;
0077     using size_type = typename base_type::size_type;
0078     using difference_type = typename base_type::difference_type;
0079     using key_compare = Comp;
0080     using value_compare = typename base_type::value_compare;
0081     using allocator_type = Allocator;
0082
0083     using reference = typename base_type::reference;
0084     using const_reference = typename base_type::const_reference;
0085     using pointer = typename base_type::pointer;
0086     using const_pointer = typename base_type::pointer;
0087
0088     using iterator = typename base_type::iterator;
0089     using const_iterator = typename base_type::const_iterator;
0090     using reverse_iterator = typename base_type::reverse_iterator;
0091     using const_reverse_iterator = typename base_type::const_reverse_iterator;
0092
0093     using node_type = typename base_type::node_type;
0094
0095     using base_type::insert;
0096
0097     concurrent_set() = default;
0098
0099     explicit concurrent_set(const key_compare& comp, const allocator_type& alloc = allocator_type()) : base_type(comp, alloc) {}
0100
0101     explicit concurrent_set(const allocator_type& alloc) : base_type(key_compare(), alloc) {}
0102
0103     template< class InputIt >
0104     concurrent_set(InputIt first, InputIt last, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
0105         : base_type(first, last, comp, alloc) {}
0106
0107     template< class InputIt >
0108     concurrent_set(InputIt first, InputIt last, const allocator_type& alloc) : base_type(first, last, key_compare(), alloc) {}
0109
0110     /** Copy constructor */
0111     concurrent_set(const concurrent_set&) = default;
0112
0113     concurrent_set(const concurrent_set& other, const allocator_type& alloc) : base_type(other, alloc) {}
0114
0115     concurrent_set(concurrent_set&&) = default;
0116
0117     concurrent_set(concurrent_set&& other, const allocator_type& alloc) : base_type(std::move(other), alloc) {}
0118
0119     concurrent_set(std::initializer_list<value_type> init, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
0120         : base_type(comp, alloc) {
0121         insert(init);
0122     }
0123
0124     concurrent_set(std::initializer_list<value_type> init, const allocator_type& alloc)
0125         : base_type(key_compare(), alloc) {
0126         insert(init);
0127     }
0128
0129     concurrent_set& operator=(const concurrent_set& other) {
0130         return static_cast<concurrent_set&>(base_type::operator=(other));
0131     }
0132
0133     concurrent_set& operator=(concurrent_set&& other) {
0134         return static_cast<concurrent_set&>(base_type::operator=(std::move(other)));
0135     }
0136
0137     template<typename C2>
0138     void merge(concurrent_set<key_type, C2, Allocator>& source) {
0139         this->internal_merge(source);
0140     }
0141
0142     template<typename C2>
0143     void merge(concurrent_set<key_type, C2, Allocator>&& source) {
0144         this->internal_merge(std::move(source));
0145     }
0146
0147     template<typename C2>
0148     void merge(concurrent_multiset<key_type, C2, Allocator>& source) {
0149         this->internal_merge(source);
0150     }
0151
0152     template<typename C2>
0153     void merge(concurrent_multiset<key_type, C2, Allocator>&& source) {
0154         this->internal_merge(std::move(source));
0155     }
0156 }; // class concurrent_set
0157
0158 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0159
0160 namespace internal {
0161
0162 using namespace tbb::internal;
0163
0164 template<template<typename...> typename Set, typename Key, typename... Args>
0165 using c_set_t = Set<Key,
0166                     std::conditional_t< (sizeof...(Args) > 0) && !is_allocator_v<pack_element_t<0, Args...> >,
0167                                         pack_element_t<0, Args...>, std::less<Key> >,
0168                     std::conditional_t< (sizeof...(Args) > 0) && is_allocator_v<pack_element_t<sizeof...(Args)-1, Args...> >,
0169                                         pack_element_t<sizeof...(Args)-1, Args...>, tbb_allocator<Key> > >;
0170 } // namespace internal
0171
0172 template<typename It, typename... Args>
0173 concurrent_set(It, It, Args...)
0174 -> internal::c_set_t<concurrent_set, internal::iterator_value_t<It>, Args...>;
0175
0176 template<typename Key, typename... Args>
0177 concurrent_set(std::initializer_list<Key>, Args...)
0178 -> internal::c_set_t<concurrent_set, Key, Args...>;
0179
0180 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0181
0182 template <typename Key, typename Comp = std::less<Key>, typename Allocator = tbb_allocator<Key>>
0183 class concurrent_multiset
0184     : public internal::concurrent_skip_list<set_traits<Key, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, true>> {
0185     using traits_type = set_traits<Key, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, true>;
0186     using base_type = internal::concurrent_skip_list<traits_type>;
0187 #if __TBB_EXTRA_DEBUG
0188 public:
0189 #endif
0190     using base_type::allow_multimapping;
0191 public:
0192     using key_type = Key;
0193     using value_type = typename traits_type::value_type;
0194     using size_type = typename base_type::size_type;
0195     using difference_type = typename base_type::difference_type;
0196     using key_compare = Comp;
0197     using value_compare = typename base_type::value_compare;
0198     using allocator_type = Allocator;
0199
0200     using reference = typename base_type::reference;
0201     using const_reference = typename base_type::const_reference;
0202     using pointer = typename base_type::pointer;
0203     using const_pointer = typename base_type::pointer;
0204
0205     using iterator = typename base_type::iterator;
0206     using const_iterator = typename base_type::const_iterator;
0207     using reverse_iterator = typename base_type::reverse_iterator;
0208     using const_reverse_iterator = typename base_type::const_reverse_iterator;
0209
0210     using node_type = typename base_type::node_type;
0211
0212     using base_type::insert;
0213
0214     concurrent_multiset() = default;
0215
0216     explicit concurrent_multiset(const key_compare& comp, const allocator_type& alloc = allocator_type()) : base_type(comp, alloc) {}
0217
0218     explicit concurrent_multiset(const allocator_type& alloc) : base_type(key_compare(), alloc) {}
0219
0220     template< class InputIt >
0221     concurrent_multiset(InputIt first, InputIt last, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
0222         : base_type(comp, alloc) {
0223         insert(first, last);
0224     }
0225
0226     template< class InputIt >
0227     concurrent_multiset(InputIt first, InputIt last, const allocator_type& alloc) : base_type(key_compare(), alloc) {
0228         insert(first, last);
0229     }
0230
0231     /** Copy constructor */
0232     concurrent_multiset(const concurrent_multiset&) = default;
0233
0234     concurrent_multiset(const concurrent_multiset& other, const allocator_type& alloc) : base_type(other, alloc) {}
0235
0236     concurrent_multiset(concurrent_multiset&&) = default;
0237
0238     concurrent_multiset(concurrent_multiset&& other, const allocator_type& alloc) : base_type(std::move(other), alloc) {}
0239
0240     concurrent_multiset(std::initializer_list<value_type> init, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
0241         : base_type(comp, alloc) {
0242         insert(init);
0243     }
0244
0245     concurrent_multiset(std::initializer_list<value_type> init, const allocator_type& alloc)
0246         : base_type(key_compare(), alloc) {
0247         insert(init);
0248     }
0249
0250     concurrent_multiset& operator=(const concurrent_multiset& other) {
0251         return static_cast<concurrent_multiset&>(base_type::operator=(other));
0252     }
0253
0254     concurrent_multiset& operator=(concurrent_multiset&& other) {
0255         return static_cast<concurrent_multiset&>(base_type::operator=(std::move(other)));
0256     }
0257
0258     template<typename C2>
0259     void merge(concurrent_set<key_type, C2, Allocator>& source) {
0260         this->internal_merge(source);
0261     }
0262
0263     template<typename C2>
0264     void merge(concurrent_set<key_type, C2, Allocator>&& source) {
0265         this->internal_merge(std::move(source));
0266     }
0267
0268     template<typename C2>
0269     void merge(concurrent_multiset<key_type, C2, Allocator>& source) {
0270         this->internal_merge(source);
0271     }
0272
0273     template<typename C2>
0274     void merge(concurrent_multiset<key_type, C2, Allocator>&& source) {
0275         this->internal_merge(std::move(source));
0276     }
0277 }; // class concurrent_multiset
0278
0279 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0280
0281
0282 template<typename It, typename... Args>
0283 concurrent_multiset(It, It, Args...)
0284 -> internal::c_set_t<concurrent_multiset, internal::iterator_value_t<It>, Args...>;
0285
0286 template<typename Key, typename... Args>
0287 concurrent_multiset(std::initializer_list<Key>, Args...)
0288 -> internal::c_set_t<concurrent_multiset, Key, Args...>;
0289
0290 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0291
0292 } // namespace interface10
0293
0294 using interface10::concurrent_set;
0295 using interface10::concurrent_multiset;
0296
0297 } // namespace tbb
0298
0299 #endif // __TBB_CONCURRENT_ORDERED_CONTAINERS_PRESENT
0300
0301 #include "internal/_warning_suppress_disable_notice.h"
0302 #undef __TBB_concurrent_set_H_include_area
0303
0304 #endif // __TBB_concurrent_set_H