diff options
Diffstat (limited to 'src/third_party/boost-1.56.0/boost/unordered/detail/buckets.hpp')
-rw-r--r-- | src/third_party/boost-1.56.0/boost/unordered/detail/buckets.hpp | 928 |
1 files changed, 928 insertions, 0 deletions
diff --git a/src/third_party/boost-1.56.0/boost/unordered/detail/buckets.hpp b/src/third_party/boost-1.56.0/boost/unordered/detail/buckets.hpp new file mode 100644 index 00000000000..fd038b7b775 --- /dev/null +++ b/src/third_party/boost-1.56.0/boost/unordered/detail/buckets.hpp @@ -0,0 +1,928 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2011 Daniel James +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED + +#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> +#include <boost/iterator.hpp> + +namespace boost { namespace unordered { namespace detail { + + template <typename Types> struct table; + template <typename NodePointer> struct bucket; + struct ptr_bucket; + template <typename Types> struct table_impl; + template <typename Types> struct grouped_table_impl; + +}}} + +// 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 { + + //////////////////////////////////////////////////////////////////////////// + // Iterators + // + // all no throw + + 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 Node, typename Policy> + struct l_iterator + : public boost::iterator< + 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 Node2, typename ConstNodePointer, typename Policy2> + friend struct boost::unordered::iterator_detail::cl_iterator; + private: +#endif + 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: + + typedef typename Node::value_type value_type; + + 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_type& operator*() const { + return ptr_->value(); + } + + value_type* operator->() const { + return ptr_->value_ptr(); + } + + l_iterator& operator++() { + ptr_ = static_cast<node_pointer>(ptr_->next_); + if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_) + != bucket_) + ptr_ = node_pointer(); + return *this; + } + + l_iterator operator++(int) { + l_iterator tmp(*this); + ++(*this); + return tmp; + } + + bool operator==(l_iterator x) const BOOST_NOEXCEPT { + return ptr_ == x.ptr_; + } + + bool operator!=(l_iterator x) const BOOST_NOEXCEPT { + return ptr_ != x.ptr_; + } + }; + + template <typename Node, typename ConstNodePointer, typename Policy> + struct cl_iterator + : public boost::iterator< + 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 + <Node, Policy>; + private: + + 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: + + typedef typename Node::value_type value_type; + + cl_iterator() BOOST_NOEXCEPT : ptr_() {} + + 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< + Node, Policy> const& x) BOOST_NOEXCEPT : + ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_) + {} + + value_type const& operator*() const { + return ptr_->value(); + } + + value_type const* operator->() const { + return ptr_->value_ptr(); + } + + cl_iterator& operator++() { + ptr_ = static_cast<node_pointer>(ptr_->next_); + if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_) + != bucket_) + ptr_ = node_pointer(); + return *this; + } + + cl_iterator operator++(int) { + cl_iterator tmp(*this); + ++(*this); + return tmp; + } + + 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) + BOOST_NOEXCEPT + { + return x.ptr_ != y.ptr_; + } + }; + + template <typename Node> + struct iterator + : public boost::iterator< + 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> + friend struct boost::unordered::iterator_detail::c_iterator; + template <typename, typename> + friend struct boost::unordered::iterator_detail::l_iterator; + template <typename, typename, typename> + friend struct boost::unordered::iterator_detail::cl_iterator; + template <typename> + friend struct boost::unordered::detail::table; + template <typename> + friend struct boost::unordered::detail::table_impl; + template <typename> + friend struct boost::unordered::detail::grouped_table_impl; + private: +#endif + typedef typename Node::node_pointer node_pointer; + node_pointer node_; + + public: + + typedef typename Node::value_type value_type; + + iterator() BOOST_NOEXCEPT : node_() {} + + explicit iterator(typename Node::link_pointer x) BOOST_NOEXCEPT : + node_(static_cast<node_pointer>(x)) {} + + value_type& operator*() const { + return node_->value(); + } + + value_type* operator->() const { + return &node_->value(); + } + + iterator& operator++() { + node_ = static_cast<node_pointer>(node_->next_); + return *this; + } + + iterator operator++(int) { + iterator tmp(node_); + node_ = static_cast<node_pointer>(node_->next_); + return tmp; + } + + bool operator==(iterator const& x) const BOOST_NOEXCEPT { + return node_ == x.node_; + } + + bool operator!=(iterator const& x) const BOOST_NOEXCEPT { + return node_ != x.node_; + } + }; + + template <typename Node, typename ConstNodePointer> + struct c_iterator + : public boost::iterator< + std::forward_iterator_tag, + typename Node::value_type, + std::ptrdiff_t, + ConstNodePointer, + typename Node::value_type const&> + { + friend struct boost::unordered::iterator_detail::iterator<Node>; + +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template <typename> + friend struct boost::unordered::detail::table; + template <typename> + friend struct boost::unordered::detail::table_impl; + template <typename> + friend struct boost::unordered::detail::grouped_table_impl; + + private: +#endif + typedef typename Node::node_pointer node_pointer; + typedef boost::unordered::iterator_detail::iterator<Node> iterator; + node_pointer node_; + + public: + + typedef typename Node::value_type value_type; + + c_iterator() BOOST_NOEXCEPT : node_() {} + + explicit c_iterator(typename Node::link_pointer x) BOOST_NOEXCEPT : + node_(static_cast<node_pointer>(x)) {} + + c_iterator(iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {} + + value_type const& operator*() const { + return node_->value(); + } + + value_type const* operator->() const { + return &node_->value(); + } + + c_iterator& operator++() { + node_ = static_cast<node_pointer>(node_->next_); + return *this; + } + + c_iterator operator++(int) { + c_iterator tmp(node_); + node_ = static_cast<node_pointer>(node_->next_); + return tmp; + } + + 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) + BOOST_NOEXCEPT + { + return x.node_ != y.node_; + } + }; +}}} + +namespace boost { namespace unordered { namespace detail { + + /////////////////////////////////////////////////////////////////// + // + // Node construction + + template <typename NodeAlloc> + struct node_constructor + { + private: + + typedef NodeAlloc node_allocator; + typedef boost::unordered::detail::allocator_traits<NodeAlloc> + node_allocator_traits; + typedef typename node_allocator_traits::value_type node; + typedef typename node_allocator_traits::pointer node_pointer; + typedef typename node::value_type value_type; + + protected: + + node_allocator& alloc_; + node_pointer node_; + bool node_constructed_; + bool value_constructed_; + + public: + + node_constructor(node_allocator& n) : + alloc_(n), + node_(), + node_constructed_(false), + value_constructed_(false) + { + } + + ~node_constructor(); + + void construct(); + + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + void construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS) + { + construct(); + boost::unordered::detail::func::construct_value_impl( + alloc_, node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); + value_constructed_ = true; + } + + template <typename A0> + void construct_with_value2(BOOST_FWD_REF(A0) a0) + { + construct(); + boost::unordered::detail::func::construct_value_impl( + alloc_, node_->value_ptr(), + BOOST_UNORDERED_EMPLACE_ARGS1(boost::forward<A0>(a0))); + value_constructed_ = true; + } + + value_type const& value() const { + BOOST_ASSERT(node_ && node_constructed_ && value_constructed_); + return node_->value(); + } + + // no throw + node_pointer release() + { + BOOST_ASSERT(node_ && node_constructed_); + node_pointer p = node_; + node_ = node_pointer(); + return p; + } + + private: + node_constructor(node_constructor const&); + node_constructor& operator=(node_constructor const&); + }; + + template <typename Alloc> + node_constructor<Alloc>::~node_constructor() + { + if (node_) { + if (value_constructed_) { + boost::unordered::detail::func::destroy_value_impl(alloc_, + node_->value_ptr()); + } + + if (node_constructed_) { + boost::unordered::detail::func::destroy( + boost::addressof(*node_)); + } + + node_allocator_traits::deallocate(alloc_, node_, 1); + } + } + + template <typename Alloc> + void node_constructor<Alloc>::construct() + { + if(!node_) { + node_constructed_ = false; + value_constructed_ = false; + + node_ = node_allocator_traits::allocate(alloc_, 1); + + new ((void*) boost::addressof(*node_)) node(); + node_->init(node_); + node_constructed_ = true; + } + else { + BOOST_ASSERT(node_constructed_); + + if (value_constructed_) + { + boost::unordered::detail::func::destroy_value_impl(alloc_, + node_->value_ptr()); + value_constructed_ = false; + } + } + } + + /////////////////////////////////////////////////////////////////// + // + // Node Holder + // + // Temporary store for nodes. Deletes any that aren't used. + + template <typename NodeAlloc> + struct node_holder : private node_constructor<NodeAlloc> + { + private: + typedef node_constructor<NodeAlloc> base; + + typedef NodeAlloc node_allocator; + typedef boost::unordered::detail::allocator_traits<NodeAlloc> + node_allocator_traits; + typedef typename node_allocator_traits::value_type node; + 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> iterator; + + node_pointer nodes_; + + public: + + template <typename Table> + explicit node_holder(Table& b) : + base(b.node_alloc()), + nodes_() + { + if (b.size_) { + typename Table::link_pointer prev = b.get_previous_start(); + nodes_ = static_cast<node_pointer>(prev->next_); + prev->next_ = link_pointer(); + b.size_ = 0; + } + } + + ~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) { + 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) { + this->construct_with_value2(v); + } + + template <typename T> + inline void move_assign_impl(T& 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) { + this->construct_with_value2(boost::move(v)); + } + + node_pointer copy_of(value_type const& v) + { + node_for_assignment(); + assign_impl(v); + return base::release(); + } + + node_pointer move_copy_of(value_type& v) + { + node_for_assignment(); + move_assign_impl(v); + return base::release(); + } + + iterator begin() const + { + return iterator(nodes_); + } + }; + + template <typename Alloc> + node_holder<Alloc>::~node_holder() + { + while (nodes_) { + node_pointer p = nodes_; + nodes_ = static_cast<node_pointer>(p->next_); + + boost::unordered::detail::func::destroy_value_impl(this->alloc_, + p->value_ptr()); + boost::unordered::detail::func::destroy(boost::addressof(*p)); + node_allocator_traits::deallocate(this->alloc_, p, 1); + } + } + + /////////////////////////////////////////////////////////////////// + // + // Bucket + + template <typename NodePointer> + struct bucket + { + typedef NodePointer link_pointer; + link_pointer next_; + + bucket() : next_() {} + + link_pointer first_from_start() + { + return next_; + } + + enum { extra_node = true }; + }; + + struct ptr_bucket + { + typedef ptr_bucket* link_pointer; + link_pointer next_; + + ptr_bucket() : next_(0) {} + + link_pointer first_from_start() + { + return this; + } + + enum { extra_node = false }; + }; + + /////////////////////////////////////////////////////////////////// + // + // Hash Policy + + template <typename SizeT> + struct prime_policy + { + template <typename Hash, typename T> + static inline SizeT apply_hash(Hash const& hf, T const& x) { + return hf(x); + } + + static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) { + return hash % bucket_count; + } + + static inline SizeT new_bucket_count(SizeT min) { + return boost::unordered::detail::next_prime(min); + } + + static inline SizeT prev_bucket_count(SizeT max) { + return boost::unordered::detail::prev_prime(max); + } + }; + + template <typename SizeT> + struct mix64_policy + { + template <typename Hash, typename T> + static inline SizeT apply_hash(Hash const& hf, T const& x) { + SizeT key = hf(x); + key = (~key) + (key << 21); // key = (key << 21) - key - 1; + key = key ^ (key >> 24); + key = (key + (key << 3)) + (key << 8); // key * 265 + key = key ^ (key >> 14); + key = (key + (key << 2)) + (key << 4); // key * 21 + key = key ^ (key >> 28); + key = key + (key << 31); + return key; + } + + static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) { + return hash & (bucket_count - 1); + } + + static inline SizeT new_bucket_count(SizeT min) { + if (min <= 4) return 4; + --min; + min |= min >> 1; + min |= min >> 2; + min |= min >> 4; + min |= min >> 8; + min |= min >> 16; + min |= min >> 32; + return min + 1; + } + + static inline SizeT prev_bucket_count(SizeT max) { + max |= max >> 1; + max |= max >> 2; + max |= max >> 4; + max |= max >> 8; + max |= max >> 16; + max |= max >> 32; + return (max >> 1) + 1; + } + }; + + template <int digits, int radix> + struct pick_policy_impl { + typedef prime_policy<std::size_t> type; + }; + + template <> + struct pick_policy_impl<64, 2> { + 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 + + // Assigning and swapping the equality and hash function objects + // needs strong exception safety. To implement that normally we'd + // require one of them to be known to not throw and the other to + // guarantee strong exception safety. Unfortunately they both only + // have basic exception safety. So to acheive strong exception + // safety we have storage space for two copies, and assign the new + // copies to the unused space. Then switch to using that to use + // them. This is implemented in 'set_hash_functions' which + // atomically assigns the new function objects in a strongly + // exception safe manner. + + template <class H, class P, bool NoThrowMoveAssign> + class set_hash_functions; + + template <class H, class P> + class functions + { + 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; + + typedef typename boost::aligned_storage< + sizeof(function_pair), + boost::alignment_of<function_pair>::value>::type aligned_function; + + bool current_; // The currently active functions. + aligned_function funcs_[2]; + + function_pair const& current() const { + return *static_cast<function_pair const*>( + 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, + 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::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) + { + construct(current_, hf, eq); + } + + functions(functions const& bf) + : current_(false) + { + 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_); + } + + H const& hash_function() const { + return current().first(); + } + + P const& key_eq() const { + return current().second(); + } + }; + + template <class H, class P> + 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_type& functions_; + bool tmp_functions_; + + public: + + 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_type& f, functions_type const& other) + : functions_(f), + tmp_functions_(!f.current_) + { + f.construct(tmp_functions_, other.current()); + } + + ~set_hash_functions() + { + functions_.destroy(tmp_functions_); + } + + void commit() + { + functions_.current_ = tmp_functions_; + tmp_functions_ = !tmp_functions_; + } + }; + + 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_CXX11_RVALUE_REFERENCES) +# define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T) +#else + struct please_ignore_this_overload { + typedef please_ignore_this_overload type; + }; + + template <typename T> + struct rv_ref_impl { + typedef BOOST_RV_REF(T) type; + }; + + template <typename T> + struct rv_ref : + boost::detail::if_true< + boost::is_class<T>::value + >::BOOST_NESTED_TEMPLATE then < + boost::unordered::detail::rv_ref_impl<T>, + please_ignore_this_overload + >::type + {}; + +# define BOOST_UNORDERED_RV_REF(T) \ + typename boost::unordered::detail::rv_ref<T>::type +#endif +}}} + +#endif |