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

Subject: [Boost-commit] svn:boost r80378 - trunk/boost/unordered/detail
From: dnljms_at_[hidden]
Date: 2012-09-03 16:01:51

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

Log:
Unordered: Avoid unnecessary swapping in rehash and move.
Text files modified: 
   trunk/boost/unordered/detail/buckets.hpp    |    41 ++++++++++++++++++++++++++++++--------- 
   trunk/boost/unordered/detail/equivalent.hpp |    24 ++++------------------                  
   trunk/boost/unordered/detail/table.hpp      |     7 ++---                                   
   trunk/boost/unordered/detail/unique.hpp     |    24 ++++------------------                  
   4 files changed, 44 insertions(+), 52 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:01:50 EDT (Mon, 03 Sep 2012)
@@ -684,38 +684,59 @@
         }
 
         buckets(buckets& b, boost::unordered::detail::move_tag m) :
-            buckets_(),
+            buckets_(b.buckets_),
             bucket_count_(b.bucket_count_),
-            size_(),
+            size_(b.size_),
             allocators_(b.allocators_, m)
         {
-            swap(b);
+            b.buckets_ = bucket_pointer();
+            b.size_ = 0;
         }
 
         template <typename Types>
         buckets(boost::unordered::detail::table<Types>& x,
                 boost::unordered::detail::move_tag m) :
-            buckets_(),
+            buckets_(x.buckets_),
             bucket_count_(x.bucket_count_),
-            size_(),
+            size_(x.size_),
             allocators_(x.allocators_, m)
         {
-            swap(x);
+            x.buckets_ = bucket_pointer();
+            x.size_ = 0;
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Create buckets
         // (never called in constructor to avoid exception issues)
 
-        void 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(), this->bucket_count_ + 1);
+            constructor.construct(bucket(), new_count + 1);
     
-            if (bucket::extra_node)
+            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_;
+
+                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);
+            }
+            else if (bucket::extra_node)
             {
                 node_constructor a(this->node_alloc());
                 a.construct_node();
@@ -725,6 +746,7 @@
                         a.release();
             }
 
+            this->bucket_count_ = new_count;
             this->buckets_ = constructor.release();
         }
 
@@ -755,7 +777,6 @@
             this->bucket_count_ = other.bucket_count_;
             this->size_ = other.size_;
             other.buckets_ = bucket_pointer();
-            other.bucket_count_ = 0;
             other.size_ = 0;
         }
 

Modified: trunk/boost/unordered/detail/equivalent.hpp
==============================================================================
--- trunk/boost/unordered/detail/equivalent.hpp	(original)
+++ trunk/boost/unordered/detail/equivalent.hpp	2012-09-03 16:01:50 EDT (Mon, 03 Sep 2012)
@@ -719,7 +719,7 @@
         {
             BOOST_ASSERT(!dst.buckets_);
 
-            dst.create_buckets();
+            dst.create_buckets(dst.bucket_count_);
 
             node_constructor a(dst.node_alloc());
 
@@ -766,7 +766,7 @@
         {
             BOOST_ASSERT(!dst.buckets_);
 
-            dst.create_buckets();
+            dst.create_buckets(dst.bucket_count_);
 
             node_constructor a(dst.node_alloc());
 
@@ -808,26 +808,12 @@
         {
             BOOST_ASSERT(this->size_);
 
-            buckets dst(this->node_alloc(), num_buckets);
-            dst.create_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.

Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp	(original)
+++ trunk/boost/unordered/detail/table.hpp	2012-09-03 16:01:50 EDT (Mon, 03 Sep 2012)
@@ -196,7 +196,7 @@
             max_load_(x.max_load_)
         {
             if(a == x.node_alloc()) {
-                this->buckets::swap(x, false_type());
+                this->move_buckets_from(x);
             }
             else if(x.size_) {
                 // Use a temporary table because move_buckets_to leaves the
@@ -403,9 +403,8 @@
     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->create_buckets((std::max)(this->bucket_count_,
+                this->min_buckets_for_size(size)));
             this->max_load_ = this->calculate_max_load();
         }
         // According to the standard this should be 'size >= max_load_',

Modified: trunk/boost/unordered/detail/unique.hpp
==============================================================================
--- trunk/boost/unordered/detail/unique.hpp	(original)
+++ trunk/boost/unordered/detail/unique.hpp	2012-09-03 16:01:50 EDT (Mon, 03 Sep 2012)
@@ -626,7 +626,7 @@
         {
             BOOST_ASSERT(!dst.buckets_);
 
-            dst.create_buckets();
+            dst.create_buckets(dst.bucket_count_);
 
             node_constructor a(dst.node_alloc());
 
@@ -657,7 +657,7 @@
         {
             BOOST_ASSERT(!dst.buckets_);
 
-            dst.create_buckets();
+            dst.create_buckets(dst.bucket_count_);
 
             node_constructor a(dst.node_alloc());
 
@@ -683,24 +683,10 @@
         {
             BOOST_ASSERT(this->size_);
 
-            buckets dst(this->node_alloc(), num_buckets);
-            dst.create_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.