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);