From: daniel_james_at_[hidden]
Date: 2008-04-21 15:19:51
Author: danieljames
Date: 2008-04-21 15:19:50 EDT (Mon, 21 Apr 2008)
New Revision: 44703
URL: http://svn.boost.org/trac/boost/changeset/44703
Log:
Merge latest changes from trunk.
Merged revisions 44616-44702 via svnmerge from
https://svn.boost.org/svn/boost/trunk
........
r44650 | danieljames | 2008-04-20 22:08:57 +0100 (Sun, 20 Apr 2008) | 1 line
Update an include.
........
r44697 | danieljames | 2008-04-21 16:55:40 +0100 (Mon, 21 Apr 2008) | 1 line
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.
........
Properties modified:
branches/unordered/trunk/ (props changed)
Text files modified:
branches/unordered/trunk/boost/unordered/detail/hash_table.hpp | 27 +++++++++++++
branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp | 79 ++++++++++++++++++++++-----------------
branches/unordered/trunk/libs/unordered/test/objects/memory.hpp | 2
3 files changed, 72 insertions(+), 36 deletions(-)
Modified: branches/unordered/trunk/boost/unordered/detail/hash_table.hpp
==============================================================================
--- branches/unordered/trunk/boost/unordered/detail/hash_table.hpp (original)
+++ branches/unordered/trunk/boost/unordered/detail/hash_table.hpp 2008-04-21 15:19:50 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: branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp (original)
+++ branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp 2008-04-21 15:19:50 EDT (Mon, 21 Apr 2008)
@@ -437,15 +437,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_);
@@ -454,7 +454,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_);
@@ -463,7 +463,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_);
@@ -471,19 +471,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();
}
}
@@ -495,15 +495,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_);
@@ -529,7 +531,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);
}
}
@@ -544,7 +547,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_);
}
@@ -555,17 +558,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
@@ -574,7 +586,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
@@ -1407,7 +1419,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));
}
@@ -1420,7 +1432,7 @@
// no throw
size_type bucket_count() const
{
- return data_.bucket_count_;
+ return data_.bucket_manager_.bucket_count();
}
// no throw
@@ -1456,7 +1468,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
@@ -1508,9 +1520,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:
@@ -1590,7 +1602,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_;
@@ -1616,7 +1628,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);
@@ -1700,13 +1712,13 @@
{
key_type const& k = extract_key(a.get()->value_);
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);
// 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.
@@ -1810,7 +1822,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))
@@ -1827,7 +1839,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.
@@ -1844,7 +1856,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)) {
@@ -1864,7 +1876,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.
@@ -1908,7 +1920,7 @@
// No side effects in this initial code
key_type const& k = extract_key(a.get()->value_);
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)) {
@@ -1919,7 +1931,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.
@@ -1973,7 +1985,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)) {
@@ -1988,7 +2000,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.
@@ -2266,4 +2278,3 @@
#undef BOOST_UNORDERED_CONST_ITERATOR
#undef BOOST_UNORDERED_LOCAL_ITERATOR
#undef BOOST_UNORDERED_CONST_LOCAL_ITERATOR
-
Modified: branches/unordered/trunk/libs/unordered/test/objects/memory.hpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/objects/memory.hpp (original)
+++ branches/unordered/trunk/libs/unordered/test/objects/memory.hpp 2008-04-21 15:19:50 EDT (Mon, 21 Apr 2008)
@@ -10,7 +10,7 @@
#include <map>
#include <boost/mpl/apply.hpp>
#include <boost/assert.hpp>
-#include <boost/unordered/detail/allocator.hpp>
+#include <boost/unordered/detail/allocator_helpers.hpp>
#include <boost/mpl/aux_/config/eti.hpp>
#include "../helpers/test.hpp"