[Boost-commit] svn:boost r52884 - trunk/boost/unordered/detail

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)