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

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.