|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r52884 - trunk/boost/unordered/detail
From: daniel_james_at_[hidden]
Date: 2009-05-10 17:24:42
Author: danieljames
Date: 2009-05-10 17:24:41 EDT (Sun, 10 May 2009)
New Revision: 52884
URL: http://svn.boost.org/trac/boost/changeset/52884
Log:
Cherrypick some unordered container changes from sandbox. Not including
anything which depends on the new move library.
------------------------------------------------------------------------
r52746 | danieljames | 2009-05-03 11:12:30 +0100 (Sun, 03 May 2009) | 1 line
Merge latest unordered container changes.
------------------------------------------------------------------------
r52747 | danieljames | 2009-05-03 11:15:35 +0100 (Sun, 03 May 2009) | 4 lines
Put the C++0x emplace implementations before the non-C++0x versions.
I'm going to change the non-C++0x to be macro heavy emulations of the
C++0x versions, so this will put the readable version first.
------------------------------------------------------------------------
r52748 | danieljames | 2009-05-03 11:15:44 +0100 (Sun, 03 May 2009) | 1 line
Refactor the unordered implementation a tad, to make implementing emplace less painful.
------------------------------------------------------------------------
Text files modified:
trunk/boost/unordered/detail/hash_table_impl.hpp | 175 ++++++++++++++++++++-------------------
1 files changed, 90 insertions(+), 85 deletions(-)
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-05-10 17:24:41 EDT (Sun, 10 May 2009)
@@ -181,9 +181,7 @@
}
}
-#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
- template <typename... Args>
- void construct(Args&&... args)
+ void construct_preamble()
{
BOOST_ASSERT(!node_);
node_constructed_ = false;
@@ -194,6 +192,13 @@
allocators_.node_alloc_.construct(node_, node());
node_constructed_ = true;
+ }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template <typename... Args>
+ void construct(Args&&... args)
+ {
+ construct_preamble();
new(node_->address()) value_type(std::forward<Args>(args)...);
value_constructed_ = true;
}
@@ -201,15 +206,7 @@
template <typename V>
void construct(V const& v)
{
- BOOST_ASSERT(!node_);
- node_constructed_ = false;
- value_constructed_ = false;
-
- node_ = allocators_.node_alloc_.allocate(1);
-
- allocators_.node_alloc_.construct(node_, node());
- node_constructed_ = true;
-
+ construct_preamble();
new(node_->address()) value_type(v);
value_constructed_ = true;
}
@@ -1599,31 +1596,36 @@
#if BOOST_UNORDERED_EQUIVALENT_KEYS
-#if !(defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL))
- // Insert (equivalent key containers)
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+
+ // Emplace (equivalent key containers)
+ // (I'm using an overloaded emplace for both 'insert' and 'emplace')
// if hash function throws, basic exception safety
// strong otherwise
- iterator_base emplace(value_type const& v)
+ template <class... Args>
+ iterator_base emplace(Args&&... args)
{
// 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);
+ a.construct(std::forward<Args>(args)...);
return emplace_impl(a);
}
- // Insert (equivalent key containers)
+ // Emplace (equivalent key containers)
+ // (I'm using an overloaded emplace for both 'insert' and 'emplace')
// if hash function throws, basic exception safety
// strong otherwise
- iterator_base emplace_hint(iterator_base const& it, value_type const& v)
+ template <class... Args>
+ iterator_base emplace_hint(iterator_base const& it, Args&&... args)
{
// 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);
+ a.construct(std::forward<Args>(args)...);
return emplace_hint_impl(it, a);
}
@@ -1631,33 +1633,29 @@
#else
// Emplace (equivalent key containers)
- // (I'm using an overloaded emplace for both 'insert' and 'emplace')
// if hash function throws, basic exception safety
// strong otherwise
- template <class... Args>
- iterator_base emplace(Args&&... args)
+ 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(std::forward<Args>(args)...);
+ a.construct(v);
return emplace_impl(a);
}
- // Insert (equivalent key containers)
- // (I'm using an overloaded emplace for both 'insert' and 'emplace')
+ // Emplace (equivalent key containers)
// if hash function throws, basic exception safety
// strong otherwise
- template <class... Args>
- iterator_base emplace_hint(iterator_base const& it, Args&&... args)
+ 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(std::forward<Args>(args)...);
+ a.construct(v);
return emplace_hint_impl(it, a);
}
@@ -1689,13 +1687,13 @@
{
// equal can throw, but with no effects
if (it == data_.end() || !equal(extract_key(a.get()->value()), *it)) {
- // Use the standard insert if the iterator doesn't point
+ // Use the standard emplace if the iterator doesn't point
// to a matching key.
return emplace_impl(a);
}
else {
// Find the first node in the group - so that the node
- // will be inserted at the end of the group.
+ // will be added at the end of the group.
link_ptr start(it.node_);
while(data_.prev_in_group(start)->next_ == start)
@@ -1803,16 +1801,43 @@
}
}
-#if !(defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL))
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+
+ // 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
+ template<typename... Args>
+ std::pair<iterator_base, bool> emplace(Args&&... args)
+ {
+ return emplace_impl(
+ extract_key(std::forward<Args>(args)...),
+ std::forward<Args>(args)...);
+ }
// Insert (unique keys)
+ // (I'm using an overloaded emplace for both 'insert' and 'emplace')
+ // I'm just ignoring hints here for now.
// if hash function throws, basic exception safety
// strong otherwise
- std::pair<iterator_base, bool> emplace(value_type const& v)
+ template<typename... Args>
+ iterator_base emplace_hint(iterator_base const&, Args&&... args)
+ {
+ return emplace_impl(
+ extract_key(std::forward<Args>(args)...),
+ std::forward<Args>(args)...).first;
+ }
+
+ template<typename... Args>
+ std::pair<iterator_base, bool> emplace_impl(key_type const& k, Args&&... args)
{
// 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);
@@ -1829,7 +1854,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(v);
+ a.construct(std::forward<Args>(args)...);
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
@@ -1838,48 +1863,30 @@
// 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 std::pair<iterator_base, bool>(iterator_base(bucket,
+ data_.link_node_in_bucket(a, bucket)), true);
}
}
- // Insert (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... Args>
+ std::pair<iterator_base, bool> emplace_impl(no_key, Args&&... args)
{
- if(it != data_.end() && equal(extract_key(v), *it))
- return it;
- else
- return emplace(v).first;
+ // Construct the node regardless - in order to get the key.
+ // It will be discarded if it isn't used
+ node_constructor a(data_.allocators_);
+ a.construct(std::forward<Args>(args)...);
+ return emplace_impl_with_node(a);
}
-
#else
- // Insert (unique keys)
- // (I'm using an overloaded insert 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.
+ // Emplace (unique keys)
// if hash function throws, basic exception safety
// strong otherwise
- template<typename... Args>
- std::pair<iterator_base, bool> emplace(Args&&... args)
- {
- return emplace_impl(
- extract_key(std::forward<Args>(args)...),
- std::forward<Args>(args)...);
- }
-
- template<typename... Args>
- std::pair<iterator_base, bool> emplace_impl(key_type const& k, Args&&... args)
+ std::pair<iterator_base, bool> emplace(value_type const& v)
{
// 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);
@@ -1896,7 +1903,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(std::forward<Args>(args)...);
+ a.construct(v);
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
@@ -1905,19 +1912,29 @@
// Nothing after this point can throw.
- return std::pair<iterator_base, bool>(iterator_base(bucket,
- data_.link_node_in_bucket(a, bucket)), true);
+ 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> emplace_impl(no_key, Args&&... args)
+ // Emplace (unique keys)
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ iterator_base emplace_hint(iterator_base const& it, value_type const& v)
{
- // Construct the node regardless - in order to get the key.
- // It will be discarded if it isn't used
- node_constructor a(data_.allocators_);
- a.construct(std::forward<Args>(args)...);
+ if(it != data_.end() && equal(extract_key(v), *it))
+ return it;
+ else
+ return emplace(v).first;
+ }
+#endif
+
+ std::pair<iterator_base, bool> emplace_impl_with_node(node_constructor& a)
+ {
// No side effects in this initial code
key_type const& k = extract_key(a.get()->value());
size_type hash_value = hash_function()(k);
@@ -1941,18 +1958,6 @@
}
}
- // Insert (unique keys)
- // (I'm using an overloaded insert for both 'insert' and 'emplace')
-
- // if hash function throws, basic exception safety
- // strong otherwise
- template<typename... Args>
- iterator_base emplace_hint(iterator_base const&, Args&&... args)
- {
- // Life is complicated - just call the normal implementation.
- return emplace(std::forward<Args>(args)...).first;
- }
-#endif
// Insert from iterators (unique keys)
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