xref: /oneTBB/include/oneapi/tbb/concurrent_map.h (revision 8dcbd5b1) 
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 #include "detail/_namespace_injection.h"
21 #include "detail/_concurrent_skip_list.h"
22 #include "tbb_allocator.h"
23 #include <functional>
24 #include <tuple>
25 #include <utility>
26 
27 namespace tbb {
28 namespace detail {
29 namespace d1 {
30 
31 template<typename Key, typename Value, typename KeyCompare, typename RandomGenerator,
32          typename Allocator, bool AllowMultimapping>
33 struct map_traits {
34     static constexpr std::size_t max_level = RandomGenerator::max_level;
35     using random_level_generator_type = RandomGenerator;
36     using key_type = Key;
37     using mapped_type = Value;
38     using compare_type = KeyCompare;
39     using value_type = std::pair<const key_type, mapped_type>;
40     using reference = value_type&;
41     using const_reference = const value_type&;
42     using allocator_type = Allocator;
43 
44     static constexpr bool allow_multimapping = AllowMultimapping;
45 
46     class value_compare {
47     public:
48         bool operator()(const value_type& lhs, const value_type& rhs) const {
49             return comp(lhs.first, rhs.first);
50         }
51 
52     protected:
53         value_compare(compare_type c) : comp(c) {}
54 
55         friend struct map_traits;
56 
57         compare_type comp;
58     };
59 
60     static value_compare value_comp(compare_type comp) { return value_compare(comp); }
61 
62     static const key_type& get_key(const_reference val) {
63         return val.first;
64     }
65 }; // struct map_traits
66 
67 template <typename Key, typename Value, typename Compare, typename Allocator>
68 class concurrent_multimap;
69 
70 template <typename Key, typename Value, typename Compare = std::less<Key>, typename Allocator = tbb::tbb_allocator<std::pair<const Key, Value>>>
71 class concurrent_map : public concurrent_skip_list<map_traits<Key, Value, Compare, concurrent_geometric_level_generator<32>, Allocator, false>> {
72     using base_type = concurrent_skip_list<map_traits<Key, Value, Compare, concurrent_geometric_level_generator<32>, Allocator, false>>;
73 public:
74     using key_type = Key;
75     using mapped_type = Value;
76     using value_type = typename base_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 = Compare;
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::const_pointer;
87 
88     using iterator = typename base_type::iterator;
89     using const_iterator = typename base_type::const_iterator;
90 
91     using node_type = typename base_type::node_type;
92 
93     // Include constructors of base type
94     using base_type::base_type;
95     using base_type::operator=;
96 
97     // Observers
98     mapped_type& at(const key_type& key) {
99         iterator it = this->find(key);
100 
101         if (it == this->end()) {
102             throw_exception(exception_id::invalid_key);
103         }
104         return it->second;
105     }
106 
107     const mapped_type& at(const key_type& key) const {
108         return const_cast<concurrent_map*>(this)->at(key);
109     }
110 
111     mapped_type& operator[](const key_type& key) {
112         iterator it = this->find(key);
113 
114         if (it == this->end()) {
115             it = this->emplace(std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>()).first;
116         }
117         return it->second;
118     }
119 
120     mapped_type& operator[](key_type&& key) {
121         iterator it = this->find(key);
122 
123         if (it == this->end()) {
124             it = this->emplace(std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>()).first;
125         }
126         return it->second;
127     }
128 
129     using base_type::insert;
130 
131     template <typename P>
132     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
133                             std::pair<iterator, bool>>::type insert( P&& value )
134     {
135         return this->emplace(std::forward<P>(value));
136     }
137 
138     template <typename P>
139     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
140                             iterator>::type insert( const_iterator hint, P&& value )
141     {
142         return this->emplace_hint(hint, std::forward<P>(value));
143     }
144 
145     template<typename OtherCompare>
146     void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>& source) {
147         this->internal_merge(source);
148     }
149 
150     template<typename OtherCompare>
151     void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>&& source) {
152         this->internal_merge(std::move(source));
153     }
154 
155     template<typename OtherCompare>
156     void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>& source) {
157         this->internal_merge(source);
158     }
159 
160     template<typename OtherCompare>
161     void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>&& source) {
162         this->internal_merge(std::move(source));
163     }
164 }; // class concurrent_map
165 
166 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
167 
168 template<template<typename...> typename Map, typename Key, typename T, typename... Args>
169 using ordered_map_type = Map<Key, T,
170                              std::conditional_t< (sizeof...(Args) > 0) && !is_allocator_v<pack_element_t<0, Args...>>,
171                                                  pack_element_t<0, Args...>,
172                                                  std::less<Key>>,
173                              std::conditional_t< (sizeof...(Args) > 0) && is_allocator_v<pack_element_t<sizeof...(Args) - 1, Args...>>,
174                                                  pack_element_t<sizeof...(Args) - 1, Args...>,
175                                                  tbb::tbb_allocator<std::pair<const Key, T> > > >;
176 
177 template<typename It, typename... Args>
178 concurrent_map(It, It, Args...)
179 -> ordered_map_type<concurrent_map, iterator_key_t<It>, iterator_mapped_t<It>, Args...>;
180 
181 template<typename Key, typename T, typename... Args>
182 concurrent_map(std::initializer_list<std::pair<const Key, T>>, Args...)
183 -> ordered_map_type<concurrent_map, Key, T, Args...>;
184 
185 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
186 
187 template <typename Key, typename Value, typename Compare, typename Allocator>
188 void swap( concurrent_map<Key, Value, Compare, Allocator>& lhs,
189            concurrent_map<Key, Value, Compare, Allocator>& rhs )
190 {
191     lhs.swap(rhs);
192 }
193 
194 template <typename Key, typename Value, typename Compare = std::less<Key>, typename Allocator = tbb::tbb_allocator<std::pair<const Key, Value>>>
195 class concurrent_multimap : public concurrent_skip_list<map_traits<Key, Value, Compare, concurrent_geometric_level_generator<32>, Allocator, true>> {
196     using base_type = concurrent_skip_list<map_traits<Key, Value, Compare, concurrent_geometric_level_generator<32>, Allocator, true>>;
197 public:
198     using key_type = Key;
199     using mapped_type = Value;
200     using value_type = typename base_type::value_type;
201     using size_type = typename base_type::size_type;
202     using difference_type = typename base_type::difference_type;
203     using key_compare = Compare;
204     using value_compare = typename base_type::value_compare;
205     using allocator_type = Allocator;
206 
207     using reference = typename base_type::reference;
208     using const_reference = typename base_type::const_reference;
209     using pointer = typename base_type::pointer;
210     using const_pointer = typename base_type::const_pointer;
211 
212     using iterator = typename base_type::iterator;
213     using const_iterator = typename base_type::const_iterator;
214 
215     using node_type = typename base_type::node_type;
216 
217     // Include constructors of base_type
218     using base_type::base_type;
219     using base_type::insert;
220     using base_type::operator=;
221 
222     template <typename P>
223     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
224                             std::pair<iterator, bool>>::type insert( P&& value )
225     {
226         return this->emplace(std::forward<P>(value));
227     }
228 
229     template <typename P>
230     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
231                             iterator>::type insert( const_iterator hint, P&& value )
232     {
233         return this->emplace_hint(hint, std::forward<P>(value));
234     }
235 
236     template<typename OtherCompare>
237     void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>& source) {
238         this->internal_merge(source);
239     }
240 
241     template<typename OtherCompare>
242     void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>&& source) {
243         this->internal_merge(std::move(source));
244     }
245 
246     template<typename OtherCompare>
247     void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>& source) {
248         this->internal_merge(source);
249     }
250 
251     template<typename OtherCompare>
252     void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>&& source) {
253         this->internal_merge(std::move(source));
254     }
255 }; // class concurrent_multimap
256 
257 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
258 
259 template<typename It, typename... Args>
260 concurrent_multimap(It, It, Args...)
261 -> ordered_map_type<concurrent_multimap, iterator_key_t<It>, iterator_mapped_t<It>, Args...>;
262 
263 template<typename Key, typename T, typename... Args>
264 concurrent_multimap(std::initializer_list<std::pair<const Key, T>>, Args...)
265 -> ordered_map_type<concurrent_multimap, Key, T, Args...>;
266 
267 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
268 
269 template <typename Key, typename Value, typename Compare, typename Allocator>
270 void swap( concurrent_multimap<Key, Value, Compare, Allocator>& lhs,
271            concurrent_multimap<Key, Value, Compare, Allocator>& rhs )
272 {
273     lhs.swap(rhs);
274 }
275 
276 } // namespace d1
277 } // namespace detail
278 
279 inline namespace v1 {
280 
281 using detail::d1::concurrent_map;
282 using detail::d1::concurrent_multimap;
283 using detail::split;
284 
285 } // inline namespace v1
286 } // namespace tbb
287 
288 #endif // __TBB_concurrent_map_H
289