[Boost-commit] svn:boost r44486 - in trunk: . boost boost/unordered/detail libs/unordered/test/unordered

From: daniel_james_at_[hidden]
Date: 2008-04-17 03:34:15

Author: danieljames
Date: 2008-04-17 03:34:15 EDT (Thu, 17 Apr 2008)
New Revision: 44486
URL: http://svn.boost.org/trac/boost/changeset/44486

Log:
Movable unordered containers, full support only for compilers with rvalue references.

Merged revisions 44076-44414 via svnmerge from 
https://svn.boost.org/svn/boost/branches/unordered/trunk

........
  r44076 | danieljames | 2008-04-06 20:41:19 +0100 (Sun, 06 Apr 2008) | 1 line
  
  Move semantics for compilers with rvalue references.
........
  r44077 | danieljames | 2008-04-06 20:48:59 +0100 (Sun, 06 Apr 2008) | 1 line
  
  Do move assignment 'properly'.
........
  r44085 | danieljames | 2008-04-06 22:46:04 +0100 (Sun, 06 Apr 2008) | 1 line
  
  Use normal references for the move members, reset the source buckets_ pointer to stop the buckets getting deleted, and remove a superflous pointer check.
........
  r44109 | danieljames | 2008-04-07 23:49:36 +0100 (Mon, 07 Apr 2008) | 1 line
  
  Add missing tests.
........
  r44366 | danieljames | 2008-04-13 12:59:46 +0100 (Sun, 13 Apr 2008) | 1 line
  
  Avoid using rvalue references in the implementation files.
........
  r44368 | danieljames | 2008-04-13 15:13:33 +0100 (Sun, 13 Apr 2008) | 6 lines
  
  Use a cut down version of the work in progress move library to implement move
  semantics on more compilers. Unfortunately the move constructor with allocator
  isn't really practical at the moment, since in the case where the container
  can't be moved, and the allocators aren't equal it will copy the container
  twice.
........

Added:
   trunk/boost/unordered/detail/config.hpp
      - copied unchanged from r44368, /branches/unordered/trunk/boost/unordered/detail/config.hpp
   trunk/boost/unordered/detail/move.hpp
      - copied unchanged from r44368, /branches/unordered/trunk/boost/unordered/detail/move.hpp
   trunk/libs/unordered/test/unordered/move_tests.cpp
      - copied unchanged from r44368, /branches/unordered/trunk/libs/unordered/test/unordered/move_tests.cpp
Properties modified: 
   trunk/   (props changed)
Text files modified: 
   trunk/boost/unordered/detail/hash_table.hpp      |     1                                         
   trunk/boost/unordered/detail/hash_table_impl.hpp |   136 ++++++++++++++++++++++++++++++++++----- 
   trunk/boost/unordered_map.hpp                    |    63 ++++++++++++++++++                      
   trunk/boost/unordered_set.hpp                    |    62 ++++++++++++++++++                      
   trunk/libs/unordered/test/unordered/Jamfile.v2   |     1                                         
   5 files changed, 245 insertions(+), 18 deletions(-)

Modified: trunk/boost/unordered/detail/hash_table.hpp
==============================================================================
--- trunk/boost/unordered/detail/hash_table.hpp	(original)
+++ trunk/boost/unordered/detail/hash_table.hpp	2008-04-17 03:34:15 EDT (Thu, 17 Apr 2008)
@@ -121,6 +121,7 @@
         }
 #endif
 
+        struct move_tag {};
     }
 }
 

Modified: trunk/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- trunk/boost/unordered/detail/hash_table_impl.hpp	(original)
+++ trunk/boost/unordered/detail/hash_table_impl.hpp	2008-04-17 03:34:15 EDT (Thu, 17 Apr 2008)
@@ -323,22 +323,8 @@
                 buckets_(), bucket_count_(next_prime(n)),
                 cached_begin_bucket_(), size_(0)
             {
-                // The array constructor will clean up in the event of an
-                // exception.
-                allocator_array_constructor<bucket_allocator>
-                    constructor(allocators_.bucket_alloc_);
-
-                // Creates an extra bucket to act as a sentinel.
-                constructor.construct(bucket(), bucket_count_ + 1);
-
-                cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count_);
-
-                // Set up the sentinel.
-                cached_begin_bucket_->next_ = link_ptr(cached_begin_bucket_);
-
-                // Only release the buckets once everything is successfully
-                // done.
-                buckets_ = constructor.release();
+                BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
+                create_buckets();
             }
 
             BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA const& x, size_type n)
@@ -346,6 +332,44 @@
                 buckets_(), bucket_count_(next_prime(n)),
                 cached_begin_bucket_(), size_(0)
             {
+                BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
+                create_buckets();
+            }
+
+            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x, move_tag)
+                : allocators_(x.allocators_),
+                buckets_(x.buckets_), bucket_count_(x.bucket_count_),
+                cached_begin_bucket_(x.cached_begin_bucket_), size_(x.size_)
+            {
+                unordered_detail::reset(x.buckets_);
+            }
+
+            BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x,
+                    value_allocator const& a, size_type n, move_tag)
+                : allocators_(a), buckets_(), bucket_count_(),
+                cached_begin_bucket_(), size_(0)
+            {
+                if(allocators_ == x.allocators_) {
+                    buckets_ = x.buckets_;
+                    bucket_count_ = x.bucket_count_;
+                    cached_begin_bucket_ = x.cached_begin_bucket_;
+                    size_ = x.size_;
+                    unordered_detail::reset(x.buckets_);
+                }
+                else {
+                    BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
+                    bucket_count_ = next_prime(n);
+                    create_buckets();
+                }
+            }
+
+            // no throw
+            ~BOOST_UNORDERED_TABLE_DATA()
+            {
+                delete_buckets();
+            }
+
+            void create_buckets() {
                 // The array constructor will clean up in the event of an
                 // exception.
                 allocator_array_constructor<bucket_allocator>
@@ -356,7 +380,7 @@
 
                 cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count_);
 
-                // Set up the sentinel
+                // Set up the sentinel.
                 cached_begin_bucket_->next_ = link_ptr(cached_begin_bucket_);
 
                 // Only release the buckets once everything is successfully
@@ -365,7 +389,7 @@
             }
 
             // no throw
-            ~BOOST_UNORDERED_TABLE_DATA()
+            void delete_buckets()
             {
                 if(buckets_) {
                     bucket_ptr begin = cached_begin_bucket_;
@@ -400,6 +424,17 @@
                 std::swap(size_, other.size_);
             }
 
+            // no throw
+            void move(BOOST_UNORDERED_TABLE_DATA& other)
+            {
+                delete_buckets();
+                buckets_ = other.buckets_;
+                unordered_detail::reset(other.buckets_);
+                bucket_count_ = other.bucket_count_;
+                cached_begin_bucket_ = other.cached_begin_bucket_;
+                size_ = other.size_;
+            }
+
             // Return the bucket for a hashed value.
             //
             // no throw
@@ -1114,6 +1149,36 @@
                 copy_buckets(x.data_, data_, current_functions());
             }
 
+            // Move Construct
+
+            BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE& x, move_tag m)
+                : func1_(x.current_functions()), // throws
+                func2_(x.current_functions()), // throws
+                func_(&BOOST_UNORDERED_TABLE::func1_), // no throw
+                mlf_(x.mlf_), // no throw
+                data_(x.data_, m)  // throws
+            {
+                calculate_max_load(); // no throw
+            }
+
+            BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE& x,
+                    value_allocator const& a, move_tag m)
+                : func1_(x.current_functions()), // throws
+                func2_(x.current_functions()), // throws
+                func_(&BOOST_UNORDERED_TABLE::func1_), // no throw
+                mlf_(x.mlf_), // no throw
+                data_(x.data_, a,
+                        x.min_buckets_for_size(x.size()), m)  // throws
+            {
+                calculate_max_load(); // no throw
+
+                if(x.data_.buckets_) {
+                    // This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean
+                    // up.
+                    copy_buckets(x.data_, data_, current_functions());
+                }
+            }
+
             // Assign
             //
             // basic exception safety, if copy_functions of reserver throws
@@ -1185,6 +1250,41 @@
                 x.calculate_max_load();
             }
 
+            // Move
+            //
+            // ----------------------------------------------------------------
+            //
+            // Strong exception safety (might change unused function objects)
+            //
+            // Can throw if hash or predicate object's copy constructor throws
+            // or if allocators are unequal.
+
+            void move(BOOST_UNORDERED_TABLE& x)
+            {
+                // This only effects the function objects that aren't in use
+                // so it is strongly exception safe, via. double buffering.
+                functions_ptr new_func_this = copy_functions(x);       // throws
+
+                if(data_.allocators_ == x.data_.allocators_) {
+                    data_.move(x.data_); // no throw
+                }
+                else {
+                    // Create new buckets in separate HASH_TABLE_DATA objects
+                    // which will clean up if anything throws an exception.
+                    // (all can throw, but with no effect as these are new objects).
+                    data new_this(data_, x.min_buckets_for_size(x.data_.size_));
+                    copy_buckets(x.data_, new_this, this->*new_func_this);
+
+                    // Start updating the data here, no throw from now on.
+                    data_.move(new_this);
+                }
+
+                // We've made it, the rest is no throw.
+                mlf_ = x.mlf_;
+                func_ = new_func_this;
+                calculate_max_load();
+            }
+
         private:
 
             functions const& current_functions() const

Modified: trunk/boost/unordered_map.hpp
==============================================================================
--- trunk/boost/unordered_map.hpp	(original)
+++ trunk/boost/unordered_map.hpp	2008-04-17 03:34:15 EDT (Thu, 17 Apr 2008)
@@ -21,6 +21,10 @@
 #include <boost/unordered/detail/hash_table.hpp>
 #include <boost/functional/hash.hpp>
 
+#if !defined(BOOST_HAS_RVALUE_REFS)
+#include <boost/unordered/detail/move.hpp>
+#endif
+
 namespace boost
 {
     template <class Key,
@@ -100,6 +104,35 @@
         {
         }
 
+#if defined(BOOST_HAS_RVALUE_REFS)
+        unordered_map(unordered_map&& other)
+            : base(other.base, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_map(unordered_map&& other, allocator_type const& a)
+            : base(other.base, a, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_map& operator=(unordered_map&& x)
+        {
+            base.move(x.base);
+            return *this;
+        }
+#else
+        unordered_map(boost::unordered_detail::move_from<unordered_map> other)
+            : base(other.base, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_map& operator=(unordered_map x)
+        {
+            base.move(x.base);
+            return *this;
+        }
+#endif
+
     private:
 
         BOOST_DEDUCED_TYPENAME implementation::iterator_base const&
@@ -424,6 +457,36 @@
         {
         }
 
+#if defined(BOOST_HAS_RVALUE_REFS)
+        unordered_multimap(unordered_multimap&& other)
+            : base(other.base, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_multimap(unordered_multimap&& other, allocator_type const& a)
+            : base(other.base, a, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_multimap& operator=(unordered_multimap&& x)
+        {
+            base.move(x.base);
+            return *this;
+        }
+#else
+        unordered_multimap(boost::unordered_detail::move_from<unordered_multimap> other)
+            : base(other.base, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_multimap& operator=(unordered_multimap x)
+        {
+            base.move(x.base);
+            return *this;
+        }
+#endif
+
+
     private:
 
         BOOST_DEDUCED_TYPENAME implementation::iterator_base const&

Modified: trunk/boost/unordered_set.hpp
==============================================================================
--- trunk/boost/unordered_set.hpp	(original)
+++ trunk/boost/unordered_set.hpp	2008-04-17 03:34:15 EDT (Thu, 17 Apr 2008)
@@ -21,6 +21,10 @@
 #include <boost/unordered/detail/hash_table.hpp>
 #include <boost/functional/hash.hpp>
 
+#if !defined(BOOST_HAS_RVALUE_REFS)
+#include <boost/unordered/detail/move.hpp>
+#endif
+
 namespace boost
 {
     template <class Value,
@@ -97,6 +101,35 @@
         {
         }
 
+#if defined(BOOST_HAS_RVALUE_REFS)
+        unordered_set(unordered_set&& other)
+            : base(other.base, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_set(unordered_set&& other, allocator_type const& a)
+            : base(other.base, a, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_set& operator=(unordered_set&& x)
+        {
+            base.move(x.base);
+            return *this;
+        }
+#else
+        unordered_set(boost::unordered_detail::move_from<unordered_set> other)
+            : base(other.base, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_set& operator=(unordered_set x)
+        {
+            base.move(x.base);
+            return *this;
+        }
+#endif
+
     private:
 
         BOOST_DEDUCED_TYPENAME implementation::iterator_base const&
@@ -392,6 +425,35 @@
         {
         }
 
+#if defined(BOOST_HAS_RVALUE_REFS)
+        unordered_multiset(unordered_multiset&& other)
+            : base(other.base, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_multiset(unordered_multiset&& other, allocator_type const& a)
+            : base(other.base, a, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_multiset& operator=(unordered_multiset&& x)
+        {
+            base.move(x.base);
+            return *this;
+        }
+#else
+        unordered_multiset(boost::unordered_detail::move_from<unordered_multiset> other)
+            : base(other.base, boost::unordered_detail::move_tag())
+        {
+        }
+
+        unordered_multiset& operator=(unordered_multiset x)
+        {
+            base.move(x.base);
+            return *this;
+        }
+#endif
+
     private:
 
         BOOST_DEDUCED_TYPENAME implementation::iterator_base const&

Modified: trunk/libs/unordered/test/unordered/Jamfile.v2
==============================================================================
--- trunk/libs/unordered/test/unordered/Jamfile.v2	(original)
+++ trunk/libs/unordered/test/unordered/Jamfile.v2	2008-04-17 03:34:15 EDT (Thu, 17 Apr 2008)
@@ -21,6 +21,7 @@
         [ run equivalent_keys_tests.cpp ]
         [ run constructor_tests.cpp ]
         [ run copy_tests.cpp ]
+        [ run move_tests.cpp ]
         [ run assign_tests.cpp ]
         [ run insert_tests.cpp ]
         [ run insert_stable_tests.cpp ]