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]