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

Copyright © 2005-2019 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.