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