diff options
Diffstat (limited to '3rdParty/Boost/src/boost/unordered/detail/unique.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/unique.hpp | 139 |
1 files changed, 58 insertions, 81 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/unique.hpp b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp index 8805652..f76ca5a 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/unique.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp @@ -7,8 +7,9 @@ #ifndef BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED #define BOOST_UNORDERED_DETAIL_UNIQUE_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/table.hpp> @@ -27,7 +28,10 @@ namespace boost { namespace unordered { namespace detail { boost::unordered::detail::value_base<T> { typedef typename ::boost::unordered::detail::rebind_wrap< - A, unique_node<A, T> >::type::pointer link_pointer; + A, unique_node<A, T> >::type allocator; + typedef typename ::boost::unordered::detail:: + allocator_traits<allocator>::pointer node_pointer; + typedef node_pointer link_pointer; link_pointer next_; std::size_t hash_; @@ -37,7 +41,7 @@ namespace boost { namespace unordered { namespace detail { hash_(0) {} - void init(link_pointer) + void init(node_pointer) { } @@ -47,23 +51,29 @@ namespace boost { namespace unordered { namespace detail { template <typename T> struct ptr_node : - boost::unordered::detail::value_base<T>, boost::unordered::detail::ptr_bucket { + typedef T value_type; typedef boost::unordered::detail::ptr_bucket bucket_base; + typedef ptr_node<T>* node_pointer; typedef ptr_bucket* link_pointer; std::size_t hash_; + boost::unordered::detail::value_base<T> value_base_; ptr_node() : bucket_base(), hash_(0) {} - void init(link_pointer) + void init(node_pointer) { } + void* address() { return value_base_.address(); } + value_type& value() { return value_base_.value(); } + value_type* value_ptr() { return value_base_.value_ptr(); } + private: ptr_node& operator=(ptr_node const&); }; @@ -136,7 +146,7 @@ namespace boost { namespace unordered { namespace detail { typedef boost::unordered::detail::table_impl<types> table; typedef boost::unordered::detail::set_extractor<value_type> extractor; - typedef boost::unordered::detail::pick_policy::type policy; + typedef typename boost::unordered::detail::pick_policy<T>::type policy; }; template <typename A, typename K, typename M, typename H, typename P> @@ -161,7 +171,7 @@ namespace boost { namespace unordered { namespace detail { typedef boost::unordered::detail::map_extractor<key_type, value_type> extractor; - typedef boost::unordered::detail::pick_policy::type policy; + typedef typename boost::unordered::detail::pick_policy<K>::type policy; }; template <typename Types> @@ -176,7 +186,6 @@ namespace boost { namespace unordered { namespace detail { typedef typename table::node_allocator_traits node_allocator_traits; typedef typename table::bucket_pointer bucket_pointer; typedef typename table::link_pointer link_pointer; - typedef typename table::previous_pointer previous_pointer; typedef typename table::hasher hasher; typedef typename table::key_equal key_equal; typedef typename table::key_type key_type; @@ -231,8 +240,7 @@ namespace boost { namespace unordered { namespace detail { Key const& k, Pred const& eq) const { - std::size_t bucket_index = - policy::to_bucket(this->bucket_count_, key_hash); + std::size_t bucket_index = this->hash_to_bucket(key_hash); iterator n = this->begin(bucket_index); for (;;) @@ -247,8 +255,7 @@ namespace boost { namespace unordered { namespace detail { } else { - if (policy::to_bucket(this->bucket_count_, node_hash) - != bucket_index) + if (this->hash_to_bucket(node_hash) != bucket_index) return iterator(); } @@ -291,13 +298,8 @@ namespace boost { namespace unordered { namespace detail { { iterator n2 = other.find_matching_node(n1); -#if !defined(BOOST_UNORDERED_DEPRECATED_EQUALITY) if (!n2.node_ || *n1 != *n2) return false; -#else - if (!n2.node_ || !extractor::compare_mapped(*n1, *n2)) - return false; -#endif } return true; @@ -312,27 +314,26 @@ namespace boost { namespace unordered { namespace detail { node_pointer n = a.release(); n->hash_ = key_hash; - bucket_pointer b = this->get_bucket( - policy::to_bucket(this->bucket_count_, key_hash)); + bucket_pointer b = this->get_bucket(this->hash_to_bucket(key_hash)); if (!b->next_) { - previous_pointer start_node = this->get_previous_start(); + link_pointer start_node = this->get_previous_start(); if (start_node->next_) { - this->get_bucket(policy::to_bucket(this->bucket_count_, + this->get_bucket(this->hash_to_bucket( static_cast<node_pointer>(start_node->next_)->hash_) )->next_ = n; } b->next_ = start_node; n->next_ = start_node->next_; - start_node->next_ = static_cast<link_pointer>(n); + start_node->next_ = n; } else { n->next_ = b->next_->next_; - b->next_->next_ = static_cast<link_pointer>(n); + b->next_->next_ = n; } ++this->size_; @@ -341,8 +342,6 @@ namespace boost { namespace unordered { namespace detail { value_type& operator[](key_type const& k) { - typedef typename value_type::second_type mapped_type; - std::size_t key_hash = this->hash(k); iterator pos = this->find_node(key_hash, k); @@ -360,8 +359,8 @@ namespace boost { namespace unordered { namespace detail { return *add_node(a, key_hash); } -#if defined(BOOST_NO_RVALUE_REFERENCES) -# if defined(BOOST_NO_VARIADIC_TEMPLATES) +#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) +# if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) emplace_return emplace(boost::unordered::detail::emplace_args1< boost::unordered::detail::please_ignore_this_overload> const&) { @@ -381,7 +380,7 @@ namespace boost { namespace unordered { namespace detail { template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplace_return emplace(BOOST_UNORDERED_EMPLACE_ARGS) { -#if !defined(BOOST_NO_VARIADIC_TEMPLATES) +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) return emplace_impl( extractor::extract(BOOST_UNORDERED_EMPLACE_FORWARD), BOOST_UNORDERED_EMPLACE_FORWARD); @@ -392,7 +391,7 @@ namespace boost { namespace unordered { namespace detail { #endif } -#if defined(BOOST_NO_VARIADIC_TEMPLATES) +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <typename A0> emplace_return emplace( boost::unordered::detail::emplace_args1<A0> const& args) @@ -518,11 +517,8 @@ namespace boost { namespace unordered { namespace detail { if(!this->size_) return 0; std::size_t key_hash = this->hash(k); - std::size_t bucket_index = - policy::to_bucket(this->bucket_count_, key_hash); - bucket_pointer this_bucket = this->get_bucket(bucket_index); - - previous_pointer prev = this_bucket->next_; + std::size_t bucket_index = this->hash_to_bucket(key_hash); + link_pointer prev = this->get_previous_start(bucket_index); if (!prev) return 0; for (;;) @@ -530,21 +526,20 @@ namespace boost { namespace unordered { namespace detail { if (!prev->next_) return 0; std::size_t node_hash = static_cast<node_pointer>(prev->next_)->hash_; - if (policy::to_bucket(this->bucket_count_, node_hash) - != bucket_index) + if (this->hash_to_bucket(node_hash) != bucket_index) return 0; if (node_hash == key_hash && this->key_eq()(k, this->get_key( static_cast<node_pointer>(prev->next_)->value()))) break; - prev = static_cast<previous_pointer>(prev->next_); + prev = prev->next_; } - node_pointer pos = static_cast<node_pointer>(prev->next_); - node_pointer end = static_cast<node_pointer>(pos->next_); - prev->next_ = pos->next_; - this->fix_buckets(this_bucket, prev, end); - return this->delete_nodes(c_iterator(pos), c_iterator(end)); + link_pointer end = static_cast<node_pointer>(prev->next_)->next_; + + std::size_t deleted_count = this->delete_nodes(prev, end); + this->fix_bucket(bucket_index, prev); + return deleted_count; } iterator erase(c_iterator r) @@ -552,46 +547,30 @@ namespace boost { namespace unordered { namespace detail { BOOST_ASSERT(r.node_); iterator next(r.node_); ++next; - - bucket_pointer this_bucket = this->get_bucket( - policy::to_bucket(this->bucket_count_, r.node_->hash_)); - previous_pointer prev = unlink_node(*this_bucket, r.node_); - - this->fix_buckets(this_bucket, prev, next.node_); - - this->delete_node(r); - + erase_nodes(r.node_, next.node_); return next; } iterator erase_range(c_iterator r1, c_iterator r2) { if (r1 == r2) return iterator(r2.node_); - - std::size_t bucket_index = - policy::to_bucket(this->bucket_count_, r1.node_->hash_); - previous_pointer prev = unlink_nodes( - *this->get_bucket(bucket_index), r1.node_, r2.node_); - this->fix_buckets_range(bucket_index, prev, r1.node_, r2.node_); - this->delete_nodes(r1, r2); - + erase_nodes(r1.node_, r2.node_); return iterator(r2.node_); } - static previous_pointer unlink_node(bucket& b, node_pointer n) + void erase_nodes(node_pointer i, node_pointer j) { - return unlink_nodes(b, n, static_cast<node_pointer>(n->next_)); - } + std::size_t bucket_index = this->hash_to_bucket(i->hash_); - static previous_pointer unlink_nodes(bucket& b, - node_pointer begin, node_pointer end) - { - previous_pointer prev = b.next_; - link_pointer begin_void = static_cast<link_pointer>(begin); - while(prev->next_ != begin_void) - prev = static_cast<previous_pointer>(prev->next_); - prev->next_ = static_cast<link_pointer>(end); - return prev; + // Find the node before i. + link_pointer prev = this->get_previous_start(bucket_index); + while(prev->next_ != i) prev = prev->next_; + + // Delete the nodes. + do { + this->delete_node(prev); + bucket_index = this->fix_bucket(bucket_index, prev); + } while (prev->next_ != j); } //////////////////////////////////////////////////////////////////////// @@ -601,12 +580,12 @@ namespace boost { namespace unordered { namespace detail { static void fill_buckets(iterator n, table& dst, NodeCreator& creator) { - previous_pointer prev = dst.get_previous_start(); + link_pointer prev = dst.get_previous_start(); while (n.node_) { node_pointer node = creator.create(*n); node->hash_ = n.node_->hash_; - prev->next_ = static_cast<link_pointer>(node); + prev->next_ = node; ++dst.size_; ++n; @@ -620,28 +599,26 @@ namespace boost { namespace unordered { namespace detail { BOOST_ASSERT(this->buckets_); this->create_buckets(num_buckets); - previous_pointer prev = this->get_previous_start(); + link_pointer prev = this->get_previous_start(); while (prev->next_) prev = place_in_bucket(*this, prev); } // Iterate through the nodes placing them in the correct buckets. // pre: prev->next_ is not null. - static previous_pointer place_in_bucket(table& dst, - previous_pointer prev) + static link_pointer place_in_bucket(table& dst, link_pointer prev) { node_pointer n = static_cast<node_pointer>(prev->next_); - bucket_pointer b = dst.get_bucket( - table::to_bucket(dst.bucket_count_, n->hash_)); + bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(n->hash_)); if (!b->next_) { b->next_ = prev; - return static_cast<previous_pointer>(n); + return n; } else { prev->next_ = n->next_; n->next_ = b->next_->next_; - b->next_->next_ = static_cast<link_pointer>(n); + b->next_->next_ = n; return prev; } } |