Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r80382 - trunk/boost/unordered/detail
From: dnljms_at_[hidden]
Date: 2012-09-03 16:03:16


Author: danieljames
Date: 2012-09-03 16:03:15 EDT (Mon, 03 Sep 2012)
New Revision: 80382
URL: http://svn.boost.org/trac/boost/changeset/80382

Log:
Unordered: Move iterators to top of buckets.hpp
Text files modified:
   trunk/boost/unordered/detail/buckets.hpp | 763 ++++++++++++++++++++-------------------
   1 files changed, 382 insertions(+), 381 deletions(-)

Modified: trunk/boost/unordered/detail/buckets.hpp
==============================================================================
--- trunk/boost/unordered/detail/buckets.hpp (original)
+++ trunk/boost/unordered/detail/buckets.hpp 2012-09-03 16:03:15 EDT (Mon, 03 Sep 2012)
@@ -35,268 +35,6 @@
     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;
-
- 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)
- {
- }
-
- ~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;
- }
-
- 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;
- }
-
- 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 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()
- {
- 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;
- }
- }
- }
-
- ///////////////////////////////////////////////////////////////////
- //
- // Node Holder
- //
- // Temporary store for nodes. Deletes any that aren't used.
-
- template <typename NodeAlloc>
- struct node_holder : private node_constructor<NodeAlloc>
- {
- private:
- typedef node_constructor<NodeAlloc> base;
-
- 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;
- typedef typename node::link_pointer link_pointer;
-
- node_pointer nodes_;
-
- public:
-
- template <typename Buckets>
- explicit node_holder(Buckets& b) :
- base(b.node_alloc()),
- nodes_()
- {
- typename Buckets::previous_pointer prev = b.get_previous_start();
- nodes_ = static_cast<node_pointer>(prev->next_);
- prev->next_ = link_pointer();
- b.size_ = 0;
- }
-
- ~node_holder();
-
- template <typename T>
- inline void assign_impl(T const& v) {
- nodes_->value() = v;
- }
-
- 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;
- }
-
- template <typename T>
- inline void move_assign_impl(T& v) {
- nodes_->value() = boost::move(v);
- }
-
- 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);
- }
-
- node_pointer copy_of(value_type const& v)
- {
- if (nodes_) {
- assign_impl(v);
- node_pointer p = nodes_;
- nodes_ = static_cast<node_pointer>(p->next_);
- p->next_ = link_pointer();
- return p;
- }
- else {
- this->construct_with_value2(v);
- return base::release();
- }
- }
-
- node_pointer move_copy_of(value_type& v)
- {
- if (nodes_) {
- move_assign_impl(v);
- node_pointer p = nodes_;
- nodes_ = static_cast<node_pointer>(p->next_);
- p->next_ = link_pointer();
- return p;
- }
- else {
- this->construct_with_value2(boost::move(v));
- return base::release();
- }
- }
- };
-
- 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);
- }
- }
-
- ///////////////////////////////////////////////////////////////////
- //
- // 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 {
@@ -400,169 +138,432 @@
         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) :
- ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_)
- {}
+ cl_iterator(boost::unordered::iterator_detail::l_iterator<
+ NodePointer, Value, Policy> const& x) :
+ ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_)
+ {}
+
+ Value const&
+ operator*() const {
+ return ptr_->value();
+ }
+
+ Value const* operator->() const {
+ return ptr_->value_ptr();
+ }
+
+ cl_iterator& operator++() {
+ ptr_ = static_cast<node_pointer>(ptr_->next_);
+ if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_)
+ != bucket_)
+ ptr_ = node_pointer();
+ return *this;
+ }
+
+ cl_iterator operator++(int) {
+ cl_iterator tmp(*this);
+ ++(*this);
+ return tmp;
+ }
+
+ friend bool operator==(cl_iterator const& x, cl_iterator const& y) {
+ return x.ptr_ == y.ptr_;
+ }
+
+ friend bool operator!=(cl_iterator const& x, cl_iterator const& y) {
+ return x.ptr_ != y.ptr_;
+ }
+ };
+
+ template <typename NodePointer, typename Value>
+ struct iterator
+ : public boost::iterator<
+ std::forward_iterator_tag, Value, std::ptrdiff_t,
+ NodePointer, Value&>
+ {
+#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+ template <typename, typename, typename>
+ friend struct boost::unordered::iterator_detail::c_iterator;
+ template <typename, typename, typename>
+ friend struct boost::unordered::iterator_detail::l_iterator;
+ template <typename, typename, typename, typename>
+ 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>
+ friend struct boost::unordered::detail::grouped_table_impl;
+ private:
+#endif
+ typedef NodePointer node_pointer;
+ node_pointer node_;
+
+ public:
+
+ iterator() : node_() {}
+
+ explicit iterator(node_pointer const& x) : node_(x) {}
+
+ Value& operator*() const {
+ return node_->value();
+ }
+
+ Value* operator->() const {
+ return &node_->value();
+ }
+
+ iterator& operator++() {
+ node_ = static_cast<node_pointer>(node_->next_);
+ return *this;
+ }
+
+ iterator operator++(int) {
+ iterator tmp(node_);
+ node_ = static_cast<node_pointer>(node_->next_);
+ return tmp;
+ }
+
+ bool operator==(iterator const& x) const {
+ return node_ == x.node_;
+ }
+
+ bool operator!=(iterator const& x) const {
+ return node_ != x.node_;
+ }
+ };
+
+ template <typename ConstNodePointer, typename NodePointer, typename Value>
+ struct c_iterator
+ : public boost::iterator<
+ std::forward_iterator_tag, Value, std::ptrdiff_t,
+ ConstNodePointer, Value const&>
+ {
+ friend struct boost::unordered::iterator_detail::iterator<
+ NodePointer, Value>;
+
+#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>
+ friend struct boost::unordered::detail::grouped_table_impl;
+
+ private:
+#endif
+
+ typedef NodePointer node_pointer;
+ typedef boost::unordered::iterator_detail::iterator<NodePointer, Value>
+ iterator;
+ node_pointer node_;
+
+ public:
+
+ c_iterator() : node_() {}
+
+ explicit c_iterator(node_pointer const& x) : node_(x) {}
+
+ c_iterator(boost::unordered::iterator_detail::iterator<
+ NodePointer, Value> const& x) : node_(x.node_) {}
+
+ Value const& operator*() const {
+ return node_->value();
+ }
+
+ Value const* operator->() const {
+ return &node_->value();
+ }
+
+ c_iterator& operator++() {
+ node_ = static_cast<node_pointer>(node_->next_);
+ return *this;
+ }
+
+ c_iterator operator++(int) {
+ c_iterator tmp(node_);
+ node_ = static_cast<node_pointer>(node_->next_);
+ return tmp;
+ }
+
+ friend bool operator==(c_iterator const& x, c_iterator const& y) {
+ return x.node_ == y.node_;
+ }
+
+ friend bool operator!=(c_iterator const& x, c_iterator const& y) {
+ return x.node_ != y.node_;
+ }
+ };
+}}}
+
+namespace boost { namespace unordered { namespace detail {
+
+ ///////////////////////////////////////////////////////////////////
+ //
+ // 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;
+
+ 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)
+ {
+ }
+
+ ~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;
+ }
+
+ 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;
+ }
+
+ 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 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_));
+ }
 
- Value const&
- operator*() const {
- return ptr_->value();
+ node_allocator_traits::deallocate(alloc_, node_, 1);
         }
+ }
 
- Value const* operator->() const {
- return ptr_->value_ptr();
- }
+ template <typename Alloc>
+ void node_constructor<Alloc>::construct()
+ {
+ if(!node_) {
+ node_constructed_ = false;
+ value_constructed_ = false;
 
- cl_iterator& operator++() {
- ptr_ = static_cast<node_pointer>(ptr_->next_);
- if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_)
- != bucket_)
- ptr_ = node_pointer();
- return *this;
- }
+ node_ = node_allocator_traits::allocate(alloc_, 1);
 
- cl_iterator operator++(int) {
- cl_iterator tmp(*this);
- ++(*this);
- return tmp;
+ 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_);
 
- friend bool operator==(cl_iterator const& x, cl_iterator const& y) {
- return x.ptr_ == y.ptr_;
+ if (value_constructed_)
+ {
+ boost::unordered::detail::destroy_value_impl(alloc_,
+ node_->value_ptr());
+ value_constructed_ = false;
+ }
         }
+ }
 
- friend bool operator!=(cl_iterator const& x, cl_iterator const& y) {
- return x.ptr_ != y.ptr_;
- }
- };
+ ///////////////////////////////////////////////////////////////////
+ //
+ // Node Holder
+ //
+ // Temporary store for nodes. Deletes any that aren't used.
 
- template <typename NodePointer, typename Value>
- struct iterator
- : public boost::iterator<
- std::forward_iterator_tag, Value, std::ptrdiff_t,
- NodePointer, Value&>
+ template <typename NodeAlloc>
+ struct node_holder : private node_constructor<NodeAlloc>
     {
-#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
- template <typename, typename, typename>
- friend struct boost::unordered::iterator_detail::c_iterator;
- template <typename, typename, typename>
- friend struct boost::unordered::iterator_detail::l_iterator;
- template <typename, typename, typename, typename>
- 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>
- friend struct boost::unordered::detail::grouped_table_impl;
     private:
-#endif
- typedef NodePointer node_pointer;
- node_pointer node_;
+ typedef node_constructor<NodeAlloc> base;
+
+ 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;
+ typedef typename node::link_pointer link_pointer;
+
+ node_pointer nodes_;
 
     public:
 
- iterator() : node_() {}
+ template <typename Buckets>
+ explicit node_holder(Buckets& b) :
+ base(b.node_alloc()),
+ nodes_()
+ {
+ typename Buckets::previous_pointer prev = b.get_previous_start();
+ nodes_ = static_cast<node_pointer>(prev->next_);
+ prev->next_ = link_pointer();
+ b.size_ = 0;
+ }
 
- explicit iterator(node_pointer const& x) : node_(x) {}
+ ~node_holder();
 
- Value& operator*() const {
- return node_->value();
+ template <typename T>
+ inline void assign_impl(T const& v) {
+ nodes_->value() = v;
         }
 
- Value* operator->() const {
- return &node_->value();
+ 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;
         }
 
- iterator& operator++() {
- node_ = static_cast<node_pointer>(node_->next_);
- return *this;
+ template <typename T>
+ inline void move_assign_impl(T& v) {
+ nodes_->value() = boost::move(v);
         }
 
- iterator operator++(int) {
- iterator tmp(node_);
- node_ = static_cast<node_pointer>(node_->next_);
- return tmp;
+ 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);
         }
 
- bool operator==(iterator const& x) const {
- return node_ == x.node_;
+ node_pointer copy_of(value_type const& v)
+ {
+ if (nodes_) {
+ assign_impl(v);
+ node_pointer p = nodes_;
+ nodes_ = static_cast<node_pointer>(p->next_);
+ p->next_ = link_pointer();
+ return p;
+ }
+ else {
+ this->construct_with_value2(v);
+ return base::release();
+ }
         }
 
- bool operator!=(iterator const& x) const {
- return node_ != x.node_;
+ node_pointer move_copy_of(value_type& v)
+ {
+ if (nodes_) {
+ move_assign_impl(v);
+ node_pointer p = nodes_;
+ nodes_ = static_cast<node_pointer>(p->next_);
+ p->next_ = link_pointer();
+ return p;
+ }
+ else {
+ this->construct_with_value2(boost::move(v));
+ return base::release();
+ }
         }
     };
 
- template <typename ConstNodePointer, typename NodePointer, typename Value>
- struct c_iterator
- : public boost::iterator<
- std::forward_iterator_tag, Value, std::ptrdiff_t,
- ConstNodePointer, Value const&>
+ template <typename Alloc>
+ node_holder<Alloc>::~node_holder()
     {
- friend struct boost::unordered::iterator_detail::iterator<
- NodePointer, Value>;
-
-#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>
- friend struct boost::unordered::detail::grouped_table_impl;
-
- private:
-#endif
-
- typedef NodePointer node_pointer;
- typedef boost::unordered::iterator_detail::iterator<NodePointer, Value>
- iterator;
- node_pointer node_;
+ while (nodes_) {
+ node_pointer p = nodes_;
+ nodes_ = static_cast<node_pointer>(p->next_);
 
- public:
+ 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);
+ }
+ }
 
- c_iterator() : node_() {}
+ ///////////////////////////////////////////////////////////////////
+ //
+ // Bucket
 
- explicit c_iterator(node_pointer const& x) : node_(x) {}
+ template <typename NodePointer>
+ struct bucket
+ {
+ typedef NodePointer previous_pointer;
+ previous_pointer next_;
 
- c_iterator(boost::unordered::iterator_detail::iterator<
- NodePointer, Value> const& x) : node_(x.node_) {}
+ bucket() : next_() {}
 
- Value const& operator*() const {
- return node_->value();
+ previous_pointer first_from_start()
+ {
+ return next_;
         }
 
- Value const* operator->() const {
- return &node_->value();
- }
+ enum { extra_node = true };
+ };
 
- c_iterator& operator++() {
- node_ = static_cast<node_pointer>(node_->next_);
- return *this;
- }
+ struct ptr_bucket
+ {
+ typedef ptr_bucket* previous_pointer;
+ previous_pointer next_;
 
- c_iterator operator++(int) {
- c_iterator tmp(node_);
- node_ = static_cast<node_pointer>(node_->next_);
- return tmp;
- }
+ ptr_bucket() : next_(0) {}
 
- friend bool operator==(c_iterator const& x, c_iterator const& y) {
- return x.node_ == y.node_;
+ previous_pointer first_from_start()
+ {
+ return this;
         }
 
- friend bool operator!=(c_iterator const& x, c_iterator const& y) {
- return x.node_ != y.node_;
- }
+ enum { extra_node = false };
     };
-}}}
-
-namespace boost { namespace unordered { namespace detail {
 
     ///////////////////////////////////////////////////////////////////
     //


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