Subject: [Boost-commit] svn:boost r81207 - trunk/boost/unordered/detail
From: dnljms_at_[hidden]
Date: 2012-11-05 13:33:00
Author: danieljames
Date: 2012-11-05 13:32:59 EST (Mon, 05 Nov 2012)
New Revision: 81207
URL: http://svn.boost.org/trac/boost/changeset/81207
Log:
Unordered: Simpler erase implementation.
Text files modified:
trunk/boost/unordered/detail/equivalent.hpp | 151 ++++++++++++---------------------------
trunk/boost/unordered/detail/table.hpp | 121 +++++++++----------------------
trunk/boost/unordered/detail/unique.hpp | 55 +++++---------
3 files changed, 102 insertions(+), 225 deletions(-)
Modified: trunk/boost/unordered/detail/equivalent.hpp
==============================================================================
--- trunk/boost/unordered/detail/equivalent.hpp (original)
+++ trunk/boost/unordered/detail/equivalent.hpp 2012-11-05 13:32:59 EST (Mon, 05 Nov 2012)
@@ -545,9 +545,7 @@
std::size_t key_hash = this->hash(k);
std::size_t bucket_index =
policy::to_bucket(this->bucket_count_, key_hash);
- bucket_pointer this_bucket = this->get_bucket(bucket_index);
-
- link_pointer prev = this_bucket->next_;
+ link_pointer prev = this->get_previous_start(bucket_index);
if (!prev) return 0;
for (;;)
@@ -565,13 +563,12 @@
prev = static_cast<node_pointer>(prev->next_)->group_prev_;
}
- node_pointer pos = static_cast<node_pointer>(prev->next_);
- link_pointer end1 =
- static_cast<node_pointer>(pos->group_prev_)->next_;
- node_pointer end = static_cast<node_pointer>(end1);
- prev->next_ = end1;
- this->fix_buckets(this_bucket, prev, end);
- return this->delete_nodes(c_iterator(pos), c_iterator(end));
+ node_pointer first_node = static_cast<node_pointer>(prev->next_);
+ link_pointer end = static_cast<node_pointer>(first_node->group_prev_)->next_;
+
+ std::size_t count = this->delete_nodes(prev, end);
+ this->fix_bucket(bucket_index, prev);
+ return count;
}
iterator erase(c_iterator r)
@@ -579,128 +576,74 @@
BOOST_ASSERT(r.node_);
iterator next(r.node_);
++next;
-
- bucket_pointer this_bucket = this->get_bucket(
- policy::to_bucket(this->bucket_count_, r.node_->hash_));
- link_pointer prev = unlink_node(*this_bucket, r.node_);
-
- this->fix_buckets(this_bucket, prev, next.node_);
-
- this->delete_node(r);
-
+ erase_nodes(r.node_, next.node_);
return next;
}
iterator erase_range(c_iterator r1, c_iterator r2)
{
if (r1 == r2) return iterator(r2.node_);
-
- std::size_t bucket_index =
- policy::to_bucket(this->bucket_count_, r1.node_->hash_);
- link_pointer prev = unlink_nodes(
- *this->get_bucket(bucket_index), r1.node_, r2.node_);
- this->fix_buckets_range(bucket_index, prev, r1.node_, r2.node_);
- this->delete_nodes(r1, r2);
-
+ erase_nodes(r1.node_, r2.node_);
return iterator(r2.node_);
}
- static link_pointer unlink_node(bucket& b, node_pointer n)
+ link_pointer erase_nodes(node_pointer begin, node_pointer end)
{
- node_pointer next = static_cast<node_pointer>(n->next_);
- link_pointer prev = n->group_prev_;
-
- if(prev->next_ != n) {
- // The node is at the beginning of a group.
+ std::size_t bucket_index =
+ policy::to_bucket(this->bucket_count_, begin->hash_);
- // Find the previous node pointer:
- prev = b.next_;
- while(prev->next_ != n) {
+ // Split the groups containing 'begin' and 'end'.
+ // And get the pointer to the node before begin while
+ // we're at it.
+ link_pointer prev = split_groups(begin, end);
+
+ // If we don't have a 'prev' it means that begin is at the
+ // beginning of a block, so search through the blocks in the
+ // same bucket.
+ if (!prev) {
+ prev = this->get_previous_start(bucket_index);
+ while (prev->next_ != begin)
prev = static_cast<node_pointer>(prev->next_)->group_prev_;
- }
-
- // Remove from group
- if (next && next->group_prev_ == n)
- {
- next->group_prev_ = n->group_prev_;
- }
- }
- else if (next && next->group_prev_ == n)
- {
- // The deleted node is not at the end of the group, so
- // change the link from the next node.
- next->group_prev_ = n->group_prev_;
- }
- else {
- // The deleted node is at the end of the group, so the
- // first node in the group is pointing to it.
- // Find that to change its pointer.
- node_pointer x = static_cast<node_pointer>(n->group_prev_);
- while (x->group_prev_ != n) {
- x = static_cast<node_pointer>(x->group_prev_);
- }
- x->group_prev_ = n->group_prev_;
}
- prev->next_ = next;
+ // Delete the nodes.
+ do {
+ link_pointer group_end =
+ static_cast<node_pointer>(
+ static_cast<node_pointer>(prev->next_)->group_prev_)->next_;
+ this->delete_nodes(prev, group_end);
+ bucket_index = this->fix_bucket(bucket_index, prev);
+ } while(prev->next_ != end);
+
return prev;
}
- static link_pointer unlink_nodes(bucket& b,
- node_pointer begin, node_pointer end)
+ static link_pointer split_groups(node_pointer begin, node_pointer end)
{
- link_pointer prev = begin->group_prev_;
+ node_pointer prev = static_cast<node_pointer>(begin->group_prev_);
+ if (prev->next_ != begin) prev = node_pointer();
- if (prev->next_ != begin) {
- // The node is at the beginning of a group.
-
- // Find the previous node pointer:
- prev = b.next_;
- while (prev->next_ != begin)
- prev = static_cast<node_pointer>(prev->next_)->group_prev_;
+ if (end) {
+ node_pointer first = end;
+ while (first != begin && static_cast<node_pointer>(first->group_prev_)->next_ == first) {
+ first = static_cast<node_pointer>(first->group_prev_);
+ }
- if (end) split_group(end);
+ boost::swap(first->group_prev_, end->group_prev_);
+ if (first == begin) return prev;
}
- else {
- node_pointer group1 = split_group(begin);
-
- if (end) {
- node_pointer group2 = split_group(end);
- if(begin == group2) {
- link_pointer end1 = group1->group_prev_;
- link_pointer end2 = end->group_prev_;
- group1->group_prev_ = end2;
- end->group_prev_ = end1;
- }
+ if (prev) {
+ node_pointer first = prev;
+ while (static_cast<node_pointer>(first->group_prev_)->next_ == first) {
+ first = static_cast<node_pointer>(first->group_prev_);
}
+ boost::swap(first->group_prev_, begin->group_prev_);
}
- prev->next_ = end;
-
return prev;
}
- // Break a ciruclar list into two, with split as the beginning
- // of the second group (if split is at the beginning then don't
- // split).
- static node_pointer split_group(node_pointer split)
- {
- // Find first node in group.
- node_pointer first = split;
- while (static_cast<node_pointer>(first->group_prev_)->next_ ==
- first)
- first = static_cast<node_pointer>(first->group_prev_);
-
- if(first == split) return split;
-
- link_pointer last = first->group_prev_;
- first->group_prev_ = split->group_prev_;
- split->group_prev_ = last;
-
- return first;
- }
-
////////////////////////////////////////////////////////////////////////
// fill_buckets
Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp (original)
+++ trunk/boost/unordered/detail/table.hpp 2012-11-05 13:32:59 EST (Mon, 05 Nov 2012)
@@ -498,26 +498,29 @@
delete_buckets();
}
- void delete_node(c_iterator n)
+ void delete_node(link_pointer prev)
{
+ node_pointer n = static_cast<node_pointer>(prev->next_);
+ prev->next_ = n->next_;
+
boost::unordered::detail::destroy_value_impl(node_alloc(),
- n.node_->value_ptr());
+ n->value_ptr());
node_allocator_traits::destroy(node_alloc(),
- boost::addressof(*n.node_));
- node_allocator_traits::deallocate(node_alloc(), n.node_, 1);
+ boost::addressof(*n));
+ node_allocator_traits::deallocate(node_alloc(), n, 1);
--size_;
}
- std::size_t delete_nodes(c_iterator begin, c_iterator end)
+ std::size_t delete_nodes(link_pointer prev, link_pointer end)
{
+ BOOST_ASSERT(prev->next_ != end);
+
std::size_t count = 0;
- while(begin != end) {
- c_iterator n = begin;
- ++begin;
- delete_node(n);
+ do {
+ delete_node(prev);
++count;
- }
+ } while (prev->next_ != end);
return count;
}
@@ -525,7 +528,7 @@
void delete_buckets()
{
if(buckets_) {
- delete_nodes(begin(), iterator());
+ if (size_) delete_nodes(get_previous_start(), link_pointer());
if (bucket::extra_node) {
node_pointer n = static_cast<node_pointer>(
@@ -545,10 +548,9 @@
void clear()
{
- if(!size_) return;
+ if (!size_) return;
- delete_nodes(begin(), iterator());
- get_previous_start()->next_ = link_pointer();
+ delete_nodes(get_previous_start(), link_pointer());
clear_buckets();
BOOST_ASSERT(!size_);
@@ -577,86 +579,33 @@
}
////////////////////////////////////////////////////////////////////////
- // Fix buckets after erase
+ // Fix buckets after delete
+ //
- // This is called after erasing a node or group of nodes to fix up
- // the bucket pointers.
- void fix_buckets(bucket_pointer this_bucket,
- link_pointer prev, node_pointer next)
+ std::size_t fix_bucket(std::size_t bucket_index, link_pointer prev)
{
- if (!next)
- {
- if (this_bucket->next_ == prev)
- this_bucket->next_ = node_pointer();
- }
- else
+ link_pointer end = prev->next_;
+ std::size_t bucket_index2 = bucket_index;
+
+ if (end)
{
- bucket_pointer next_bucket = get_bucket(
- policy::to_bucket(bucket_count_, next->hash_));
+ bucket_index2 = policy::to_bucket(bucket_count_,
+ static_cast<node_pointer>(end)->hash_);
- if (next_bucket != this_bucket)
- {
- next_bucket->next_ = prev;
- if (this_bucket->next_ == prev)
- this_bucket->next_ = node_pointer();
- }
- }
- }
+ // If begin and end are in the same bucket, then
+ // there's nothing to do.
+ if (bucket_index == bucket_index2) return bucket_index2;
- // This is called after erasing a range of nodes to fix any bucket
- // pointers into that range.
- void fix_buckets_range(std::size_t bucket_index,
- link_pointer prev, node_pointer begin, node_pointer end)
- {
- node_pointer n = begin;
-
- // If we're not at the start of the current bucket, then
- // go to the start of the next bucket.
- if (get_bucket(bucket_index)->next_ != prev)
- {
- for(;;) {
- n = static_cast<node_pointer>(n->next_);
- if (n == end) {
- if (n) {
- std::size_t new_bucket_index =
- policy::to_bucket(bucket_count_, n->hash_);
- if (bucket_index != new_bucket_index) {
- get_bucket(new_bucket_index)->next_ = prev;
- }
- }
- return;
- }
-
- std::size_t new_bucket_index =
- policy::to_bucket(bucket_count_, n->hash_);
- if (bucket_index != new_bucket_index) {
- bucket_index = new_bucket_index;
- break;
- }
- }
+ // Update the bucket containing end.
+ get_bucket(bucket_index2)->next_ = prev;
}
- // Iterate through the remaining nodes, clearing out the bucket
- // pointers.
- get_bucket(bucket_index)->next_ = link_pointer();
- for(;;) {
- n = static_cast<node_pointer>(n->next_);
- if (n == end) break;
-
- std::size_t new_bucket_index =
- policy::to_bucket(bucket_count_, n->hash_);
- if (bucket_index != new_bucket_index) {
- bucket_index = new_bucket_index;
- get_bucket(bucket_index)->next_ = link_pointer();
- }
- };
+ // Check if this bucket is now empty.
+ bucket_pointer this_bucket = get_bucket(bucket_index);
+ if (this_bucket->next_ == prev)
+ this_bucket->next_ = link_pointer();
- // Finally fix the bucket containing the trailing node.
- if (n) {
- get_bucket(
- policy::to_bucket(bucket_count_, n->hash_))->next_
- = prev;
- }
+ return bucket_index2;
}
////////////////////////////////////////////////////////////////////////
Modified: trunk/boost/unordered/detail/unique.hpp
==============================================================================
--- trunk/boost/unordered/detail/unique.hpp (original)
+++ trunk/boost/unordered/detail/unique.hpp 2012-11-05 13:32:59 EST (Mon, 05 Nov 2012)
@@ -519,9 +519,7 @@
std::size_t key_hash = this->hash(k);
std::size_t bucket_index =
policy::to_bucket(this->bucket_count_, key_hash);
- bucket_pointer this_bucket = this->get_bucket(bucket_index);
-
- link_pointer prev = this_bucket->next_;
+ link_pointer prev = this->get_previous_start(bucket_index);
if (!prev) return 0;
for (;;)
@@ -539,11 +537,11 @@
prev = prev->next_;
}
- node_pointer pos = static_cast<node_pointer>(prev->next_);
- node_pointer end = static_cast<node_pointer>(pos->next_);
- prev->next_ = pos->next_;
- this->fix_buckets(this_bucket, prev, end);
- return this->delete_nodes(c_iterator(pos), c_iterator(end));
+ link_pointer end = static_cast<node_pointer>(prev->next_)->next_;
+
+ std::size_t count = this->delete_nodes(prev, end);
+ this->fix_bucket(bucket_index, prev);
+ return count;
}
iterator erase(c_iterator r)
@@ -551,44 +549,31 @@
BOOST_ASSERT(r.node_);
iterator next(r.node_);
++next;
-
- bucket_pointer this_bucket = this->get_bucket(
- policy::to_bucket(this->bucket_count_, r.node_->hash_));
- link_pointer prev = unlink_node(*this_bucket, r.node_);
-
- this->fix_buckets(this_bucket, prev, next.node_);
-
- this->delete_node(r);
-
+ erase_nodes(r.node_, next.node_);
return next;
}
iterator erase_range(c_iterator r1, c_iterator r2)
{
if (r1 == r2) return iterator(r2.node_);
-
- std::size_t bucket_index =
- policy::to_bucket(this->bucket_count_, r1.node_->hash_);
- link_pointer prev = unlink_nodes(
- *this->get_bucket(bucket_index), r1.node_, r2.node_);
- this->fix_buckets_range(bucket_index, prev, r1.node_, r2.node_);
- this->delete_nodes(r1, r2);
-
+ erase_nodes(r1.node_, r2.node_);
return iterator(r2.node_);
}
- static link_pointer unlink_node(bucket& b, node_pointer n)
+ void erase_nodes(node_pointer begin, node_pointer end)
{
- return unlink_nodes(b, n, static_cast<node_pointer>(n->next_));
- }
+ std::size_t bucket_index =
+ policy::to_bucket(this->bucket_count_, begin->hash_);
- static link_pointer unlink_nodes(bucket& b,
- node_pointer begin, node_pointer end)
- {
- link_pointer prev = b.next_;
- while (prev->next_ != begin) prev = prev->next_;
- prev->next_ = end;
- return prev;
+ // Find the node before begin.
+ link_pointer prev = this->get_previous_start(bucket_index);
+ while(prev->next_ != begin) prev = prev->next_;
+
+ // Delete the nodes.
+ do {
+ this->delete_node(prev);
+ bucket_index = this->fix_bucket(bucket_index, prev);
+ } while (prev->next_ != end);
}
////////////////////////////////////////////////////////////////////////