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

Subject: [Boost-commit] svn:boost r78365 - in trunk: boost/unordered boost/unordered/detail libs/unordered/doc libs/unordered/test/unordered
From: dnljms_at_[hidden]
Date: 2012-05-07 06:58:33

Author: danieljames
Date: 2012-05-07 06:58:32 EDT (Mon, 07 May 2012)
New Revision: 78365
URL: http://svn.boost.org/trac/boost/changeset/78365

Log:
Unordered: Implement reserve. Refs #6857.
Text files modified: 
   trunk/boost/unordered/detail/table.hpp               |    14 ++++++++++-                             
   trunk/boost/unordered/unordered_map.hpp              |    14 +++++++++++                             
   trunk/boost/unordered/unordered_set.hpp              |    14 +++++++++++                             
   trunk/libs/unordered/doc/changes.qbk                 |     2 +                                       
   trunk/libs/unordered/doc/ref.php                     |    12 ++++++++++                              
   trunk/libs/unordered/doc/ref.xml                     |    48 ++++++++++++++++++++++++++++++++++++++++
   trunk/libs/unordered/test/unordered/rehash_tests.cpp |    31 +++++++++++++++++++++++++               
   7 files changed, 133 insertions(+), 2 deletions(-)

Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp	(original)
+++ trunk/boost/unordered/detail/table.hpp	2012-05-07 06:58:32 EDT (Mon, 07 May 2012)
@@ -387,6 +387,7 @@
 
         void reserve_for_insert(std::size_t);
         void rehash(std::size_t);
+        void reserve(std::size_t);
     };
 
     ////////////////////////////////////////////////////////////////////////////
@@ -402,7 +403,9 @@
             this->create_buckets();
             this->max_load_ = this->calculate_max_load();
         }
-        else if(size >= max_load_) {
+        // According to the standard this should be 'size >= max_load_',
+        // but I think this is better, defect report filed.
+        else if(size > max_load_) {
             std::size_t num_buckets
                 = this->min_buckets_for_size((std::max)(size,
                     this->size_ + (this->size_ >> 1)));
@@ -417,7 +420,7 @@
     // strong otherwise.
 
     template <typename Types>
-    void table<Types>::rehash(std::size_t min_buckets)
+    inline void table<Types>::rehash(std::size_t min_buckets)
     {
         using namespace std;
 
@@ -437,6 +440,13 @@
             }
         }
     }
+
+    template <typename Types>
+    inline void table<Types>::reserve(std::size_t num_elements)
+    {
+        rehash(static_cast<std::size_t>(
+            std::ceil(static_cast<double>(num_elements) / this->mlf_)));
+    }
 }}}
 
 #endif

Modified: trunk/boost/unordered/unordered_map.hpp
==============================================================================
--- trunk/boost/unordered/unordered_map.hpp	(original)
+++ trunk/boost/unordered/unordered_map.hpp	2012-05-07 06:58:32 EDT (Mon, 07 May 2012)
@@ -515,6 +515,7 @@
         float load_factor() const;
         void max_load_factor(float);
         void rehash(size_type);
+        void reserve(size_type);
 
 #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
         friend bool operator==<K,T,H,P,A>(
@@ -997,6 +998,7 @@
         float load_factor() const;
         void max_load_factor(float);
         void rehash(size_type);
+        void reserve(size_type);
 
 #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
         friend bool operator==<K,T,H,P,A>(
@@ -1301,6 +1303,12 @@
     }
 
     template <class K, class T, class H, class P, class A>
+    void unordered_map<K,T,H,P,A>::reserve(size_type n)
+    {
+        table_.reserve(n);
+    }
+
+    template <class K, class T, class H, class P, class A>
     inline bool operator==(
             unordered_map<K,T,H,P,A> const& m1,
             unordered_map<K,T,H,P,A> const& m2)
@@ -1607,6 +1615,12 @@
     }
 
     template <class K, class T, class H, class P, class A>
+    void unordered_multimap<K,T,H,P,A>::reserve(size_type n)
+    {
+        table_.reserve(n);
+    }
+
+    template <class K, class T, class H, class P, class A>
     inline bool operator==(
             unordered_multimap<K,T,H,P,A> const& m1,
             unordered_multimap<K,T,H,P,A> const& m2)

Modified: trunk/boost/unordered/unordered_set.hpp
==============================================================================
--- trunk/boost/unordered/unordered_set.hpp	(original)
+++ trunk/boost/unordered/unordered_set.hpp	2012-05-07 06:58:32 EDT (Mon, 07 May 2012)
@@ -500,6 +500,7 @@
         float load_factor() const;
         void max_load_factor(float);
         void rehash(size_type);
+        void reserve(size_type);
 
 #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
         friend bool operator==<T,H,P,A>(
@@ -972,6 +973,7 @@
         float load_factor() const;
         void max_load_factor(float);
         void rehash(size_type);
+        void reserve(size_type);
 
 #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
         friend bool operator==<T,H,P,A>(
@@ -1227,6 +1229,12 @@
     }
 
     template <class T, class H, class P, class A>
+    void unordered_set<T,H,P,A>::reserve(size_type n)
+    {
+        table_.reserve(n);
+    }
+
+    template <class T, class H, class P, class A>
     inline bool operator==(
             unordered_set<T,H,P,A> const& m1,
             unordered_set<T,H,P,A> const& m2)
@@ -1505,6 +1513,12 @@
     }
 
     template <class T, class H, class P, class A>
+    void unordered_multiset<T,H,P,A>::reserve(size_type n)
+    {
+        table_.reserve(n);
+    }
+
+    template <class T, class H, class P, class A>
     inline bool operator==(
             unordered_multiset<T,H,P,A> const& m1,
             unordered_multiset<T,H,P,A> const& m2)

Modified: trunk/libs/unordered/doc/changes.qbk
==============================================================================
--- trunk/libs/unordered/doc/changes.qbk	(original)
+++ trunk/libs/unordered/doc/changes.qbk	2012-05-07 06:58:32 EDT (Mon, 07 May 2012)
@@ -178,6 +178,8 @@
 [h2 Boost 1.50.0]
 
 * Fix equality for `unordered_multiset` and `unordered_multimap`.
+* [@https://svn.boost.org/trac/boost/ticket/6857 Ticket 6857]:
+  Implement `reserve`.
 * [@https://svn.boost.org/trac/boost/ticket/6771 Ticket 6771]:
   Avoid gcc's `-Wfloat-equal` warning.
 * [@https://svn.boost.org/trac/boost/ticket/6784 Ticket 6784]:

Modified: trunk/libs/unordered/doc/ref.php
==============================================================================
--- trunk/libs/unordered/doc/ref.php	(original)
+++ trunk/libs/unordered/doc/ref.php	2012-05-07 06:58:32 EDT (Mon, 07 May 2012)
@@ -963,6 +963,18 @@
                 <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
               </throws>
             </method>
+            <method name="reserve">
+              <parameter name="n">
+                <paramtype>size_type</paramtype>
+              </parameter>
+              <type>void</type>
+              <description>
+                <para>Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.</para>
+              </description>
+              <throws>
+                <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
+              </throws>
+            </method>
           </method-group>
           <free-function-group name="Equality Comparisons">
             <function name="operator==">

Modified: trunk/libs/unordered/doc/ref.xml
==============================================================================
--- trunk/libs/unordered/doc/ref.xml	(original)
+++ trunk/libs/unordered/doc/ref.xml	2012-05-07 06:58:32 EDT (Mon, 07 May 2012)
@@ -846,6 +846,18 @@
                 <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
               </throws>
             </method>
+            <method name="reserve">
+              <parameter name="n">
+                <paramtype>size_type</paramtype>
+              </parameter>
+              <type>void</type>
+              <description>
+                <para>Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.</para>
+              </description>
+              <throws>
+                <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
+              </throws>
+            </method>
           </method-group>
           <free-function-group name="Equality Comparisons">
             <function name="operator==">
@@ -1797,6 +1809,18 @@
                 <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
               </throws>
             </method>
+            <method name="reserve">
+              <parameter name="n">
+                <paramtype>size_type</paramtype>
+              </parameter>
+              <type>void</type>
+              <description>
+                <para>Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.</para>
+              </description>
+              <throws>
+                <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
+              </throws>
+            </method>
           </method-group>
           <free-function-group name="Equality Comparisons">
             <function name="operator==">
@@ -2793,6 +2817,18 @@
                 <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
               </throws>
             </method>
+            <method name="reserve">
+              <parameter name="n">
+                <paramtype>size_type</paramtype>
+              </parameter>
+              <type>void</type>
+              <description>
+                <para>Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.</para>
+              </description>
+              <throws>
+                <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
+              </throws>
+            </method>
           </method-group>
           <free-function-group name="Equality Comparisons">
             <function name="operator==">
@@ -3758,6 +3794,18 @@
                 <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
               </throws>
             </method>
+            <method name="reserve">
+              <parameter name="n">
+                <paramtype>size_type</paramtype>
+              </parameter>
+              <type>void</type>
+              <description>
+                <para>Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.</para>
+              </description>
+              <throws>
+                <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
+              </throws>
+            </method>
           </method-group>
           <free-function-group name="Equality Comparisons">
             <function name="operator==">

Modified: trunk/libs/unordered/test/unordered/rehash_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/rehash_tests.cpp	(original)
+++ trunk/libs/unordered/test/unordered/rehash_tests.cpp	2012-05-07 06:58:32 EDT (Mon, 07 May 2012)
@@ -100,6 +100,34 @@
     tracker.compare(x);
 }
 
+template <class X>
+void reserve_test(X* = 0,
+    test::random_generator generator = test::default_generator)
+{
+    for (int random_mlf = 0; random_mlf < 2; ++random_mlf)
+    {
+        for (int i = 0; i < 2000; i += i < 50 ? 1 : 13)
+        {
+            test::random_values<X> v(i, generator);
+
+            test::ordered<X> tracker;
+            tracker.insert_range(v.begin(), v.end());
+
+            X x;
+            x.max_load_factor(random_mlf ?
+                static_cast<float>(std::rand() % 1000) / 500.0 + 0.5f : 1.0f);
+            // For the current standard this should reserve i+1, I've
+            // submitted a defect report and will assume it's a defect
+            // for now.
+            x.reserve(i);
+            std::size_t bucket_count = x.bucket_count();
+            x.insert(v.begin(), v.end());
+            BOOST_TEST(bucket_count == x.bucket_count());
+            tracker.compare(x);
+        }
+    }
+}
+
 boost::unordered_set<int>* int_set_ptr;
 boost::unordered_multiset<int>* int_multiset_ptr;
 boost::unordered_map<int, int>* int_map_ptr;
@@ -117,6 +145,9 @@
 UNORDERED_TEST(rehash_test1,
     ((int_set_ptr)(int_multiset_ptr)(int_map_ptr)(int_multimap_ptr))
 )
+UNORDERED_TEST(reserve_test,
+    ((int_set_ptr)(int_multiset_ptr)(int_map_ptr)(int_multimap_ptr))
+)
 
 }