diff options
Diffstat (limited to '3rdParty/Boost/src/boost/unordered/detail/buckets.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/buckets.hpp | 399 |
1 files changed, 264 insertions, 135 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp index def5c7c..fd038b7 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp @@ -7,14 +7,17 @@ #ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED #define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED -#if defined(_MSC_VER) && (_MSC_VER >= 1020) -# pragma once +#include <boost/config.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +#pragma once #endif #include <boost/unordered/detail/util.hpp> #include <boost/unordered/detail/allocate.hpp> #include <boost/type_traits/aligned_storage.hpp> #include <boost/type_traits/alignment_of.hpp> +#include <boost/type_traits/is_nothrow_move_constructible.hpp> +#include <boost/type_traits/is_nothrow_move_assignable.hpp> #include <boost/swap.hpp> #include <boost/assert.hpp> #include <boost/limits.hpp> @@ -30,6 +33,10 @@ namespace boost { namespace unordered { namespace detail { }}} +// The 'iterator_detail' namespace was a misguided attempt at avoiding ADL +// in the detail namespace. It didn't work because the template parameters +// were in detail. I'm not changing it at the moment to be safe. I might +// do in the future if I change the iterator types. namespace boost { namespace unordered { namespace iterator_detail { //////////////////////////////////////////////////////////////////////////// @@ -37,49 +44,50 @@ namespace boost { namespace unordered { namespace iterator_detail { // // all no throw - template <typename NodePointer, typename Value> struct iterator; - template <typename ConstNodePointer, typename NodePointer, - typename Value> struct c_iterator; - template <typename NodePointer, typename Value, typename Policy> - struct l_iterator; - template <typename ConstNodePointer, typename NodePointer, - typename Value, typename Policy> struct cl_iterator; + template <typename Node> struct iterator; + template <typename Node, typename ConstNodePointer> struct c_iterator; + template <typename Node, typename Policy> struct l_iterator; + template <typename Node, typename ConstNodePointer, typename Policy> + struct cl_iterator; // Local Iterators // // all no throw - template <typename NodePointer, typename Value, typename Policy> + template <typename Node, typename Policy> struct l_iterator : public boost::iterator< - std::forward_iterator_tag, Value, std::ptrdiff_t, - NodePointer, Value&> + std::forward_iterator_tag, + typename Node::value_type, + std::ptrdiff_t, + typename Node::node_pointer, + typename Node::value_type&> { #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) - template <typename ConstNodePointer, typename NodePointer2, - typename Value2, typename Policy2> + template <typename Node2, typename ConstNodePointer, typename Policy2> friend struct boost::unordered::iterator_detail::cl_iterator; private: #endif - typedef NodePointer node_pointer; - typedef boost::unordered::iterator_detail::iterator<NodePointer, Value> - iterator; + typedef typename Node::node_pointer node_pointer; + typedef boost::unordered::iterator_detail::iterator<Node> iterator; node_pointer ptr_; std::size_t bucket_; std::size_t bucket_count_; public: - l_iterator() : ptr_() {} + typedef typename Node::value_type value_type; - l_iterator(iterator x, std::size_t b, std::size_t c) + l_iterator() BOOST_NOEXCEPT : ptr_() {} + + l_iterator(iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT : ptr_(x.node_), bucket_(b), bucket_count_(c) {} - Value& operator*() const { + value_type& operator*() const { return ptr_->value(); } - Value* operator->() const { + value_type* operator->() const { return ptr_->value_ptr(); } @@ -97,51 +105,53 @@ namespace boost { namespace unordered { namespace iterator_detail { return tmp; } - bool operator==(l_iterator x) const { + bool operator==(l_iterator x) const BOOST_NOEXCEPT { return ptr_ == x.ptr_; } - bool operator!=(l_iterator x) const { + bool operator!=(l_iterator x) const BOOST_NOEXCEPT { return ptr_ != x.ptr_; } }; - template <typename ConstNodePointer, typename NodePointer, typename Value, - typename Policy> + template <typename Node, typename ConstNodePointer, typename Policy> struct cl_iterator : public boost::iterator< - std::forward_iterator_tag, Value, std::ptrdiff_t, - ConstNodePointer, Value const&> + std::forward_iterator_tag, + typename Node::value_type, + std::ptrdiff_t, + ConstNodePointer, + typename Node::value_type const&> { friend struct boost::unordered::iterator_detail::l_iterator - <NodePointer, Value, Policy>; + <Node, Policy>; private: - typedef NodePointer node_pointer; - typedef boost::unordered::iterator_detail::iterator<NodePointer, Value> - iterator; + typedef typename Node::node_pointer node_pointer; + typedef boost::unordered::iterator_detail::iterator<Node> iterator; node_pointer ptr_; std::size_t bucket_; std::size_t bucket_count_; public: - cl_iterator() : ptr_() {} + typedef typename Node::value_type value_type; + + cl_iterator() BOOST_NOEXCEPT : ptr_() {} - cl_iterator(iterator x, std::size_t b, std::size_t c) : + cl_iterator(iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT : ptr_(x.node_), bucket_(b), bucket_count_(c) {} cl_iterator(boost::unordered::iterator_detail::l_iterator< - NodePointer, Value, Policy> const& x) : + Node, Policy> const& x) BOOST_NOEXCEPT : ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_) {} - Value const& - operator*() const { + value_type const& operator*() const { return ptr_->value(); } - Value const* operator->() const { + value_type const* operator->() const { return ptr_->value_ptr(); } @@ -159,27 +169,34 @@ namespace boost { namespace unordered { namespace iterator_detail { return tmp; } - friend bool operator==(cl_iterator const& x, cl_iterator const& y) { + friend bool operator==(cl_iterator const& x, cl_iterator const& y) + BOOST_NOEXCEPT + { return x.ptr_ == y.ptr_; } - friend bool operator!=(cl_iterator const& x, cl_iterator const& y) { + friend bool operator!=(cl_iterator const& x, cl_iterator const& y) + BOOST_NOEXCEPT + { return x.ptr_ != y.ptr_; } }; - template <typename NodePointer, typename Value> + template <typename Node> struct iterator : public boost::iterator< - std::forward_iterator_tag, Value, std::ptrdiff_t, - NodePointer, Value&> + std::forward_iterator_tag, + typename Node::value_type, + std::ptrdiff_t, + typename Node::node_pointer, + typename Node::value_type&> { #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) - template <typename, typename, typename> + template <typename, typename> friend struct boost::unordered::iterator_detail::c_iterator; - template <typename, typename, typename> + template <typename, typename> friend struct boost::unordered::iterator_detail::l_iterator; - template <typename, typename, typename, typename> + template <typename, typename, typename> friend struct boost::unordered::iterator_detail::cl_iterator; template <typename> friend struct boost::unordered::detail::table; @@ -189,20 +206,23 @@ namespace boost { namespace unordered { namespace iterator_detail { friend struct boost::unordered::detail::grouped_table_impl; private: #endif - typedef NodePointer node_pointer; + typedef typename Node::node_pointer node_pointer; node_pointer node_; public: - iterator() : node_() {} + typedef typename Node::value_type value_type; + + iterator() BOOST_NOEXCEPT : node_() {} - explicit iterator(node_pointer const& x) : node_(x) {} + explicit iterator(typename Node::link_pointer x) BOOST_NOEXCEPT : + node_(static_cast<node_pointer>(x)) {} - Value& operator*() const { + value_type& operator*() const { return node_->value(); } - Value* operator->() const { + value_type* operator->() const { return &node_->value(); } @@ -217,23 +237,25 @@ namespace boost { namespace unordered { namespace iterator_detail { return tmp; } - bool operator==(iterator const& x) const { + bool operator==(iterator const& x) const BOOST_NOEXCEPT { return node_ == x.node_; } - bool operator!=(iterator const& x) const { + bool operator!=(iterator const& x) const BOOST_NOEXCEPT { return node_ != x.node_; } }; - template <typename ConstNodePointer, typename NodePointer, typename Value> + template <typename Node, typename ConstNodePointer> struct c_iterator : public boost::iterator< - std::forward_iterator_tag, Value, std::ptrdiff_t, - ConstNodePointer, Value const&> + std::forward_iterator_tag, + typename Node::value_type, + std::ptrdiff_t, + ConstNodePointer, + typename Node::value_type const&> { - friend struct boost::unordered::iterator_detail::iterator< - NodePointer, Value>; + friend struct boost::unordered::iterator_detail::iterator<Node>; #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) template <typename> @@ -245,26 +267,26 @@ namespace boost { namespace unordered { namespace iterator_detail { private: #endif - - typedef NodePointer node_pointer; - typedef boost::unordered::iterator_detail::iterator<NodePointer, Value> - iterator; + typedef typename Node::node_pointer node_pointer; + typedef boost::unordered::iterator_detail::iterator<Node> iterator; node_pointer node_; public: - c_iterator() : node_() {} + typedef typename Node::value_type value_type; - explicit c_iterator(node_pointer const& x) : node_(x) {} + c_iterator() BOOST_NOEXCEPT : node_() {} - c_iterator(boost::unordered::iterator_detail::iterator< - NodePointer, Value> const& x) : node_(x.node_) {} + explicit c_iterator(typename Node::link_pointer x) BOOST_NOEXCEPT : + node_(static_cast<node_pointer>(x)) {} - Value const& operator*() const { + c_iterator(iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {} + + value_type const& operator*() const { return node_->value(); } - Value const* operator->() const { + value_type const* operator->() const { return &node_->value(); } @@ -279,11 +301,15 @@ namespace boost { namespace unordered { namespace iterator_detail { return tmp; } - friend bool operator==(c_iterator const& x, c_iterator const& y) { + friend bool operator==(c_iterator const& x, c_iterator const& y) + BOOST_NOEXCEPT + { return x.node_ == y.node_; } - friend bool operator!=(c_iterator const& x, c_iterator const& y) { + friend bool operator!=(c_iterator const& x, c_iterator const& y) + BOOST_NOEXCEPT + { return x.node_ != y.node_; } }; @@ -310,9 +336,6 @@ namespace boost { namespace unordered { namespace detail { protected: node_allocator& alloc_; - - private: - node_pointer node_; bool node_constructed_; bool value_constructed_; @@ -335,7 +358,7 @@ namespace boost { namespace unordered { namespace detail { void construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS) { construct(); - boost::unordered::detail::construct_value_impl( + boost::unordered::detail::func::construct_value_impl( alloc_, node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); value_constructed_ = true; } @@ -344,7 +367,7 @@ namespace boost { namespace unordered { namespace detail { void construct_with_value2(BOOST_FWD_REF(A0) a0) { construct(); - boost::unordered::detail::construct_value_impl( + boost::unordered::detail::func::construct_value_impl( alloc_, node_->value_ptr(), BOOST_UNORDERED_EMPLACE_ARGS1(boost::forward<A0>(a0))); value_constructed_ = true; @@ -374,12 +397,12 @@ namespace boost { namespace unordered { namespace detail { { if (node_) { if (value_constructed_) { - boost::unordered::detail::destroy_value_impl(alloc_, + boost::unordered::detail::func::destroy_value_impl(alloc_, node_->value_ptr()); } if (node_constructed_) { - node_allocator_traits::destroy(alloc_, + boost::unordered::detail::func::destroy( boost::addressof(*node_)); } @@ -396,9 +419,8 @@ namespace boost { namespace unordered { namespace detail { node_ = node_allocator_traits::allocate(alloc_, 1); - node_allocator_traits::construct(alloc_, - boost::addressof(*node_), node()); - node_->init(static_cast<typename node::link_pointer>(node_)); + new ((void*) boost::addressof(*node_)) node(); + node_->init(node_); node_constructed_ = true; } else { @@ -406,7 +428,7 @@ namespace boost { namespace unordered { namespace detail { if (value_constructed_) { - boost::unordered::detail::destroy_value_impl(alloc_, + boost::unordered::detail::func::destroy_value_impl(alloc_, node_->value_ptr()); value_constructed_ = false; } @@ -432,8 +454,7 @@ namespace boost { namespace unordered { namespace detail { typedef typename node_allocator_traits::pointer node_pointer; typedef typename node::value_type value_type; typedef typename node::link_pointer link_pointer; - typedef boost::unordered::iterator_detail:: - iterator<node_pointer, value_type> iterator; + typedef boost::unordered::iterator_detail::iterator<node> iterator; node_pointer nodes_; @@ -445,7 +466,7 @@ namespace boost { namespace unordered { namespace detail { nodes_() { if (b.size_) { - typename Table::previous_pointer prev = b.get_previous_start(); + typename Table::link_pointer prev = b.get_previous_start(); nodes_ = static_cast<node_pointer>(prev->next_); prev->next_ = link_pointer(); b.size_ = 0; @@ -454,60 +475,61 @@ namespace boost { namespace unordered { namespace detail { ~node_holder(); + void node_for_assignment() + { + if (!this->node_ && nodes_) { + this->node_ = nodes_; + nodes_ = static_cast<node_pointer>(nodes_->next_); + this->node_->init(this->node_); + this->node_->next_ = link_pointer(); + + this->node_constructed_ = true; + this->value_constructed_ = true; + } + } + template <typename T> inline void assign_impl(T const& v) { - nodes_->value() = v; + if (this->node_ && this->value_constructed_) { + this->node_->value() = v; + } + else { + this->construct_with_value2(v); + } } template <typename T1, typename T2> inline void assign_impl(std::pair<T1 const, T2> const& v) { - const_cast<T1&>(nodes_->value().first) = v.first; - nodes_->value().second = v.second; + this->construct_with_value2(v); } template <typename T> inline void move_assign_impl(T& v) { - nodes_->value() = boost::move(v); + if (this->node_ && this->value_constructed_) { + this->node_->value() = boost::move(v); + } + else { + this->construct_with_value2(boost::move(v)); + } } template <typename T1, typename T2> inline void move_assign_impl(std::pair<T1 const, T2>& v) { - // TODO: Move key as well? - const_cast<T1&>(nodes_->value().first) = - boost::move(const_cast<T1&>(v.first)); - nodes_->value().second = boost::move(v.second); + this->construct_with_value2(boost::move(v)); } node_pointer copy_of(value_type const& v) { - if (nodes_) { - assign_impl(v); - node_pointer p = nodes_; - nodes_ = static_cast<node_pointer>(p->next_); - p->init(static_cast<typename node::link_pointer>(p)); - p->next_ = link_pointer(); - return p; - } - else { - this->construct_with_value2(v); - return base::release(); - } + node_for_assignment(); + assign_impl(v); + return base::release(); } node_pointer move_copy_of(value_type& v) { - if (nodes_) { - move_assign_impl(v); - node_pointer p = nodes_; - nodes_ = static_cast<node_pointer>(p->next_); - p->init(static_cast<typename node::link_pointer>(p)); - p->next_ = link_pointer(); - return p; - } - else { - this->construct_with_value2(boost::move(v)); - return base::release(); - } + node_for_assignment(); + move_assign_impl(v); + return base::release(); } iterator begin() const @@ -523,9 +545,9 @@ namespace boost { namespace unordered { namespace detail { node_pointer p = nodes_; nodes_ = static_cast<node_pointer>(p->next_); - boost::unordered::detail::destroy_value_impl(this->alloc_, + boost::unordered::detail::func::destroy_value_impl(this->alloc_, p->value_ptr()); - node_allocator_traits::destroy(this->alloc_, boost::addressof(*p)); + boost::unordered::detail::func::destroy(boost::addressof(*p)); node_allocator_traits::deallocate(this->alloc_, p, 1); } } @@ -537,12 +559,12 @@ namespace boost { namespace unordered { namespace detail { template <typename NodePointer> struct bucket { - typedef NodePointer previous_pointer; - previous_pointer next_; + typedef NodePointer link_pointer; + link_pointer next_; bucket() : next_() {} - previous_pointer first_from_start() + link_pointer first_from_start() { return next_; } @@ -552,12 +574,12 @@ namespace boost { namespace unordered { namespace detail { struct ptr_bucket { - typedef ptr_bucket* previous_pointer; - previous_pointer next_; + typedef ptr_bucket* link_pointer; + link_pointer next_; ptr_bucket() : next_(0) {} - previous_pointer first_from_start() + link_pointer first_from_start() { return this; } @@ -568,8 +590,6 @@ namespace boost { namespace unordered { namespace detail { /////////////////////////////////////////////////////////////////// // // Hash Policy - // - // Don't really want table to derive from this, but will for now. template <typename SizeT> struct prime_policy @@ -645,11 +665,51 @@ namespace boost { namespace unordered { namespace detail { typedef mix64_policy<std::size_t> type; }; + template <typename T> struct pick_policy : pick_policy_impl< std::numeric_limits<std::size_t>::digits, std::numeric_limits<std::size_t>::radix> {}; + // While the mix policy is generally faster, the prime policy is a lot + // faster when a large number consecutive integers are used, because + // there are no collisions. Since that is probably quite common, use + // prime policy for integeral types. But not the smaller ones, as they + // don't have enough unique values for this to be an issue. + + template <> + struct pick_policy<int> { + typedef prime_policy<std::size_t> type; + }; + + template <> + struct pick_policy<unsigned int> { + typedef prime_policy<std::size_t> type; + }; + + template <> + struct pick_policy<long> { + typedef prime_policy<std::size_t> type; + }; + + template <> + struct pick_policy<unsigned long> { + typedef prime_policy<std::size_t> type; + }; + + // TODO: Maybe not if std::size_t is smaller than long long. +#if !defined(BOOST_NO_LONG_LONG) + template <> + struct pick_policy<long long> { + typedef prime_policy<std::size_t> type; + }; + + template <> + struct pick_policy<unsigned long long> { + typedef prime_policy<std::size_t> type; + }; +#endif + //////////////////////////////////////////////////////////////////////////// // Functions @@ -664,12 +724,23 @@ namespace boost { namespace unordered { namespace detail { // atomically assigns the new function objects in a strongly // exception safe manner. - template <class H, class P> class set_hash_functions; + template <class H, class P, bool NoThrowMoveAssign> + class set_hash_functions; template <class H, class P> class functions { - friend class boost::unordered::detail::set_hash_functions<H, P>; + public: + static const bool nothrow_move_assignable = + boost::is_nothrow_move_assignable<H>::value && + boost::is_nothrow_move_assignable<P>::value; + static const bool nothrow_move_constructible = + boost::is_nothrow_move_constructible<H>::value && + boost::is_nothrow_move_constructible<P>::value; + + private: + friend class boost::unordered::detail::set_hash_functions<H, P, + nothrow_move_assignable>; functions& operator=(functions const&); typedef compressed<H, P> function_pair; @@ -686,23 +757,40 @@ namespace boost { namespace unordered { namespace detail { static_cast<void const*>(&funcs_[current_])); } + function_pair& current() { + return *static_cast<function_pair*>( + static_cast<void*>(&funcs_[current_])); + } + void construct(bool which, H const& hf, P const& eq) { new((void*) &funcs_[which]) function_pair(hf, eq); } - void construct(bool which, function_pair const& f) + void construct(bool which, function_pair const& f, + boost::unordered::detail::false_type = + boost::unordered::detail::false_type()) { new((void*) &funcs_[which]) function_pair(f); } + void construct(bool which, function_pair& f, + boost::unordered::detail::true_type) + { + new((void*) &funcs_[which]) function_pair(f, + boost::unordered::detail::move_tag()); + } + void destroy(bool which) { - boost::unordered::detail::destroy((function_pair*)(&funcs_[which])); + boost::unordered::detail::func::destroy((function_pair*)(&funcs_[which])); } public: + typedef boost::unordered::detail::set_hash_functions<H, P, + nothrow_move_assignable> set_hash_functions; + functions(H const& hf, P const& eq) : current_(false) { @@ -715,6 +803,14 @@ namespace boost { namespace unordered { namespace detail { construct(current_, bf.current()); } + functions(functions& bf, boost::unordered::detail::move_tag) + : current_(false) + { + construct(current_, bf.current(), + boost::unordered::detail::integral_constant<bool, + nothrow_move_constructible>()); + } + ~functions() { this->destroy(current_); } @@ -727,26 +823,28 @@ namespace boost { namespace unordered { namespace detail { return current().second(); } }; - + template <class H, class P> - class set_hash_functions + class set_hash_functions<H, P, false> { set_hash_functions(set_hash_functions const&); set_hash_functions& operator=(set_hash_functions const&); + + typedef functions<H, P> functions_type; - functions<H,P>& functions_; + functions_type& functions_; bool tmp_functions_; public: - set_hash_functions(functions<H,P>& f, H const& h, P const& p) + set_hash_functions(functions_type& f, H const& h, P const& p) : functions_(f), tmp_functions_(!f.current_) { f.construct(tmp_functions_, h, p); } - set_hash_functions(functions<H,P>& f, functions<H,P> const& other) + set_hash_functions(functions_type& f, functions_type const& other) : functions_(f), tmp_functions_(!f.current_) { @@ -765,11 +863,42 @@ namespace boost { namespace unordered { namespace detail { } }; + template <class H, class P> + class set_hash_functions<H, P, true> + { + set_hash_functions(set_hash_functions const&); + set_hash_functions& operator=(set_hash_functions const&); + + typedef functions<H, P> functions_type; + + functions_type& functions_; + H hash_; + P pred_; + + public: + + set_hash_functions(functions_type& f, H const& h, P const& p) : + functions_(f), + hash_(h), + pred_(p) {} + + set_hash_functions(functions_type& f, functions_type const& other) : + functions_(f), + hash_(other.hash_function()), + pred_(other.key_eq()) {} + + void commit() + { + functions_.current().first() = boost::move(hash_); + functions_.current().second() = boost::move(pred_); + } + }; + //////////////////////////////////////////////////////////////////////////// // rvalue parameters when type can't be a BOOST_RV_REF(T) parameter // e.g. for int -#if !defined(BOOST_NO_RVALUE_REFERENCES) +#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) # define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T) #else struct please_ignore_this_overload { |