Mercurial > hg > vamp-build-and-test
diff DEPENDENCIES/generic/include/boost/intrusive/slist.hpp @ 101:c530137014c0
Update Boost headers (1.58.0)
| author | Chris Cannam |
|---|---|
| date | Mon, 07 Sep 2015 11:12:49 +0100 |
| parents | 2665513ce2d3 |
| children |
line wrap: on
line diff
--- a/DEPENDENCIES/generic/include/boost/intrusive/slist.hpp Fri Sep 04 12:01:02 2015 +0100 +++ b/DEPENDENCIES/generic/include/boost/intrusive/slist.hpp Mon Sep 07 11:12:49 2015 +0100 @@ -1,7 +1,7 @@ ///////////////////////////////////////////////////////////////////////////// // // (C) Copyright Olaf Krzikalla 2004-2006. -// (C) Copyright Ion Gaztanaga 2006-2013 +// (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 @@ -15,49 +15,73 @@ #define BOOST_INTRUSIVE_SLIST_HPP #include <boost/intrusive/detail/config_begin.hpp> -#include <boost/static_assert.hpp> +#include <boost/intrusive/intrusive_fwd.hpp> + #include <boost/intrusive/detail/assert.hpp> -#include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/slist_hook.hpp> #include <boost/intrusive/circular_slist_algorithms.hpp> #include <boost/intrusive/linear_slist_algorithms.hpp> #include <boost/intrusive/pointer_traits.hpp> -#include <boost/intrusive/detail/clear_on_destructor_base.hpp> #include <boost/intrusive/link_mode.hpp> -#include <boost/intrusive/options.hpp> -#include <boost/intrusive/detail/utilities.hpp> -#include <iterator> -#include <functional> -#include <algorithm> +#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/uncast.hpp> +#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/detail/iterator.hpp> +#include <boost/intrusive/detail/slist_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/intrusive/detail/algorithm.hpp> + +#include <boost/move/utility_core.hpp> +#include <boost/static_assert.hpp> + +#include <boost/intrusive/detail/minimal_less_equal_header.hpp>//std::less #include <cstddef> //std::size_t -#include <utility> //std::pair -#include <boost/move/move.hpp> +#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { /// @cond -template<class Node, class NodePtr, bool> -struct root_plus_last +template<class HeaderHolder, class NodePtr, bool> +struct header_holder_plus_last { - Node root_; + HeaderHolder header_holder_; NodePtr last_; }; -template<class Node, class NodePtr> -struct root_plus_last<Node, NodePtr, false> +template<class HeaderHolder, class NodePtr> +struct header_holder_plus_last<HeaderHolder, NodePtr, false> { - Node root_; + HeaderHolder header_holder_; }; +struct default_slist_hook_applier +{ template <class T> struct apply{ typedef typename T::default_slist_hook type; }; }; + +template<> +struct is_default_hook_tag<default_slist_hook_applier> +{ static const bool value = true; }; + struct slist_defaults { - typedef detail::default_slist_hook proto_value_traits; + typedef default_slist_hook_applier proto_value_traits; static const bool constant_time_size = true; static const bool linear = false; typedef std::size_t size_type; static const bool cache_last = false; + typedef void header_holder_type; }; struct slist_bool_flags @@ -96,41 +120,35 @@ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class ValueTraits, class SizeType, std::size_t BoolFlags> +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> #endif class slist_impl - : private detail::clear_on_destructor_base - < slist_impl<ValueTraits, SizeType, BoolFlags> - , is_safe_autounlink<detail::get_real_value_traits<ValueTraits>::type::link_mode>::value - > { - template<class C, bool> friend class detail::clear_on_destructor_base; //Public typedefs public: typedef ValueTraits value_traits; - /// @cond - static const bool external_value_traits = - detail::external_value_traits_bool_is_true<value_traits>::value; - typedef typename detail::get_real_value_traits<ValueTraits>::type real_value_traits; - /// @endcond - typedef typename real_value_traits::pointer pointer; - typedef typename real_value_traits::const_pointer const_pointer; + 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 SizeType size_type; - typedef slist_iterator<real_value_traits, false> iterator; - typedef slist_iterator<real_value_traits, true> const_iterator; - typedef typename real_value_traits::node_traits node_traits; + typedef slist_iterator<value_traits, false> iterator; + typedef slist_iterator<value_traits, true> const_iterator; + 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 typename detail::get_header_holder_type + < value_traits, HeaderHolder >::type header_holder_type; static const bool constant_time_size = 0 != (BoolFlags & slist_bool_flags::constant_time_size_pos); - static const bool stateful_value_traits = detail::is_stateful_value_traits<real_value_traits>::value; + static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; static const bool linear = 0 != (BoolFlags & slist_bool_flags::linear_pos); static const bool cache_last = 0 != (BoolFlags & slist_bool_flags::cache_last_pos); + static const bool has_container_from_iterator = + detail::is_same< header_holder_type, detail::default_header_holder< node_traits > >::value; typedef typename detail::if_c < linear @@ -145,14 +163,14 @@ //noncopyable BOOST_MOVABLE_BUT_NOT_COPYABLE(slist_impl) - static const bool safemode_or_autounlink = is_safe_autounlink<real_value_traits::link_mode>::value; + 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))); + BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink))); //Linear singly linked lists are incompatible with auto-unlink hooks! - BOOST_STATIC_ASSERT(!(linear && ((int)real_value_traits::link_mode == (int)auto_unlink))); + BOOST_STATIC_ASSERT(!(linear && ((int)value_traits::link_mode == (int)auto_unlink))); //A list with cached last node is incompatible with auto-unlink hooks! - BOOST_STATIC_ASSERT(!(cache_last && ((int)real_value_traits::link_mode == (int)auto_unlink))); + BOOST_STATIC_ASSERT(!(cache_last && ((int)value_traits::link_mode == (int)auto_unlink))); node_ptr get_end_node() { return node_ptr(linear ? node_ptr() : this->get_root_node()); } @@ -163,10 +181,10 @@ (linear ? const_node_ptr() : this->get_root_node()); } node_ptr get_root_node() - { return pointer_traits<node_ptr>::pointer_to(data_.root_plus_size_.root_); } + { return data_.root_plus_size_.header_holder_.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_.header_holder_.get_node(); } node_ptr get_last_node() { return this->get_last_node(detail::bool_<cache_last>()); } @@ -208,9 +226,10 @@ } } + typedef header_holder_plus_last<header_holder_type, node_ptr, cache_last> header_holder_plus_last_t; struct root_plus_size : public size_traits - , public root_plus_last<node, node_ptr, cache_last> + , public header_holder_plus_last_t {}; struct data_t @@ -230,51 +249,22 @@ 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>()); } - - typedef typename pointer_traits<node_ptr>::template rebind_pointer<const real_value_traits>::type const_real_value_traits_ptr; - - const_real_value_traits_ptr real_value_traits_ptr() const - { return pointer_traits<const_real_value_traits_ptr>::pointer_to(this->get_real_value_traits()); } - - public: - ///@cond //! <b>Requires</b>: f and before_l belong to another slist. @@ -325,7 +315,7 @@ //! //! <b>Effects</b>: Constructs a list equal to [b ,e). //! - //! <b>Complexity</b>: Linear in std::distance(b, e). No copy constructors are called. + //! <b>Complexity</b>: Linear in distance(b, e). No copy constructors are called. //! //! <b>Throws</b>: If value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). @@ -334,6 +324,7 @@ : data_(v_traits) { this->set_default_constructed_state(); + //nothrow, no need to rollback to release elements on exception this->insert_after(this->cbefore_begin(), b, e); } @@ -344,6 +335,7 @@ { 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); } @@ -352,7 +344,6 @@ slist_impl& operator=(BOOST_RV_REF(slist_impl) x) { this->swap(x); return *this; } - #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! <b>Effects</b>: If it's a safe-mode //! or auto-unlink value, the destructor does nothing //! (ie. no code is generated). Otherwise it detaches all elements from this. @@ -363,8 +354,12 @@ //! <b>Complexity</b>: Linear to the number of elements in the list, if //! it's a safe-mode or auto-unlink value. Otherwise constant. ~slist_impl() - {} - #endif + { + if(is_safe_autounlink<ValueTraits::link_mode>::value){ + this->clear(); + node_algorithms::init(this->get_root_node()); + } + } //! <b>Effects</b>: Erases all the elements of the container. //! @@ -403,7 +398,7 @@ ++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)); } this->set_default_constructed_state(); } @@ -420,7 +415,7 @@ //! <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)); if(cache_last){ @@ -446,7 +441,7 @@ void push_back(reference value) { BOOST_STATIC_ASSERT((cache_last)); - node_ptr n = get_real_value_traits().to_node_ptr(value); + node_ptr n = priv_value_traits().to_node_ptr(value); if(safemode_or_autounlink) BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(n)); node_algorithms::link_after(this->get_last_node(), n); @@ -485,7 +480,7 @@ 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)); if(cache_last){ if(this->empty()){ this->set_last_node(this->get_root_node()); @@ -499,7 +494,7 @@ //! //! <b>Complexity</b>: Constant. reference front() - { return *this->get_real_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); } + { return *this->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. //! @@ -507,7 +502,7 @@ //! //! <b>Complexity</b>: Constant. const_reference front() const - { return *this->get_real_value_traits().to_value_ptr(detail::uncast(node_traits::get_next(this->get_root_node()))); } + { return *this->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. //! @@ -520,7 +515,7 @@ reference back() { BOOST_STATIC_ASSERT((cache_last)); - return *this->get_real_value_traits().to_value_ptr(this->get_last_node()); + return *this->priv_value_traits().to_value_ptr(this->get_last_node()); } //! <b>Effects</b>: Returns a const_reference to the last element of the list. @@ -534,7 +529,7 @@ const_reference back() const { BOOST_STATIC_ASSERT((cache_last)); - return *this->get_real_value_traits().to_value_ptr(this->get_last_node()); + return *this->priv_value_traits().to_value_ptr(this->get_last_node()); } //! <b>Effects</b>: Returns an iterator to the first element contained in the list. @@ -543,7 +538,7 @@ //! //! <b>Complexity</b>: Constant. iterator begin() - { return iterator (node_traits::get_next(this->get_root_node()), this->real_value_traits_ptr()); } + { 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. //! @@ -551,7 +546,7 @@ //! //! <b>Complexity</b>: Constant. const_iterator begin() const - { return const_iterator (node_traits::get_next(this->get_root_node()), this->real_value_traits_ptr()); } + { return const_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. //! @@ -559,7 +554,7 @@ //! //! <b>Complexity</b>: Constant. const_iterator cbegin() const - { return const_iterator(node_traits::get_next(this->get_root_node()), this->real_value_traits_ptr()); } + { 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. //! @@ -567,7 +562,7 @@ //! //! <b>Complexity</b>: Constant. iterator end() - { return iterator(this->get_end_node(), this->real_value_traits_ptr()); } + { return iterator(this->get_end_node(), this->priv_value_traits_ptr()); } //! <b>Effects</b>: Returns a const_iterator to the end of the list. //! @@ -575,7 +570,7 @@ //! //! <b>Complexity</b>: Constant. const_iterator end() const - { return const_iterator(detail::uncast(this->get_end_node()), this->real_value_traits_ptr()); } + { return const_iterator(detail::uncast(this->get_end_node()), this->priv_value_traits_ptr()); } //! <b>Effects</b>: Returns a const_iterator to the end of the list. //! @@ -592,7 +587,7 @@ //! //! <b>Complexity</b>: Constant. iterator before_begin() - { return iterator(this->get_root_node(), this->real_value_traits_ptr()); } + { return iterator(this->get_root_node(), this->priv_value_traits_ptr()); } //! <b>Effects</b>: Returns an iterator that points to a position //! before the first element. Equivalent to "end()" @@ -601,7 +596,7 @@ //! //! <b>Complexity</b>: Constant. const_iterator before_begin() const - { return const_iterator(detail::uncast(this->get_root_node()), this->real_value_traits_ptr()); } + { return const_iterator(detail::uncast(this->get_root_node()), this->priv_value_traits_ptr()); } //! <b>Effects</b>: Returns an iterator that points to a position //! before the first element. Equivalent to "end()" @@ -623,7 +618,7 @@ { //This function shall not be used if cache_last is not true BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last); - return iterator (this->get_last_node(), this->real_value_traits_ptr()); + return iterator (this->get_last_node(), this->priv_value_traits_ptr()); } //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list. @@ -637,7 +632,7 @@ { //This function shall not be used if cache_last is not true BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last); - return const_iterator (this->get_last_node(), this->real_value_traits_ptr()); + return const_iterator (this->get_last_node(), this->priv_value_traits_ptr()); } //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list. @@ -648,7 +643,7 @@ //! //! <b>Note</b>: This function is present only if cached_last<> option is true. const_iterator clast() const - { return const_iterator(this->get_last_node(), this->real_value_traits_ptr()); } + { return const_iterator(this->get_last_node(), this->priv_value_traits_ptr()); } //! <b>Precondition</b>: end_iterator must be a valid end iterator //! of slist. @@ -788,7 +783,7 @@ //! <b>Note</b>: Does not affect the validity of iterators and references. iterator insert_after(const_iterator prev_p, reference value) { - node_ptr n = get_real_value_traits().to_node_ptr(value); + node_ptr n = priv_value_traits().to_node_ptr(value); if(safemode_or_autounlink) BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(n)); node_ptr prev_n(prev_p.pointed_node()); @@ -797,7 +792,7 @@ this->set_last_node(n); } this->priv_size_traits().increment(); - return iterator (n, this->real_value_traits_ptr()); + return iterator (n, this->priv_value_traits_ptr()); } //! <b>Requires</b>: Dereferencing iterator must yield @@ -819,7 +814,7 @@ size_type count = 0; node_ptr prev_n(prev_p.pointed_node()); for (; f != l; ++f, ++count){ - const node_ptr n = get_real_value_traits().to_node_ptr(*f); + const node_ptr n = priv_value_traits().to_node_ptr(*f); if(safemode_or_autounlink) BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(n)); node_algorithms::link_after(prev_n, n); @@ -914,7 +909,7 @@ } //! <b>Effects</b>: Erases the range (before_f, l) from - //! the list. n must be std::distance(before_f, l) - 1. + //! the list. n must be distance(before_f, l) - 1. //! No destructors are called. //! //! <b>Returns</b>: the first element remaining beyond the removed elements, @@ -929,7 +924,7 @@ //! erased element. iterator erase_after(const_iterator before_f, const_iterator l, size_type n) { - BOOST_INTRUSIVE_INVARIANT_ASSERT(std::distance(++const_iterator(before_f), l) == difference_type(n)); + BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance((++const_iterator(before_f)).pointed_node(), l.pointed_node()) == n); if(safemode_or_autounlink){ return this->erase_after(before_f, l); } @@ -982,7 +977,7 @@ { return this->erase_after(this->previous(f), l); } //! <b>Effects</b>: Erases the range [f, l) from - //! the list. n must be std::distance(f, l). + //! the list. n must be distance(f, l). //! No destructors are called. //! //! <b>Returns</b>: the first element remaining beyond the removed elements, @@ -1026,7 +1021,7 @@ } 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 it.unconst(); } @@ -1045,7 +1040,7 @@ node_algorithms::unlink_after(prev_n); if(safemode_or_autounlink) node_algorithms::init(to_erase); - disposer(real_value_traits::to_value_ptr(to_erase)); + disposer(value_traits::to_value_ptr(to_erase)); return it.unconst(); } @@ -1079,7 +1074,7 @@ fp = node_traits::get_next(fp); 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(); } if(cache_last && (node_traits::get_next(bfp) == this->get_end_node())){ @@ -1263,7 +1258,7 @@ void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator before_f, const_iterator before_l) { if(constant_time_size) - this->splice_after(prev_pos, x, before_f, before_l, std::distance(before_f, before_l)); + this->splice_after(prev_pos, x, before_f, before_l, node_algorithms::distance(before_f.pointed_node(), before_l.pointed_node())); else this->priv_splice_after (prev_pos.pointed_node(), x, before_f.pointed_node(), before_l.pointed_node()); @@ -1272,7 +1267,7 @@ //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be //! before_begin(), and before_f and before_l belong to x and //! ++before_f != x.end() && before_l != x.end() and - //! n == std::distance(before_f, before_l). + //! n == distance(before_f, before_l). //! //! <b>Effects</b>: Transfers the range (before_f, before_l] from list x to this //! list, after the element pointed by p. No destructors or copy constructors are called. @@ -1285,7 +1280,7 @@ //! list. Iterators of this list and all the references are not invalidated. void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator before_f, const_iterator before_l, size_type n) { - BOOST_INTRUSIVE_INVARIANT_ASSERT(std::distance(before_f, before_l) == difference_type(n)); + BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance(before_f.pointed_node(), before_l.pointed_node()) == n); this->priv_splice_after (prev_pos.pointed_node(), x, before_f.pointed_node(), before_l.pointed_node()); if(constant_time_size){ @@ -1357,7 +1352,7 @@ //! <b>Requires</b>: pos must be a dereferenceable iterator in *this //! and f and l belong to x and f and l a valid range on x. - //! n == std::distance(f, l). + //! n == distance(f, l). //! //! <b>Effects</b>: Transfers the range [f, l) from list x to this //! list, before the element pointed by pos. @@ -1567,7 +1562,20 @@ //! 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 bbeg = this->get_root_node(); + typename node_algorithms::stable_partition_info info; + node_algorithms::stable_partition + (bbeg, this->get_end_node(), detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info); + //After cache last is set, slist invariants are preserved... + if(cache_last){ + this->set_last_node(info.new_last_node); + } + //...so erase can be safely called + this->erase_after( const_iterator(bbeg, 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. //! @@ -1584,20 +1592,18 @@ template<class Pred, class Disposer> void remove_and_dispose_if(Pred pred, Disposer disposer) { - const_iterator bcur(this->before_begin()), cur(this->begin()), e(this->end()); - - while(cur != e){ - if (pred(*cur)){ - cur = this->erase_after_and_dispose(bcur, disposer); - } - else{ - bcur = cur; - ++cur; - } + const node_ptr bbeg = this->get_root_node(); + typename node_algorithms::stable_partition_info info; + node_algorithms::stable_partition + (bbeg, this->get_end_node(), detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info); + //After cache last is set, slist invariants are preserved... + if(cache_last){ + this->set_last_node(info.new_last_node); } - if(cache_last){ - this->set_last_node(bcur.pointed_node()); - } + //...so erase can be safely called + this->erase_after_and_dispose( const_iterator(bbeg, 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 @@ -1691,8 +1697,7 @@ static iterator s_iterator_to(reference value) { BOOST_STATIC_ASSERT((!stateful_value_traits)); - //BOOST_INTRUSIVE_INVARIANT_ASSERT (!node_algorithms::inited(value_traits::to_node_ptr(value))); - return iterator (value_traits::to_node_ptr(value), const_real_value_traits_ptr()); + 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. @@ -1709,8 +1714,8 @@ static const_iterator s_iterator_to(const_reference value) { BOOST_STATIC_ASSERT((!stateful_value_traits)); - //BOOST_INTRUSIVE_INVARIANT_ASSERT (!node_algorithms::inited(value_traits::to_node_ptr(const_cast<reference> (value)))); - return const_iterator (value_traits::to_node_ptr(const_cast<reference> (value)), const_real_value_traits_ptr()); + reference r =*detail::uncast(pointer_traits<const_pointer>::pointer_to(value)); + 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. @@ -1724,8 +1729,8 @@ //! <b>Note</b>: Iterators and references are not invalidated. iterator iterator_to(reference value) { - //BOOST_INTRUSIVE_INVARIANT_ASSERT (!node_algorithms::inited(value_traits::to_node_ptr(value))); - return iterator (value_traits::to_node_ptr(value), this->real_value_traits_ptr()); + BOOST_INTRUSIVE_INVARIANT_ASSERT(linear || !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. @@ -1739,8 +1744,9 @@ //! <b>Note</b>: Iterators and references are not invalidated. const_iterator iterator_to(const_reference value) const { - //BOOST_INTRUSIVE_INVARIANT_ASSERT (!node_algorithms::inited(value_traits::to_node_ptr(const_cast<reference> (value)))); - return const_iterator (value_traits::to_node_ptr(const_cast<reference> (value)), this->real_value_traits_ptr()); + reference r =*detail::uncast(pointer_traits<const_pointer>::pointer_to(value)); + BOOST_INTRUSIVE_INVARIANT_ASSERT (linear || !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>Returns</b>: The iterator to the element before i in the list. @@ -1789,11 +1795,11 @@ const_iterator previous(const_iterator prev_from, const_iterator i) const { if(cache_last && (i.pointed_node() == this->get_end_node())){ - return const_iterator(detail::uncast(this->get_last_node()), this->real_value_traits_ptr()); + return const_iterator(detail::uncast(this->get_last_node()), this->priv_value_traits_ptr()); } return const_iterator (node_algorithms::get_previous_node - (prev_from.pointed_node(), i.pointed_node()), this->real_value_traits_ptr()); + (prev_from.pointed_node(), i.pointed_node()), this->priv_value_traits_ptr()); } ///@cond @@ -1817,14 +1823,14 @@ void incorporate_after(const_iterator prev_pos, const node_ptr & f, const node_ptr & before_l) { if(constant_time_size) - this->incorporate_after(prev_pos, f, before_l, std::distance(f, before_l)+1); + this->incorporate_after(prev_pos, f, before_l, node_algorithms::distance(f.pointed_node(), before_l.pointed_node())+1); else this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l); } //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be //! before_begin(), and f and before_l belong to another slist. - //! n == std::distance(f, before_l) + 1. + //! n == distance(f, before_l) + 1. //! //! <b>Effects</b>: Transfers the range [f, before_l] to this //! list, after the element pointed by prev_pos. @@ -1843,9 +1849,9 @@ if(n){ BOOST_INTRUSIVE_INVARIANT_ASSERT(n > 0); BOOST_INTRUSIVE_INVARIANT_ASSERT - (size_type(std::distance - ( iterator(f, this->real_value_traits_ptr()) - , iterator(before_l, this->real_value_traits_ptr()))) + (size_type(boost::intrusive::iterator_distance + ( iterator(f, this->priv_value_traits_ptr()) + , iterator(before_l, this->priv_value_traits_ptr()))) +1 == n); this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l); if(constant_time_size){ @@ -1856,6 +1862,49 @@ ///@endcond + //! <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 is never null + BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_next(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); + if (!linear) + { + BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p); + } + else + { + BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p != header_ptr); + } + if ((!linear && next_p == header_ptr) || (linear && !next_p)) + { + if (cache_last) + BOOST_INTRUSIVE_INVARIANT_ASSERT(get_last_node() == p); + break; + } + p = next_p; + ++node_count; + } + if (constant_time_size) + BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == node_count); + } + private: void priv_splice_after(const node_ptr & prev_pos_n, slist_impl &x, const node_ptr & before_f_n, const node_ptr & before_l_n) { @@ -1982,8 +2031,12 @@ //Obtaining the container from the end iterator is not possible with linear //singly linked lists (because "end" is represented by the null pointer) BOOST_STATIC_ASSERT(!linear); - 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); + header_holder_plus_last_t* hpl = detail::parent_from_member< header_holder_plus_last_t, header_holder_type> + (h, &header_holder_plus_last_t::header_holder_); + root_plus_size* r = static_cast< root_plus_size* >(hpl); data_t *d = detail::parent_from_member<data_t, root_plus_size> ( r, &data_t::root_plus_size_); slist_impl *s = detail::parent_from_member<slist_impl, data_t>(d, &slist_impl::data_); @@ -1994,124 +2047,105 @@ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class ValueTraits, class SizeType, std::size_t BoolFlags> +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> #endif inline bool operator< #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) #else -( const slist_impl<ValueTraits, SizeType, BoolFlags> &x -, const slist_impl<ValueTraits, SizeType, BoolFlags> &y) +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) #endif -{ return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } +{ return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class ValueTraits, class SizeType, std::size_t BoolFlags> +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> #endif bool operator== #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) #else -( const slist_impl<ValueTraits, SizeType, BoolFlags> &x -, const slist_impl<ValueTraits, SizeType, BoolFlags> &y) +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) #endif { - typedef slist_impl<ValueTraits, SizeType, BoolFlags> slist_type; - typedef typename slist_type::const_iterator const_iterator; + typedef slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> slist_type; const bool C = slist_type::constant_time_size; if(C && x.size() != y.size()){ return false; } - const_iterator end1 = x.end(); - - const_iterator i1 = x.begin(); - const_iterator i2 = y.begin(); - if(C){ - while (i1 != end1 && *i1 == *i2) { - ++i1; - ++i2; - } - return i1 == end1; - } - else{ - const_iterator end2 = y.end(); - while (i1 != end1 && i2 != end2 && *i1 == *i2) { - ++i1; - ++i2; - } - return i1 == end1 && i2 == end2; - } + return ::boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend()); } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class ValueTraits, class SizeType, std::size_t BoolFlags> +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> #endif inline bool operator!= #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) #else -( const slist_impl<ValueTraits, SizeType, BoolFlags> &x -, const slist_impl<ValueTraits, SizeType, BoolFlags> &y) +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) #endif { return !(x == y); } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class ValueTraits, class SizeType, std::size_t BoolFlags> +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> #endif inline bool operator> #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) #else -( const slist_impl<ValueTraits, SizeType, BoolFlags> &x -, const slist_impl<ValueTraits, SizeType, BoolFlags> &y) +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) #endif { return y < x; } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class ValueTraits, class SizeType, std::size_t BoolFlags> +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> #endif inline bool operator<= #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) #else -( const slist_impl<ValueTraits, SizeType, BoolFlags> &x -, const slist_impl<ValueTraits, SizeType, BoolFlags> &y) +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) #endif { return !(y < x); } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class ValueTraits, class SizeType, std::size_t BoolFlags> +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> #endif inline bool operator>= #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) #else -( const slist_impl<ValueTraits, SizeType, BoolFlags> &x -, const slist_impl<ValueTraits, SizeType, BoolFlags> &y) +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) #endif { return !(x < y); } #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) template<class T, class ...Options> #else -template<class ValueTraits, class SizeType, std::size_t BoolFlags> +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> #endif inline void swap #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) (slist_impl<T, Options...> &x, slist_impl<T, Options...> &y) #else -( slist_impl<ValueTraits, SizeType, BoolFlags> &x -, slist_impl<ValueTraits, SizeType, BoolFlags> &y) +( slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) #endif { x.swap(y); } @@ -2120,7 +2154,7 @@ #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) template<class T, class ...Options> #else -template<class T, class O1 = void, class O2 = void, class O3 = void, class O4 = void, class O5 = void> +template<class T, class O1 = void, class O2 = void, class O3 = void, class O4 = void, class O5 = void, class O6 = void> #endif struct make_slist { @@ -2128,11 +2162,12 @@ typedef typename pack_options < slist_defaults, #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) - O1, O2, O3, O4, O5 + O1, O2, O3, O4, O5, O6 #else Options... #endif >::type packed_options; + typedef typename detail::get_value_traits <T, typename packed_options::proto_value_traits>::type value_traits; typedef slist_impl @@ -2141,6 +2176,7 @@ , (std::size_t(packed_options::linear)*slist_bool_flags::linear_pos) |(std::size_t(packed_options::constant_time_size)*slist_bool_flags::constant_time_size_pos) |(std::size_t(packed_options::cache_last)*slist_bool_flags::cache_last_pos) + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -2150,14 +2186,14 @@ #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) -template<class T, class O1, class O2, class O3, class O4, class O5> +template<class T, class O1, class O2, class O3, class O4, class O5, class O6> #else template<class T, class ...Options> #endif class slist : public make_slist<T, #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) - O1, O2, O3, O4, O5 + O1, O2, O3, O4, O5, O6 #else Options... #endif @@ -2166,14 +2202,13 @@ typedef typename make_slist <T, #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) - O1, O2, O3, O4, O5 + O1, O2, O3, O4, O5, O6 #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(slist) public: @@ -2200,11 +2235,11 @@ {} slist(BOOST_RV_REF(slist) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} slist& operator=(BOOST_RV_REF(slist) x) - { return static_cast<slist &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<slist &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static slist &container_from_end_iterator(iterator end_iterator) { return static_cast<slist &>(Base::container_from_end_iterator(end_iterator)); }