oneapi/tbb/concurrent_map.h

0001 /*
0002     Copyright (c) 2019-2021 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 #include "detail/_namespace_injection.h"
0021 #include "detail/_concurrent_skip_list.h"
0022 #include "tbb_allocator.h"
0023 #include <functional>
0024 #include <tuple>
0025 #include <utility>
0026
0027 namespace tbb {
0028 namespace detail {
0029 namespace d2 {
0030
0031 template<typename Key, typename Value, typename KeyCompare, typename RandomGenerator,
0032          typename Allocator, bool AllowMultimapping>
0033 struct map_traits {
0034     static constexpr std::size_t max_level = RandomGenerator::max_level;
0035     using random_level_generator_type = RandomGenerator;
0036     using key_type = Key;
0037     using mapped_type = Value;
0038     using compare_type = KeyCompare;
0039     using value_type = std::pair<const key_type, mapped_type>;
0040     using reference = value_type&;
0041     using const_reference = const value_type&;
0042     using allocator_type = Allocator;
0043
0044     static constexpr bool allow_multimapping = AllowMultimapping;
0045
0046     class value_compare {
0047     public:
0048         bool operator()(const value_type& lhs, const value_type& rhs) const {
0049             return comp(lhs.first, rhs.first);
0050         }
0051
0052     protected:
0053         value_compare(compare_type c) : comp(c) {}
0054
0055         friend struct map_traits;
0056
0057         compare_type comp;
0058     };
0059
0060     static value_compare value_comp(compare_type comp) { return value_compare(comp); }
0061
0062     static const key_type& get_key(const_reference val) {
0063         return val.first;
0064     }
0065 }; // struct map_traits
0066
0067 template <typename Key, typename Value, typename Compare, typename Allocator>
0068 class concurrent_multimap;
0069
0070 template <typename Key, typename Value, typename Compare = std::less<Key>, typename Allocator = tbb::tbb_allocator<std::pair<const Key, Value>>>
0071 class concurrent_map : public concurrent_skip_list<map_traits<Key, Value, Compare, concurrent_geometric_level_generator<32>, Allocator, false>> {
0072     using base_type = concurrent_skip_list<map_traits<Key, Value, Compare, concurrent_geometric_level_generator<32>, Allocator, false>>;
0073 public:
0074     using key_type = Key;
0075     using mapped_type = Value;
0076     using value_type = typename base_type::value_type;
0077     using size_type = typename base_type::size_type;
0078     using difference_type = typename base_type::difference_type;
0079     using key_compare = Compare;
0080     using value_compare = typename base_type::value_compare;
0081     using allocator_type = Allocator;
0082
0083     using reference = typename base_type::reference;
0084     using const_reference = typename base_type::const_reference;
0085     using pointer = typename base_type::pointer;
0086     using const_pointer = typename base_type::const_pointer;
0087
0088     using iterator = typename base_type::iterator;
0089     using const_iterator = typename base_type::const_iterator;
0090
0091     using node_type = typename base_type::node_type;
0092
0093     // Include constructors of base type
0094     using base_type::base_type;
0095
0096     // Required for implicit deduction guides
0097     concurrent_map() = default;
0098     concurrent_map( const concurrent_map& ) = default;
0099     concurrent_map( const concurrent_map& other, const allocator_type& alloc ) : base_type(other, alloc) {}
0100     concurrent_map( concurrent_map&& ) = default;
0101     concurrent_map( concurrent_map&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
0102     // Required to respect the rule of 5
0103     concurrent_map& operator=( const concurrent_map& ) = default;
0104     concurrent_map& operator=( concurrent_map&& ) = default;
0105
0106     concurrent_map& operator=( std::initializer_list<value_type> il ) {
0107         base_type::operator= (il);
0108         return *this;
0109     }
0110
0111     // Observers
0112     mapped_type& at(const key_type& key) {
0113         iterator it = this->find(key);
0114
0115         if (it == this->end()) {
0116             throw_exception(exception_id::invalid_key);
0117         }
0118         return it->second;
0119     }
0120
0121     const mapped_type& at(const key_type& key) const {
0122         return const_cast<concurrent_map*>(this)->at(key);
0123     }
0124
0125     mapped_type& operator[](const key_type& key) {
0126         iterator it = this->find(key);
0127
0128         if (it == this->end()) {
0129             it = this->emplace(std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>()).first;
0130         }
0131         return it->second;
0132     }
0133
0134     mapped_type& operator[](key_type&& key) {
0135         iterator it = this->find(key);
0136
0137         if (it == this->end()) {
0138             it = this->emplace(std::piecewise_construct, std::forward_as_tuple(std::move(key)), std::tuple<>()).first;
0139         }
0140         return it->second;
0141     }
0142
0143     using base_type::insert;
0144
0145     template <typename P>
0146     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
0147                             std::pair<iterator, bool>>::type insert( P&& value )
0148     {
0149         return this->emplace(std::forward<P>(value));
0150     }
0151
0152     template <typename P>
0153     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
0154                             iterator>::type insert( const_iterator hint, P&& value )
0155     {
0156         return this->emplace_hint(hint, std::forward<P>(value));
0157     }
0158
0159     template<typename OtherCompare>
0160     void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>& source) {
0161         this->internal_merge(source);
0162     }
0163
0164     template<typename OtherCompare>
0165     void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>&& source) {
0166         this->internal_merge(std::move(source));
0167     }
0168
0169     template<typename OtherCompare>
0170     void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>& source) {
0171         this->internal_merge(source);
0172     }
0173
0174     template<typename OtherCompare>
0175     void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>&& source) {
0176         this->internal_merge(std::move(source));
0177     }
0178 }; // class concurrent_map
0179
0180 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0181
0182 template <typename It,
0183           typename Comp = std::less<iterator_key_t<It>>,
0184           typename Alloc = tbb::tbb_allocator<iterator_alloc_pair_t<It>>,
0185           typename = std::enable_if_t<is_input_iterator_v<It>>,
0186           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0187           typename = std::enable_if_t<!is_allocator_v<Comp>>>
0188 concurrent_map( It, It, Comp = Comp(), Alloc = Alloc() )
0189 -> concurrent_map<iterator_key_t<It>, iterator_mapped_t<It>, Comp, Alloc>;
0190
0191 template <typename Key, typename T,
0192           typename Comp = std::less<std::remove_const_t<Key>>,
0193           typename Alloc = tbb::tbb_allocator<std::pair<const Key, T>>,
0194           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0195           typename = std::enable_if_t<!is_allocator_v<Comp>>>
0196 concurrent_map( std::initializer_list<std::pair<Key, T>>, Comp = Comp(), Alloc = Alloc() )
0197 -> concurrent_map<std::remove_const_t<Key>, T, Comp, Alloc>;
0198
0199 template <typename It, typename Alloc,
0200           typename = std::enable_if_t<is_input_iterator_v<It>>,
0201           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0202 concurrent_map( It, It, Alloc )
0203 -> concurrent_map<iterator_key_t<It>, iterator_mapped_t<It>,
0204                   std::less<iterator_key_t<It>>, Alloc>;
0205
0206 template <typename Key, typename T, typename Alloc,
0207           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0208 concurrent_map( std::initializer_list<std::pair<Key, T>>, Alloc )
0209 -> concurrent_map<std::remove_const_t<Key>, T, std::less<std::remove_const_t<Key>>, Alloc>;
0210
0211 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0212
0213 template <typename Key, typename Value, typename Compare, typename Allocator>
0214 void swap( concurrent_map<Key, Value, Compare, Allocator>& lhs,
0215            concurrent_map<Key, Value, Compare, Allocator>& rhs )
0216 {
0217     lhs.swap(rhs);
0218 }
0219
0220 template <typename Key, typename Value, typename Compare = std::less<Key>, typename Allocator = tbb::tbb_allocator<std::pair<const Key, Value>>>
0221 class concurrent_multimap : public concurrent_skip_list<map_traits<Key, Value, Compare, concurrent_geometric_level_generator<32>, Allocator, true>> {
0222     using base_type = concurrent_skip_list<map_traits<Key, Value, Compare, concurrent_geometric_level_generator<32>, Allocator, true>>;
0223 public:
0224     using key_type = Key;
0225     using mapped_type = Value;
0226     using value_type = typename base_type::value_type;
0227     using size_type = typename base_type::size_type;
0228     using difference_type = typename base_type::difference_type;
0229     using key_compare = Compare;
0230     using value_compare = typename base_type::value_compare;
0231     using allocator_type = Allocator;
0232
0233     using reference = typename base_type::reference;
0234     using const_reference = typename base_type::const_reference;
0235     using pointer = typename base_type::pointer;
0236     using const_pointer = typename base_type::const_pointer;
0237
0238     using iterator = typename base_type::iterator;
0239     using const_iterator = typename base_type::const_iterator;
0240
0241     using node_type = typename base_type::node_type;
0242
0243     // Include constructors of base_type
0244     using base_type::base_type;
0245     using base_type::insert;
0246
0247     // Required for implicit deduction guides
0248     concurrent_multimap() = default;
0249     concurrent_multimap( const concurrent_multimap& ) = default;
0250     concurrent_multimap( const concurrent_multimap& other, const allocator_type& alloc ) : base_type(other, alloc) {}
0251     concurrent_multimap( concurrent_multimap&& ) = default;
0252     concurrent_multimap( concurrent_multimap&& other, const allocator_type& alloc ) : base_type(std::move(other), alloc) {}
0253     // Required to respect the rule of 5
0254     concurrent_multimap& operator=( const concurrent_multimap& ) = default;
0255     concurrent_multimap& operator=( concurrent_multimap&& ) = default;
0256
0257     concurrent_multimap& operator=( std::initializer_list<value_type> il ) {
0258         base_type::operator= (il);
0259         return *this;
0260     }
0261
0262     template <typename P>
0263     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
0264                             std::pair<iterator, bool>>::type insert( P&& value )
0265     {
0266         return this->emplace(std::forward<P>(value));
0267     }
0268
0269     template <typename P>
0270     typename std::enable_if<std::is_constructible<value_type, P&&>::value,
0271                             iterator>::type insert( const_iterator hint, P&& value )
0272     {
0273         return this->emplace_hint(hint, std::forward<P>(value));
0274     }
0275
0276     template<typename OtherCompare>
0277     void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>& source) {
0278         this->internal_merge(source);
0279     }
0280
0281     template<typename OtherCompare>
0282     void merge(concurrent_multimap<key_type, mapped_type, OtherCompare, Allocator>&& source) {
0283         this->internal_merge(std::move(source));
0284     }
0285
0286     template<typename OtherCompare>
0287     void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>& source) {
0288         this->internal_merge(source);
0289     }
0290
0291     template<typename OtherCompare>
0292     void merge(concurrent_map<key_type, mapped_type, OtherCompare, Allocator>&& source) {
0293         this->internal_merge(std::move(source));
0294     }
0295 }; // class concurrent_multimap
0296
0297 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0298
0299 template <typename It,
0300           typename Comp = std::less<iterator_key_t<It>>,
0301           typename Alloc = tbb::tbb_allocator<iterator_alloc_pair_t<It>>,
0302           typename = std::enable_if_t<is_input_iterator_v<It>>,
0303           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0304           typename = std::enable_if_t<!is_allocator_v<Comp>>>
0305 concurrent_multimap( It, It, Comp = Comp(), Alloc = Alloc() )
0306 -> concurrent_multimap<iterator_key_t<It>, iterator_mapped_t<It>, Comp, Alloc>;
0307
0308 template <typename Key, typename T,
0309           typename Comp = std::less<std::remove_const_t<Key>>,
0310           typename Alloc = tbb::tbb_allocator<std::pair<const Key, T>>,
0311           typename = std::enable_if_t<is_allocator_v<Alloc>>,
0312           typename = std::enable_if_t<!is_allocator_v<Comp>>>
0313 concurrent_multimap( std::initializer_list<std::pair<Key, T>>, Comp = Comp(), Alloc = Alloc() )
0314 -> concurrent_multimap<std::remove_const_t<Key>, T, Comp, Alloc>;
0315
0316 template <typename It, typename Alloc,
0317           typename = std::enable_if_t<is_input_iterator_v<It>>,
0318           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0319 concurrent_multimap( It, It, Alloc )
0320 -> concurrent_multimap<iterator_key_t<It>, iterator_mapped_t<It>,
0321                        std::less<iterator_key_t<It>>, Alloc>;
0322
0323 template <typename Key, typename T, typename Alloc,
0324           typename = std::enable_if_t<is_allocator_v<Alloc>>>
0325 concurrent_multimap( std::initializer_list<std::pair<Key, T>>, Alloc )
0326 -> concurrent_multimap<std::remove_const_t<Key>, T, std::less<std::remove_const_t<Key>>, Alloc>;
0327
0328
0329 #endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
0330
0331 template <typename Key, typename Value, typename Compare, typename Allocator>
0332 void swap( concurrent_multimap<Key, Value, Compare, Allocator>& lhs,
0333            concurrent_multimap<Key, Value, Compare, Allocator>& rhs )
0334 {
0335     lhs.swap(rhs);
0336 }
0337
0338 } // namespace d2
0339 } // namespace detail
0340
0341 inline namespace v1 {
0342
0343 using detail::d2::concurrent_map;
0344 using detail::d2::concurrent_multimap;
0345 using detail::split;
0346
0347 } // inline namespace v1
0348 } // namespace tbb
0349
0350 #endif // __TBB_concurrent_map_H