include/tbb/concurrent_map.h

   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
  29 #include "internal/_concurrent_skip_list_impl.h"
  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;
  49     using node_type = tbb::internal::node_handle<key_type, value_type, internal::skip_list_node<value_type, mutex_type>, allocator_type>;
  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
 131     /** Copy constructor */
 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()) {
 162             tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
 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()) {
 172             tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
 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
 198     template<typename P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type>
 199     std::pair<iterator, bool> insert(P&& value) {
 200         return emplace(std::forward<P>(value));
 201     }
 202
 203     template<typename P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type>
 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
 303     /** Copy constructor */
 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
 330     template<typename P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type>
 331     std::pair<iterator, bool> insert(P&& value) {
 332         return emplace(std::forward<P>(value));
 333     }
 334
 335     template<typename P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type>
 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