Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
concurrent_set.h
Go to the documentation of this file.
1/*
2 Copyright (c) 2019-2020 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_set_H
18#define __TBB_concurrent_set_H
19
20#define __TBB_concurrent_set_H_include_area
22
23#if !TBB_PREVIEW_CONCURRENT_ORDERED_CONTAINERS
24#error Set TBB_PREVIEW_CONCURRENT_ORDERED_CONTAINERS to include concurrent_set.h
25#endif
26
27#include "tbb/tbb_config.h"
28
29// concurrent_set requires C++11 support
30#if __TBB_CONCURRENT_ORDERED_CONTAINERS_PRESENT
31
33
34namespace tbb {
35namespace interface10 {
36
37// TODO: test this class
38template<typename Key, typename KeyCompare, typename RandomGenerator, size_t MAX_LEVELS, typename Allocator, bool AllowMultimapping>
39class set_traits {
40public:
41 static constexpr size_t MAX_LEVEL = MAX_LEVELS;
42 using random_level_generator_type = RandomGenerator;
43 using key_type = Key;
44 using value_type = key_type;
45 using compare_type = KeyCompare;
46 using value_compare = compare_type;
47 using reference = value_type & ;
48 using const_reference = const value_type&;
49 using allocator_type = Allocator;
50 using mutex_type = tbb::spin_mutex;
52
53 static const bool allow_multimapping = AllowMultimapping;
54
55 static const key_type& get_key(const_reference val) {
56 return val;
57 }
58
59 static value_compare value_comp(compare_type comp) { return comp; }
60};
61
62template <typename Key, typename Comp, typename Allocator>
63class concurrent_multiset;
64
65template <typename Key, typename Comp = std::less<Key>, typename Allocator = tbb_allocator<Key>>
66class concurrent_set
67 : public internal::concurrent_skip_list<set_traits<Key, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, false>> {
68 using traits_type = set_traits<Key, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, false>;
69 using base_type = internal::concurrent_skip_list<traits_type>;
70#if __TBB_EXTRA_DEBUG
71public:
72#endif
73 using base_type::allow_multimapping;
74public:
75 using key_type = Key;
76 using value_type = typename traits_type::value_type;
77 using size_type = typename base_type::size_type;
78 using difference_type = typename base_type::difference_type;
79 using key_compare = Comp;
80 using value_compare = typename base_type::value_compare;
81 using allocator_type = Allocator;
82
83 using reference = typename base_type::reference;
84 using const_reference = typename base_type::const_reference;
85 using pointer = typename base_type::pointer;
86 using const_pointer = typename base_type::pointer;
87
88 using iterator = typename base_type::iterator;
89 using const_iterator = typename base_type::const_iterator;
90 using reverse_iterator = typename base_type::reverse_iterator;
91 using const_reverse_iterator = typename base_type::const_reverse_iterator;
92
93 using node_type = typename base_type::node_type;
94
95 using base_type::insert;
96
97 concurrent_set() = default;
98
99 explicit concurrent_set(const key_compare& comp, const allocator_type& alloc = allocator_type()) : base_type(comp, alloc) {}
100
101 explicit concurrent_set(const allocator_type& alloc) : base_type(key_compare(), alloc) {}
102
103 template< class InputIt >
104 concurrent_set(InputIt first, InputIt last, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
105 : base_type(first, last, comp, alloc) {}
106
107 template< class InputIt >
108 concurrent_set(InputIt first, InputIt last, const allocator_type& alloc) : base_type(first, last, key_compare(), alloc) {}
109
111 concurrent_set(const concurrent_set&) = default;
112
113 concurrent_set(const concurrent_set& other, const allocator_type& alloc) : base_type(other, alloc) {}
114
115 concurrent_set(concurrent_set&&) = default;
116
117 concurrent_set(concurrent_set&& other, const allocator_type& alloc) : base_type(std::move(other), alloc) {}
118
119 concurrent_set(std::initializer_list<value_type> init, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
120 : base_type(comp, alloc) {
121 insert(init);
122 }
123
124 concurrent_set(std::initializer_list<value_type> init, const allocator_type& alloc)
125 : base_type(key_compare(), alloc) {
126 insert(init);
127 }
128
129 concurrent_set& operator=(const concurrent_set& other) {
130 return static_cast<concurrent_set&>(base_type::operator=(other));
131 }
132
133 concurrent_set& operator=(concurrent_set&& other) {
134 return static_cast<concurrent_set&>(base_type::operator=(std::move(other)));
135 }
136
137 template<typename C2>
138 void merge(concurrent_set<key_type, C2, Allocator>& source) {
139 this->internal_merge(source);
140 }
141
142 template<typename C2>
143 void merge(concurrent_set<key_type, C2, Allocator>&& source) {
144 this->internal_merge(std::move(source));
145 }
146
147 template<typename C2>
148 void merge(concurrent_multiset<key_type, C2, Allocator>& source) {
149 this->internal_merge(source);
150 }
151
152 template<typename C2>
153 void merge(concurrent_multiset<key_type, C2, Allocator>&& source) {
154 this->internal_merge(std::move(source));
155 }
156}; // class concurrent_set
157
158#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
159
160namespace internal {
161
162using namespace tbb::internal;
163
164template<template<typename...> typename Set, typename Key, typename... Args>
165using c_set_t = Set<Key,
166 std::conditional_t< (sizeof...(Args) > 0) && !is_allocator_v<pack_element_t<0, Args...> >,
167 pack_element_t<0, Args...>, std::less<Key> >,
168 std::conditional_t< (sizeof...(Args) > 0) && is_allocator_v<pack_element_t<sizeof...(Args)-1, Args...> >,
169 pack_element_t<sizeof...(Args)-1, Args...>, tbb_allocator<Key> > >;
170} // namespace internal
171
172template<typename It, typename... Args>
173concurrent_set(It, It, Args...)
174-> internal::c_set_t<concurrent_set, internal::iterator_value_t<It>, Args...>;
175
176template<typename Key, typename... Args>
177concurrent_set(std::initializer_list<Key>, Args...)
178-> internal::c_set_t<concurrent_set, Key, Args...>;
179
180#endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
181
182template <typename Key, typename Comp = std::less<Key>, typename Allocator = tbb_allocator<Key>>
183class concurrent_multiset
184 : public internal::concurrent_skip_list<set_traits<Key, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, true>> {
185 using traits_type = set_traits<Key, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, true>;
186 using base_type = internal::concurrent_skip_list<traits_type>;
187#if __TBB_EXTRA_DEBUG
188public:
189#endif
190 using base_type::allow_multimapping;
191public:
192 using key_type = Key;
193 using value_type = typename traits_type::value_type;
194 using size_type = typename base_type::size_type;
195 using difference_type = typename base_type::difference_type;
196 using key_compare = Comp;
197 using value_compare = typename base_type::value_compare;
198 using allocator_type = Allocator;
199
200 using reference = typename base_type::reference;
201 using const_reference = typename base_type::const_reference;
202 using pointer = typename base_type::pointer;
203 using const_pointer = typename base_type::pointer;
204
205 using iterator = typename base_type::iterator;
206 using const_iterator = typename base_type::const_iterator;
207 using reverse_iterator = typename base_type::reverse_iterator;
208 using const_reverse_iterator = typename base_type::const_reverse_iterator;
209
210 using node_type = typename base_type::node_type;
211
212 using base_type::insert;
213
214 concurrent_multiset() = default;
215
216 explicit concurrent_multiset(const key_compare& comp, const allocator_type& alloc = allocator_type()) : base_type(comp, alloc) {}
217
218 explicit concurrent_multiset(const allocator_type& alloc) : base_type(key_compare(), alloc) {}
219
220 template< class InputIt >
221 concurrent_multiset(InputIt first, InputIt last, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
222 : base_type(comp, alloc) {
223 insert(first, last);
224 }
225
226 template< class InputIt >
227 concurrent_multiset(InputIt first, InputIt last, const allocator_type& alloc) : base_type(key_compare(), alloc) {
228 insert(first, last);
229 }
230
232 concurrent_multiset(const concurrent_multiset&) = default;
233
234 concurrent_multiset(const concurrent_multiset& other, const allocator_type& alloc) : base_type(other, alloc) {}
235
236 concurrent_multiset(concurrent_multiset&&) = default;
237
238 concurrent_multiset(concurrent_multiset&& other, const allocator_type& alloc) : base_type(std::move(other), alloc) {}
239
240 concurrent_multiset(std::initializer_list<value_type> init, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
241 : base_type(comp, alloc) {
242 insert(init);
243 }
244
245 concurrent_multiset(std::initializer_list<value_type> init, const allocator_type& alloc)
246 : base_type(key_compare(), alloc) {
247 insert(init);
248 }
249
250 concurrent_multiset& operator=(const concurrent_multiset& other) {
251 return static_cast<concurrent_multiset&>(base_type::operator=(other));
252 }
253
254 concurrent_multiset& operator=(concurrent_multiset&& other) {
255 return static_cast<concurrent_multiset&>(base_type::operator=(std::move(other)));
256 }
257
258 template<typename C2>
259 void merge(concurrent_set<key_type, C2, Allocator>& source) {
260 this->internal_merge(source);
261 }
262
263 template<typename C2>
264 void merge(concurrent_set<key_type, C2, Allocator>&& source) {
265 this->internal_merge(std::move(source));
266 }
267
268 template<typename C2>
269 void merge(concurrent_multiset<key_type, C2, Allocator>& source) {
270 this->internal_merge(source);
271 }
272
273 template<typename C2>
274 void merge(concurrent_multiset<key_type, C2, Allocator>&& source) {
275 this->internal_merge(std::move(source));
276 }
277}; // class concurrent_multiset
278
279#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
280
281
282template<typename It, typename... Args>
283concurrent_multiset(It, It, Args...)
284-> internal::c_set_t<concurrent_multiset, internal::iterator_value_t<It>, Args...>;
285
286template<typename Key, typename... Args>
287concurrent_multiset(std::initializer_list<Key>, Args...)
288-> internal::c_set_t<concurrent_multiset, Key, Args...>;
289
290#endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
291
292} // namespace interface10
293
294using interface10::concurrent_set;
295using interface10::concurrent_multiset;
296
297} // namespace tbb
298
299#endif // __TBB_CONCURRENT_ORDERED_CONTAINERS_PRESENT
300
302#undef __TBB_concurrent_set_H_include_area
303
304#endif // __TBB_concurrent_set_H
The graph class.
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:319
Identifiers declared inside namespace internal should never be used directly by client code.
Definition: atomic.h:65
auto last(Container &c) -> decltype(begin(c))
auto first(Container &c) -> decltype(begin(c))
A lock that occupies a single byte.
Definition: spin_mutex.h:39
Class for determining type of std::allocator<T>::value_type.
Definition: tbb_stddef.h:471

Copyright © 2005-2020 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.