[Boost-commit] svn:boost r80558 - in branches/release: . boost boost/unordered boost/unordered/detail libs libs/unordered libs/unordered/test/objects libs/unordered/test/unordered

Subject: [Boost-commit] svn:boost r80558 - in branches/release: . boost boost/unordered boost/unordered/detail libs libs/unordered libs/unordered/test/objects libs/unordered/test/unordered
From: dnljms_at_[hidden]
Date: 2012-09-17 14:53:32

Author: danieljames
Date: 2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
New Revision: 80558
URL: http://svn.boost.org/trac/boost/changeset/80558

Log:
Unordered: Merge from trunk.

Faster assign, plus simplified some of the implementation.

Properties modified: 
   branches/release/   (props changed)
   branches/release/boost/   (props changed)
   branches/release/boost/unordered/   (props changed)
   branches/release/libs/   (props changed)
   branches/release/libs/unordered/   (props changed)
Text files modified: 
   branches/release/boost/unordered/detail/buckets.hpp             |   808 +++++++++++++-------------------------- 
   branches/release/boost/unordered/detail/equivalent.hpp          |   138 +-----                                  
   branches/release/boost/unordered/detail/table.hpp               |   756 +++++++++++++++++++++++++++++-------    
   branches/release/boost/unordered/detail/unique.hpp              |   125 +----                                   
   branches/release/boost/unordered/unordered_map.hpp              |     2                                         
   branches/release/boost/unordered/unordered_set.hpp              |     2                                         
   branches/release/libs/unordered/test/objects/test.hpp           |   140 ++++++                                  
   branches/release/libs/unordered/test/unordered/insert_tests.cpp |    18                                         
   8 files changed, 1084 insertions(+), 905 deletions(-)

Modified: branches/release/boost/unordered/detail/buckets.hpp
==============================================================================
--- branches/release/boost/unordered/detail/buckets.hpp	(original)
+++ branches/release/boost/unordered/detail/buckets.hpp	2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -20,171 +20,14 @@
 #include <boost/limits.hpp>
 #include <boost/iterator.hpp>
 
-#if defined(BOOST_MSVC)
-#pragma warning(push)
-#pragma warning(disable:4127) // conditional expression is constant
-#endif
-
 namespace boost { namespace unordered { namespace detail {
 
     template <typename Types> struct table;
     template <typename NodePointer> struct bucket;
     struct ptr_bucket;
-    template <typename A, typename Bucket, typename Node, typename Policy>
-    struct buckets;
     template <typename Types> struct table_impl;
     template <typename Types> struct grouped_table_impl;
 
-    ///////////////////////////////////////////////////////////////////
-    //
-    // 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;
-
-        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_node();
-
-        template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
-        void construct_value(BOOST_UNORDERED_EMPLACE_ARGS)
-        {
-            BOOST_ASSERT(node_ && node_constructed_ && !value_constructed_);
-            boost::unordered::detail::construct_value_impl(
-                alloc_, node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
-            value_constructed_ = true;
-        }
-
-        template <typename A0>
-        void construct_value2(BOOST_FWD_REF(A0) a0)
-        {
-            BOOST_ASSERT(node_ && node_constructed_ && !value_constructed_);
-            boost::unordered::detail::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()
-        {
-            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::destroy_value_impl(alloc_,
-                    node_->value_ptr());
-            }
-
-            if (node_constructed_) {
-                node_allocator_traits::destroy(alloc_,
-                    boost::addressof(*node_));
-            }
-
-            node_allocator_traits::deallocate(alloc_, node_, 1);
-        }
-    }
-
-    template <typename Alloc>
-    void node_constructor<Alloc>::construct_node()
-    {
-        if(!node_) {
-            node_constructed_ = false;
-            value_constructed_ = false;
-
-            node_ = node_allocator_traits::allocate(alloc_, 1);
-
-            node_allocator_traits::construct(alloc_,
-                boost::addressof(*node_), node());
-            node_->init(static_cast<typename node::link_pointer>(node_));
-            node_constructed_ = true;
-        }
-        else {
-            BOOST_ASSERT(node_constructed_);
-
-            if (value_constructed_)
-            {
-                boost::unordered::detail::destroy_value_impl(alloc_,
-                    node_->value_ptr());
-                value_constructed_ = false;
-            }
-        }
-    }
-
-    ///////////////////////////////////////////////////////////////////
-    //
-    // Bucket
-
-    template <typename NodePointer>
-    struct bucket
-    {
-        typedef NodePointer previous_pointer;
-        previous_pointer next_;
-
-        bucket() : next_() {}
-
-        previous_pointer first_from_start()
-        {
-            return next_;
-        }
-
-        enum { extra_node = true };
-    };
-
-    struct ptr_bucket
-    {
-        typedef ptr_bucket* previous_pointer;
-        previous_pointer next_;
-
-        ptr_bucket() : next_(0) {}
-
-        previous_pointer first_from_start()
-        {
-            return this;
-        }
-
-        enum { extra_node = false };
-    };
 }}}
 
 namespace boost { namespace unordered { namespace iterator_detail {
@@ -340,8 +183,6 @@
         friend struct boost::unordered::iterator_detail::cl_iterator;
         template <typename>
         friend struct boost::unordered::detail::table;
-        template <typename, typename, typename, typename>
-        friend struct boost::unordered::detail::buckets;
         template <typename>
         friend struct boost::unordered::detail::table_impl;
         template <typename>
@@ -397,8 +238,6 @@
 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
         template <typename>
         friend struct boost::unordered::detail::table;
-        template <typename, typename, typename, typename>
-        friend struct boost::unordered::detail::buckets;
         template <typename>
         friend struct boost::unordered::detail::table_impl;
         template <typename>
@@ -454,472 +293,361 @@
 
     ///////////////////////////////////////////////////////////////////
     //
-    // Hash Policy
-    //
-    // Don't really want buckets to derive from this, but will for now.
+    // Node construction
 
-    template <typename SizeT>
-    struct prime_policy
+    template <typename NodeAlloc>
+    struct node_constructor
     {
-        template <typename Hash, typename T>
-        static inline SizeT apply_hash(Hash const& hf, T const& x) {
-            return hf(x);
+    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_;
+
+    private:
+
+        node_pointer node_;
+        bool node_constructed_;
+        bool value_constructed_;
+
+    public:
+
+        node_constructor(node_allocator& n) :
+            alloc_(n),
+            node_(),
+            node_constructed_(false),
+            value_constructed_(false)
+        {
         }
 
-        static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
-            return hash % bucket_count;
+        ~node_constructor();
+
+        void construct();
+
+        template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
+        void construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS)
+        {
+            construct();
+            boost::unordered::detail::construct_value_impl(
+                alloc_, node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
+            value_constructed_ = true;
         }
 
-        static inline SizeT new_bucket_count(SizeT min) {
-            return boost::unordered::detail::next_prime(min);
+        template <typename A0>
+        void construct_with_value2(BOOST_FWD_REF(A0) a0)
+        {
+            construct();
+            boost::unordered::detail::construct_value_impl(
+                alloc_, node_->value_ptr(),
+                BOOST_UNORDERED_EMPLACE_ARGS1(boost::forward<A0>(a0)));
+            value_constructed_ = true;
         }
 
-        static inline SizeT prev_bucket_count(SizeT max) {
-            return boost::unordered::detail::prev_prime(max);
+        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 SizeT>
-    struct mix64_policy
+    template <typename Alloc>
+    node_constructor<Alloc>::~node_constructor()
     {
-        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;
-        }
+        if (node_) {
+            if (value_constructed_) {
+                boost::unordered::detail::destroy_value_impl(alloc_,
+                    node_->value_ptr());
+            }
 
-        static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
-            return hash & (bucket_count - 1);
-        }
+            if (node_constructed_) {
+                node_allocator_traits::destroy(alloc_,
+                    boost::addressof(*node_));
+            }
 
-        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;
+            node_allocator_traits::deallocate(alloc_, node_, 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 <typename Alloc>
+    void node_constructor<Alloc>::construct()
+    {
+        if(!node_) {
+            node_constructed_ = false;
+            value_constructed_ = false;
 
-    template <int digits, int radix>
-    struct pick_policy_impl {
-        typedef prime_policy<std::size_t> type;
-    };
+            node_ = node_allocator_traits::allocate(alloc_, 1);
 
-    template <>
-    struct pick_policy_impl<64, 2> {
-        typedef mix64_policy<std::size_t> type;
-    };
+            node_allocator_traits::construct(alloc_,
+                boost::addressof(*node_), node());
+            node_->init(static_cast<typename node::link_pointer>(node_));
+            node_constructed_ = true;
+        }
+        else {
+            BOOST_ASSERT(node_constructed_);
 
-    struct pick_policy :
-        pick_policy_impl<
-            std::numeric_limits<std::size_t>::digits,
-            std::numeric_limits<std::size_t>::radix> {};
+            if (value_constructed_)
+            {
+                boost::unordered::detail::destroy_value_impl(alloc_,
+                    node_->value_ptr());
+                value_constructed_ = false;
+            }
+        }
+    }
 
     ///////////////////////////////////////////////////////////////////
     //
-    // Buckets
+    // Node Holder
+    //
+    // Temporary store for nodes. Deletes any that aren't used.
 
-    template <typename A, typename Bucket, typename Node, typename Policy>
-    struct buckets : Policy
+    template <typename NodeAlloc>
+    struct node_holder : private node_constructor<NodeAlloc>
     {
     private:
-        buckets(buckets const&);
-        buckets& operator=(buckets const&);
-    public:
-        typedef boost::unordered::detail::allocator_traits<A> traits;
-        typedef typename traits::value_type value_type;
+        typedef node_constructor<NodeAlloc> base;
 
-        typedef Policy policy;
-        typedef Node node;
-        typedef Bucket bucket;
-        typedef typename boost::unordered::detail::rebind_wrap<A, node>::type
-            node_allocator;
-        typedef typename boost::unordered::detail::rebind_wrap<A, bucket>::type
-            bucket_allocator;
-        typedef boost::unordered::detail::allocator_traits<node_allocator>
+        typedef NodeAlloc node_allocator;
+        typedef boost::unordered::detail::allocator_traits<NodeAlloc>
             node_allocator_traits;
-        typedef boost::unordered::detail::allocator_traits<bucket_allocator>
-            bucket_allocator_traits;
-        typedef typename node_allocator_traits::pointer
-            node_pointer;
-        typedef typename node_allocator_traits::const_pointer
-            const_node_pointer;
-        typedef typename bucket_allocator_traits::pointer
-            bucket_pointer;
-        typedef typename bucket::previous_pointer
-            previous_pointer;
-        typedef boost::unordered::detail::node_constructor<node_allocator>
-            node_constructor;
-
+        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_pointer, value_type> iterator;
-        typedef boost::unordered::iterator_detail::
-            c_iterator<const_node_pointer, node_pointer, value_type> c_iterator;
-        typedef boost::unordered::iterator_detail::
-            l_iterator<node_pointer, value_type, policy> l_iterator;
-        typedef boost::unordered::iterator_detail::
-            cl_iterator<const_node_pointer, node_pointer, value_type, policy>
-            cl_iterator;
-
-        // Members
 
-        bucket_pointer buckets_;
-        std::size_t bucket_count_;
-        std::size_t size_;
-        boost::unordered::detail::compressed<bucket_allocator, node_allocator>
-            allocators_;
+        node_pointer nodes_;
 
-        // Data access
+    public:
 
-        bucket_allocator const& bucket_alloc() const
+        template <typename Table>
+        explicit node_holder(Table& b) :
+            base(b.node_alloc()),
+            nodes_()
         {
-            return allocators_.first();
+            typename Table::previous_pointer prev = b.get_previous_start();
+            nodes_ = static_cast<node_pointer>(prev->next_);
+            prev->next_ = link_pointer();
+            b.size_ = 0;
         }
 
-        node_allocator const& node_alloc() const
-        {
-            return allocators_.second();
-        }
+        ~node_holder();
 
-        bucket_allocator& bucket_alloc()
-        {
-            return allocators_.first();
+        template <typename T>
+        inline void assign_impl(T const& v) {
+            nodes_->value() = v;
         }
 
-        node_allocator& node_alloc()
-        {
-            return allocators_.second();
+        template <typename T1, typename T2>
+        inline void assign_impl(std::pair<T1 const, T2> const& v) {
+            const_cast<T1&>(nodes_->value().first) = v.first;
+            nodes_->value().second = v.second;
         }
 
-        std::size_t max_bucket_count() const
-        {
-            // -1 to account for the start bucket.
-            return policy::prev_bucket_count(
-                bucket_allocator_traits::max_size(bucket_alloc()) - 1);
+        template <typename T>
+        inline void move_assign_impl(T& v) {
+            nodes_->value() = boost::move(v);
         }
 
-        bucket_pointer get_bucket(std::size_t bucket_index) const
-        {
-            return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
+        template <typename T1, typename T2>
+        inline void move_assign_impl(std::pair<T1 const, T2>& v) {
+            // TODO: Move key as well?
+            const_cast<T1&>(nodes_->value().first) =
+                boost::move(const_cast<T1&>(v.first));
+            nodes_->value().second = boost::move(v.second);
         }
 
-        previous_pointer get_previous_start() const
+        node_pointer copy_of(value_type const& v)
         {
-            return this->get_bucket(this->bucket_count_)->first_from_start();
+            if (nodes_) {
+                assign_impl(v);
+                node_pointer p = nodes_;
+                nodes_ = static_cast<node_pointer>(p->next_);
+                p->init(static_cast<typename node::link_pointer>(p));
+                p->next_ = link_pointer();
+                return p;
+            }
+            else {
+                this->construct_with_value2(v);
+                return base::release();
+            }
         }
 
-        previous_pointer get_previous_start(std::size_t bucket_index) const
+        node_pointer move_copy_of(value_type& v)
         {
-            return this->get_bucket(bucket_index)->next_;
+            if (nodes_) {
+                move_assign_impl(v);
+                node_pointer p = nodes_;
+                nodes_ = static_cast<node_pointer>(p->next_);
+                p->init(static_cast<typename node::link_pointer>(p));
+                p->next_ = link_pointer();
+                return p;
+            }
+            else {
+                this->construct_with_value2(boost::move(v));
+                return base::release();
+            }
         }
 
         iterator get_start() const
         {
-            return iterator(static_cast<node_pointer>(
-                        this->get_previous_start()->next_));
-        }
-
-        iterator get_start(std::size_t bucket_index) const
-        {
-            previous_pointer prev = this->get_previous_start(bucket_index);
-            return prev ? iterator(static_cast<node_pointer>(prev->next_)) :
-                iterator();
+            return iterator(nodes_);
         }
+    };
 
-        float load_factor() const
-        {
-            BOOST_ASSERT(this->bucket_count_ != 0);
-            return static_cast<float>(this->size_)
-                / static_cast<float>(this->bucket_count_);
+    template <typename Alloc>
+    node_holder<Alloc>::~node_holder()
+    {
+        while (nodes_) {
+            node_pointer p = nodes_;
+            nodes_ = static_cast<node_pointer>(p->next_);
+
+            boost::unordered::detail::destroy_value_impl(this->alloc_,
+                p->value_ptr());
+            node_allocator_traits::destroy(this->alloc_, boost::addressof(*p));
+            node_allocator_traits::deallocate(this->alloc_, p, 1);
         }
+    }
 
-        std::size_t bucket_size(std::size_t index) const
-        {
-            if (!this->size_) return 0;
-            iterator it = this->get_start(index);
-            if (!it.node_) return 0;
-
-            std::size_t count = 0;
-            while(it.node_ && policy::to_bucket(
-                        this->bucket_count_, it.node_->hash_) == index)
-            {
-                ++count;
-                ++it;
-            }
+    ///////////////////////////////////////////////////////////////////
+    //
+    // Bucket
 
-            return count;
-        }
+    template <typename NodePointer>
+    struct bucket
+    {
+        typedef NodePointer previous_pointer;
+        previous_pointer next_;
 
-        ////////////////////////////////////////////////////////////////////////
-        // Constructors
+        bucket() : next_() {}
 
-        buckets(node_allocator const& a, std::size_t bucket_count) :
-            buckets_(),
-            bucket_count_(bucket_count),
-            size_(),
-            allocators_(a,a)
+        previous_pointer first_from_start()
         {
+            return next_;
         }
 
-        buckets(buckets& b, boost::unordered::detail::move_tag m) :
-            buckets_(),
-            bucket_count_(b.bucket_count_),
-            size_(),
-            allocators_(b.allocators_, m)
-        {
-            swap(b);
-        }
+        enum { extra_node = true };
+    };
 
-        template <typename Types>
-        buckets(boost::unordered::detail::table<Types>& x,
-                boost::unordered::detail::move_tag m) :
-            buckets_(),
-            bucket_count_(x.bucket_count_),
-            size_(),
-            allocators_(x.allocators_, m)
-        {
-            swap(x);
-        }
+    struct ptr_bucket
+    {
+        typedef ptr_bucket* previous_pointer;
+        previous_pointer next_;
 
-        ////////////////////////////////////////////////////////////////////////
-        // Create buckets
-        // (never called in constructor to avoid exception issues)
+        ptr_bucket() : next_(0) {}
 
-        void create_buckets()
+        previous_pointer first_from_start()
         {
-            boost::unordered::detail::array_constructor<bucket_allocator>
-                constructor(bucket_alloc());
-    
-            // Creates an extra bucket to act as the start node.
-            constructor.construct(bucket(), this->bucket_count_ + 1);
-    
-            if (bucket::extra_node)
-            {
-                node_constructor a(this->node_alloc());
-                a.construct_node();
-
-                (constructor.get() +
-                    static_cast<std::ptrdiff_t>(this->bucket_count_))->next_ =
-                        a.release();
-            }
-
-            this->buckets_ = constructor.release();
+            return this;
         }
 
-        ////////////////////////////////////////////////////////////////////////
-        // Swap and Move
+        enum { extra_node = false };
+    };
 
-        void swap(buckets& other, false_type = false_type())
-        {
-            BOOST_ASSERT(node_alloc() == other.node_alloc());
-            boost::swap(buckets_, other.buckets_);
-            boost::swap(bucket_count_, other.bucket_count_);
-            boost::swap(size_, other.size_);
-        }
+    ///////////////////////////////////////////////////////////////////
+    //
+    // Hash Policy
+    //
+    // Don't really want table to derive from this, but will for now.
 
-        void swap(buckets& other, true_type)
-        {
-            allocators_.swap(other.allocators_);
-            boost::swap(buckets_, other.buckets_);
-            boost::swap(bucket_count_, other.bucket_count_);
-            boost::swap(size_, other.size_);
+    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);
         }
 
-        void move_buckets_from(buckets& other)
-        {
-            BOOST_ASSERT(node_alloc() == other.node_alloc());
-            BOOST_ASSERT(!this->buckets_);
-            this->buckets_ = other.buckets_;
-            this->bucket_count_ = other.bucket_count_;
-            this->size_ = other.size_;
-            other.buckets_ = bucket_pointer();
-            other.bucket_count_ = 0;
-            other.size_ = 0;
+        static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
+            return hash % bucket_count;
         }
 
-        ////////////////////////////////////////////////////////////////////////
-        // Delete/destruct
-
-        inline void delete_node(c_iterator n)
-        {
-            boost::unordered::detail::destroy_value_impl(node_alloc(),
-                n.node_->value_ptr());
-            node_allocator_traits::destroy(node_alloc(),
-                    boost::addressof(*n.node_));
-            node_allocator_traits::deallocate(node_alloc(), n.node_, 1);
-            --size_;
+        static inline SizeT new_bucket_count(SizeT min) {
+            return boost::unordered::detail::next_prime(min);
         }
 
-        std::size_t delete_nodes(c_iterator begin, c_iterator end)
-        {
-            std::size_t count = 0;
-
-            while(begin != end) {
-                c_iterator n = begin;
-                ++begin;
-                delete_node(n);
-                ++count;
-            }
-
-            return count;
+        static inline SizeT prev_bucket_count(SizeT max) {
+            return boost::unordered::detail::prev_prime(max);
         }
+    };
 
-        inline void delete_extra_node(bucket_pointer) {}
-
-        inline void delete_extra_node(node_pointer n) {
-            node_allocator_traits::destroy(node_alloc(), boost::addressof(*n));
-            node_allocator_traits::deallocate(node_alloc(), n, 1);
+    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;
         }
 
-        inline ~buckets()
-        {
-            this->delete_buckets();
+        static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
+            return hash & (bucket_count - 1);
         }
 
-        void delete_buckets()
-        {
-            if(this->buckets_) {
-                previous_pointer prev = this->get_previous_start();
-
-                while(prev->next_) {
-                    node_pointer n = static_cast<node_pointer>(prev->next_);
-                    prev->next_ = n->next_;
-                    delete_node(iterator(n));
-                }
-
-                delete_extra_node(prev);
-
-                bucket_pointer end = this->get_bucket(this->bucket_count_ + 1);
-                for(bucket_pointer it = this->buckets_; it != end; ++it)
-                {
-                    bucket_allocator_traits::destroy(bucket_alloc(),
-                        boost::addressof(*it));
-                }
-
-                bucket_allocator_traits::deallocate(bucket_alloc(),
-                    this->buckets_, this->bucket_count_ + 1);
-    
-                this->buckets_ = bucket_pointer();
-            }
-
-            BOOST_ASSERT(!this->size_);
+        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;
         }
 
-        void clear()
-        {
-            if(!this->size_) return;
-
-            previous_pointer prev = this->get_previous_start();
-
-            while(prev->next_) {
-                node_pointer n = static_cast<node_pointer>(prev->next_);
-                prev->next_ = n->next_;
-                delete_node(iterator(n));
-            }
-
-            bucket_pointer end = this->get_bucket(this->bucket_count_);
-            for(bucket_pointer it = this->buckets_; it != end; ++it)
-            {
-                it->next_ = node_pointer();
-            }
-
-            BOOST_ASSERT(!this->size_);
+        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;
         }
+    };
 
-        // This is called after erasing a node or group of nodes to fix up
-        // the bucket pointers.
-        void fix_buckets(bucket_pointer this_bucket,
-                previous_pointer prev, node_pointer next)
-        {
-            if (!next)
-            {
-                if (this_bucket->next_ == prev)
-                    this_bucket->next_ = node_pointer();
-            }
-            else
-            {
-                bucket_pointer next_bucket = this->get_bucket(
-                    policy::to_bucket(this->bucket_count_, next->hash_));
-
-                if (next_bucket != this_bucket)
-                {
-                    next_bucket->next_ = prev;
-                    if (this_bucket->next_ == prev)
-                        this_bucket->next_ = node_pointer();
-                }
-            }
-        }
+    template <int digits, int radix>
+    struct pick_policy_impl {
+        typedef prime_policy<std::size_t> type;
+    };
 
-        // This is called after erasing a range of nodes to fix any bucket
-        // pointers into that range.
-        void fix_buckets_range(std::size_t bucket_index,
-                previous_pointer prev, node_pointer begin, node_pointer end)
-        {
-            node_pointer n = begin;
-    
-            // If we're not at the start of the current bucket, then
-            // go to the start of the next bucket.
-            if (this->get_bucket(bucket_index)->next_ != prev)
-            {
-                for(;;) {
-                    n = static_cast<node_pointer>(n->next_);
-                    if (n == end) return;
-    
-                    std::size_t new_bucket_index =
-                        policy::to_bucket(this->bucket_count_, n->hash_);
-                    if (bucket_index != new_bucket_index) {
-                        bucket_index = new_bucket_index;
-                        break;
-                    }
-                }
-            }
-    
-            // Iterate through the remaining nodes, clearing out the bucket
-            // pointers.
-            this->get_bucket(bucket_index)->next_ = previous_pointer();
-            for(;;) {
-                n = static_cast<node_pointer>(n->next_);
-                if (n == end) break;
-    
-                std::size_t new_bucket_index =
-                    policy::to_bucket(this->bucket_count_, n->hash_);
-                if (bucket_index != new_bucket_index) {
-                    bucket_index = new_bucket_index;
-                    this->get_bucket(bucket_index)->next_ = previous_pointer();
-                }
-            };
-    
-            // Finally fix the bucket containing the trailing node.
-            if (n) {
-                this->get_bucket(
-                    policy::to_bucket(this->bucket_count_, n->hash_))->next_
-                    = prev;
-            }
-        }
+    template <>
+    struct pick_policy_impl<64, 2> {
+        typedef mix64_policy<std::size_t> type;
     };
 
+    struct pick_policy :
+        pick_policy_impl<
+            std::numeric_limits<std::size_t>::digits,
+            std::numeric_limits<std::size_t>::radix> {};
+
     ////////////////////////////////////////////////////////////////////////////
     // Functions
 
@@ -1066,8 +794,4 @@
 #endif
 }}}
 
-#if defined(BOOST_MSVC)
-#pragma warning(pop)
-#endif
-
 #endif

Modified: branches/release/boost/unordered/detail/equivalent.hpp
==============================================================================
--- branches/release/boost/unordered/detail/equivalent.hpp	(original)
+++ branches/release/boost/unordered/detail/equivalent.hpp	2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -125,16 +125,15 @@
     {
         typedef boost::unordered::detail::multiset<A, T, H, P> types;
 
+        typedef A allocator;
         typedef T value_type;
         typedef H hasher;
         typedef P key_equal;
         typedef T key_type;
 
-        typedef typename boost::unordered::detail::rebind_wrap<
-                A, value_type>::type allocator;
-
         typedef boost::unordered::detail::allocator_traits<allocator> traits;
-        typedef boost::unordered::detail::pick_grouped_node<allocator, value_type> pick;
+        typedef boost::unordered::detail::pick_grouped_node<allocator,
+            value_type> pick;
         typedef typename pick::node node;
         typedef typename pick::bucket bucket;
         typedef typename pick::link_pointer link_pointer;
@@ -150,16 +149,15 @@
     {
         typedef boost::unordered::detail::multimap<A, K, M, H, P> types;
 
+        typedef A allocator;
         typedef std::pair<K const, M> value_type;
         typedef H hasher;
         typedef P key_equal;
         typedef K key_type;
 
-        typedef typename boost::unordered::detail::rebind_wrap<
-                A, value_type>::type allocator;
-
         typedef boost::unordered::detail::allocator_traits<allocator> traits;
-        typedef boost::unordered::detail::pick_grouped_node<allocator, value_type> pick;
+        typedef boost::unordered::detail::pick_grouped_node<allocator,
+                value_type> pick;
         typedef typename pick::node node;
         typedef typename pick::bucket bucket;
         typedef typename pick::link_pointer link_pointer;
@@ -177,7 +175,6 @@
         typedef boost::unordered::detail::table<Types> table;
         typedef typename table::value_type value_type;
         typedef typename table::bucket bucket;
-        typedef typename table::buckets buckets;
         typedef typename table::policy policy;
         typedef typename table::node_pointer node_pointer;
         typedef typename table::node_allocator node_allocator;
@@ -204,12 +201,17 @@
 
         grouped_table_impl(grouped_table_impl const& x)
           : table(x, node_allocator_traits::
-                select_on_container_copy_construction(x.node_alloc())) {}
+                select_on_container_copy_construction(x.node_alloc()))
+        {
+            this->init(x);
+        }
 
         grouped_table_impl(grouped_table_impl const& x,
                 node_allocator const& a)
           : table(x, a)
-        {}
+        {
+            this->init(x);
+        }
 
         grouped_table_impl(grouped_table_impl& x,
                 boost::unordered::detail::move_tag m)
@@ -220,7 +222,9 @@
                 node_allocator const& a,
                 boost::unordered::detail::move_tag m)
           : table(x, a, m)
-        {}
+        {
+            this->move_init(x);
+        }
 
         // Accessors
 
@@ -230,6 +234,8 @@
                 Key const& k,
                 Pred const& eq) const
         {
+            if (!this->size_) return iterator();
+
             std::size_t bucket_index =
                 policy::to_bucket(this->bucket_count_, key_hash);
             iterator n = this->get_start(bucket_index);
@@ -487,8 +493,7 @@
         iterator emplace(BOOST_UNORDERED_EMPLACE_ARGS)
         {
             node_constructor a(this->node_alloc());
-            a.construct_node();
-            a.construct_value(BOOST_UNORDERED_EMPLACE_FORWARD);
+            a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD);
 
             return iterator(emplace_impl(a));
         }
@@ -507,8 +512,7 @@
             std::size_t distance = boost::unordered::detail::distance(i, j);
             if(distance == 1) {
                 node_constructor a(this->node_alloc());
-                a.construct_node();
-                a.construct_value2(*i);
+                a.construct_with_value2(*i);
                 emplace_impl(a);
             }
             else {
@@ -517,8 +521,7 @@
 
                 node_constructor a(this->node_alloc());
                 for (; i != j; ++i) {
-                    a.construct_node();
-                    a.construct_value2(*i);
+                    a.construct_with_value2(*i);
                     emplace_impl_no_rehash(a);
                 }
             }
@@ -530,8 +533,7 @@
         {
             node_constructor a(this->node_alloc());
             for (; i != j; ++i) {
-                a.construct_node();
-                a.construct_value2(*i);
+                a.construct_with_value2(*i);
                 emplace_impl(a);
             }
         }
@@ -710,20 +712,12 @@
         }
 
         ////////////////////////////////////////////////////////////////////////
-        // copy_buckets_to
-        //
-        // Basic exception safety. If an exception is thrown this will
-        // leave dst partially filled and the buckets unset.
+        // fill_buckets
 
-        static void copy_buckets_to(buckets const& src, buckets& dst)
+        template <class NodeCreator>
+        static void fill_buckets(iterator n, table& dst,
+            NodeCreator& creator)
         {
-            BOOST_ASSERT(!dst.buckets_);
-
-            dst.create_buckets();
-
-            node_constructor a(dst.node_alloc());
-
-            iterator n = src.get_start();
             previous_pointer prev = dst.get_previous_start();
 
             while (n.node_) {
@@ -733,10 +727,7 @@
                         static_cast<node_pointer>(n.node_->group_prev_)->next_
                     ));
 
-                a.construct_node();
-                a.construct_value2(*n);
-
-                node_pointer first_node = a.release();
+                node_pointer first_node = creator.create(*n);
                 node_pointer end = first_node;
                 first_node->hash_ = key_hash;
                 prev->next_ = static_cast<link_pointer>(first_node);
@@ -744,56 +735,7 @@
 
                 for (++n; n != group_end; ++n)
                 {
-                    a.construct_node();
-                    a.construct_value2(*n);
-                    end = a.release();
-                    end->hash_ = key_hash;
-                    add_after_node(end, first_node);
-                    ++dst.size_;
-                }
-
-                prev = place_in_bucket(dst, prev, end);
-            }
-        }
-
-        ////////////////////////////////////////////////////////////////////////
-        // move_buckets_to
-        //
-        // Basic exception safety. The source nodes are left in an unusable
-        // state if an exception throws.
-
-        static void move_buckets_to(buckets& src, buckets& dst)
-        {
-            BOOST_ASSERT(!dst.buckets_);
-
-            dst.create_buckets();
-
-            node_constructor a(dst.node_alloc());
-
-            iterator n = src.get_start();
-            previous_pointer prev = dst.get_previous_start();
-
-            while (n.node_) {
-                std::size_t key_hash = n.node_->hash_;
-                iterator group_end(
-                    static_cast<node_pointer>(
-                        static_cast<node_pointer>(n.node_->group_prev_)->next_
-                    ));
-
-                a.construct_node();
-                a.construct_value2(boost::move(*n));
-
-                node_pointer first_node = a.release();
-                node_pointer end = first_node;
-                first_node->hash_ = key_hash;
-                prev->next_ = static_cast<link_pointer>(first_node);
-                ++dst.size_;
-
-                for(++n; n != group_end; ++n)
-                {
-                    a.construct_node();
-                    a.construct_value2(boost::move(*n));
-                    end = a.release();
+                    end = creator.create(*n);
                     end->hash_ = key_hash;
                     add_after_node(end, first_node);
                     ++dst.size_;
@@ -806,33 +748,19 @@
         // strong otherwise exception safety
         void rehash_impl(std::size_t num_buckets)
         {
-            BOOST_ASSERT(this->size_);
-
-            buckets dst(this->node_alloc(), num_buckets);
-            dst.create_buckets();
+            BOOST_ASSERT(this->buckets_);
 
-            previous_pointer src_start = this->get_previous_start();
-            previous_pointer dst_start = dst.get_previous_start();
-
-            dst_start->next_ = src_start->next_;
-            src_start->next_ = link_pointer();
-            dst.size_ = this->size_;
-            this->size_ = 0;
-
-            previous_pointer prev = dst_start;
+            this->create_buckets(num_buckets);
+            previous_pointer prev = this->get_previous_start();
             while (prev->next_)
-                prev = place_in_bucket(dst, prev,
+                prev = place_in_bucket(*this, prev,
                     static_cast<node_pointer>(
                         static_cast<node_pointer>(prev->next_)->group_prev_));
-
-            // Swap the new nodes back into the container and setup the
-            // variables.
-            dst.swap(*this); // no throw
         }
 
         // Iterate through the nodes placing them in the correct buckets.
         // pre: prev->next_ is not null.
-        static previous_pointer place_in_bucket(buckets& dst,
+        static previous_pointer place_in_bucket(table& dst,
                 previous_pointer prev, node_pointer end)
         {
             bucket_pointer b = dst.get_bucket(policy::to_bucket(

Modified: branches/release/boost/unordered/detail/table.hpp
==============================================================================
--- branches/release/boost/unordered/detail/table.hpp	(original)
+++ branches/release/boost/unordered/detail/table.hpp	2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -13,6 +13,11 @@
 #include <boost/type_traits/alignment_of.hpp>
 #include <cmath>
 
+#if defined(BOOST_MSVC)
+#pragma warning(push)
+#pragma warning(disable:4127) // conditional expression is constant
+#endif
+
 namespace boost { namespace unordered { namespace detail {
 
     ////////////////////////////////////////////////////////////////////////////
@@ -54,13 +59,73 @@
         value_base& operator=(value_base const&);
     };
 
+    template <typename NodeAlloc>
+    struct copy_nodes
+    {
+        typedef boost::unordered::detail::allocator_traits<NodeAlloc>
+            node_allocator_traits;
+
+        node_constructor<NodeAlloc> constructor;
+
+        explicit copy_nodes(NodeAlloc& a) : constructor(a) {}
+
+        typename node_allocator_traits::pointer create(
+                typename node_allocator_traits::value_type::value_type const& v)
+        {
+            constructor.construct_with_value2(v);
+            return constructor.release();
+        }
+    };
+
+    template <typename NodeAlloc>
+    struct move_nodes
+    {
+        typedef boost::unordered::detail::allocator_traits<NodeAlloc>
+            node_allocator_traits;
+
+        node_constructor<NodeAlloc> constructor;
+
+        explicit move_nodes(NodeAlloc& a) : constructor(a) {}
+
+        typename node_allocator_traits::pointer create(
+                typename node_allocator_traits::value_type::value_type& v)
+        {
+            constructor.construct_with_value2(boost::move(v));
+            return constructor.release();
+        }
+    };
+
+    template <typename Buckets>
+    struct assign_nodes
+    {
+        node_holder<typename Buckets::node_allocator> holder;
+
+        explicit assign_nodes(Buckets& b) : holder(b) {}
+
+        typename Buckets::node_pointer create(
+                typename Buckets::value_type const& v)
+        {
+            return holder.copy_of(v);
+        }
+    };
+
+    template <typename Buckets>
+    struct move_assign_nodes
+    {
+        node_holder<typename Buckets::node_allocator> holder;
+
+        explicit move_assign_nodes(Buckets& b) : holder(b) {}
+
+        typename Buckets::node_pointer create(
+                typename Buckets::value_type& v)
+        {
+            return holder.move_copy_of(v);
+        }
+    };
+
     template <typename Types>
     struct table :
-        boost::unordered::detail::buckets<
-            typename Types::allocator,
-            typename Types::bucket,
-            typename Types::node,
-            typename Types::policy>,
+        Types::policy,
         boost::unordered::detail::functions<
             typename Types::hasher,
             typename Types::key_equal>
@@ -69,6 +134,8 @@
         table(table const&);
         table& operator=(table const&);
     public:
+        typedef typename Types::node node;
+        typedef typename Types::bucket bucket;
         typedef typename Types::hasher hasher;
         typedef typename Types::key_equal key_equal;
         typedef typename Types::key_type key_type;
@@ -82,23 +149,128 @@
             typename Types::hasher,
             typename Types::key_equal> functions;
 
-        typedef boost::unordered::detail::buckets<
-            typename Types::allocator,
-            typename Types::bucket,
-            typename Types::node,
-            typename Types::policy> buckets;
-
-        typedef typename buckets::node_allocator node_allocator;
-        typedef typename buckets::node_allocator_traits node_allocator_traits;
-        typedef typename buckets::node_pointer node_pointer;
-        typedef typename buckets::const_node_pointer const_node_pointer;
-
-        typedef typename table::iterator iterator;
+        typedef typename Types::allocator allocator;
+        typedef typename boost::unordered::detail::
+            rebind_wrap<allocator, node>::type node_allocator;
+        typedef typename boost::unordered::detail::
+            rebind_wrap<allocator, bucket>::type bucket_allocator;
+        typedef boost::unordered::detail::allocator_traits<node_allocator>
+            node_allocator_traits;
+        typedef boost::unordered::detail::allocator_traits<bucket_allocator>
+            bucket_allocator_traits;
+        typedef typename node_allocator_traits::pointer
+            node_pointer;
+        typedef typename node_allocator_traits::const_pointer
+            const_node_pointer;
+        typedef typename bucket_allocator_traits::pointer
+            bucket_pointer;
+        typedef typename bucket::previous_pointer
+            previous_pointer;
+        typedef boost::unordered::detail::node_constructor<node_allocator>
+            node_constructor;
+
+        typedef boost::unordered::iterator_detail::
+            iterator<node_pointer, value_type> iterator;
+        typedef boost::unordered::iterator_detail::
+            c_iterator<const_node_pointer, node_pointer, value_type> c_iterator;
+        typedef boost::unordered::iterator_detail::
+            l_iterator<node_pointer, value_type, policy> l_iterator;
+        typedef boost::unordered::iterator_detail::
+            cl_iterator<const_node_pointer, node_pointer, value_type, policy>
+            cl_iterator;
 
+        ////////////////////////////////////////////////////////////////////////
         // Members
 
+        boost::unordered::detail::compressed<bucket_allocator, node_allocator>
+            allocators_;
+        std::size_t bucket_count_;
+        std::size_t size_;
         float mlf_;
-        std::size_t max_load_; // Only use if this->buckets_.
+        std::size_t max_load_; // Only use if buckets_.
+        bucket_pointer buckets_;
+
+        ////////////////////////////////////////////////////////////////////////
+        // Data access
+
+        bucket_allocator const& bucket_alloc() const
+        {
+            return allocators_.first();
+        }
+
+        node_allocator const& node_alloc() const
+        {
+            return allocators_.second();
+        }
+
+        bucket_allocator& bucket_alloc()
+        {
+            return allocators_.first();
+        }
+
+        node_allocator& node_alloc()
+        {
+            return allocators_.second();
+        }
+
+        std::size_t max_bucket_count() const
+        {
+            // -1 to account for the start bucket.
+            return policy::prev_bucket_count(
+                bucket_allocator_traits::max_size(bucket_alloc()) - 1);
+        }
+
+        bucket_pointer get_bucket(std::size_t bucket_index) const
+        {
+            return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
+        }
+
+        previous_pointer get_previous_start() const
+        {
+            return get_bucket(bucket_count_)->first_from_start();
+        }
+
+        previous_pointer get_previous_start(std::size_t bucket_index) const
+        {
+            return get_bucket(bucket_index)->next_;
+        }
+
+        iterator get_start() const
+        {
+            return iterator(static_cast<node_pointer>(
+                        get_previous_start()->next_));
+        }
+
+        iterator get_start(std::size_t bucket_index) const
+        {
+            previous_pointer prev = get_previous_start(bucket_index);
+            return prev ? iterator(static_cast<node_pointer>(prev->next_)) :
+                iterator();
+        }
+
+        float load_factor() const
+        {
+            BOOST_ASSERT(bucket_count_ != 0);
+            return static_cast<float>(size_)
+                / static_cast<float>(bucket_count_);
+        }
+
+        std::size_t bucket_size(std::size_t index) const
+        {
+            if (!size_) return 0;
+            iterator it = get_start(index);
+            if (!it.node_) return 0;
+
+            std::size_t count = 0;
+            while(it.node_ && policy::to_bucket(
+                        bucket_count_, it.node_->hash_) == index)
+            {
+                ++count;
+                ++it;
+            }
+
+            return count;
+        }
 
         ////////////////////////////////////////////////////////////////////////
         // Load methods
@@ -109,34 +281,34 @@
     
             // size < mlf_ * count
             return boost::unordered::detail::double_to_size(ceil(
-                    static_cast<double>(this->mlf_) *
-                    static_cast<double>(this->max_bucket_count())
+                    static_cast<double>(mlf_) *
+                    static_cast<double>(max_bucket_count())
                 )) - 1;
         }
 
-        std::size_t calculate_max_load()
+        void recalculate_max_load()
         {
             using namespace std;
     
             // From 6.3.1/13:
             // Only resize when size >= mlf_ * count
-            return boost::unordered::detail::double_to_size(ceil(
-                    static_cast<double>(this->mlf_) *
-                    static_cast<double>(this->bucket_count_)
+            max_load_ = boost::unordered::detail::double_to_size(ceil(
+                    static_cast<double>(mlf_) *
+                    static_cast<double>(bucket_count_)
                 ));
 
         }
+
         void max_load_factor(float z)
         {
             BOOST_ASSERT(z > 0);
             mlf_ = (std::max)(z, minimum_max_load_factor);
-            if (this->buckets_)
-                this->max_load_ = this->calculate_max_load();
+            if (buckets_) recalculate_max_load();
         }
 
         std::size_t min_buckets_for_size(std::size_t size) const
         {
-            BOOST_ASSERT(this->mlf_ >= minimum_max_load_factor);
+            BOOST_ASSERT(mlf_ >= minimum_max_load_factor);
     
             using namespace std;
     
@@ -160,127 +332,450 @@
                 hasher const& hf,
                 key_equal const& eq,
                 node_allocator const& a) :
-            buckets(a, policy::new_bucket_count(num_buckets)),
             functions(hf, eq),
+            allocators_(a,a),
+            bucket_count_(policy::new_bucket_count(num_buckets)),
+            size_(0),
             mlf_(1.0f),
-            max_load_(0)
+            max_load_(0),
+            buckets_()
         {}
 
         table(table const& x, node_allocator const& a) :
-            buckets(a, x.min_buckets_for_size(x.size_)),
             functions(x),
+            allocators_(a,a),
+            bucket_count_(x.min_buckets_for_size(x.size_)),
+            size_(0),
             mlf_(x.mlf_),
-            max_load_(0)
-        {
-            if(x.size_) {
-                table_impl::copy_buckets_to(x, *this);
-                this->max_load_ = calculate_max_load();
-            }
-        }
+            max_load_(0),
+            buckets_()
+        {}
 
-        // TODO: Why calculate_max_load?
         table(table& x, boost::unordered::detail::move_tag m) :
-            buckets(x, m),
             functions(x),
+            allocators_(x.allocators_, m),
+            bucket_count_(x.bucket_count_),
+            size_(x.size_),
             mlf_(x.mlf_),
-            max_load_(calculate_max_load())
-        {}
+            max_load_(x.max_load_),
+            buckets_(x.buckets_)
+        {
+            x.buckets_ = bucket_pointer();
+            x.size_ = 0;
+        }
 
-        // TODO: Why not calculate_max_load?
-        // TODO: Why do I use x's bucket count?
         table(table& x, node_allocator const& a,
-                boost::unordered::detail::move_tag m) :
-            buckets(a, x.bucket_count_),
+                boost::unordered::detail::move_tag) :
             functions(x),
+            allocators_(a, a),
+            bucket_count_(x.bucket_count_),
+            size_(0),
             mlf_(x.mlf_),
-            max_load_(x.max_load_)
+            max_load_(x.max_load_),
+            buckets_()
+        {}
+
+        ////////////////////////////////////////////////////////////////////////
+        // Initialisation.
+
+        void init(table const& x)
         {
-            if(a == x.node_alloc()) {
-                this->buckets::swap(x, false_type());
+            if (x.size_) {
+                create_buckets(bucket_count_);
+                copy_nodes<node_allocator> copy(node_alloc());
+                table_impl::fill_buckets(x.get_start(), *this, copy);
+            }
+        }
+
+        void move_init(table& x)
+        {
+            if(node_alloc() == x.node_alloc()) {
+                move_buckets_from(x);
             }
             else if(x.size_) {
-                // Use a temporary table because move_buckets_to leaves the
-                // source container in a complete mess.
+                // TODO: Could pick new bucket size?
+                create_buckets(bucket_count_);
+
+                move_nodes<node_allocator> move(node_alloc());
+                node_holder<node_allocator> nodes(x);
+                table_impl::fill_buckets(nodes.get_start(), *this, move);
+            }
+        }
+
+        ////////////////////////////////////////////////////////////////////////
+        // Create buckets
+
+        void create_buckets(std::size_t new_count)
+        {
+            boost::unordered::detail::array_constructor<bucket_allocator>
+                constructor(bucket_alloc());
+    
+            // Creates an extra bucket to act as the start node.
+            constructor.construct(bucket(), new_count + 1);
+
+            if (buckets_)
+            {
+                // Copy the nodes to the new buckets, including the dummy
+                // node if there is one.
+                (constructor.get() +
+                    static_cast<std::ptrdiff_t>(new_count))->next_ =
+                        (buckets_ + static_cast<std::ptrdiff_t>(
+                            bucket_count_))->next_;
+                destroy_buckets();
+            }
+            else if (bucket::extra_node)
+            {
+                node_constructor a(node_alloc());
+                a.construct();
+
+                (constructor.get() +
+                    static_cast<std::ptrdiff_t>(new_count))->next_ =
+                        a.release();
+            }
+
+            bucket_count_ = new_count;
+            buckets_ = constructor.release();
+            recalculate_max_load();
+        }
+
+        ////////////////////////////////////////////////////////////////////////
+        // Swap and Move
+
+        void swap_allocators(table& other, false_type)
+        {
+            // According to 23.2.1.8, if propagate_on_container_swap is
+            // false the behaviour is undefined unless the allocators
+            // are equal.
+            BOOST_ASSERT(node_alloc() == other.node_alloc());
+        }
+
+        void swap_allocators(table& other, true_type)
+        {
+            allocators_.swap(other.allocators_);
+        }
+
+        // Only swaps the allocators if propagate_on_container_swap
+        void swap(table& x)
+        {
+            boost::unordered::detail::set_hash_functions<hasher, key_equal>
+                op1(*this, x);
+            boost::unordered::detail::set_hash_functions<hasher, key_equal>
+                op2(x, *this);
+
+            // I think swap can throw if Propagate::value,
+            // since the allocators' swap can throw. Not sure though.
+            swap_allocators(x,
+                boost::unordered::detail::integral_constant<bool,
+                    allocator_traits<node_allocator>::
+                    propagate_on_container_swap::value>());
+
+            boost::swap(buckets_, x.buckets_);
+            boost::swap(bucket_count_, x.bucket_count_);
+            boost::swap(size_, x.size_);
+            std::swap(mlf_, x.mlf_);
+            std::swap(max_load_, x.max_load_);
+            op1.commit();
+            op2.commit();
+        }
+
+        void move_buckets_from(table& other)
+        {
+            BOOST_ASSERT(node_alloc() == other.node_alloc());
+            BOOST_ASSERT(!buckets_);
+            buckets_ = other.buckets_;
+            bucket_count_ = other.bucket_count_;
+            size_ = other.size_;
+            other.buckets_ = bucket_pointer();
+            other.size_ = 0;
+        }
+
+        ////////////////////////////////////////////////////////////////////////
+        // Delete/destruct
+
+        ~table()
+        {
+            delete_buckets();
+        }
+
+        void delete_node(c_iterator n)
+        {
+            boost::unordered::detail::destroy_value_impl(node_alloc(),
+                n.node_->value_ptr());
+            node_allocator_traits::destroy(node_alloc(),
+                    boost::addressof(*n.node_));
+            node_allocator_traits::deallocate(node_alloc(), n.node_, 1);
+            --size_;
+        }
+
+        std::size_t delete_nodes(c_iterator begin, c_iterator end)
+        {
+            std::size_t count = 0;
+
+            while(begin != end) {
+                c_iterator n = begin;
+                ++begin;
+                delete_node(n);
+                ++count;
+            }
+
+            return count;
+        }
+
+        void delete_buckets()
+        {
+            if(buckets_) {
+                delete_nodes(get_start(), iterator());
+
+                if (bucket::extra_node) {
+                    node_pointer n = static_cast<node_pointer>(
+                            get_bucket(bucket_count_)->next_);
+                    node_allocator_traits::destroy(node_alloc(),
+                            boost::addressof(*n));
+                    node_allocator_traits::deallocate(node_alloc(), n, 1);
+                }
+
+                destroy_buckets();
+                buckets_ = bucket_pointer();
+            }
+
+            BOOST_ASSERT(!size_);
+        }
+
+        void clear()
+        {
+            if(!size_) return;
+
+            delete_nodes(get_start(), iterator());
+            get_previous_start()->next_ = link_pointer();
+            clear_buckets();
+
+            BOOST_ASSERT(!size_);
+        }
+
+        void clear_buckets()
+        {
+            bucket_pointer end = get_bucket(bucket_count_);
+            for(bucket_pointer it = buckets_; it != end; ++it)
+            {
+                it->next_ = node_pointer();
+            }
+        }
+
+        void destroy_buckets()
+        {
+            bucket_pointer end = get_bucket(bucket_count_ + 1);
+            for(bucket_pointer it = buckets_; it != end; ++it)
+            {
+                bucket_allocator_traits::destroy(bucket_alloc(),
+                    boost::addressof(*it));
+            }
+
+            bucket_allocator_traits::deallocate(bucket_alloc(),
+                buckets_, bucket_count_ + 1);
+        }
+
+        ////////////////////////////////////////////////////////////////////////
+        // Fix buckets after erase
+
+        // This is called after erasing a node or group of nodes to fix up
+        // the bucket pointers.
+        void fix_buckets(bucket_pointer this_bucket,
+                previous_pointer prev, node_pointer next)
+        {
+            if (!next)
+            {
+                if (this_bucket->next_ == prev)
+                    this_bucket->next_ = node_pointer();
+            }
+            else
+            {
+                bucket_pointer next_bucket = get_bucket(
+                    policy::to_bucket(bucket_count_, next->hash_));
+
+                if (next_bucket != this_bucket)
+                {
+                    next_bucket->next_ = prev;
+                    if (this_bucket->next_ == prev)
+                        this_bucket->next_ = node_pointer();
+                }
+            }
+        }
+
+        // This is called after erasing a range of nodes to fix any bucket
+        // pointers into that range.
+        void fix_buckets_range(std::size_t bucket_index,
+                previous_pointer prev, node_pointer begin, node_pointer end)
+        {
+            node_pointer n = begin;
+
+            // If we're not at the start of the current bucket, then
+            // go to the start of the next bucket.
+            if (get_bucket(bucket_index)->next_ != prev)
+            {
+                for(;;) {
+                    n = static_cast<node_pointer>(n->next_);
+                    if (n == end) return;
+
+                    std::size_t new_bucket_index =
+                        policy::to_bucket(bucket_count_, n->hash_);
+                    if (bucket_index != new_bucket_index) {
+                        bucket_index = new_bucket_index;
+                        break;
+                    }
+                }
+            }
+
+            // Iterate through the remaining nodes, clearing out the bucket
+            // pointers.
+            get_bucket(bucket_index)->next_ = previous_pointer();
+            for(;;) {
+                n = static_cast<node_pointer>(n->next_);
+                if (n == end) break;
+
+                std::size_t new_bucket_index =
+                    policy::to_bucket(bucket_count_, n->hash_);
+                if (bucket_index != new_bucket_index) {
+                    bucket_index = new_bucket_index;
+                    get_bucket(bucket_index)->next_ = previous_pointer();
+                }
+            };
 
-                buckets tmp(x, m);
-                table_impl::move_buckets_to(tmp, *this);
-                this->max_load_ = calculate_max_load();
+            // Finally fix the bucket containing the trailing node.
+            if (n) {
+                get_bucket(
+                    policy::to_bucket(bucket_count_, n->hash_))->next_
+                    = prev;
             }
         }
 
+        ////////////////////////////////////////////////////////////////////////
         // Iterators
 
         iterator begin() const {
-            return !this->buckets_ ?
-                iterator() : this->get_start();
+            return !buckets_ ? iterator() : get_start();
         }
 
+        ////////////////////////////////////////////////////////////////////////
         // Assignment
 
         void assign(table const& x)
         {
-            assign(x,
-                boost::unordered::detail::integral_constant<bool,
-                    allocator_traits<node_allocator>::
-                    propagate_on_container_copy_assignment::value>());
+            if (this != boost::addressof(x))
+            {
+                assign(x,
+                    boost::unordered::detail::integral_constant<bool,
+                        allocator_traits<node_allocator>::
+                        propagate_on_container_copy_assignment::value>());
+            }
         }
 
         void assign(table const& x, false_type)
         {
-            table tmp(x, this->node_alloc());
-            this->swap(tmp, false_type());
+            // Strong exception safety.
+            boost::unordered::detail::set_hash_functions<hasher, key_equal>
+                new_func_this(*this, x);
+            new_func_this.commit();
+            mlf_ = x.mlf_;
+            recalculate_max_load();
+
+            if (!size_ && !x.size_) return;
+
+            if (!buckets_ || x.size_ >= max_load_) {
+                create_buckets(min_buckets_for_size(x.size_));
+            }
+            else {
+                clear_buckets();
+            }
+
+            // assign_nodes takes ownership of the container's elements,
+            // assigning to them if possible, and deleting any that are
+            // left over.
+            assign_nodes<table> assign(*this);
+
+            if (x.size_) {
+                table_impl::fill_buckets(x.get_start(), *this, assign);
+            }
         }
 
         void assign(table const& x, true_type)
         {
-            table tmp(x, x.node_alloc());
-            // Need to delete before setting the allocator so that buckets
-            // aren't deleted with the wrong allocator.
-            if(this->buckets_) this->delete_buckets();
-            // TODO: Can allocator assignment throw?
-            this->allocators_.assign(x.allocators_);
-            this->swap(tmp, false_type());
+            if (node_alloc() == x.node_alloc()) {
+                allocators_.assign(x.allocators_);
+                assign(x, false_type());
+            }
+            else {
+                boost::unordered::detail::set_hash_functions<hasher, key_equal>
+                    new_func_this(*this, x);
+
+                // Delete everything with current allocators before assigning
+                // the new ones.
+                if (buckets_) delete_buckets();
+                allocators_.assign(x.allocators_);
+
+                // Copy over other data, all no throw.
+                new_func_this.commit();
+                mlf_ = x.mlf_;
+                bucket_count_ = min_buckets_for_size(x.size_);
+                max_load_ = 0;
+
+                // Finally copy the elements.
+                if (x.size_) {
+                    create_buckets(bucket_count_);
+                    copy_nodes<node_allocator> copy(node_alloc());
+                    table_impl::fill_buckets(x.get_start(), *this, copy);
+                }
+            }
         }
 
         void move_assign(table& x)
         {
-            move_assign(x,
-                boost::unordered::detail::integral_constant<bool,
-                    allocator_traits<node_allocator>::
-                    propagate_on_container_move_assignment::value>());
+            if (this != boost::addressof(x))
+            {
+                move_assign(x,
+                    boost::unordered::detail::integral_constant<bool,
+                        allocator_traits<node_allocator>::
+                        propagate_on_container_move_assignment::value>());
+            }
         }
 
         void move_assign(table& x, true_type)
         {
-            if(this->buckets_) this->delete_buckets();
-            this->allocators_.move_assign(x.allocators_);
+            if(buckets_) delete_buckets();
+            allocators_.move_assign(x.allocators_);
             move_assign_no_alloc(x);
         }
 
         void move_assign(table& x, false_type)
         {
-            if(this->node_alloc() == x.node_alloc()) {
-                if(this->buckets_) this->delete_buckets();
+            if (node_alloc() == x.node_alloc()) {
+                if(buckets_) delete_buckets();
                 move_assign_no_alloc(x);
             }
             else {
                 boost::unordered::detail::set_hash_functions<hasher, key_equal>
                     new_func_this(*this, x);
+                new_func_this.commit();
+                mlf_ = x.mlf_;
+                recalculate_max_load();
 
-                if (x.size_) {
-                    buckets b(this->node_alloc(),
-                        x.min_buckets_for_size(x.size_));
-                    buckets tmp(x, move_tag());
-                    table_impl::move_buckets_to(tmp, b);
-                    b.swap(*this);
+                if (!size_ && !x.size_) return;
+
+                if (!buckets_ || x.size_ >= max_load_) {
+                    create_buckets(min_buckets_for_size(x.size_));
                 }
                 else {
-                    this->clear();
+                    clear_buckets();
+                }
+
+                // move_assign_nodes takes ownership of the container's
+                // elements, assigning to them if possible, and deleting
+                // any that are left over.
+                move_assign_nodes<table> assign(*this);
+
+                if (x.size_) {
+                    node_holder<node_allocator> nodes(x);
+                    table_impl::fill_buckets(nodes.get_start(), *this, assign);
                 }
-                
-                this->mlf_ = x.mlf_;
-                if (this->buckets_) this->max_load_ = calculate_max_load();
-                new_func_this.commit();
             }
         }
         
@@ -289,53 +784,12 @@
             boost::unordered::detail::set_hash_functions<hasher, key_equal>
                 new_func_this(*this, x);
             // No throw from here.
-            this->move_buckets_from(x);
-            this->mlf_ = x.mlf_;
-            this->max_load_ = x.max_load_;
+            move_buckets_from(x);
+            mlf_ = x.mlf_;
+            max_load_ = x.max_load_;
             new_func_this.commit();
         }
 
-        ////////////////////////////////////////////////////////////////////////
-        // Swap & Move
-
-        void swap(table& x)
-        {
-            swap(x,
-                boost::unordered::detail::integral_constant<bool,
-                    allocator_traits<node_allocator>::
-                    propagate_on_container_swap::value>());
-        }
-
-        // Only swaps the allocators if Propagate::value
-        template <typename Propagate>
-        void swap(table& x, Propagate p)
-        {
-            // According to 23.2.1.8, if propagate_on_container_swap is
-            // false the behaviour is undefined unless the allocators
-            // are equal.
-            BOOST_ASSERT(p.value || this->node_alloc() == x.node_alloc());
-
-            boost::unordered::detail::set_hash_functions<hasher, key_equal>
-                op1(*this, x);
-            boost::unordered::detail::set_hash_functions<hasher, key_equal>
-                op2(x, *this);
-            // I think swap can throw if Propagate::value,
-            // since the allocators' swap can throw. Not sure though.
-            this->buckets::swap(x, p);
-            std::swap(this->mlf_, x.mlf_);
-            std::swap(this->max_load_, x.max_load_);
-            op1.commit();
-            op2.commit();
-        }
-
-        // Swap everything but the allocators, and the functions objects.
-        void swap_contents(table& x)
-        {
-            this->buckets::swap(x, false_type());
-            std::swap(this->mlf_, x.mlf_);
-            std::swap(this->max_load_, x.max_load_);
-        }
-
         // Accessors
 
         key_type const& get_key(value_type const& x) const
@@ -356,7 +810,6 @@
                 Hash const& hf,
                 Pred const& eq) const
         {
-            if (!this->size_) return iterator();
             return static_cast<table_impl const*>(this)->
                 find_node_impl(policy::apply_hash(hf, k), k, eq);
         }
@@ -365,16 +818,14 @@
                 std::size_t key_hash,
                 key_type const& k) const
         {
-            if (!this->size_) return iterator();
             return static_cast<table_impl const*>(this)->
                 find_node_impl(key_hash, k, this->key_eq());
         }
 
         iterator find_node(key_type const& k) const
         {
-            if (!this->size_) return iterator();
             return static_cast<table_impl const*>(this)->
-                find_node_impl(this->hash(k), k, this->key_eq());
+                find_node_impl(hash(k), k, this->key_eq());
         }
 
         iterator find_matching_node(iterator n) const
@@ -402,22 +853,19 @@
     template <typename Types>
     inline void table<Types>::reserve_for_insert(std::size_t size)
     {
-        if (!this->buckets_) {
-            this->bucket_count_ = (std::max)(this->bucket_count_,
-                this->min_buckets_for_size(size));
-            this->create_buckets();
-            this->max_load_ = this->calculate_max_load();
+        if (!buckets_) {
+            create_buckets((std::max)(bucket_count_,
+                min_buckets_for_size(size)));
         }
         // According to the standard this should be 'size >= max_load_',
         // but I think this is better, defect report filed.
         else if(size > max_load_) {
             std::size_t num_buckets
-                = this->min_buckets_for_size((std::max)(size,
-                    this->size_ + (this->size_ >> 1)));
-            if (num_buckets != this->bucket_count_) {
+                = min_buckets_for_size((std::max)(size,
+                    size_ + (size_ >> 1)));
+
+            if (num_buckets != bucket_count_)
                 static_cast<table_impl*>(this)->rehash_impl(num_buckets);
-                this->max_load_ = this->calculate_max_load();
-            }
         }
     }
 
@@ -429,20 +877,18 @@
     {
         using namespace std;
 
-        if(!this->size_) {
-            if(this->buckets_) this->delete_buckets();
-            this->bucket_count_ = policy::new_bucket_count(min_buckets);
+        if(!size_) {
+            if(buckets_) delete_buckets();
+            bucket_count_ = policy::new_bucket_count(min_buckets);
         }
         else {
             min_buckets = policy::new_bucket_count((std::max)(min_buckets,
                 boost::unordered::detail::double_to_size(floor(
-                    static_cast<double>(this->size_) /
+                    static_cast<double>(size_) /
                     static_cast<double>(mlf_))) + 1));
 
-            if(min_buckets != this->bucket_count_) {
+            if(min_buckets != bucket_count_)
                 static_cast<table_impl*>(this)->rehash_impl(min_buckets);
-                this->max_load_ = this->calculate_max_load();
-            }
         }
     }
 
@@ -450,8 +896,12 @@
     inline void table<Types>::reserve(std::size_t num_elements)
     {
         rehash(static_cast<std::size_t>(
-            std::ceil(static_cast<double>(num_elements) / this->mlf_)));
+            std::ceil(static_cast<double>(num_elements) / mlf_)));
     }
 }}}
 
+#if defined(BOOST_MSVC)
+#pragma warning(pop)
+#endif
+
 #endif

Modified: branches/release/boost/unordered/detail/unique.hpp
==============================================================================
--- branches/release/boost/unordered/detail/unique.hpp	(original)
+++ branches/release/boost/unordered/detail/unique.hpp	2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -121,14 +121,12 @@
     {
         typedef boost::unordered::detail::set<A, T, H, P> types;
 
+        typedef A allocator;
         typedef T value_type;
         typedef H hasher;
         typedef P key_equal;
         typedef T key_type;
 
-        typedef typename boost::unordered::detail::rebind_wrap<
-                A, value_type>::type allocator;
-
         typedef boost::unordered::detail::allocator_traits<allocator> traits;
         typedef boost::unordered::detail::pick_node<allocator, value_type> pick;
         typedef typename pick::node node;
@@ -146,15 +144,14 @@
     {
         typedef boost::unordered::detail::map<A, K, M, H, P> types;
 
+        typedef A allocator;
         typedef std::pair<K const, M> value_type;
         typedef H hasher;
         typedef P key_equal;
         typedef K key_type;
 
-        typedef typename boost::unordered::detail::rebind_wrap<
-                A, value_type>::type allocator;
-
-        typedef boost::unordered::detail::allocator_traits<allocator> traits;
+        typedef boost::unordered::detail::allocator_traits<allocator>
+            traits;
         typedef boost::unordered::detail::pick_node<allocator, value_type> pick;
         typedef typename pick::node node;
         typedef typename pick::bucket bucket;
@@ -173,7 +170,6 @@
         typedef boost::unordered::detail::table<Types> table;
         typedef typename table::value_type value_type;
         typedef typename table::bucket bucket;
-        typedef typename table::buckets buckets;
         typedef typename table::policy policy;
         typedef typename table::node_pointer node_pointer;
         typedef typename table::node_allocator node_allocator;
@@ -202,12 +198,17 @@
 
         table_impl(table_impl const& x)
           : table(x, node_allocator_traits::
-                select_on_container_copy_construction(x.node_alloc())) {}
+                select_on_container_copy_construction(x.node_alloc()))
+        {
+            this->init(x);
+        }
 
         table_impl(table_impl const& x,
                 node_allocator const& a)
           : table(x, a)
-        {}
+        {
+            this->init(x);
+        }
 
         table_impl(table_impl& x,
                 boost::unordered::detail::move_tag m)
@@ -218,7 +219,9 @@
                 node_allocator const& a,
                 boost::unordered::detail::move_tag m)
           : table(x, a, m)
-        {}
+        {
+            this->move_init(x);
+        }
 
         // Accessors
 
@@ -228,6 +231,8 @@
                 Key const& k,
                 Pred const& eq) const
         {
+            if (!this->size_) return iterator();
+
             std::size_t bucket_index =
                 policy::to_bucket(this->bucket_count_, key_hash);
             iterator n = this->get_start(bucket_index);
@@ -349,9 +354,7 @@
             // Create the node before rehashing in case it throws an
             // exception (need strong safety in such a case).
             node_constructor a(this->node_alloc());
-            a.construct_node();
-
-            a.construct_value(BOOST_UNORDERED_EMPLACE_ARGS3(
+            a.construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS3(
                 boost::unordered::piecewise_construct,
                 boost::make_tuple(k),
                 boost::make_tuple()));
@@ -413,8 +416,7 @@
             // Create the node before rehashing in case it throws an
             // exception (need strong safety in such a case).
             node_constructor a(this->node_alloc());
-            a.construct_node();
-            a.construct_value(BOOST_UNORDERED_EMPLACE_FORWARD);
+            a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD);
     
             // reserve has basic exception safety if the hash function
             // throws, strong otherwise.
@@ -442,8 +444,7 @@
             // Don't have a key, so construct the node first in order
             // to be able to lookup the position.
             node_constructor a(this->node_alloc());
-            a.construct_node();
-            a.construct_value(BOOST_UNORDERED_EMPLACE_FORWARD);
+            a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD);
             return emplace_impl_with_node(a);
         }
 
@@ -490,8 +491,7 @@
             InputIt i, InputIt j)
         {
             std::size_t key_hash = this->hash(k);
-            a.construct_node();
-            a.construct_value2(*i);
+            a.construct_with_value2(*i);
             this->reserve_for_insert(this->size_ +
                 boost::unordered::detail::insert_size(i, j));
             this->add_node(a, key_hash);
@@ -506,9 +506,7 @@
             iterator pos = this->find_node(key_hash, k);
     
             if (!pos.node_) {
-                a.construct_node();
-                a.construct_value2(*i);
-    
+                a.construct_with_value2(*i);
                 if(this->size_ + 1 > this->max_load_)
                     this->reserve_for_insert(this->size_ +
                         boost::unordered::detail::insert_size(i, j));
@@ -524,8 +522,7 @@
             node_constructor a(this->node_alloc());
 
             do {
-                a.construct_node();
-                a.construct_value2(*i);
+                a.construct_with_value2(*i);
                 emplace_impl_with_node(a);
             } while(++i != j);
         }
@@ -617,58 +614,16 @@
         }
 
         ////////////////////////////////////////////////////////////////////////
-        // copy_buckets_to
-        //
-        // Basic exception safety. If an exception is thrown this will
-        // leave dst partially filled and the buckets unset.
-
-        static void copy_buckets_to(buckets const& src, buckets& dst)
-        {
-            BOOST_ASSERT(!dst.buckets_);
-
-            dst.create_buckets();
-
-            node_constructor a(dst.node_alloc());
-
-            iterator n = src.get_start();
-            previous_pointer prev = dst.get_previous_start();
-
-            while(n.node_) {
-                a.construct_node();
-                a.construct_value2(*n);
-
-                node_pointer node = a.release();
-                node->hash_ = n.node_->hash_;
-                prev->next_ = static_cast<link_pointer>(node);
-                ++dst.size_;
-                ++n;
-
-                prev = place_in_bucket(dst, prev);
-            }
-        }
-
-        ////////////////////////////////////////////////////////////////////////
-        // move_buckets_to
-        //
-        // Basic exception safety. The source nodes are left in an unusable
-        // state if an exception throws.
+        // fill_buckets
 
-        static void move_buckets_to(buckets& src, buckets& dst)
+        template <class NodeCreator>
+        static void fill_buckets(iterator n, table& dst,
+            NodeCreator& creator)
         {
-            BOOST_ASSERT(!dst.buckets_);
-
-            dst.create_buckets();
-
-            node_constructor a(dst.node_alloc());
-
-            iterator n = src.get_start();
             previous_pointer prev = dst.get_previous_start();
 
             while (n.node_) {
-                a.construct_node();
-                a.construct_value2(boost::move(*n));
-
-                node_pointer node = a.release();
+                node_pointer node = creator.create(*n);
                 node->hash_ = n.node_->hash_;
                 prev->next_ = static_cast<link_pointer>(node);
                 ++dst.size_;
@@ -681,36 +636,22 @@
         // strong otherwise exception safety
         void rehash_impl(std::size_t num_buckets)
         {
-            BOOST_ASSERT(this->size_);
-
-            buckets dst(this->node_alloc(), num_buckets);
-            dst.create_buckets();
+            BOOST_ASSERT(this->buckets_);
 
-            previous_pointer src_start = this->get_previous_start();
-            previous_pointer dst_start = dst.get_previous_start();
-
-            dst_start->next_ = src_start->next_;
-            src_start->next_ = link_pointer();
-            dst.size_ = this->size_;
-            this->size_ = 0;
-
-            previous_pointer prev = dst.get_previous_start();
+            this->create_buckets(num_buckets);
+            previous_pointer prev = this->get_previous_start();
             while (prev->next_)
-                prev = place_in_bucket(dst, prev);
-
-            // Swap the new nodes back into the container and setup the
-            // variables.
-            dst.swap(*this); // no throw
+                prev = place_in_bucket(*this, prev);
         }
 
         // Iterate through the nodes placing them in the correct buckets.
         // pre: prev->next_ is not null.
-        static previous_pointer place_in_bucket(buckets& dst,
+        static previous_pointer place_in_bucket(table& dst,
                 previous_pointer prev)
         {
             node_pointer n = static_cast<node_pointer>(prev->next_);
             bucket_pointer b = dst.get_bucket(
-                buckets::to_bucket(dst.bucket_count_, n->hash_));
+                table::to_bucket(dst.bucket_count_, n->hash_));
 
             if (!b->next_) {
                 b->next_ = prev;

Modified: branches/release/boost/unordered/unordered_map.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_map.hpp	(original)
+++ branches/release/boost/unordered/unordered_map.hpp	2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -56,7 +56,6 @@
     private:
 
         typedef boost::unordered::detail::map<A, K, T, H, P> types;
-        typedef typename types::allocator value_allocator;
         typedef typename types::traits allocator_traits;
         typedef typename types::table table;
 
@@ -542,7 +541,6 @@
     private:
 
         typedef boost::unordered::detail::multimap<A, K, T, H, P> types;
-        typedef typename types::allocator value_allocator;
         typedef typename types::traits allocator_traits;
         typedef typename types::table table;
 

Modified: branches/release/boost/unordered/unordered_set.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_set.hpp	(original)
+++ branches/release/boost/unordered/unordered_set.hpp	2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -54,7 +54,6 @@
     private:
 
         typedef boost::unordered::detail::set<A, T, H, P> types;
-        typedef typename types::allocator value_allocator;
         typedef typename types::traits allocator_traits;
         typedef typename types::table table;
 
@@ -526,7 +525,6 @@
     private:
 
         typedef boost::unordered::detail::multiset<A, T, H, P> types;
-        typedef typename types::allocator value_allocator;
         typedef typename types::traits allocator_traits;
         typedef typename types::table table;
 

Modified: branches/release/libs/unordered/test/objects/test.hpp
==============================================================================
--- branches/release/libs/unordered/test/objects/test.hpp	(original)
+++ branches/release/libs/unordered/test/objects/test.hpp	2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -186,9 +186,8 @@
         }
     };
 
-    // allocator1 and allocator2 are pretty similar.
     // allocator1 only has the old fashioned 'construct' method and has
-    // a few less typedefs
+    // a few less typedefs. allocator2 uses a custom pointer class.
 
     template <class T>
     class allocator1
@@ -273,6 +272,127 @@
         };
     };
 
+    template <class T> class ptr;
+    template <class T> class const_ptr;
+
+    struct void_ptr
+    {
+#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+        template <typename T>
+        friend class ptr;
+    private:
+#endif
+
+        void* ptr_;
+
+    public:
+        void_ptr() : ptr_(0) {}
+
+        template <typename T>
+        explicit void_ptr(ptr<T> const& x) : ptr_(x.ptr_) {}
+
+        // I'm not using the safe bool idiom because the containers should be
+        // able to cope with bool conversions.
+        operator bool() const { return !!ptr_; }
+
+        bool operator==(void_ptr const& x) const { return ptr_ == x.ptr_; }
+        bool operator!=(void_ptr const& x) const { return ptr_ != x.ptr_; }
+    };
+
+    class void_const_ptr
+    {
+#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+        template <typename T>
+        friend class const_ptr;
+    private:
+#endif
+
+        void* ptr_;
+
+    public:
+        void_const_ptr() : ptr_(0) {}
+
+        template <typename T>
+        explicit void_const_ptr(const_ptr<T> const& x) : ptr_(x.ptr_) {}
+
+        // I'm not using the safe bool idiom because the containers should be
+        // able to cope with bool conversions.
+        operator bool() const { return !!ptr_; }
+
+        bool operator==(void_const_ptr const& x) const { return ptr_ == x.ptr_; }
+        bool operator!=(void_const_ptr const& x) const { return ptr_ != x.ptr_; }
+    };
+
+    template <class T>
+    class ptr
+    {
+        friend class allocator2<T>;
+        friend class const_ptr<T>;
+        friend struct void_ptr;
+
+        T* ptr_;
+
+        ptr(T* x) : ptr_(x) {}
+    public:
+        ptr() : ptr_(0) {}
+        explicit ptr(void_ptr const& x) : ptr_((T*) x.ptr_) {}
+
+        T& operator*() const { return *ptr_; }
+        T* operator->() const { return ptr_; }
+        ptr& operator++() { ++ptr_; return *this; }
+        ptr operator++(int) { ptr tmp(*this); ++ptr_; return tmp; }
+        ptr operator+(std::ptrdiff_t s) const { return ptr<T>(ptr_ + s); }
+        friend ptr operator+(std::ptrdiff_t s, ptr p)
+            { return ptr<T>(s + p.ptr_); }
+        T& operator[](std::ptrdiff_t s) const { return ptr_[s]; }
+        bool operator!() const { return !ptr_; }
+
+        // I'm not using the safe bool idiom because the containers should be
+        // able to cope with bool conversions.
+        operator bool() const { return !!ptr_; }
+
+        bool operator==(ptr const& x) const { return ptr_ == x.ptr_; }
+        bool operator!=(ptr const& x) const { return ptr_ != x.ptr_; }
+        bool operator<(ptr const& x) const { return ptr_ < x.ptr_; }
+        bool operator>(ptr const& x) const { return ptr_ > x.ptr_; }
+        bool operator<=(ptr const& x) const { return ptr_ <= x.ptr_; }
+        bool operator>=(ptr const& x) const { return ptr_ >= x.ptr_; }
+    };
+
+    template <class T>
+    class const_ptr
+    {
+        friend class allocator2<T>;
+        friend struct const_void_ptr;
+
+        T const* ptr_;
+
+        const_ptr(T const* ptr) : ptr_(ptr) {}
+    public:
+        const_ptr() : ptr_(0) {}
+        const_ptr(ptr<T> const& x) : ptr_(x.ptr_) {}
+        explicit const_ptr(void_const_ptr const& x) : ptr_((T const*) x.ptr_) {}
+
+        T const& operator*() const { return *ptr_; }
+        T const* operator->() const { return ptr_; }
+        const_ptr& operator++() { ++ptr_; return *this; }
+        const_ptr operator++(int) { const_ptr tmp(*this); ++ptr_; return tmp; }
+        const_ptr operator+(std::ptrdiff_t s) const
+            { return const_ptr(ptr_ + s); }
+        friend const_ptr operator+(std::ptrdiff_t s, const_ptr p)
+            { return ptr<T>(s + p.ptr_); }
+        T const& operator[](int s) const { return ptr_[s]; }
+        bool operator!() const { return !ptr_; }
+        operator bool() const { return !!ptr_; }
+
+        bool operator==(const_ptr const& x) const { return ptr_ == x.ptr_; }
+        bool operator!=(const_ptr const& x) const { return ptr_ != x.ptr_; }
+        bool operator<(const_ptr const& x) const { return ptr_ < x.ptr_; }
+        bool operator>(const_ptr const& x) const { return ptr_ > x.ptr_; }
+        bool operator<=(const_ptr const& x) const { return ptr_ <= x.ptr_; }
+        bool operator>=(const_ptr const& x) const { return ptr_ >= x.ptr_; }
+    };
+
     template <class T>
     class allocator2
     {
@@ -285,8 +405,10 @@
     public:
         typedef std::size_t size_type;
         typedef std::ptrdiff_t difference_type;
-        typedef T* pointer;
-        typedef T const* const_pointer;
+        typedef void_ptr void_pointer;
+        typedef void_const_ptr const_void_pointer;
+        typedef ptr<T> pointer;
+        typedef const_ptr<T> const_pointer;
         typedef T& reference;
         typedef T const& const_reference;
         typedef T value_type;
@@ -326,9 +448,9 @@
         }
 
         pointer allocate(size_type n) {
-            pointer ptr(static_cast<T*>(::operator new(n * sizeof(T))));
-            detail::tracker.track_allocate((void*) ptr, n, sizeof(T), tag_);
-            return ptr;
+            pointer p(static_cast<T*>(::operator new(n * sizeof(T))));
+            detail::tracker.track_allocate((void*) p.ptr_, n, sizeof(T), tag_);
+            return p;
         }
 
         pointer allocate(size_type n, void const* u)
@@ -340,8 +462,8 @@
 
         void deallocate(pointer p, size_type n)
         {
-            detail::tracker.track_deallocate((void*) p, n, sizeof(T), tag_);
-            ::operator delete((void*) p);
+            detail::tracker.track_deallocate((void*) p.ptr_, n, sizeof(T), tag_);
+            ::operator delete((void*) p.ptr_);
         }
 
         void construct(T* p, T const& t) {

Modified: branches/release/libs/unordered/test/unordered/insert_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/insert_tests.cpp	(original)
+++ branches/release/libs/unordered/test/unordered/insert_tests.cpp	2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -229,6 +229,24 @@
         test::check_equivalent_keys(x);
     }
 
+    std::cerr<<"insert range with rehash tests.\n";
+
+    {
+        test::check_instances check_;
+
+        X x;
+
+        test::random_values<X> v(1000, generator);
+
+        x.insert(*v.begin());
+        x.clear();
+
+        x.insert(v.begin(), v.end());
+
+        test::check_container(x, v);
+        test::check_equivalent_keys(x);
+    }
+
     std::cerr<<"insert input iterator range tests.\n";
 
     {