|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r73755 - trunk/boost/unordered/detail
From: dnljms_at_[hidden]
Date: 2011-08-14 14:53:04
Author: danieljames
Date: 2011-08-14 14:53:03 EDT (Sun, 14 Aug 2011)
New Revision: 73755
URL: http://svn.boost.org/trac/boost/changeset/73755
Log:
Unordered: Move some of the unordered implementation.
Text files modified:
trunk/boost/unordered/detail/buckets.hpp | 103 ++++++++++++++++++++++++++++
trunk/boost/unordered/detail/table.hpp | 140 ++++++----------------------------------
2 files changed, 121 insertions(+), 122 deletions(-)
Modified: trunk/boost/unordered/detail/buckets.hpp
==============================================================================
--- trunk/boost/unordered/detail/buckets.hpp (original)
+++ trunk/boost/unordered/detail/buckets.hpp 2011-08-14 14:53:03 EDT (Sun, 14 Aug 2011)
@@ -64,6 +64,7 @@
bucket_ptr buckets_;
std::size_t bucket_count_;
+ std::size_t size_;
::boost::compressed_pair<bucket_allocator, node_allocator> allocators_;
// Data access
@@ -100,6 +101,7 @@
buckets(node_allocator const& a, std::size_t bucket_count)
: buckets_(),
bucket_count_(bucket_count),
+ size_(),
allocators_(a,a)
{
}
@@ -109,6 +111,7 @@
buckets(buckets& b, move_tag)
: buckets_(),
bucket_count_(b.bucket_count_),
+ size_(),
allocators_(b.allocators_)
{
}
@@ -138,6 +141,7 @@
BOOST_ASSERT(node_alloc() == other.node_alloc());
std::swap(buckets_, other.buckets_);
std::swap(bucket_count_, other.bucket_count_);
+ std::swap(size_, other.size_);
}
void swap(buckets& other, true_type)
@@ -145,6 +149,7 @@
allocators_.swap(other.allocators_);
std::swap(buckets_, other.buckets_);
std::swap(bucket_count_, other.bucket_count_);
+ std::swap(size_, other.size_);
}
void move(buckets& other)
@@ -153,13 +158,15 @@
if(this->buckets_) { this->delete_buckets(); }
this->buckets_ = other.buckets_;
this->bucket_count_ = other.bucket_count_;
+ this->size_ = other.size_;
other.buckets_ = bucket_ptr();
other.bucket_count_ = 0;
+ other.size_ = 0;
}
std::size_t bucket_size(std::size_t index) const
{
- if (!this->buckets_) return 0;
+ if (!this->size_) return 0;
node_ptr ptr = this->buckets_[index].next_;
if (!ptr) return 0;
ptr = ptr->next_;
@@ -177,7 +184,7 @@
node_ptr bucket_begin(std::size_t bucket_index) const
{
- if (!this->buckets_) return node_ptr();
+ if (!this->size_) return node_ptr();
bucket& b = this->buckets_[bucket_index];
if (!b.next_) return node_ptr();
return b.next_->next_;
@@ -190,6 +197,13 @@
return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
}
+ float load_factor() const
+ {
+ BOOST_ASSERT(this->bucket_count_ != 0);
+ return static_cast<float>(this->size_)
+ / static_cast<float>(this->bucket_count_);
+ }
+
////////////////////////////////////////////////////////////////////////
// Delete
@@ -201,12 +215,13 @@
::boost::unordered::detail::destroy(raw_ptr->value_ptr());
allocator_traits<node_allocator>::destroy(node_alloc(), raw_ptr);
allocator_traits<node_allocator>::deallocate(node_alloc(), real_ptr, 1);
+
+ --this->size_;
}
void delete_buckets()
{
bucket_ptr end = this->get_bucket(this->bucket_count_);
-
node_ptr n = (end)->next_;
while(BOOST_UNORDERED_BORLAND_BOOL(n))
{
@@ -224,6 +239,7 @@
allocator_traits<bucket_allocator>::deallocate(bucket_alloc(), this->buckets_, this->bucket_count_ + 1);
this->buckets_ = bucket_ptr();
+ BOOST_ASSERT(this->size_ == 0);
}
std::size_t delete_nodes(node_ptr begin, node_ptr end)
@@ -238,6 +254,57 @@
return count;
}
+ void clear()
+ {
+ if(!this->size_) return;
+
+ bucket_ptr end = this->get_bucket(this->bucket_count_);
+
+ node_ptr n = (end)->next_;
+ while(BOOST_UNORDERED_BORLAND_BOOL(n))
+ {
+ node_ptr node_to_delete = n;
+ n = n->next_;
+ this->delete_node(node_to_delete);
+ }
+
+ ++end;
+ for(bucket_ptr begin = this->buckets_; begin != end; ++begin) {
+ begin->next_ = bucket_ptr();
+ }
+
+ this->size_ = 0;
+ }
+
+ node_ptr erase(node_ptr r)
+ {
+ BOOST_ASSERT(r);
+ node_ptr next = r->next_;
+
+ bucket_ptr bucket = this->get_bucket(
+ node::get_hash(r) % this->bucket_count_);
+ node_ptr prev = node::unlink_node(*bucket, r);
+
+ this->fix_buckets(bucket, prev, next);
+
+ this->delete_node(r);
+
+ return next;
+ }
+
+ node_ptr erase_range(node_ptr r1, node_ptr r2)
+ {
+ if (r1 == r2) return r2;
+
+ std::size_t bucket_index = node::get_hash(r1) % this->bucket_count_;
+ node_ptr prev = node::unlink_nodes(
+ this->buckets_[bucket_index], r1, r2);
+ this->fix_buckets_range(bucket_index, prev, r1, r2);
+ this->delete_nodes(r1, r2);
+
+ return r2;
+ }
+
// This is called after erasing a node or group of nodes to fix up
// the bucket pointers.
void fix_buckets(bucket_ptr bucket, node_ptr prev, node_ptr next)
@@ -324,6 +391,7 @@
void copy_buckets_to(buckets&) const;
void move_buckets_to(buckets&) const;
+ void rehash_impl(std::size_t);
};
// Assigning and swapping the equality and hash function objects
@@ -643,12 +711,14 @@
node_ptr first_node = a.release();
node::set_hash(first_node, hash);
node_ptr end = prev->next_ = first_node;
+ ++dst.size_;
for(n = n->next_; n != group_end; n = n->next_) {
a.construct(node::get_value(n));
end = a.release();
node::set_hash(end, hash);
node::add_after_node(end, first_node);
+ ++dst.size_;
}
prev = dst.place_in_bucket(prev, end);
@@ -690,12 +760,39 @@
end = a.release();
node::set_hash(end, hash);
node::add_after_node(end, first_node);
+ ++dst.size_;
}
prev = dst.place_in_bucket(prev, end);
}
}
}
+
+ // strong otherwise exception safety
+ template <class A, bool Unique>
+ void buckets<A, Unique>::rehash_impl(std::size_t num_buckets)
+ {
+ BOOST_ASSERT(this->size_);
+
+ buckets dst(this->node_alloc(), num_buckets);
+ dst.create_buckets();
+
+ bucket_ptr src_start = this->get_bucket(this->bucket_count_);
+ bucket_ptr dst_start = dst.get_bucket(dst.bucket_count_);
+
+ dst_start->next_ = src_start->next_;
+ src_start->next_ = bucket_ptr();
+ dst.size_ = this->size_;
+ this->size_ = 0;
+
+ node_ptr prev = dst_start;
+ while (BOOST_UNORDERED_BORLAND_BOOL(prev->next_))
+ prev = dst.place_in_bucket(prev, node::next_group2(prev));
+
+ // Swap the new nodes back into the container and setup the
+ // variables.
+ dst.swap(*this); // no throw
+ }
}}}
#endif
Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp (original)
+++ trunk/boost/unordered/detail/table.hpp 2011-08-14 14:53:03 EDT (Sun, 14 Aug 2011)
@@ -42,7 +42,6 @@
// Members
- std::size_t size_;
float mlf_;
std::size_t max_load_;
@@ -92,7 +91,7 @@
{
if (!this->size_) return node_ptr();
std::size_t hash = hash_function(k);
- return find_node_impl(hash % this->bucket_count_, hash, k, eq);
+ return this->find_node_impl(hash % this->bucket_count_, hash, k, eq);
}
node_ptr find_node(
@@ -101,14 +100,14 @@
key_type const& k) const
{
if (!this->size_) return node_ptr();
- return find_node_impl(bucket_index, hash, k, this->key_eq());
+ return this->find_node_impl(bucket_index, hash, k, this->key_eq());
}
node_ptr find_node(key_type const& k) const
{
if (!this->size_) return node_ptr();
std::size_t hash = this->hash_function()(k);
- return find_node_impl(hash % this->bucket_count_, hash, k,
+ return this->find_node_impl(hash % this->bucket_count_, hash, k,
this->key_eq());
}
@@ -167,13 +166,6 @@
return next_prime(double_to_size_t(floor(size / (double) mlf_)) + 1);
}
- float load_factor() const
- {
- BOOST_ASSERT(this->bucket_count_ != 0);
- return static_cast<float>(this->size_)
- / static_cast<float>(this->bucket_count_);
- }
-
////////////////////////////////////////////////////////////////////////
// Constructors
@@ -183,7 +175,6 @@
node_allocator const& a)
: buckets(a, next_prime(num_buckets)),
functions(hf, eq),
- size_(),
mlf_(1.0f),
max_load_(0)
{
@@ -192,7 +183,6 @@
table(table const& x, node_allocator const& a)
: buckets(a, x.min_buckets_for_size(x.size_)),
functions(x),
- size_(x.size_),
mlf_(x.mlf_),
max_load_(0)
{
@@ -205,7 +195,6 @@
table(table& x, move_tag m)
: buckets(x, m),
functions(x),
- size_(0),
mlf_(1.0f),
max_load_(0)
{
@@ -215,7 +204,6 @@
table(table& x, node_allocator const& a, move_tag m)
: buckets(a, x.bucket_count_),
functions(x),
- size_(0),
mlf_(x.mlf_),
max_load_(0)
{
@@ -225,9 +213,8 @@
else if(x.size_) {
// Use a temporary table because move_buckets_to leaves the
// source container in a complete mess.
- table tmp(x, m);
+ buckets tmp(x, m);
tmp.move_buckets_to(*this);
- this->size_ = tmp.size_;
this->max_load_ = calculate_max_load();
}
}
@@ -257,30 +244,30 @@
if(this->node_alloc() == x.node_alloc()) {
this->buckets::move(x); // no throw
- this->size_ = x.size_;
+ this->mlf_ = x.mlf_;
this->max_load_ = x.max_load_;
- x.size_ = 0;
}
else {
// Create new buckets in separate buckets
// which will clean up if anything throws an exception.
buckets b(this->node_alloc(), x.min_buckets_for_size(x.size_));
+
if (x.size_) {
// Use a temporary table because move_buckets_to leaves the
// source container in a complete mess.
- table tmp(x, move_tag());
+ buckets tmp(x, move_tag());
tmp.move_buckets_to(b);
+ b.swap(*this);
+ this->mlf_ = x.mlf_;
+ this->max_load_ = calculate_max_load();
+ }
+ else {
+ b.swap(*this);
+ this->mlf_ = x.mlf_;
}
-
- // Start updating the data here, no throw from now on.
- this->size_ = x.size_;
- b.swap(*this);
- this->max_load_ = x.size_ ? calculate_max_load() : 0;
}
- // We've made it, the rest is no throw.
- this->mlf_ = x.mlf_;
new_func_this.commit();
}
@@ -304,7 +291,6 @@
op2.commit();
}
- std::swap(this->size_, x.size_);
std::swap(this->mlf_, x.mlf_);
std::swap(this->max_load_, x.max_load_);
}
@@ -326,7 +312,6 @@
void partial_swap(table& x)
{
this->buckets::swap(x, false_type());
- std::swap(this->size_, x.size_);
std::swap(this->mlf_, x.mlf_);
std::swap(this->max_load_, x.max_load_);
}
@@ -365,28 +350,6 @@
//
// no throw
- void clear()
- {
- if(!this->size_) return;
-
- bucket_ptr end = this->get_bucket(this->bucket_count_);
-
- node_ptr n = (end)->next_;
- while(BOOST_UNORDERED_BORLAND_BOOL(n))
- {
- node_ptr node_to_delete = n;
- n = n->next_;
- this->delete_node(node_to_delete);
- }
-
- ++end;
- for(bucket_ptr begin = this->buckets_; begin != end; ++begin) {
- begin->next_ = bucket_ptr();
- }
-
- this->size_ = 0;
- }
-
std::size_t erase_key(key_type const& k)
{
if(!this->size_) return 0;
@@ -413,50 +376,14 @@
node_ptr pos = prev->next_;
node_ptr end = node::next_group(pos);
prev->next_ = end;
-
this->fix_buckets(bucket, prev, end);
-
- std::size_t count = this->delete_nodes(pos, end);
- this->size_ -= count;
-
- return count;
- }
-
- node_ptr erase(node_ptr r)
- {
- BOOST_ASSERT(r);
- node_ptr next = r->next_;
-
- bucket_ptr bucket = this->get_bucket(
- node::get_hash(r) % this->bucket_count_);
- node_ptr prev = node::unlink_node(*bucket, r);
-
- this->fix_buckets(bucket, prev, next);
-
- this->delete_node(r);
- --this->size_;
-
- return next;
- }
-
- node_ptr erase_range(node_ptr r1, node_ptr r2)
- {
- if (r1 == r2) return r2;
-
- std::size_t bucket_index = node::get_hash(r1) % this->bucket_count_;
- node_ptr prev = node::unlink_nodes(
- this->buckets_[bucket_index], r1, r2);
- this->fix_buckets_range(bucket_index, prev, r1, r2);
- this->size_ -= this->delete_nodes(r1, r2);
-
- return r2;
+ return this->delete_nodes(pos, end);
}
// Reserve and rehash
bool reserve_for_insert(std::size_t);
void rehash(std::size_t);
- void rehash_impl(std::size_t);
};
////////////////////////////////////////////////////////////////////////////
@@ -480,7 +407,8 @@
= this->min_buckets_for_size((std::max)(size,
this->size_ + (this->size_ >> 1)));
if (num_buckets != this->bucket_count_) {
- rehash_impl(num_buckets);
+ this->rehash_impl(num_buckets);
+ this->max_load_ = calculate_max_load();
return true;
}
}
@@ -506,39 +434,13 @@
// no throw:
min_buckets = next_prime((std::max)(min_buckets,
double_to_size_t(floor(this->size_ / (double) mlf_)) + 1));
- if(min_buckets != this->bucket_count_) rehash_impl(min_buckets);
+ if(min_buckets != this->bucket_count_) {
+ this->rehash_impl(min_buckets);
+ this->max_load_ = calculate_max_load();
+ }
}
}
- // strong otherwise exception safety
- template <class T>
- void table<T>::rehash_impl(std::size_t num_buckets)
- {
- std::size_t size = this->size_;
- BOOST_ASSERT(size);
-
- buckets dst(this->node_alloc(), num_buckets);
- dst.create_buckets();
-
- bucket_ptr src_start = this->get_bucket(this->bucket_count_);
- bucket_ptr dst_start = dst.get_bucket(dst.bucket_count_);
-
- dst_start->next_ = src_start->next_;
- src_start->next_ = bucket_ptr();
- // No need to do this, since the following is 'no throw'.
- //this->size_ = 0;
-
- node_ptr prev = dst_start;
- while (BOOST_UNORDERED_BORLAND_BOOL(prev->next_))
- prev = dst.place_in_bucket(prev, node::next_group2(prev));
-
- // Swap the new nodes back into the container and setup the
- // variables.
- dst.swap(*this); // no throw
- this->size_ = size;
- this->max_load_ = calculate_max_load();
- }
-
////////////////////////////////////////////////////////////////////////////
//
// types
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk