|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r52862 - in sandbox/move: boost/unordered boost/unordered/detail libs/unordered/test/unordered
From: daniel_james_at_[hidden]
Date: 2009-05-09 15:17:47
Author: danieljames
Date: 2009-05-09 15:17:46 EDT (Sat, 09 May 2009)
New Revision: 52862
URL: http://svn.boost.org/trac/boost/changeset/52862
Log:
Implement emplace for compilers without C++0x features.
Text files modified:
sandbox/move/boost/unordered/detail/hash_table.hpp | 18 +
sandbox/move/boost/unordered/detail/hash_table_impl.hpp | 431 ++++++++++++++++++++++++++++++---------
sandbox/move/boost/unordered/unordered_map.hpp | 91 ++++++++
sandbox/move/boost/unordered/unordered_set.hpp | 90 ++++++++
sandbox/move/libs/unordered/test/unordered/compile_tests.hpp | 8
sandbox/move/libs/unordered/test/unordered/unnecessary_copy_tests.cpp | 138 +++++++++--
6 files changed, 626 insertions(+), 150 deletions(-)
Modified: sandbox/move/boost/unordered/detail/hash_table.hpp
==============================================================================
--- sandbox/move/boost/unordered/detail/hash_table.hpp (original)
+++ sandbox/move/boost/unordered/detail/hash_table.hpp 2009-05-09 15:17:46 EDT (Sat, 09 May 2009)
@@ -13,6 +13,10 @@
#include <boost/config.hpp>
+#if !defined(BOOST_UNORDERED_EMPLACE_LIMIT)
+#define BOOST_UNORDERED_EMPLACE_LIMIT 5
+#endif
+
#include <cstddef>
#include <boost/config/no_tr1/cmath.hpp>
#include <algorithm>
@@ -32,14 +36,28 @@
#include <boost/type_traits/remove_const.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/and.hpp>
+#include <boost/mpl/or.hpp>
#include <boost/mpl/not.hpp>
#include <boost/detail/workaround.hpp>
#include <boost/utility/swap.hpp>
#include <boost/preprocessor/seq/size.hpp>
#include <boost/preprocessor/seq/enum.hpp>
+#include <boost/move/move.hpp>
#include <boost/mpl/aux_/config/eti.hpp>
+#if !(defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL))
+
+#include <boost/preprocessor/cat.hpp>
+#include <boost/preprocessor/repetition/enum.hpp>
+#include <boost/preprocessor/repetition/enum_params.hpp>
+#include <boost/preprocessor/repetition/repeat_from_to.hpp>
+
+#define BOOST_UNORDERED_PARAMS_FWD_REF(z, n, data) BOOST_FWD_REF(Arg##n) arg##n
+#define BOOST_UNORDERED_PARAMS_FORWARD(z, n, data) boost::forward<Arg##n>(arg##n)
+
+#endif
+
#if BOOST_WORKAROUND(__BORLANDC__, <= 0x0582)
#define BOOST_UNORDERED_BORLAND_BOOL(x) (bool)(x)
#else
Modified: sandbox/move/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- sandbox/move/boost/unordered/detail/hash_table_impl.hpp (original)
+++ sandbox/move/boost/unordered/detail/hash_table_impl.hpp 2009-05-09 15:17:46 EDT (Sat, 09 May 2009)
@@ -183,15 +183,19 @@
void construct_preamble()
{
- BOOST_ASSERT(!node_);
- node_constructed_ = false;
- value_constructed_ = false;
-
- node_ = allocators_.node_alloc_.allocate(1);
-
- allocators_.node_alloc_.construct(node_, node());
- node_constructed_ = true;
-
+ if(!node_) {
+ node_constructed_ = false;
+ value_constructed_ = false;
+
+ node_ = allocators_.node_alloc_.allocate(1);
+ allocators_.node_alloc_.construct(node_, node());
+ node_constructed_ = true;
+ }
+ else {
+ BOOST_ASSERT(node_constructed_ && value_constructed_);
+ BOOST_UNORDERED_DESTRUCT(&node_->value(), value_type);
+ value_constructed_ = false;
+ }
}
#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
@@ -202,32 +206,143 @@
new(node_->address()) value_type(std::forward<Args>(args)...);
value_constructed_ = true;
}
-#else
- template <typename V>
- void construct(V const& v)
+
+#if defined(__GLIBCPP__) || defined(__GLIBCXX__)
+ // The GCC C++0x standard library implementation does not have
+ // a single argument pair constructor, so this works around that.
+
+ template <typename Arg>
+ void construct(Arg&& arg)
{
construct_preamble();
- new(node_->address()) value_type(v);
+ construct_impl(std::forward<Arg>(arg),
+ (value_type const*) 0,
+ (typename boost::remove_reference<Arg>::type const*) 0);
value_constructed_ = true;
}
-#endif
- template <typename K, typename M>
- void construct_pair(K const& k, M*)
+ template <
+ typename Arg,
+ typename ValueType,
+ typename Type>
+ void construct_impl(Arg&& arg, ValueType const*, Type const*)
{
- BOOST_ASSERT(!node_);
- node_constructed_ = false;
- value_constructed_ = false;
+ new(node_->address()) value_type(std::forward<Arg>(arg));
+ }
- node_ = allocators_.node_alloc_.allocate(1);
+ template <
+ typename Arg,
+ typename ValueFirst, typename ValueSecond,
+ typename TypeFirst, typename TypeSecond>
+ void construct_impl(
+ Arg&& arg,
+ std::pair<ValueFirst, ValueSecond> const*,
+ std::pair<TypeFirst, TypeSecond> const*)
+ {
+ new(node_->address()) value_type(std::forward<Arg>(arg));
+ }
- allocators_.node_alloc_.construct(node_, node());
- node_constructed_ = true;
+ template <
+ typename Arg,
+ typename ValueFirst, typename ValueSecond,
+ typename Type>
+ void construct_impl(
+ Arg&& arg,
+ std::pair<ValueFirst, ValueSecond> const*,
+ Type const*)
+ {
+ new(node_->address()) value_type(std::forward<Arg>(arg), ValueSecond());
+ }
+#endif
+
+#else
- new(node_->address()) value_type(k, M());
+ void construct()
+ {
+ construct_preamble();
+ new(node_->address()) value_type;
value_constructed_ = true;
}
+#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, n, _) \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ void construct( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ construct_preamble(); \
+ construct_impl( \
+ (value_type*) 0, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ ); \
+ value_constructed_ = true; \
+ } \
+ \
+ template < \
+ typename T, \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ void construct_impl( \
+ T*, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ new(node_->address()) value_type( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ ); \
+ } \
+ \
+
+#define BOOST_UNORDERED_CONSTRUCT_IMPL2(z, n, _) \
+ template <typename First, typename Second, typename Key, \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ void construct_impl( \
+ std::pair<First, Second>*, \
+ BOOST_FWD_REF(Key) k, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ new(node_->address()) value_type(boost::forward<Key>(k), \
+ Second( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ ) \
+ ); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_CONSTRUCT_IMPL, _)
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_CONSTRUCT_IMPL2, _)
+
+ template <typename First, typename Second, typename T1, typename T2>
+ void construct_impl(std::pair<First, Second>*,
+ std::pair<T1, T2> const& arg0)
+ {
+ new(node_->address()) value_type(arg0);
+ }
+
+ template <typename First, typename Second, typename T1, typename T2>
+ void construct_impl(std::pair<First, Second>*,
+ BOOST_RV_REF_2_TEMPL_ARGS(std::pair, T1, T2) arg0)
+ {
+ new(node_->address()) value_type(
+ boost::forward<BOOST_RV_REF_2_TEMPL_ARGS(std::pair, T1, T2)>(arg0));
+ }
+
+ template <typename First, typename Second, typename Key>
+ void construct_impl(std::pair<First, Second>*, BOOST_FWD_REF(Key) k)
+ {
+ First f(boost::forward<Key>(k));
+ new(node_->address()) value_type(f, Second());
+ }
+
+#undef BOOST_UNORDERED_CONSTRUCT_IMPL
+
+#endif
+
node_ptr get() const
{
BOOST_ASSERT(node_);
@@ -1424,19 +1539,29 @@
}
// key extractors
+ //
+ // no throw
+ //
+ // 'extract_key' is called with the emplace parameters to return a
+ // key if available or 'no_key' is one isn't and will need to be
+ // constructed.
struct no_key {
no_key() {}
template <class T> no_key(T const&) {}
};
- // no throw
-
+
+ // If emplace is called with no arguments then there obviously
+ // isn't an available key.
+
static no_key extract_key()
{
return no_key();
}
+ // Emplace or insert was called with the value type.
+
static key_type const& extract_key(value_type const& v)
{
return extract(v, (type_wrapper<value_type>*)0);
@@ -1454,6 +1579,9 @@
return v.first;
}
+ // For maps, if emplace is called with just a key, then it's the value type
+ // with the second value default initialised.
+
template <typename Arg>
static BOOST_DEDUCED_TYPENAME
boost::mpl::if_<boost::is_same<Arg, key_type>, key_type const&, no_key>::type
@@ -1462,6 +1590,9 @@
return k;
}
+ // For a map, the argument might be a pair with the key as the first
+ // part and a convertible value as the second part.
+
template <typename First, typename Second>
static BOOST_DEDUCED_TYPENAME
boost::mpl::if_<
@@ -1478,9 +1609,43 @@
return v.first;
}
+ // If we're using move emulation then a special case is needed for
+ // moved values.
+
+#if !defined(BOOST_HAS_RVALUE_REFS)
+
+ template <typename Arg>
+ static BOOST_DEDUCED_TYPENAME
+ boost::mpl::if_<
+ mpl::or_<
+ boost::is_same<Arg, key_type>,
+ boost::is_same<Arg, value_type>
+ >, key_type const&, no_key>::type
+ extract_key(BOOST_RV_REF(Arg) k)
+ {
+ return extract_key(static_cast<Arg const&>(k));
+ }
+
+#endif
+
+ // For maps if there is more than one argument, the key can be the first argument.
+
#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template <typename Arg, typename Arg1, 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, Arg1 const&, Args const&...)
+ {
+ return k;
+ }
- template <typename Arg, typename... Args>
+#else
+ template <typename Arg, typename Arg1>
static BOOST_DEDUCED_TYPENAME
boost::mpl::if_<
boost::mpl::and_<
@@ -1488,11 +1653,24 @@
boost::is_same<Arg, key_type>
>,
key_type const&, no_key
- >::type extract_key(Arg const& k, Args const&...)
+ >::type extract_key(Arg const& k, Arg1 const&)
{
return k;
}
+ template <typename Arg, typename Arg1>
+ 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(BOOST_RV_REF(Arg) k, Arg1 const&)
+ {
+ return static_cast<Arg const&>(k);
+ }
+
#endif
public:
@@ -1632,34 +1810,39 @@
#else
- // Emplace (equivalent key containers)
-
- // if hash function throws, basic exception safety
- // strong otherwise
- iterator_base emplace(value_type const& v)
- {
- // 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(v);
-
- return emplace_impl(a);
+#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ iterator_base emplace( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ node_constructor a(data_.allocators_); \
+ a.construct( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ ); \
+ return emplace_impl(a); \
+ } \
+ \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ iterator_base emplace_hint(iterator_base const& it, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ node_constructor a(data_.allocators_); \
+ a.construct( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ ); \
+ return emplace_hint_impl(it, a); \
}
- // Emplace (equivalent key containers)
-
- // if hash function throws, basic exception safety
- // strong otherwise
- iterator_base emplace_hint(iterator_base const& it, value_type const& v)
- {
- // 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(v);
-
- return emplace_hint_impl(it, a);
- }
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_INSERT_IMPL, _)
+#undef BOOST_UNORDERED_INSERT_IMPL
#endif
iterator_base emplace_impl(node_constructor& a)
@@ -1788,7 +1971,7 @@
// 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_pair(k, (mapped_type*) 0);
+ a.construct(k);
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
@@ -1805,10 +1988,6 @@
// Emplace (unique keys)
// (I'm using an overloaded emplace for both 'insert' and 'emplace')
- //
- // TODO:
- // For sets: create a local key without creating the node?
- // For maps: use the first argument as the key.
// if hash function throws, basic exception safety
// strong otherwise
@@ -1831,7 +2010,7 @@
{
return emplace_impl(
extract_key(std::forward<Args>(args)...),
- std::forward<Args>(args)...);
+ std::forward<Args>(args)...).first;
}
template<typename... Args>
@@ -1878,59 +2057,97 @@
return emplace_impl_with_node(a);
}
#else
-
- // Emplace (unique keys)
-
- // if hash function throws, basic exception safety
- // strong otherwise
- std::pair<iterator_base, bool> emplace(value_type const& v)
+ template <typename Arg0>
+ std::pair<iterator_base, bool> emplace(BOOST_FWD_REF(Arg0) arg0)
{
- // No side effects in this initial code
- key_type const& k = extract_key(v);
- 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(v);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(reserve_for_insert(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);
- }
+ return emplace_impl(extract_key(arg0), arg0);
}
- // Emplace (unique keys)
-
- // if hash function throws, basic exception safety
- // strong otherwise
- iterator_base emplace_hint(iterator_base const& it, value_type const& v)
+ template <typename Arg0>
+ iterator_base emplace_hint(iterator_base const& it, BOOST_FWD_REF(Arg0) arg0)
{
- if(it != data_.end() && equal(extract_key(v), *it))
- return it;
- else
- return emplace(v).first;
+ return emplace_impl(extract_key(arg0), arg0).first;
+ }
+
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ std::pair<iterator_base, bool> emplace( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ return emplace_impl( \
+ extract_key(arg0, arg1), \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ ); \
+ } \
+ \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ iterator_base emplace_hint(iterator_base const& it, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ return emplace_impl( \
+ extract_key(arg0, arg1), \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ ).first; \
+ } \
+ BOOST_UNORDERED_INSERT_IMPL2(z, n, _)
+
+#define BOOST_UNORDERED_INSERT_IMPL2(z, n, _) \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ std::pair<iterator_base, bool> emplace_impl(key_type const& k, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ 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)) { \
+ return std::pair<iterator_base, bool>( \
+ iterator_base(bucket, pos), false); \
+ } else { \
+ node_constructor a(data_.allocators_); \
+ a.construct( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ ); \
+ \
+ if(reserve_for_insert(size() + 1)) \
+ bucket = data_.bucket_ptr_from_hash(hash_value); \
+ \
+ return std::pair<iterator_base, bool>(iterator_base(bucket, \
+ data_.link_node_in_bucket(a, bucket)), true); \
+ } \
+ } \
+ \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ std::pair<iterator_base, bool> emplace_impl(no_key, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ node_constructor a(data_.allocators_); \
+ a.construct( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ ); \
+ return emplace_impl_with_node(a); \
}
+ BOOST_UNORDERED_INSERT_IMPL2(1, 1, _)
+
+ BOOST_PP_REPEAT_FROM_TO(2, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_INSERT_IMPL, _)
+
+#undef BOOST_UNORDERED_INSERT_IMPL
+
#endif
std::pair<iterator_base, bool> emplace_impl_with_node(node_constructor& a)
@@ -1958,7 +2175,6 @@
}
}
-
// Insert from iterators (unique keys)
template <typename I>
@@ -2137,8 +2353,9 @@
key_type const& k) const
{
link_ptr it = data_.begin(bucket);
- while (BOOST_UNORDERED_BORLAND_BOOL(it) && !equal(k, data::get_value(it)))
+ while (BOOST_UNORDERED_BORLAND_BOOL(it) && !equal(k, data::get_value(it))) {
it = data::next_group(it);
+ }
return it;
}
Modified: sandbox/move/boost/unordered/unordered_map.hpp
==============================================================================
--- sandbox/move/boost/unordered/unordered_map.hpp (original)
+++ sandbox/move/boost/unordered/unordered_map.hpp 2009-05-09 15:17:46 EDT (Sat, 09 May 2009)
@@ -1,4 +1,3 @@
-#include <iostream>
// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
// Copyright (C) 2005-2009 Daniel James.
@@ -14,10 +13,10 @@
# pragma once
#endif
+#include <boost/move/move.hpp>
#include <boost/unordered/unordered_map_fwd.hpp>
#include <boost/functional/hash.hpp>
#include <boost/unordered/detail/hash_table.hpp>
-#include <boost/move/move.hpp>
#if defined(BOOST_MSVC)
#pragma warning(push)
@@ -226,6 +225,50 @@
{
return iterator(base.emplace_hint(get(hint), std::forward<Args>(args)...));
}
+#else
+
+ std::pair<iterator, bool> emplace(value_type const& v = value_type())
+ {
+ return boost::unordered_detail::pair_cast<iterator, bool>(
+ base.emplace(v));
+ }
+
+ iterator emplace_hint(const_iterator hint, value_type const& v = value_type())
+ {
+ return iterator(base.emplace_hint(get(hint), v));
+ }
+
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ std::pair<iterator, bool> emplace( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ return boost::unordered_detail::pair_cast<iterator, bool>( \
+ base.emplace( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ )); \
+ } \
+ \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ iterator emplace_hint(const_iterator hint, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ return iterator(base.emplace_hint(get(hint), \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ )); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_EMPLACE, _)
+
+#undef BOOST_UNORDERED_EMPLACE
+
#endif
std::pair<iterator, bool> insert(const value_type& obj)
@@ -627,6 +670,50 @@
{
return iterator(base.emplace_hint(get(hint), std::forward<Args>(args)...));
}
+#else
+
+ iterator emplace(value_type const& v = value_type())
+ {
+ return iterator(base.emplace(v));
+ }
+
+ iterator emplace_hint(const_iterator hint, value_type const& v = value_type())
+ {
+ return iterator(base.emplace_hint(get(hint), v));
+ }
+
+
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ iterator emplace( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ return iterator( \
+ base.emplace( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ )); \
+ } \
+ \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ iterator emplace_hint(const_iterator hint, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ return iterator(base.emplace_hint(get(hint), \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ )); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_EMPLACE, _)
+
+#undef BOOST_UNORDERED_EMPLACE
+
#endif
iterator insert(const value_type& obj)
Modified: sandbox/move/boost/unordered/unordered_set.hpp
==============================================================================
--- sandbox/move/boost/unordered/unordered_set.hpp (original)
+++ sandbox/move/boost/unordered/unordered_set.hpp 2009-05-09 15:17:46 EDT (Sat, 09 May 2009)
@@ -13,10 +13,10 @@
# pragma once
#endif
+#include <boost/move/move.hpp>
#include <boost/unordered/unordered_set_fwd.hpp>
#include <boost/functional/hash.hpp>
#include <boost/unordered/detail/hash_table.hpp>
-#include <boost/move/move.hpp>
#if defined(BOOST_MSVC)
#pragma warning(push)
@@ -223,6 +223,51 @@
return iterator(
base.emplace_hint(get(hint), std::forward<Args>(args)...));
}
+#else
+
+ std::pair<iterator, bool> emplace(value_type v = value_type())
+ {
+ return boost::unordered_detail::pair_cast<iterator, bool>(
+ base.emplace(boost::move(v)));
+ }
+
+ iterator emplace_hint(const_iterator hint, value_type v = value_type())
+ {
+ return iterator(
+ base.emplace_hint(get(hint), boost::move(v)));
+ }
+
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ std::pair<iterator, bool> emplace( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ return boost::unordered_detail::pair_cast<iterator, bool>( \
+ base.emplace( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ )); \
+ } \
+ \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ iterator emplace_hint(const_iterator hint, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ return iterator(base.emplace_hint(get(hint), \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ )); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_EMPLACE, _)
+
+#undef BOOST_UNORDERED_EMPLACE
+
#endif
std::pair<iterator, bool> insert(const value_type& obj)
@@ -594,6 +639,49 @@
{
return iterator(base.emplace_hint(get(hint), std::forward<Args>(args)...));
}
+#else
+
+ iterator emplace(value_type v = value_type())
+ {
+ return iterator(base.emplace(boost::move(v)));
+ }
+
+ iterator emplace_hint(const_iterator hint, value_type v = value_type())
+ {
+ return iterator(base.emplace_hint(get(hint), boost::move(v)));
+ }
+
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ iterator emplace( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ return iterator( \
+ base.emplace( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ )); \
+ } \
+ \
+ template < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename Arg) \
+ > \
+ iterator emplace_hint(const_iterator hint, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FWD_REF, _) \
+ ) \
+ { \
+ return iterator(base.emplace_hint(get(hint), \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_PARAMS_FORWARD, _) \
+ )); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_EMPLACE, _)
+
+#undef BOOST_UNORDERED_EMPLACE
+
#endif
iterator insert(const value_type& obj)
Modified: sandbox/move/libs/unordered/test/unordered/compile_tests.hpp
==============================================================================
--- sandbox/move/libs/unordered/test/unordered/compile_tests.hpp (original)
+++ sandbox/move/libs/unordered/test/unordered/compile_tests.hpp 2009-05-09 15:17:46 EDT (Sat, 09 May 2009)
@@ -151,14 +151,12 @@
r.insert(std::pair<Key const, T>(k, v));
-#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
Key k_lvalue(k);
T v_lvalue(v);
r.emplace(k, v);
r.emplace(k_lvalue, v_lvalue);
r.emplace(rvalue(k), rvalue(v));
-#endif
}
template <class X>
@@ -175,9 +173,7 @@
{
typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
test::check_return_type<std::pair<iterator, bool> >::equals(r.insert(t));
-#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
test::check_return_type<std::pair<iterator, bool> >::equals(r.emplace(t));
-#endif
}
template <class X, class T>
@@ -185,9 +181,7 @@
{
typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
test::check_return_type<iterator>::equals(r.insert(t));
-#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
test::check_return_type<iterator>::equals(r.emplace(t));
-#endif
}
template <class X, class Key, class T>
@@ -289,9 +283,7 @@
const_iterator q = a.cbegin();
test::check_return_type<iterator>::equals(a.insert(q, t));
-#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
test::check_return_type<iterator>::equals(a.emplace_hint(q, t));
-#endif
a.insert(i, j);
test::check_return_type<size_type>::equals(a.erase(k));
Modified: sandbox/move/libs/unordered/test/unordered/unnecessary_copy_tests.cpp
==============================================================================
--- sandbox/move/libs/unordered/test/unordered/unnecessary_copy_tests.cpp (original)
+++ sandbox/move/libs/unordered/test/unordered/unnecessary_copy_tests.cpp 2009-05-09 15:17:46 EDT (Sat, 09 May 2009)
@@ -11,8 +11,11 @@
{
struct count_copies
{
+ BOOST_ENABLE_MOVE_EMULATION(count_copies)
+
static int copies;
static int moves;
+
count_copies() : tag_(0) { ++copies; }
explicit count_copies(int tag) : tag_(tag) { ++copies; }
@@ -29,12 +32,12 @@
: tag_(x.tag_) { ++copies; }
count_copies(count_copies const& x) : tag_(x.tag_) { ++copies; }
-#if defined(BOOST_HAS_RVALUE_REFS)
- count_copies(count_copies&& x) : tag_(x.tag_) {
+
+ count_copies(BOOST_RV_REF(count_copies) x) : tag_(x.tag_) {
x.tag_ = -1; ++moves;
}
-#endif
- int tag_;
+
+ int tag_;
private:
count_copies& operator=(count_copies const&);
};
@@ -68,12 +71,22 @@
#define COPY_COUNT(n) \
if(count_copies::copies != n) { \
BOOST_ERROR("Wrong number of copies."); \
- std::cerr<<"Number of copies: "<<count_copies::copies<<std::endl; \
+ std::cerr<<"Number of copies: "<<count_copies::copies<<" expecting: "<<n<<std::endl; \
}
#define MOVE_COUNT(n) \
if(count_copies::moves != n) { \
BOOST_ERROR("Wrong number of moves."); \
- std::cerr<<"Number of moves: "<<count_copies::moves<<std::endl; \
+ std::cerr<<"Number of moves: "<<count_copies::moves<<" expecting: "<<n<<std::endl; \
+ }
+#define COPY_COUNT_RANGE(a, b) \
+ if(count_copies::copies < a || count_copies::copies > b) { \
+ BOOST_ERROR("Wrong number of copies."); \
+ std::cerr<<"Number of copies: "<<count_copies::copies<<" expecting: ["<<a<<", "<<b<<"]"<<std::endl; \
+ }
+#define MOVE_COUNT_RANGE(a, b) \
+ if(count_copies::moves < a || count_copies::moves > b) { \
+ BOOST_ERROR("Wrong number of moves."); \
+ std::cerr<<"Number of moves: "<<count_copies::copies<<" expecting: ["<<a<<", "<<b<<"]"<<std::endl; \
}
namespace unnecessary_copy_tests
@@ -95,11 +108,17 @@
boost::unordered_multiset<count_copies>* multiset;
boost::unordered_map<int, count_copies>* map;
boost::unordered_multimap<int, count_copies>* multimap;
+
+#define UNORDERED_TEST_CONTAINERS (set)(multiset)(map)(multimap)
+
+#if defined(BOOST_HAS_RVALUE_REFS)
+# define UNORDRED_TEST_MOVABLE_CONTAINERS (set)(multiset)(map)(multimap)
+#else
+# define UNORDRED_TEST_MOVABLE_CONTAINERS (set)(multiset)
+#endif
- UNORDERED_TEST(unnecessary_copy_insert_test,
- ((set)(multiset)(map)(multimap)))
+ UNORDERED_TEST(unnecessary_copy_insert_test, (UNORDERED_TEST_CONTAINERS))
-#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
template <class T>
void unnecessary_copy_emplace_test(T*)
{
@@ -127,16 +146,16 @@
T x;
BOOST_DEDUCED_TYPENAME T::value_type a;
COPY_COUNT(1); MOVE_COUNT(0);
- x.emplace(std::move(a));
+ x.emplace(boost::move(a));
COPY_COUNT(1); MOVE_COUNT(1);
}
UNORDERED_TEST(unnecessary_copy_emplace_test,
- ((set)(multiset)(map)(multimap)))
+ (UNORDERED_TEST_CONTAINERS))
UNORDERED_TEST(unnecessary_copy_emplace_rvalue_test,
- ((set)(multiset)(map)(multimap)))
+ (UNORDRED_TEST_MOVABLE_CONTAINERS))
UNORDERED_TEST(unnecessary_copy_emplace_move_test,
- ((set)(multiset)(map)(multimap)))
+ (UNORDRED_TEST_MOVABLE_CONTAINERS))
UNORDERED_AUTO_TEST(unnecessary_copy_emplace_set_test)
{
@@ -152,9 +171,21 @@
// The container will have to create a copy in order to compare with
// the existing element.
- reset();
+ reset();
x.emplace();
+#if defined(BOOST_HAS_RVALUE_REFS)
COPY_COUNT(1); MOVE_COUNT(0);
+#else
+ // In this implementation a zero argument emplace will construct the
+ // object and then move it into place. This is the only way I could
+ // find to implement it so that it doesn't get instantiated for
+ // object with no zero argument constructors.
+# if BOOST_WORKAROUND(__GNUC__, >= 4) && BOOST_WORKAROUND(__GNUC_MINOR__, >= 2)
+ COPY_COUNT(1); MOVE_COUNT(1);
+# else
+ COPY_COUNT(1); MOVE_COUNT(2);
+# endif
+#endif
//
// 1 argument
@@ -164,18 +195,40 @@
// without creating a new one.
reset();
x.emplace(a);
+#if defined(BOOST_HAS_RVALUE_REFS)
COPY_COUNT(0); MOVE_COUNT(0);
+#else
+ // TODO: When there isn't rvalue references the argument is passed by
+ // value (to allow for more efficient moves). Should I reconsider that?
+ COPY_COUNT(1); MOVE_COUNT(1);
+#endif
// A new object is created by source, but it shouldn't be moved or
// copied.
reset();
x.emplace(source<count_copies>());
+#if defined(BOOST_HAS_RVALUE_REFS)
COPY_COUNT(1); MOVE_COUNT(0);
+#else
+ // Because the argument is taken by value it's moved once into the
+ // parameter.
+# if BOOST_WORKAROUND(__GNUC__, >= 4) && BOOST_WORKAROUND(__GNUC_MINOR__, >= 2)
+ COPY_COUNT(1); MOVE_COUNT(1);
+# else
+ COPY_COUNT(1); MOVE_COUNT(3);
+# endif
+#endif
// No move should take place.
reset();
- x.emplace(std::move(a));
+ x.emplace(boost::move(a));
+#if defined(BOOST_HAS_RVALUE_REFS)
COPY_COUNT(0); MOVE_COUNT(0);
+#else
+ // Unavoidable without rvalue references.
+ // TODO: Or is it? If I used boost::rv it wouldn't happen, surely?
+ COPY_COUNT(0); MOVE_COUNT(1);
+#endif
// Just in case a did get moved...
count_copies b;
@@ -194,8 +247,10 @@
// the existing element.
//
// Note to self: If copy_count == 0 it's an error not an optimization.
+ // TODO: Devise a better test.
reset();
+
x.emplace(b, b);
COPY_COUNT(1); MOVE_COUNT(0);
}
@@ -232,24 +287,34 @@
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);
+ // TODO: This doesn't work on older versions of gcc.
+ //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.
+ // (since a is already in the container)
reset();
- x.emplace(std::move(a));
+ x.emplace(boost::move(a));
+#if defined(BOOST_HAS_RVALUE_REFS)
COPY_COUNT(0); MOVE_COUNT(0);
+#endif
- // Just in case a did get moved
std::pair<count_copies const, count_copies> b;
-
- // This test requires a C++0x std::pair. Which gcc hasn't got yet.
- //reset();
- //x.emplace(b.first.tag_);
- //COPY_COUNT(2); MOVE_COUNT(0);
+ reset();
+ x.emplace(b.first.tag_);
+#if defined(BOOST_HAS_RVALUE_REFS)
+# if defined(__GLIBCPP__) || defined(__GLIBCXX__)
+ COPY_COUNT(2); MOVE_COUNT(1);
+# else
+ COPY_COUNT(2); MOVE_COUNT(0);
+# endif
+#else
+ // TODO: Why is this one 4?
+ COPY_COUNT(4); MOVE_COUNT(0);
+#endif
//
// 2 arguments
@@ -261,18 +326,27 @@
reset();
x.emplace(source<count_copies>(), source<count_copies>());
- COPY_COUNT(2); MOVE_COUNT(0);
+ COPY_COUNT(2);
+#if defined(BOOST_HAS_RVALUE_REFS)
+ MOVE_COUNT(0);
+#else
+ MOVE_COUNT_RANGE(0, 2);
+#endif
// source<count_copies> creates a single copy.
reset();
x.emplace(b.first, source<count_copies>());
- COPY_COUNT(1); MOVE_COUNT(0);
+ COPY_COUNT(1);
+#if defined(BOOST_HAS_RVALUE_REFS)
+ MOVE_COUNT(0);
+#else
+ MOVE_COUNT_RANGE(0, 1);
+#endif
reset();
- x.emplace(b.first.tag_, b.second.tag_);
- COPY_COUNT(2); MOVE_COUNT(0);
+ x.emplace(count_copies(b.first.tag_), count_copies(b.second.tag_));
+ COPY_COUNT(2); MOVE_COUNT(0);
}
-#endif
}
RUN_TESTS()
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk