Subject: [Boost-commit] svn:boost r80558 - in branches/release: . boost boost/unordered boost/unordered/detail libs libs/unordered libs/unordered/test/objects libs/unordered/test/unordered
From: dnljms_at_[hidden]
Date: 2012-09-17 14:53:32
Author: danieljames
Date: 2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
New Revision: 80558
URL: http://svn.boost.org/trac/boost/changeset/80558
Log:
Unordered: Merge from trunk.
Faster assign, plus simplified some of the implementation.
Properties modified:
branches/release/ (props changed)
branches/release/boost/ (props changed)
branches/release/boost/unordered/ (props changed)
branches/release/libs/ (props changed)
branches/release/libs/unordered/ (props changed)
Text files modified:
branches/release/boost/unordered/detail/buckets.hpp | 808 +++++++++++++--------------------------
branches/release/boost/unordered/detail/equivalent.hpp | 138 +-----
branches/release/boost/unordered/detail/table.hpp | 756 +++++++++++++++++++++++++++++-------
branches/release/boost/unordered/detail/unique.hpp | 125 +----
branches/release/boost/unordered/unordered_map.hpp | 2
branches/release/boost/unordered/unordered_set.hpp | 2
branches/release/libs/unordered/test/objects/test.hpp | 140 ++++++
branches/release/libs/unordered/test/unordered/insert_tests.cpp | 18
8 files changed, 1084 insertions(+), 905 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-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -20,171 +20,14 @@
#include <boost/limits.hpp>
#include <boost/iterator.hpp>
-#if defined(BOOST_MSVC)
-#pragma warning(push)
-#pragma warning(disable:4127) // conditional expression is constant
-#endif
-
namespace boost { namespace unordered { namespace detail {
template <typename Types> struct table;
template <typename NodePointer> struct bucket;
struct ptr_bucket;
- template <typename A, typename Bucket, typename Node, typename Policy>
- struct buckets;
template <typename Types> struct table_impl;
template <typename Types> struct grouped_table_impl;
- ///////////////////////////////////////////////////////////////////
- //
- // Node construction
-
- template <typename NodeAlloc>
- struct node_constructor
- {
- private:
-
- typedef NodeAlloc node_allocator;
- typedef boost::unordered::detail::allocator_traits<NodeAlloc>
- node_allocator_traits;
- typedef typename node_allocator_traits::value_type node;
- typedef typename node_allocator_traits::pointer node_pointer;
- typedef typename node::value_type value_type;
-
- node_allocator& alloc_;
- node_pointer node_;
- bool node_constructed_;
- bool value_constructed_;
-
- public:
-
- node_constructor(node_allocator& n) :
- alloc_(n),
- node_(),
- node_constructed_(false),
- value_constructed_(false)
- {
- }
-
- ~node_constructor();
-
- void construct_node();
-
- template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
- void construct_value(BOOST_UNORDERED_EMPLACE_ARGS)
- {
- BOOST_ASSERT(node_ && node_constructed_ && !value_constructed_);
- boost::unordered::detail::construct_value_impl(
- alloc_, node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
- value_constructed_ = true;
- }
-
- template <typename A0>
- void construct_value2(BOOST_FWD_REF(A0) a0)
- {
- BOOST_ASSERT(node_ && node_constructed_ && !value_constructed_);
- boost::unordered::detail::construct_value_impl(
- alloc_, node_->value_ptr(),
- BOOST_UNORDERED_EMPLACE_ARGS1(boost::forward<A0>(a0)));
- value_constructed_ = true;
- }
-
- value_type const& value() const {
- BOOST_ASSERT(node_ && node_constructed_ && value_constructed_);
- return node_->value();
- }
-
- // no throw
- node_pointer release()
- {
- node_pointer p = node_;
- node_ = node_pointer();
- return p;
- }
-
- private:
- node_constructor(node_constructor const&);
- node_constructor& operator=(node_constructor const&);
- };
-
- template <typename Alloc>
- node_constructor<Alloc>::~node_constructor()
- {
- if (node_) {
- if (value_constructed_) {
- boost::unordered::detail::destroy_value_impl(alloc_,
- node_->value_ptr());
- }
-
- if (node_constructed_) {
- node_allocator_traits::destroy(alloc_,
- boost::addressof(*node_));
- }
-
- node_allocator_traits::deallocate(alloc_, node_, 1);
- }
- }
-
- template <typename Alloc>
- void node_constructor<Alloc>::construct_node()
- {
- if(!node_) {
- node_constructed_ = false;
- value_constructed_ = false;
-
- node_ = node_allocator_traits::allocate(alloc_, 1);
-
- node_allocator_traits::construct(alloc_,
- boost::addressof(*node_), node());
- node_->init(static_cast<typename node::link_pointer>(node_));
- node_constructed_ = true;
- }
- else {
- BOOST_ASSERT(node_constructed_);
-
- if (value_constructed_)
- {
- boost::unordered::detail::destroy_value_impl(alloc_,
- node_->value_ptr());
- value_constructed_ = false;
- }
- }
- }
-
- ///////////////////////////////////////////////////////////////////
- //
- // Bucket
-
- template <typename NodePointer>
- struct bucket
- {
- typedef NodePointer previous_pointer;
- previous_pointer next_;
-
- bucket() : next_() {}
-
- previous_pointer first_from_start()
- {
- return next_;
- }
-
- enum { extra_node = true };
- };
-
- struct ptr_bucket
- {
- typedef ptr_bucket* previous_pointer;
- previous_pointer next_;
-
- ptr_bucket() : next_(0) {}
-
- previous_pointer first_from_start()
- {
- return this;
- }
-
- enum { extra_node = false };
- };
}}}
namespace boost { namespace unordered { namespace iterator_detail {
@@ -340,8 +183,6 @@
friend struct boost::unordered::iterator_detail::cl_iterator;
template <typename>
friend struct boost::unordered::detail::table;
- template <typename, typename, typename, typename>
- friend struct boost::unordered::detail::buckets;
template <typename>
friend struct boost::unordered::detail::table_impl;
template <typename>
@@ -397,8 +238,6 @@
#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
template <typename>
friend struct boost::unordered::detail::table;
- template <typename, typename, typename, typename>
- friend struct boost::unordered::detail::buckets;
template <typename>
friend struct boost::unordered::detail::table_impl;
template <typename>
@@ -454,472 +293,361 @@
///////////////////////////////////////////////////////////////////
//
- // Hash Policy
- //
- // Don't really want buckets to derive from this, but will for now.
+ // Node construction
- template <typename SizeT>
- struct prime_policy
+ template <typename NodeAlloc>
+ struct node_constructor
{
- template <typename Hash, typename T>
- static inline SizeT apply_hash(Hash const& hf, T const& x) {
- return hf(x);
+ private:
+
+ typedef NodeAlloc node_allocator;
+ typedef boost::unordered::detail::allocator_traits<NodeAlloc>
+ node_allocator_traits;
+ typedef typename node_allocator_traits::value_type node;
+ typedef typename node_allocator_traits::pointer node_pointer;
+ typedef typename node::value_type value_type;
+
+ protected:
+
+ node_allocator& alloc_;
+
+ private:
+
+ node_pointer node_;
+ bool node_constructed_;
+ bool value_constructed_;
+
+ public:
+
+ node_constructor(node_allocator& n) :
+ alloc_(n),
+ node_(),
+ node_constructed_(false),
+ value_constructed_(false)
+ {
}
- static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
- return hash % bucket_count;
+ ~node_constructor();
+
+ void construct();
+
+ template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ void construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS)
+ {
+ construct();
+ boost::unordered::detail::construct_value_impl(
+ alloc_, node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
+ value_constructed_ = true;
}
- static inline SizeT new_bucket_count(SizeT min) {
- return boost::unordered::detail::next_prime(min);
+ template <typename A0>
+ void construct_with_value2(BOOST_FWD_REF(A0) a0)
+ {
+ construct();
+ boost::unordered::detail::construct_value_impl(
+ alloc_, node_->value_ptr(),
+ BOOST_UNORDERED_EMPLACE_ARGS1(boost::forward<A0>(a0)));
+ value_constructed_ = true;
}
- static inline SizeT prev_bucket_count(SizeT max) {
- return boost::unordered::detail::prev_prime(max);
+ value_type const& value() const {
+ BOOST_ASSERT(node_ && node_constructed_ && value_constructed_);
+ return node_->value();
+ }
+
+ // no throw
+ node_pointer release()
+ {
+ BOOST_ASSERT(node_ && node_constructed_);
+ node_pointer p = node_;
+ node_ = node_pointer();
+ return p;
}
+
+ private:
+ node_constructor(node_constructor const&);
+ node_constructor& operator=(node_constructor const&);
};
- template <typename SizeT>
- struct mix64_policy
+ template <typename Alloc>
+ node_constructor<Alloc>::~node_constructor()
{
- template <typename Hash, typename T>
- static inline SizeT apply_hash(Hash const& hf, T const& x) {
- SizeT key = hf(x);
- key = (~key) + (key << 21); // key = (key << 21) - key - 1;
- key = key ^ (key >> 24);
- key = (key + (key << 3)) + (key << 8); // key * 265
- key = key ^ (key >> 14);
- key = (key + (key << 2)) + (key << 4); // key * 21
- key = key ^ (key >> 28);
- key = key + (key << 31);
- return key;
- }
+ if (node_) {
+ if (value_constructed_) {
+ boost::unordered::detail::destroy_value_impl(alloc_,
+ node_->value_ptr());
+ }
- static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
- return hash & (bucket_count - 1);
- }
+ if (node_constructed_) {
+ node_allocator_traits::destroy(alloc_,
+ boost::addressof(*node_));
+ }
- static inline SizeT new_bucket_count(SizeT min) {
- if (min <= 4) return 4;
- --min;
- min |= min >> 1;
- min |= min >> 2;
- min |= min >> 4;
- min |= min >> 8;
- min |= min >> 16;
- min |= min >> 32;
- return min + 1;
+ node_allocator_traits::deallocate(alloc_, node_, 1);
}
+ }
- static inline SizeT prev_bucket_count(SizeT max) {
- max |= max >> 1;
- max |= max >> 2;
- max |= max >> 4;
- max |= max >> 8;
- max |= max >> 16;
- max |= max >> 32;
- return (max >> 1) + 1;
- }
- };
+ template <typename Alloc>
+ void node_constructor<Alloc>::construct()
+ {
+ if(!node_) {
+ node_constructed_ = false;
+ value_constructed_ = false;
- template <int digits, int radix>
- struct pick_policy_impl {
- typedef prime_policy<std::size_t> type;
- };
+ node_ = node_allocator_traits::allocate(alloc_, 1);
- template <>
- struct pick_policy_impl<64, 2> {
- typedef mix64_policy<std::size_t> type;
- };
+ node_allocator_traits::construct(alloc_,
+ boost::addressof(*node_), node());
+ node_->init(static_cast<typename node::link_pointer>(node_));
+ node_constructed_ = true;
+ }
+ else {
+ BOOST_ASSERT(node_constructed_);
- struct pick_policy :
- pick_policy_impl<
- std::numeric_limits<std::size_t>::digits,
- std::numeric_limits<std::size_t>::radix> {};
+ if (value_constructed_)
+ {
+ boost::unordered::detail::destroy_value_impl(alloc_,
+ node_->value_ptr());
+ value_constructed_ = false;
+ }
+ }
+ }
///////////////////////////////////////////////////////////////////
//
- // Buckets
+ // Node Holder
+ //
+ // Temporary store for nodes. Deletes any that aren't used.
- template <typename A, typename Bucket, typename Node, typename Policy>
- struct buckets : Policy
+ template <typename NodeAlloc>
+ struct node_holder : private node_constructor<NodeAlloc>
{
private:
- buckets(buckets const&);
- buckets& operator=(buckets const&);
- public:
- typedef boost::unordered::detail::allocator_traits<A> traits;
- typedef typename traits::value_type value_type;
+ typedef node_constructor<NodeAlloc> base;
- typedef Policy policy;
- typedef Node node;
- typedef Bucket bucket;
- typedef typename boost::unordered::detail::rebind_wrap<A, node>::type
- node_allocator;
- typedef typename boost::unordered::detail::rebind_wrap<A, bucket>::type
- bucket_allocator;
- typedef boost::unordered::detail::allocator_traits<node_allocator>
+ typedef NodeAlloc node_allocator;
+ typedef boost::unordered::detail::allocator_traits<NodeAlloc>
node_allocator_traits;
- typedef boost::unordered::detail::allocator_traits<bucket_allocator>
- bucket_allocator_traits;
- typedef typename node_allocator_traits::pointer
- node_pointer;
- typedef typename node_allocator_traits::const_pointer
- 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 typename node_allocator_traits::value_type node;
+ 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::
- c_iterator<const_node_pointer, node_pointer, value_type> c_iterator;
- typedef boost::unordered::iterator_detail::
- l_iterator<node_pointer, value_type, policy> l_iterator;
- typedef boost::unordered::iterator_detail::
- cl_iterator<const_node_pointer, node_pointer, value_type, policy>
- cl_iterator;
-
- // Members
- bucket_pointer buckets_;
- std::size_t bucket_count_;
- std::size_t size_;
- boost::unordered::detail::compressed<bucket_allocator, node_allocator>
- allocators_;
+ node_pointer nodes_;
- // Data access
+ public:
- bucket_allocator const& bucket_alloc() const
+ template <typename Table>
+ explicit node_holder(Table& b) :
+ base(b.node_alloc()),
+ nodes_()
{
- return allocators_.first();
+ typename Table::previous_pointer prev = b.get_previous_start();
+ nodes_ = static_cast<node_pointer>(prev->next_);
+ prev->next_ = link_pointer();
+ b.size_ = 0;
}
- node_allocator const& node_alloc() const
- {
- return allocators_.second();
- }
+ ~node_holder();
- bucket_allocator& bucket_alloc()
- {
- return allocators_.first();
+ template <typename T>
+ inline void assign_impl(T const& v) {
+ nodes_->value() = v;
}
- node_allocator& node_alloc()
- {
- return allocators_.second();
+ template <typename T1, typename T2>
+ inline void assign_impl(std::pair<T1 const, T2> const& v) {
+ const_cast<T1&>(nodes_->value().first) = v.first;
+ nodes_->value().second = v.second;
}
- std::size_t max_bucket_count() const
- {
- // -1 to account for the start bucket.
- return policy::prev_bucket_count(
- bucket_allocator_traits::max_size(bucket_alloc()) - 1);
+ template <typename T>
+ inline void move_assign_impl(T& v) {
+ nodes_->value() = boost::move(v);
}
- bucket_pointer get_bucket(std::size_t bucket_index) const
- {
- return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
+ template <typename T1, typename T2>
+ inline void move_assign_impl(std::pair<T1 const, T2>& v) {
+ // TODO: Move key as well?
+ const_cast<T1&>(nodes_->value().first) =
+ boost::move(const_cast<T1&>(v.first));
+ nodes_->value().second = boost::move(v.second);
}
- previous_pointer get_previous_start() const
+ node_pointer copy_of(value_type const& v)
{
- return this->get_bucket(this->bucket_count_)->first_from_start();
+ if (nodes_) {
+ assign_impl(v);
+ node_pointer p = nodes_;
+ nodes_ = static_cast<node_pointer>(p->next_);
+ p->init(static_cast<typename node::link_pointer>(p));
+ p->next_ = link_pointer();
+ return p;
+ }
+ else {
+ this->construct_with_value2(v);
+ return base::release();
+ }
}
- previous_pointer get_previous_start(std::size_t bucket_index) const
+ node_pointer move_copy_of(value_type& v)
{
- return this->get_bucket(bucket_index)->next_;
+ if (nodes_) {
+ 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->next_ = link_pointer();
+ return p;
+ }
+ else {
+ this->construct_with_value2(boost::move(v));
+ return base::release();
+ }
}
iterator get_start() const
{
- return iterator(static_cast<node_pointer>(
- this->get_previous_start()->next_));
- }
-
- iterator get_start(std::size_t bucket_index) const
- {
- previous_pointer prev = this->get_previous_start(bucket_index);
- return prev ? iterator(static_cast<node_pointer>(prev->next_)) :
- iterator();
+ return iterator(nodes_);
}
+ };
- float load_factor() const
- {
- BOOST_ASSERT(this->bucket_count_ != 0);
- return static_cast<float>(this->size_)
- / static_cast<float>(this->bucket_count_);
+ template <typename Alloc>
+ node_holder<Alloc>::~node_holder()
+ {
+ while (nodes_) {
+ node_pointer p = nodes_;
+ nodes_ = static_cast<node_pointer>(p->next_);
+
+ boost::unordered::detail::destroy_value_impl(this->alloc_,
+ p->value_ptr());
+ node_allocator_traits::destroy(this->alloc_, boost::addressof(*p));
+ node_allocator_traits::deallocate(this->alloc_, p, 1);
}
+ }
- std::size_t bucket_size(std::size_t index) const
- {
- if (!this->size_) return 0;
- iterator it = this->get_start(index);
- if (!it.node_) return 0;
-
- std::size_t count = 0;
- while(it.node_ && policy::to_bucket(
- this->bucket_count_, it.node_->hash_) == index)
- {
- ++count;
- ++it;
- }
+ ///////////////////////////////////////////////////////////////////
+ //
+ // Bucket
- return count;
- }
+ template <typename NodePointer>
+ struct bucket
+ {
+ typedef NodePointer previous_pointer;
+ previous_pointer next_;
- ////////////////////////////////////////////////////////////////////////
- // Constructors
+ bucket() : next_() {}
- buckets(node_allocator const& a, std::size_t bucket_count) :
- buckets_(),
- bucket_count_(bucket_count),
- size_(),
- allocators_(a,a)
+ previous_pointer first_from_start()
{
+ return next_;
}
- buckets(buckets& b, boost::unordered::detail::move_tag m) :
- buckets_(),
- bucket_count_(b.bucket_count_),
- size_(),
- allocators_(b.allocators_, m)
- {
- swap(b);
- }
+ enum { extra_node = true };
+ };
- template <typename Types>
- buckets(boost::unordered::detail::table<Types>& x,
- boost::unordered::detail::move_tag m) :
- buckets_(),
- bucket_count_(x.bucket_count_),
- size_(),
- allocators_(x.allocators_, m)
- {
- swap(x);
- }
+ struct ptr_bucket
+ {
+ typedef ptr_bucket* previous_pointer;
+ previous_pointer next_;
- ////////////////////////////////////////////////////////////////////////
- // Create buckets
- // (never called in constructor to avoid exception issues)
+ ptr_bucket() : next_(0) {}
- void create_buckets()
+ previous_pointer first_from_start()
{
- boost::unordered::detail::array_constructor<bucket_allocator>
- constructor(bucket_alloc());
-
- // Creates an extra bucket to act as the start node.
- constructor.construct(bucket(), this->bucket_count_ + 1);
-
- if (bucket::extra_node)
- {
- node_constructor a(this->node_alloc());
- a.construct_node();
-
- (constructor.get() +
- static_cast<std::ptrdiff_t>(this->bucket_count_))->next_ =
- a.release();
- }
-
- this->buckets_ = constructor.release();
+ return this;
}
- ////////////////////////////////////////////////////////////////////////
- // Swap and Move
+ enum { extra_node = false };
+ };
- void swap(buckets& other, false_type = false_type())
- {
- BOOST_ASSERT(node_alloc() == other.node_alloc());
- boost::swap(buckets_, other.buckets_);
- boost::swap(bucket_count_, other.bucket_count_);
- boost::swap(size_, other.size_);
- }
+ ///////////////////////////////////////////////////////////////////
+ //
+ // Hash Policy
+ //
+ // Don't really want table to derive from this, but will for now.
- void swap(buckets& other, true_type)
- {
- allocators_.swap(other.allocators_);
- boost::swap(buckets_, other.buckets_);
- boost::swap(bucket_count_, other.bucket_count_);
- boost::swap(size_, other.size_);
+ template <typename SizeT>
+ struct prime_policy
+ {
+ template <typename Hash, typename T>
+ static inline SizeT apply_hash(Hash const& hf, T const& x) {
+ return hf(x);
}
- void move_buckets_from(buckets& other)
- {
- BOOST_ASSERT(node_alloc() == other.node_alloc());
- BOOST_ASSERT(!this->buckets_);
- this->buckets_ = other.buckets_;
- this->bucket_count_ = other.bucket_count_;
- this->size_ = other.size_;
- other.buckets_ = bucket_pointer();
- other.bucket_count_ = 0;
- other.size_ = 0;
+ static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
+ return hash % bucket_count;
}
- ////////////////////////////////////////////////////////////////////////
- // Delete/destruct
-
- inline void delete_node(c_iterator n)
- {
- boost::unordered::detail::destroy_value_impl(node_alloc(),
- n.node_->value_ptr());
- node_allocator_traits::destroy(node_alloc(),
- boost::addressof(*n.node_));
- node_allocator_traits::deallocate(node_alloc(), n.node_, 1);
- --size_;
+ static inline SizeT new_bucket_count(SizeT min) {
+ return boost::unordered::detail::next_prime(min);
}
- std::size_t delete_nodes(c_iterator begin, c_iterator end)
- {
- std::size_t count = 0;
-
- while(begin != end) {
- c_iterator n = begin;
- ++begin;
- delete_node(n);
- ++count;
- }
-
- return count;
+ static inline SizeT prev_bucket_count(SizeT max) {
+ return boost::unordered::detail::prev_prime(max);
}
+ };
- inline void delete_extra_node(bucket_pointer) {}
-
- inline void delete_extra_node(node_pointer n) {
- node_allocator_traits::destroy(node_alloc(), boost::addressof(*n));
- node_allocator_traits::deallocate(node_alloc(), n, 1);
+ template <typename SizeT>
+ struct mix64_policy
+ {
+ template <typename Hash, typename T>
+ static inline SizeT apply_hash(Hash const& hf, T const& x) {
+ SizeT key = hf(x);
+ key = (~key) + (key << 21); // key = (key << 21) - key - 1;
+ key = key ^ (key >> 24);
+ key = (key + (key << 3)) + (key << 8); // key * 265
+ key = key ^ (key >> 14);
+ key = (key + (key << 2)) + (key << 4); // key * 21
+ key = key ^ (key >> 28);
+ key = key + (key << 31);
+ return key;
}
- inline ~buckets()
- {
- this->delete_buckets();
+ static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
+ return hash & (bucket_count - 1);
}
- void delete_buckets()
- {
- if(this->buckets_) {
- previous_pointer prev = this->get_previous_start();
-
- while(prev->next_) {
- node_pointer n = static_cast<node_pointer>(prev->next_);
- prev->next_ = n->next_;
- delete_node(iterator(n));
- }
-
- delete_extra_node(prev);
-
- bucket_pointer end = this->get_bucket(this->bucket_count_ + 1);
- for(bucket_pointer it = this->buckets_; it != end; ++it)
- {
- bucket_allocator_traits::destroy(bucket_alloc(),
- boost::addressof(*it));
- }
-
- bucket_allocator_traits::deallocate(bucket_alloc(),
- this->buckets_, this->bucket_count_ + 1);
-
- this->buckets_ = bucket_pointer();
- }
-
- BOOST_ASSERT(!this->size_);
+ static inline SizeT new_bucket_count(SizeT min) {
+ if (min <= 4) return 4;
+ --min;
+ min |= min >> 1;
+ min |= min >> 2;
+ min |= min >> 4;
+ min |= min >> 8;
+ min |= min >> 16;
+ min |= min >> 32;
+ return min + 1;
}
- void clear()
- {
- if(!this->size_) return;
-
- previous_pointer prev = this->get_previous_start();
-
- while(prev->next_) {
- node_pointer n = static_cast<node_pointer>(prev->next_);
- prev->next_ = n->next_;
- delete_node(iterator(n));
- }
-
- bucket_pointer end = this->get_bucket(this->bucket_count_);
- for(bucket_pointer it = this->buckets_; it != end; ++it)
- {
- it->next_ = node_pointer();
- }
-
- BOOST_ASSERT(!this->size_);
+ static inline SizeT prev_bucket_count(SizeT max) {
+ max |= max >> 1;
+ max |= max >> 2;
+ max |= max >> 4;
+ max |= max >> 8;
+ max |= max >> 16;
+ max |= max >> 32;
+ return (max >> 1) + 1;
}
+ };
- // 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)
- {
- if (!next)
- {
- if (this_bucket->next_ == prev)
- this_bucket->next_ = node_pointer();
- }
- else
- {
- bucket_pointer next_bucket = this->get_bucket(
- policy::to_bucket(this->bucket_count_, next->hash_));
-
- if (next_bucket != this_bucket)
- {
- next_bucket->next_ = prev;
- if (this_bucket->next_ == prev)
- this_bucket->next_ = node_pointer();
- }
- }
- }
+ template <int digits, int radix>
+ struct pick_policy_impl {
+ typedef prime_policy<std::size_t> type;
+ };
- // 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 (this->get_bucket(bucket_index)->next_ != prev)
- {
- for(;;) {
- n = static_cast<node_pointer>(n->next_);
- if (n == end) return;
-
- std::size_t new_bucket_index =
- policy::to_bucket(this->bucket_count_, n->hash_);
- if (bucket_index != new_bucket_index) {
- bucket_index = new_bucket_index;
- break;
- }
- }
- }
-
- // Iterate through the remaining nodes, clearing out the bucket
- // pointers.
- this->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(this->bucket_count_, n->hash_);
- if (bucket_index != new_bucket_index) {
- bucket_index = new_bucket_index;
- this->get_bucket(bucket_index)->next_ = previous_pointer();
- }
- };
-
- // Finally fix the bucket containing the trailing node.
- if (n) {
- this->get_bucket(
- policy::to_bucket(this->bucket_count_, n->hash_))->next_
- = prev;
- }
- }
+ template <>
+ struct pick_policy_impl<64, 2> {
+ typedef mix64_policy<std::size_t> type;
};
+ struct pick_policy :
+ pick_policy_impl<
+ std::numeric_limits<std::size_t>::digits,
+ std::numeric_limits<std::size_t>::radix> {};
+
////////////////////////////////////////////////////////////////////////////
// Functions
@@ -1066,8 +794,4 @@
#endif
}}}
-#if defined(BOOST_MSVC)
-#pragma warning(pop)
-#endif
-
#endif
Modified: branches/release/boost/unordered/detail/equivalent.hpp
==============================================================================
--- branches/release/boost/unordered/detail/equivalent.hpp (original)
+++ branches/release/boost/unordered/detail/equivalent.hpp 2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -125,16 +125,15 @@
{
typedef boost::unordered::detail::multiset<A, T, H, P> types;
+ typedef A allocator;
typedef T value_type;
typedef H hasher;
typedef P key_equal;
typedef T key_type;
- typedef typename boost::unordered::detail::rebind_wrap<
- A, value_type>::type allocator;
-
typedef boost::unordered::detail::allocator_traits<allocator> traits;
- typedef boost::unordered::detail::pick_grouped_node<allocator, value_type> pick;
+ typedef boost::unordered::detail::pick_grouped_node<allocator,
+ value_type> pick;
typedef typename pick::node node;
typedef typename pick::bucket bucket;
typedef typename pick::link_pointer link_pointer;
@@ -150,16 +149,15 @@
{
typedef boost::unordered::detail::multimap<A, K, M, H, P> types;
+ typedef A allocator;
typedef std::pair<K const, M> value_type;
typedef H hasher;
typedef P key_equal;
typedef K key_type;
- typedef typename boost::unordered::detail::rebind_wrap<
- A, value_type>::type allocator;
-
typedef boost::unordered::detail::allocator_traits<allocator> traits;
- typedef boost::unordered::detail::pick_grouped_node<allocator, value_type> pick;
+ typedef boost::unordered::detail::pick_grouped_node<allocator,
+ value_type> pick;
typedef typename pick::node node;
typedef typename pick::bucket bucket;
typedef typename pick::link_pointer link_pointer;
@@ -177,7 +175,6 @@
typedef boost::unordered::detail::table<Types> table;
typedef typename table::value_type value_type;
typedef typename table::bucket bucket;
- typedef typename table::buckets buckets;
typedef typename table::policy policy;
typedef typename table::node_pointer node_pointer;
typedef typename table::node_allocator node_allocator;
@@ -204,12 +201,17 @@
grouped_table_impl(grouped_table_impl const& x)
: table(x, node_allocator_traits::
- select_on_container_copy_construction(x.node_alloc())) {}
+ select_on_container_copy_construction(x.node_alloc()))
+ {
+ this->init(x);
+ }
grouped_table_impl(grouped_table_impl const& x,
node_allocator const& a)
: table(x, a)
- {}
+ {
+ this->init(x);
+ }
grouped_table_impl(grouped_table_impl& x,
boost::unordered::detail::move_tag m)
@@ -220,7 +222,9 @@
node_allocator const& a,
boost::unordered::detail::move_tag m)
: table(x, a, m)
- {}
+ {
+ this->move_init(x);
+ }
// Accessors
@@ -230,6 +234,8 @@
Key const& k,
Pred const& eq) const
{
+ if (!this->size_) return iterator();
+
std::size_t bucket_index =
policy::to_bucket(this->bucket_count_, key_hash);
iterator n = this->get_start(bucket_index);
@@ -487,8 +493,7 @@
iterator emplace(BOOST_UNORDERED_EMPLACE_ARGS)
{
node_constructor a(this->node_alloc());
- a.construct_node();
- a.construct_value(BOOST_UNORDERED_EMPLACE_FORWARD);
+ a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD);
return iterator(emplace_impl(a));
}
@@ -507,8 +512,7 @@
std::size_t distance = boost::unordered::detail::distance(i, j);
if(distance == 1) {
node_constructor a(this->node_alloc());
- a.construct_node();
- a.construct_value2(*i);
+ a.construct_with_value2(*i);
emplace_impl(a);
}
else {
@@ -517,8 +521,7 @@
node_constructor a(this->node_alloc());
for (; i != j; ++i) {
- a.construct_node();
- a.construct_value2(*i);
+ a.construct_with_value2(*i);
emplace_impl_no_rehash(a);
}
}
@@ -530,8 +533,7 @@
{
node_constructor a(this->node_alloc());
for (; i != j; ++i) {
- a.construct_node();
- a.construct_value2(*i);
+ a.construct_with_value2(*i);
emplace_impl(a);
}
}
@@ -710,20 +712,12 @@
}
////////////////////////////////////////////////////////////////////////
- // copy_buckets_to
- //
- // Basic exception safety. If an exception is thrown this will
- // leave dst partially filled and the buckets unset.
+ // fill_buckets
- static void copy_buckets_to(buckets const& src, buckets& dst)
+ template <class NodeCreator>
+ static void fill_buckets(iterator n, table& dst,
+ NodeCreator& creator)
{
- BOOST_ASSERT(!dst.buckets_);
-
- dst.create_buckets();
-
- node_constructor a(dst.node_alloc());
-
- iterator n = src.get_start();
previous_pointer prev = dst.get_previous_start();
while (n.node_) {
@@ -733,10 +727,7 @@
static_cast<node_pointer>(n.node_->group_prev_)->next_
));
- a.construct_node();
- a.construct_value2(*n);
-
- node_pointer first_node = a.release();
+ 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);
@@ -744,56 +735,7 @@
for (++n; n != group_end; ++n)
{
- a.construct_node();
- a.construct_value2(*n);
- end = a.release();
- end->hash_ = key_hash;
- add_after_node(end, first_node);
- ++dst.size_;
- }
-
- prev = place_in_bucket(dst, prev, end);
- }
- }
-
- ////////////////////////////////////////////////////////////////////////
- // move_buckets_to
- //
- // Basic exception safety. The source nodes are left in an unusable
- // state if an exception throws.
-
- static void move_buckets_to(buckets& src, buckets& dst)
- {
- BOOST_ASSERT(!dst.buckets_);
-
- dst.create_buckets();
-
- node_constructor a(dst.node_alloc());
-
- iterator n = src.get_start();
- previous_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_
- ));
-
- a.construct_node();
- a.construct_value2(boost::move(*n));
-
- node_pointer first_node = a.release();
- node_pointer end = first_node;
- first_node->hash_ = key_hash;
- prev->next_ = static_cast<link_pointer>(first_node);
- ++dst.size_;
-
- for(++n; n != group_end; ++n)
- {
- a.construct_node();
- a.construct_value2(boost::move(*n));
- end = a.release();
+ end = creator.create(*n);
end->hash_ = key_hash;
add_after_node(end, first_node);
++dst.size_;
@@ -806,33 +748,19 @@
// strong otherwise exception safety
void rehash_impl(std::size_t num_buckets)
{
- BOOST_ASSERT(this->size_);
-
- buckets dst(this->node_alloc(), num_buckets);
- dst.create_buckets();
+ BOOST_ASSERT(this->buckets_);
- previous_pointer src_start = this->get_previous_start();
- previous_pointer dst_start = dst.get_previous_start();
-
- dst_start->next_ = src_start->next_;
- src_start->next_ = link_pointer();
- dst.size_ = this->size_;
- this->size_ = 0;
-
- previous_pointer prev = dst_start;
+ this->create_buckets(num_buckets);
+ previous_pointer prev = this->get_previous_start();
while (prev->next_)
- prev = place_in_bucket(dst, prev,
+ prev = place_in_bucket(*this, prev,
static_cast<node_pointer>(
static_cast<node_pointer>(prev->next_)->group_prev_));
-
- // Swap the new nodes back into the container and setup the
- // variables.
- dst.swap(*this); // no throw
}
// Iterate through the nodes placing them in the correct buckets.
// pre: prev->next_ is not null.
- static previous_pointer place_in_bucket(buckets& dst,
+ static previous_pointer place_in_bucket(table& dst,
previous_pointer prev, node_pointer end)
{
bucket_pointer b = dst.get_bucket(policy::to_bucket(
Modified: branches/release/boost/unordered/detail/table.hpp
==============================================================================
--- branches/release/boost/unordered/detail/table.hpp (original)
+++ branches/release/boost/unordered/detail/table.hpp 2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -13,6 +13,11 @@
#include <boost/type_traits/alignment_of.hpp>
#include <cmath>
+#if defined(BOOST_MSVC)
+#pragma warning(push)
+#pragma warning(disable:4127) // conditional expression is constant
+#endif
+
namespace boost { namespace unordered { namespace detail {
////////////////////////////////////////////////////////////////////////////
@@ -54,13 +59,73 @@
value_base& operator=(value_base const&);
};
+ template <typename NodeAlloc>
+ struct copy_nodes
+ {
+ typedef boost::unordered::detail::allocator_traits<NodeAlloc>
+ node_allocator_traits;
+
+ node_constructor<NodeAlloc> constructor;
+
+ explicit copy_nodes(NodeAlloc& a) : constructor(a) {}
+
+ typename node_allocator_traits::pointer create(
+ typename node_allocator_traits::value_type::value_type const& v)
+ {
+ constructor.construct_with_value2(v);
+ return constructor.release();
+ }
+ };
+
+ template <typename NodeAlloc>
+ struct move_nodes
+ {
+ typedef boost::unordered::detail::allocator_traits<NodeAlloc>
+ node_allocator_traits;
+
+ node_constructor<NodeAlloc> constructor;
+
+ explicit move_nodes(NodeAlloc& a) : constructor(a) {}
+
+ typename node_allocator_traits::pointer create(
+ typename node_allocator_traits::value_type::value_type& v)
+ {
+ constructor.construct_with_value2(boost::move(v));
+ return constructor.release();
+ }
+ };
+
+ template <typename Buckets>
+ struct assign_nodes
+ {
+ node_holder<typename Buckets::node_allocator> holder;
+
+ explicit assign_nodes(Buckets& b) : holder(b) {}
+
+ typename Buckets::node_pointer create(
+ typename Buckets::value_type const& v)
+ {
+ return holder.copy_of(v);
+ }
+ };
+
+ template <typename Buckets>
+ struct move_assign_nodes
+ {
+ node_holder<typename Buckets::node_allocator> holder;
+
+ explicit move_assign_nodes(Buckets& b) : holder(b) {}
+
+ typename Buckets::node_pointer create(
+ typename Buckets::value_type& v)
+ {
+ return holder.move_copy_of(v);
+ }
+ };
+
template <typename Types>
struct table :
- boost::unordered::detail::buckets<
- typename Types::allocator,
- typename Types::bucket,
- typename Types::node,
- typename Types::policy>,
+ Types::policy,
boost::unordered::detail::functions<
typename Types::hasher,
typename Types::key_equal>
@@ -69,6 +134,8 @@
table(table const&);
table& operator=(table const&);
public:
+ typedef typename Types::node node;
+ typedef typename Types::bucket bucket;
typedef typename Types::hasher hasher;
typedef typename Types::key_equal key_equal;
typedef typename Types::key_type key_type;
@@ -82,23 +149,128 @@
typename Types::hasher,
typename Types::key_equal> functions;
- typedef boost::unordered::detail::buckets<
- typename Types::allocator,
- typename Types::bucket,
- typename Types::node,
- typename Types::policy> buckets;
-
- typedef typename buckets::node_allocator node_allocator;
- typedef typename buckets::node_allocator_traits node_allocator_traits;
- typedef typename buckets::node_pointer node_pointer;
- typedef typename buckets::const_node_pointer const_node_pointer;
-
- typedef typename table::iterator iterator;
+ typedef typename Types::allocator allocator;
+ typedef typename boost::unordered::detail::
+ rebind_wrap<allocator, node>::type node_allocator;
+ typedef typename boost::unordered::detail::
+ rebind_wrap<allocator, bucket>::type bucket_allocator;
+ typedef boost::unordered::detail::allocator_traits<node_allocator>
+ node_allocator_traits;
+ typedef boost::unordered::detail::allocator_traits<bucket_allocator>
+ bucket_allocator_traits;
+ typedef typename node_allocator_traits::pointer
+ node_pointer;
+ typedef typename node_allocator_traits::const_pointer
+ 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;
+ typedef boost::unordered::iterator_detail::
+ c_iterator<const_node_pointer, node_pointer, value_type> c_iterator;
+ typedef boost::unordered::iterator_detail::
+ l_iterator<node_pointer, value_type, policy> l_iterator;
+ typedef boost::unordered::iterator_detail::
+ cl_iterator<const_node_pointer, node_pointer, value_type, policy>
+ cl_iterator;
+ ////////////////////////////////////////////////////////////////////////
// Members
+ boost::unordered::detail::compressed<bucket_allocator, node_allocator>
+ allocators_;
+ std::size_t bucket_count_;
+ std::size_t size_;
float mlf_;
- std::size_t max_load_; // Only use if this->buckets_.
+ std::size_t max_load_; // Only use if buckets_.
+ bucket_pointer buckets_;
+
+ ////////////////////////////////////////////////////////////////////////
+ // Data access
+
+ bucket_allocator const& bucket_alloc() const
+ {
+ return allocators_.first();
+ }
+
+ node_allocator const& node_alloc() const
+ {
+ return allocators_.second();
+ }
+
+ bucket_allocator& bucket_alloc()
+ {
+ return allocators_.first();
+ }
+
+ node_allocator& node_alloc()
+ {
+ return allocators_.second();
+ }
+
+ std::size_t max_bucket_count() const
+ {
+ // -1 to account for the start bucket.
+ return policy::prev_bucket_count(
+ bucket_allocator_traits::max_size(bucket_alloc()) - 1);
+ }
+
+ bucket_pointer get_bucket(std::size_t bucket_index) const
+ {
+ return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
+ }
+
+ previous_pointer get_previous_start() const
+ {
+ return get_bucket(bucket_count_)->first_from_start();
+ }
+
+ previous_pointer get_previous_start(std::size_t bucket_index) const
+ {
+ return get_bucket(bucket_index)->next_;
+ }
+
+ iterator get_start() const
+ {
+ return iterator(static_cast<node_pointer>(
+ get_previous_start()->next_));
+ }
+
+ iterator get_start(std::size_t bucket_index) const
+ {
+ previous_pointer prev = get_previous_start(bucket_index);
+ return prev ? iterator(static_cast<node_pointer>(prev->next_)) :
+ iterator();
+ }
+
+ float load_factor() const
+ {
+ BOOST_ASSERT(bucket_count_ != 0);
+ return static_cast<float>(size_)
+ / static_cast<float>(bucket_count_);
+ }
+
+ std::size_t bucket_size(std::size_t index) const
+ {
+ if (!size_) return 0;
+ iterator it = get_start(index);
+ if (!it.node_) return 0;
+
+ std::size_t count = 0;
+ while(it.node_ && policy::to_bucket(
+ bucket_count_, it.node_->hash_) == index)
+ {
+ ++count;
+ ++it;
+ }
+
+ return count;
+ }
////////////////////////////////////////////////////////////////////////
// Load methods
@@ -109,34 +281,34 @@
// size < mlf_ * count
return boost::unordered::detail::double_to_size(ceil(
- static_cast<double>(this->mlf_) *
- static_cast<double>(this->max_bucket_count())
+ static_cast<double>(mlf_) *
+ static_cast<double>(max_bucket_count())
)) - 1;
}
- std::size_t calculate_max_load()
+ void recalculate_max_load()
{
using namespace std;
// From 6.3.1/13:
// Only resize when size >= mlf_ * count
- return boost::unordered::detail::double_to_size(ceil(
- static_cast<double>(this->mlf_) *
- static_cast<double>(this->bucket_count_)
+ max_load_ = boost::unordered::detail::double_to_size(ceil(
+ static_cast<double>(mlf_) *
+ static_cast<double>(bucket_count_)
));
}
+
void max_load_factor(float z)
{
BOOST_ASSERT(z > 0);
mlf_ = (std::max)(z, minimum_max_load_factor);
- if (this->buckets_)
- this->max_load_ = this->calculate_max_load();
+ if (buckets_) recalculate_max_load();
}
std::size_t min_buckets_for_size(std::size_t size) const
{
- BOOST_ASSERT(this->mlf_ >= minimum_max_load_factor);
+ BOOST_ASSERT(mlf_ >= minimum_max_load_factor);
using namespace std;
@@ -160,127 +332,450 @@
hasher const& hf,
key_equal const& eq,
node_allocator const& a) :
- buckets(a, policy::new_bucket_count(num_buckets)),
functions(hf, eq),
+ allocators_(a,a),
+ bucket_count_(policy::new_bucket_count(num_buckets)),
+ size_(0),
mlf_(1.0f),
- max_load_(0)
+ max_load_(0),
+ buckets_()
{}
table(table const& x, node_allocator const& a) :
- buckets(a, x.min_buckets_for_size(x.size_)),
functions(x),
+ allocators_(a,a),
+ bucket_count_(x.min_buckets_for_size(x.size_)),
+ size_(0),
mlf_(x.mlf_),
- max_load_(0)
- {
- if(x.size_) {
- table_impl::copy_buckets_to(x, *this);
- this->max_load_ = calculate_max_load();
- }
- }
+ max_load_(0),
+ buckets_()
+ {}
- // TODO: Why calculate_max_load?
table(table& x, boost::unordered::detail::move_tag m) :
- buckets(x, m),
functions(x),
+ allocators_(x.allocators_, m),
+ bucket_count_(x.bucket_count_),
+ size_(x.size_),
mlf_(x.mlf_),
- max_load_(calculate_max_load())
- {}
+ max_load_(x.max_load_),
+ buckets_(x.buckets_)
+ {
+ x.buckets_ = bucket_pointer();
+ x.size_ = 0;
+ }
- // TODO: Why not calculate_max_load?
- // TODO: Why do I use x's bucket count?
table(table& x, node_allocator const& a,
- boost::unordered::detail::move_tag m) :
- buckets(a, x.bucket_count_),
+ boost::unordered::detail::move_tag) :
functions(x),
+ allocators_(a, a),
+ bucket_count_(x.bucket_count_),
+ size_(0),
mlf_(x.mlf_),
- max_load_(x.max_load_)
+ max_load_(x.max_load_),
+ buckets_()
+ {}
+
+ ////////////////////////////////////////////////////////////////////////
+ // Initialisation.
+
+ void init(table const& x)
{
- if(a == x.node_alloc()) {
- this->buckets::swap(x, false_type());
+ if (x.size_) {
+ create_buckets(bucket_count_);
+ copy_nodes<node_allocator> copy(node_alloc());
+ table_impl::fill_buckets(x.get_start(), *this, copy);
+ }
+ }
+
+ void move_init(table& x)
+ {
+ if(node_alloc() == x.node_alloc()) {
+ move_buckets_from(x);
}
else if(x.size_) {
- // Use a temporary table because move_buckets_to leaves the
- // source container in a complete mess.
+ // TODO: Could pick new bucket size?
+ create_buckets(bucket_count_);
+
+ move_nodes<node_allocator> move(node_alloc());
+ node_holder<node_allocator> nodes(x);
+ table_impl::fill_buckets(nodes.get_start(), *this, move);
+ }
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Create buckets
+
+ void create_buckets(std::size_t new_count)
+ {
+ boost::unordered::detail::array_constructor<bucket_allocator>
+ constructor(bucket_alloc());
+
+ // Creates an extra bucket to act as the start node.
+ constructor.construct(bucket(), new_count + 1);
+
+ if (buckets_)
+ {
+ // Copy the nodes to the new buckets, including the dummy
+ // node if there is one.
+ (constructor.get() +
+ static_cast<std::ptrdiff_t>(new_count))->next_ =
+ (buckets_ + static_cast<std::ptrdiff_t>(
+ bucket_count_))->next_;
+ destroy_buckets();
+ }
+ else if (bucket::extra_node)
+ {
+ node_constructor a(node_alloc());
+ a.construct();
+
+ (constructor.get() +
+ static_cast<std::ptrdiff_t>(new_count))->next_ =
+ a.release();
+ }
+
+ bucket_count_ = new_count;
+ buckets_ = constructor.release();
+ recalculate_max_load();
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Swap and Move
+
+ void swap_allocators(table& other, false_type)
+ {
+ // According to 23.2.1.8, if propagate_on_container_swap is
+ // false the behaviour is undefined unless the allocators
+ // are equal.
+ BOOST_ASSERT(node_alloc() == other.node_alloc());
+ }
+
+ void swap_allocators(table& other, true_type)
+ {
+ allocators_.swap(other.allocators_);
+ }
+
+ // Only swaps the allocators if propagate_on_container_swap
+ void swap(table& x)
+ {
+ boost::unordered::detail::set_hash_functions<hasher, key_equal>
+ op1(*this, x);
+ boost::unordered::detail::set_hash_functions<hasher, key_equal>
+ op2(x, *this);
+
+ // I think swap can throw if Propagate::value,
+ // since the allocators' swap can throw. Not sure though.
+ swap_allocators(x,
+ boost::unordered::detail::integral_constant<bool,
+ allocator_traits<node_allocator>::
+ propagate_on_container_swap::value>());
+
+ boost::swap(buckets_, x.buckets_);
+ boost::swap(bucket_count_, x.bucket_count_);
+ boost::swap(size_, x.size_);
+ std::swap(mlf_, x.mlf_);
+ std::swap(max_load_, x.max_load_);
+ op1.commit();
+ op2.commit();
+ }
+
+ void move_buckets_from(table& other)
+ {
+ BOOST_ASSERT(node_alloc() == other.node_alloc());
+ BOOST_ASSERT(!buckets_);
+ buckets_ = other.buckets_;
+ bucket_count_ = other.bucket_count_;
+ size_ = other.size_;
+ other.buckets_ = bucket_pointer();
+ other.size_ = 0;
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Delete/destruct
+
+ ~table()
+ {
+ delete_buckets();
+ }
+
+ void delete_node(c_iterator n)
+ {
+ boost::unordered::detail::destroy_value_impl(node_alloc(),
+ n.node_->value_ptr());
+ node_allocator_traits::destroy(node_alloc(),
+ boost::addressof(*n.node_));
+ node_allocator_traits::deallocate(node_alloc(), n.node_, 1);
+ --size_;
+ }
+
+ std::size_t delete_nodes(c_iterator begin, c_iterator end)
+ {
+ std::size_t count = 0;
+
+ while(begin != end) {
+ c_iterator n = begin;
+ ++begin;
+ delete_node(n);
+ ++count;
+ }
+
+ return count;
+ }
+
+ void delete_buckets()
+ {
+ if(buckets_) {
+ delete_nodes(get_start(), iterator());
+
+ if (bucket::extra_node) {
+ node_pointer n = static_cast<node_pointer>(
+ get_bucket(bucket_count_)->next_);
+ node_allocator_traits::destroy(node_alloc(),
+ boost::addressof(*n));
+ node_allocator_traits::deallocate(node_alloc(), n, 1);
+ }
+
+ destroy_buckets();
+ buckets_ = bucket_pointer();
+ }
+
+ BOOST_ASSERT(!size_);
+ }
+
+ void clear()
+ {
+ if(!size_) return;
+
+ delete_nodes(get_start(), iterator());
+ get_previous_start()->next_ = link_pointer();
+ clear_buckets();
+
+ BOOST_ASSERT(!size_);
+ }
+
+ void clear_buckets()
+ {
+ bucket_pointer end = get_bucket(bucket_count_);
+ for(bucket_pointer it = buckets_; it != end; ++it)
+ {
+ it->next_ = node_pointer();
+ }
+ }
+
+ void destroy_buckets()
+ {
+ bucket_pointer end = get_bucket(bucket_count_ + 1);
+ for(bucket_pointer it = buckets_; it != end; ++it)
+ {
+ bucket_allocator_traits::destroy(bucket_alloc(),
+ boost::addressof(*it));
+ }
+
+ bucket_allocator_traits::deallocate(bucket_alloc(),
+ buckets_, bucket_count_ + 1);
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Fix buckets after erase
+
+ // 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)
+ {
+ if (!next)
+ {
+ if (this_bucket->next_ == prev)
+ this_bucket->next_ = node_pointer();
+ }
+ else
+ {
+ bucket_pointer next_bucket = get_bucket(
+ policy::to_bucket(bucket_count_, next->hash_));
+
+ if (next_bucket != this_bucket)
+ {
+ next_bucket->next_ = prev;
+ if (this_bucket->next_ == prev)
+ this_bucket->next_ = node_pointer();
+ }
+ }
+ }
+
+ // 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) 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;
+ }
+ }
+ }
+
+ // 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();
+ }
+ };
- buckets tmp(x, m);
- table_impl::move_buckets_to(tmp, *this);
- this->max_load_ = calculate_max_load();
+ // Finally fix the bucket containing the trailing node.
+ if (n) {
+ get_bucket(
+ policy::to_bucket(bucket_count_, n->hash_))->next_
+ = prev;
}
}
+ ////////////////////////////////////////////////////////////////////////
// Iterators
iterator begin() const {
- return !this->buckets_ ?
- iterator() : this->get_start();
+ return !buckets_ ? iterator() : get_start();
}
+ ////////////////////////////////////////////////////////////////////////
// Assignment
void assign(table const& x)
{
- assign(x,
- boost::unordered::detail::integral_constant<bool,
- allocator_traits<node_allocator>::
- propagate_on_container_copy_assignment::value>());
+ if (this != boost::addressof(x))
+ {
+ assign(x,
+ boost::unordered::detail::integral_constant<bool,
+ allocator_traits<node_allocator>::
+ propagate_on_container_copy_assignment::value>());
+ }
}
void assign(table const& x, false_type)
{
- table tmp(x, this->node_alloc());
- this->swap(tmp, false_type());
+ // Strong exception safety.
+ boost::unordered::detail::set_hash_functions<hasher, key_equal>
+ new_func_this(*this, x);
+ new_func_this.commit();
+ mlf_ = x.mlf_;
+ recalculate_max_load();
+
+ if (!size_ && !x.size_) return;
+
+ if (!buckets_ || x.size_ >= max_load_) {
+ create_buckets(min_buckets_for_size(x.size_));
+ }
+ else {
+ clear_buckets();
+ }
+
+ // assign_nodes takes ownership of the container's elements,
+ // assigning to them if possible, and deleting any that are
+ // left over.
+ assign_nodes<table> assign(*this);
+
+ if (x.size_) {
+ table_impl::fill_buckets(x.get_start(), *this, assign);
+ }
}
void assign(table const& x, true_type)
{
- table tmp(x, x.node_alloc());
- // Need to delete before setting the allocator so that buckets
- // aren't deleted with the wrong allocator.
- if(this->buckets_) this->delete_buckets();
- // TODO: Can allocator assignment throw?
- this->allocators_.assign(x.allocators_);
- this->swap(tmp, false_type());
+ if (node_alloc() == x.node_alloc()) {
+ allocators_.assign(x.allocators_);
+ assign(x, false_type());
+ }
+ else {
+ boost::unordered::detail::set_hash_functions<hasher, key_equal>
+ new_func_this(*this, x);
+
+ // Delete everything with current allocators before assigning
+ // the new ones.
+ if (buckets_) delete_buckets();
+ allocators_.assign(x.allocators_);
+
+ // Copy over other data, all no throw.
+ new_func_this.commit();
+ mlf_ = x.mlf_;
+ bucket_count_ = min_buckets_for_size(x.size_);
+ max_load_ = 0;
+
+ // Finally copy the elements.
+ if (x.size_) {
+ create_buckets(bucket_count_);
+ copy_nodes<node_allocator> copy(node_alloc());
+ table_impl::fill_buckets(x.get_start(), *this, copy);
+ }
+ }
}
void move_assign(table& x)
{
- move_assign(x,
- boost::unordered::detail::integral_constant<bool,
- allocator_traits<node_allocator>::
- propagate_on_container_move_assignment::value>());
+ if (this != boost::addressof(x))
+ {
+ move_assign(x,
+ boost::unordered::detail::integral_constant<bool,
+ allocator_traits<node_allocator>::
+ propagate_on_container_move_assignment::value>());
+ }
}
void move_assign(table& x, true_type)
{
- if(this->buckets_) this->delete_buckets();
- this->allocators_.move_assign(x.allocators_);
+ if(buckets_) delete_buckets();
+ allocators_.move_assign(x.allocators_);
move_assign_no_alloc(x);
}
void move_assign(table& x, false_type)
{
- if(this->node_alloc() == x.node_alloc()) {
- if(this->buckets_) this->delete_buckets();
+ if (node_alloc() == x.node_alloc()) {
+ if(buckets_) delete_buckets();
move_assign_no_alloc(x);
}
else {
boost::unordered::detail::set_hash_functions<hasher, key_equal>
new_func_this(*this, x);
+ new_func_this.commit();
+ mlf_ = x.mlf_;
+ recalculate_max_load();
- if (x.size_) {
- buckets b(this->node_alloc(),
- x.min_buckets_for_size(x.size_));
- buckets tmp(x, move_tag());
- table_impl::move_buckets_to(tmp, b);
- b.swap(*this);
+ if (!size_ && !x.size_) return;
+
+ if (!buckets_ || x.size_ >= max_load_) {
+ create_buckets(min_buckets_for_size(x.size_));
}
else {
- this->clear();
+ clear_buckets();
+ }
+
+ // move_assign_nodes takes ownership of the container's
+ // elements, assigning to them if possible, and deleting
+ // any that are left over.
+ move_assign_nodes<table> assign(*this);
+
+ if (x.size_) {
+ node_holder<node_allocator> nodes(x);
+ table_impl::fill_buckets(nodes.get_start(), *this, assign);
}
-
- this->mlf_ = x.mlf_;
- if (this->buckets_) this->max_load_ = calculate_max_load();
- new_func_this.commit();
}
}
@@ -289,53 +784,12 @@
boost::unordered::detail::set_hash_functions<hasher, key_equal>
new_func_this(*this, x);
// No throw from here.
- this->move_buckets_from(x);
- this->mlf_ = x.mlf_;
- this->max_load_ = x.max_load_;
+ move_buckets_from(x);
+ mlf_ = x.mlf_;
+ max_load_ = x.max_load_;
new_func_this.commit();
}
- ////////////////////////////////////////////////////////////////////////
- // Swap & Move
-
- void swap(table& x)
- {
- swap(x,
- boost::unordered::detail::integral_constant<bool,
- allocator_traits<node_allocator>::
- propagate_on_container_swap::value>());
- }
-
- // Only swaps the allocators if Propagate::value
- template <typename Propagate>
- void swap(table& x, Propagate p)
- {
- // According to 23.2.1.8, if propagate_on_container_swap is
- // false the behaviour is undefined unless the allocators
- // are equal.
- BOOST_ASSERT(p.value || this->node_alloc() == x.node_alloc());
-
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- op1(*this, x);
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- op2(x, *this);
- // I think swap can throw if Propagate::value,
- // since the allocators' swap can throw. Not sure though.
- this->buckets::swap(x, p);
- std::swap(this->mlf_, x.mlf_);
- std::swap(this->max_load_, x.max_load_);
- op1.commit();
- op2.commit();
- }
-
- // Swap everything but the allocators, and the functions objects.
- void swap_contents(table& x)
- {
- this->buckets::swap(x, false_type());
- std::swap(this->mlf_, x.mlf_);
- std::swap(this->max_load_, x.max_load_);
- }
-
// Accessors
key_type const& get_key(value_type const& x) const
@@ -356,7 +810,6 @@
Hash const& hf,
Pred const& eq) const
{
- if (!this->size_) return iterator();
return static_cast<table_impl const*>(this)->
find_node_impl(policy::apply_hash(hf, k), k, eq);
}
@@ -365,16 +818,14 @@
std::size_t key_hash,
key_type const& k) const
{
- if (!this->size_) return iterator();
return static_cast<table_impl const*>(this)->
find_node_impl(key_hash, k, this->key_eq());
}
iterator find_node(key_type const& k) const
{
- if (!this->size_) return iterator();
return static_cast<table_impl const*>(this)->
- find_node_impl(this->hash(k), k, this->key_eq());
+ find_node_impl(hash(k), k, this->key_eq());
}
iterator find_matching_node(iterator n) const
@@ -402,22 +853,19 @@
template <typename Types>
inline void table<Types>::reserve_for_insert(std::size_t size)
{
- if (!this->buckets_) {
- this->bucket_count_ = (std::max)(this->bucket_count_,
- this->min_buckets_for_size(size));
- this->create_buckets();
- this->max_load_ = this->calculate_max_load();
+ if (!buckets_) {
+ create_buckets((std::max)(bucket_count_,
+ min_buckets_for_size(size)));
}
// According to the standard this should be 'size >= max_load_',
// but I think this is better, defect report filed.
else if(size > max_load_) {
std::size_t num_buckets
- = this->min_buckets_for_size((std::max)(size,
- this->size_ + (this->size_ >> 1)));
- if (num_buckets != this->bucket_count_) {
+ = min_buckets_for_size((std::max)(size,
+ size_ + (size_ >> 1)));
+
+ if (num_buckets != bucket_count_)
static_cast<table_impl*>(this)->rehash_impl(num_buckets);
- this->max_load_ = this->calculate_max_load();
- }
}
}
@@ -429,20 +877,18 @@
{
using namespace std;
- if(!this->size_) {
- if(this->buckets_) this->delete_buckets();
- this->bucket_count_ = policy::new_bucket_count(min_buckets);
+ if(!size_) {
+ if(buckets_) delete_buckets();
+ bucket_count_ = policy::new_bucket_count(min_buckets);
}
else {
min_buckets = policy::new_bucket_count((std::max)(min_buckets,
boost::unordered::detail::double_to_size(floor(
- static_cast<double>(this->size_) /
+ static_cast<double>(size_) /
static_cast<double>(mlf_))) + 1));
- if(min_buckets != this->bucket_count_) {
+ if(min_buckets != bucket_count_)
static_cast<table_impl*>(this)->rehash_impl(min_buckets);
- this->max_load_ = this->calculate_max_load();
- }
}
}
@@ -450,8 +896,12 @@
inline void table<Types>::reserve(std::size_t num_elements)
{
rehash(static_cast<std::size_t>(
- std::ceil(static_cast<double>(num_elements) / this->mlf_)));
+ std::ceil(static_cast<double>(num_elements) / mlf_)));
}
}}}
+#if defined(BOOST_MSVC)
+#pragma warning(pop)
+#endif
+
#endif
Modified: branches/release/boost/unordered/detail/unique.hpp
==============================================================================
--- branches/release/boost/unordered/detail/unique.hpp (original)
+++ branches/release/boost/unordered/detail/unique.hpp 2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -121,14 +121,12 @@
{
typedef boost::unordered::detail::set<A, T, H, P> types;
+ typedef A allocator;
typedef T value_type;
typedef H hasher;
typedef P key_equal;
typedef T key_type;
- typedef typename boost::unordered::detail::rebind_wrap<
- A, value_type>::type allocator;
-
typedef boost::unordered::detail::allocator_traits<allocator> traits;
typedef boost::unordered::detail::pick_node<allocator, value_type> pick;
typedef typename pick::node node;
@@ -146,15 +144,14 @@
{
typedef boost::unordered::detail::map<A, K, M, H, P> types;
+ typedef A allocator;
typedef std::pair<K const, M> value_type;
typedef H hasher;
typedef P key_equal;
typedef K key_type;
- typedef typename boost::unordered::detail::rebind_wrap<
- A, value_type>::type allocator;
-
- typedef boost::unordered::detail::allocator_traits<allocator> traits;
+ typedef boost::unordered::detail::allocator_traits<allocator>
+ traits;
typedef boost::unordered::detail::pick_node<allocator, value_type> pick;
typedef typename pick::node node;
typedef typename pick::bucket bucket;
@@ -173,7 +170,6 @@
typedef boost::unordered::detail::table<Types> table;
typedef typename table::value_type value_type;
typedef typename table::bucket bucket;
- typedef typename table::buckets buckets;
typedef typename table::policy policy;
typedef typename table::node_pointer node_pointer;
typedef typename table::node_allocator node_allocator;
@@ -202,12 +198,17 @@
table_impl(table_impl const& x)
: table(x, node_allocator_traits::
- select_on_container_copy_construction(x.node_alloc())) {}
+ select_on_container_copy_construction(x.node_alloc()))
+ {
+ this->init(x);
+ }
table_impl(table_impl const& x,
node_allocator const& a)
: table(x, a)
- {}
+ {
+ this->init(x);
+ }
table_impl(table_impl& x,
boost::unordered::detail::move_tag m)
@@ -218,7 +219,9 @@
node_allocator const& a,
boost::unordered::detail::move_tag m)
: table(x, a, m)
- {}
+ {
+ this->move_init(x);
+ }
// Accessors
@@ -228,6 +231,8 @@
Key const& k,
Pred const& eq) const
{
+ if (!this->size_) return iterator();
+
std::size_t bucket_index =
policy::to_bucket(this->bucket_count_, key_hash);
iterator n = this->get_start(bucket_index);
@@ -349,9 +354,7 @@
// Create the node before rehashing in case it throws an
// exception (need strong safety in such a case).
node_constructor a(this->node_alloc());
- a.construct_node();
-
- a.construct_value(BOOST_UNORDERED_EMPLACE_ARGS3(
+ a.construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS3(
boost::unordered::piecewise_construct,
boost::make_tuple(k),
boost::make_tuple()));
@@ -413,8 +416,7 @@
// Create the node before rehashing in case it throws an
// exception (need strong safety in such a case).
node_constructor a(this->node_alloc());
- a.construct_node();
- a.construct_value(BOOST_UNORDERED_EMPLACE_FORWARD);
+ a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD);
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
@@ -442,8 +444,7 @@
// Don't have a key, so construct the node first in order
// to be able to lookup the position.
node_constructor a(this->node_alloc());
- a.construct_node();
- a.construct_value(BOOST_UNORDERED_EMPLACE_FORWARD);
+ a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD);
return emplace_impl_with_node(a);
}
@@ -490,8 +491,7 @@
InputIt i, InputIt j)
{
std::size_t key_hash = this->hash(k);
- a.construct_node();
- a.construct_value2(*i);
+ a.construct_with_value2(*i);
this->reserve_for_insert(this->size_ +
boost::unordered::detail::insert_size(i, j));
this->add_node(a, key_hash);
@@ -506,9 +506,7 @@
iterator pos = this->find_node(key_hash, k);
if (!pos.node_) {
- a.construct_node();
- a.construct_value2(*i);
-
+ a.construct_with_value2(*i);
if(this->size_ + 1 > this->max_load_)
this->reserve_for_insert(this->size_ +
boost::unordered::detail::insert_size(i, j));
@@ -524,8 +522,7 @@
node_constructor a(this->node_alloc());
do {
- a.construct_node();
- a.construct_value2(*i);
+ a.construct_with_value2(*i);
emplace_impl_with_node(a);
} while(++i != j);
}
@@ -617,58 +614,16 @@
}
////////////////////////////////////////////////////////////////////////
- // copy_buckets_to
- //
- // Basic exception safety. If an exception is thrown this will
- // leave dst partially filled and the buckets unset.
-
- static void copy_buckets_to(buckets const& src, buckets& dst)
- {
- BOOST_ASSERT(!dst.buckets_);
-
- dst.create_buckets();
-
- node_constructor a(dst.node_alloc());
-
- iterator n = src.get_start();
- previous_pointer prev = dst.get_previous_start();
-
- while(n.node_) {
- a.construct_node();
- a.construct_value2(*n);
-
- node_pointer node = a.release();
- node->hash_ = n.node_->hash_;
- prev->next_ = static_cast<link_pointer>(node);
- ++dst.size_;
- ++n;
-
- prev = place_in_bucket(dst, prev);
- }
- }
-
- ////////////////////////////////////////////////////////////////////////
- // move_buckets_to
- //
- // Basic exception safety. The source nodes are left in an unusable
- // state if an exception throws.
+ // fill_buckets
- static void move_buckets_to(buckets& src, buckets& dst)
+ template <class NodeCreator>
+ static void fill_buckets(iterator n, table& dst,
+ NodeCreator& creator)
{
- BOOST_ASSERT(!dst.buckets_);
-
- dst.create_buckets();
-
- node_constructor a(dst.node_alloc());
-
- iterator n = src.get_start();
previous_pointer prev = dst.get_previous_start();
while (n.node_) {
- a.construct_node();
- a.construct_value2(boost::move(*n));
-
- node_pointer node = a.release();
+ node_pointer node = creator.create(*n);
node->hash_ = n.node_->hash_;
prev->next_ = static_cast<link_pointer>(node);
++dst.size_;
@@ -681,36 +636,22 @@
// strong otherwise exception safety
void rehash_impl(std::size_t num_buckets)
{
- BOOST_ASSERT(this->size_);
-
- buckets dst(this->node_alloc(), num_buckets);
- dst.create_buckets();
+ BOOST_ASSERT(this->buckets_);
- previous_pointer src_start = this->get_previous_start();
- previous_pointer dst_start = dst.get_previous_start();
-
- dst_start->next_ = src_start->next_;
- src_start->next_ = link_pointer();
- dst.size_ = this->size_;
- this->size_ = 0;
-
- previous_pointer prev = dst.get_previous_start();
+ this->create_buckets(num_buckets);
+ previous_pointer prev = this->get_previous_start();
while (prev->next_)
- prev = place_in_bucket(dst, prev);
-
- // Swap the new nodes back into the container and setup the
- // variables.
- dst.swap(*this); // no throw
+ 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(buckets& dst,
+ static previous_pointer place_in_bucket(table& dst,
previous_pointer prev)
{
node_pointer n = static_cast<node_pointer>(prev->next_);
bucket_pointer b = dst.get_bucket(
- buckets::to_bucket(dst.bucket_count_, n->hash_));
+ table::to_bucket(dst.bucket_count_, n->hash_));
if (!b->next_) {
b->next_ = 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-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -56,7 +56,6 @@
private:
typedef boost::unordered::detail::map<A, K, T, H, P> types;
- typedef typename types::allocator value_allocator;
typedef typename types::traits allocator_traits;
typedef typename types::table table;
@@ -542,7 +541,6 @@
private:
typedef boost::unordered::detail::multimap<A, K, T, H, P> types;
- typedef typename types::allocator value_allocator;
typedef typename types::traits allocator_traits;
typedef typename types::table table;
Modified: branches/release/boost/unordered/unordered_set.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_set.hpp (original)
+++ branches/release/boost/unordered/unordered_set.hpp 2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -54,7 +54,6 @@
private:
typedef boost::unordered::detail::set<A, T, H, P> types;
- typedef typename types::allocator value_allocator;
typedef typename types::traits allocator_traits;
typedef typename types::table table;
@@ -526,7 +525,6 @@
private:
typedef boost::unordered::detail::multiset<A, T, H, P> types;
- typedef typename types::allocator value_allocator;
typedef typename types::traits allocator_traits;
typedef typename types::table table;
Modified: branches/release/libs/unordered/test/objects/test.hpp
==============================================================================
--- branches/release/libs/unordered/test/objects/test.hpp (original)
+++ branches/release/libs/unordered/test/objects/test.hpp 2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -186,9 +186,8 @@
}
};
- // allocator1 and allocator2 are pretty similar.
// allocator1 only has the old fashioned 'construct' method and has
- // a few less typedefs
+ // a few less typedefs. allocator2 uses a custom pointer class.
template <class T>
class allocator1
@@ -273,6 +272,127 @@
};
};
+ template <class T> class ptr;
+ template <class T> class const_ptr;
+
+ struct void_ptr
+ {
+#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+ template <typename T>
+ friend class ptr;
+ private:
+#endif
+
+ void* ptr_;
+
+ public:
+ void_ptr() : ptr_(0) {}
+
+ template <typename T>
+ explicit void_ptr(ptr<T> const& x) : ptr_(x.ptr_) {}
+
+ // I'm not using the safe bool idiom because the containers should be
+ // able to cope with bool conversions.
+ operator bool() const { return !!ptr_; }
+
+ bool operator==(void_ptr const& x) const { return ptr_ == x.ptr_; }
+ bool operator!=(void_ptr const& x) const { return ptr_ != x.ptr_; }
+ };
+
+ class void_const_ptr
+ {
+#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+ template <typename T>
+ friend class const_ptr;
+ private:
+#endif
+
+ void* ptr_;
+
+ public:
+ void_const_ptr() : ptr_(0) {}
+
+ template <typename T>
+ explicit void_const_ptr(const_ptr<T> const& x) : ptr_(x.ptr_) {}
+
+ // I'm not using the safe bool idiom because the containers should be
+ // able to cope with bool conversions.
+ operator bool() const { return !!ptr_; }
+
+ bool operator==(void_const_ptr const& x) const { return ptr_ == x.ptr_; }
+ bool operator!=(void_const_ptr const& x) const { return ptr_ != x.ptr_; }
+ };
+
+ template <class T>
+ class ptr
+ {
+ friend class allocator2<T>;
+ friend class const_ptr<T>;
+ friend struct void_ptr;
+
+ T* ptr_;
+
+ ptr(T* x) : ptr_(x) {}
+ public:
+ ptr() : ptr_(0) {}
+ explicit ptr(void_ptr const& x) : ptr_((T*) x.ptr_) {}
+
+ T& operator*() const { return *ptr_; }
+ T* operator->() const { return ptr_; }
+ ptr& operator++() { ++ptr_; return *this; }
+ ptr operator++(int) { ptr tmp(*this); ++ptr_; return tmp; }
+ ptr operator+(std::ptrdiff_t s) const { return ptr<T>(ptr_ + s); }
+ friend ptr operator+(std::ptrdiff_t s, ptr p)
+ { return ptr<T>(s + p.ptr_); }
+ T& operator[](std::ptrdiff_t s) const { return ptr_[s]; }
+ bool operator!() const { return !ptr_; }
+
+ // I'm not using the safe bool idiom because the containers should be
+ // able to cope with bool conversions.
+ operator bool() const { return !!ptr_; }
+
+ bool operator==(ptr const& x) const { return ptr_ == x.ptr_; }
+ bool operator!=(ptr const& x) const { return ptr_ != x.ptr_; }
+ bool operator<(ptr const& x) const { return ptr_ < x.ptr_; }
+ bool operator>(ptr const& x) const { return ptr_ > x.ptr_; }
+ bool operator<=(ptr const& x) const { return ptr_ <= x.ptr_; }
+ bool operator>=(ptr const& x) const { return ptr_ >= x.ptr_; }
+ };
+
+ template <class T>
+ class const_ptr
+ {
+ friend class allocator2<T>;
+ friend struct const_void_ptr;
+
+ T const* ptr_;
+
+ const_ptr(T const* ptr) : ptr_(ptr) {}
+ public:
+ const_ptr() : ptr_(0) {}
+ const_ptr(ptr<T> const& x) : ptr_(x.ptr_) {}
+ explicit const_ptr(void_const_ptr const& x) : ptr_((T const*) x.ptr_) {}
+
+ T const& operator*() const { return *ptr_; }
+ T const* operator->() const { return ptr_; }
+ const_ptr& operator++() { ++ptr_; return *this; }
+ const_ptr operator++(int) { const_ptr tmp(*this); ++ptr_; return tmp; }
+ const_ptr operator+(std::ptrdiff_t s) const
+ { return const_ptr(ptr_ + s); }
+ friend const_ptr operator+(std::ptrdiff_t s, const_ptr p)
+ { return ptr<T>(s + p.ptr_); }
+ T const& operator[](int s) const { return ptr_[s]; }
+ bool operator!() const { return !ptr_; }
+ operator bool() const { return !!ptr_; }
+
+ bool operator==(const_ptr const& x) const { return ptr_ == x.ptr_; }
+ bool operator!=(const_ptr const& x) const { return ptr_ != x.ptr_; }
+ bool operator<(const_ptr const& x) const { return ptr_ < x.ptr_; }
+ bool operator>(const_ptr const& x) const { return ptr_ > x.ptr_; }
+ bool operator<=(const_ptr const& x) const { return ptr_ <= x.ptr_; }
+ bool operator>=(const_ptr const& x) const { return ptr_ >= x.ptr_; }
+ };
+
template <class T>
class allocator2
{
@@ -285,8 +405,10 @@
public:
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
- typedef T* pointer;
- typedef T const* const_pointer;
+ typedef void_ptr void_pointer;
+ typedef void_const_ptr const_void_pointer;
+ typedef ptr<T> pointer;
+ typedef const_ptr<T> const_pointer;
typedef T& reference;
typedef T const& const_reference;
typedef T value_type;
@@ -326,9 +448,9 @@
}
pointer allocate(size_type n) {
- pointer ptr(static_cast<T*>(::operator new(n * sizeof(T))));
- detail::tracker.track_allocate((void*) ptr, n, sizeof(T), tag_);
- return ptr;
+ pointer p(static_cast<T*>(::operator new(n * sizeof(T))));
+ detail::tracker.track_allocate((void*) p.ptr_, n, sizeof(T), tag_);
+ return p;
}
pointer allocate(size_type n, void const* u)
@@ -340,8 +462,8 @@
void deallocate(pointer p, size_type n)
{
- detail::tracker.track_deallocate((void*) p, n, sizeof(T), tag_);
- ::operator delete((void*) p);
+ detail::tracker.track_deallocate((void*) p.ptr_, n, sizeof(T), tag_);
+ ::operator delete((void*) p.ptr_);
}
void construct(T* p, T const& t) {
Modified: branches/release/libs/unordered/test/unordered/insert_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/insert_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/insert_tests.cpp 2012-09-17 14:53:30 EDT (Mon, 17 Sep 2012)
@@ -229,6 +229,24 @@
test::check_equivalent_keys(x);
}
+ std::cerr<<"insert range with rehash tests.\n";
+
+ {
+ test::check_instances check_;
+
+ X x;
+
+ test::random_values<X> v(1000, generator);
+
+ x.insert(*v.begin());
+ x.clear();
+
+ x.insert(v.begin(), v.end());
+
+ test::check_container(x, v);
+ test::check_equivalent_keys(x);
+ }
+
std::cerr<<"insert input iterator range tests.\n";
{