Chris@16: 
Chris@16: // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
Chris@16: // Copyright (C) 2005-2011 Daniel James
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See accompanying
Chris@16: // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
Chris@16: #define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
Chris@16: 
Chris@101: #include <boost/config.hpp>
Chris@101: #if defined(BOOST_HAS_PRAGMA_ONCE)
Chris@101: #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/unordered/detail/util.hpp>
Chris@16: #include <boost/unordered/detail/allocate.hpp>
Chris@16: #include <boost/type_traits/aligned_storage.hpp>
Chris@16: #include <boost/type_traits/alignment_of.hpp>
Chris@16: #include <boost/type_traits/is_nothrow_move_constructible.hpp>
Chris@16: #include <boost/type_traits/is_nothrow_move_assignable.hpp>
Chris@16: #include <boost/swap.hpp>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/limits.hpp>
Chris@16: #include <boost/iterator.hpp>
Chris@16: 
Chris@16: namespace boost { namespace unordered { namespace detail {
Chris@16: 
Chris@16:     template <typename Types> struct table;
Chris@16:     template <typename NodePointer> struct bucket;
Chris@16:     struct ptr_bucket;
Chris@16:     template <typename Types> struct table_impl;
Chris@16:     template <typename Types> struct grouped_table_impl;
Chris@16: 
Chris@16: }}}
Chris@16: 
Chris@16: // The 'iterator_detail' namespace was a misguided attempt at avoiding ADL
Chris@16: // in the detail namespace. It didn't work because the template parameters
Chris@16: // were in detail. I'm not changing it at the moment to be safe. I might
Chris@16: // do in the future if I change the iterator types.
Chris@16: namespace boost { namespace unordered { namespace iterator_detail {
Chris@16: 
Chris@16:     ////////////////////////////////////////////////////////////////////////////
Chris@16:     // Iterators
Chris@16:     //
Chris@16:     // all no throw
Chris@16: 
Chris@16:     template <typename Node> struct iterator;
Chris@101:     template <typename Node> struct c_iterator;
Chris@16:     template <typename Node, typename Policy> struct l_iterator;
Chris@101:     template <typename Node, typename Policy>
Chris@16:         struct cl_iterator;
Chris@16: 
Chris@16:     // Local Iterators
Chris@16:     //
Chris@16:     // all no throw
Chris@16: 
Chris@16:     template <typename Node, typename Policy>
Chris@16:     struct l_iterator
Chris@16:         : public boost::iterator<
Chris@16:             std::forward_iterator_tag,
Chris@16:             typename Node::value_type,
Chris@16:             std::ptrdiff_t,
Chris@101:             typename Node::value_type*,
Chris@16:             typename Node::value_type&>
Chris@16:     {
Chris@16: #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
Chris@101:         template <typename Node2, typename Policy2>
Chris@16:         friend struct boost::unordered::iterator_detail::cl_iterator;
Chris@16:     private:
Chris@16: #endif
Chris@16:         typedef typename Node::node_pointer node_pointer;
Chris@101:         typedef boost::unordered::iterator_detail::iterator<Node> n_iterator;
Chris@16:         node_pointer ptr_;
Chris@16:         std::size_t bucket_;
Chris@16:         std::size_t bucket_count_;
Chris@16: 
Chris@16:     public:
Chris@16: 
Chris@16:         typedef typename Node::value_type value_type;
Chris@16: 
Chris@16:         l_iterator() BOOST_NOEXCEPT : ptr_() {}
Chris@16: 
Chris@101:         l_iterator(n_iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT
Chris@16:             : ptr_(x.node_), bucket_(b), bucket_count_(c) {}
Chris@16: 
Chris@16:         value_type& operator*() const {
Chris@16:             return ptr_->value();
Chris@16:         }
Chris@16: 
Chris@16:         value_type* operator->() const {
Chris@16:             return ptr_->value_ptr();
Chris@16:         }
Chris@16: 
Chris@16:         l_iterator& operator++() {
Chris@16:             ptr_ = static_cast<node_pointer>(ptr_->next_);
Chris@16:             if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_)
Chris@16:                     != bucket_)
Chris@16:                 ptr_ = node_pointer();
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         l_iterator operator++(int) {
Chris@16:             l_iterator tmp(*this);
Chris@16:             ++(*this);
Chris@16:             return tmp;
Chris@16:         }
Chris@16: 
Chris@16:         bool operator==(l_iterator x) const BOOST_NOEXCEPT {
Chris@16:             return ptr_ == x.ptr_;
Chris@16:         }
Chris@16: 
Chris@16:         bool operator!=(l_iterator x) const BOOST_NOEXCEPT {
Chris@16:             return ptr_ != x.ptr_;
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@101:     template <typename Node, typename Policy>
Chris@16:     struct cl_iterator
Chris@16:         : public boost::iterator<
Chris@16:             std::forward_iterator_tag,
Chris@16:             typename Node::value_type,
Chris@16:             std::ptrdiff_t,
Chris@101:             typename Node::value_type const*,
Chris@16:             typename Node::value_type const&>
Chris@16:     {
Chris@16:         friend struct boost::unordered::iterator_detail::l_iterator
Chris@16:             <Node, Policy>;
Chris@16:     private:
Chris@16: 
Chris@16:         typedef typename Node::node_pointer node_pointer;
Chris@101:         typedef boost::unordered::iterator_detail::iterator<Node> n_iterator;
Chris@16:         node_pointer ptr_;
Chris@16:         std::size_t bucket_;
Chris@16:         std::size_t bucket_count_;
Chris@16: 
Chris@16:     public:
Chris@16: 
Chris@16:         typedef typename Node::value_type value_type;
Chris@16: 
Chris@16:         cl_iterator() BOOST_NOEXCEPT : ptr_() {}
Chris@16: 
Chris@101:         cl_iterator(n_iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT :
Chris@16:             ptr_(x.node_), bucket_(b), bucket_count_(c) {}
Chris@16: 
Chris@16:         cl_iterator(boost::unordered::iterator_detail::l_iterator<
Chris@16:                 Node, Policy> const& x) BOOST_NOEXCEPT :
Chris@16:             ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_)
Chris@16:         {}
Chris@16: 
Chris@16:         value_type const& operator*() const {
Chris@16:             return ptr_->value();
Chris@16:         }
Chris@16: 
Chris@16:         value_type const* operator->() const {
Chris@16:             return ptr_->value_ptr();
Chris@16:         }
Chris@16: 
Chris@16:         cl_iterator& operator++() {
Chris@16:             ptr_ = static_cast<node_pointer>(ptr_->next_);
Chris@16:             if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_)
Chris@16:                     != bucket_)
Chris@16:                 ptr_ = node_pointer();
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         cl_iterator operator++(int) {
Chris@16:             cl_iterator tmp(*this);
Chris@16:             ++(*this);
Chris@16:             return tmp;
Chris@16:         }
Chris@16: 
Chris@16:         friend bool operator==(cl_iterator const& x, cl_iterator const& y)
Chris@16:             BOOST_NOEXCEPT
Chris@16:         {
Chris@16:             return x.ptr_ == y.ptr_;
Chris@16:         }
Chris@16: 
Chris@16:         friend bool operator!=(cl_iterator const& x, cl_iterator const& y)
Chris@16:             BOOST_NOEXCEPT
Chris@16:         {
Chris@16:             return x.ptr_ != y.ptr_;
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Node>
Chris@16:     struct iterator
Chris@16:         : public boost::iterator<
Chris@16:             std::forward_iterator_tag,
Chris@16:             typename Node::value_type,
Chris@16:             std::ptrdiff_t,
Chris@101:             typename Node::value_type*,
Chris@16:             typename Node::value_type&>
Chris@16:     {
Chris@16: #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
Chris@101:         template <typename>
Chris@16:         friend struct boost::unordered::iterator_detail::c_iterator;
Chris@16:         template <typename, typename>
Chris@16:         friend struct boost::unordered::iterator_detail::l_iterator;
Chris@101:         template <typename, typename>
Chris@16:         friend struct boost::unordered::iterator_detail::cl_iterator;
Chris@16:         template <typename>
Chris@16:         friend struct boost::unordered::detail::table;
Chris@16:         template <typename>
Chris@16:         friend struct boost::unordered::detail::table_impl;
Chris@16:         template <typename>
Chris@16:         friend struct boost::unordered::detail::grouped_table_impl;
Chris@16:     private:
Chris@16: #endif
Chris@16:         typedef typename Node::node_pointer node_pointer;
Chris@16:         node_pointer node_;
Chris@16: 
Chris@16:     public:
Chris@16: 
Chris@16:         typedef typename Node::value_type value_type;
Chris@16: 
Chris@16:         iterator() BOOST_NOEXCEPT : node_() {}
Chris@16: 
Chris@16:         explicit iterator(typename Node::link_pointer x) BOOST_NOEXCEPT :
Chris@16:             node_(static_cast<node_pointer>(x)) {}
Chris@16: 
Chris@16:         value_type& operator*() const {
Chris@16:             return node_->value();
Chris@16:         }
Chris@16: 
Chris@16:         value_type* operator->() const {
Chris@101:             return node_->value_ptr();
Chris@16:         }
Chris@16: 
Chris@16:         iterator& operator++() {
Chris@16:             node_ = static_cast<node_pointer>(node_->next_);
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         iterator operator++(int) {
Chris@16:             iterator tmp(node_);
Chris@16:             node_ = static_cast<node_pointer>(node_->next_);
Chris@16:             return tmp;
Chris@16:         }
Chris@16: 
Chris@16:         bool operator==(iterator const& x) const BOOST_NOEXCEPT {
Chris@16:             return node_ == x.node_;
Chris@16:         }
Chris@16: 
Chris@16:         bool operator!=(iterator const& x) const BOOST_NOEXCEPT {
Chris@16:             return node_ != x.node_;
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@101:     template <typename Node>
Chris@16:     struct c_iterator
Chris@16:         : public boost::iterator<
Chris@16:             std::forward_iterator_tag,
Chris@16:             typename Node::value_type,
Chris@16:             std::ptrdiff_t,
Chris@101:             typename Node::value_type const*,
Chris@16:             typename Node::value_type const&>
Chris@16:     {
Chris@16:         friend struct boost::unordered::iterator_detail::iterator<Node>;
Chris@16: 
Chris@16: #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
Chris@16:         template <typename>
Chris@16:         friend struct boost::unordered::detail::table;
Chris@16:         template <typename>
Chris@16:         friend struct boost::unordered::detail::table_impl;
Chris@16:         template <typename>
Chris@16:         friend struct boost::unordered::detail::grouped_table_impl;
Chris@16: 
Chris@16:     private:
Chris@16: #endif
Chris@16:         typedef typename Node::node_pointer node_pointer;
Chris@101:         typedef boost::unordered::iterator_detail::iterator<Node> n_iterator;
Chris@16:         node_pointer node_;
Chris@16: 
Chris@16:     public:
Chris@16: 
Chris@16:         typedef typename Node::value_type value_type;
Chris@16: 
Chris@16:         c_iterator() BOOST_NOEXCEPT : node_() {}
Chris@16: 
Chris@16:         explicit c_iterator(typename Node::link_pointer x) BOOST_NOEXCEPT :
Chris@16:             node_(static_cast<node_pointer>(x)) {}
Chris@16: 
Chris@101:         c_iterator(n_iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {}
Chris@16: 
Chris@16:         value_type const& operator*() const {
Chris@16:             return node_->value();
Chris@16:         }
Chris@16: 
Chris@16:         value_type const* operator->() const {
Chris@101:             return node_->value_ptr();
Chris@16:         }
Chris@16: 
Chris@16:         c_iterator& operator++() {
Chris@16:             node_ = static_cast<node_pointer>(node_->next_);
Chris@16:             return *this;
Chris@16:         }
Chris@16: 
Chris@16:         c_iterator operator++(int) {
Chris@16:             c_iterator tmp(node_);
Chris@16:             node_ = static_cast<node_pointer>(node_->next_);
Chris@16:             return tmp;
Chris@16:         }
Chris@16: 
Chris@16:         friend bool operator==(c_iterator const& x, c_iterator const& y)
Chris@16:             BOOST_NOEXCEPT
Chris@16:         {
Chris@16:             return x.node_ == y.node_;
Chris@16:         }
Chris@16: 
Chris@16:         friend bool operator!=(c_iterator const& x, c_iterator const& y)
Chris@16:             BOOST_NOEXCEPT
Chris@16:         {
Chris@16:             return x.node_ != y.node_;
Chris@16:         }
Chris@16:     };
Chris@16: }}}
Chris@16: 
Chris@16: namespace boost { namespace unordered { namespace detail {
Chris@16: 
Chris@16:     ///////////////////////////////////////////////////////////////////
Chris@16:     //
Chris@16:     // Node construction
Chris@16: 
Chris@16:     template <typename NodeAlloc>
Chris@16:     struct node_constructor
Chris@16:     {
Chris@16:     private:
Chris@16: 
Chris@16:         typedef NodeAlloc node_allocator;
Chris@16:         typedef boost::unordered::detail::allocator_traits<NodeAlloc>
Chris@16:             node_allocator_traits;
Chris@16:         typedef typename node_allocator_traits::value_type node;
Chris@16:         typedef typename node_allocator_traits::pointer node_pointer;
Chris@16:         typedef typename node::value_type value_type;
Chris@16: 
Chris@16:     protected:
Chris@16: 
Chris@16:         node_allocator& alloc_;
Chris@16:         node_pointer node_;
Chris@16:         bool node_constructed_;
Chris@16:         bool value_constructed_;
Chris@16: 
Chris@16:     public:
Chris@16: 
Chris@16:         node_constructor(node_allocator& n) :
Chris@16:             alloc_(n),
Chris@16:             node_(),
Chris@16:             node_constructed_(false),
Chris@16:             value_constructed_(false)
Chris@16:         {
Chris@16:         }
Chris@16: 
Chris@16:         ~node_constructor();
Chris@16: 
Chris@16:         void construct();
Chris@16: 
Chris@16:         template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
Chris@16:         void construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS)
Chris@16:         {
Chris@16:             construct();
Chris@16:             boost::unordered::detail::func::construct_value_impl(
Chris@16:                 alloc_, node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
Chris@16:             value_constructed_ = true;
Chris@16:         }
Chris@16: 
Chris@16:         template <typename A0>
Chris@16:         void construct_with_value2(BOOST_FWD_REF(A0) a0)
Chris@16:         {
Chris@16:             construct();
Chris@16:             boost::unordered::detail::func::construct_value_impl(
Chris@16:                 alloc_, node_->value_ptr(),
Chris@16:                 BOOST_UNORDERED_EMPLACE_ARGS1(boost::forward<A0>(a0)));
Chris@16:             value_constructed_ = true;
Chris@16:         }
Chris@16: 
Chris@16:         value_type const& value() const {
Chris@16:             BOOST_ASSERT(node_ && node_constructed_ && value_constructed_);
Chris@16:             return node_->value();
Chris@16:         }
Chris@16: 
Chris@16:         // no throw
Chris@16:         node_pointer release()
Chris@16:         {
Chris@16:             BOOST_ASSERT(node_ && node_constructed_);
Chris@16:             node_pointer p = node_;
Chris@16:             node_ = node_pointer();
Chris@16:             return p;
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         node_constructor(node_constructor const&);
Chris@16:         node_constructor& operator=(node_constructor const&);
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Alloc>
Chris@16:     node_constructor<Alloc>::~node_constructor()
Chris@16:     {
Chris@16:         if (node_) {
Chris@16:             if (value_constructed_) {
Chris@16:                 boost::unordered::detail::func::destroy_value_impl(alloc_,
Chris@16:                     node_->value_ptr());
Chris@16:             }
Chris@16: 
Chris@16:             if (node_constructed_) {
Chris@101:                 boost::unordered::detail::func::destroy(
Chris@16:                     boost::addressof(*node_));
Chris@16:             }
Chris@16: 
Chris@16:             node_allocator_traits::deallocate(alloc_, node_, 1);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Alloc>
Chris@16:     void node_constructor<Alloc>::construct()
Chris@16:     {
Chris@16:         if(!node_) {
Chris@16:             node_constructed_ = false;
Chris@16:             value_constructed_ = false;
Chris@16: 
Chris@16:             node_ = node_allocator_traits::allocate(alloc_, 1);
Chris@16: 
Chris@101:             new ((void*) boost::addressof(*node_)) node();
Chris@16:             node_->init(node_);
Chris@16:             node_constructed_ = true;
Chris@16:         }
Chris@16:         else {
Chris@16:             BOOST_ASSERT(node_constructed_);
Chris@16: 
Chris@16:             if (value_constructed_)
Chris@16:             {
Chris@16:                 boost::unordered::detail::func::destroy_value_impl(alloc_,
Chris@16:                     node_->value_ptr());
Chris@16:                 value_constructed_ = false;
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     ///////////////////////////////////////////////////////////////////
Chris@16:     //
Chris@16:     // Node Holder
Chris@16:     //
Chris@16:     // Temporary store for nodes. Deletes any that aren't used.
Chris@16: 
Chris@16:     template <typename NodeAlloc>
Chris@16:     struct node_holder : private node_constructor<NodeAlloc>
Chris@16:     {
Chris@16:     private:
Chris@16:         typedef node_constructor<NodeAlloc> base;
Chris@16: 
Chris@16:         typedef NodeAlloc node_allocator;
Chris@16:         typedef boost::unordered::detail::allocator_traits<NodeAlloc>
Chris@16:             node_allocator_traits;
Chris@16:         typedef typename node_allocator_traits::value_type node;
Chris@16:         typedef typename node_allocator_traits::pointer node_pointer;
Chris@16:         typedef typename node::value_type value_type;
Chris@16:         typedef typename node::link_pointer link_pointer;
Chris@16:         typedef boost::unordered::iterator_detail::iterator<node> iterator;
Chris@16: 
Chris@16:         node_pointer nodes_;
Chris@16: 
Chris@16:     public:
Chris@16: 
Chris@16:         template <typename Table>
Chris@16:         explicit node_holder(Table& b) :
Chris@16:             base(b.node_alloc()),
Chris@16:             nodes_()
Chris@16:         {
Chris@16:             if (b.size_) {
Chris@16:                 typename Table::link_pointer prev = b.get_previous_start();
Chris@16:                 nodes_ = static_cast<node_pointer>(prev->next_);
Chris@16:                 prev->next_ = link_pointer();
Chris@16:                 b.size_ = 0;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         ~node_holder();
Chris@16: 
Chris@16:         void node_for_assignment()
Chris@16:         {
Chris@16:             if (!this->node_ && nodes_) {
Chris@16:                 this->node_ = nodes_;
Chris@16:                 nodes_ = static_cast<node_pointer>(nodes_->next_);
Chris@16:                 this->node_->init(this->node_);
Chris@16:                 this->node_->next_ = link_pointer();
Chris@16: 
Chris@16:                 this->node_constructed_ = true;
Chris@16:                 this->value_constructed_ = true;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         template <typename T>
Chris@16:         inline void assign_impl(T const& v) {
Chris@16:             if (this->node_ && this->value_constructed_) {
Chris@16:                 this->node_->value() = v;
Chris@16:             }
Chris@16:             else {
Chris@16:                 this->construct_with_value2(v);
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         template <typename T1, typename T2>
Chris@16:         inline void assign_impl(std::pair<T1 const, T2> const& v) {
Chris@16:             this->construct_with_value2(v);
Chris@16:         }
Chris@16: 
Chris@16:         template <typename T>
Chris@16:         inline void move_assign_impl(T& v) {
Chris@16:             if (this->node_ && this->value_constructed_) {
Chris@16:                 this->node_->value() = boost::move(v);
Chris@16:             }
Chris@16:             else {
Chris@16:                 this->construct_with_value2(boost::move(v));
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         template <typename T1, typename T2>
Chris@16:         inline void move_assign_impl(std::pair<T1 const, T2>& v) {
Chris@16:             this->construct_with_value2(boost::move(v));
Chris@16:         }
Chris@16: 
Chris@16:         node_pointer copy_of(value_type const& v)
Chris@16:         {
Chris@16:             node_for_assignment();
Chris@16:             assign_impl(v);
Chris@16:             return base::release();
Chris@16:         }
Chris@16: 
Chris@16:         node_pointer move_copy_of(value_type& v)
Chris@16:         {
Chris@16:             node_for_assignment();
Chris@16:             move_assign_impl(v);
Chris@16:             return base::release();
Chris@16:         }
Chris@16: 
Chris@16:         iterator begin() const
Chris@16:         {
Chris@16:             return iterator(nodes_);
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Alloc>
Chris@16:     node_holder<Alloc>::~node_holder()
Chris@16:     {
Chris@16:         while (nodes_) {
Chris@16:             node_pointer p = nodes_;
Chris@16:             nodes_ = static_cast<node_pointer>(p->next_);
Chris@16: 
Chris@16:             boost::unordered::detail::func::destroy_value_impl(this->alloc_,
Chris@16:                 p->value_ptr());
Chris@101:             boost::unordered::detail::func::destroy(boost::addressof(*p));
Chris@16:             node_allocator_traits::deallocate(this->alloc_, p, 1);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     ///////////////////////////////////////////////////////////////////
Chris@16:     //
Chris@16:     // Bucket
Chris@16: 
Chris@16:     template <typename NodePointer>
Chris@16:     struct bucket
Chris@16:     {
Chris@16:         typedef NodePointer link_pointer;
Chris@16:         link_pointer next_;
Chris@16: 
Chris@16:         bucket() : next_() {}
Chris@16: 
Chris@16:         link_pointer first_from_start()
Chris@16:         {
Chris@16:             return next_;
Chris@16:         }
Chris@16: 
Chris@16:         enum { extra_node = true };
Chris@16:     };
Chris@16: 
Chris@16:     struct ptr_bucket
Chris@16:     {
Chris@16:         typedef ptr_bucket* link_pointer;
Chris@16:         link_pointer next_;
Chris@16: 
Chris@16:         ptr_bucket() : next_(0) {}
Chris@16: 
Chris@16:         link_pointer first_from_start()
Chris@16:         {
Chris@16:             return this;
Chris@16:         }
Chris@16: 
Chris@16:         enum { extra_node = false };
Chris@16:     };
Chris@16: 
Chris@16:     ///////////////////////////////////////////////////////////////////
Chris@16:     //
Chris@16:     // Hash Policy
Chris@16: 
Chris@16:     template <typename SizeT>
Chris@16:     struct prime_policy
Chris@16:     {
Chris@16:         template <typename Hash, typename T>
Chris@16:         static inline SizeT apply_hash(Hash const& hf, T const& x) {
Chris@16:             return hf(x);
Chris@16:         }
Chris@16: 
Chris@16:         static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
Chris@16:             return hash % bucket_count;
Chris@16:         }
Chris@16: 
Chris@16:         static inline SizeT new_bucket_count(SizeT min) {
Chris@16:             return boost::unordered::detail::next_prime(min);
Chris@16:         }
Chris@16: 
Chris@16:         static inline SizeT prev_bucket_count(SizeT max) {
Chris@16:             return boost::unordered::detail::prev_prime(max);
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename SizeT>
Chris@16:     struct mix64_policy
Chris@16:     {
Chris@16:         template <typename Hash, typename T>
Chris@16:         static inline SizeT apply_hash(Hash const& hf, T const& x) {
Chris@16:             SizeT key = hf(x);
Chris@16:             key = (~key) + (key << 21); // key = (key << 21) - key - 1;
Chris@16:             key = key ^ (key >> 24);
Chris@16:             key = (key + (key << 3)) + (key << 8); // key * 265
Chris@16:             key = key ^ (key >> 14);
Chris@16:             key = (key + (key << 2)) + (key << 4); // key * 21
Chris@16:             key = key ^ (key >> 28);
Chris@16:             key = key + (key << 31);
Chris@16:             return key;
Chris@16:         }
Chris@16: 
Chris@16:         static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
Chris@16:             return hash & (bucket_count - 1);
Chris@16:         }
Chris@16: 
Chris@16:         static inline SizeT new_bucket_count(SizeT min) {
Chris@16:             if (min <= 4) return 4;
Chris@16:             --min;
Chris@16:             min |= min >> 1;
Chris@16:             min |= min >> 2;
Chris@16:             min |= min >> 4;
Chris@16:             min |= min >> 8;
Chris@16:             min |= min >> 16;
Chris@16:             min |= min >> 32;
Chris@16:             return min + 1;
Chris@16:         }
Chris@16: 
Chris@16:         static inline SizeT prev_bucket_count(SizeT max) {
Chris@16:             max |= max >> 1;
Chris@16:             max |= max >> 2;
Chris@16:             max |= max >> 4;
Chris@16:             max |= max >> 8;
Chris@16:             max |= max >> 16;
Chris@16:             max |= max >> 32;
Chris@16:             return (max >> 1) + 1;
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <int digits, int radix>
Chris@16:     struct pick_policy_impl {
Chris@16:         typedef prime_policy<std::size_t> type;
Chris@16:     };
Chris@16: 
Chris@16:     template <>
Chris@16:     struct pick_policy_impl<64, 2> {
Chris@16:         typedef mix64_policy<std::size_t> type;
Chris@16:     };
Chris@16: 
Chris@101:     template <typename T>
Chris@16:     struct pick_policy :
Chris@16:         pick_policy_impl<
Chris@16:             std::numeric_limits<std::size_t>::digits,
Chris@16:             std::numeric_limits<std::size_t>::radix> {};
Chris@16: 
Chris@101:     // While the mix policy is generally faster, the prime policy is a lot
Chris@101:     // faster when a large number consecutive integers are used, because
Chris@101:     // there are no collisions. Since that is probably quite common, use
Chris@101:     // prime policy for integeral types. But not the smaller ones, as they
Chris@101:     // don't have enough unique values for this to be an issue.
Chris@101: 
Chris@101:     template <>
Chris@101:     struct pick_policy<int> {
Chris@101:         typedef prime_policy<std::size_t> type;
Chris@101:     };
Chris@101: 
Chris@101:     template <>
Chris@101:     struct pick_policy<unsigned int> {
Chris@101:         typedef prime_policy<std::size_t> type;
Chris@101:     };
Chris@101: 
Chris@101:     template <>
Chris@101:     struct pick_policy<long> {
Chris@101:         typedef prime_policy<std::size_t> type;
Chris@101:     };
Chris@101: 
Chris@101:     template <>
Chris@101:     struct pick_policy<unsigned long> {
Chris@101:         typedef prime_policy<std::size_t> type;
Chris@101:     };
Chris@101: 
Chris@101:     // TODO: Maybe not if std::size_t is smaller than long long.
Chris@101: #if !defined(BOOST_NO_LONG_LONG)
Chris@101:     template <>
Chris@101:     struct pick_policy<long long> {
Chris@101:         typedef prime_policy<std::size_t> type;
Chris@101:     };
Chris@101: 
Chris@101:     template <>
Chris@101:     struct pick_policy<unsigned long long> {
Chris@101:         typedef prime_policy<std::size_t> type;
Chris@101:     };
Chris@101: #endif
Chris@101: 
Chris@16:     ////////////////////////////////////////////////////////////////////////////
Chris@16:     // Functions
Chris@16: 
Chris@16:     // Assigning and swapping the equality and hash function objects
Chris@16:     // needs strong exception safety. To implement that normally we'd
Chris@16:     // require one of them to be known to not throw and the other to
Chris@16:     // guarantee strong exception safety. Unfortunately they both only
Chris@16:     // have basic exception safety. So to acheive strong exception
Chris@16:     // safety we have storage space for two copies, and assign the new
Chris@16:     // copies to the unused space. Then switch to using that to use
Chris@16:     // them. This is implemented in 'set_hash_functions' which
Chris@16:     // atomically assigns the new function objects in a strongly
Chris@16:     // exception safe manner.
Chris@16: 
Chris@16:     template <class H, class P, bool NoThrowMoveAssign>
Chris@16:     class set_hash_functions;
Chris@16: 
Chris@16:     template <class H, class P>
Chris@16:     class functions
Chris@16:     {
Chris@16:     public:
Chris@16:         static const bool nothrow_move_assignable =
Chris@16:                 boost::is_nothrow_move_assignable<H>::value &&
Chris@16:                 boost::is_nothrow_move_assignable<P>::value;
Chris@16:         static const bool nothrow_move_constructible =
Chris@16:                 boost::is_nothrow_move_constructible<H>::value &&
Chris@16:                 boost::is_nothrow_move_constructible<P>::value;
Chris@16: 
Chris@16:     private:
Chris@16:         friend class boost::unordered::detail::set_hash_functions<H, P,
Chris@16:                nothrow_move_assignable>;
Chris@16:         functions& operator=(functions const&);
Chris@16: 
Chris@16:         typedef compressed<H, P> function_pair;
Chris@16: 
Chris@16:         typedef typename boost::aligned_storage<
Chris@16:             sizeof(function_pair),
Chris@16:             boost::alignment_of<function_pair>::value>::type aligned_function;
Chris@16: 
Chris@16:         bool current_; // The currently active functions.
Chris@16:         aligned_function funcs_[2];
Chris@16: 
Chris@16:         function_pair const& current() const {
Chris@16:             return *static_cast<function_pair const*>(
Chris@16:                 static_cast<void const*>(&funcs_[current_]));
Chris@16:         }
Chris@16: 
Chris@16:         function_pair& current() {
Chris@16:             return *static_cast<function_pair*>(
Chris@16:                 static_cast<void*>(&funcs_[current_]));
Chris@16:         }
Chris@16: 
Chris@16:         void construct(bool which, H const& hf, P const& eq)
Chris@16:         {
Chris@16:             new((void*) &funcs_[which]) function_pair(hf, eq);
Chris@16:         }
Chris@16: 
Chris@16:         void construct(bool which, function_pair const& f,
Chris@16:                 boost::unordered::detail::false_type =
Chris@16:                     boost::unordered::detail::false_type())
Chris@16:         {
Chris@16:             new((void*) &funcs_[which]) function_pair(f);
Chris@16:         }
Chris@16:         
Chris@16:         void construct(bool which, function_pair& f,
Chris@16:                 boost::unordered::detail::true_type)
Chris@16:         {
Chris@16:             new((void*) &funcs_[which]) function_pair(f,
Chris@16:                 boost::unordered::detail::move_tag());
Chris@16:         }
Chris@16: 
Chris@16:         void destroy(bool which)
Chris@16:         {
Chris@16:             boost::unordered::detail::func::destroy((function_pair*)(&funcs_[which]));
Chris@16:         }
Chris@16:         
Chris@16:     public:
Chris@16: 
Chris@16:         typedef boost::unordered::detail::set_hash_functions<H, P,
Chris@16:                 nothrow_move_assignable> set_hash_functions;
Chris@16: 
Chris@16:         functions(H const& hf, P const& eq)
Chris@16:             : current_(false)
Chris@16:         {
Chris@16:             construct(current_, hf, eq);
Chris@16:         }
Chris@16: 
Chris@16:         functions(functions const& bf)
Chris@16:             : current_(false)
Chris@16:         {
Chris@16:             construct(current_, bf.current());
Chris@16:         }
Chris@16: 
Chris@16:         functions(functions& bf, boost::unordered::detail::move_tag)
Chris@16:             : current_(false)
Chris@16:         {
Chris@16:             construct(current_, bf.current(),
Chris@16:                 boost::unordered::detail::integral_constant<bool,
Chris@16:                     nothrow_move_constructible>());
Chris@16:         }
Chris@16: 
Chris@16:         ~functions() {
Chris@16:             this->destroy(current_);
Chris@16:         }
Chris@16: 
Chris@16:         H const& hash_function() const {
Chris@16:             return current().first();
Chris@16:         }
Chris@16: 
Chris@16:         P const& key_eq() const {
Chris@16:             return current().second();
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <class H, class P>
Chris@16:     class set_hash_functions<H, P, false>
Chris@16:     {
Chris@16:         set_hash_functions(set_hash_functions const&);
Chris@16:         set_hash_functions& operator=(set_hash_functions const&);
Chris@16: 
Chris@16:         typedef functions<H, P> functions_type;
Chris@16:     
Chris@16:         functions_type& functions_;
Chris@16:         bool tmp_functions_;
Chris@16: 
Chris@16:     public:
Chris@16: 
Chris@16:         set_hash_functions(functions_type& f, H const& h, P const& p)
Chris@16:           : functions_(f),
Chris@16:             tmp_functions_(!f.current_)
Chris@16:         {
Chris@16:             f.construct(tmp_functions_, h, p);
Chris@16:         }
Chris@16: 
Chris@16:         set_hash_functions(functions_type& f, functions_type const& other)
Chris@16:           : functions_(f),
Chris@16:             tmp_functions_(!f.current_)
Chris@16:         {
Chris@16:             f.construct(tmp_functions_, other.current());
Chris@16:         }
Chris@16: 
Chris@16:         ~set_hash_functions()
Chris@16:         {
Chris@16:             functions_.destroy(tmp_functions_);
Chris@16:         }
Chris@16: 
Chris@16:         void commit()
Chris@16:         {
Chris@16:             functions_.current_ = tmp_functions_;
Chris@16:             tmp_functions_ = !tmp_functions_;
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <class H, class P>
Chris@16:     class set_hash_functions<H, P, true>
Chris@16:     {
Chris@16:         set_hash_functions(set_hash_functions const&);
Chris@16:         set_hash_functions& operator=(set_hash_functions const&);
Chris@16: 
Chris@16:         typedef functions<H, P> functions_type;
Chris@16: 
Chris@16:         functions_type& functions_;
Chris@16:         H hash_;
Chris@16:         P pred_;
Chris@16:     
Chris@16:     public:
Chris@16: 
Chris@16:         set_hash_functions(functions_type& f, H const& h, P const& p) :
Chris@16:             functions_(f),
Chris@16:             hash_(h),
Chris@16:             pred_(p) {}
Chris@16: 
Chris@16:         set_hash_functions(functions_type& f, functions_type const& other) :
Chris@16:             functions_(f),
Chris@16:             hash_(other.hash_function()),
Chris@16:             pred_(other.key_eq()) {}
Chris@16: 
Chris@16:         void commit()
Chris@16:         {
Chris@16:             functions_.current().first() = boost::move(hash_);
Chris@16:             functions_.current().second() = boost::move(pred_);
Chris@16:         }
Chris@16:     };
Chris@16:     
Chris@16:     ////////////////////////////////////////////////////////////////////////////
Chris@16:     // rvalue parameters when type can't be a BOOST_RV_REF(T) parameter
Chris@16:     // e.g. for int
Chris@16: 
Chris@16: #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
Chris@16: #   define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T)
Chris@16: #else
Chris@16:     struct please_ignore_this_overload {
Chris@16:         typedef please_ignore_this_overload type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     struct rv_ref_impl {
Chris@16:         typedef BOOST_RV_REF(T) type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename T>
Chris@16:     struct rv_ref :
Chris@16:         boost::detail::if_true<
Chris@16:             boost::is_class<T>::value
Chris@16:         >::BOOST_NESTED_TEMPLATE then <
Chris@16:             boost::unordered::detail::rv_ref_impl<T>,
Chris@16:             please_ignore_this_overload
Chris@16:         >::type
Chris@16:     {};
Chris@16: 
Chris@16: #   define BOOST_UNORDERED_RV_REF(T) \
Chris@16:         typename boost::unordered::detail::rv_ref<T>::type
Chris@16: #endif
Chris@16: }}}
Chris@16: 
Chris@16: #endif