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_ALL_HPP_INCLUDED
Chris@16: #define BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED
Chris@16: 
Chris@101: #include <boost/config.hpp>
Chris@101: #if defined(BOOST_HAS_PRAGMA_ONCE)
Chris@101: #pragma once
Chris@101: #endif
Chris@101: 
Chris@16: #include <boost/unordered/detail/buckets.hpp>
Chris@16: #include <boost/unordered/detail/util.hpp>
Chris@16: #include <boost/type_traits/aligned_storage.hpp>
Chris@16: #include <boost/type_traits/alignment_of.hpp>
Chris@16: #include <cmath>
Chris@16: 
Chris@16: #if defined(BOOST_MSVC)
Chris@16: #pragma warning(push)
Chris@16: #pragma warning(disable:4127) // conditional expression is constant
Chris@16: #endif
Chris@16: 
Chris@16: #if defined(BOOST_UNORDERED_DEPRECATED_EQUALITY)
Chris@16: 
Chris@16: #if defined(__EDG__)
Chris@16: #elif defined(_MSC_VER) || defined(__BORLANDC__) || defined(__DMC__)
Chris@16: #pragma message("Warning: BOOST_UNORDERED_DEPRECATED_EQUALITY is no longer supported.")
Chris@16: #elif defined(__GNUC__) || defined(__HP_aCC) || \
Chris@16:     defined(__SUNPRO_CC) || defined(__IBMCPP__)
Chris@16: #warning "BOOST_UNORDERED_DEPRECATED_EQUALITY is no longer supported."
Chris@16: #endif
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: namespace boost { namespace unordered { namespace detail {
Chris@16: 
Chris@16:     ////////////////////////////////////////////////////////////////////////////
Chris@16:     // convert double to std::size_t
Chris@16: 
Chris@16:     inline std::size_t double_to_size(double f)
Chris@16:     {
Chris@16:         return f >= static_cast<double>(
Chris@16:             (std::numeric_limits<std::size_t>::max)()) ?
Chris@16:             (std::numeric_limits<std::size_t>::max)() :
Chris@16:             static_cast<std::size_t>(f);
Chris@16:     }
Chris@16: 
Chris@16:     // The space used to store values in a node.
Chris@16: 
Chris@16:     template <typename ValueType>
Chris@16:     struct value_base
Chris@16:     {
Chris@16:         typedef ValueType value_type;
Chris@16: 
Chris@16:         typename boost::aligned_storage<
Chris@16:             sizeof(value_type),
Chris@16:             boost::alignment_of<value_type>::value>::type data_;
Chris@16: 
Chris@101:         value_base() :
Chris@101:             data_()
Chris@101:         {}
Chris@101: 
Chris@16:         void* address() {
Chris@16:             return this;
Chris@16:         }
Chris@16: 
Chris@16:         value_type& value() {
Chris@16:             return *(ValueType*) this;
Chris@16:         }
Chris@16: 
Chris@16:         value_type* value_ptr() {
Chris@16:             return (ValueType*) this;
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16: 
Chris@16:         value_base& operator=(value_base const&);
Chris@16:     };
Chris@16: 
Chris@16:     template <typename NodeAlloc>
Chris@16:     struct copy_nodes
Chris@16:     {
Chris@16:         typedef boost::unordered::detail::allocator_traits<NodeAlloc>
Chris@16:             node_allocator_traits;
Chris@16: 
Chris@16:         node_constructor<NodeAlloc> constructor;
Chris@16: 
Chris@16:         explicit copy_nodes(NodeAlloc& a) : constructor(a) {}
Chris@16: 
Chris@16:         typename node_allocator_traits::pointer create(
Chris@16:                 typename node_allocator_traits::value_type::value_type const& v)
Chris@16:         {
Chris@16:             constructor.construct_with_value2(v);
Chris@16:             return constructor.release();
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename NodeAlloc>
Chris@16:     struct move_nodes
Chris@16:     {
Chris@16:         typedef boost::unordered::detail::allocator_traits<NodeAlloc>
Chris@16:             node_allocator_traits;
Chris@16: 
Chris@16:         node_constructor<NodeAlloc> constructor;
Chris@16: 
Chris@16:         explicit move_nodes(NodeAlloc& a) : constructor(a) {}
Chris@16: 
Chris@16:         typename node_allocator_traits::pointer create(
Chris@16:                 typename node_allocator_traits::value_type::value_type& v)
Chris@16:         {
Chris@16:             constructor.construct_with_value2(boost::move(v));
Chris@16:             return constructor.release();
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Buckets>
Chris@16:     struct assign_nodes
Chris@16:     {
Chris@16:         node_holder<typename Buckets::node_allocator> holder;
Chris@16: 
Chris@16:         explicit assign_nodes(Buckets& b) : holder(b) {}
Chris@16: 
Chris@16:         typename Buckets::node_pointer create(
Chris@16:                 typename Buckets::value_type const& v)
Chris@16:         {
Chris@16:             return holder.copy_of(v);
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Buckets>
Chris@16:     struct move_assign_nodes
Chris@16:     {
Chris@16:         node_holder<typename Buckets::node_allocator> holder;
Chris@16: 
Chris@16:         explicit move_assign_nodes(Buckets& b) : holder(b) {}
Chris@16: 
Chris@16:         typename Buckets::node_pointer create(
Chris@16:                 typename Buckets::value_type& v)
Chris@16:         {
Chris@16:             return holder.move_copy_of(v);
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Types>
Chris@16:     struct table :
Chris@16:         boost::unordered::detail::functions<
Chris@16:             typename Types::hasher,
Chris@16:             typename Types::key_equal>
Chris@16:     {
Chris@16:     private:
Chris@16:         table(table const&);
Chris@16:         table& operator=(table const&);
Chris@16:     public:
Chris@16:         typedef typename Types::node node;
Chris@16:         typedef typename Types::bucket bucket;
Chris@16:         typedef typename Types::hasher hasher;
Chris@16:         typedef typename Types::key_equal key_equal;
Chris@16:         typedef typename Types::key_type key_type;
Chris@16:         typedef typename Types::extractor extractor;
Chris@16:         typedef typename Types::value_type value_type;
Chris@16:         typedef typename Types::table table_impl;
Chris@16:         typedef typename Types::link_pointer link_pointer;
Chris@16:         typedef typename Types::policy policy;
Chris@16: 
Chris@16:         typedef boost::unordered::detail::functions<
Chris@16:             typename Types::hasher,
Chris@16:             typename Types::key_equal> functions;
Chris@16:         typedef typename functions::set_hash_functions set_hash_functions;
Chris@16: 
Chris@16:         typedef typename Types::allocator allocator;
Chris@16:         typedef typename boost::unordered::detail::
Chris@16:             rebind_wrap<allocator, node>::type node_allocator;
Chris@16:         typedef typename boost::unordered::detail::
Chris@16:             rebind_wrap<allocator, bucket>::type bucket_allocator;
Chris@16:         typedef boost::unordered::detail::allocator_traits<node_allocator>
Chris@16:             node_allocator_traits;
Chris@16:         typedef boost::unordered::detail::allocator_traits<bucket_allocator>
Chris@16:             bucket_allocator_traits;
Chris@16:         typedef typename node_allocator_traits::pointer
Chris@16:             node_pointer;
Chris@16:         typedef typename node_allocator_traits::const_pointer
Chris@16:             const_node_pointer;
Chris@16:         typedef typename bucket_allocator_traits::pointer
Chris@16:             bucket_pointer;
Chris@16:         typedef boost::unordered::detail::node_constructor<node_allocator>
Chris@16:             node_constructor;
Chris@16: 
Chris@16:         typedef boost::unordered::iterator_detail::
Chris@16:             iterator<node> iterator;
Chris@16:         typedef boost::unordered::iterator_detail::
Chris@101:             c_iterator<node> c_iterator;
Chris@16:         typedef boost::unordered::iterator_detail::
Chris@16:             l_iterator<node, policy> l_iterator;
Chris@16:         typedef boost::unordered::iterator_detail::
Chris@101:             cl_iterator<node, policy> cl_iterator;
Chris@16: 
Chris@16:         ////////////////////////////////////////////////////////////////////////
Chris@16:         // Members
Chris@16: 
Chris@16:         boost::unordered::detail::compressed<bucket_allocator, node_allocator>
Chris@16:             allocators_;
Chris@16:         std::size_t bucket_count_;
Chris@16:         std::size_t size_;
Chris@16:         float mlf_;
Chris@16:         std::size_t max_load_;
Chris@16:         bucket_pointer buckets_;
Chris@16: 
Chris@16:         ////////////////////////////////////////////////////////////////////////
Chris@16:         // Data access
Chris@16: 
Chris@16:         bucket_allocator const& bucket_alloc() const
Chris@16:         {
Chris@16:             return allocators_.first();
Chris@16:         }
Chris@16: 
Chris@16:         node_allocator const& node_alloc() const
Chris@16:         {
Chris@16:             return allocators_.second();
Chris@16:         }
Chris@16: 
Chris@16:         bucket_allocator& bucket_alloc()
Chris@16:         {
Chris@16:             return allocators_.first();
Chris@16:         }
Chris@16: 
Chris@16:         node_allocator& node_alloc()
Chris@16:         {
Chris@16:             return allocators_.second();
Chris@16:         }
Chris@16: 
Chris@16:         std::size_t max_bucket_count() const
Chris@16:         {
Chris@16:             // -1 to account for the start bucket.
Chris@16:             return policy::prev_bucket_count(
Chris@16:                 bucket_allocator_traits::max_size(bucket_alloc()) - 1);
Chris@16:         }
Chris@16: 
Chris@16:         bucket_pointer get_bucket(std::size_t bucket_index) const
Chris@16:         {
Chris@16:             BOOST_ASSERT(buckets_);
Chris@16:             return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
Chris@16:         }
Chris@16: 
Chris@16:         link_pointer get_previous_start() const
Chris@16:         {
Chris@16:             return get_bucket(bucket_count_)->first_from_start();
Chris@16:         }
Chris@16: 
Chris@16:         link_pointer get_previous_start(std::size_t bucket_index) const
Chris@16:         {
Chris@16:             return get_bucket(bucket_index)->next_;
Chris@16:         }
Chris@16: 
Chris@16:         iterator begin() const
Chris@16:         {
Chris@16:             return size_ ? iterator(get_previous_start()->next_) : iterator();
Chris@16:         }
Chris@16: 
Chris@16:         iterator begin(std::size_t bucket_index) const
Chris@16:         {
Chris@16:             if (!size_) return iterator();
Chris@16:             link_pointer prev = get_previous_start(bucket_index);
Chris@16:             return prev ? iterator(prev->next_) : iterator();
Chris@16:         }
Chris@16:         
Chris@101:         std::size_t hash_to_bucket(std::size_t hash_value) const
Chris@16:         {
Chris@101:             return policy::to_bucket(bucket_count_, hash_value);
Chris@16:         }
Chris@16: 
Chris@16:         float load_factor() const
Chris@16:         {
Chris@16:             BOOST_ASSERT(bucket_count_ != 0);
Chris@16:             return static_cast<float>(size_)
Chris@16:                 / static_cast<float>(bucket_count_);
Chris@16:         }
Chris@16: 
Chris@16:         std::size_t bucket_size(std::size_t index) const
Chris@16:         {
Chris@16:             iterator it = begin(index);
Chris@16:             if (!it.node_) return 0;
Chris@16: 
Chris@16:             std::size_t count = 0;
Chris@16:             while(it.node_ && hash_to_bucket(it.node_->hash_) == index)
Chris@16:             {
Chris@16:                 ++count;
Chris@16:                 ++it;
Chris@16:             }
Chris@16: 
Chris@16:             return count;
Chris@16:         }
Chris@16: 
Chris@16:         ////////////////////////////////////////////////////////////////////////
Chris@16:         // Load methods
Chris@16: 
Chris@16:         std::size_t max_size() const
Chris@16:         {
Chris@16:             using namespace std;
Chris@16:     
Chris@16:             // size < mlf_ * count
Chris@16:             return boost::unordered::detail::double_to_size(ceil(
Chris@16:                     static_cast<double>(mlf_) *
Chris@16:                     static_cast<double>(max_bucket_count())
Chris@16:                 )) - 1;
Chris@16:         }
Chris@16: 
Chris@16:         void recalculate_max_load()
Chris@16:         {
Chris@16:             using namespace std;
Chris@16:     
Chris@16:             // From 6.3.1/13:
Chris@16:             // Only resize when size >= mlf_ * count
Chris@16:             max_load_ = buckets_ ? boost::unordered::detail::double_to_size(ceil(
Chris@16:                     static_cast<double>(mlf_) *
Chris@16:                     static_cast<double>(bucket_count_)
Chris@16:                 )) : 0;
Chris@16: 
Chris@16:         }
Chris@16: 
Chris@16:         void max_load_factor(float z)
Chris@16:         {
Chris@16:             BOOST_ASSERT(z > 0);
Chris@16:             mlf_ = (std::max)(z, minimum_max_load_factor);
Chris@16:             recalculate_max_load();
Chris@16:         }
Chris@16: 
Chris@16:         std::size_t min_buckets_for_size(std::size_t size) const
Chris@16:         {
Chris@16:             BOOST_ASSERT(mlf_ >= minimum_max_load_factor);
Chris@16:     
Chris@16:             using namespace std;
Chris@16:     
Chris@16:             // From 6.3.1/13:
Chris@16:             // size < mlf_ * count
Chris@16:             // => count > size / mlf_
Chris@16:             //
Chris@16:             // Or from rehash post-condition:
Chris@16:             // count > size / mlf_
Chris@16: 
Chris@16:             return policy::new_bucket_count(
Chris@16:                 boost::unordered::detail::double_to_size(floor(
Chris@16:                     static_cast<double>(size) /
Chris@101:                     static_cast<double>(mlf_)) + 1));
Chris@16:         }
Chris@16: 
Chris@16:         ////////////////////////////////////////////////////////////////////////
Chris@16:         // Constructors
Chris@16: 
Chris@16:         table(std::size_t num_buckets,
Chris@16:                 hasher const& hf,
Chris@16:                 key_equal const& eq,
Chris@16:                 node_allocator const& a) :
Chris@16:             functions(hf, eq),
Chris@16:             allocators_(a,a),
Chris@16:             bucket_count_(policy::new_bucket_count(num_buckets)),
Chris@16:             size_(0),
Chris@16:             mlf_(1.0f),
Chris@16:             max_load_(0),
Chris@16:             buckets_()
Chris@16:         {}
Chris@16: 
Chris@16:         table(table const& x, node_allocator const& a) :
Chris@16:             functions(x),
Chris@16:             allocators_(a,a),
Chris@16:             bucket_count_(x.min_buckets_for_size(x.size_)),
Chris@16:             size_(0),
Chris@16:             mlf_(x.mlf_),
Chris@16:             max_load_(0),
Chris@16:             buckets_()
Chris@16:         {}
Chris@16: 
Chris@16:         table(table& x, boost::unordered::detail::move_tag m) :
Chris@16:             functions(x, m),
Chris@16:             allocators_(x.allocators_, m),
Chris@16:             bucket_count_(x.bucket_count_),
Chris@16:             size_(x.size_),
Chris@16:             mlf_(x.mlf_),
Chris@16:             max_load_(x.max_load_),
Chris@16:             buckets_(x.buckets_)
Chris@16:         {
Chris@16:             x.buckets_ = bucket_pointer();
Chris@16:             x.size_ = 0;
Chris@16:             x.max_load_ = 0;
Chris@16:         }
Chris@16: 
Chris@16:         table(table& x, node_allocator const& a,
Chris@16:                 boost::unordered::detail::move_tag m) :
Chris@16:             functions(x, m),
Chris@16:             allocators_(a, a),
Chris@16:             bucket_count_(x.bucket_count_),
Chris@16:             size_(0),
Chris@16:             mlf_(x.mlf_),
Chris@16:             max_load_(x.max_load_),
Chris@16:             buckets_()
Chris@16:         {}
Chris@16: 
Chris@16:         ////////////////////////////////////////////////////////////////////////
Chris@16:         // Initialisation.
Chris@16: 
Chris@16:         void init(table const& x)
Chris@16:         {
Chris@16:             if (x.size_) {
Chris@16:                 create_buckets(bucket_count_);
Chris@101:                 copy_nodes<node_allocator> node_creator(node_alloc());
Chris@101:                 table_impl::fill_buckets(x.begin(), *this, node_creator);
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         void move_init(table& x)
Chris@16:         {
Chris@16:             if(node_alloc() == x.node_alloc()) {
Chris@16:                 move_buckets_from(x);
Chris@16:             }
Chris@16:             else if(x.size_) {
Chris@16:                 // TODO: Could pick new bucket size?
Chris@16:                 create_buckets(bucket_count_);
Chris@16: 
Chris@101:                 move_nodes<node_allocator> node_creator(node_alloc());
Chris@16:                 node_holder<node_allocator> nodes(x);
Chris@101:                 table_impl::fill_buckets(nodes.begin(), *this, node_creator);
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         ////////////////////////////////////////////////////////////////////////
Chris@16:         // Create buckets
Chris@16: 
Chris@16:         void create_buckets(std::size_t new_count)
Chris@16:         {
Chris@16:             boost::unordered::detail::array_constructor<bucket_allocator>
Chris@16:                 constructor(bucket_alloc());
Chris@16:     
Chris@16:             // Creates an extra bucket to act as the start node.
Chris@16:             constructor.construct(bucket(), new_count + 1);
Chris@16: 
Chris@16:             if (buckets_)
Chris@16:             {
Chris@16:                 // Copy the nodes to the new buckets, including the dummy
Chris@16:                 // node if there is one.
Chris@16:                 (constructor.get() +
Chris@16:                     static_cast<std::ptrdiff_t>(new_count))->next_ =
Chris@16:                         (buckets_ + static_cast<std::ptrdiff_t>(
Chris@16:                             bucket_count_))->next_;
Chris@16:                 destroy_buckets();
Chris@16:             }
Chris@16:             else if (bucket::extra_node)
Chris@16:             {
Chris@16:                 node_constructor a(node_alloc());
Chris@16:                 a.construct();
Chris@16: 
Chris@16:                 (constructor.get() +
Chris@16:                     static_cast<std::ptrdiff_t>(new_count))->next_ =
Chris@16:                         a.release();
Chris@16:             }
Chris@16: 
Chris@16:             bucket_count_ = new_count;
Chris@16:             buckets_ = constructor.release();
Chris@16:             recalculate_max_load();
Chris@16:         }
Chris@16: 
Chris@16:         ////////////////////////////////////////////////////////////////////////
Chris@16:         // Swap and Move
Chris@16: 
Chris@16:         void swap_allocators(table& other, false_type)
Chris@16:         {
Chris@16:             boost::unordered::detail::func::ignore_unused_variable_warning(other);
Chris@16: 
Chris@16:             // According to 23.2.1.8, if propagate_on_container_swap is
Chris@16:             // false the behaviour is undefined unless the allocators
Chris@16:             // are equal.
Chris@16:             BOOST_ASSERT(node_alloc() == other.node_alloc());
Chris@16:         }
Chris@16: 
Chris@16:         void swap_allocators(table& other, true_type)
Chris@16:         {
Chris@16:             allocators_.swap(other.allocators_);
Chris@16:         }
Chris@16: 
Chris@16:         // Only swaps the allocators if propagate_on_container_swap
Chris@16:         void swap(table& x)
Chris@16:         {
Chris@16:             set_hash_functions op1(*this, x);
Chris@16:             set_hash_functions op2(x, *this);
Chris@16: 
Chris@16:             // I think swap can throw if Propagate::value,
Chris@16:             // since the allocators' swap can throw. Not sure though.
Chris@16:             swap_allocators(x,
Chris@16:                 boost::unordered::detail::integral_constant<bool,
Chris@16:                     allocator_traits<node_allocator>::
Chris@16:                     propagate_on_container_swap::value>());
Chris@16: 
Chris@16:             boost::swap(buckets_, x.buckets_);
Chris@16:             boost::swap(bucket_count_, x.bucket_count_);
Chris@16:             boost::swap(size_, x.size_);
Chris@16:             std::swap(mlf_, x.mlf_);
Chris@16:             std::swap(max_load_, x.max_load_);
Chris@16:             op1.commit();
Chris@16:             op2.commit();
Chris@16:         }
Chris@16: 
Chris@101:         // Only call with nodes allocated with the currect allocator, or
Chris@101:         // one that is equal to it. (Can't assert because other's
Chris@101:         // allocators might have already been moved).
Chris@16:         void move_buckets_from(table& other)
Chris@16:         {
Chris@16:             BOOST_ASSERT(!buckets_);
Chris@16:             buckets_ = other.buckets_;
Chris@16:             bucket_count_ = other.bucket_count_;
Chris@16:             size_ = other.size_;
Chris@16:             other.buckets_ = bucket_pointer();
Chris@16:             other.size_ = 0;
Chris@16:             other.max_load_ = 0;
Chris@16:         }
Chris@16: 
Chris@16:         ////////////////////////////////////////////////////////////////////////
Chris@16:         // Delete/destruct
Chris@16: 
Chris@16:         ~table()
Chris@16:         {
Chris@16:             delete_buckets();
Chris@16:         }
Chris@16: 
Chris@16:         void delete_node(link_pointer prev)
Chris@16:         {
Chris@16:             node_pointer n = static_cast<node_pointer>(prev->next_);
Chris@16:             prev->next_ = n->next_;
Chris@16: 
Chris@16:             boost::unordered::detail::func::destroy_value_impl(node_alloc(),
Chris@16:                 n->value_ptr());
Chris@101:             boost::unordered::detail::func::destroy(boost::addressof(*n));
Chris@16:             node_allocator_traits::deallocate(node_alloc(), n, 1);
Chris@16:             --size_;
Chris@16:         }
Chris@16: 
Chris@16:         std::size_t delete_nodes(link_pointer prev, link_pointer end)
Chris@16:         {
Chris@16:             BOOST_ASSERT(prev->next_ != end);
Chris@16: 
Chris@16:             std::size_t count = 0;
Chris@16: 
Chris@16:             do {
Chris@16:                 delete_node(prev);
Chris@16:                 ++count;
Chris@16:             } while (prev->next_ != end);
Chris@16: 
Chris@16:             return count;
Chris@16:         }
Chris@16: 
Chris@16:         void delete_buckets()
Chris@16:         {
Chris@16:             if(buckets_) {
Chris@16:                 if (size_) delete_nodes(get_previous_start(), link_pointer());
Chris@16: 
Chris@16:                 if (bucket::extra_node) {
Chris@16:                     node_pointer n = static_cast<node_pointer>(
Chris@16:                             get_bucket(bucket_count_)->next_);
Chris@101:                     boost::unordered::detail::func::destroy(
Chris@16:                             boost::addressof(*n));
Chris@16:                     node_allocator_traits::deallocate(node_alloc(), n, 1);
Chris@16:                 }
Chris@16: 
Chris@16:                 destroy_buckets();
Chris@16:                 buckets_ = bucket_pointer();
Chris@16:                 max_load_ = 0;
Chris@16:             }
Chris@16: 
Chris@16:             BOOST_ASSERT(!size_);
Chris@16:         }
Chris@16: 
Chris@16:         void clear()
Chris@16:         {
Chris@16:             if (!size_) return;
Chris@16: 
Chris@16:             delete_nodes(get_previous_start(), link_pointer());
Chris@16:             clear_buckets();
Chris@16: 
Chris@16:             BOOST_ASSERT(!size_);
Chris@16:         }
Chris@16: 
Chris@16:         void clear_buckets()
Chris@16:         {
Chris@16:             bucket_pointer end = get_bucket(bucket_count_);
Chris@16:             for(bucket_pointer it = buckets_; it != end; ++it)
Chris@16:             {
Chris@16:                 it->next_ = node_pointer();
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         void destroy_buckets()
Chris@16:         {
Chris@16:             bucket_pointer end = get_bucket(bucket_count_ + 1);
Chris@16:             for(bucket_pointer it = buckets_; it != end; ++it)
Chris@16:             {
Chris@101:                 boost::unordered::detail::func::destroy(
Chris@16:                     boost::addressof(*it));
Chris@16:             }
Chris@16: 
Chris@16:             bucket_allocator_traits::deallocate(bucket_alloc(),
Chris@16:                 buckets_, bucket_count_ + 1);
Chris@16:         }
Chris@16: 
Chris@16:         ////////////////////////////////////////////////////////////////////////
Chris@16:         // Fix buckets after delete
Chris@16:         //
Chris@16: 
Chris@16:         std::size_t fix_bucket(std::size_t bucket_index, link_pointer prev)
Chris@16:         {
Chris@16:             link_pointer end = prev->next_;
Chris@16:             std::size_t bucket_index2 = bucket_index;
Chris@16: 
Chris@16:             if (end)
Chris@16:             {
Chris@16:                 bucket_index2 = hash_to_bucket(
Chris@16:                     static_cast<node_pointer>(end)->hash_);
Chris@16: 
Chris@16:                 // If begin and end are in the same bucket, then
Chris@16:                 // there's nothing to do.
Chris@16:                 if (bucket_index == bucket_index2) return bucket_index2;
Chris@16: 
Chris@16:                 // Update the bucket containing end.
Chris@16:                 get_bucket(bucket_index2)->next_ = prev;
Chris@16:             }
Chris@16: 
Chris@16:             // Check if this bucket is now empty.
Chris@16:             bucket_pointer this_bucket = get_bucket(bucket_index);
Chris@16:             if (this_bucket->next_ == prev)
Chris@16:                 this_bucket->next_ = link_pointer();
Chris@16: 
Chris@16:             return bucket_index2;
Chris@16:         }
Chris@16: 
Chris@16:         ////////////////////////////////////////////////////////////////////////
Chris@16:         // Assignment
Chris@16: 
Chris@16:         void assign(table const& x)
Chris@16:         {
Chris@16:             if (this != boost::addressof(x))
Chris@16:             {
Chris@16:                 assign(x,
Chris@16:                     boost::unordered::detail::integral_constant<bool,
Chris@16:                         allocator_traits<node_allocator>::
Chris@16:                         propagate_on_container_copy_assignment::value>());
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         void assign(table const& x, false_type)
Chris@16:         {
Chris@16:             // Strong exception safety.
Chris@16:             set_hash_functions new_func_this(*this, x);
Chris@16:             new_func_this.commit();
Chris@16:             mlf_ = x.mlf_;
Chris@16:             recalculate_max_load();
Chris@16: 
Chris@16:             if (!size_ && !x.size_) return;
Chris@16: 
Chris@16:             if (x.size_ >= max_load_) {
Chris@16:                 create_buckets(min_buckets_for_size(x.size_));
Chris@16:             }
Chris@16:             else {
Chris@16:                 clear_buckets();
Chris@16:             }
Chris@16: 
Chris@16:             // assign_nodes takes ownership of the container's elements,
Chris@16:             // assigning to them if possible, and deleting any that are
Chris@16:             // left over.
Chris@101:             assign_nodes<table> node_creator(*this);
Chris@101:             table_impl::fill_buckets(x.begin(), *this, node_creator);
Chris@16:         }
Chris@16: 
Chris@16:         void assign(table const& x, true_type)
Chris@16:         {
Chris@16:             if (node_alloc() == x.node_alloc()) {
Chris@16:                 allocators_.assign(x.allocators_);
Chris@16:                 assign(x, false_type());
Chris@16:             }
Chris@16:             else {
Chris@16:                 set_hash_functions new_func_this(*this, x);
Chris@16: 
Chris@16:                 // Delete everything with current allocators before assigning
Chris@16:                 // the new ones.
Chris@16:                 delete_buckets();
Chris@16:                 allocators_.assign(x.allocators_);
Chris@16: 
Chris@16:                 // Copy over other data, all no throw.
Chris@16:                 new_func_this.commit();
Chris@16:                 mlf_ = x.mlf_;
Chris@16:                 bucket_count_ = min_buckets_for_size(x.size_);
Chris@16:                 max_load_ = 0;
Chris@16: 
Chris@16:                 // Finally copy the elements.
Chris@16:                 if (x.size_) {
Chris@16:                     create_buckets(bucket_count_);
Chris@101:                     copy_nodes<node_allocator> node_creator(node_alloc());
Chris@101:                     table_impl::fill_buckets(x.begin(), *this, node_creator);
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         void move_assign(table& x)
Chris@16:         {
Chris@16:             if (this != boost::addressof(x))
Chris@16:             {
Chris@16:                 move_assign(x,
Chris@16:                     boost::unordered::detail::integral_constant<bool,
Chris@16:                         allocator_traits<node_allocator>::
Chris@16:                         propagate_on_container_move_assignment::value>());
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         void move_assign(table& x, true_type)
Chris@16:         {
Chris@16:             delete_buckets();
Chris@101:             set_hash_functions new_func_this(*this, x);
Chris@16:             allocators_.move_assign(x.allocators_);
Chris@101:             // No throw from here.
Chris@101:             mlf_ = x.mlf_;
Chris@101:             max_load_ = x.max_load_;
Chris@101:             move_buckets_from(x);
Chris@101:             new_func_this.commit();
Chris@16:         }
Chris@16: 
Chris@16:         void move_assign(table& x, false_type)
Chris@16:         {
Chris@16:             if (node_alloc() == x.node_alloc()) {
Chris@16:                 delete_buckets();
Chris@101:                 set_hash_functions new_func_this(*this, x);
Chris@101:                 // No throw from here.
Chris@101:                 mlf_ = x.mlf_;
Chris@101:                 max_load_ = x.max_load_;
Chris@101:                 move_buckets_from(x);
Chris@101:                 new_func_this.commit();
Chris@16:             }
Chris@16:             else {
Chris@16:                 set_hash_functions new_func_this(*this, x);
Chris@16:                 new_func_this.commit();
Chris@16:                 mlf_ = x.mlf_;
Chris@16:                 recalculate_max_load();
Chris@16: 
Chris@16:                 if (!size_ && !x.size_) return;
Chris@16: 
Chris@16:                 if (x.size_ >= max_load_) {
Chris@16:                     create_buckets(min_buckets_for_size(x.size_));
Chris@16:                 }
Chris@16:                 else {
Chris@16:                     clear_buckets();
Chris@16:                 }
Chris@16: 
Chris@16:                 // move_assign_nodes takes ownership of the container's
Chris@16:                 // elements, assigning to them if possible, and deleting
Chris@16:                 // any that are left over.
Chris@101:                 move_assign_nodes<table> node_creator(*this);
Chris@16:                 node_holder<node_allocator> nodes(x);
Chris@101:                 table_impl::fill_buckets(nodes.begin(), *this, node_creator);
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         // Accessors
Chris@16: 
Chris@16:         key_type const& get_key(value_type const& x) const
Chris@16:         {
Chris@16:             return extractor::extract(x);
Chris@16:         }
Chris@16: 
Chris@16:         std::size_t hash(key_type const& k) const
Chris@16:         {
Chris@16:             return policy::apply_hash(this->hash_function(), k);
Chris@16:         }
Chris@16: 
Chris@16:         // Find Node
Chris@16: 
Chris@16:         template <typename Key, typename Hash, typename Pred>
Chris@16:         iterator generic_find_node(
Chris@16:                 Key const& k,
Chris@16:                 Hash const& hf,
Chris@16:                 Pred const& eq) const
Chris@16:         {
Chris@16:             return static_cast<table_impl const*>(this)->
Chris@16:                 find_node_impl(policy::apply_hash(hf, k), k, eq);
Chris@16:         }
Chris@16: 
Chris@16:         iterator find_node(
Chris@16:                 std::size_t key_hash,
Chris@16:                 key_type const& k) const
Chris@16:         {
Chris@16:             return static_cast<table_impl const*>(this)->
Chris@16:                 find_node_impl(key_hash, k, this->key_eq());
Chris@16:         }
Chris@16: 
Chris@16:         iterator find_node(key_type const& k) const
Chris@16:         {
Chris@16:             return static_cast<table_impl const*>(this)->
Chris@16:                 find_node_impl(hash(k), k, this->key_eq());
Chris@16:         }
Chris@16: 
Chris@16:         iterator find_matching_node(iterator n) const
Chris@16:         {
Chris@16:             // TODO: Does this apply to C++11?
Chris@16:             //
Chris@16:             // For some stupid reason, I decided to support equality comparison
Chris@16:             // when different hash functions are used. So I can't use the hash
Chris@16:             // value from the node here.
Chris@16:     
Chris@16:             return find_node(get_key(*n));
Chris@16:         }
Chris@16: 
Chris@16:         // Reserve and rehash
Chris@16: 
Chris@16:         void reserve_for_insert(std::size_t);
Chris@16:         void rehash(std::size_t);
Chris@16:         void reserve(std::size_t);
Chris@16:     };
Chris@16: 
Chris@16:     ////////////////////////////////////////////////////////////////////////////
Chris@16:     // Reserve & Rehash
Chris@16: 
Chris@16:     // basic exception safety
Chris@16:     template <typename Types>
Chris@16:     inline void table<Types>::reserve_for_insert(std::size_t size)
Chris@16:     {
Chris@16:         if (!buckets_) {
Chris@16:             create_buckets((std::max)(bucket_count_,
Chris@16:                 min_buckets_for_size(size)));
Chris@16:         }
Chris@16:         // According to the standard this should be 'size >= max_load_',
Chris@16:         // but I think this is better, defect report filed.
Chris@16:         else if(size > max_load_) {
Chris@16:             std::size_t num_buckets
Chris@16:                 = min_buckets_for_size((std::max)(size,
Chris@16:                     size_ + (size_ >> 1)));
Chris@16: 
Chris@16:             if (num_buckets != bucket_count_)
Chris@16:                 static_cast<table_impl*>(this)->rehash_impl(num_buckets);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     // if hash function throws, basic exception safety
Chris@16:     // strong otherwise.
Chris@16: 
Chris@16:     template <typename Types>
Chris@16:     inline void table<Types>::rehash(std::size_t min_buckets)
Chris@16:     {
Chris@16:         using namespace std;
Chris@16: 
Chris@16:         if(!size_) {
Chris@16:             delete_buckets();
Chris@16:             bucket_count_ = policy::new_bucket_count(min_buckets);
Chris@16:         }
Chris@16:         else {
Chris@16:             min_buckets = policy::new_bucket_count((std::max)(min_buckets,
Chris@16:                 boost::unordered::detail::double_to_size(floor(
Chris@16:                     static_cast<double>(size_) /
Chris@16:                     static_cast<double>(mlf_))) + 1));
Chris@16: 
Chris@16:             if(min_buckets != bucket_count_)
Chris@16:                 static_cast<table_impl*>(this)->rehash_impl(min_buckets);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Types>
Chris@16:     inline void table<Types>::reserve(std::size_t num_elements)
Chris@16:     {
Chris@16:         rehash(static_cast<std::size_t>(
Chris@16:             std::ceil(static_cast<double>(num_elements) / mlf_)));
Chris@16:     }
Chris@16: }}}
Chris@16: 
Chris@16: #if defined(BOOST_MSVC)
Chris@16: #pragma warning(pop)
Chris@16: #endif
Chris@16: 
Chris@16: #endif