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