diff options
Diffstat (limited to 'boost/intrusive/list.hpp')
| -rw-r--r-- | boost/intrusive/list.hpp | 391 |
1 files changed, 211 insertions, 180 deletions
diff --git a/boost/intrusive/list.hpp b/boost/intrusive/list.hpp index 5450bc5d81..297267d34b 100644 --- a/boost/intrusive/list.hpp +++ b/boost/intrusive/list.hpp @@ -1,7 +1,7 @@ ///////////////////////////////////////////////////////////////////////////// // // (C) Copyright Olaf Krzikalla 2004-2006. -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2014 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -14,48 +14,57 @@ #ifndef BOOST_INTRUSIVE_LIST_HPP #define BOOST_INTRUSIVE_LIST_HPP +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/detail/config_begin.hpp> -#include <boost/intrusive/detail/assert.hpp> #include <boost/intrusive/intrusive_fwd.hpp> +#include <boost/intrusive/detail/assert.hpp> #include <boost/intrusive/list_hook.hpp> #include <boost/intrusive/circular_list_algorithms.hpp> #include <boost/intrusive/pointer_traits.hpp> -#include <boost/intrusive/detail/clear_on_destructor_base.hpp> #include <boost/intrusive/detail/mpl.hpp> #include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/detail/get_value_traits.hpp> +#include <boost/intrusive/detail/is_stateful_value_traits.hpp> +#include <boost/intrusive/detail/default_header_holder.hpp> +#include <boost/intrusive/detail/reverse_iterator.hpp> +#include <boost/intrusive/detail/uncast.hpp> +#include <boost/intrusive/detail/list_iterator.hpp> +#include <boost/intrusive/detail/array_initializer.hpp> +#include <boost/intrusive/detail/exception_disposer.hpp> +#include <boost/intrusive/detail/equal_to_value.hpp> +#include <boost/intrusive/detail/key_nodeptr_comp.hpp> +#include <boost/intrusive/detail/simple_disposers.hpp> +#include <boost/intrusive/detail/size_holder.hpp> + +#include <boost/move/utility_core.hpp> #include <boost/static_assert.hpp> -#include <boost/intrusive/options.hpp> -#include <boost/intrusive/pointer_traits.hpp> -#include <boost/intrusive/detail/utilities.hpp> -#include <iterator> + #include <algorithm> #include <functional> #include <cstddef> -#include <boost/move/move.hpp> namespace boost { namespace intrusive { /// @cond -template <class ValueTraits, class SizeType, bool ConstantTimeSize> -struct listopt -{ - typedef ValueTraits value_traits; - typedef SizeType size_type; - static const bool constant_time_size = ConstantTimeSize; -}; +struct default_list_hook_applier +{ template <class T> struct apply{ typedef typename T::default_list_hook type; }; }; +template<> +struct is_default_hook_tag<default_list_hook_applier> +{ static const bool value = true; }; -template <class T> struct list_defaults - : pack_options - < none - , base_hook<detail::default_list_hook> - , constant_time_size<true> - , size_type<std::size_t> - >::type -{}; +{ + typedef default_list_hook_applier proto_value_traits; + static const bool constant_time_size = true; + typedef std::size_t size_type; + typedef void header_holder_type; +}; /// @endcond @@ -72,43 +81,35 @@ struct list_defaults #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class Config> +template <class ValueTraits, class SizeType, bool ConstantTimeSize, typename HeaderHolder> #endif class list_impl - : private detail::clear_on_destructor_base< list_impl<Config> > { - template<class C> friend class detail::clear_on_destructor_base; //Public typedefs public: - typedef typename Config::value_traits value_traits; - /// @cond - static const bool external_value_traits = - detail::external_value_traits_is_true<value_traits>::value; - typedef typename detail::eval_if_c - < external_value_traits - , detail::eval_value_traits<value_traits> - , detail::identity<value_traits> - >::type real_value_traits; - /// @endcond - typedef typename real_value_traits::pointer pointer; - typedef typename real_value_traits::const_pointer const_pointer; + typedef ValueTraits value_traits; + typedef typename value_traits::pointer pointer; + typedef typename value_traits::const_pointer const_pointer; typedef typename pointer_traits<pointer>::element_type value_type; typedef typename pointer_traits<pointer>::reference reference; typedef typename pointer_traits<const_pointer>::reference const_reference; typedef typename pointer_traits<pointer>::difference_type difference_type; - typedef typename Config::size_type size_type; - typedef list_iterator<list_impl, false> iterator; - typedef list_iterator<list_impl, true> const_iterator; + typedef SizeType size_type; + typedef list_iterator<value_traits, false> iterator; + typedef list_iterator<value_traits, true> const_iterator; typedef boost::intrusive::detail::reverse_iterator<iterator> reverse_iterator; typedef boost::intrusive::detail::reverse_iterator<const_iterator>const_reverse_iterator; - typedef typename real_value_traits::node_traits node_traits; + typedef typename value_traits::node_traits node_traits; typedef typename node_traits::node node; typedef typename node_traits::node_ptr node_ptr; typedef typename node_traits::const_node_ptr const_node_ptr; typedef circular_list_algorithms<node_traits> node_algorithms; + typedef HeaderHolder header_holder_type; - static const bool constant_time_size = Config::constant_time_size; - static const bool stateful_value_traits = detail::is_stateful_value_traits<real_value_traits>::value; + static const bool constant_time_size = ConstantTimeSize; + static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; + static const bool has_container_from_iterator = + detail::is_same< header_holder_type, detail::default_header_holder< node_traits > >::value; /// @cond @@ -118,34 +119,28 @@ class list_impl //noncopyable BOOST_MOVABLE_BUT_NOT_COPYABLE(list_impl) - enum { safemode_or_autounlink = - (int)real_value_traits::link_mode == (int)auto_unlink || - (int)real_value_traits::link_mode == (int)safe_link }; + static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; //Constant-time size is incompatible with auto-unlink hooks! BOOST_STATIC_ASSERT(!(constant_time_size && - ((int)real_value_traits::link_mode == (int)auto_unlink) + ((int)value_traits::link_mode == (int)auto_unlink) )); - //Const cast emulation for smart pointers - static node_ptr uncast(const const_node_ptr & ptr) - { return pointer_traits<node_ptr>::const_cast_from(ptr); } - node_ptr get_root_node() - { return pointer_traits<node_ptr>::pointer_to(data_.root_plus_size_.root_); } + { return data_.root_plus_size_.m_header.get_node(); } const_node_ptr get_root_node() const - { return pointer_traits<const_node_ptr>::pointer_to(data_.root_plus_size_.root_); } + { return data_.root_plus_size_.m_header.get_node(); } struct root_plus_size : public size_traits { - node root_; + header_holder_type m_header; }; struct data_t : public value_traits { typedef typename list_impl::value_traits value_traits; - data_t(const value_traits &val_traits) + explicit data_t(const value_traits &val_traits) : value_traits(val_traits) {} @@ -158,51 +153,29 @@ class list_impl const size_traits &priv_size_traits() const { return data_.root_plus_size_; } - const real_value_traits &get_real_value_traits(detail::bool_<false>) const - { return data_; } - - const real_value_traits &get_real_value_traits(detail::bool_<true>) const - { return data_.get_value_traits(*this); } - - real_value_traits &get_real_value_traits(detail::bool_<false>) - { return data_; } - - real_value_traits &get_real_value_traits(detail::bool_<true>) - { return data_.get_value_traits(*this); } - const value_traits &priv_value_traits() const { return data_; } value_traits &priv_value_traits() { return data_; } - protected: - node &prot_root_node() - { return data_.root_plus_size_.root_; } + typedef typename boost::intrusive::value_traits_pointers + <ValueTraits>::const_value_traits_ptr const_value_traits_ptr; - node const &prot_root_node() const - { return data_.root_plus_size_.root_; } - - void prot_set_size(size_type s) - { data_.root_plus_size_.set_size(s); } + const_value_traits_ptr priv_value_traits_ptr() const + { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); } /// @endcond public: - const real_value_traits &get_real_value_traits() const - { return this->get_real_value_traits(detail::bool_<external_value_traits>()); } - - real_value_traits &get_real_value_traits() - { return this->get_real_value_traits(detail::bool_<external_value_traits>()); } - //! <b>Effects</b>: constructs an empty list. //! //! <b>Complexity</b>: Constant //! - //! <b>Throws</b>: If real_value_traits::node_traits::node + //! <b>Throws</b>: If value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). - list_impl(const value_traits &v_traits = value_traits()) + explicit list_impl(const value_traits &v_traits = value_traits()) : data_(v_traits) { this->priv_size_traits().set_size(size_type(0)); @@ -215,14 +188,16 @@ class list_impl //! //! <b>Complexity</b>: Linear in std::distance(b, e). No copy constructors are called. //! - //! <b>Throws</b>: If real_value_traits::node_traits::node + //! <b>Throws</b>: If value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). template<class Iterator> list_impl(Iterator b, Iterator e, const value_traits &v_traits = value_traits()) : data_(v_traits) { + //nothrow, no need to rollback to release elements on exception this->priv_size_traits().set_size(size_type(0)); node_algorithms::init_header(this->get_root_node()); + //nothrow, no need to rollback to release elements on exception this->insert(this->cend(), b, e); } @@ -233,6 +208,7 @@ class list_impl { this->priv_size_traits().set_size(size_type(0)); node_algorithms::init_header(this->get_root_node()); + //nothrow, no need to rollback to release elements on exception this->swap(x); } @@ -251,7 +227,12 @@ class list_impl //! <b>Complexity</b>: Linear to the number of elements in the list, if //! it's a safe-mode or auto-unlink value . Otherwise constant. ~list_impl() - {} + { + if(is_safe_autounlink<ValueTraits::link_mode>::value){ + this->clear(); + node_algorithms::init(this->get_root_node()); + } + } //! <b>Requires</b>: value must be an lvalue. //! @@ -265,7 +246,7 @@ class list_impl //! <b>Note</b>: Does not affect the validity of iterators and references. void push_back(reference value) { - node_ptr to_insert = get_real_value_traits().to_node_ptr(value); + node_ptr to_insert = priv_value_traits().to_node_ptr(value); if(safemode_or_autounlink) BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(to_insert)); node_algorithms::link_before(this->get_root_node(), to_insert); @@ -284,7 +265,7 @@ class list_impl //! <b>Note</b>: Does not affect the validity of iterators and references. void push_front(reference value) { - node_ptr to_insert = get_real_value_traits().to_node_ptr(value); + node_ptr to_insert = priv_value_traits().to_node_ptr(value); if(safemode_or_autounlink) BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(to_insert)); node_algorithms::link_before(node_traits::get_next(this->get_root_node()), to_insert); @@ -321,7 +302,7 @@ class list_impl this->priv_size_traits().decrement(); if(safemode_or_autounlink) node_algorithms::init(to_erase); - disposer(get_real_value_traits().to_value_ptr(to_erase)); + disposer(priv_value_traits().to_value_ptr(to_erase)); } //! <b>Effects</b>: Erases the first element of the list. @@ -354,7 +335,7 @@ class list_impl this->priv_size_traits().decrement(); if(safemode_or_autounlink) node_algorithms::init(to_erase); - disposer(get_real_value_traits().to_value_ptr(to_erase)); + disposer(priv_value_traits().to_value_ptr(to_erase)); } //! <b>Effects</b>: Returns a reference to the first element of the list. @@ -363,7 +344,7 @@ class list_impl //! //! <b>Complexity</b>: Constant. reference front() - { return *get_real_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); } + { return *priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); } //! <b>Effects</b>: Returns a const_reference to the first element of the list. //! @@ -371,7 +352,7 @@ class list_impl //! //! <b>Complexity</b>: Constant. const_reference front() const - { return *get_real_value_traits().to_value_ptr(uncast(node_traits::get_next(this->get_root_node()))); } + { return *priv_value_traits().to_value_ptr(detail::uncast(node_traits::get_next(this->get_root_node()))); } //! <b>Effects</b>: Returns a reference to the last element of the list. //! @@ -379,7 +360,7 @@ class list_impl //! //! <b>Complexity</b>: Constant. reference back() - { return *get_real_value_traits().to_value_ptr(node_traits::get_previous(this->get_root_node())); } + { return *priv_value_traits().to_value_ptr(node_traits::get_previous(this->get_root_node())); } //! <b>Effects</b>: Returns a const_reference to the last element of the list. //! @@ -387,7 +368,7 @@ class list_impl //! //! <b>Complexity</b>: Constant. const_reference back() const - { return *get_real_value_traits().to_value_ptr(uncast(node_traits::get_previous(this->get_root_node()))); } + { return *priv_value_traits().to_value_ptr(detail::uncast(node_traits::get_previous(this->get_root_node()))); } //! <b>Effects</b>: Returns an iterator to the first element contained in the list. //! @@ -395,7 +376,7 @@ class list_impl //! //! <b>Complexity</b>: Constant. iterator begin() - { return iterator(node_traits::get_next(this->get_root_node()), this); } + { return iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. //! @@ -411,7 +392,7 @@ class list_impl //! //! <b>Complexity</b>: Constant. const_iterator cbegin() const - { return const_iterator(node_traits::get_next(this->get_root_node()), this); } + { return const_iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } //! <b>Effects</b>: Returns an iterator to the end of the list. //! @@ -419,7 +400,7 @@ class list_impl //! //! <b>Complexity</b>: Constant. iterator end() - { return iterator(this->get_root_node(), this); } + { return iterator(this->get_root_node(), this->priv_value_traits_ptr()); } //! <b>Effects</b>: Returns a const_iterator to the end of the list. //! @@ -435,7 +416,7 @@ class list_impl //! //! <b>Complexity</b>: Constant. const_iterator cend() const - { return const_iterator(uncast(this->get_root_node()), this); } + { return const_iterator(detail::uncast(this->get_root_node()), this->priv_value_traits_ptr()); } //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning //! of the reversed list. @@ -637,15 +618,15 @@ class list_impl //! //! <b>Note</b>: Invalidates the iterators (but not the references) to the //! erased elements. - iterator erase(const_iterator b, const_iterator e, difference_type n) + iterator erase(const_iterator b, const_iterator e, size_type n) { - BOOST_INTRUSIVE_INVARIANT_ASSERT(std::distance(b, e) == difference_type(n)); + BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance(b.pointed_node(), e.pointed_node()) == n); if(safemode_or_autounlink || constant_time_size){ return this->erase_and_dispose(b, e, detail::null_disposer()); } else{ if(constant_time_size){ - this->priv_size_traits().set_size(this->priv_size_traits().get_size() - n); + this->priv_size_traits().decrease(n); } node_algorithms::unlink(b.pointed_node(), e.pointed_node()); return e.unconst(); @@ -675,7 +656,7 @@ class list_impl this->priv_size_traits().decrement(); if(safemode_or_autounlink) node_algorithms::init(to_erase); - disposer(this->get_real_value_traits().to_value_ptr(to_erase)); + disposer(this->priv_value_traits().to_value_ptr(to_erase)); return i.unconst(); } @@ -709,7 +690,7 @@ class list_impl bp = node_traits::get_next(bp); if(safemode_or_autounlink) node_algorithms::init(to_erase); - disposer(get_real_value_traits().to_value_ptr(to_erase)); + disposer(priv_value_traits().to_value_ptr(to_erase)); this->priv_size_traits().decrement(); } return e.unconst(); @@ -755,7 +736,7 @@ class list_impl ++it; if(safemode_or_autounlink) node_algorithms::init(to_erase); - disposer(get_real_value_traits().to_value_ptr(to_erase)); + disposer(priv_value_traits().to_value_ptr(to_erase)); } node_algorithms::init_header(this->get_root_node()); this->priv_size_traits().set_size(0); @@ -801,12 +782,12 @@ class list_impl //! <b>Note</b>: Does not affect the validity of iterators and references. iterator insert(const_iterator p, reference value) { - node_ptr to_insert = this->get_real_value_traits().to_node_ptr(value); + node_ptr to_insert = this->priv_value_traits().to_node_ptr(value); if(safemode_or_autounlink) BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(to_insert)); node_algorithms::link_before(p.pointed_node(), to_insert); this->priv_size_traits().increment(); - return iterator(to_insert, this); + return iterator(to_insert, this->priv_value_traits_ptr()); } //! <b>Requires</b>: Dereferencing iterator must yield @@ -886,11 +867,11 @@ class list_impl void splice(const_iterator p, list_impl& x) { if(!x.empty()){ - size_traits &thist = this->priv_size_traits(); - size_traits &xt = x.priv_size_traits(); node_algorithms::transfer (p.pointed_node(), x.begin().pointed_node(), x.end().pointed_node()); - thist.set_size(thist.get_size() + xt.get_size()); + size_traits &thist = this->priv_size_traits(); + size_traits &xt = x.priv_size_traits(); + thist.increase(xt.get_size()); xt.set_size(size_type(0)); } } @@ -899,7 +880,7 @@ class list_impl //! new_ele must point to an element contained in list x. //! //! <b>Effects</b>: Transfers the value pointed by new_ele, from list x to this list, - //! before the the element pointed by p. No destructors or copy constructors are called. + //! before the element pointed by p. No destructors or copy constructors are called. //! If p == new_ele or p == ++new_ele, this function is a null operation. //! //! <b>Throws</b>: Nothing. @@ -916,10 +897,10 @@ class list_impl } //! <b>Requires</b>: p must be a valid iterator of *this. - //! start and end must point to elements contained in list x. + //! f and e must point to elements contained in list x. //! - //! <b>Effects</b>: Transfers the range pointed by start and end from list x to this list, - //! before the the element pointed by p. No destructors or copy constructors are called. + //! <b>Effects</b>: Transfers the range pointed by f and e from list x to this list, + //! before the element pointed by p. No destructors or copy constructors are called. //! //! <b>Throws</b>: Nothing. //! @@ -928,20 +909,20 @@ class list_impl //! //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this //! list. Iterators of this list and all the references are not invalidated. - void splice(const_iterator p, list_impl&x, const_iterator start, const_iterator end) + void splice(const_iterator p, list_impl&x, const_iterator f, const_iterator e) { if(constant_time_size) - this->splice(p, x, start, end, std::distance(start, end)); + this->splice(p, x, f, e, node_algorithms::distance(f.pointed_node(), e.pointed_node())); else - this->splice(p, x, start, end, 1);//distance is a dummy value + this->splice(p, x, f, e, 1);//distance is a dummy value } //! <b>Requires</b>: p must be a valid iterator of *this. - //! start and end must point to elements contained in list x. - //! n == std::distance(start, end) + //! f and e must point to elements contained in list x. + //! n == std::distance(f, e) //! - //! <b>Effects</b>: Transfers the range pointed by start and end from list x to this list, - //! before the the element pointed by p. No destructors or copy constructors are called. + //! <b>Effects</b>: Transfers the range pointed by f and e from list x to this list, + //! before the element pointed by p. No destructors or copy constructors are called. //! //! <b>Throws</b>: Nothing. //! @@ -949,19 +930,19 @@ class list_impl //! //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this //! list. Iterators of this list and all the references are not invalidated. - void splice(const_iterator p, list_impl&x, const_iterator start, const_iterator end, difference_type n) + void splice(const_iterator p, list_impl&x, const_iterator f, const_iterator e, size_type n) { if(n){ if(constant_time_size){ + BOOST_INTRUSIVE_INVARIANT_ASSERT(n == node_algorithms::distance(f.pointed_node(), e.pointed_node())); + node_algorithms::transfer(p.pointed_node(), f.pointed_node(), e.pointed_node()); size_traits &thist = this->priv_size_traits(); size_traits &xt = x.priv_size_traits(); - BOOST_INTRUSIVE_INVARIANT_ASSERT(n == std::distance(start, end)); - node_algorithms::transfer(p.pointed_node(), start.pointed_node(), end.pointed_node()); - thist.set_size(thist.get_size() + n); - xt.set_size(xt.get_size() - n); + thist.increase(n); + xt.decrease(n); } else{ - node_algorithms::transfer(p.pointed_node(), start.pointed_node(), end.pointed_node()); + node_algorithms::transfer(p.pointed_node(), f.pointed_node(), e.pointed_node()); } } } @@ -969,7 +950,7 @@ class list_impl //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. //! The sort is stable, that is, the relative order of equivalent elements is preserved. //! - //! <b>Throws</b>: If real_value_traits::node_traits::node + //! <b>Throws</b>: If value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) //! or std::less<value_type> throws. Basic guarantee. //! @@ -985,7 +966,7 @@ class list_impl //! <b>Effects</b>: This function sorts the list *this according to p. The sort is //! stable, that is, the relative order of equivalent elements is preserved. //! - //! <b>Throws</b>: If real_value_traits::node_traits::node + //! <b>Throws</b>: If value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) //! or the predicate throws. Basic guarantee. //! @@ -1121,7 +1102,17 @@ class list_impl //! and iterators to elements that are not removed remain valid. template<class Pred> void remove_if(Pred pred) - { this->remove_and_dispose_if(pred, detail::null_disposer()); } + { + const node_ptr root_node = this->get_root_node(); + typename node_algorithms::stable_partition_info info; + node_algorithms::stable_partition + (node_traits::get_next(root_node), root_node, detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info); + //Invariants preserved by stable_partition so erase can be safely called + //The first element might have changed so calculate it again + this->erase( const_iterator(node_traits::get_next(root_node), this->priv_value_traits_ptr()) + , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr()) + , info.num_1st_partition); + } //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. //! @@ -1138,16 +1129,15 @@ class list_impl template<class Pred, class Disposer> void remove_and_dispose_if(Pred pred, Disposer disposer) { - const_iterator cur(this->cbegin()); - const_iterator last(this->cend()); - while(cur != last) { - if(pred(*cur)){ - cur = this->erase_and_dispose(cur, disposer); - } - else{ - ++cur; - } - } + const node_ptr root_node = this->get_root_node(); + typename node_algorithms::stable_partition_info info; + node_algorithms::stable_partition + (node_traits::get_next(root_node), root_node, detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info); + //Invariants preserved by stable_partition so erase can be safely called + //The first element might have changed so calculate it again + this->erase_and_dispose( const_iterator(node_traits::get_next(root_node), this->priv_value_traits_ptr()) + , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr()) + , disposer); } //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent @@ -1239,8 +1229,8 @@ class list_impl static iterator s_iterator_to(reference value) { BOOST_STATIC_ASSERT((!stateful_value_traits)); - BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(real_value_traits::to_node_ptr(value))); - return iterator(real_value_traits::to_node_ptr(value), 0); + BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(value_traits::to_node_ptr(value))); + return iterator(value_traits::to_node_ptr(value), const_value_traits_ptr()); } //! <b>Requires</b>: value must be a const reference to a value inserted in a list. @@ -1257,8 +1247,9 @@ class list_impl static const_iterator s_iterator_to(const_reference value) { BOOST_STATIC_ASSERT((!stateful_value_traits)); - BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(real_value_traits::to_node_ptr(const_cast<reference> (value)))); - return const_iterator(real_value_traits::to_node_ptr(const_cast<reference> (value)), 0); + reference r =*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value)); + BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(value_traits::to_node_ptr(r))); + return const_iterator(value_traits::to_node_ptr(r), const_value_traits_ptr()); } //! <b>Requires</b>: value must be a reference to a value inserted in a list. @@ -1272,8 +1263,8 @@ class list_impl //! <b>Note</b>: Iterators and references are not invalidated. iterator iterator_to(reference value) { - BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(real_value_traits::to_node_ptr(value))); - return iterator(real_value_traits::to_node_ptr(value), this); + BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(this->priv_value_traits().to_node_ptr(value))); + return iterator(this->priv_value_traits().to_node_ptr(value), this->priv_value_traits_ptr()); } //! <b>Requires</b>: value must be a const reference to a value inserted in a list. @@ -1287,8 +1278,45 @@ class list_impl //! <b>Note</b>: Iterators and references are not invalidated. const_iterator iterator_to(const_reference value) const { - BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(real_value_traits::to_node_ptr(const_cast<reference> (value)))); - return const_iterator(real_value_traits::to_node_ptr(const_cast<reference> (value)), this); + reference r = *pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value)); + BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(this->priv_value_traits().to_node_ptr(r))); + return const_iterator(this->priv_value_traits().to_node_ptr(r), this->priv_value_traits_ptr()); + } + + //! <b>Effects</b>: Asserts the integrity of the container. + //! + //! <b>Complexity</b>: Linear time. + //! + //! <b>Note</b>: The method has no effect when asserts are turned off (e.g., with NDEBUG). + //! Experimental function, interface might change in future versions. + void check() const + { + const_node_ptr header_ptr = get_root_node(); + // header's next and prev are never null + BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_next(header_ptr)); + BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_previous(header_ptr)); + // header's next and prev either both point to header (empty list) or neither does + BOOST_INTRUSIVE_INVARIANT_ASSERT((node_traits::get_next(header_ptr) == header_ptr) + == (node_traits::get_previous(header_ptr) == header_ptr)); + if (node_traits::get_next(header_ptr) == header_ptr) + { + if (constant_time_size) + BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == 0); + return; + } + size_t node_count = 0; + const_node_ptr p = header_ptr; + while (true) + { + const_node_ptr next_p = node_traits::get_next(p); + BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p); + BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_previous(next_p) == p); + p = next_p; + if (p == header_ptr) break; + ++node_count; + } + if (constant_time_size) + BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == node_count); } /// @cond @@ -1296,8 +1324,11 @@ class list_impl private: static list_impl &priv_container_from_end_iterator(const const_iterator &end_iterator) { - root_plus_size *r = detail::parent_from_member<root_plus_size, node> - ( boost::intrusive::detail::to_raw_pointer(end_iterator.pointed_node()), &root_plus_size::root_); + BOOST_STATIC_ASSERT((has_container_from_iterator)); + node_ptr p = end_iterator.pointed_node(); + header_holder_type* h = header_holder_type::get_holder(p); + root_plus_size* r = detail::parent_from_member + < root_plus_size, header_holder_type>(h, &root_plus_size::m_header); data_t *d = detail::parent_from_member<data_t, root_plus_size> ( r, &data_t::root_plus_size_); list_impl *s = detail::parent_from_member<list_impl, data_t>(d, &list_impl::data_); @@ -1309,29 +1340,29 @@ class list_impl #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class Config> +template <class ValueTraits, class SizeType, bool ConstantTimeSize, typename HeaderHolder> #endif inline bool operator< #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const list_impl<T, Options...> &x, const list_impl<T, Options...> &y) #else -(const list_impl<Config> &x, const list_impl<Config> &y) +(const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &x, const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &y) #endif { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class Config> +template <class ValueTraits, class SizeType, bool ConstantTimeSize, typename HeaderHolder> #endif bool operator== #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const list_impl<T, Options...> &x, const list_impl<T, Options...> &y) #else -(const list_impl<Config> &x, const list_impl<Config> &y) +(const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &x, const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &y) #endif { - typedef list_impl<Config> list_type; + typedef list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> list_type; typedef typename list_type::const_iterator const_iterator; const bool C = list_type::constant_time_size; if(C && x.size() != y.size()){ @@ -1361,65 +1392,65 @@ bool operator== #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class Config> +template <class ValueTraits, class SizeType, bool ConstantTimeSize, typename HeaderHolder> #endif inline bool operator!= #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const list_impl<T, Options...> &x, const list_impl<T, Options...> &y) #else -(const list_impl<Config> &x, const list_impl<Config> &y) +(const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &x, const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &y) #endif { return !(x == y); } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class Config> +template <class ValueTraits, class SizeType, bool ConstantTimeSize, typename HeaderHolder> #endif inline bool operator> #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const list_impl<T, Options...> &x, const list_impl<T, Options...> &y) #else -(const list_impl<Config> &x, const list_impl<Config> &y) +(const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &x, const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &y) #endif { return y < x; } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class Config> +template <class ValueTraits, class SizeType, bool ConstantTimeSize, typename HeaderHolder> #endif inline bool operator<= #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const list_impl<T, Options...> &x, const list_impl<T, Options...> &y) #else -(const list_impl<Config> &x, const list_impl<Config> &y) +(const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &x, const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &y) #endif { return !(y < x); } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class Config> +template <class ValueTraits, class SizeType, bool ConstantTimeSize, typename HeaderHolder> #endif inline bool operator>= #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const list_impl<T, Options...> &x, const list_impl<T, Options...> &y) #else -(const list_impl<Config> &x, const list_impl<Config> &y) +(const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &x, const list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &y) #endif { return !(x < y); } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class Config> +template <class ValueTraits, class SizeType, bool ConstantTimeSize, typename HeaderHolder> #endif inline void swap #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (list_impl<T, Options...> &x, list_impl<T, Options...> &y) #else -(list_impl<Config> &x, list_impl<Config> &y) +(list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &x, list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder> &y) #endif { x.swap(y); } @@ -1428,30 +1459,31 @@ inline void swap #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) template<class T, class ...Options> #else -template<class T, class O1 = none, class O2 = none, class O3 = none> +template<class T, class O1 = void, class O2 = void, class O3 = void, class O4 = void> #endif struct make_list { /// @cond typedef typename pack_options - < list_defaults<T>, + < list_defaults, #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) - O1, O2, O3 + O1, O2, O3, O4 #else Options... #endif >::type packed_options; typedef typename detail::get_value_traits - <T, typename packed_options::value_traits>::type value_traits; + <T, typename packed_options::proto_value_traits>::type value_traits; + typedef typename detail::get_header_holder_type + < value_traits, typename packed_options::header_holder_type >::type header_holder_type; typedef list_impl < - listopt - < value_traits - , typename packed_options::size_type - , packed_options::constant_time_size - > + value_traits, + typename packed_options::size_type, + packed_options::constant_time_size, + header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -1461,14 +1493,14 @@ struct make_list #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) -template<class T, class O1, class O2, class O3> +template<class T, class O1, class O2, class O3, class O4> #else template<class T, class ...Options> #endif class list : public make_list<T, #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) - O1, O2, O3 + O1, O2, O3, O4 #else Options... #endif @@ -1477,14 +1509,13 @@ class list typedef typename make_list <T, #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) - O1, O2, O3 + O1, O2, O3, O4 #else Options... #endif >::type Base; - typedef typename Base::real_value_traits real_value_traits; //Assert if passed value traits are compatible with the type - BOOST_STATIC_ASSERT((detail::is_same<typename real_value_traits::value_type, T>::value)); + BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value)); BOOST_MOVABLE_BUT_NOT_COPYABLE(list) public: @@ -1492,7 +1523,7 @@ class list typedef typename Base::iterator iterator; typedef typename Base::const_iterator const_iterator; - list(const value_traits &v_traits = value_traits()) + explicit list(const value_traits &v_traits = value_traits()) : Base(v_traits) {} @@ -1506,7 +1537,7 @@ class list {} list& operator=(BOOST_RV_REF(list) x) - { this->Base::operator=(::boost::move(static_cast<Base&>(x))); return *this; } + { return static_cast<list &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } static list &container_from_end_iterator(iterator end_iterator) { return static_cast<list &>(Base::container_from_end_iterator(end_iterator)); } |