From: daniel_james_at_[hidden]
Date: 2008-04-21 11:55:41
Author: danieljames
Date: 2008-04-21 11:55:40 EDT (Mon, 21 Apr 2008)
New Revision: 44697
URL: http://svn.boost.org/trac/boost/changeset/44697
Log:
Factor out the code for choosing the bucket count, and which bucket that hash values map to make it easier to experiment with alternative policies.
Text files modified:
trunk/boost/unordered/detail/hash_table.hpp | 27 +++++++++++++
trunk/boost/unordered/detail/hash_table_impl.hpp | 75 ++++++++++++++++++++++-----------------
2 files changed, 69 insertions(+), 33 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-04-21 11:55:40 EDT (Mon, 21 Apr 2008)
@@ -50,7 +50,6 @@
static const std::size_t default_initial_bucket_count = 50;
static const float minimum_max_load_factor = 1e-3f;
- inline std::size_t next_prime(std::size_t n);
template <class T>
inline void hash_swap(T& x, T& y)
@@ -101,6 +100,32 @@
bound--;
return *bound;
}
+
+ // Controls how many buckets are allocated and which buckets hash
+ // values map to. Does not contain the buckets themselves, or ever
+ // deal with them directly.
+
+ struct bucket_manager {
+ std::size_t bucket_count_;
+
+ bucket_manager()
+ : bucket_count_(0) {}
+
+ explicit bucket_manager(std::size_t n)
+ : bucket_count_(next_prime(n)) {}
+
+ std::size_t bucket_count() const {
+ return bucket_count_;
+ }
+
+ std::size_t bucket_from_hash(std::size_t hashed) const {
+ return hashed % bucket_count_;
+ }
+
+ std::size_t max_bucket_count(std::size_t max_size) const {
+ return prev_prime(max_size);
+ }
+ };
// pair_cast - used to convert between pair types.
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-04-21 11:55:40 EDT (Mon, 21 Apr 2008)
@@ -312,15 +312,15 @@
allocators allocators_;
bucket_ptr buckets_;
- size_type bucket_count_;
+ bucket_manager bucket_manager_;
bucket_ptr cached_begin_bucket_;
- size_type size_;
+ size_type size_;
// Constructors/Deconstructor
BOOST_UNORDERED_TABLE_DATA(size_type n, value_allocator const& a)
: allocators_(a),
- buckets_(), bucket_count_(next_prime(n)),
+ buckets_(), bucket_manager_(n),
cached_begin_bucket_(), size_(0)
{
BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
@@ -329,7 +329,7 @@
BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA const& x, size_type n)
: allocators_(x.allocators_),
- buckets_(), bucket_count_(next_prime(n)),
+ buckets_(), bucket_manager_(n),
cached_begin_bucket_(), size_(0)
{
BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
@@ -338,7 +338,7 @@
BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x, move_tag)
: allocators_(x.allocators_),
- buckets_(x.buckets_), bucket_count_(x.bucket_count_),
+ buckets_(x.buckets_), bucket_manager_(x.bucket_manager_),
cached_begin_bucket_(x.cached_begin_bucket_), size_(x.size_)
{
unordered_detail::reset(x.buckets_);
@@ -346,19 +346,19 @@
BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x,
value_allocator const& a, size_type n, move_tag)
- : allocators_(a), buckets_(), bucket_count_(),
+ : allocators_(a), buckets_(), bucket_manager_(),
cached_begin_bucket_(), size_(0)
{
if(allocators_ == x.allocators_) {
buckets_ = x.buckets_;
- bucket_count_ = x.bucket_count_;
+ bucket_manager_ = x.bucket_manager_;
cached_begin_bucket_ = x.cached_begin_bucket_;
size_ = x.size_;
unordered_detail::reset(x.buckets_);
}
else {
BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
- bucket_count_ = next_prime(n);
+ bucket_manager_ = bucket_manager(n);
create_buckets();
}
}
@@ -370,15 +370,17 @@
}
void create_buckets() {
+ size_type bucket_count = bucket_manager_.bucket_count();
+
// The array constructor will clean up in the event of an
// exception.
allocator_array_constructor<bucket_allocator>
constructor(allocators_.bucket_alloc_);
// Creates an extra bucket to act as a sentinel.
- constructor.construct(bucket(), bucket_count_ + 1);
+ constructor.construct(bucket(), bucket_count + 1);
- cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count_);
+ cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count);
// Set up the sentinel.
cached_begin_bucket_->next_ = link_ptr(cached_begin_bucket_);
@@ -404,7 +406,8 @@
for(begin = buckets_; begin != end; ++begin)
allocators_.bucket_alloc_.destroy(begin);
- allocators_.bucket_alloc_.deallocate(buckets_, bucket_count_ + 1);
+ allocators_.bucket_alloc_.deallocate(buckets_,
+ bucket_manager_.bucket_count() + 1);
}
}
@@ -419,7 +422,7 @@
void swap(BOOST_UNORDERED_TABLE_DATA& other)
{
std::swap(buckets_, other.buckets_);
- std::swap(bucket_count_, other.bucket_count_);
+ std::swap(bucket_manager_, other.bucket_manager_);
std::swap(cached_begin_bucket_, other.cached_begin_bucket_);
std::swap(size_, other.size_);
}
@@ -430,17 +433,26 @@
delete_buckets();
buckets_ = other.buckets_;
unordered_detail::reset(other.buckets_);
- bucket_count_ = other.bucket_count_;
+ bucket_manager_ = other.bucket_manager_;
cached_begin_bucket_ = other.cached_begin_bucket_;
size_ = other.size_;
}
+ // Return the bucket number for a hashed value.
+ //
+ // no throw
+ size_type bucket_from_hash(size_type hashed) const
+ {
+ return bucket_manager_.bucket_from_hash(hashed);
+ }
+
// Return the bucket for a hashed value.
//
// no throw
- bucket_ptr bucket_from_hash(size_type hashed) const
+ bucket_ptr bucket_ptr_from_hash(size_type hashed) const
{
- return buckets_ + static_cast<difference_type>(hashed % bucket_count_);
+ return buckets_ + static_cast<difference_type>(
+ bucket_manager_.bucket_from_hash(hashed));
}
// Begin & End
@@ -449,7 +461,7 @@
bucket_ptr buckets_end() const
{
- return buckets_ + static_cast<difference_type>(bucket_count_);
+ return buckets_ + static_cast<difference_type>(bucket_manager_.bucket_count());
}
iterator_base begin() const
@@ -1282,7 +1294,7 @@
size_type bucket(key_type const& k) const
{
// hash_function can throw:
- return hash_function()(k) % data_.bucket_count_;
+ return data_.bucket_from_hash(hash_function()(k));
}
@@ -1295,7 +1307,7 @@
// no throw
size_type bucket_count() const
{
- return data_.bucket_count_;
+ return data_.bucket_manager_.bucket_count();
}
// no throw
@@ -1331,7 +1343,7 @@
// From 6.3.1/13:
// Only resize when size >= mlf_ * count
max_load_ = double_to_size_t(ceil(
- (double) mlf_ * data_.bucket_count_));
+ (double) mlf_ * data_.bucket_manager_.bucket_count()));
}
// basic exception safety
@@ -1383,9 +1395,9 @@
// no throw
float load_factor() const
{
- BOOST_ASSERT(data_.bucket_count_ != 0);
+ BOOST_ASSERT(data_.bucket_manager_.bucket_count() != 0);
return static_cast<float>(data_.size_)
- / static_cast<float>(data_.bucket_count_);
+ / static_cast<float>(data_.bucket_manager_.bucket_count());
}
private:
@@ -1465,7 +1477,7 @@
// src_bucket to dst.
// This next line throws iff the hash function throws.
- bucket_ptr dst_bucket = dst.bucket_from_hash(
+ bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
hf(extract_key(data::get_value(src_bucket->next_))));
link_ptr n = src_bucket->next_;
@@ -1491,7 +1503,7 @@
for(link_ptr it = src.begin(i);
BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it)) {
// hash function can throw.
- bucket_ptr dst_bucket = dst.bucket_from_hash(
+ bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
hf(extract_key(data::get_value(it))));
// throws, strong
dst.copy_group(it, dst_bucket);
@@ -1516,7 +1528,7 @@
{
key_type const& k = extract_key(v);
size_type hash_value = hash_function()(k);
- bucket_ptr bucket = data_.bucket_from_hash(hash_value);
+ bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
link_ptr position = find_iterator(bucket, k);
// Create the node before rehashing in case it throws an
@@ -1527,7 +1539,7 @@
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(reserve(size() + 1))
- bucket = data_.bucket_from_hash(hash_value);
+ bucket = data_.bucket_ptr_from_hash(hash_value);
// I'm relying on link_ptr not being invalidated by
// the rehash here.
@@ -1640,7 +1652,7 @@
typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
size_type hash_value = hash_function()(k);
- bucket_ptr bucket = data_.bucket_from_hash(hash_value);
+ bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
link_ptr pos = find_iterator(bucket, k);
if (BOOST_UNORDERED_BORLAND_BOOL(pos))
@@ -1657,7 +1669,7 @@
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(reserve(size() + 1))
- bucket = data_.bucket_from_hash(hash_value);
+ bucket = data_.bucket_ptr_from_hash(hash_value);
// Nothing after this point can throw.
@@ -1674,7 +1686,7 @@
// 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_from_hash(hash_value);
+ bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
link_ptr pos = find_iterator(bucket, k);
if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
@@ -1694,7 +1706,7 @@
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(reserve(size() + 1))
- bucket = data_.bucket_from_hash(hash_value);
+ bucket = data_.bucket_ptr_from_hash(hash_value);
// Nothing after this point can throw.
@@ -1749,7 +1761,7 @@
for (; i != j; ++i) {
// No side effects in this initial code
size_type hash_value = hash_function()(extract_key(*i));
- bucket_ptr bucket = data_.bucket_from_hash(hash_value);
+ bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
link_ptr pos = find_iterator(bucket, extract_key(*i));
if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
@@ -1764,7 +1776,7 @@
// throws, strong otherwise.
if(size() + 1 >= max_load_) {
reserve(size() + insert_size(i, j));
- bucket = data_.bucket_from_hash(hash_value);
+ bucket = data_.bucket_ptr_from_hash(hash_value);
}
// Nothing after this point can throw.
@@ -2042,4 +2054,3 @@
#undef BOOST_UNORDERED_CONST_ITERATOR
#undef BOOST_UNORDERED_LOCAL_ITERATOR
#undef BOOST_UNORDERED_CONST_LOCAL_ITERATOR
-