Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-09-17 08:52:35 

0001 /* Fast open-addressing, node-based concurrent hashset.
0002  *
0003  * Copyright 2023 Christian Mazakas.
0004  * Copyright 2023-2024 Joaquin M Lopez Munoz.
0005  * Distributed under the Boost Software License, Version 1.0.
0006  * (See accompanying file LICENSE_1_0.txt or copy at
0007  * http://www.boost.org/LICENSE_1_0.txt)
0008  *
0009  * See https://www.boost.org/libs/unordered for library home page.
0010  */
0011 
0012 #ifndef BOOST_UNORDERED_CONCURRENT_NODE_SET_HPP
0013 #define BOOST_UNORDERED_CONCURRENT_NODE_SET_HPP
0014 
0015 #include <boost/unordered/concurrent_node_set_fwd.hpp>
0016 #include <boost/unordered/detail/concurrent_static_asserts.hpp>
0017 #include <boost/unordered/detail/foa/concurrent_table.hpp>
0018 #include <boost/unordered/detail/foa/element_type.hpp>
0019 #include <boost/unordered/detail/foa/node_set_handle.hpp>
0020 #include <boost/unordered/detail/foa/node_set_types.hpp>
0021 #include <boost/unordered/detail/type_traits.hpp>
0022 #include <boost/unordered/unordered_node_set_fwd.hpp>
0023 
0024 #include <boost/container_hash/hash.hpp>
0025 #include <boost/core/allocator_access.hpp>
0026 #include <boost/core/serialization.hpp>
0027 
0028 #include <utility>
0029 
0030 namespace boost {
0031   namespace unordered {
0032     template <class Key, class Hash, class Pred, class Allocator>
0033     class concurrent_node_set
0034     {
0035     private:
0036       template <class Key2, class Hash2, class Pred2, class Allocator2>
0037       friend class concurrent_node_set;
0038       template <class Key2, class Hash2, class Pred2, class Allocator2>
0039       friend class unordered_node_set;
0040 
0041       using type_policy = detail::foa::node_set_types<Key,
0042         typename boost::allocator_void_pointer<Allocator>::type>;
0043 
0044       using table_type =
0045         detail::foa::concurrent_table<type_policy, Hash, Pred, Allocator>;
0046 
0047       table_type table_;
0048 
0049       template <class K, class H, class KE, class A>
0050       bool friend operator==(concurrent_node_set<K, H, KE, A> const& lhs,
0051         concurrent_node_set<K, H, KE, A> const& rhs);
0052 
0053       template <class K, class H, class KE, class A, class Predicate>
0054       friend typename concurrent_node_set<K, H, KE, A>::size_type erase_if(
0055         concurrent_node_set<K, H, KE, A>& set, Predicate pred);
0056 
0057       template<class Archive, class K, class H, class KE, class A>
0058       friend void serialize(
0059         Archive& ar, concurrent_node_set<K, H, KE, A>& c,
0060         unsigned int version);
0061 
0062     public:
0063       using key_type = Key;
0064       using value_type = typename type_policy::value_type;
0065       using init_type = typename type_policy::init_type;
0066       using size_type = std::size_t;
0067       using difference_type = std::ptrdiff_t;
0068       using hasher = typename boost::unordered::detail::type_identity<Hash>::type;
0069       using key_equal = typename boost::unordered::detail::type_identity<Pred>::type;
0070       using allocator_type = typename boost::unordered::detail::type_identity<Allocator>::type;
0071       using reference = value_type&;
0072       using const_reference = value_type const&;
0073       using pointer = typename boost::allocator_pointer<allocator_type>::type;
0074       using const_pointer =
0075         typename boost::allocator_const_pointer<allocator_type>::type;
0076       using node_type = detail::foa::node_set_handle<type_policy,
0077         typename boost::allocator_rebind<Allocator,
0078           typename type_policy::value_type>::type>;
0079       using insert_return_type =
0080         detail::foa::iteratorless_insert_return_type<node_type>;
0081       static constexpr size_type bulk_visit_size = table_type::bulk_visit_size;
0082 
0083 #if defined(BOOST_UNORDERED_ENABLE_STATS)
0084       using stats = typename table_type::stats;
0085 #endif
0086 
0087       concurrent_node_set()
0088           : concurrent_node_set(detail::foa::default_bucket_count)
0089       {
0090       }
0091 
0092       explicit concurrent_node_set(size_type n, const hasher& hf = hasher(),
0093         const key_equal& eql = key_equal(),
0094         const allocator_type& a = allocator_type())
0095           : table_(n, hf, eql, a)
0096       {
0097       }
0098 
0099       template <class InputIterator>
0100       concurrent_node_set(InputIterator f, InputIterator l,
0101         size_type n = detail::foa::default_bucket_count,
0102         const hasher& hf = hasher(), const key_equal& eql = key_equal(),
0103         const allocator_type& a = allocator_type())
0104           : table_(n, hf, eql, a)
0105       {
0106         this->insert(f, l);
0107       }
0108 
0109       concurrent_node_set(concurrent_node_set const& rhs)
0110           : table_(rhs.table_,
0111               boost::allocator_select_on_container_copy_construction(
0112                 rhs.get_allocator()))
0113       {
0114       }
0115 
0116       concurrent_node_set(concurrent_node_set&& rhs)
0117           : table_(std::move(rhs.table_))
0118       {
0119       }
0120 
0121       template <class InputIterator>
0122       concurrent_node_set(
0123         InputIterator f, InputIterator l, allocator_type const& a)
0124           : concurrent_node_set(f, l, 0, hasher(), key_equal(), a)
0125       {
0126       }
0127 
0128       explicit concurrent_node_set(allocator_type const& a)
0129           : table_(detail::foa::default_bucket_count, hasher(), key_equal(), a)
0130       {
0131       }
0132 
0133       concurrent_node_set(
0134         concurrent_node_set const& rhs, allocator_type const& a)
0135           : table_(rhs.table_, a)
0136       {
0137       }
0138 
0139       concurrent_node_set(concurrent_node_set&& rhs, allocator_type const& a)
0140           : table_(std::move(rhs.table_), a)
0141       {
0142       }
0143 
0144       concurrent_node_set(std::initializer_list<value_type> il,
0145         size_type n = detail::foa::default_bucket_count,
0146         const hasher& hf = hasher(), const key_equal& eql = key_equal(),
0147         const allocator_type& a = allocator_type())
0148           : concurrent_node_set(n, hf, eql, a)
0149       {
0150         this->insert(il.begin(), il.end());
0151       }
0152 
0153       concurrent_node_set(size_type n, const allocator_type& a)
0154           : concurrent_node_set(n, hasher(), key_equal(), a)
0155       {
0156       }
0157 
0158       concurrent_node_set(
0159         size_type n, const hasher& hf, const allocator_type& a)
0160           : concurrent_node_set(n, hf, key_equal(), a)
0161       {
0162       }
0163 
0164       template <typename InputIterator>
0165       concurrent_node_set(
0166         InputIterator f, InputIterator l, size_type n, const allocator_type& a)
0167           : concurrent_node_set(f, l, n, hasher(), key_equal(), a)
0168       {
0169       }
0170 
0171       template <typename InputIterator>
0172       concurrent_node_set(InputIterator f, InputIterator l, size_type n,
0173         const hasher& hf, const allocator_type& a)
0174           : concurrent_node_set(f, l, n, hf, key_equal(), a)
0175       {
0176       }
0177 
0178       concurrent_node_set(
0179         std::initializer_list<value_type> il, const allocator_type& a)
0180           : concurrent_node_set(
0181               il, detail::foa::default_bucket_count, hasher(), key_equal(), a)
0182       {
0183       }
0184 
0185       concurrent_node_set(std::initializer_list<value_type> il, size_type n,
0186         const allocator_type& a)
0187           : concurrent_node_set(il, n, hasher(), key_equal(), a)
0188       {
0189       }
0190 
0191       concurrent_node_set(std::initializer_list<value_type> il, size_type n,
0192         const hasher& hf, const allocator_type& a)
0193           : concurrent_node_set(il, n, hf, key_equal(), a)
0194       {
0195       }
0196 
0197       template <bool avoid_explicit_instantiation = true>
0198       concurrent_node_set(
0199         unordered_node_set<Key, Hash, Pred, Allocator>&& other)
0200           : table_(std::move(other.table_))
0201       {
0202       }
0203 
0204       ~concurrent_node_set() = default;
0205 
0206       concurrent_node_set& operator=(concurrent_node_set const& rhs)
0207       {
0208         table_ = rhs.table_;
0209         return *this;
0210       }
0211 
0212       concurrent_node_set& operator=(concurrent_node_set&& rhs)
0213         noexcept(boost::allocator_is_always_equal<Allocator>::type::value ||
0214                  boost::allocator_propagate_on_container_move_assignment<
0215                    Allocator>::type::value)
0216       {
0217         table_ = std::move(rhs.table_);
0218         return *this;
0219       }
0220 
0221       concurrent_node_set& operator=(std::initializer_list<value_type> ilist)
0222       {
0223         table_ = ilist;
0224         return *this;
0225       }
0226 
0227       /// Capacity
0228       ///
0229 
0230       size_type size() const noexcept { return table_.size(); }
0231       size_type max_size() const noexcept { return table_.max_size(); }
0232 
0233       BOOST_ATTRIBUTE_NODISCARD bool empty() const noexcept
0234       {
0235         return size() == 0;
0236       }
0237 
0238       template <class F>
0239       BOOST_FORCEINLINE size_type visit(key_type const& k, F f)
0240       {
0241         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0242         return table_.visit(k, f);
0243       }
0244 
0245       template <class F>
0246       BOOST_FORCEINLINE size_type visit(key_type const& k, F f) const
0247       {
0248         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0249         return table_.visit(k, f);
0250       }
0251 
0252       template <class F>
0253       BOOST_FORCEINLINE size_type cvisit(key_type const& k, F f) const
0254       {
0255         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0256         return table_.visit(k, f);
0257       }
0258 
0259       template <class K, class F>
0260       BOOST_FORCEINLINE typename std::enable_if<
0261         detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
0262       visit(K&& k, F f)
0263       {
0264         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0265         return table_.visit(std::forward<K>(k), f);
0266       }
0267 
0268       template <class K, class F>
0269       BOOST_FORCEINLINE typename std::enable_if<
0270         detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
0271       visit(K&& k, F f) const
0272       {
0273         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0274         return table_.visit(std::forward<K>(k), f);
0275       }
0276 
0277       template <class K, class F>
0278       BOOST_FORCEINLINE typename std::enable_if<
0279         detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
0280       cvisit(K&& k, F f) const
0281       {
0282         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0283         return table_.visit(std::forward<K>(k), f);
0284       }
0285 
0286       template<class FwdIterator, class F>
0287       BOOST_FORCEINLINE
0288       size_t visit(FwdIterator first, FwdIterator last, F f)
0289       {
0290         BOOST_UNORDERED_STATIC_ASSERT_BULK_VISIT_ITERATOR(FwdIterator)
0291         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0292         return table_.visit(first, last, f);
0293       }
0294 
0295       template<class FwdIterator, class F>
0296       BOOST_FORCEINLINE
0297       size_t visit(FwdIterator first, FwdIterator last, F f) const
0298       {
0299         BOOST_UNORDERED_STATIC_ASSERT_BULK_VISIT_ITERATOR(FwdIterator)
0300         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0301         return table_.visit(first, last, f);
0302       }
0303 
0304       template<class FwdIterator, class F>
0305       BOOST_FORCEINLINE
0306       size_t cvisit(FwdIterator first, FwdIterator last, F f) const
0307       {
0308         BOOST_UNORDERED_STATIC_ASSERT_BULK_VISIT_ITERATOR(FwdIterator)
0309         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0310         return table_.visit(first, last, f);
0311       }
0312 
0313       template <class F> size_type visit_all(F f)
0314       {
0315         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0316         return table_.visit_all(f);
0317       }
0318 
0319       template <class F> size_type visit_all(F f) const
0320       {
0321         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0322         return table_.visit_all(f);
0323       }
0324 
0325       template <class F> size_type cvisit_all(F f) const
0326       {
0327         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0328         return table_.cvisit_all(f);
0329       }
0330 
0331 #if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
0332       template <class ExecPolicy, class F>
0333       typename std::enable_if<detail::is_execution_policy<ExecPolicy>::value,
0334         void>::type
0335       visit_all(ExecPolicy&& p, F f)
0336       {
0337         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0338         BOOST_UNORDERED_STATIC_ASSERT_EXEC_POLICY(ExecPolicy)
0339         table_.visit_all(p, f);
0340       }
0341 
0342       template <class ExecPolicy, class F>
0343       typename std::enable_if<detail::is_execution_policy<ExecPolicy>::value,
0344         void>::type
0345       visit_all(ExecPolicy&& p, F f) const
0346       {
0347         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0348         BOOST_UNORDERED_STATIC_ASSERT_EXEC_POLICY(ExecPolicy)
0349         table_.visit_all(p, f);
0350       }
0351 
0352       template <class ExecPolicy, class F>
0353       typename std::enable_if<detail::is_execution_policy<ExecPolicy>::value,
0354         void>::type
0355       cvisit_all(ExecPolicy&& p, F f) const
0356       {
0357         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0358         BOOST_UNORDERED_STATIC_ASSERT_EXEC_POLICY(ExecPolicy)
0359         table_.cvisit_all(p, f);
0360       }
0361 #endif
0362 
0363       template <class F> bool visit_while(F f)
0364       {
0365         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0366         return table_.visit_while(f);
0367       }
0368 
0369       template <class F> bool visit_while(F f) const
0370       {
0371         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0372         return table_.visit_while(f);
0373       }
0374 
0375       template <class F> bool cvisit_while(F f) const
0376       {
0377         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0378         return table_.cvisit_while(f);
0379       }
0380 
0381 #if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
0382       template <class ExecPolicy, class F>
0383       typename std::enable_if<detail::is_execution_policy<ExecPolicy>::value,
0384         bool>::type
0385       visit_while(ExecPolicy&& p, F f)
0386       {
0387         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0388         BOOST_UNORDERED_STATIC_ASSERT_EXEC_POLICY(ExecPolicy)
0389         return table_.visit_while(p, f);
0390       }
0391 
0392       template <class ExecPolicy, class F>
0393       typename std::enable_if<detail::is_execution_policy<ExecPolicy>::value,
0394         bool>::type
0395       visit_while(ExecPolicy&& p, F f) const
0396       {
0397         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0398         BOOST_UNORDERED_STATIC_ASSERT_EXEC_POLICY(ExecPolicy)
0399         return table_.visit_while(p, f);
0400       }
0401 
0402       template <class ExecPolicy, class F>
0403       typename std::enable_if<detail::is_execution_policy<ExecPolicy>::value,
0404         bool>::type
0405       cvisit_while(ExecPolicy&& p, F f) const
0406       {
0407         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0408         BOOST_UNORDERED_STATIC_ASSERT_EXEC_POLICY(ExecPolicy)
0409         return table_.cvisit_while(p, f);
0410       }
0411 #endif
0412 
0413       /// Modifiers
0414       ///
0415 
0416       BOOST_FORCEINLINE bool insert(value_type const& obj)
0417       {
0418         return table_.insert(obj);
0419       }
0420 
0421       BOOST_FORCEINLINE bool insert(value_type&& obj)
0422       {
0423         return table_.insert(std::move(obj));
0424       }
0425 
0426       template <class K>
0427       BOOST_FORCEINLINE typename std::enable_if<
0428         detail::are_transparent<K, hasher, key_equal>::value,
0429         bool >::type
0430       insert(K&& k)
0431       {
0432         return table_.try_emplace(std::forward<K>(k));
0433       }
0434 
0435       template <class InputIterator>
0436       size_type insert(InputIterator begin, InputIterator end)
0437       {
0438         size_type count_elements = 0;
0439         for (auto pos = begin; pos != end; ++pos, ++count_elements) {
0440           table_.emplace(*pos);
0441         }
0442         return count_elements;
0443       }
0444 
0445       size_type insert(std::initializer_list<value_type> ilist)
0446       {
0447         return this->insert(ilist.begin(), ilist.end());
0448       }
0449 
0450       insert_return_type insert(node_type&& nh)
0451       {
0452         using access = detail::foa::node_handle_access;
0453 
0454         if (nh.empty()) {
0455           return {false, node_type{}};
0456         }
0457 
0458         // Caveat: get_allocator() incurs synchronization (not cheap)
0459         BOOST_ASSERT(get_allocator() == nh.get_allocator());
0460 
0461         if (table_.insert(std::move(access::element(nh)))) {
0462           access::reset(nh);
0463           return {true, node_type{}};
0464         } else {
0465           return {false, std::move(nh)};
0466         }
0467       }
0468 
0469       template <class F>
0470       BOOST_FORCEINLINE bool insert_or_visit(value_type const& obj, F f)
0471       {
0472         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0473         return table_.insert_or_visit(obj, f);
0474       }
0475 
0476       template <class F>
0477       BOOST_FORCEINLINE bool insert_or_visit(value_type&& obj, F f)
0478       {
0479         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0480         return table_.insert_or_visit(std::move(obj), f);
0481       }
0482 
0483       template <class K, class F>
0484       BOOST_FORCEINLINE typename std::enable_if<
0485         detail::are_transparent<K, hasher, key_equal>::value,
0486         bool >::type
0487       insert_or_visit(K&& k, F f)
0488       {
0489         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0490         return table_.try_emplace_or_visit(std::forward<K>(k), f);
0491       }
0492 
0493       template <class InputIterator, class F>
0494       size_type insert_or_visit(InputIterator first, InputIterator last, F f)
0495       {
0496         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0497         size_type count_elements = 0;
0498         for (; first != last; ++first, ++count_elements) {
0499           table_.emplace_or_visit(*first, f);
0500         }
0501         return count_elements;
0502       }
0503 
0504       template <class F>
0505       size_type insert_or_visit(std::initializer_list<value_type> ilist, F f)
0506       {
0507         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0508         return this->insert_or_visit(ilist.begin(), ilist.end(), std::ref(f));
0509       }
0510 
0511       template <class F>
0512       insert_return_type insert_or_visit(node_type&& nh, F f)
0513       {
0514         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0515         using access = detail::foa::node_handle_access;
0516 
0517         if (nh.empty()) {
0518           return {false, node_type{}};
0519         }
0520 
0521         // Caveat: get_allocator() incurs synchronization (not cheap)
0522         BOOST_ASSERT(get_allocator() == nh.get_allocator());
0523 
0524         if (table_.insert_or_visit(std::move(access::element(nh)), f)) {
0525           access::reset(nh);
0526           return {true, node_type{}};
0527         } else {
0528           return {false, std::move(nh)};
0529         }
0530       }
0531 
0532       template <class F>
0533       BOOST_FORCEINLINE bool insert_or_cvisit(value_type const& obj, F f)
0534       {
0535         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0536         return table_.insert_or_cvisit(obj, f);
0537       }
0538 
0539       template <class F>
0540       BOOST_FORCEINLINE bool insert_or_cvisit(value_type&& obj, F f)
0541       {
0542         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0543         return table_.insert_or_cvisit(std::move(obj), f);
0544       }
0545 
0546       template <class K, class F>
0547       BOOST_FORCEINLINE typename std::enable_if<
0548         detail::are_transparent<K, hasher, key_equal>::value,
0549         bool >::type
0550       insert_or_cvisit(K&& k, F f)
0551       {
0552         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0553         return table_.try_emplace_or_cvisit(std::forward<K>(k), f);
0554       }
0555 
0556       template <class InputIterator, class F>
0557       size_type insert_or_cvisit(InputIterator first, InputIterator last, F f)
0558       {
0559         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0560         size_type count_elements = 0;
0561         for (; first != last; ++first, ++count_elements) {
0562           table_.emplace_or_cvisit(*first, f);
0563         }
0564         return count_elements;
0565       }
0566 
0567       template <class F>
0568       size_type insert_or_cvisit(std::initializer_list<value_type> ilist, F f)
0569       {
0570         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0571         return this->insert_or_cvisit(ilist.begin(), ilist.end(), std::ref(f));
0572       }
0573 
0574       template <class F>
0575       insert_return_type insert_or_cvisit(node_type&& nh, F f)
0576       {
0577         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
0578         using access = detail::foa::node_handle_access;
0579 
0580         if (nh.empty()) {
0581           return {false, node_type{}};
0582         }
0583 
0584         // Caveat: get_allocator() incurs synchronization (not cheap)
0585         BOOST_ASSERT(get_allocator() == nh.get_allocator());
0586 
0587         if (table_.insert_or_cvisit(std::move(access::element(nh)), f)) {
0588           access::reset(nh);
0589           return {true, node_type{}};
0590         } else {
0591           return {false, std::move(nh)};
0592         }
0593       }
0594 
0595       template <class F1, class F2>
0596       BOOST_FORCEINLINE bool insert_and_visit(
0597         value_type const& obj, F1 f1, F2 f2)
0598       {
0599         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0600         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0601         return table_.insert_and_visit(obj, f1, f2);
0602       }
0603 
0604       template <class F1, class F2>
0605       BOOST_FORCEINLINE bool insert_and_visit(value_type&& obj, F1 f1, F2 f2)
0606       {
0607         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0608         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0609         return table_.insert_and_visit(std::move(obj), f1, f2);
0610       }
0611 
0612       template <class K, class F1, class F2>
0613       BOOST_FORCEINLINE typename std::enable_if<
0614         detail::are_transparent<K, hasher, key_equal>::value,
0615         bool >::type
0616       insert_and_visit(K&& k, F1 f1, F2 f2)
0617       {
0618         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0619         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0620         return table_.try_emplace_and_visit(std::forward<K>(k), f1, f2);
0621       }
0622 
0623       template <class InputIterator, class F1, class F2>
0624       size_type insert_and_visit(
0625         InputIterator first, InputIterator last, F1 f1, F2 f2)
0626       {
0627         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0628         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0629         size_type count_elements = 0;
0630         for (; first != last; ++first, ++count_elements) {
0631           table_.emplace_and_visit(*first, f1, f2);
0632         }
0633         return count_elements;
0634       }
0635 
0636       template <class F1, class F2>
0637       size_type insert_and_visit(
0638         std::initializer_list<value_type> ilist, F1 f1, F2 f2)
0639       {
0640         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0641         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0642         return this->insert_and_visit(
0643           ilist.begin(), ilist.end(), std::ref(f1), std::ref(f2));
0644       }
0645 
0646       template <class F1, class F2>
0647       insert_return_type insert_and_visit(node_type&& nh, F1 f1, F2 f2)
0648       {
0649         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0650         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0651         using access = detail::foa::node_handle_access;
0652 
0653         if (nh.empty()) {
0654           return {false, node_type{}};
0655         }
0656 
0657         // Caveat: get_allocator() incurs synchronization (not cheap)
0658         BOOST_ASSERT(get_allocator() == nh.get_allocator());
0659 
0660         if (table_.insert_and_visit(std::move(access::element(nh)), f1, f2)) {
0661           access::reset(nh);
0662           return {true, node_type{}};
0663         } else {
0664           return {false, std::move(nh)};
0665         }
0666       }
0667 
0668       template <class F1, class F2>
0669       BOOST_FORCEINLINE bool insert_and_cvisit(
0670         value_type const& obj, F1 f1, F2 f2)
0671       {
0672         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0673         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0674         return table_.insert_and_cvisit(obj, f1, f2);
0675       }
0676 
0677       template <class F1, class F2>
0678       BOOST_FORCEINLINE bool insert_and_cvisit(value_type&& obj, F1 f1, F2 f2)
0679       {
0680         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0681         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0682         return table_.insert_and_cvisit(std::move(obj), f1, f2);
0683       }
0684 
0685       template <class K, class F1, class F2>
0686       BOOST_FORCEINLINE typename std::enable_if<
0687         detail::are_transparent<K, hasher, key_equal>::value,
0688         bool >::type
0689       insert_and_cvisit(K&& k, F1 f1, F2 f2)
0690       {
0691         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0692         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0693         return table_.try_emplace_and_cvisit(std::forward<K>(k), f1, f2);
0694       }
0695 
0696       template <class InputIterator, class F1, class F2>
0697       size_type insert_and_cvisit(
0698         InputIterator first, InputIterator last, F1 f1, F2 f2)
0699       {
0700         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0701         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0702         size_type count_elements = 0;
0703         for (; first != last; ++first, ++count_elements) {
0704           table_.emplace_and_cvisit(*first, f1, f2);
0705         }
0706         return count_elements;
0707       }
0708 
0709       template <class F1, class F2>
0710       size_type insert_and_cvisit(
0711         std::initializer_list<value_type> ilist, F1 f1, F2 f2)
0712       {
0713         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0714         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0715         return this->insert_and_cvisit(
0716           ilist.begin(), ilist.end(), std::ref(f1), std::ref(f2));
0717       }
0718 
0719       template <class F1, class F2>
0720       insert_return_type insert_and_cvisit(node_type&& nh, F1 f1, F2 f2)
0721       {
0722         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F1)
0723         BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F2)
0724         using access = detail::foa::node_handle_access;
0725 
0726         if (nh.empty()) {
0727           return {false, node_type{}};
0728         }
0729 
0730         // Caveat: get_allocator() incurs synchronization (not cheap)
0731         BOOST_ASSERT(get_allocator() == nh.get_allocator());
0732 
0733         if (table_.insert_and_cvisit(std::move(access::element(nh)), f1, f2)) {
0734           access::reset(nh);
0735           return {true, node_type{}};
0736         } else {
0737           return {false, std::move(nh)};
0738         }
0739       }
0740 
0741       template <class... Args> BOOST_FORCEINLINE bool emplace(Args&&... args)
0742       {
0743         return table_.emplace(std::forward<Args>(args)...);
0744       }
0745 
0746       template <class Arg, class... Args>
0747       BOOST_FORCEINLINE bool emplace_or_visit(Arg&& arg, Args&&... args)
0748       {
0749         BOOST_UNORDERED_STATIC_ASSERT_LAST_ARG_CONST_INVOCABLE(Arg, Args...)
0750         return table_.emplace_or_visit(
0751           std::forward<Arg>(arg), std::forward<Args>(args)...);
0752       }
0753 
0754       template <class Arg, class... Args>
0755       BOOST_FORCEINLINE bool emplace_or_cvisit(Arg&& arg, Args&&... args)
0756       {
0757         BOOST_UNORDERED_STATIC_ASSERT_LAST_ARG_CONST_INVOCABLE(Arg, Args...)
0758         return table_.emplace_or_cvisit(
0759           std::forward<Arg>(arg), std::forward<Args>(args)...);
0760       }
0761 
0762       template <class Arg1, class Arg2, class... Args>
0763       BOOST_FORCEINLINE bool emplace_and_visit(
0764         Arg1&& arg1, Arg2&& arg2, Args&&... args)
0765       {
0766         BOOST_UNORDERED_STATIC_ASSERT_PENULTIMATE_ARG_CONST_INVOCABLE(
0767           Arg1, Arg2, Args...)
0768         BOOST_UNORDERED_STATIC_ASSERT_LAST_ARG_CONST_INVOCABLE(Arg2, Args...)
0769         return table_.emplace_and_visit(
0770           std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
0771           std::forward<Args>(args)...);
0772       }
0773 
0774       template <class Arg1, class Arg2, class... Args>
0775       BOOST_FORCEINLINE bool emplace_and_cvisit(
0776         Arg1&& arg1, Arg2&& arg2, Args&&... args)
0777       {
0778         BOOST_UNORDERED_STATIC_ASSERT_PENULTIMATE_ARG_CONST_INVOCABLE(
0779           Arg1, Arg2, Args...)
0780         BOOST_UNORDERED_STATIC_ASSERT_LAST_ARG_CONST_INVOCABLE(Arg2, Args...)
0781         return table_.emplace_and_cvisit(
0782           std::forward<Arg1>(arg1), std::forward<Arg2>(arg2),
0783           std::forward<Args>(args)...);
0784       }
0785 
0786       BOOST_FORCEINLINE size_type erase(key_type const& k)
0787       {
0788         return table_.erase(k);
0789       }
0790 
0791       template <class K>
0792       BOOST_FORCEINLINE typename std::enable_if<
0793         detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
0794       erase(K&& k)
0795       {
0796         return table_.erase(std::forward<K>(k));
0797       }
0798 
0799       template <class F>
0800       BOOST_FORCEINLINE size_type erase_if(key_type const& k, F f)
0801       {
0802         return table_.erase_if(k, f);
0803       }
0804 
0805       template <class K, class F>
0806       BOOST_FORCEINLINE typename std::enable_if<
0807         detail::are_transparent<K, hasher, key_equal>::value &&
0808           !detail::is_execution_policy<K>::value,
0809         size_type>::type
0810       erase_if(K&& k, F f)
0811       {
0812         return table_.erase_if(std::forward<K>(k), f);
0813       }
0814 
0815 #if defined(BOOST_UNORDERED_PARALLEL_ALGORITHMS)
0816       template <class ExecPolicy, class F>
0817       typename std::enable_if<detail::is_execution_policy<ExecPolicy>::value,
0818         void>::type
0819       erase_if(ExecPolicy&& p, F f)
0820       {
0821         BOOST_UNORDERED_STATIC_ASSERT_EXEC_POLICY(ExecPolicy)
0822         table_.erase_if(p, f);
0823       }
0824 #endif
0825 
0826       template <class F> size_type erase_if(F f) { return table_.erase_if(f); }
0827 
0828       void swap(concurrent_node_set& other) noexcept(
0829         boost::allocator_is_always_equal<Allocator>::type::value ||
0830         boost::allocator_propagate_on_container_swap<Allocator>::type::value)
0831       {
0832         return table_.swap(other.table_);
0833       }
0834 
0835       node_type extract(key_type const& key)
0836       {
0837         node_type nh;
0838         table_.extract(key, detail::foa::node_handle_emplacer(nh));
0839         return nh;
0840       }
0841 
0842       template <class K>
0843       typename std::enable_if<
0844         detail::are_transparent<K, hasher, key_equal>::value, node_type>::type
0845       extract(K const& key)
0846       {
0847         node_type nh;
0848         table_.extract(key, detail::foa::node_handle_emplacer(nh));
0849         return nh;
0850       }
0851 
0852       template <class F>
0853       node_type extract_if(key_type const& key, F f)
0854       {
0855         node_type nh;
0856         table_.extract_if(key, f, detail::foa::node_handle_emplacer(nh));
0857         return nh;
0858       }
0859 
0860       template <class K, class F>
0861       typename std::enable_if<
0862         detail::are_transparent<K, hasher, key_equal>::value, node_type>::type
0863       extract_if(K const& key, F f)
0864       {
0865         node_type nh;
0866         table_.extract_if(key, f, detail::foa::node_handle_emplacer(nh));
0867         return nh;
0868       }
0869 
0870       void clear() noexcept { table_.clear(); }
0871 
0872       template <typename H2, typename P2>
0873       size_type merge(concurrent_node_set<Key, H2, P2, Allocator>& x)
0874       {
0875         BOOST_ASSERT(get_allocator() == x.get_allocator());
0876         return table_.merge(x.table_);
0877       }
0878 
0879       template <typename H2, typename P2>
0880       size_type merge(concurrent_node_set<Key, H2, P2, Allocator>&& x)
0881       {
0882         return merge(x);
0883       }
0884 
0885       BOOST_FORCEINLINE size_type count(key_type const& k) const
0886       {
0887         return table_.count(k);
0888       }
0889 
0890       template <class K>
0891       BOOST_FORCEINLINE typename std::enable_if<
0892         detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
0893       count(K const& k)
0894       {
0895         return table_.count(k);
0896       }
0897 
0898       BOOST_FORCEINLINE bool contains(key_type const& k) const
0899       {
0900         return table_.contains(k);
0901       }
0902 
0903       template <class K>
0904       BOOST_FORCEINLINE typename std::enable_if<
0905         detail::are_transparent<K, hasher, key_equal>::value, bool>::type
0906       contains(K const& k) const
0907       {
0908         return table_.contains(k);
0909       }
0910 
0911       /// Hash Policy
0912       ///
0913       size_type bucket_count() const noexcept { return table_.capacity(); }
0914 
0915       float load_factor() const noexcept { return table_.load_factor(); }
0916       float max_load_factor() const noexcept
0917       {
0918         return table_.max_load_factor();
0919       }
0920       void max_load_factor(float) {}
0921       size_type max_load() const noexcept { return table_.max_load(); }
0922 
0923       void rehash(size_type n) { table_.rehash(n); }
0924       void reserve(size_type n) { table_.reserve(n); }
0925 
0926 #if defined(BOOST_UNORDERED_ENABLE_STATS)
0927       /// Stats
0928       ///
0929       stats get_stats() const { return table_.get_stats(); }
0930 
0931       void reset_stats() noexcept { table_.reset_stats(); }
0932 #endif
0933 
0934       /// Observers
0935       ///
0936       allocator_type get_allocator() const noexcept
0937       {
0938         return table_.get_allocator();
0939       }
0940 
0941       hasher hash_function() const { return table_.hash_function(); }
0942       key_equal key_eq() const { return table_.key_eq(); }
0943     };
0944 
0945     template <class Key, class Hash, class KeyEqual, class Allocator>
0946     bool operator==(
0947       concurrent_node_set<Key, Hash, KeyEqual, Allocator> const& lhs,
0948       concurrent_node_set<Key, Hash, KeyEqual, Allocator> const& rhs)
0949     {
0950       return lhs.table_ == rhs.table_;
0951     }
0952 
0953     template <class Key, class Hash, class KeyEqual, class Allocator>
0954     bool operator!=(
0955       concurrent_node_set<Key, Hash, KeyEqual, Allocator> const& lhs,
0956       concurrent_node_set<Key, Hash, KeyEqual, Allocator> const& rhs)
0957     {
0958       return !(lhs == rhs);
0959     }
0960 
0961     template <class Key, class Hash, class Pred, class Alloc>
0962     void swap(concurrent_node_set<Key, Hash, Pred, Alloc>& x,
0963       concurrent_node_set<Key, Hash, Pred, Alloc>& y)
0964       noexcept(noexcept(x.swap(y)))
0965     {
0966       x.swap(y);
0967     }
0968 
0969     template <class K, class H, class P, class A, class Predicate>
0970     typename concurrent_node_set<K, H, P, A>::size_type erase_if(
0971       concurrent_node_set<K, H, P, A>& c, Predicate pred)
0972     {
0973       return c.table_.erase_if(pred);
0974     }
0975 
0976     template<class Archive, class K, class H, class KE, class A>
0977     void serialize(
0978       Archive& ar, concurrent_node_set<K, H, KE, A>& c, unsigned int)
0979     {
0980       ar & core::make_nvp("table",c.table_);
0981     }
0982 
0983 #if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
0984 
0985     template <class InputIterator,
0986       class Hash =
0987         boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
0988       class Pred =
0989         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
0990       class Allocator = std::allocator<
0991         typename std::iterator_traits<InputIterator>::value_type>,
0992       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
0993       class = std::enable_if_t<detail::is_hash_v<Hash> >,
0994       class = std::enable_if_t<detail::is_pred_v<Pred> >,
0995       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
0996     concurrent_node_set(InputIterator, InputIterator,
0997       std::size_t = boost::unordered::detail::foa::default_bucket_count,
0998       Hash = Hash(), Pred = Pred(), Allocator = Allocator())
0999       -> concurrent_node_set<
1000         typename std::iterator_traits<InputIterator>::value_type, Hash, Pred,
1001         Allocator>;
1002 
1003     template <class T, class Hash = boost::hash<T>,
1004       class Pred = std::equal_to<T>, class Allocator = std::allocator<T>,
1005       class = std::enable_if_t<detail::is_hash_v<Hash> >,
1006       class = std::enable_if_t<detail::is_pred_v<Pred> >,
1007       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1008     concurrent_node_set(std::initializer_list<T>,
1009       std::size_t = boost::unordered::detail::foa::default_bucket_count,
1010       Hash = Hash(), Pred = Pred(), Allocator = Allocator())
1011       -> concurrent_node_set< T, Hash, Pred, Allocator>;
1012 
1013     template <class InputIterator, class Allocator,
1014       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1015       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1016     concurrent_node_set(InputIterator, InputIterator, std::size_t, Allocator)
1017       -> concurrent_node_set<
1018         typename std::iterator_traits<InputIterator>::value_type,
1019         boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
1020         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
1021         Allocator>;
1022 
1023     template <class InputIterator, class Allocator,
1024       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1025       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1026     concurrent_node_set(InputIterator, InputIterator, Allocator)
1027       -> concurrent_node_set<
1028         typename std::iterator_traits<InputIterator>::value_type,
1029         boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
1030         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
1031         Allocator>;
1032 
1033     template <class InputIterator, class Hash, class Allocator,
1034       class = std::enable_if_t<detail::is_hash_v<Hash> >,
1035       class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
1036       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1037     concurrent_node_set(
1038       InputIterator, InputIterator, std::size_t, Hash, Allocator)
1039       -> concurrent_node_set<
1040         typename std::iterator_traits<InputIterator>::value_type, Hash,
1041         std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
1042         Allocator>;
1043 
1044     template <class T, class Allocator,
1045       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1046     concurrent_node_set(std::initializer_list<T>, std::size_t, Allocator)
1047       -> concurrent_node_set<T, boost::hash<T>,std::equal_to<T>, Allocator>;
1048 
1049     template <class T, class Allocator,
1050       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1051     concurrent_node_set(std::initializer_list<T >, Allocator)
1052       -> concurrent_node_set<T, boost::hash<T>, std::equal_to<T>, Allocator>;
1053 
1054     template <class T, class Hash, class Allocator,
1055       class = std::enable_if_t<detail::is_hash_v<Hash> >,
1056       class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
1057     concurrent_node_set(std::initializer_list<T >, std::size_t,Hash, Allocator)
1058       -> concurrent_node_set<T, Hash, std::equal_to<T>, Allocator>;
1059 
1060 #endif
1061 
1062   } // namespace unordered
1063 } // namespace boost
1064 
1065 #endif // BOOST_UNORDERED_CONCURRENT_NODE_SET_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!