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

Subject: [Boost-commit] svn:boost r52393 - in trunk: boost/unordered/detail libs/unordered/test/unordered
From: daniel_james_at_[hidden]
Date: 2009-04-14 13:23:38

Author: danieljames
Date: 2009-04-14 13:23:37 EDT (Tue, 14 Apr 2009)
New Revision: 52393
URL: http://svn.boost.org/trac/boost/changeset/52393

Log:
Implement full extract_key for compilers without SFINAE and variadic
templates.
Text files modified: 
   trunk/boost/unordered/detail/hash_table.hpp                    |    10 +--                                     
   trunk/boost/unordered/detail/hash_table_impl.hpp               |   100 ++++++++++++++++++++++++++++++--------- 
   trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp |     2                                         
   3 files changed, 82 insertions(+), 30 deletions(-)

Modified: trunk/boost/unordered/detail/hash_table.hpp
==============================================================================
--- trunk/boost/unordered/detail/hash_table.hpp	(original)
+++ trunk/boost/unordered/detail/hash_table.hpp	2009-04-14 13:23:37 EDT (Tue, 14 Apr 2009)
@@ -28,20 +28,16 @@
 #include <boost/type_traits/is_same.hpp>
 #include <boost/type_traits/aligned_storage.hpp>
 #include <boost/type_traits/alignment_of.hpp>
+#include <boost/type_traits/remove_reference.hpp>
+#include <boost/type_traits/remove_const.hpp>
 #include <boost/mpl/if.hpp>
 #include <boost/mpl/and.hpp>
+#include <boost/mpl/not.hpp>
 #include <boost/detail/workaround.hpp>
 #include <boost/utility/swap.hpp>
 
 #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: 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	2009-04-14 13:23:37 EDT (Tue, 14 Apr 2009)
@@ -1428,7 +1428,18 @@
 
             // key extractors
 
+            struct no_key {
+                no_key() {}
+                template <class T> no_key(T const&) {}
+            };
+
             // no throw
+            
+            static no_key extract_key()
+            {
+                return no_key();
+            }
+            
             static key_type const& extract_key(value_type const& v)
             {
                 return extract(v, (type_wrapper<value_type>*)0);
@@ -1445,40 +1456,46 @@
             {
                 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&...)
+            
+            template <typename Arg>
+            static BOOST_DEDUCED_TYPENAME
+                boost::mpl::if_<boost::is_same<Arg, key_type>, key_type const&, no_key>::type
+                extract_key(Arg const& k)
             {
                 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)
+            static BOOST_DEDUCED_TYPENAME
+                boost::mpl::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 const&, no_key
+                >::type extract_key(std::pair<First, Second> const& v)
             {
                 return v.first;
             }
 
-            template <typename... Args>
-            static no_key extract_key(Args const&...)
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+
+            template <typename Arg, typename... Args>
+            static BOOST_DEDUCED_TYPENAME
+                boost::mpl::if_<
+                    boost::mpl::and_<
+                        boost::mpl::not_<boost::is_same<value_type, key_type> >,
+                        boost::is_same<Arg, key_type>
+                    >,
+                    key_type const&, no_key
+                >::type extract_key(Arg const& k, Args const&...)
             {
-                return no_key();
+                return k;
             }
+
 #endif
 
         public:
@@ -1964,6 +1981,13 @@
             template <typename InputIterator>
             void insert_range(InputIterator i, InputIterator j)
             {
+                if(i != j)
+                    return insert_range_impl(extract_key(*i), i, j);
+            }
+            
+            template <typename InputIterator>
+            void insert_range_impl(key_type const&, InputIterator i, InputIterator j)
+            {
                 node_constructor a(data_.allocators_);
 
                 for (; i != j; ++i) {
@@ -1992,6 +2016,36 @@
                     }
                 }
             }
+
+            template <typename InputIterator>
+            void insert_range_impl(no_key, InputIterator i, InputIterator j)
+            {
+                node_constructor a(data_.allocators_);
+
+                for (; i != j; ++i) {
+                    // No side effects in this initial code
+                    a.construct(*i);
+                    key_type const& k = extract_key(a.get()->value());
+                    size_type hash_value = hash_function()(extract_key(k));
+                    bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
+                    link_ptr pos = find_iterator(bucket, k);
+
+                    if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+                        // Doesn't already exist, add to bucket.
+                        // Side effects only in this block.
+
+                        // reserve has basic exception safety if the hash function
+                        // throws, strong otherwise.
+                        if(size() + 1 >= max_load_) {
+                            reserve_for_insert(size() + insert_size(i, j));
+                            bucket = data_.bucket_ptr_from_hash(hash_value);
+                        }
+
+                        // Nothing after this point can throw.
+                        data_.link_node_in_bucket(a, bucket);
+                    }
+                }
+            }
 #endif
         public:
 

Modified: trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp	(original)
+++ trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp	2009-04-14 13:23:37 EDT (Tue, 14 Apr 2009)
@@ -192,6 +192,8 @@
 
         // The container will have to create b copy in order to compare with
         // the existing element.
+        //
+        // Note to self: If copy_count == 0 it's an error not an optimization.
 
         reset();
         x.emplace(b, b);