[Boost-commit] svn:boost r44737 - in branches/unordered/trunk: boost/unordered/detail libs/unordered/test/unordered

From: daniel_james_at_[hidden]
Date: 2008-04-23 02:56:35

Author: danieljames
Date: 2008-04-23 02:56:35 EDT (Wed, 23 Apr 2008)
New Revision: 44737
URL: http://svn.boost.org/trac/boost/changeset/44737

Log:
Avoid creating unnecessary copies in unordered_set::emplace and unordered_map::emplace.

Text files modified: 
   branches/unordered/trunk/boost/unordered/detail/hash_table.hpp                    |     7 +++                                     
   branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp               |    79 ++++++++++++++++++++++++++++++++++++++++
   branches/unordered/trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp |    11 ++++-                                   
   3 files changed, 95 insertions(+), 2 deletions(-)

Modified: branches/unordered/trunk/boost/unordered/detail/hash_table.hpp
==============================================================================
--- branches/unordered/trunk/boost/unordered/detail/hash_table.hpp	(original)
+++ branches/unordered/trunk/boost/unordered/detail/hash_table.hpp	2008-04-23 02:56:35 EDT (Wed, 23 Apr 2008)
@@ -32,6 +32,13 @@
 
 #include <boost/mpl/aux_/config/eti.hpp>
 
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+#include <boost/type_traits/remove_reference.hpp>
+#include <boost/type_traits/remove_const.hpp>
+#include <boost/utility/enable_if.hpp>
+#include <boost/mpl/not.hpp>
+#endif
+
 #if BOOST_WORKAROUND(__BORLANDC__, <= 0x0582)
 #define BOOST_UNORDERED_BORLAND_BOOL(x) (bool)(x)
 #else

Modified: branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp	(original)
+++ branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp	2008-04-23 02:56:35 EDT (Wed, 23 Apr 2008)
@@ -1527,6 +1527,41 @@
                 return v.first;
             }
 
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+            struct no_key {};
+
+            template <typename Arg1, typename... Args>
+            static typename boost::enable_if<
+                boost::mpl::and_<
+                    boost::mpl::not_<boost::is_same<key_type, value_type> >,
+                    boost::is_same<Arg1, key_type>
+                >,
+                key_type>::type const& extract_key(Arg1 const& k, Args const&...)
+            {
+                return k;
+            }
+
+            template <typename First, typename Second>
+            static typename boost::enable_if<
+                boost::mpl::and_<
+                    boost::mpl::not_<boost::is_same<key_type, value_type> >,
+                    boost::is_same<key_type,
+                        typename boost::remove_const<
+                            typename boost::remove_reference<First>::type
+                        >::type>
+                >,
+                key_type>::type const& extract_key(std::pair<First, Second> const& v)
+            {
+                return v.first;
+            }
+
+            template <typename... Args>
+            static no_key extract_key(Args const&...)
+            {
+                return no_key();
+            }
+#endif
+
         public:
 
             // if hash function throws, basic exception safety
@@ -1892,6 +1927,50 @@
             template<typename... Args>
             std::pair<iterator_base, bool> insert(Args&&... args)
             {
+                return insert_impl(
+                    extract_key(std::forward<Args>(args)...),
+                    std::forward<Args>(args)...);
+            }
+
+            template<typename... Args>
+            std::pair<iterator_base, bool> insert_impl(key_type const& k, Args&&... args)
+            {
+                // No side effects in this initial code
+                size_type hash_value = hash_function()(k);
+                bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
+                link_ptr pos = find_iterator(bucket, k);
+
+                if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+                    // Found an existing key, return it (no throw).
+                    return std::pair<iterator_base, bool>(
+                        iterator_base(bucket, pos), false);
+
+                } else {
+                    // Doesn't already exist, add to bucket.
+                    // Side effects only in this block.
+
+                    // Create the node before rehashing in case it throws an
+                    // exception (need strong safety in such a case).
+                    node_constructor a(data_.allocators_);
+                    a.construct(std::forward<Args>(args)...);
+
+                    // reserve has basic exception safety if the hash function
+                    // throws, strong otherwise.
+                    if(reserve(size() + 1))
+                        bucket = data_.bucket_ptr_from_hash(hash_value);
+
+                    // Nothing after this point can throw.
+
+                    link_ptr n = data_.link_node_in_bucket(a, bucket);
+
+                    return std::pair<iterator_base, bool>(
+                        iterator_base(bucket, n), true);
+                }
+            }
+
+            template<typename... Args>
+            std::pair<iterator_base, bool> insert_impl(no_key, Args&&... args)
+            {
                 // Construct the node regardless - in order to get the key.
                 // It will be discarded if it isn't used
                 node_constructor a(data_.allocators_);

Modified: branches/unordered/trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp	(original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp	2008-04-23 02:56:35 EDT (Wed, 23 Apr 2008)
@@ -219,6 +219,12 @@
         x.emplace(source<std::pair<count_copies, count_copies> >());
         COPY_COUNT(2); MOVE_COUNT(0);
 
+        count_copies part;
+        reset();
+        std::pair<count_copies const&, count_copies const&> a_ref(part, part);
+        x.emplace(a_ref);
+        COPY_COUNT(0); MOVE_COUNT(0);
+
         // No move should take place.
         reset();
         x.emplace(std::move(a));
@@ -238,15 +244,16 @@
 
         reset();
         x.emplace(b.first, b.second);
-        COPY_COUNT(2); MOVE_COUNT(0);
+        COPY_COUNT(0); MOVE_COUNT(0);
 
         reset();
         x.emplace(source<count_copies>(), source<count_copies>());
         COPY_COUNT(2); MOVE_COUNT(0);
 
+        // source<count_copies> creates a single copy.
         reset();
         x.emplace(b.first, source<count_copies>());
-        COPY_COUNT(2); MOVE_COUNT(0);
+        COPY_COUNT(1); MOVE_COUNT(0);
 
         reset();
         x.emplace(b.first.tag_, b.second.tag_);