1 /* 2 Copyright (c) 2019-2021 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 d2 { 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 // Required for implicit deduction guides 98 concurrent_map() = default; 99 concurrent_map( const concurrent_map& ) = default; 100 concurrent_map( const concurrent_map& other, const allocator_type& alloc ) : base_type(other, alloc) {} 101 concurrent_map( concurrent_map&& ) = default; 102 concurrent_map( concurrent_map&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {} 103 // Required to respect the rule of 5 104 concurrent_map& operator=( const concurrent_map& ) = default; 105 concurrent_map& operator=( concurrent_map&& ) = default; 106 107 // Observers 108 mapped_type& at(const key_type& key) { 109 iterator it = this->find(key); 110 111 if (it == this->end()) { 112 throw_exception(exception_id::invalid_key); 113 } 114 return it->second; 115 } 116 117 const mapped_type& at(const key_type& key) const { 118 return const_cast<concurrent_map*>(this)->at(key); 119 } 120 121 mapped_type& operator[](const key_type& key) { 122 iterator it = this->find(key); 123 124 if (it == this->end()) { 125 it = this->emplace(std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>()).first; 126 } 127 return it->second; 128 } 129 130 mapped_type& operator[](key_type&& key) { 131 iterator it = this->find(key); 132 133 if (it == this->end()) { 134 it = this->emplace(std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>()).first; 135 } 136 return it->second; 137 } 138 139 using base_type::insert; 140 141 template <typename P> 142 typename std::enable_if<std::is_constructible<value_type, P&&>::value, 143 std::pair<iterator, bool>>::type insert( P&& value ) 144 { 145 return this->emplace(std::forward<P>(value)); 146 } 147 148 template <typename P> 149 typename std::enable_if<std::is_constructible<value_type, P&&>::value, 150 iterator>::type insert( const_iterator hint, P&& value ) 151 { 152 return this->emplace_hint(hint, std::forward<P>(value)); 153 } 154 155 template<typename OtherCompare> 156 void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>& source) { 157 this->internal_merge(source); 158 } 159 160 template<typename OtherCompare> 161 void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>&& source) { 162 this->internal_merge(std::move(source)); 163 } 164 165 template<typename OtherCompare> 166 void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>& source) { 167 this->internal_merge(source); 168 } 169 170 template<typename OtherCompare> 171 void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>&& source) { 172 this->internal_merge(std::move(source)); 173 } 174 }; // class concurrent_map 175 176 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 177 178 template <typename It, 179 typename Comp = std::less<iterator_key_t<It>>, 180 typename Alloc = tbb::tbb_allocator<iterator_alloc_pair_t<It>>, 181 typename = std::enable_if_t<is_input_iterator_v<It>>, 182 typename = std::enable_if_t<is_allocator_v<Alloc>>, 183 typename = std::enable_if_t<!is_allocator_v<Comp>>> 184 concurrent_map( It, It, Comp = Comp(), Alloc = Alloc() ) 185 -> concurrent_map<iterator_key_t<It>, iterator_mapped_t<It>, Comp, Alloc>; 186 187 template <typename Key, typename T, 188 typename Comp = std::less<std::remove_const_t<Key>>, 189 typename Alloc = tbb::tbb_allocator<std::pair<const Key, T>>, 190 typename = std::enable_if_t<is_allocator_v<Alloc>>, 191 typename = std::enable_if_t<!is_allocator_v<Comp>>> 192 concurrent_map( std::initializer_list<std::pair<Key, T>>, Comp = Comp(), Alloc = Alloc() ) 193 -> concurrent_map<std::remove_const_t<Key>, T, Comp, Alloc>; 194 195 template <typename It, typename Alloc, 196 typename = std::enable_if_t<is_input_iterator_v<It>>, 197 typename = std::enable_if_t<is_allocator_v<Alloc>>> 198 concurrent_map( It, It, Alloc ) 199 -> concurrent_map<iterator_key_t<It>, iterator_mapped_t<It>, 200 std::less<iterator_key_t<It>>, Alloc>; 201 202 template <typename Key, typename T, typename Alloc, 203 typename = std::enable_if_t<is_allocator_v<Alloc>>> 204 concurrent_map( std::initializer_list<std::pair<Key, T>>, Alloc ) 205 -> concurrent_map<std::remove_const_t<Key>, T, std::less<std::remove_const_t<Key>>, Alloc>; 206 207 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 208 209 template <typename Key, typename Value, typename Compare, typename Allocator> 210 void swap( concurrent_map<Key, Value, Compare, Allocator>& lhs, 211 concurrent_map<Key, Value, Compare, Allocator>& rhs ) 212 { 213 lhs.swap(rhs); 214 } 215 216 template <typename Key, typename Value, typename Compare = std::less<Key>, typename Allocator = tbb::tbb_allocator<std::pair<const Key, Value>>> 217 class concurrent_multimap : public concurrent_skip_list<map_traits<Key, Value, Compare, concurrent_geometric_level_generator<32>, Allocator, true>> { 218 using base_type = concurrent_skip_list<map_traits<Key, Value, Compare, concurrent_geometric_level_generator<32>, Allocator, true>>; 219 public: 220 using key_type = Key; 221 using mapped_type = Value; 222 using value_type = typename base_type::value_type; 223 using size_type = typename base_type::size_type; 224 using difference_type = typename base_type::difference_type; 225 using key_compare = Compare; 226 using value_compare = typename base_type::value_compare; 227 using allocator_type = Allocator; 228 229 using reference = typename base_type::reference; 230 using const_reference = typename base_type::const_reference; 231 using pointer = typename base_type::pointer; 232 using const_pointer = typename base_type::const_pointer; 233 234 using iterator = typename base_type::iterator; 235 using const_iterator = typename base_type::const_iterator; 236 237 using node_type = typename base_type::node_type; 238 239 // Include constructors of base_type 240 using base_type::base_type; 241 using base_type::insert; 242 using base_type::operator=; 243 244 // Required for implicit deduction guides 245 concurrent_multimap() = default; 246 concurrent_multimap( const concurrent_multimap& ) = default; 247 concurrent_multimap( const concurrent_multimap& other, const allocator_type& alloc ) : base_type(other, alloc) {} 248 concurrent_multimap( concurrent_multimap&& ) = default; 249 concurrent_multimap( concurrent_multimap&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {} 250 // Required to respect the rule of 5 251 concurrent_multimap& operator=( const concurrent_multimap& ) = default; 252 concurrent_multimap& operator=( concurrent_multimap&& ) = default; 253 254 template <typename P> 255 typename std::enable_if<std::is_constructible<value_type, P&&>::value, 256 std::pair<iterator, bool>>::type insert( P&& value ) 257 { 258 return this->emplace(std::forward<P>(value)); 259 } 260 261 template <typename P> 262 typename std::enable_if<std::is_constructible<value_type, P&&>::value, 263 iterator>::type insert( const_iterator hint, P&& value ) 264 { 265 return this->emplace_hint(hint, std::forward<P>(value)); 266 } 267 268 template<typename OtherCompare> 269 void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>& source) { 270 this->internal_merge(source); 271 } 272 273 template<typename OtherCompare> 274 void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>&& source) { 275 this->internal_merge(std::move(source)); 276 } 277 278 template<typename OtherCompare> 279 void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>& source) { 280 this->internal_merge(source); 281 } 282 283 template<typename OtherCompare> 284 void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>&& source) { 285 this->internal_merge(std::move(source)); 286 } 287 }; // class concurrent_multimap 288 289 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 290 291 template <typename It, 292 typename Comp = std::less<iterator_key_t<It>>, 293 typename Alloc = tbb::tbb_allocator<iterator_alloc_pair_t<It>>, 294 typename = std::enable_if_t<is_input_iterator_v<It>>, 295 typename = std::enable_if_t<is_allocator_v<Alloc>>, 296 typename = std::enable_if_t<!is_allocator_v<Comp>>> 297 concurrent_multimap( It, It, Comp = Comp(), Alloc = Alloc() ) 298 -> concurrent_multimap<iterator_key_t<It>, iterator_mapped_t<It>, Comp, Alloc>; 299 300 template <typename Key, typename T, 301 typename Comp = std::less<std::remove_const_t<Key>>, 302 typename Alloc = tbb::tbb_allocator<std::pair<const Key, T>>, 303 typename = std::enable_if_t<is_allocator_v<Alloc>>, 304 typename = std::enable_if_t<!is_allocator_v<Comp>>> 305 concurrent_multimap( std::initializer_list<std::pair<Key, T>>, Comp = Comp(), Alloc = Alloc() ) 306 -> concurrent_multimap<std::remove_const_t<Key>, T, Comp, Alloc>; 307 308 template <typename It, typename Alloc, 309 typename = std::enable_if_t<is_input_iterator_v<It>>, 310 typename = std::enable_if_t<is_allocator_v<Alloc>>> 311 concurrent_multimap( It, It, Alloc ) 312 -> concurrent_multimap<iterator_key_t<It>, iterator_mapped_t<It>, 313 std::less<iterator_key_t<It>>, Alloc>; 314 315 template <typename Key, typename T, typename Alloc, 316 typename = std::enable_if_t<is_allocator_v<Alloc>>> 317 concurrent_multimap( std::initializer_list<std::pair<Key, T>>, Alloc ) 318 -> concurrent_multimap<std::remove_const_t<Key>, T, std::less<std::remove_const_t<Key>>, Alloc>; 319 320 321 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 322 323 template <typename Key, typename Value, typename Compare, typename Allocator> 324 void swap( concurrent_multimap<Key, Value, Compare, Allocator>& lhs, 325 concurrent_multimap<Key, Value, Compare, Allocator>& rhs ) 326 { 327 lhs.swap(rhs); 328 } 329 330 } // namespace d2 331 } // namespace detail 332 333 inline namespace v1 { 334 335 using detail::d2::concurrent_map; 336 using detail::d2::concurrent_multimap; 337 using detail::split; 338 339 } // inline namespace v1 340 } // namespace tbb 341 342 #endif // __TBB_concurrent_map_H 343