[Boost-commit] svn:boost r80380 - trunk/boost/unordered/detail

Subject: [Boost-commit] svn:boost r80380 - trunk/boost/unordered/detail
From: dnljms_at_[hidden]
Date: 2012-09-03 16:02:32

Author: danieljames
Date: 2012-09-03 16:02:31 EDT (Mon, 03 Sep 2012)
New Revision: 80380
URL: http://svn.boost.org/trac/boost/changeset/80380

Log:
Unordered: Faster assign implementation
Text files modified: 
   trunk/boost/unordered/detail/buckets.hpp |   123 +++++++++++++++++++++++++++++++++       
   trunk/boost/unordered/detail/table.hpp   |   144 +++++++++++++++++++++++++++++++-------- 
   2 files changed, 233 insertions(+), 34 deletions(-)

Modified: trunk/boost/unordered/detail/buckets.hpp
==============================================================================
--- trunk/boost/unordered/detail/buckets.hpp	(original)
+++ trunk/boost/unordered/detail/buckets.hpp	2012-09-03 16:02:31 EDT (Mon, 03 Sep 2012)
@@ -51,7 +51,12 @@
         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_;
@@ -97,6 +102,7 @@
         // no throw
         node_pointer release()
         {
+            BOOST_ASSERT(node_ && node_constructed_);
             node_pointer p = node_;
             node_ = node_pointer();
             return p;
@@ -153,6 +159,114 @@
 
     ///////////////////////////////////////////////////////////////////
     //
+    // Node Holder
+    //
+    // Temporary store for nodes. Deletes any that aren't used.
+
+    template <typename NodeAlloc>
+    struct node_holder : private node_constructor<NodeAlloc>
+    {
+    private:
+        typedef node_constructor<NodeAlloc> base;
+
+        typedef NodeAlloc node_allocator;
+        typedef boost::unordered::detail::allocator_traits<NodeAlloc>
+            node_allocator_traits;
+        typedef typename node_allocator_traits::value_type node;
+        typedef typename node_allocator_traits::pointer node_pointer;
+        typedef typename node::value_type value_type;
+        typedef typename node::link_pointer link_pointer;
+
+        node_pointer nodes_;
+
+    public:
+
+        template <typename Buckets>
+        explicit node_holder(Buckets& b) :
+            base(b.node_alloc()),
+            nodes_()
+        {
+            typename Buckets::previous_pointer prev = b.get_previous_start();
+            nodes_ = static_cast<node_pointer>(prev->next_);
+            prev->next_ = link_pointer();
+            b.size_ = 0;
+        }
+
+        ~node_holder();
+
+        template <typename T>
+        inline void assign_impl(T const& v) {
+            nodes_->value() = v;
+        }
+
+        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;
+        }
+
+        template <typename T>
+        inline void move_assign_impl(T& v) {
+            nodes_->value() = boost::move(v);
+        }
+
+        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);
+        }
+
+        node_pointer copy_of(value_type const& v)
+        {
+            if (nodes_) {
+                assign_impl(v);
+                node_pointer p = nodes_;
+                nodes_ = static_cast<node_pointer>(p->next_);
+                p->next_ = link_pointer();
+                return p;
+            }
+            else {
+                this->construct_node();
+                this->construct_value2(v);
+                return base::release();
+            }
+        }
+
+        node_pointer move_copy_of(value_type& v)
+        {
+            if (nodes_) {
+                move_assign_impl(v);
+                node_pointer p = nodes_;
+                nodes_ = static_cast<node_pointer>(p->next_);
+                p->next_ = link_pointer();
+                return p;
+            }
+            else {
+                this->construct_node();
+                this->construct_value2(boost::move(v));
+                return base::release();
+            }
+        }
+    };
+
+    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);
+        }
+    }
+
+    ///////////////////////////////////////////////////////////////////
+    //
     // Bucket
 
     template <typename NodePointer>
@@ -860,13 +974,18 @@
                 delete_node(iterator(n));
             }
 
+            clear_buckets();
+
+            BOOST_ASSERT(!this->size_);
+        }
+
+        void clear_buckets()
+        {
             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_);
         }
 
         // This is called after erasing a node or group of nodes to fix up

Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp	(original)
+++ trunk/boost/unordered/detail/table.hpp	2012-09-03 16:02:31 EDT (Mon, 03 Sep 2012)
@@ -92,6 +92,33 @@
         }
     };
 
+    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 :
@@ -264,35 +291,84 @@
 
         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_;
+            this->max_load_ = this->calculate_max_load();
+
+            if (!this->size_ && !x.size_) return;
+
+            if (!this->buckets_ || x.size_ >= this->max_load_) {
+                this->create_buckets(min_buckets_for_size(x.size_));
+                this->max_load_ = this->calculate_max_load();
+            }
+            else {
+                this->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 (this->node_alloc() == x.node_alloc()) {
+                this->allocators_.assign(x.allocators_);
+                this->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 (this->buckets_) this->delete_buckets();
+                this->allocators_.assign(x.allocators_);
+
+                // Copy over other data, all no throw.
+                new_func_this.commit();
+                this->mlf_ = x.mlf_;
+                this->bucket_count_ = this->min_buckets_for_size(x.size_);
+                this->max_load_ = 0;
+
+                // Finally copy the elements.
+                if (x.size_) {
+                    this->create_buckets(this->bucket_count_);
+                    copy_nodes<node_allocator> copy(this->node_alloc());
+                    table_impl::fill_buckets(x.get_start(), *this, copy);
+                    this->max_load_ = this->calculate_max_load();
+                }
+            }
         }
 
         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)
@@ -304,32 +380,36 @@
 
         void move_assign(table& x, false_type)
         {
-            if(this->node_alloc() == x.node_alloc()) {
+            if (this->node_alloc() == x.node_alloc()) {
                 if(this->buckets_) this->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_;
+                this->max_load_ = this->calculate_max_load();
 
-                if (x.size_) {
-                    buckets b(this->node_alloc(),
-                        x.min_buckets_for_size(x.size_));
-                    buckets tmp(x, move_tag());
-
-                    b.create_buckets(b.bucket_count_);
-                    move_nodes<node_allocator> move(b.node_alloc());
-                    table_impl::fill_buckets(tmp.get_start(), b, move);
+                if (!this->size_ && !x.size_) return;
 
-                    b.swap(*this);
+                if (!this->buckets_ || x.size_ >= max_load_) {
+                    this->create_buckets(min_buckets_for_size(x.size_));
+                    this->max_load_ = this->calculate_max_load();
                 }
                 else {
-                    this->clear();
+                    this->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();
             }
         }