|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r81358 - in branches/release: . boost boost/unordered boost/unordered/detail
From: dnljms_at_[hidden]
Date: 2012-11-15 08:43:39
Author: danieljames
Date: 2012-11-15 08:43:37 EST (Thu, 15 Nov 2012)
New Revision: 81358
URL: http://svn.boost.org/trac/boost/changeset/81358
Log:
Unordered: Merge code clean up.
Properties modified:
branches/release/ (props changed)
branches/release/boost/ (props changed)
branches/release/boost/unordered/ (props changed)
Text files modified:
branches/release/boost/unordered/detail/buckets.hpp | 142 ++++++++++++----------
branches/release/boost/unordered/detail/equivalent.hpp | 249 +++++++++++++--------------------------
branches/release/boost/unordered/detail/extract_key.hpp | 16 +-
branches/release/boost/unordered/detail/table.hpp | 153 ++++++++----------------
branches/release/boost/unordered/detail/unique.hpp | 106 ++++++----------
branches/release/boost/unordered/unordered_map.hpp | 6
branches/release/boost/unordered/unordered_set.hpp | 6
7 files changed, 263 insertions(+), 415 deletions(-)
Modified: branches/release/boost/unordered/detail/buckets.hpp
==============================================================================
--- branches/release/boost/unordered/detail/buckets.hpp (original)
+++ branches/release/boost/unordered/detail/buckets.hpp 2012-11-15 08:43:37 EST (Thu, 15 Nov 2012)
@@ -37,49 +37,50 @@
//
// all no throw
- template <typename NodePointer, typename Value> struct iterator;
- template <typename ConstNodePointer, typename NodePointer,
- typename Value> struct c_iterator;
- template <typename NodePointer, typename Value, typename Policy>
- struct l_iterator;
- template <typename ConstNodePointer, typename NodePointer,
- typename Value, typename Policy> struct cl_iterator;
+ template <typename Node> struct iterator;
+ template <typename Node, typename ConstNodePointer> struct c_iterator;
+ template <typename Node, typename Policy> struct l_iterator;
+ template <typename Node, typename ConstNodePointer, typename Policy>
+ struct cl_iterator;
// Local Iterators
//
// all no throw
- template <typename NodePointer, typename Value, typename Policy>
+ template <typename Node, typename Policy>
struct l_iterator
: public boost::iterator<
- std::forward_iterator_tag, Value, std::ptrdiff_t,
- NodePointer, Value&>
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ typename Node::node_pointer,
+ typename Node::value_type&>
{
#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
- template <typename ConstNodePointer, typename NodePointer2,
- typename Value2, typename Policy2>
+ template <typename Node2, typename ConstNodePointer, typename Policy2>
friend struct boost::unordered::iterator_detail::cl_iterator;
private:
#endif
- typedef NodePointer node_pointer;
- typedef boost::unordered::iterator_detail::iterator<NodePointer, Value>
- iterator;
+ typedef typename Node::node_pointer node_pointer;
+ typedef boost::unordered::iterator_detail::iterator<Node> iterator;
node_pointer ptr_;
std::size_t bucket_;
std::size_t bucket_count_;
public:
+ typedef typename Node::value_type value_type;
+
l_iterator() : ptr_() {}
l_iterator(iterator x, std::size_t b, std::size_t c)
: ptr_(x.node_), bucket_(b), bucket_count_(c) {}
- Value& operator*() const {
+ value_type& operator*() const {
return ptr_->value();
}
- Value* operator->() const {
+ value_type* operator->() const {
return ptr_->value_ptr();
}
@@ -106,42 +107,44 @@
}
};
- template <typename ConstNodePointer, typename NodePointer, typename Value,
- typename Policy>
+ template <typename Node, typename ConstNodePointer, typename Policy>
struct cl_iterator
: public boost::iterator<
- std::forward_iterator_tag, Value, std::ptrdiff_t,
- ConstNodePointer, Value const&>
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ ConstNodePointer,
+ typename Node::value_type const&>
{
friend struct boost::unordered::iterator_detail::l_iterator
- <NodePointer, Value, Policy>;
+ <Node, Policy>;
private:
- typedef NodePointer node_pointer;
- typedef boost::unordered::iterator_detail::iterator<NodePointer, Value>
- iterator;
+ typedef typename Node::node_pointer node_pointer;
+ typedef boost::unordered::iterator_detail::iterator<Node> iterator;
node_pointer ptr_;
std::size_t bucket_;
std::size_t bucket_count_;
public:
+ typedef typename Node::value_type value_type;
+
cl_iterator() : ptr_() {}
cl_iterator(iterator x, std::size_t b, std::size_t c) :
ptr_(x.node_), bucket_(b), bucket_count_(c) {}
cl_iterator(boost::unordered::iterator_detail::l_iterator<
- NodePointer, Value, Policy> const& x) :
+ Node, Policy> const& x) :
ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_)
{}
- Value const&
- operator*() const {
+ value_type const& operator*() const {
return ptr_->value();
}
- Value const* operator->() const {
+ value_type const* operator->() const {
return ptr_->value_ptr();
}
@@ -168,18 +171,21 @@
}
};
- template <typename NodePointer, typename Value>
+ template <typename Node>
struct iterator
: public boost::iterator<
- std::forward_iterator_tag, Value, std::ptrdiff_t,
- NodePointer, Value&>
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ typename Node::node_pointer,
+ typename Node::value_type&>
{
#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
- template <typename, typename, typename>
+ template <typename, typename>
friend struct boost::unordered::iterator_detail::c_iterator;
- template <typename, typename, typename>
+ template <typename, typename>
friend struct boost::unordered::iterator_detail::l_iterator;
- template <typename, typename, typename, typename>
+ template <typename, typename, typename>
friend struct boost::unordered::iterator_detail::cl_iterator;
template <typename>
friend struct boost::unordered::detail::table;
@@ -189,20 +195,23 @@
friend struct boost::unordered::detail::grouped_table_impl;
private:
#endif
- typedef NodePointer node_pointer;
+ typedef typename Node::node_pointer node_pointer;
node_pointer node_;
public:
+ typedef typename Node::value_type value_type;
+
iterator() : node_() {}
- explicit iterator(node_pointer const& x) : node_(x) {}
+ explicit iterator(typename Node::link_pointer x) :
+ node_(static_cast<node_pointer>(x)) {}
- Value& operator*() const {
+ value_type& operator*() const {
return node_->value();
}
- Value* operator->() const {
+ value_type* operator->() const {
return &node_->value();
}
@@ -226,14 +235,16 @@
}
};
- template <typename ConstNodePointer, typename NodePointer, typename Value>
+ template <typename Node, typename ConstNodePointer>
struct c_iterator
: public boost::iterator<
- std::forward_iterator_tag, Value, std::ptrdiff_t,
- ConstNodePointer, Value const&>
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ ConstNodePointer,
+ typename Node::value_type const&>
{
- friend struct boost::unordered::iterator_detail::iterator<
- NodePointer, Value>;
+ friend struct boost::unordered::iterator_detail::iterator<Node>;
#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
template <typename>
@@ -245,26 +256,26 @@
private:
#endif
-
- typedef NodePointer node_pointer;
- typedef boost::unordered::iterator_detail::iterator<NodePointer, Value>
- iterator;
+ typedef typename Node::node_pointer node_pointer;
+ typedef boost::unordered::iterator_detail::iterator<Node> iterator;
node_pointer node_;
public:
+ typedef typename Node::value_type value_type;
+
c_iterator() : node_() {}
- explicit c_iterator(node_pointer const& x) : node_(x) {}
+ explicit c_iterator(typename Node::link_pointer x) :
+ node_(static_cast<node_pointer>(x)) {}
- c_iterator(boost::unordered::iterator_detail::iterator<
- NodePointer, Value> const& x) : node_(x.node_) {}
+ c_iterator(iterator const& x) : node_(x.node_) {}
- Value const& operator*() const {
+ value_type const& operator*() const {
return node_->value();
}
- Value const* operator->() const {
+ value_type const* operator->() const {
return &node_->value();
}
@@ -398,7 +409,7 @@
node_allocator_traits::construct(alloc_,
boost::addressof(*node_), node());
- node_->init(static_cast<typename node::link_pointer>(node_));
+ node_->init(node_);
node_constructed_ = true;
}
else {
@@ -432,8 +443,7 @@
typedef typename node_allocator_traits::pointer node_pointer;
typedef typename node::value_type value_type;
typedef typename node::link_pointer link_pointer;
- typedef boost::unordered::iterator_detail::
- iterator<node_pointer, value_type> iterator;
+ typedef boost::unordered::iterator_detail::iterator<node> iterator;
node_pointer nodes_;
@@ -445,7 +455,7 @@
nodes_()
{
if (b.size_) {
- typename Table::previous_pointer prev = b.get_previous_start();
+ typename Table::link_pointer prev = b.get_previous_start();
nodes_ = static_cast<node_pointer>(prev->next_);
prev->next_ = link_pointer();
b.size_ = 0;
@@ -484,7 +494,7 @@
assign_impl(v);
node_pointer p = nodes_;
nodes_ = static_cast<node_pointer>(p->next_);
- p->init(static_cast<typename node::link_pointer>(p));
+ p->init(p);
p->next_ = link_pointer();
return p;
}
@@ -500,7 +510,7 @@
move_assign_impl(v);
node_pointer p = nodes_;
nodes_ = static_cast<node_pointer>(p->next_);
- p->init(static_cast<typename node::link_pointer>(p));
+ p->init(p);
p->next_ = link_pointer();
return p;
}
@@ -537,12 +547,12 @@
template <typename NodePointer>
struct bucket
{
- typedef NodePointer previous_pointer;
- previous_pointer next_;
+ typedef NodePointer link_pointer;
+ link_pointer next_;
bucket() : next_() {}
- previous_pointer first_from_start()
+ link_pointer first_from_start()
{
return next_;
}
@@ -552,12 +562,12 @@
struct ptr_bucket
{
- typedef ptr_bucket* previous_pointer;
- previous_pointer next_;
+ typedef ptr_bucket* link_pointer;
+ link_pointer next_;
ptr_bucket() : next_(0) {}
- previous_pointer first_from_start()
+ link_pointer first_from_start()
{
return this;
}
@@ -568,8 +578,6 @@
///////////////////////////////////////////////////////////////////
//
// Hash Policy
- //
- // Don't really want table to derive from this, but will for now.
template <typename SizeT>
struct prime_policy
Modified: branches/release/boost/unordered/detail/equivalent.hpp
==============================================================================
--- branches/release/boost/unordered/detail/equivalent.hpp (original)
+++ branches/release/boost/unordered/detail/equivalent.hpp 2012-11-15 08:43:37 EST (Thu, 15 Nov 2012)
@@ -25,10 +25,13 @@
boost::unordered::detail::value_base<T>
{
typedef typename ::boost::unordered::detail::rebind_wrap<
- A, grouped_node<A, T> >::type::pointer link_pointer;
+ A, grouped_node<A, T> >::type allocator;
+ typedef typename ::boost::unordered::detail::
+ allocator_traits<allocator>::pointer node_pointer;
+ typedef node_pointer link_pointer;
link_pointer next_;
- link_pointer group_prev_;
+ node_pointer group_prev_;
std::size_t hash_;
grouped_node() :
@@ -37,7 +40,7 @@
hash_(0)
{}
- void init(link_pointer self)
+ void init(node_pointer self)
{
group_prev_ = self;
}
@@ -52,9 +55,10 @@
boost::unordered::detail::ptr_bucket
{
typedef boost::unordered::detail::ptr_bucket bucket_base;
+ typedef grouped_ptr_node<T>* node_pointer;
typedef ptr_bucket* link_pointer;
- link_pointer group_prev_;
+ node_pointer group_prev_;
std::size_t hash_;
grouped_ptr_node() :
@@ -63,7 +67,7 @@
hash_(0)
{}
- void init(link_pointer self)
+ void init(node_pointer self)
{
group_prev_ = self;
}
@@ -181,7 +185,6 @@
typedef typename table::node_allocator_traits node_allocator_traits;
typedef typename table::bucket_pointer bucket_pointer;
typedef typename table::link_pointer link_pointer;
- typedef typename table::previous_pointer previous_pointer;
typedef typename table::hasher hasher;
typedef typename table::key_equal key_equal;
typedef typename table::key_type key_type;
@@ -234,8 +237,7 @@
Key const& k,
Pred const& eq) const
{
- std::size_t bucket_index =
- policy::to_bucket(this->bucket_count_, key_hash);
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
iterator n = this->begin(bucket_index);
for (;;)
@@ -250,13 +252,11 @@
}
else
{
- if (policy::to_bucket(this->bucket_count_, node_hash)
- != bucket_index)
+ if (this->hash_to_bucket(node_hash) != bucket_index)
return iterator();
}
- n = iterator(static_cast<node_pointer>(
- static_cast<node_pointer>(n.node_->group_prev_)->next_));
+ n = iterator(n.node_->group_prev_->next_);
}
}
@@ -268,7 +268,7 @@
std::size_t x = 0;
node_pointer it = n.node_;
do {
- it = static_cast<node_pointer>(it->group_prev_);
+ it = it->group_prev_;
++x;
} while(it != n.node_);
@@ -280,10 +280,7 @@
{
iterator n = this->find_node(k);
return std::make_pair(
- n, n.node_ ? iterator(
- static_cast<node_pointer>(
- static_cast<node_pointer>(n.node_->group_prev_)->next_
- )) : n);
+ n, n.node_ ? iterator(n.node_->group_prev_->next_) : n);
}
// Equality
@@ -296,10 +293,8 @@
{
iterator n2 = other.find_matching_node(n1);
if (!n2.node_) return false;
- iterator end1(static_cast<node_pointer>(
- static_cast<node_pointer>(n1.node_->group_prev_)->next_));
- iterator end2(static_cast<node_pointer>(
- static_cast<node_pointer>(n2.node_->group_prev_)->next_));
+ iterator end1(n1.node_->group_prev_->next_);
+ iterator end2(n2.node_->group_prev_->next_);
if (!group_equals(n1, end1, n2, end2)) return false;
n1 = end1;
}
@@ -395,11 +390,10 @@
node_pointer n,
node_pointer pos)
{
- n->next_ = static_cast<node_pointer>(pos->group_prev_)->next_;
+ n->next_ = pos->group_prev_->next_;
n->group_prev_ = pos->group_prev_;
- static_cast<node_pointer>(pos->group_prev_)->next_ =
- static_cast<link_pointer>(n);
- pos->group_prev_ = static_cast<link_pointer>(n);
+ pos->group_prev_->next_ = n;
+ pos->group_prev_ = n;
}
inline iterator add_node(
@@ -412,37 +406,35 @@
if (pos.node_) {
this->add_after_node(n, pos.node_);
if (n->next_) {
- std::size_t next_bucket = policy::to_bucket(
- this->bucket_count_,
+ std::size_t next_bucket = this->hash_to_bucket(
static_cast<node_pointer>(n->next_)->hash_);
- if (next_bucket !=
- policy::to_bucket(this->bucket_count_, key_hash)) {
+ if (next_bucket != this->hash_to_bucket(key_hash)) {
this->get_bucket(next_bucket)->next_ = n;
}
}
}
else {
bucket_pointer b = this->get_bucket(
- policy::to_bucket(this->bucket_count_, key_hash));
+ this->hash_to_bucket(key_hash));
if (!b->next_)
{
- previous_pointer start_node = this->get_previous_start();
+ link_pointer start_node = this->get_previous_start();
if (start_node->next_) {
- this->get_bucket(policy::to_bucket(this->bucket_count_,
+ this->get_bucket(this->hash_to_bucket(
static_cast<node_pointer>(start_node->next_)->hash_
))->next_ = n;
}
b->next_ = start_node;
n->next_ = start_node->next_;
- start_node->next_ = static_cast<link_pointer>(n);
+ start_node->next_ = n;
}
else
{
n->next_ = b->next_->next_;
- b->next_->next_ = static_cast<link_pointer>(n);
+ b->next_->next_ = n;
}
}
++this->size_;
@@ -545,11 +537,8 @@
if(!this->size_) return 0;
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);
-
- previous_pointer prev = this_bucket->next_;
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
+ link_pointer prev = this->get_previous_start(bucket_index);
if (!prev) return 0;
for (;;)
@@ -557,24 +546,21 @@
if (!prev->next_) return 0;
std::size_t node_hash =
static_cast<node_pointer>(prev->next_)->hash_;
- if (policy::to_bucket(this->bucket_count_, node_hash)
- != bucket_index)
+ if (this->hash_to_bucket(node_hash) != bucket_index)
return 0;
if (node_hash == key_hash &&
this->key_eq()(k, this->get_key(
static_cast<node_pointer>(prev->next_)->value())))
break;
- prev = static_cast<previous_pointer>(
- static_cast<node_pointer>(prev->next_)->group_prev_);
+ 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 = 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)
@@ -582,132 +568,72 @@
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_));
- previous_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_);
- previous_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 previous_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_);
- previous_pointer prev =
- static_cast<previous_pointer>(n->group_prev_);
-
- if(prev->next_ != n) {
- // The node is at the beginning of a group.
-
- // Find the previous node pointer:
- prev = b.next_;
- while(prev->next_ != n) {
- prev = static_cast<previous_pointer>(
- static_cast<node_pointer>(prev->next_)->group_prev_);
- }
+ std::size_t bucket_index = this->hash_to_bucket(begin->hash_);
- // Remove from group
- if (next && next->group_prev_ == static_cast<link_pointer>(n))
- {
- next->group_prev_ = n->group_prev_;
- }
- }
- else if (next && next->group_prev_ == static_cast<link_pointer>(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_ != static_cast<link_pointer>(n)) {
- x = static_cast<node_pointer>(x->group_prev_);
- }
- x->group_prev_ = n->group_prev_;
+ // 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_;
}
- prev->next_ = static_cast<link_pointer>(next);
+ // Delete the nodes.
+ do {
+ link_pointer group_end =
+ 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 previous_pointer unlink_nodes(bucket& b,
- node_pointer begin, node_pointer end)
+ static link_pointer split_groups(node_pointer begin, node_pointer end)
{
- previous_pointer prev = static_cast<previous_pointer>(
- begin->group_prev_);
+ node_pointer prev = begin->group_prev_;
+ if (prev->next_ != begin) prev = node_pointer();
- if(prev->next_ != static_cast<link_pointer>(begin)) {
- // The node is at the beginning of a group.
-
- // Find the previous node pointer:
- prev = b.next_;
- while(prev->next_ != static_cast<link_pointer>(begin))
- prev = static_cast<previous_pointer>(
- static_cast<node_pointer>(prev->next_)->group_prev_);
+ if (end) {
+ node_pointer first = end;
+ while (first != begin && first->group_prev_->next_ == first) {
+ first = 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 (first->group_prev_->next_ == first) {
+ first = first->group_prev_;
}
+ boost::swap(first->group_prev_, begin->group_prev_);
}
- prev->next_ = static_cast<link_pointer>(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_ ==
- static_cast<link_pointer>(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
@@ -715,19 +641,16 @@
static void fill_buckets(iterator n, table& dst,
NodeCreator& creator)
{
- previous_pointer prev = dst.get_previous_start();
+ link_pointer prev = dst.get_previous_start();
while (n.node_) {
std::size_t key_hash = n.node_->hash_;
- iterator group_end(
- static_cast<node_pointer>(
- static_cast<node_pointer>(n.node_->group_prev_)->next_
- ));
+ iterator group_end(n.node_->group_prev_->next_);
node_pointer first_node = creator.create(*n);
node_pointer end = first_node;
first_node->hash_ = key_hash;
- prev->next_ = static_cast<link_pointer>(first_node);
+ prev->next_ = first_node;
++dst.size_;
for (++n; n != group_end; ++n)
@@ -748,24 +671,22 @@
BOOST_ASSERT(this->buckets_);
this->create_buckets(num_buckets);
- previous_pointer prev = this->get_previous_start();
+ link_pointer prev = this->get_previous_start();
while (prev->next_)
prev = place_in_bucket(*this, prev,
- static_cast<node_pointer>(
- static_cast<node_pointer>(prev->next_)->group_prev_));
+ static_cast<node_pointer>(prev->next_)->group_prev_);
}
// Iterate through the nodes placing them in the correct buckets.
// pre: prev->next_ is not null.
- static previous_pointer place_in_bucket(table& dst,
- previous_pointer prev, node_pointer end)
+ static link_pointer place_in_bucket(table& dst,
+ link_pointer prev, node_pointer end)
{
- bucket_pointer b = dst.get_bucket(policy::to_bucket(
- dst.bucket_count_, end->hash_));
+ bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(end->hash_));
if (!b->next_) {
- b->next_ = static_cast<node_pointer>(prev);
- return static_cast<previous_pointer>(end);
+ b->next_ = prev;
+ return end;
}
else {
link_pointer next = end->next_;
Modified: branches/release/boost/unordered/detail/extract_key.hpp
==============================================================================
--- branches/release/boost/unordered/detail/extract_key.hpp (original)
+++ branches/release/boost/unordered/detail/extract_key.hpp 2012-11-15 08:43:37 EST (Thu, 15 Nov 2012)
@@ -155,7 +155,7 @@
#define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
template <typename T2> \
static no_key extract(boost::unordered::piecewise_construct_t, \
- namespace_::tuple<> const&, BOOST_FWD_REF(T2)) \
+ namespace_ tuple<> const&, BOOST_FWD_REF(T2)) \
{ \
return no_key(); \
} \
@@ -163,17 +163,17 @@
template <typename T, typename T2> \
static typename is_key<key_type, T>::type \
extract(boost::unordered::piecewise_construct_t, \
- namespace_::tuple<T> const& k, BOOST_FWD_REF(T2)) \
+ namespace_ tuple<T> const& k, BOOST_FWD_REF(T2)) \
{ \
return typename is_key<key_type, T>::type( \
- namespace_::get<0>(k)); \
+ namespace_ get<0>(k)); \
}
#else
#define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
static no_key extract(boost::unordered::piecewise_construct_t, \
- namespace_::tuple<> const&) \
+ namespace_ tuple<> const&) \
{ \
return no_key(); \
} \
@@ -181,18 +181,18 @@
template <typename T> \
static typename is_key<key_type, T>::type \
extract(boost::unordered::piecewise_construct_t, \
- namespace_::tuple<T> const& k) \
+ namespace_ tuple<T> const& k) \
{ \
return typename is_key<key_type, T>::type( \
- namespace_::get<0>(k)); \
+ namespace_ get<0>(k)); \
}
#endif
-BOOST_UNORDERED_KEY_FROM_TUPLE(boost)
+BOOST_UNORDERED_KEY_FROM_TUPLE(boost::)
#if !defined(BOOST_NO_CXX11_HDR_TUPLE)
-BOOST_UNORDERED_KEY_FROM_TUPLE(std)
+BOOST_UNORDERED_KEY_FROM_TUPLE(std::)
#endif
Modified: branches/release/boost/unordered/detail/table.hpp
==============================================================================
--- branches/release/boost/unordered/detail/table.hpp (original)
+++ branches/release/boost/unordered/detail/table.hpp 2012-11-15 08:43:37 EST (Thu, 15 Nov 2012)
@@ -125,7 +125,6 @@
template <typename Types>
struct table :
- Types::policy,
boost::unordered::detail::functions<
typename Types::hasher,
typename Types::key_equal>
@@ -164,20 +163,17 @@
const_node_pointer;
typedef typename bucket_allocator_traits::pointer
bucket_pointer;
- typedef typename bucket::previous_pointer
- previous_pointer;
typedef boost::unordered::detail::node_constructor<node_allocator>
node_constructor;
typedef boost::unordered::iterator_detail::
- iterator<node_pointer, value_type> iterator;
+ iterator<node> iterator;
typedef boost::unordered::iterator_detail::
- c_iterator<const_node_pointer, node_pointer, value_type> c_iterator;
+ c_iterator<node, const_node_pointer> c_iterator;
typedef boost::unordered::iterator_detail::
- l_iterator<node_pointer, value_type, policy> l_iterator;
+ l_iterator<node, policy> l_iterator;
typedef boost::unordered::iterator_detail::
- cl_iterator<const_node_pointer, node_pointer, value_type, policy>
- cl_iterator;
+ cl_iterator<node, const_node_pointer, policy> cl_iterator;
////////////////////////////////////////////////////////////////////////
// Members
@@ -226,28 +222,31 @@
return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
}
- previous_pointer get_previous_start() const
+ link_pointer get_previous_start() const
{
return get_bucket(bucket_count_)->first_from_start();
}
- previous_pointer get_previous_start(std::size_t bucket_index) const
+ link_pointer get_previous_start(std::size_t bucket_index) const
{
return get_bucket(bucket_index)->next_;
}
iterator begin() const
{
- return size_ ? iterator(static_cast<node_pointer>(
- get_previous_start()->next_)) : iterator();
+ return size_ ? iterator(get_previous_start()->next_) : iterator();
}
iterator begin(std::size_t bucket_index) const
{
if (!size_) return iterator();
- previous_pointer prev = get_previous_start(bucket_index);
- return prev ? iterator(static_cast<node_pointer>(prev->next_)) :
- iterator();
+ link_pointer prev = get_previous_start(bucket_index);
+ return prev ? iterator(prev->next_) : iterator();
+ }
+
+ std::size_t hash_to_bucket(std::size_t hash) const
+ {
+ return policy::to_bucket(bucket_count_, hash);
}
float load_factor() const
@@ -263,8 +262,7 @@
if (!it.node_) return 0;
std::size_t count = 0;
- while(it.node_ && policy::to_bucket(
- bucket_count_, it.node_->hash_) == index)
+ while(it.node_ && hash_to_bucket(it.node_->hash_) == index)
{
++count;
++it;
@@ -500,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;
}
@@ -527,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>(
@@ -547,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_);
@@ -579,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,
- previous_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 = hash_to_bucket(
+ 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,
- previous_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_ = previous_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_ = previous_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: branches/release/boost/unordered/detail/unique.hpp
==============================================================================
--- branches/release/boost/unordered/detail/unique.hpp (original)
+++ branches/release/boost/unordered/detail/unique.hpp 2012-11-15 08:43:37 EST (Thu, 15 Nov 2012)
@@ -27,7 +27,8 @@
boost::unordered::detail::value_base<T>
{
typedef typename ::boost::unordered::detail::rebind_wrap<
- A, unique_node<A, T> >::type::pointer link_pointer;
+ A, unique_node<A, T> >::type::pointer node_pointer;
+ typedef node_pointer link_pointer;
link_pointer next_;
std::size_t hash_;
@@ -37,7 +38,7 @@
hash_(0)
{}
- void init(link_pointer)
+ void init(node_pointer)
{
}
@@ -51,6 +52,7 @@
boost::unordered::detail::ptr_bucket
{
typedef boost::unordered::detail::ptr_bucket bucket_base;
+ typedef ptr_node<T>* node_pointer;
typedef ptr_bucket* link_pointer;
std::size_t hash_;
@@ -60,7 +62,7 @@
hash_(0)
{}
- void init(link_pointer)
+ void init(node_pointer)
{
}
@@ -176,7 +178,6 @@
typedef typename table::node_allocator_traits node_allocator_traits;
typedef typename table::bucket_pointer bucket_pointer;
typedef typename table::link_pointer link_pointer;
- typedef typename table::previous_pointer previous_pointer;
typedef typename table::hasher hasher;
typedef typename table::key_equal key_equal;
typedef typename table::key_type key_type;
@@ -231,8 +232,7 @@
Key const& k,
Pred const& eq) const
{
- std::size_t bucket_index =
- policy::to_bucket(this->bucket_count_, key_hash);
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
iterator n = this->begin(bucket_index);
for (;;)
@@ -247,8 +247,7 @@
}
else
{
- if (policy::to_bucket(this->bucket_count_, node_hash)
- != bucket_index)
+ if (this->hash_to_bucket(node_hash) != bucket_index)
return iterator();
}
@@ -312,27 +311,26 @@
node_pointer n = a.release();
n->hash_ = key_hash;
- bucket_pointer b = this->get_bucket(
- policy::to_bucket(this->bucket_count_, key_hash));
+ bucket_pointer b = this->get_bucket(this->hash_to_bucket(key_hash));
if (!b->next_)
{
- previous_pointer start_node = this->get_previous_start();
+ link_pointer start_node = this->get_previous_start();
if (start_node->next_) {
- this->get_bucket(policy::to_bucket(this->bucket_count_,
+ this->get_bucket(this->hash_to_bucket(
static_cast<node_pointer>(start_node->next_)->hash_)
)->next_ = n;
}
b->next_ = start_node;
n->next_ = start_node->next_;
- start_node->next_ = static_cast<link_pointer>(n);
+ start_node->next_ = n;
}
else
{
n->next_ = b->next_->next_;
- b->next_->next_ = static_cast<link_pointer>(n);
+ b->next_->next_ = n;
}
++this->size_;
@@ -518,11 +516,8 @@
if(!this->size_) return 0;
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);
-
- previous_pointer prev = this_bucket->next_;
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
+ link_pointer prev = this->get_previous_start(bucket_index);
if (!prev) return 0;
for (;;)
@@ -530,21 +525,20 @@
if (!prev->next_) return 0;
std::size_t node_hash =
static_cast<node_pointer>(prev->next_)->hash_;
- if (policy::to_bucket(this->bucket_count_, node_hash)
- != bucket_index)
+ if (this->hash_to_bucket(node_hash) != bucket_index)
return 0;
if (node_hash == key_hash &&
this->key_eq()(k, this->get_key(
static_cast<node_pointer>(prev->next_)->value())))
break;
- prev = static_cast<previous_pointer>(prev->next_);
+ 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)
@@ -552,46 +546,30 @@
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_));
- previous_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_);
- previous_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 previous_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 = this->hash_to_bucket(begin->hash_);
- static previous_pointer unlink_nodes(bucket& b,
- node_pointer begin, node_pointer end)
- {
- previous_pointer prev = b.next_;
- link_pointer begin_void = static_cast<link_pointer>(begin);
- while(prev->next_ != begin_void)
- prev = static_cast<previous_pointer>(prev->next_);
- prev->next_ = static_cast<link_pointer>(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);
}
////////////////////////////////////////////////////////////////////////
@@ -601,12 +579,12 @@
static void fill_buckets(iterator n, table& dst,
NodeCreator& creator)
{
- previous_pointer prev = dst.get_previous_start();
+ link_pointer prev = dst.get_previous_start();
while (n.node_) {
node_pointer node = creator.create(*n);
node->hash_ = n.node_->hash_;
- prev->next_ = static_cast<link_pointer>(node);
+ prev->next_ = node;
++dst.size_;
++n;
@@ -620,28 +598,26 @@
BOOST_ASSERT(this->buckets_);
this->create_buckets(num_buckets);
- previous_pointer prev = this->get_previous_start();
+ link_pointer prev = this->get_previous_start();
while (prev->next_)
prev = place_in_bucket(*this, prev);
}
// Iterate through the nodes placing them in the correct buckets.
// pre: prev->next_ is not null.
- static previous_pointer place_in_bucket(table& dst,
- previous_pointer prev)
+ static link_pointer place_in_bucket(table& dst, link_pointer prev)
{
node_pointer n = static_cast<node_pointer>(prev->next_);
- bucket_pointer b = dst.get_bucket(
- table::to_bucket(dst.bucket_count_, n->hash_));
+ bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(n->hash_));
if (!b->next_) {
b->next_ = prev;
- return static_cast<previous_pointer>(n);
+ return n;
}
else {
prev->next_ = n->next_;
n->next_ = b->next_->next_;
- b->next_->next_ = static_cast<link_pointer>(n);
+ b->next_->next_ = n;
return prev;
}
}
Modified: branches/release/boost/unordered/unordered_map.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_map.hpp (original)
+++ branches/release/boost/unordered/unordered_map.hpp 2012-11-15 08:43:37 EST (Thu, 15 Nov 2012)
@@ -463,8 +463,7 @@
size_type bucket(const key_type& k) const
{
- return table::to_bucket(table_.bucket_count_,
- table_.hash(k));
+ return table_.hash_to_bucket(table_.hash(k));
}
local_iterator begin(size_type n)
@@ -942,8 +941,7 @@
size_type bucket(const key_type& k) const
{
- return table::to_bucket(table_.bucket_count_,
- table_.hash(k));
+ return table_.hash_to_bucket(table_.hash(k));
}
local_iterator begin(size_type n)
Modified: branches/release/boost/unordered/unordered_set.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_set.hpp (original)
+++ branches/release/boost/unordered/unordered_set.hpp 2012-11-15 08:43:37 EST (Thu, 15 Nov 2012)
@@ -448,8 +448,7 @@
size_type bucket(const key_type& k) const
{
- return table::to_bucket(table_.bucket_count_,
- table_.hash(k));
+ return table_.hash_to_bucket(table_.hash(k));
}
local_iterator begin(size_type n)
@@ -917,8 +916,7 @@
size_type bucket(const key_type& k) const
{
- return table::to_bucket(table_.bucket_count_,
- table_.hash(k));
+ return table_.hash_to_bucket(table_.hash(k));
}
local_iterator begin(size_type n)
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