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

Subject: [Boost-commit] svn:boost r49926 - in trunk: boost/unordered/detail libs/unordered/doc
From: daniel_james_at_[hidden]
Date: 2008-11-24 17:56:04

Author: danieljames
Date: 2008-11-24 17:56:04 EST (Mon, 24 Nov 2008)
New Revision: 49926
URL: http://svn.boost.org/trac/boost/changeset/49926

Log:
Use a larger prime number list. Fixes #1710
Text files modified: 
   trunk/boost/unordered/detail/hash_table.hpp      |     5 +++--                                   
   trunk/boost/unordered/detail/hash_table_impl.hpp |    31 +++++++++++++++++++++++--------         
   trunk/libs/unordered/doc/changes.qbk             |     3 +++                                     
   3 files changed, 29 insertions(+), 10 deletions(-)

Modified: trunk/boost/unordered/detail/hash_table.hpp
==============================================================================
--- trunk/boost/unordered/detail/hash_table.hpp	(original)
+++ trunk/boost/unordered/detail/hash_table.hpp	2008-11-24 17:56:04 EST (Mon, 24 Nov 2008)
@@ -76,8 +76,9 @@
 
         template<typename T>
         std::size_t const prime_list_template<T>::value[] = {
-            53ul, 97ul, 193ul, 389ul, 769ul,
-            1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
+            5ul, 11ul, 17ul, 29ul, 37ul, 53ul, 67ul, 79ul,
+            97ul, 131ul, 193ul, 257ul, 389ul, 521ul, 769ul,
+            1031ul, 1543ul, 2053ul, 3079ul, 6151ul, 12289ul, 24593ul,
             49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
             1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
             50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,

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	2008-11-24 17:56:04 EST (Mon, 24 Nov 2008)
@@ -1469,6 +1469,21 @@
                 return need_to_reserve;
             }
 
+            // basic exception safety
+            bool reserve_for_insert(size_type n)
+            {
+                bool need_to_reserve = n >= max_load_;
+                // throws - basic:
+                if (need_to_reserve) {
+                    size_type s = size();
+                    s = s + (s >> 1);
+                    s = s > n ? s : n;
+                    rehash_impl(min_buckets_for_size(s));
+                }
+                BOOST_ASSERT(n < max_load_ || n > max_size());
+                return need_to_reserve;
+            }
+
         public:
 
             // no throw
@@ -1720,7 +1735,7 @@
 
                 // reserve has basic exception safety if the hash function
                 // throws, strong otherwise.
-                if(reserve(size() + 1))
+                if(reserve_for_insert(size() + 1))
                     bucket = data_.bucket_ptr_from_hash(hash_value);
 
                 // I'm relying on link_ptr not being invalidated by
@@ -1750,7 +1765,7 @@
 
                     // reserve has basic exception safety if the hash function
                     // throws, strong otherwise.
-                    bucket_ptr base = reserve(size() + 1) ?
+                    bucket_ptr base = reserve_for_insert(size() + 1) ?
                         get_bucket(extract_key(a.get()->value_)) : it.bucket_;
 
                     // Nothing after this point can throw
@@ -1775,7 +1790,7 @@
                 }
                 else {
                     // Only require basic exception safety here
-                    reserve(size() + distance);
+                    reserve_for_insert(size() + distance);
                     node_constructor a(data_.allocators_);
 
                     for (; i != j; ++i) {
@@ -1841,7 +1856,7 @@
 
                     // reserve has basic exception safety if the hash function
                     // throws, strong otherwise.
-                    if(reserve(size() + 1))
+                    if(reserve_for_insert(size() + 1))
                         bucket = data_.bucket_ptr_from_hash(hash_value);
 
                     // Nothing after this point can throw.
@@ -1880,7 +1895,7 @@
 
                     // reserve has basic exception safety if the hash function
                     // throws, strong otherwise.
-                    if(reserve(size() + 1))
+                    if(reserve_for_insert(size() + 1))
                         bucket = data_.bucket_ptr_from_hash(hash_value);
 
                     // Nothing after this point can throw.
@@ -1947,7 +1962,7 @@
 
                     // reserve has basic exception safety if the hash function
                     // throws, strong otherwise.
-                    if(reserve(size() + 1))
+                    if(reserve_for_insert(size() + 1))
                         bucket = data_.bucket_ptr_from_hash(hash_value);
 
                     // Nothing after this point can throw.
@@ -1978,7 +1993,7 @@
                 } else {
                     // reserve has basic exception safety if the hash function
                     // throws, strong otherwise.
-                    if(reserve(size() + 1))
+                    if(reserve_for_insert(size() + 1))
                         bucket = data_.bucket_ptr_from_hash(hash_value);
 
                     // Nothing after this point can throw.
@@ -2047,7 +2062,7 @@
                         // reserve has basic exception safety if the hash function
                         // throws, strong otherwise.
                         if(size() + 1 >= max_load_) {
-                            reserve(size() + insert_size(i, j));
+                            reserve_for_insert(size() + insert_size(i, j));
                             bucket = data_.bucket_ptr_from_hash(hash_value);
                         }
 

Modified: trunk/libs/unordered/doc/changes.qbk
==============================================================================
--- trunk/libs/unordered/doc/changes.qbk	(original)
+++ trunk/libs/unordered/doc/changes.qbk	2008-11-24 17:56:04 EST (Mon, 24 Nov 2008)
@@ -49,5 +49,8 @@
   Document that the equality and inequality operators are undefined for two
   objects if their equality predicates aren't equivalent. Thanks to Daniel
   Krügler.
+* [@https://svn.boost.org/trac/boost/ticket/1710 Ticket 1710]: 
+  Use a larger prime number list. Thanks to Thorsten Ottosen and Hervé
+  Brönnimann.
 
 [endsect]