Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
concurrent_map.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_map_H
18#define __TBB_concurrent_map_H
19
20#define __TBB_concurrent_map_H_include_area
22
23#if !TBB_PREVIEW_CONCURRENT_ORDERED_CONTAINERS
24#error Set TBB_PREVIEW_CONCURRENT_ORDERED_CONTAINERS to include concurrent_map.h
25#endif
26
27#include "tbb_config.h"
28
29// concurrent_map requires C++11 support
30#if __TBB_CONCURRENT_ORDERED_CONTAINERS_PRESENT
31
33
34namespace tbb {
35
36namespace interface10 {
37
38template<typename Key, typename Value, typename KeyCompare, typename RandomGenerator,
39 size_t MAX_LEVELS, typename Allocator, bool AllowMultimapping>
40class map_traits {
41public:
42 static constexpr size_t MAX_LEVEL = MAX_LEVELS;
43 using random_level_generator_type = RandomGenerator;
44 using key_type = Key;
45 using mapped_type = Value;
46 using compare_type = KeyCompare;
47 using value_type = std::pair<const key_type, mapped_type>;
48 using reference = value_type&;
49 using const_reference = const value_type&;
50 using allocator_type = Allocator;
51 using mutex_type = tbb::spin_mutex;
53
54 static const bool allow_multimapping = AllowMultimapping;
55
56 class value_compare {
57 public:
58 // TODO: these member types are deprecated in C++17, do we need to let them
59 using result_type = bool;
60 using first_argument_type = value_type;
61 using second_argument_type = value_type;
62
63 bool operator()(const value_type& lhs, const value_type& rhs) const {
64 return comp(lhs.first, rhs.first);
65 }
66
67 protected:
68 value_compare(compare_type c) : comp(c) {}
69
70 friend class map_traits;
71
72 compare_type comp;
73 };
74
75 static value_compare value_comp(compare_type comp) { return value_compare(comp); }
76
77 static const key_type& get_key(const_reference val) {
78 return val.first;
79 }
80}; // class map_traits
81
82template <typename Key, typename Value, typename Comp, typename Allocator>
83class concurrent_multimap;
84
85template <typename Key, typename Value, typename Comp = std::less<Key>, typename Allocator = tbb_allocator<std::pair<const Key, Value>>>
86class concurrent_map
87 : public internal::concurrent_skip_list<map_traits<Key, Value, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, false>> {
88 using traits_type = map_traits<Key, Value, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, false>;
89 using base_type = internal::concurrent_skip_list<traits_type>;
90#if __TBB_EXTRA_DEBUG
91public:
92#endif
93 using base_type::allow_multimapping;
94public:
95 using key_type = Key;
96 using mapped_type = Value;
97 using value_type = typename traits_type::value_type;
98 using size_type = typename base_type::size_type;
99 using difference_type = typename base_type::difference_type;
100 using key_compare = Comp;
101 using value_compare = typename base_type::value_compare;
102 using allocator_type = Allocator;
103
104 using reference = typename base_type::reference;
105 using const_reference = typename base_type::const_reference;
106 using pointer = typename base_type::pointer;
107 using const_pointer = typename base_type::pointer;
108
109 using iterator = typename base_type::iterator;
110 using const_iterator = typename base_type::const_iterator;
111 using reverse_iterator = typename base_type::reverse_iterator;
112 using const_reverse_iterator = typename base_type::const_reverse_iterator;
113
114 using node_type = typename base_type::node_type;
115
116 using base_type::end;
117 using base_type::find;
118 using base_type::emplace;
119 using base_type::insert;
120
121 concurrent_map() = default;
122
123 explicit concurrent_map(const key_compare& comp, const allocator_type& alloc = allocator_type()) : base_type(comp, alloc) {}
124
125 explicit concurrent_map(const allocator_type& alloc) : base_type(key_compare(), alloc) {}
126
127 template< class InputIt >
128 concurrent_map(InputIt first, InputIt last, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
129 : base_type(first, last, comp, alloc) {}
130
131 template< class InputIt >
132 concurrent_map(InputIt first, InputIt last, const allocator_type& alloc) : base_type(first, last, key_compare(), alloc) {}
133
135 concurrent_map(const concurrent_map&) = default;
136
137 concurrent_map(const concurrent_map& other, const allocator_type& alloc) : base_type(other, alloc) {}
138
139 concurrent_map(concurrent_map&&) = default;
140
141 concurrent_map(concurrent_map&& other, const allocator_type& alloc) : base_type(std::move(other), alloc) {}
142
143 concurrent_map(std::initializer_list<value_type> init, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
144 : base_type(comp, alloc) {
145 insert(init);
146 }
147
148 concurrent_map(std::initializer_list<value_type> init, const allocator_type& alloc)
149 : base_type(key_compare(), alloc) {
150 insert(init);
151 }
152
153 concurrent_map& operator=(const concurrent_map& other) {
154 return static_cast<concurrent_map&>(base_type::operator=(other));
155 }
156
157 concurrent_map& operator=(concurrent_map&& other) {
158 return static_cast<concurrent_map&>(base_type::operator=(std::move(other)));
159 }
160
161 mapped_type& at(const key_type& key) {
162 iterator it = find(key);
163
164 if (it == end()) {
166 }
167
168 return it->second;
169 }
170
171 const mapped_type& at(const key_type& key) const {
172 const_iterator it = find(key);
173
174 if (it == end()) {
176 }
177
178 return it->second;
179 }
180
181 mapped_type& operator[](const key_type& key) {
182 iterator it = find(key);
183
184 if (it == end()) {
185 it = emplace(std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>()).first;
186 }
187
188 return it->second;
189 }
190
191 mapped_type& operator[](key_type&& key) {
192 iterator it = find(key);
193
194 if (it == end()) {
195 it = emplace(std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>()).first;
196 }
197
198 return it->second;
199 }
200
202 std::pair<iterator, bool> insert(P&& value) {
203 return emplace(std::forward<P>(value));
204 }
205
207 iterator insert(const_iterator hint, P&& value) {
208 return emplace_hint(hint, std::forward<P>(value));
209 return end();
210 }
211
212 template<typename C2>
213 void merge(concurrent_map<key_type, mapped_type, C2, Allocator>& source) {
214 this->internal_merge(source);
215 }
216
217 template<typename C2>
218 void merge(concurrent_map<key_type, mapped_type, C2, Allocator>&& source) {
219 this->internal_merge(std::move(source));
220 }
221
222 template<typename C2>
223 void merge(concurrent_multimap<key_type, mapped_type, C2, Allocator>& source) {
224 this->internal_merge(source);
225 }
226
227 template<typename C2>
228 void merge(concurrent_multimap<key_type, mapped_type, C2, Allocator>&& source) {
229 this->internal_merge(std::move(source));
230 }
231}; // class concurrent_map
232
233#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
234
235namespace internal {
236
237using namespace tbb::internal;
238
239template<template<typename...> typename Map, typename Key, typename T, typename... Args>
240using c_map_t = Map<Key, T,
241 std::conditional_t< (sizeof...(Args) > 0) && !is_allocator_v<pack_element_t<0, Args...> >,
242 pack_element_t<0, Args...>, std::less<Key> >,
243 std::conditional_t< (sizeof...(Args) > 0) && is_allocator_v<pack_element_t<sizeof...(Args)-1, Args...> >,
244 pack_element_t<sizeof...(Args)-1, Args...>, tbb_allocator<std::pair<const Key, T> > > >;
245} // namespace internal
246
247template<typename It, typename... Args>
248concurrent_map(It, It, Args...)
249-> internal::c_map_t<concurrent_map, internal::iterator_key_t<It>, internal::iterator_mapped_t<It>, Args...>;
250
251template<typename Key, typename T, typename... Args>
252concurrent_map(std::initializer_list<std::pair<const Key, T>>, Args...)
253-> internal::c_map_t<concurrent_map, Key, T, Args...>;
254
255#endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
256
257template <typename Key, typename Value, typename Comp = std::less<Key>, typename Allocator = tbb_allocator<std::pair<const Key, Value>>>
258class concurrent_multimap
259 : public internal::concurrent_skip_list<map_traits<Key, Value, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, true>> {
260 using traits_type = map_traits<Key, Value, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, true>;
261 using base_type = internal::concurrent_skip_list<traits_type>;
262#if __TBB_EXTRA_DEBUG
263public:
264#endif
265 using base_type::allow_multimapping;
266public:
267 using key_type = Key;
268 using mapped_type = Value;
269 using value_type = typename traits_type::value_type;
270 using size_type = typename base_type::size_type;
271 using difference_type = typename base_type::difference_type;
272 using key_compare = Comp;
273 using value_compare = typename base_type::value_compare;
274 using allocator_type = Allocator;
275
276 using reference = typename base_type::reference;
277 using const_reference = typename base_type::const_reference;
278 using pointer = typename base_type::pointer;
279 using const_pointer = typename base_type::pointer;
280
281 using iterator = typename base_type::iterator;
282 using const_iterator = typename base_type::const_iterator;
283 using reverse_iterator = typename base_type::reverse_iterator;
284 using const_reverse_iterator = typename base_type::const_reverse_iterator;
285
286 using node_type = typename base_type::node_type;
287
288 using base_type::end;
289 using base_type::find;
290 using base_type::emplace;
291 using base_type::insert;
292
293 concurrent_multimap() = default;
294
295 explicit concurrent_multimap(const key_compare& comp, const allocator_type& alloc = allocator_type()) : base_type(comp, alloc) {}
296
297 explicit concurrent_multimap(const allocator_type& alloc) : base_type(key_compare(), alloc) {}
298
299 template< class InputIt >
300 concurrent_multimap(InputIt first, InputIt last, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
301 : base_type(first, last, comp, alloc) {}
302
303 template< class InputIt >
304 concurrent_multimap(InputIt first, InputIt last, const allocator_type& alloc) : base_type(first, last, key_compare(), alloc) {}
305
307 concurrent_multimap(const concurrent_multimap&) = default;
308
309 concurrent_multimap(const concurrent_multimap& other, const allocator_type& alloc) : base_type(other, alloc) {}
310
311 concurrent_multimap(concurrent_multimap&&) = default;
312
313 concurrent_multimap(concurrent_multimap&& other, const allocator_type& alloc) : base_type(std::move(other), alloc) {}
314
315 concurrent_multimap(std::initializer_list<value_type> init, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
316 : base_type(comp, alloc) {
317 insert(init);
318 }
319
320 concurrent_multimap(std::initializer_list<value_type> init, const allocator_type& alloc)
321 : base_type(key_compare(), alloc) {
322 insert(init);
323 }
324
325 concurrent_multimap& operator=(const concurrent_multimap& other) {
326 return static_cast<concurrent_multimap&>(base_type::operator=(other));
327 }
328
329 concurrent_multimap& operator=(concurrent_multimap&& other) {
330 return static_cast<concurrent_multimap&>(base_type::operator=(std::move(other)));
331 }
332
334 std::pair<iterator, bool> insert(P&& value) {
335 return emplace(std::forward<P>(value));
336 }
337
339 iterator insert(const_iterator hint, P&& value) {
340 return emplace_hint(hint, std::forward<P>(value));
341 return end();
342 }
343
344 template<typename C2>
345 void merge(concurrent_multimap<key_type, mapped_type, C2, Allocator>& source) {
346 this->internal_merge(source);
347 }
348
349 template<typename C2>
350 void merge(concurrent_multimap<key_type, mapped_type, C2, Allocator>&& source) {
351 this->internal_merge(std::move(source));
352 }
353
354 template<typename C2>
355 void merge(concurrent_map<key_type, mapped_type, C2, Allocator>& source) {
356 this->internal_merge(source);
357 }
358
359 template<typename C2>
360 void merge(concurrent_map<key_type, mapped_type, C2, Allocator>&& source) {
361 this->internal_merge(std::move(source));
362 }
363
364}; // class concurrent_multimap
365
366#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
367
368template<typename It, typename... Args>
369concurrent_multimap(It, It, Args...)
370-> internal::c_map_t<concurrent_multimap, internal::iterator_key_t<It>, internal::iterator_mapped_t<It>, Args...>;
371
372template<typename Key, typename T, typename... Args>
373concurrent_multimap(std::initializer_list<std::pair<const Key, T>>, Args...)
374-> internal::c_map_t<concurrent_multimap, Key, T, Args...>;
375
376#endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
377
378} // namespace interface10
379
380using interface10::concurrent_map;
381using interface10::concurrent_multimap;
382
383} // namespace tbb
384
386#undef __TBB_concurrent_map_H_include_area
387
388#endif // __TBB_CONCURRENT_ORDERED_CONTAINERS_PRESENT
389#endif // __TBB_concurrent_map_H
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp end
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle * key
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
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
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.