include/tbb/concurrent_map.h

0001 /*
0002     Copyright (c) 2019-2020 Intel Corporation
0003
0004     Licensed under the Apache License, Version 2.0 (the "License");
0005     you may not use this file except in compliance with the License.
0006     You may obtain a copy of the License at
0007
0008         http://www.apache.org/licenses/LICENSE-2.0
0009
0010     Unless required by applicable law or agreed to in writing, software
0011     distributed under the License is distributed on an "AS IS" BASIS,
0012     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013     See the License for the specific language governing permissions and
0014     limitations under the License.
0015 */
0016
0017 #ifndef __TBB_concurrent_map_H
0018 #define __TBB_concurrent_map_H
0019
0020 #define __TBB_concurrent_map_H_include_area
0021 #include "internal/_warning_suppress_enable_notice.h"
0022
0023 #if !TBB_PREVIEW_CONCURRENT_ORDERED_CONTAINERS
0024 #error Set TBB_PREVIEW_CONCURRENT_ORDERED_CONTAINERS to include concurrent_map.h
0025 #endif
0026
0027 #include "tbb_config.h"
0028
0029 // concurrent_map requires C++11 support
0030 #if __TBB_CONCURRENT_ORDERED_CONTAINERS_PRESENT
0031
0032 #include "internal/_concurrent_skip_list_impl.h"
0033
0034 namespace tbb {
0035
0036 namespace interface10 {
0037
0038 template<typename Key, typename Value, typename KeyCompare, typename RandomGenerator,
0039          size_t MAX_LEVELS, typename Allocator, bool AllowMultimapping>
0040 class map_traits {
0041 public:
0042     static constexpr size_t MAX_LEVEL = MAX_LEVELS;
0043     using random_level_generator_type = RandomGenerator;
0044     using key_type = Key;
0045     using mapped_type = Value;
0046     using compare_type = KeyCompare;
0047     using value_type = std::pair<const key_type, mapped_type>;
0048     using reference = value_type&;
0049     using const_reference = const value_type&;
0050     using allocator_type = Allocator;
0051     using mutex_type = tbb::spin_mutex;
0052     using node_type = tbb::internal::node_handle<key_type, value_type, internal::skip_list_node<value_type, mutex_type>, allocator_type>;
0053
0054     static const bool allow_multimapping = AllowMultimapping;
0055
0056     class value_compare {
0057     public:
0058         // TODO: these member types are deprecated in C++17, do we need to let them
0059         using result_type = bool;
0060         using first_argument_type = value_type;
0061         using second_argument_type = value_type;
0062
0063         bool operator()(const value_type& lhs, const value_type& rhs) const {
0064             return comp(lhs.first, rhs.first);
0065         }
0066
0067     protected:
0068         value_compare(compare_type c) : comp(c) {}
0069
0070         friend class map_traits;
0071
0072         compare_type comp;
0073     };
0074
0075     static value_compare value_comp(compare_type comp) { return value_compare(comp); }
0076
0077     static const key_type& get_key(const_reference val) {
0078         return val.first;
0079     }
0080 }; // class map_traits
0081
0082 template <typename Key, typename Value, typename Comp, typename Allocator>
0083 class concurrent_multimap;
0084
0085 template <typename Key, typename Value, typename Comp = std::less<Key>, typename Allocator = tbb_allocator<std::pair<const Key, Value>>>
0086 class concurrent_map
0087     : public internal::concurrent_skip_list<map_traits<Key, Value, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, false>> {
0088     using traits_type = map_traits<Key, Value, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, false>;
0089     using base_type = internal::concurrent_skip_list<traits_type>;
0090 #if __TBB_EXTRA_DEBUG
0091 public:
0092 #endif
0093     using base_type::allow_multimapping;
0094 public:
0095     using key_type = Key;
0096     using mapped_type = Value;
0097     using value_type = typename traits_type::value_type;
0098     using size_type = typename base_type::size_type;
0099     using difference_type = typename base_type::difference_type;
0100     using key_compare = Comp;
0101     using value_compare = typename base_type::value_compare;
0102     using allocator_type = Allocator;
0103
0104     using reference = typename base_type::reference;
0105     using const_reference = typename base_type::const_reference;
0106     using pointer = typename base_type::pointer;
0107     using const_pointer = typename base_type::pointer;
0108
0109     using iterator = typename base_type::iterator;
0110     using const_iterator = typename base_type::const_iterator;
0111     using reverse_iterator = typename base_type::reverse_iterator;
0112     using const_reverse_iterator = typename base_type::const_reverse_iterator;
0113
0114     using node_type = typename base_type::node_type;
0115
0116     using base_type::end;
0117     using base_type::find;
0118     using base_type::emplace;
0119     using base_type::insert;
0120
0121     concurrent_map() = default;
0122
0123     explicit concurrent_map(const key_compare& comp, const allocator_type& alloc = allocator_type()) : base_type(comp, alloc) {}
0124
0125     explicit concurrent_map(const allocator_type& alloc) : base_type(key_compare(), alloc) {}
0126
0127     template< class InputIt >
0128     concurrent_map(InputIt first, InputIt last, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
0129         : base_type(first, last, comp, alloc) {}
0130
0131     template< class InputIt >
0132     concurrent_map(InputIt first, InputIt last, const allocator_type& alloc) : base_type(first, last, key_compare(), alloc) {}
0133
0134     /** Copy constructor */
0135     concurrent_map(const concurrent_map&) = default;
0136
0137     concurrent_map(const concurrent_map& other, const allocator_type& alloc) : base_type(other, alloc) {}
0138
0139     concurrent_map(concurrent_map&&) = default;
0140
0141     concurrent_map(concurrent_map&& other, const allocator_type& alloc) : base_type(std::move(other), alloc) {}
0142
0143     concurrent_map(std::initializer_list<value_type> init, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
0144         : base_type(comp, alloc) {
0145         insert(init);
0146     }
0147
0148     concurrent_map(std::initializer_list<value_type> init, const allocator_type& alloc)
0149         : base_type(key_compare(), alloc) {
0150         insert(init);
0151     }
0152
0153     concurrent_map& operator=(const concurrent_map& other) {
0154         return static_cast<concurrent_map&>(base_type::operator=(other));
0155     }
0156
0157     concurrent_map& operator=(concurrent_map&& other) {
0158         return static_cast<concurrent_map&>(base_type::operator=(std::move(other)));
0159     }
0160
0161     mapped_type& at(const key_type& key) {
0162         iterator it = find(key);
0163
0164         if (it == end()) {
0165             tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
0166         }
0167
0168         return it->second;
0169     }
0170
0171     const mapped_type& at(const key_type& key) const {
0172         const_iterator it = find(key);
0173
0174         if (it == end()) {
0175             tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
0176         }
0177
0178         return it->second;
0179     }
0180
0181     mapped_type& operator[](const key_type& key) {
0182         iterator it = find(key);
0183
0184         if (it == end()) {
0185             it = emplace(std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>()).first;
0186         }
0187
0188         return it->second;
0189     }
0190
0191     mapped_type& operator[](key_type&& key) {
0192         iterator it = find(key);
0193
0194         if (it == end()) {
0195             it = emplace(std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>()).first;
0196         }
0197
0198         return it->second;
0199     }
0200
0201     template<typename P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type>
0202     std::pair<iterator, bool> insert(P&& value) {
0203         return emplace(std::forward<P>(value));
0204     }
0205
0206     template<typename P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type>
0207     iterator insert(const_iterator hint, P&& value) {
0208             return emplace_hint(hint, std::forward<P>(value));
0209         return end();
0210     }
0211
0212     template<typename C2>
0213     void merge(concurrent_map<key_type, mapped_type, C2, Allocator>& source) {
0214         this->internal_merge(source);
0215     }
0216
0217     template<typename C2>
0218     void merge(concurrent_map<key_type, mapped_type, C2, Allocator>&& source) {
0219         this->internal_merge(std::move(source));
0220     }
0221
0222     template<typename C2>
0223     void merge(concurrent_multimap<key_type, mapped_type, C2, Allocator>& source) {
0224         this->internal_merge(source);
0225     }
0226
0227     template<typename C2>
0228     void merge(concurrent_multimap<key_type, mapped_type, C2, Allocator>&& source) {
0229         this->internal_merge(std::move(source));
0230     }
0231 }; // class concurrent_map
0232
0233 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0234
0235 namespace internal {
0236
0237 using namespace tbb::internal;
0238
0239 template<template<typename...> typename Map, typename Key, typename T, typename... Args>
0240 using c_map_t = Map<Key, T,
0241                     std::conditional_t< (sizeof...(Args) > 0) && !is_allocator_v<pack_element_t<0, Args...> >,
0242                                         pack_element_t<0, Args...>, std::less<Key> >,
0243                     std::conditional_t< (sizeof...(Args) > 0) && is_allocator_v<pack_element_t<sizeof...(Args)-1, Args...> >,
0244                                         pack_element_t<sizeof...(Args)-1, Args...>, tbb_allocator<std::pair<const Key, T> > > >;
0245 } // namespace internal
0246
0247 template<typename It, typename... Args>
0248 concurrent_map(It, It, Args...)
0249 -> internal::c_map_t<concurrent_map, internal::iterator_key_t<It>, internal::iterator_mapped_t<It>, Args...>;
0250
0251 template<typename Key, typename T, typename... Args>
0252 concurrent_map(std::initializer_list<std::pair<const Key, T>>, Args...)
0253 -> internal::c_map_t<concurrent_map, Key, T, Args...>;
0254
0255 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0256
0257 template <typename Key, typename Value, typename Comp = std::less<Key>, typename Allocator = tbb_allocator<std::pair<const Key, Value>>>
0258 class concurrent_multimap
0259     : public internal::concurrent_skip_list<map_traits<Key, Value, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, true>> {
0260     using traits_type = map_traits<Key, Value, Comp, internal::concurrent_geometric_level_generator<64>, 64, Allocator, true>;
0261     using base_type = internal::concurrent_skip_list<traits_type>;
0262 #if __TBB_EXTRA_DEBUG
0263 public:
0264 #endif
0265     using base_type::allow_multimapping;
0266 public:
0267     using key_type = Key;
0268     using mapped_type = Value;
0269     using value_type = typename traits_type::value_type;
0270     using size_type = typename base_type::size_type;
0271     using difference_type = typename base_type::difference_type;
0272     using key_compare = Comp;
0273     using value_compare = typename base_type::value_compare;
0274     using allocator_type = Allocator;
0275
0276     using reference = typename base_type::reference;
0277     using const_reference = typename base_type::const_reference;
0278     using pointer = typename base_type::pointer;
0279     using const_pointer = typename base_type::pointer;
0280
0281     using iterator = typename base_type::iterator;
0282     using const_iterator = typename base_type::const_iterator;
0283     using reverse_iterator = typename base_type::reverse_iterator;
0284     using const_reverse_iterator = typename base_type::const_reverse_iterator;
0285
0286     using node_type = typename base_type::node_type;
0287
0288     using base_type::end;
0289     using base_type::find;
0290     using base_type::emplace;
0291     using base_type::insert;
0292
0293     concurrent_multimap() = default;
0294
0295     explicit concurrent_multimap(const key_compare& comp, const allocator_type& alloc = allocator_type()) : base_type(comp, alloc) {}
0296
0297     explicit concurrent_multimap(const allocator_type& alloc) : base_type(key_compare(), alloc) {}
0298
0299     template< class InputIt >
0300     concurrent_multimap(InputIt first, InputIt last, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
0301         : base_type(first, last, comp, alloc) {}
0302
0303     template< class InputIt >
0304     concurrent_multimap(InputIt first, InputIt last, const allocator_type& alloc) : base_type(first, last, key_compare(), alloc) {}
0305
0306     /** Copy constructor */
0307     concurrent_multimap(const concurrent_multimap&) = default;
0308
0309     concurrent_multimap(const concurrent_multimap& other, const allocator_type& alloc) : base_type(other, alloc) {}
0310
0311     concurrent_multimap(concurrent_multimap&&) = default;
0312
0313     concurrent_multimap(concurrent_multimap&& other, const allocator_type& alloc) : base_type(std::move(other), alloc) {}
0314
0315     concurrent_multimap(std::initializer_list<value_type> init, const key_compare& comp = Comp(), const allocator_type& alloc = allocator_type())
0316         : base_type(comp, alloc) {
0317         insert(init);
0318     }
0319
0320     concurrent_multimap(std::initializer_list<value_type> init, const allocator_type& alloc)
0321         : base_type(key_compare(), alloc) {
0322         insert(init);
0323     }
0324
0325     concurrent_multimap& operator=(const concurrent_multimap& other) {
0326         return static_cast<concurrent_multimap&>(base_type::operator=(other));
0327     }
0328
0329     concurrent_multimap& operator=(concurrent_multimap&& other) {
0330         return static_cast<concurrent_multimap&>(base_type::operator=(std::move(other)));
0331     }
0332
0333     template<typename P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type>
0334     std::pair<iterator, bool> insert(P&& value) {
0335         return emplace(std::forward<P>(value));
0336     }
0337
0338     template<typename P, typename std::enable_if<std::is_constructible<value_type, P&&>::value>::type>
0339     iterator insert(const_iterator hint, P&& value) {
0340             return emplace_hint(hint, std::forward<P>(value));
0341         return end();
0342     }
0343
0344     template<typename C2>
0345     void merge(concurrent_multimap<key_type, mapped_type, C2, Allocator>& source) {
0346         this->internal_merge(source);
0347     }
0348
0349     template<typename C2>
0350     void merge(concurrent_multimap<key_type, mapped_type, C2, Allocator>&& source) {
0351         this->internal_merge(std::move(source));
0352     }
0353
0354     template<typename C2>
0355     void merge(concurrent_map<key_type, mapped_type, C2, Allocator>& source) {
0356         this->internal_merge(source);
0357     }
0358
0359     template<typename C2>
0360     void merge(concurrent_map<key_type, mapped_type, C2, Allocator>&& source) {
0361         this->internal_merge(std::move(source));
0362     }
0363
0364 }; // class concurrent_multimap
0365
0366 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0367
0368 template<typename It, typename... Args>
0369 concurrent_multimap(It, It, Args...)
0370 -> internal::c_map_t<concurrent_multimap, internal::iterator_key_t<It>, internal::iterator_mapped_t<It>, Args...>;
0371
0372 template<typename Key, typename T, typename... Args>
0373 concurrent_multimap(std::initializer_list<std::pair<const Key, T>>, Args...)
0374 -> internal::c_map_t<concurrent_multimap, Key, T, Args...>;
0375
0376 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0377
0378 } // namespace interface10
0379
0380 using interface10::concurrent_map;
0381 using interface10::concurrent_multimap;
0382
0383 } // namespace tbb
0384
0385 #include "internal/_warning_suppress_disable_notice.h"
0386 #undef __TBB_concurrent_map_H_include_area
0387
0388 #endif // __TBB_CONCURRENT_ORDERED_CONTAINERS_PRESENT
0389 #endif // __TBB_concurrent_map_H