include/tbb/concurrent_unordered_map.h

   1 /*
   2     Copyright (c) 2005-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 /* Container implementations in this header are based on PPL implementations
  18    provided by Microsoft. */
  19
  20 #ifndef __TBB_concurrent_unordered_map_H
  21 #define __TBB_concurrent_unordered_map_H
  22
  23 #include "internal/_concurrent_unordered_impl.h"
  24
  25 namespace tbb
  26 {
  27
  28 namespace interface5 {
  29
  30 // Template class for hash map traits
  31 template<typename Key, typename T, typename Hash_compare, typename Allocator, bool Allow_multimapping>
  32 class concurrent_unordered_map_traits
  33 {
  34 protected:
  35     typedef std::pair<const Key, T> value_type;
  36     typedef Key key_type;
  37     typedef Hash_compare hash_compare;
  38     typedef typename tbb::internal::allocator_rebind<Allocator, value_type>::type allocator_type;
  39 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
  40     typedef tbb::internal::node_handle<key_type, value_type,
  41                                   typename internal::split_ordered_list<value_type, allocator_type>::node,
  42                                   allocator_type> node_type;
  43 #endif // __TBB_UNORDERED_NODE_HANDLE_PRESENT
  44
  45     enum { allow_multimapping = Allow_multimapping };
  46
  47     concurrent_unordered_map_traits() : my_hash_compare() {}
  48     concurrent_unordered_map_traits(const hash_compare& hc) : my_hash_compare(hc) {}
  49
  50     template<class Type1, class Type2>
  51     static const Key& get_key(const std::pair<Type1, Type2>& value) {
  52         return (value.first);
  53     }
  54
  55     hash_compare my_hash_compare; // the comparator predicate for keys
  56 };
  57
  58 template<typename Key, typename T, typename Hasher, typename Key_equality, typename Allocator>
  59 class concurrent_unordered_multimap;
  60
  61 template <typename Key, typename T, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>,
  62          typename Allocator = tbb::tbb_allocator<std::pair<const Key, T> > >
  63 class concurrent_unordered_map :
  64     public internal::concurrent_unordered_base< concurrent_unordered_map_traits<Key, T,
  65     internal::hash_compare<Key, Hasher, Key_equality>, Allocator, false> >
  66 {
  67     // Base type definitions
  68     typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
  69     typedef concurrent_unordered_map_traits<Key, T, hash_compare, Allocator, false> traits_type;
  70     typedef internal::concurrent_unordered_base< traits_type > base_type;
  71 #if __TBB_EXTRA_DEBUG
  72 public:
  73 #endif
  74     using traits_type::allow_multimapping;
  75 public:
  76     using base_type::end;
  77     using base_type::find;
  78     using base_type::insert;
  79
  80     // Type definitions
  81     typedef Key key_type;
  82     typedef typename base_type::value_type value_type;
  83     typedef T mapped_type;
  84     typedef Hasher hasher;
  85     typedef Key_equality key_equal;
  86     typedef hash_compare key_compare;
  87
  88     typedef typename base_type::allocator_type allocator_type;
  89     typedef typename base_type::pointer pointer;
  90     typedef typename base_type::const_pointer const_pointer;
  91     typedef typename base_type::reference reference;
  92     typedef typename base_type::const_reference const_reference;
  93
  94     typedef typename base_type::size_type size_type;
  95     typedef typename base_type::difference_type difference_type;
  96
  97     typedef typename base_type::iterator iterator;
  98     typedef typename base_type::const_iterator const_iterator;
  99     typedef typename base_type::iterator local_iterator;
 100     typedef typename base_type::const_iterator const_local_iterator;
 101 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
 102     typedef typename base_type::node_type node_type;
 103 #endif // __TBB_UNORDERED_NODE_HANDLE_PRESENT
 104
 105     // Construction/destruction/copying
 106     explicit concurrent_unordered_map(size_type n_of_buckets = base_type::initial_bucket_number,
 107         const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
 108         const allocator_type& a = allocator_type())
 109         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
 110     {}
 111
 112     concurrent_unordered_map(size_type n_of_buckets, const allocator_type& a)
 113         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
 114     {}
 115
 116     concurrent_unordered_map(size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
 117         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
 118     {}
 119
 120     explicit concurrent_unordered_map(const Allocator& a) : base_type(base_type::initial_bucket_number, key_compare(), a)
 121     {}
 122
 123     template <typename Iterator>
 124     concurrent_unordered_map(Iterator first, Iterator last, size_type n_of_buckets = base_type::initial_bucket_number,
 125         const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
 126         const allocator_type& a = allocator_type())
 127         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
 128     {
 129         insert(first, last);
 130     }
 131
 132     template <typename Iterator>
 133     concurrent_unordered_map(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type& a)
 134         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
 135     {
 136         insert(first, last);
 137     }
 138
 139     template <typename Iterator>
 140     concurrent_unordered_map(Iterator first, Iterator last, size_type n_of_buckets, const hasher& a_hasher,
 141         const allocator_type& a)
 142         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
 143     {
 144         insert(first, last);
 145     }
 146
 147 #if __TBB_INITIALIZER_LISTS_PRESENT
 148     //! Constructor from initializer_list
 149     concurrent_unordered_map(std::initializer_list<value_type> il, size_type n_of_buckets = base_type::initial_bucket_number,
 150         const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
 151         const allocator_type& a = allocator_type())
 152         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
 153     {
 154         insert(il.begin(),il.end());
 155     }
 156
 157     concurrent_unordered_map(std::initializer_list<value_type> il, size_type n_of_buckets, const allocator_type& a)
 158         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
 159     {
 160         insert(il.begin(), il.end());
 161     }
 162
 163     concurrent_unordered_map(std::initializer_list<value_type> il, size_type n_of_buckets, const hasher& a_hasher,
 164         const allocator_type& a)
 165         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
 166     {
 167         insert(il.begin(), il.end());
 168     }
 169
 170 #endif //# __TBB_INITIALIZER_LISTS_PRESENT
 171
 172
 173 #if __TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
 174     concurrent_unordered_map(const concurrent_unordered_map& table)
 175         : base_type(table)
 176     {}
 177
 178     concurrent_unordered_map& operator=(const concurrent_unordered_map& table)
 179     {
 180         return static_cast<concurrent_unordered_map&>(base_type::operator=(table));
 181     }
 182
 183     concurrent_unordered_map(concurrent_unordered_map&& table)
 184         : base_type(std::move(table))
 185     {}
 186
 187     concurrent_unordered_map& operator=(concurrent_unordered_map&& table)
 188     {
 189         return static_cast<concurrent_unordered_map&>(base_type::operator=(std::move(table)));
 190     }
 191 #endif //__TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
 192
 193 #if __TBB_CPP11_RVALUE_REF_PRESENT
 194     concurrent_unordered_map(concurrent_unordered_map&& table, const Allocator& a) : base_type(std::move(table), a)
 195     {}
 196 #endif /*__TBB_CPP11_RVALUE_REF_PRESENT*/
 197
 198 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
 199     template<typename Hash, typename Equality>
 200     void merge(concurrent_unordered_map<Key, T, Hash, Equality, Allocator>& source)
 201               { this->internal_merge(source); }
 202
 203     template<typename Hash, typename Equality>
 204     void merge(concurrent_unordered_map<Key, T, Hash, Equality, Allocator>&& source)
 205               { this->internal_merge(source); }
 206
 207     template<typename Hash, typename Equality>
 208     void merge(concurrent_unordered_multimap<Key, T, Hash, Equality, Allocator>& source)
 209               { this->internal_merge(source); }
 210
 211     template<typename Hash, typename Equality>
 212     void merge(concurrent_unordered_multimap<Key, T, Hash, Equality, Allocator>&& source)
 213               { this->internal_merge(source); }
 214
 215 #endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
 216
 217     concurrent_unordered_map(const concurrent_unordered_map& table, const Allocator& a)
 218         : base_type(table, a)
 219     {}
 220
 221     // Observers
 222     mapped_type& operator[](const key_type& key)
 223     {
 224         iterator where = find(key);
 225
 226         if (where == end())
 227         {
 228             where = insert(std::pair<key_type, mapped_type>(key, mapped_type())).first;
 229         }
 230
 231         return ((*where).second);
 232     }
 233
 234     mapped_type& at(const key_type& key)
 235     {
 236         iterator where = find(key);
 237
 238         if (where == end())
 239         {
 240             tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
 241         }
 242
 243         return ((*where).second);
 244     }
 245
 246     const mapped_type& at(const key_type& key) const
 247     {
 248         const_iterator where = find(key);
 249
 250         if (where == end())
 251         {
 252             tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
 253         }
 254
 255         return ((*where).second);
 256     }
 257 };
 258
 259 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
 260
 261 namespace internal {
 262 using namespace tbb::internal;
 263
 264 template<template<typename...> typename Map, typename Key, typename Element, typename... Args>
 265 using cu_map_t = Map<
 266     Key, Element,
 267     std::conditional_t< (sizeof...(Args)>0) && !is_allocator_v< pack_element_t<0, Args...> >,
 268                         pack_element_t<0, Args...>, tbb_hash<Key> >,
 269     std::conditional_t< (sizeof...(Args)>1) && !is_allocator_v< pack_element_t<1, Args...> >,
 270                         pack_element_t<1, Args...>, std::equal_to<Key> >,
 271     std::conditional_t< (sizeof...(Args)>0) && is_allocator_v< pack_element_t<sizeof...(Args)-1, Args...> >,
 272                         pack_element_t<sizeof...(Args)-1, Args...>, tbb_allocator<std::pair<const Key, Element> > >
 273 >;
 274 }
 275
 276 // Deduction guide for the constructor from two iterators
 277 template<typename I>
 278 concurrent_unordered_map (I, I)
 279 -> internal::cu_map_t<concurrent_unordered_map, internal::iterator_key_t<I>, internal::iterator_mapped_t<I>>;
 280
 281 // Deduction guide for the constructor from two iterators and hasher/equality/allocator
 282 template<typename I, typename... Args>
 283 concurrent_unordered_map(I, I, size_t, Args...)
 284 -> internal::cu_map_t<concurrent_unordered_map, internal::iterator_key_t<I>, internal::iterator_mapped_t<I>, Args...>;
 285
 286 // Deduction guide for the constructor from an initializer_list
 287 template<typename Key, typename Element>
 288 concurrent_unordered_map(std::initializer_list<std::pair<const Key, Element>>)
 289 -> internal::cu_map_t<concurrent_unordered_map, Key, Element>;
 290
 291 // Deduction guide for the constructor from an initializer_list and hasher/equality/allocator
 292 template<typename Key, typename Element, typename... Args>
 293 concurrent_unordered_map(std::initializer_list<std::pair<const Key, Element>>, size_t, Args...)
 294 -> internal::cu_map_t<concurrent_unordered_map, Key, Element, Args...>;
 295
 296 #endif /* __TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
 297
 298 template < typename Key, typename T, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>,
 299         typename Allocator = tbb::tbb_allocator<std::pair<const Key, T> > >
 300 class concurrent_unordered_multimap :
 301     public internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T,
 302     internal::hash_compare<Key, Hasher, Key_equality>, Allocator, true> >
 303 {
 304     // Base type definitions
 305     typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
 306     typedef concurrent_unordered_map_traits<Key, T, hash_compare, Allocator, true> traits_type;
 307     typedef internal::concurrent_unordered_base<traits_type> base_type;
 308 #if __TBB_EXTRA_DEBUG
 309 public:
 310 #endif
 311     using traits_type::allow_multimapping;
 312 public:
 313     using base_type::insert;
 314
 315     // Type definitions
 316     typedef Key key_type;
 317     typedef typename base_type::value_type value_type;
 318     typedef T mapped_type;
 319     typedef Hasher hasher;
 320     typedef Key_equality key_equal;
 321     typedef hash_compare key_compare;
 322
 323     typedef typename base_type::allocator_type allocator_type;
 324     typedef typename base_type::pointer pointer;
 325     typedef typename base_type::const_pointer const_pointer;
 326     typedef typename base_type::reference reference;
 327     typedef typename base_type::const_reference const_reference;
 328
 329     typedef typename base_type::size_type size_type;
 330     typedef typename base_type::difference_type difference_type;
 331
 332     typedef typename base_type::iterator iterator;
 333     typedef typename base_type::const_iterator const_iterator;
 334     typedef typename base_type::iterator local_iterator;
 335     typedef typename base_type::const_iterator const_local_iterator;
 336 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
 337     typedef typename base_type::node_type node_type;
 338 #endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
 339
 340     // Construction/destruction/copying
 341     explicit concurrent_unordered_multimap(size_type n_of_buckets = base_type::initial_bucket_number,
 342         const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
 343         const allocator_type& a = allocator_type())
 344         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
 345     {}
 346
 347     concurrent_unordered_multimap(size_type n_of_buckets, const allocator_type& a)
 348         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
 349     {}
 350
 351     concurrent_unordered_multimap(size_type n_of_buckets, const hasher& a_hasher, const allocator_type& a)
 352         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
 353     {}
 354
 355     explicit concurrent_unordered_multimap(const Allocator& a) : base_type(base_type::initial_bucket_number, key_compare(), a)
 356     {}
 357
 358     template <typename Iterator>
 359     concurrent_unordered_multimap(Iterator first, Iterator last, size_type n_of_buckets = base_type::initial_bucket_number,
 360         const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
 361         const allocator_type& a = allocator_type())
 362         : base_type(n_of_buckets,key_compare(a_hasher,a_keyeq), a)
 363     {
 364         insert(first, last);
 365     }
 366
 367     template <typename Iterator>
 368     concurrent_unordered_multimap(Iterator first, Iterator last, size_type n_of_buckets, const allocator_type& a)
 369         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
 370     {
 371         insert(first, last);
 372     }
 373
 374     template <typename Iterator>
 375     concurrent_unordered_multimap(Iterator first, Iterator last, size_type n_of_buckets, const hasher& a_hasher,
 376         const allocator_type& a)
 377         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
 378     {
 379         insert(first, last);
 380     }
 381
 382 #if __TBB_INITIALIZER_LISTS_PRESENT
 383     //! Constructor from initializer_list
 384     concurrent_unordered_multimap(std::initializer_list<value_type> il, size_type n_of_buckets = base_type::initial_bucket_number,
 385         const hasher& a_hasher = hasher(), const key_equal& a_keyeq = key_equal(),
 386         const allocator_type& a = allocator_type())
 387         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
 388     {
 389         insert(il.begin(),il.end());
 390     }
 391
 392     concurrent_unordered_multimap(std::initializer_list<value_type> il, size_type n_of_buckets, const allocator_type& a)
 393         : base_type(n_of_buckets, key_compare(hasher(), key_equal()), a)
 394     {
 395         insert(il.begin(), il.end());
 396     }
 397
 398     concurrent_unordered_multimap(std::initializer_list<value_type> il, size_type n_of_buckets, const hasher& a_hasher,
 399         const allocator_type& a)
 400         : base_type(n_of_buckets, key_compare(a_hasher, key_equal()), a)
 401     {
 402         insert(il.begin(), il.end());
 403     }
 404
 405 #endif //# __TBB_INITIALIZER_LISTS_PRESENT
 406
 407 #if __TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
 408     concurrent_unordered_multimap(const concurrent_unordered_multimap& table)
 409         : base_type(table)
 410     {}
 411
 412     concurrent_unordered_multimap& operator=(const concurrent_unordered_multimap& table)
 413     {
 414         return static_cast<concurrent_unordered_multimap&>(base_type::operator=(table));
 415     }
 416
 417     concurrent_unordered_multimap(concurrent_unordered_multimap&& table)
 418         : base_type(std::move(table))
 419     {}
 420
 421     concurrent_unordered_multimap& operator=(concurrent_unordered_multimap&& table)
 422     {
 423         return static_cast<concurrent_unordered_multimap&>(base_type::operator=(std::move(table)));
 424     }
 425 #endif //__TBB_CPP11_RVALUE_REF_PRESENT && !__TBB_IMPLICIT_MOVE_PRESENT
 426
 427 #if __TBB_CPP11_RVALUE_REF_PRESENT
 428     concurrent_unordered_multimap(concurrent_unordered_multimap&& table, const Allocator& a) : base_type(std::move(table), a)
 429     {}
 430 #endif /*__TBB_CPP11_RVALUE_REF_PRESENT*/
 431
 432 #if __TBB_UNORDERED_NODE_HANDLE_PRESENT
 433     template<typename Hash, typename Equality>
 434     void merge(concurrent_unordered_map<Key, T, Hash, Equality, Allocator>& source)
 435               { this->internal_merge(source); }
 436
 437     template<typename Hash, typename Equality>
 438     void merge(concurrent_unordered_map<Key, T, Hash, Equality, Allocator>&& source)
 439               { this->internal_merge(source); }
 440
 441     template<typename Hash, typename Equality>
 442     void merge(concurrent_unordered_multimap<Key, T, Hash, Equality, Allocator>& source)
 443               { this->internal_merge(source); }
 444
 445     template<typename Hash, typename Equality>
 446     void merge(concurrent_unordered_multimap<Key, T, Hash, Equality, Allocator>&& source)
 447               { this->internal_merge(source); }
 448
 449 #endif //__TBB_UNORDERED_NODE_HANDLE_PRESENT
 450
 451     concurrent_unordered_multimap(const concurrent_unordered_multimap& table, const Allocator& a)
 452         : base_type(table, a)
 453     {}
 454 };
 455
 456 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
 457
 458 // Deduction guide for the constructor from two iterators
 459 template<typename I>
 460 concurrent_unordered_multimap (I, I)
 461 -> internal::cu_map_t<concurrent_unordered_multimap, internal::iterator_key_t<I>, internal::iterator_mapped_t<I>>;
 462
 463 // Deduction guide for the constructor from two iterators and hasher/equality/allocator
 464 template<typename I, typename... Args>
 465 concurrent_unordered_multimap(I, I, size_t, Args...)
 466 -> internal::cu_map_t<concurrent_unordered_multimap, internal::iterator_key_t<I>, internal::iterator_mapped_t<I>, Args...>;
 467
 468 // Deduction guide for the constructor from an initializer_list
 469 template<typename Key, typename Element>
 470 concurrent_unordered_multimap(std::initializer_list<std::pair<const Key, Element>>)
 471 -> internal::cu_map_t<concurrent_unordered_multimap, Key, Element>;
 472
 473 // Deduction guide for the constructor from an initializer_list and hasher/equality/allocator
 474 template<typename Key, typename Element, typename... Args>
 475 concurrent_unordered_multimap(std::initializer_list<std::pair<const Key, Element>>, size_t, Args...)
 476 -> internal::cu_map_t<concurrent_unordered_multimap, Key, Element, Args...>;
 477
 478 #endif /* __TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
 479 } // namespace interface5
 480
 481 using interface5::concurrent_unordered_map;
 482 using interface5::concurrent_unordered_multimap;
 483
 484 } // namespace tbb
 485
 486 #endif// __TBB_concurrent_unordered_map_H