diff options
Diffstat (limited to 'boost/intrusive')
93 files changed, 1819 insertions, 1481 deletions
diff --git a/boost/intrusive/any_hook.hpp b/boost/intrusive/any_hook.hpp index 1b538373d9..809507c3bf 100644 --- a/boost/intrusive/any_hook.hpp +++ b/boost/intrusive/any_hook.hpp @@ -13,10 +13,6 @@ #ifndef BOOST_INTRUSIVE_ANY_HOOK_HPP #define BOOST_INTRUSIVE_ANY_HOOK_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/any_node_and_algorithms.hpp> @@ -25,6 +21,10 @@ #include <boost/intrusive/detail/mpl.hpp> #include <boost/intrusive/pointer_rebind.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { diff --git a/boost/intrusive/avl_set.hpp b/boost/intrusive/avl_set.hpp index 58d6108f95..d06d441a19 100644 --- a/boost/intrusive/avl_set.hpp +++ b/boost/intrusive/avl_set.hpp @@ -12,10 +12,6 @@ #ifndef BOOST_INTRUSIVE_AVL_SET_HPP #define BOOST_INTRUSIVE_AVL_SET_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/avltree.hpp> @@ -23,6 +19,10 @@ #include <boost/move/utility_core.hpp> #include <boost/static_assert.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -96,12 +96,12 @@ class avl_set_impl //! @copydoc ::boost::intrusive::avltree::avltree(avltree &&) avl_set_impl(BOOST_RV_REF(avl_set_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::avltree::operator=(avltree &&) avl_set_impl& operator=(BOOST_RV_REF(avl_set_impl) x) - { return static_cast<avl_set_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<avl_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED @@ -268,7 +268,7 @@ class avl_set_impl //! @copydoc ::boost::intrusive::avltree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::avltree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -418,15 +418,13 @@ struct make_avl_set typedef typename detail::get_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 avl_set_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -479,11 +477,11 @@ class avl_set {} avl_set(BOOST_RV_REF(avl_set) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} avl_set& operator=(BOOST_RV_REF(avl_set) x) - { return static_cast<avl_set &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<avl_set &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static avl_set &container_from_end_iterator(iterator end_iterator) { return static_cast<avl_set &>(Base::container_from_end_iterator(end_iterator)); } @@ -569,12 +567,12 @@ class avl_multiset_impl //! @copydoc ::boost::intrusive::avltree::avltree(avltree &&) avl_multiset_impl(BOOST_RV_REF(avl_multiset_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::avltree::operator=(avltree &&) avl_multiset_impl& operator=(BOOST_RV_REF(avl_multiset_impl) x) - { return static_cast<avl_multiset_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<avl_multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::avltree::~avltree() @@ -646,7 +644,7 @@ class avl_multiset_impl //! @copydoc ::boost::intrusive::avltree::clone_from template <class Cloner, class Disposer> void clone_from(const avl_multiset_impl &src, Cloner cloner, Disposer disposer); - + #endif //#ifdef BOOST_iNTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::avltree::insert_equal(reference) @@ -717,7 +715,7 @@ class avl_multiset_impl //! @copydoc ::boost::intrusive::avltree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::avltree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -859,15 +857,13 @@ struct make_avl_multiset typedef typename detail::get_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 avl_multiset_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -921,11 +917,11 @@ class avl_multiset {} avl_multiset(BOOST_RV_REF(avl_multiset) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} avl_multiset& operator=(BOOST_RV_REF(avl_multiset) x) - { return static_cast<avl_multiset &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<avl_multiset &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static avl_multiset &container_from_end_iterator(iterator end_iterator) { return static_cast<avl_multiset &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/avl_set_hook.hpp b/boost/intrusive/avl_set_hook.hpp index 6fdc51b707..b61f95f2f0 100644 --- a/boost/intrusive/avl_set_hook.hpp +++ b/boost/intrusive/avl_set_hook.hpp @@ -13,10 +13,6 @@ #ifndef BOOST_INTRUSIVE_AVL_SET_HOOK_HPP #define BOOST_INTRUSIVE_AVL_SET_HOOK_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -25,6 +21,10 @@ #include <boost/intrusive/options.hpp> #include <boost/intrusive/detail/generic_hook.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { diff --git a/boost/intrusive/avltree.hpp b/boost/intrusive/avltree.hpp index d2adf24917..1996d69c68 100644 --- a/boost/intrusive/avltree.hpp +++ b/boost/intrusive/avltree.hpp @@ -12,15 +12,11 @@ #ifndef BOOST_INTRUSIVE_AVLTREE_HPP #define BOOST_INTRUSIVE_AVLTREE_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <cstddef> -#include <functional> -#include <utility> +#include <boost/intrusive/detail/minimal_less_equal_header.hpp> +#include <boost/intrusive/detail/minimal_pair_header.hpp> #include <boost/static_assert.hpp> #include <boost/intrusive/avl_set_hook.hpp> @@ -35,6 +31,10 @@ #include <boost/intrusive/link_mode.hpp> #include <boost/move/utility_core.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -86,7 +86,7 @@ class avltree_impl /// @cond typedef bstree_impl< ValueTraits, VoidOrKeyComp, SizeType , ConstantTimeSize, AvlTreeAlgorithms - , HeaderHolder> tree_type; + , HeaderHolder> tree_type; typedef tree_type implementation_defined; /// @endcond @@ -140,12 +140,12 @@ class avltree_impl //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) avltree_impl(BOOST_RV_REF(avltree_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) avltree_impl& operator=(BOOST_RV_REF(avltree_impl) x) - { return static_cast<avltree_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<avltree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED @@ -307,7 +307,7 @@ class avltree_impl //! @copydoc ::boost::intrusive::bstree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -455,15 +455,13 @@ struct make_avltree typedef typename detail::get_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 avltree_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -520,11 +518,11 @@ class avltree {} avltree(BOOST_RV_REF(avltree) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} avltree& operator=(BOOST_RV_REF(avltree) x) - { return static_cast<avltree &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<avltree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static avltree &container_from_end_iterator(iterator end_iterator) { return static_cast<avltree &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/avltree_algorithms.hpp b/boost/intrusive/avltree_algorithms.hpp index e5bcfde160..60a981c381 100644 --- a/boost/intrusive/avltree_algorithms.hpp +++ b/boost/intrusive/avltree_algorithms.hpp @@ -14,10 +14,6 @@ #ifndef BOOST_INTRUSIVE_AVLTREE_ALGORITHMS_HPP #define BOOST_INTRUSIVE_AVLTREE_ALGORITHMS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -28,6 +24,11 @@ #include <boost/intrusive/detail/ebo_functor_holder.hpp> #include <boost/intrusive/bstree_algorithms.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + + namespace boost { namespace intrusive { @@ -35,7 +36,8 @@ namespace intrusive { template<class NodeTraits, class F> struct avltree_node_cloner - : private detail::ebo_functor_holder<F> + //Use public inheritance to avoid MSVC bugs with closures + : public detail::ebo_functor_holder<F> { typedef typename NodeTraits::node_ptr node_ptr; typedef detail::ebo_functor_holder<F> base_t; @@ -50,6 +52,13 @@ struct avltree_node_cloner NodeTraits::set_balance(n, NodeTraits::get_balance(p)); return n; } + + node_ptr operator()(const node_ptr & p) const + { + node_ptr n = base_t::get()(p); + NodeTraits::set_balance(n, NodeTraits::get_balance(p)); + return n; + } }; namespace detail { @@ -168,7 +177,7 @@ class avltree_algorithms //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree static void swap_tree(const node_ptr & header1, const node_ptr & header2); - + #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&) @@ -604,7 +613,7 @@ class avltree_algorithms const node_ptr c = NodeTraits::get_right(a_oldleft); bstree_algo::rotate_left_no_parent_fix(a_oldleft, c); //No need to link c with a [NodeTraits::set_parent(c, a) + NodeTraits::set_left(a, c)] - //as c is not root and another rotation is coming + //as c is not root and another rotation is coming bstree_algo::rotate_right(a, c, NodeTraits::get_parent(a), hdr); left_right_balancing(a, a_oldleft, c); return c; diff --git a/boost/intrusive/bs_set.hpp b/boost/intrusive/bs_set.hpp index b87a543a5e..f246ce606d 100644 --- a/boost/intrusive/bs_set.hpp +++ b/boost/intrusive/bs_set.hpp @@ -12,10 +12,6 @@ #ifndef BOOST_INTRUSIVE_BS_SET_HPP #define BOOST_INTRUSIVE_BS_SET_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/mpl.hpp> @@ -23,6 +19,10 @@ #include <boost/move/utility_core.hpp> #include <boost/static_assert.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -95,12 +95,12 @@ class bs_set_impl //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) bs_set_impl(BOOST_RV_REF(bs_set_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) bs_set_impl& operator=(BOOST_RV_REF(bs_set_impl) x) - { return static_cast<bs_set_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<bs_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::bstree::~bstree() @@ -172,7 +172,7 @@ class bs_set_impl //! @copydoc ::boost::intrusive::bstree::clone_from template <class Cloner, class Disposer> void clone_from(const bs_set_impl &src, Cloner cloner, Disposer disposer); - + #endif //#ifdef BOOST_iNTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::bstree::insert_unique(reference) @@ -266,7 +266,7 @@ class bs_set_impl //! @copydoc ::boost::intrusive::bstree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -416,15 +416,13 @@ struct make_bs_set typedef typename detail::get_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 bs_set_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -477,11 +475,11 @@ class bs_set {} bs_set(BOOST_RV_REF(bs_set) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} bs_set& operator=(BOOST_RV_REF(bs_set) x) - { return static_cast<bs_set &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<bs_set &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static bs_set &container_from_end_iterator(iterator end_iterator) { return static_cast<bs_set &>(Base::container_from_end_iterator(end_iterator)); } @@ -567,12 +565,12 @@ class bs_multiset_impl //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) bs_multiset_impl(BOOST_RV_REF(bs_multiset_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) bs_multiset_impl& operator=(BOOST_RV_REF(bs_multiset_impl) x) - { return static_cast<bs_multiset_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<bs_multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::bstree::~bstree() @@ -712,10 +710,10 @@ class bs_multiset_impl //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyValueCompare)const template<class KeyType, class KeyValueCompare> size_type count(const KeyType& key, KeyValueCompare comp) const; - + //! @copydoc ::boost::intrusive::bstree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -857,15 +855,13 @@ struct make_bs_multiset typedef typename detail::get_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 bs_multiset_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -919,11 +915,11 @@ class bs_multiset {} bs_multiset(BOOST_RV_REF(bs_multiset) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} bs_multiset& operator=(BOOST_RV_REF(bs_multiset) x) - { return static_cast<bs_multiset &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<bs_multiset &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static bs_multiset &container_from_end_iterator(iterator end_iterator) { return static_cast<bs_multiset &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/bs_set_hook.hpp b/boost/intrusive/bs_set_hook.hpp index cb5af30d63..e96248b4ec 100644 --- a/boost/intrusive/bs_set_hook.hpp +++ b/boost/intrusive/bs_set_hook.hpp @@ -13,10 +13,6 @@ #ifndef BOOST_INTRUSIVE_BS_SET_HOOK_HPP #define BOOST_INTRUSIVE_BS_SET_HOOK_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -25,6 +21,10 @@ #include <boost/intrusive/options.hpp> #include <boost/intrusive/detail/generic_hook.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { diff --git a/boost/intrusive/bstree.hpp b/boost/intrusive/bstree.hpp index 44b02bb790..39c9d3ed2a 100644 --- a/boost/intrusive/bstree.hpp +++ b/boost/intrusive/bstree.hpp @@ -12,10 +12,6 @@ #ifndef BOOST_INTRUSIVE_BSTREE_HPP #define BOOST_INTRUSIVE_BSTREE_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -38,18 +34,22 @@ #include <boost/intrusive/detail/simple_disposers.hpp> #include <boost/intrusive/detail/size_holder.hpp> #include <boost/intrusive/detail/algo_type.hpp> +#include <boost/intrusive/detail/algorithm.hpp> #include <boost/intrusive/detail/get_value_traits.hpp> #include <boost/intrusive/bstree_algorithms.hpp> #include <boost/intrusive/link_mode.hpp> #include <boost/intrusive/parent_from_member.hpp> #include <boost/move/utility_core.hpp> +#include <boost/move/adl_move_swap.hpp> -#include <utility> //pair,lexicographical_compare -#include <algorithm> //swap +#include <boost/intrusive/detail/minimal_pair_header.hpp> #include <cstddef> //size_t... -#include <functional>//less, equal_to +#include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal_to +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -85,8 +85,8 @@ struct bstbase3 typedef typename node_traits::const_node_ptr const_node_ptr; typedef tree_iterator<value_traits, false> iterator; typedef tree_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 boost::intrusive::reverse_iterator<iterator> reverse_iterator; + typedef boost::intrusive::reverse_iterator<const_iterator> const_reverse_iterator; typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer; typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::const_pointer) const_pointer; typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::element_type) value_type; @@ -94,7 +94,8 @@ struct bstbase3 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::reference) reference; typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::reference) const_reference; typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::difference_type) difference_type; - typedef HeaderHolder header_holder_type; + typedef typename detail::get_header_holder_type + < value_traits,HeaderHolder >::type header_holder_type; static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; @@ -227,13 +228,13 @@ struct bstbase3 }; template<class Less, class T> -struct get_less +struct get_compare { typedef Less type; }; template<class T> -struct get_less<void, T> +struct get_compare<void, T> { typedef ::std::less<T> type; }; @@ -241,15 +242,16 @@ struct get_less<void, T> template<class ValueTraits, class VoidOrKeyComp, algo_types AlgoType, typename HeaderHolder> struct bstbase2 //Put the (possibly empty) functor in the first position to get EBO in MSVC - : public detail::ebo_functor_holder<typename get_less< VoidOrKeyComp + //Use public inheritance to avoid MSVC bugs with closures + : public detail::ebo_functor_holder<typename get_compare< VoidOrKeyComp , typename ValueTraits::value_type >::type> , public bstbase3<ValueTraits, AlgoType, HeaderHolder> { - typedef bstbase3<ValueTraits, AlgoType, HeaderHolder> treeheader_t; + typedef bstbase3<ValueTraits, AlgoType, HeaderHolder> treeheader_t; typedef typename treeheader_t::value_traits value_traits; typedef typename treeheader_t::node_algorithms node_algorithms; - typedef typename get_less + typedef typename get_compare < VoidOrKeyComp, typename value_traits::value_type>::type value_compare; typedef BOOST_INTRUSIVE_IMPDEF(value_compare) key_compare; typedef typename treeheader_t::iterator iterator; @@ -267,7 +269,7 @@ struct bstbase2 value_compare &comp() { return this->get(); } - typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer; + typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer; typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::const_pointer) const_pointer; typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::element_type) value_type; typedef BOOST_INTRUSIVE_IMPDEF(value_type) key_type; @@ -618,8 +620,8 @@ class bstree_impl typedef BOOST_INTRUSIVE_IMPDEF(value_compare) key_compare; typedef BOOST_INTRUSIVE_IMPDEF(iterator_type) iterator; typedef BOOST_INTRUSIVE_IMPDEF(const_iterator_type) const_iterator; - typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::detail::reverse_iterator<iterator>) reverse_iterator; - typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::detail::reverse_iterator<const_iterator>) const_reverse_iterator; + typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::reverse_iterator<iterator>) reverse_iterator; + typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::reverse_iterator<const_iterator>) const_reverse_iterator; typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::node_traits) node_traits; typedef BOOST_INTRUSIVE_IMPDEF(typename node_traits::node) node; typedef BOOST_INTRUSIVE_IMPDEF(typename node_traits::node_ptr) node_ptr; @@ -911,8 +913,7 @@ class bstree_impl void swap(bstree_impl& other) { //This can throw - using std::swap; - swap(this->comp(), this->comp()); + ::boost::adl_move_swap(this->comp(), this->comp()); //These can't throw node_algorithms::swap_tree(this->header_ptr(), node_ptr(other.header_ptr())); if(constant_time_size){ @@ -944,8 +945,8 @@ class bstree_impl detail::exception_disposer<bstree_impl, Disposer> rollback(*this, disposer); node_algorithms::clone - (const_node_ptr(src.header_ptr()) - ,node_ptr(this->header_ptr()) + (src.header_ptr() + ,this->header_ptr() ,detail::node_cloner <Cloner, value_traits, AlgoType>(cloner, &this->get_value_traits()) ,detail::node_disposer<Disposer, value_traits, AlgoType>(disposer, &this->get_value_traits())); this->sz_traits().set_size(src.sz_traits().get_size()); @@ -954,6 +955,41 @@ class bstree_impl } } + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! Cloner should yield to nodes equivalent to the original nodes. + //! + //! <b>Effects</b>: Erases all the elements from *this + //! calling Disposer::operator()(pointer), clones all the + //! elements from src calling Cloner::operator()(const_reference ) + //! and inserts them on *this. Copies the predicate from the source container. + //! + //! If cloner throws, all cloned elements are unlinked and disposed + //! calling Disposer::operator()(pointer). + //! + //! <b>Complexity</b>: Linear to erased plus inserted elements. + //! + //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee. + //! + //! <b>Note</b>: This version can modify the source container, useful to implement + //! move semantics. + template <class Cloner, class Disposer> + void clone_from(bstree_impl &src, Cloner cloner, Disposer disposer) + { + this->clear_and_dispose(disposer); + if(!src.empty()){ + detail::exception_disposer<bstree_impl, Disposer> + rollback(*this, disposer); + node_algorithms::clone + (src.header_ptr() + ,this->header_ptr() + ,detail::node_cloner <Cloner, value_traits, AlgoType, false>(cloner, &this->get_value_traits()) + ,detail::node_disposer<Disposer, value_traits, AlgoType>(disposer, &this->get_value_traits())); + this->sz_traits().set_size(src.sz_traits().get_size()); + this->comp() = src.comp(); + rollback.release(); + } + } + //! <b>Requires</b>: value must be an lvalue //! //! <b>Effects</b>: Inserts value into the container before the upper bound. @@ -1271,7 +1307,7 @@ class bstree_impl node_algorithms::push_front(this->header_ptr(), to_insert); } - //! <b>Effects</b>: Erases the element pointed to by pos. + //! <b>Effects</b>: Erases the element pointed to by i. //! //! <b>Complexity</b>: Average complexity for erase element is constant time. //! @@ -1344,7 +1380,7 @@ class bstree_impl //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. //! - //! <b>Effects</b>: Erases the element pointed to by pos. + //! <b>Effects</b>: Erases the element pointed to by i. //! Disposer::operator()(pointer) is called for the removed element. //! //! <b>Complexity</b>: Average complexity for erase element is constant time. @@ -1951,7 +1987,7 @@ inline bool operator< ( const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &x , const bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, 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> @@ -1967,29 +2003,11 @@ bool operator== #endif { typedef bstree_impl<ValueTraits, VoidKeyComp, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> tree_type; - typedef typename tree_type::const_iterator const_iterator; if(tree_type::constant_time_size && x.size() != y.size()){ return false; } - const_iterator end1 = x.end(); - const_iterator i1 = x.begin(); - const_iterator i2 = y.begin(); - if(tree_type::constant_time_size){ - 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) @@ -2085,8 +2103,6 @@ struct make_bstree typedef typename detail::get_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 bstree_impl < value_traits @@ -2094,7 +2110,7 @@ struct make_bstree , typename packed_options::size_type , packed_options::constant_time_size , BsTreeAlgorithms - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -2149,11 +2165,11 @@ class bstree {} bstree(BOOST_RV_REF(bstree) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} bstree& operator=(BOOST_RV_REF(bstree) x) - { return static_cast<bstree &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<bstree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static bstree &container_from_end_iterator(iterator end_iterator) { return static_cast<bstree &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/bstree_algorithms.hpp b/boost/intrusive/bstree_algorithms.hpp index de5445ec52..f7e915e914 100644 --- a/boost/intrusive/bstree_algorithms.hpp +++ b/boost/intrusive/bstree_algorithms.hpp @@ -13,18 +13,20 @@ #ifndef BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP #define BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <cstddef> #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> +#include <boost/intrusive/detail/bstree_algorithms_base.hpp> #include <boost/intrusive/detail/assert.hpp> #include <boost/intrusive/detail/uncast.hpp> #include <boost/intrusive/detail/math.hpp> #include <boost/intrusive/detail/algo_type.hpp> -#include <utility> + +#include <boost/intrusive/detail/minimal_pair_header.hpp> + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -167,7 +169,7 @@ struct bstree_node_checker //! //! <tt>static void set_right(node_ptr n, node_ptr right);</tt> template<class NodeTraits> -class bstree_algorithms +class bstree_algorithms : public bstree_algorithms_base<NodeTraits> { public: typedef typename NodeTraits::node node; @@ -178,7 +180,8 @@ class bstree_algorithms typedef data_for_rebalance_t<node_ptr> data_for_rebalance; /// @cond - + typedef bstree_algorithms<NodeTraits> this_type; + typedef bstree_algorithms_base<NodeTraits> base_type; private: template<class Disposer> struct dispose_subtree_disposer @@ -247,6 +250,7 @@ class bstree_algorithms static bool unique(const const_node_ptr & node) { return !NodeTraits::get_parent(node); } + #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) //! <b>Requires</b>: 'node' is a node of the tree or a header node. //! //! <b>Effects</b>: Returns the header of the tree. @@ -254,42 +258,8 @@ class bstree_algorithms //! <b>Complexity</b>: Logarithmic. //! //! <b>Throws</b>: Nothing. - static node_ptr get_header(const const_node_ptr & node) - { - node_ptr n(detail::uncast(node)); - node_ptr p(NodeTraits::get_parent(node)); - //If p is null, then n is the header of an empty tree - if(p){ - //Non-empty tree, check if n is neither root nor header - node_ptr pp(NodeTraits::get_parent(p)); - //If granparent is not equal to n, then n is neither root nor header, - //the try the fast path - if(n != pp){ - do{ - n = p; - p = pp; - pp = NodeTraits::get_parent(pp); - }while(n != pp); - n = p; - } - //Check if n is root or header when size() > 0 - else if(!is_header(n)){ - n = p; - } - } - return n; - /* - node_ptr h = detail::uncast(node); - node_ptr p = NodeTraits::get_parent(node); - if(p){ - while(!is_header(p)) - p = NodeTraits::get_parent(p); - return p; - } - else{ - return h; - }*/ - } + static node_ptr get_header(const const_node_ptr & node); + #endif //! <b>Requires</b>: node1 and node2 can't be header nodes //! of two trees. @@ -311,7 +281,7 @@ class bstree_algorithms if(node1 == node2) return; - node_ptr header1(get_header(node1)), header2(get_header(node2)); + node_ptr header1(base_type::get_header(node1)), header2(base_type::get_header(node2)); swap_nodes(node1, header1, node2, header2); } @@ -481,7 +451,7 @@ class bstree_algorithms { if(node_to_be_replaced == new_node) return; - replace_node(node_to_be_replaced, get_header(node_to_be_replaced), new_node); + replace_node(node_to_be_replaced, base_type::get_header(node_to_be_replaced), new_node); } //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree @@ -541,6 +511,7 @@ class bstree_algorithms } } + #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) //! <b>Requires</b>: 'node' is a node from the tree except the header. //! //! <b>Effects</b>: Returns the next node of the tree. @@ -548,22 +519,7 @@ class bstree_algorithms //! <b>Complexity</b>: Average constant time. //! //! <b>Throws</b>: Nothing. - static node_ptr next_node(const node_ptr & node) - { - node_ptr const n_right(NodeTraits::get_right(node)); - if(n_right){ - return minimum(n_right); - } - else { - node_ptr n(node); - node_ptr p(NodeTraits::get_parent(n)); - while(n == NodeTraits::get_right(p)){ - n = p; - p = NodeTraits::get_parent(p); - } - return NodeTraits::get_right(n) != p ? p : n; - } - } + static node_ptr next_node(const node_ptr & node); //! <b>Requires</b>: 'node' is a node from the tree except the leftmost node. //! @@ -572,25 +528,7 @@ class bstree_algorithms //! <b>Complexity</b>: Average constant time. //! //! <b>Throws</b>: Nothing. - static node_ptr prev_node(const node_ptr & node) - { - if(is_header(node)){ - return NodeTraits::get_right(node); - //return maximum(NodeTraits::get_parent(node)); - } - else if(NodeTraits::get_left(node)){ - return maximum(NodeTraits::get_left(node)); - } - else { - node_ptr p(node); - node_ptr x = NodeTraits::get_parent(p); - while(p == NodeTraits::get_left(x)){ - p = x; - x = NodeTraits::get_parent(x); - } - return x; - } - } + static node_ptr prev_node(const node_ptr & node); //! <b>Requires</b>: 'node' is a node of a tree but not the header. //! @@ -599,15 +537,7 @@ class bstree_algorithms //! <b>Complexity</b>: Logarithmic to the size of the subtree. //! //! <b>Throws</b>: Nothing. - static node_ptr minimum(node_ptr node) - { - for(node_ptr p_left = NodeTraits::get_left(node) - ;p_left - ;p_left = NodeTraits::get_left(node)){ - node = p_left; - } - return node; - } + static node_ptr minimum(node_ptr node); //! <b>Requires</b>: 'node' is a node of a tree but not the header. //! @@ -616,15 +546,8 @@ class bstree_algorithms //! <b>Complexity</b>: Logarithmic to the size of the subtree. //! //! <b>Throws</b>: Nothing. - static node_ptr maximum(node_ptr node) - { - for(node_ptr p_right = NodeTraits::get_right(node) - ;p_right - ;p_right = NodeTraits::get_right(node)){ - node = p_right; - } - return node; - } + static node_ptr maximum(node_ptr node); + #endif //! <b>Requires</b>: 'node' must not be part of any tree. //! @@ -716,7 +639,7 @@ class bstree_algorithms if (leftmost_right){ NodeTraits::set_parent(leftmost_right, leftmost_parent); - NodeTraits::set_left(header, bstree_algorithms::minimum(leftmost_right)); + NodeTraits::set_left(header, base_type::minimum(leftmost_right)); if (is_root) NodeTraits::set_parent(header, leftmost_right); @@ -747,7 +670,7 @@ class bstree_algorithms node_ptr beg(begin_node(header)); node_ptr end(end_node(header)); std::size_t i = 0; - for(;beg != end; beg = next_node(beg)) ++i; + for(;beg != end; beg = base_type::next_node(beg)) ++i; return i; } @@ -800,6 +723,7 @@ class bstree_algorithms } } + #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) //! <b>Requires</b>: p is a node of a tree. //! //! <b>Effects</b>: Returns true if p is the header of the tree. @@ -807,22 +731,8 @@ class bstree_algorithms //! <b>Complexity</b>: Constant. //! //! <b>Throws</b>: Nothing. - static bool is_header(const const_node_ptr & p) - { - node_ptr p_left (NodeTraits::get_left(p)); - node_ptr p_right(NodeTraits::get_right(p)); - if(!NodeTraits::get_parent(p) || //Header condition when empty tree - (p_left && p_right && //Header always has leftmost and rightmost - (p_left == p_right || //Header condition when only node - (NodeTraits::get_parent(p_left) != p || - NodeTraits::get_parent(p_right) != p )) - //When tree size > 1 headers can't be leftmost's - //and rightmost's parent - )){ - return true; - } - return false; - } + static bool is_header(const const_node_ptr & p); + #endif //! <b>Requires</b>: "header" must be the header node of a tree. //! KeyNodePtrCompare is a function object that induces a strict weak @@ -849,7 +759,7 @@ class bstree_algorithms //! ordering compatible with the strict weak ordering used to create the //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If - //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false. + //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be true. //! //! <b>Effects</b>: Returns an a pair with the following criteria: //! @@ -892,7 +802,7 @@ class bstree_algorithms x = NodeTraits::get_left(x); } else{ - //x is inside the bounded range( x >= lower_key && x <= upper_key), + //x is inside the bounded range(lower_key <= x <= upper_key), //so we must split lower and upper searches // //Sanity check: if lower_key and upper_key are equal, then both left_closed and right_closed can't be false @@ -940,7 +850,7 @@ class bstree_algorithms std::size_t n = 0; while(ret.first != ret.second){ ++n; - ret.first = next_node(ret.first); + ret.first = base_type::next_node(ret.first); } return n; } @@ -985,7 +895,7 @@ class bstree_algorithms node_ptr const lb(lower_bound(header, key, comp)); std::pair<node_ptr, node_ptr> ret_ii(lb, lb); if(lb != header && !comp(key, lb)){ - ret_ii.second = next_node(ret_ii.second); + ret_ii.second = base_type::next_node(ret_ii.second); } return ret_ii; } @@ -1087,7 +997,7 @@ class bstree_algorithms (const const_node_ptr & header, const KeyType &key ,KeyNodePtrCompare comp, insert_commit_data &commit_data #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED - , std::size_t *pdepth = 0 + , std::size_t *pdepth = 0 #endif ) { @@ -1164,7 +1074,7 @@ class bstree_algorithms (const const_node_ptr & header, const node_ptr &hint, const KeyType &key ,KeyNodePtrCompare comp, insert_commit_data &commit_data #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED - , std::size_t *pdepth = 0 + , std::size_t *pdepth = 0 #endif ) { @@ -1172,7 +1082,7 @@ class bstree_algorithms if(hint == header || comp(key, hint)){ node_ptr prev(hint); //Previous value should be less than the key - if(hint == begin_node(header) || comp((prev = prev_node(hint)), key)){ + if(hint == begin_node(header) || comp((prev = base_type::prev_node(hint)), key)){ commit_data.link_left = unique(header) || !NodeTraits::get_left(hint); commit_data.node = commit_data.link_left ? hint : prev; if(pdepth){ @@ -1203,7 +1113,7 @@ class bstree_algorithms static node_ptr insert_equal (const node_ptr & h, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED - , std::size_t *pdepth = 0 + , std::size_t *pdepth = 0 #endif ) { @@ -1229,7 +1139,7 @@ class bstree_algorithms static node_ptr insert_equal_upper_bound (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED - , std::size_t *pdepth = 0 + , std::size_t *pdepth = 0 #endif ) { @@ -1255,7 +1165,7 @@ class bstree_algorithms static node_ptr insert_equal_lower_bound (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED - , std::size_t *pdepth = 0 + , std::size_t *pdepth = 0 #endif ) { @@ -1282,7 +1192,7 @@ class bstree_algorithms static node_ptr insert_before (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED - , std::size_t *pdepth = 0 + , std::size_t *pdepth = 0 #endif ) { @@ -1308,7 +1218,7 @@ class bstree_algorithms static void push_back (const node_ptr & header, const node_ptr & new_node #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED - , std::size_t *pdepth = 0 + , std::size_t *pdepth = 0 #endif ) { @@ -1333,7 +1243,7 @@ class bstree_algorithms static void push_front (const node_ptr & header, const node_ptr & new_node #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED - , std::size_t *pdepth = 0 + , std::size_t *pdepth = 0 #endif ) { @@ -1375,7 +1285,7 @@ class bstree_algorithms //! the nodes of the target tree. If "cloner" throws, the cloned target nodes //! are disposed using <tt>void disposer(const node_ptr &)</tt>. //! - //! <b>Complexity</b>: Linear to the number of element of the source tree plus the. + //! <b>Complexity</b>: Linear to the number of element of the source tree plus the //! number of elements of tree target tree when calling this function. //! //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed. @@ -1422,7 +1332,7 @@ class bstree_algorithms { node_ptr x = NodeTraits::get_parent(node); if(x){ - while(!is_header(x)) + while(!base_type::is_header(x)) x = NodeTraits::get_parent(x); erase(x, node); } @@ -1503,27 +1413,25 @@ class bstree_algorithms template<class Checker> static void check(const const_node_ptr& header, Checker checker, typename Checker::return_type& checker_return) { - const_node_ptr root_node_ptr = NodeTraits::get_parent(header); - if (!root_node_ptr) - { - // check left&right header pointers - BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == header); - BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == header); - } - else - { - // check parent pointer of root node - BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(root_node_ptr) == header); - // check subtree from root - check_subtree(root_node_ptr, checker, checker_return); - // check left&right header pointers - const_node_ptr p = root_node_ptr; - while (NodeTraits::get_left(p)) { p = NodeTraits::get_left(p); } - BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == p); - p = root_node_ptr; - while (NodeTraits::get_right(p)) { p = NodeTraits::get_right(p); } - BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == p); - } + const_node_ptr root_node_ptr = NodeTraits::get_parent(header); + if (!root_node_ptr){ + // check left&right header pointers + BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == header); + BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == header); + } + else{ + // check parent pointer of root node + BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(root_node_ptr) == header); + // check subtree from root + check_subtree(root_node_ptr, checker, checker_return); + // check left&right header pointers + const_node_ptr p = root_node_ptr; + while (NodeTraits::get_left(p)) { p = NodeTraits::get_left(p); } + BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == p); + p = root_node_ptr; + while (NodeTraits::get_right(p)) { p = NodeTraits::get_right(p); } + BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == p); + } } protected: @@ -1543,7 +1451,7 @@ class bstree_algorithms } else{ //make y != z // y = find z's successor - y = bstree_algorithms::minimum(z_right); + y = base_type::minimum(z_right); x = NodeTraits::get_right(y); // x might be null. } @@ -1573,14 +1481,14 @@ class bstree_algorithms x_parent = y; } NodeTraits::set_parent(y, z_parent); - bstree_algorithms::set_child(header, y, z_parent, z_is_leftchild); + this_type::set_child(header, y, z_parent, z_is_leftchild); } else { // z has zero or one child, x is one child (it can be null) //Just link x to z's parent x_parent = z_parent; if(x) NodeTraits::set_parent(x, z_parent); - bstree_algorithms::set_child(header, x, z_parent, z_is_leftchild); + this_type::set_child(header, x, z_parent, z_is_leftchild); //Now update leftmost/rightmost in case z was one of them if(NodeTraits::get_left(header) == z){ @@ -1588,14 +1496,14 @@ class bstree_algorithms BOOST_ASSERT(!z_left); NodeTraits::set_left(header, !z_right ? z_parent : // makes leftmost == header if z == root - bstree_algorithms::minimum(z_right)); + base_type::minimum(z_right)); } if(NodeTraits::get_right(header) == z){ //z_right must be null because z is the rightmost BOOST_ASSERT(!z_right); NodeTraits::set_right(header, !z_left ? z_parent : // makes rightmost == header if z == root - bstree_algorithms::maximum(z_left)); + base_type::maximum(z_left)); } } @@ -1676,13 +1584,13 @@ class bstree_algorithms (const node_ptr &header, const node_ptr & pos , insert_commit_data &commit_data #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED - , std::size_t *pdepth = 0 + , std::size_t *pdepth = 0 #endif ) { node_ptr prev(pos); if(pos != NodeTraits::get_left(header)) - prev = prev_node(pos); + prev = base_type::prev_node(pos); bool link_left = unique(header) || !NodeTraits::get_left(pos); commit_data.link_left = link_left; commit_data.node = link_left ? pos : prev; @@ -1694,7 +1602,7 @@ class bstree_algorithms static void push_back_check (const node_ptr & header, insert_commit_data &commit_data #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED - , std::size_t *pdepth = 0 + , std::size_t *pdepth = 0 #endif ) { @@ -1709,7 +1617,7 @@ class bstree_algorithms static void push_front_check (const node_ptr & header, insert_commit_data &commit_data #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED - , std::size_t *pdepth = 0 + , std::size_t *pdepth = 0 #endif ) { @@ -1733,7 +1641,7 @@ class bstree_algorithms if(hint == header || !comp(hint, new_node)){ node_ptr prev(hint); if(hint == NodeTraits::get_left(header) || - !comp(new_node, (prev = prev_node(hint)))){ + !comp(new_node, (prev = base_type::prev_node(hint)))){ bool link_left = unique(header) || !NodeTraits::get_left(hint); commit_data.link_left = link_left; commit_data.node = link_left ? hint : prev; @@ -1894,7 +1802,7 @@ class bstree_algorithms } } size = len; - } + } static void compress_subtree(node_ptr scanner, std::size_t count) { @@ -1945,7 +1853,7 @@ class bstree_algorithms BOOST_INTRUSIVE_INVARIANT_ASSERT((!inited(node))); node_ptr x = NodeTraits::get_parent(node); if(x){ - while(!is_header(x)){ + while(!base_type::is_header(x)){ x = NodeTraits::get_parent(x); } return x; diff --git a/boost/intrusive/circular_list_algorithms.hpp b/boost/intrusive/circular_list_algorithms.hpp index 1e888a1cae..f3430455ae 100644 --- a/boost/intrusive/circular_list_algorithms.hpp +++ b/boost/intrusive/circular_list_algorithms.hpp @@ -14,16 +14,16 @@ #ifndef BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP #define BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/algo_type.hpp> #include <boost/core/no_exceptions_support.hpp> #include <cstddef> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -211,60 +211,6 @@ class circular_list_algorithms //! <b>Complexity</b>: Constant //! //! <b>Throws</b>: Nothing. -/* - static void swap_nodes(const node_ptr &this_node, const node_ptr &other_node) - { - - if (other_node == this_node) - return; - bool empty1 = unique(this_node); - bool empty2 = unique(other_node); - - node_ptr next_this(NodeTraits::get_next(this_node)); - node_ptr prev_this(NodeTraits::get_previous(this_node)); - node_ptr next_other(NodeTraits::get_next(other_node)); - node_ptr prev_other(NodeTraits::get_previous(other_node)); - - //Do the swap - NodeTraits::set_next(this_node, next_other); - NodeTraits::set_next(other_node, next_this); - - NodeTraits::set_previous(this_node, prev_other); - NodeTraits::set_previous(other_node, prev_this); - - if (empty2){ - init(this_node); - } - else{ - NodeTraits::set_next(prev_other, this_node); - NodeTraits::set_previous(next_other, this_node); - } - if (empty1){ - init(other_node); - } - else{ - NodeTraits::set_next(prev_this, other_node); - NodeTraits::set_previous(next_this, other_node); - } - } -*/ - - //Watanabe version - private: - static void swap_prev(const node_ptr &this_node, const node_ptr &other_node) - { - node_ptr temp(NodeTraits::get_previous(this_node)); - NodeTraits::set_previous(this_node, NodeTraits::get_previous(other_node)); - NodeTraits::set_previous(other_node, temp); - } - static void swap_next(const node_ptr &this_node, const node_ptr &other_node) - { - node_ptr temp(NodeTraits::get_next(this_node)); - NodeTraits::set_next(this_node, NodeTraits::get_next(other_node)); - NodeTraits::set_next(other_node, temp); - } - - public: static void swap_nodes(const node_ptr &this_node, const node_ptr &other_node) { if (other_node == this_node) @@ -475,7 +421,7 @@ class circular_list_algorithms BOOST_CATCH(...){ node_traits::set_next (last_to_remove, new_f); node_traits::set_previous(new_f, last_to_remove); - throw; + BOOST_RETHROW; } BOOST_CATCH_END node_traits::set_next(last_to_remove, new_f); @@ -487,6 +433,21 @@ class circular_list_algorithms info.num_2nd_partition = num2; info.beg_2st_partition = new_f; } + + private: + static void swap_prev(const node_ptr &this_node, const node_ptr &other_node) + { + node_ptr temp(NodeTraits::get_previous(this_node)); + NodeTraits::set_previous(this_node, NodeTraits::get_previous(other_node)); + NodeTraits::set_previous(other_node, temp); + } + + static void swap_next(const node_ptr &this_node, const node_ptr &other_node) + { + node_ptr temp(NodeTraits::get_next(this_node)); + NodeTraits::set_next(this_node, NodeTraits::get_next(other_node)); + NodeTraits::set_next(other_node, temp); + } }; /// @cond diff --git a/boost/intrusive/circular_slist_algorithms.hpp b/boost/intrusive/circular_slist_algorithms.hpp index 3dd561df50..951a40ab87 100644 --- a/boost/intrusive/circular_slist_algorithms.hpp +++ b/boost/intrusive/circular_slist_algorithms.hpp @@ -14,16 +14,15 @@ #ifndef BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP #define BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <cstddef> #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/common_slist_algorithms.hpp> #include <boost/intrusive/detail/algo_type.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { diff --git a/boost/intrusive/derivation_value_traits.hpp b/boost/intrusive/derivation_value_traits.hpp index 87bc489cf5..06991983f3 100644 --- a/boost/intrusive/derivation_value_traits.hpp +++ b/boost/intrusive/derivation_value_traits.hpp @@ -13,15 +13,15 @@ #ifndef BOOST_INTRUSIVE_DERIVATION_VALUE_TRAITS_HPP #define BOOST_INTRUSIVE_DERIVATION_VALUE_TRAITS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/link_mode.hpp> #include <boost/intrusive/pointer_traits.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -29,7 +29,7 @@ namespace intrusive { //!from user defined node traits where value_traits::value_type will //!derive from node_traits::node -template<class T, class NodeTraits, link_mode_type LinkMode +template<class T, class NodeTraits, link_mode_type LinkMode #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED = safe_link #endif diff --git a/boost/intrusive/detail/algo_type.hpp b/boost/intrusive/detail/algo_type.hpp index e40cb43b4e..6da48e9e79 100644 --- a/boost/intrusive/detail/algo_type.hpp +++ b/boost/intrusive/detail/algo_type.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_ALGO_TYPE_HPP #define BOOST_INTRUSIVE_DETAIL_ALGO_TYPE_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/algorithm.hpp b/boost/intrusive/detail/algorithm.hpp new file mode 100644 index 0000000000..d2421ffaad --- /dev/null +++ b/boost/intrusive/detail/algorithm.hpp @@ -0,0 +1,90 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2014-2014. +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/libs/intrusive for documentation. +// +////////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_INTRUSIVE_DETAIL_ALGORITHM_HPP +#define BOOST_INTRUSIVE_DETAIL_ALGORITHM_HPP + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +namespace boost { +namespace intrusive { + +struct algo_pred_equal +{ + template<class T> + bool operator()(const T &x, const T &y) const + { return x == y; } +}; + +struct algo_pred_less +{ + template<class T> + bool operator()(const T &x, const T &y) const + { return x < y; } +}; + +template<class InputIt1, class InputIt2, class BinaryPredicate> +bool algo_equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, BinaryPredicate p) +{ + for (; first1 != last1; ++first1, ++first2) { + if (!p(*first1, *first2)) { + return false; + } + } + return true; +} + +template<class InputIt1, class InputIt2> +bool algo_equal(InputIt1 first1, InputIt1 last1, InputIt2 first2) +{ return (algo_equal)(first1, last1, first2, algo_pred_equal()); } + +template<class InputIt1, class InputIt2, class BinaryPredicate> +bool algo_equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, BinaryPredicate pred) +{ + for (; first1 != last1 && first2 != last2; ++first1, ++first2) + if (!pred(*first1, *first2)) + return false; + return first1 == last1 && first2 == last2; +} + +template<class InputIt1, class InputIt2> +bool algo_equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) +{ return (algo_equal)(first1, last1, first2, last2, algo_pred_equal()); } + +template <class InputIterator1, class InputIterator2, class BinaryPredicate> + bool algo_lexicographical_compare (InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, InputIterator2 last2, + BinaryPredicate pred) +{ + while (first1 != last1){ + if (first2 == last2 || *first2 < *first1) return false; + else if (pred(*first1, *first2)) return true; + ++first1; ++first2; + } + return (first2 != last2); +} + +template <class InputIterator1, class InputIterator2> + bool algo_lexicographical_compare (InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, InputIterator2 last2) +{ return (algo_lexicographical_compare)(first1, last1, first2, last2, algo_pred_less()); } + +} //namespace intrusive { +} //namespace boost { + +#endif //#ifndef BOOST_INTRUSIVE_DETAIL_ALGORITHM_HPP diff --git a/boost/intrusive/detail/any_node_and_algorithms.hpp b/boost/intrusive/detail/any_node_and_algorithms.hpp index 5a0e8c27fe..3c76e58528 100644 --- a/boost/intrusive/detail/any_node_and_algorithms.hpp +++ b/boost/intrusive/detail/any_node_and_algorithms.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_ANY_NODE_HPP #define BOOST_INTRUSIVE_ANY_NODE_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -43,13 +47,13 @@ struct any_list_node_traits typedef typename node::node_ptr node_ptr; typedef typename node::const_node_ptr const_node_ptr; - static const node_ptr &get_next(const const_node_ptr & n) + static node_ptr get_next(const const_node_ptr & n) { return n->node_ptr_1; } static void set_next(const node_ptr & n, const node_ptr & next) { n->node_ptr_1 = next; } - static const node_ptr &get_previous(const const_node_ptr & n) + static node_ptr get_previous(const const_node_ptr & n) { return n->node_ptr_2; } static void set_previous(const node_ptr & n, const node_ptr & prev) @@ -64,7 +68,7 @@ struct any_slist_node_traits typedef typename node::node_ptr node_ptr; typedef typename node::const_node_ptr const_node_ptr; - static const node_ptr &get_next(const const_node_ptr & n) + static node_ptr get_next(const const_node_ptr & n) { return n->node_ptr_1; } static void set_next(const node_ptr & n, const node_ptr & next) @@ -84,7 +88,7 @@ struct any_unordered_node_traits static const bool store_hash = true; static const bool optimize_multikey = true; - static const node_ptr &get_next(const const_node_ptr & n) + static node_ptr get_next(const const_node_ptr & n) { return n->node_ptr_1; } static void set_next(const node_ptr & n, const node_ptr & next) @@ -113,19 +117,19 @@ struct any_rbtree_node_traits typedef std::size_t color; - static const node_ptr &get_parent(const const_node_ptr & n) + static node_ptr get_parent(const const_node_ptr & n) { return n->node_ptr_1; } static void set_parent(const node_ptr & n, const node_ptr & p) { n->node_ptr_1 = p; } - static const node_ptr &get_left(const const_node_ptr & n) + static node_ptr get_left(const const_node_ptr & n) { return n->node_ptr_2; } static void set_left(const node_ptr & n, const node_ptr & l) { n->node_ptr_2 = l; } - static const node_ptr &get_right(const const_node_ptr & n) + static node_ptr get_right(const const_node_ptr & n) { return n->node_ptr_3; } static void set_right(const node_ptr & n, const node_ptr & r) @@ -154,19 +158,19 @@ struct any_avltree_node_traits typedef std::size_t balance; - static const node_ptr &get_parent(const const_node_ptr & n) + static node_ptr get_parent(const const_node_ptr & n) { return n->node_ptr_1; } static void set_parent(const node_ptr & n, const node_ptr & p) { n->node_ptr_1 = p; } - static const node_ptr &get_left(const const_node_ptr & n) + static node_ptr get_left(const const_node_ptr & n) { return n->node_ptr_2; } static void set_left(const node_ptr & n, const node_ptr & l) { n->node_ptr_2 = l; } - static const node_ptr &get_right(const const_node_ptr & n) + static node_ptr get_right(const const_node_ptr & n) { return n->node_ptr_3; } static void set_right(const node_ptr & n, const node_ptr & r) @@ -196,19 +200,19 @@ struct any_tree_node_traits typedef typename node::node_ptr node_ptr; typedef typename node::const_node_ptr const_node_ptr; - static const node_ptr &get_parent(const const_node_ptr & n) + static node_ptr get_parent(const const_node_ptr & n) { return n->node_ptr_1; } static void set_parent(const node_ptr & n, const node_ptr & p) { n->node_ptr_1 = p; } - static const node_ptr &get_left(const const_node_ptr & n) + static node_ptr get_left(const const_node_ptr & n) { return n->node_ptr_2; } static void set_left(const node_ptr & n, const node_ptr & l) { n->node_ptr_2 = l; } - static const node_ptr &get_right(const const_node_ptr & n) + static node_ptr get_right(const const_node_ptr & n) { return n->node_ptr_3; } static void set_right(const node_ptr & n, const node_ptr & r) diff --git a/boost/intrusive/detail/array_initializer.hpp b/boost/intrusive/detail/array_initializer.hpp index b2072a872d..126a253afb 100644 --- a/boost/intrusive/detail/array_initializer.hpp +++ b/boost/intrusive/detail/array_initializer.hpp @@ -13,10 +13,15 @@ #ifndef BOOST_INTRUSIVE_DETAIL_ARRAY_INITIALIZER_HPP #define BOOST_INTRUSIVE_DETAIL_ARRAY_INITIALIZER_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif +#include <boost/config.hpp> #include <boost/core/no_exceptions_support.hpp> namespace boost { @@ -31,7 +36,7 @@ union max_align int int_; long long_; #ifdef BOOST_HAS_LONG_LONG - long long long_long_; + ::boost::long_long_type long_long_; #endif float float_; double double_; diff --git a/boost/intrusive/detail/assert.hpp b/boost/intrusive/detail/assert.hpp index d75d225ac4..7199eb240c 100644 --- a/boost/intrusive/detail/assert.hpp +++ b/boost/intrusive/detail/assert.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_ASSERT_HPP #define BOOST_INTRUSIVE_DETAIL_ASSERT_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) #pragma once #endif diff --git a/boost/intrusive/detail/avltree_node.hpp b/boost/intrusive/detail/avltree_node.hpp index 522806a89e..22b8fd1219 100644 --- a/boost/intrusive/detail/avltree_node.hpp +++ b/boost/intrusive/detail/avltree_node.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_AVLTREE_NODE_HPP #define BOOST_INTRUSIVE_AVLTREE_NODE_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/bstree_algorithms_base.hpp b/boost/intrusive/detail/bstree_algorithms_base.hpp new file mode 100644 index 0000000000..ed28a430ea --- /dev/null +++ b/boost/intrusive/detail/bstree_algorithms_base.hpp @@ -0,0 +1,184 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2014-2014 +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/libs/intrusive for documentation. +// +///////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP +#define BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include <boost/intrusive/detail/uncast.hpp> + +namespace boost { +namespace intrusive { + +template<class NodeTraits> +class bstree_algorithms_base +{ + public: + typedef typename NodeTraits::node node; + typedef NodeTraits node_traits; + typedef typename NodeTraits::node_ptr node_ptr; + typedef typename NodeTraits::const_node_ptr const_node_ptr; + + //! <b>Requires</b>: 'node' is a node from the tree except the header. + //! + //! <b>Effects</b>: Returns the next node of the tree. + //! + //! <b>Complexity</b>: Average constant time. + //! + //! <b>Throws</b>: Nothing. + static node_ptr next_node(const node_ptr & node) + { + node_ptr const n_right(NodeTraits::get_right(node)); + if(n_right){ + return minimum(n_right); + } + else { + node_ptr n(node); + node_ptr p(NodeTraits::get_parent(n)); + while(n == NodeTraits::get_right(p)){ + n = p; + p = NodeTraits::get_parent(p); + } + return NodeTraits::get_right(n) != p ? p : n; + } + } + + //! <b>Requires</b>: 'node' is a node from the tree except the leftmost node. + //! + //! <b>Effects</b>: Returns the previous node of the tree. + //! + //! <b>Complexity</b>: Average constant time. + //! + //! <b>Throws</b>: Nothing. + static node_ptr prev_node(const node_ptr & node) + { + if(is_header(node)){ + return NodeTraits::get_right(node); + //return maximum(NodeTraits::get_parent(node)); + } + else if(NodeTraits::get_left(node)){ + return maximum(NodeTraits::get_left(node)); + } + else { + node_ptr p(node); + node_ptr x = NodeTraits::get_parent(p); + while(p == NodeTraits::get_left(x)){ + p = x; + x = NodeTraits::get_parent(x); + } + return x; + } + } + + //! <b>Requires</b>: 'node' is a node of a tree but not the header. + //! + //! <b>Effects</b>: Returns the minimum node of the subtree starting at p. + //! + //! <b>Complexity</b>: Logarithmic to the size of the subtree. + //! + //! <b>Throws</b>: Nothing. + static node_ptr minimum(node_ptr node) + { + for(node_ptr p_left = NodeTraits::get_left(node) + ;p_left + ;p_left = NodeTraits::get_left(node)){ + node = p_left; + } + return node; + } + + //! <b>Requires</b>: 'node' is a node of a tree but not the header. + //! + //! <b>Effects</b>: Returns the maximum node of the subtree starting at p. + //! + //! <b>Complexity</b>: Logarithmic to the size of the subtree. + //! + //! <b>Throws</b>: Nothing. + static node_ptr maximum(node_ptr node) + { + for(node_ptr p_right = NodeTraits::get_right(node) + ;p_right + ;p_right = NodeTraits::get_right(node)){ + node = p_right; + } + return node; + } + + //! <b>Requires</b>: p is a node of a tree. + //! + //! <b>Effects</b>: Returns true if p is the header of the tree. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Throws</b>: Nothing. + static bool is_header(const const_node_ptr & p) + { + node_ptr p_left (NodeTraits::get_left(p)); + node_ptr p_right(NodeTraits::get_right(p)); + if(!NodeTraits::get_parent(p) || //Header condition when empty tree + (p_left && p_right && //Header always has leftmost and rightmost + (p_left == p_right || //Header condition when only node + (NodeTraits::get_parent(p_left) != p || + NodeTraits::get_parent(p_right) != p )) + //When tree size > 1 headers can't be leftmost's + //and rightmost's parent + )){ + return true; + } + return false; + } + + //! <b>Requires</b>: 'node' is a node of the tree or a header node. + //! + //! <b>Effects</b>: Returns the header of the tree. + //! + //! <b>Complexity</b>: Logarithmic. + //! + //! <b>Throws</b>: Nothing. + static node_ptr get_header(const const_node_ptr & node) + { + node_ptr n(detail::uncast(node)); + node_ptr p(NodeTraits::get_parent(node)); + //If p is null, then n is the header of an empty tree + if(p){ + //Non-empty tree, check if n is neither root nor header + node_ptr pp(NodeTraits::get_parent(p)); + //If granparent is not equal to n, then n is neither root nor header, + //the try the fast path + if(n != pp){ + do{ + n = p; + p = pp; + pp = NodeTraits::get_parent(pp); + }while(n != pp); + n = p; + } + //Check if n is root or header when size() > 0 + else if(!bstree_algorithms_base::is_header(n)){ + n = p; + } + } + return n; + } +}; + +} //namespace intrusive +} //namespace boost + +#endif //BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP diff --git a/boost/intrusive/detail/common_slist_algorithms.hpp b/boost/intrusive/detail/common_slist_algorithms.hpp index 4c7f1a11e0..deaea7c97b 100644 --- a/boost/intrusive/detail/common_slist_algorithms.hpp +++ b/boost/intrusive/detail/common_slist_algorithms.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP #define BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -143,7 +147,7 @@ class common_slist_algorithms } BOOST_CATCH(...){ node_traits::set_next(last_to_remove, new_f); - throw; + BOOST_RETHROW; } BOOST_CATCH_END node_traits::set_next(last_to_remove, new_f); diff --git a/boost/intrusive/detail/default_header_holder.hpp b/boost/intrusive/detail/default_header_holder.hpp index c471691640..d10109b8c9 100644 --- a/boost/intrusive/detail/default_header_holder.hpp +++ b/boost/intrusive/detail/default_header_holder.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_DEFAULT_HEADER_HOLDER_HPP #define BOOST_INTRUSIVE_DETAIL_DEFAULT_HEADER_HOLDER_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -28,34 +32,34 @@ namespace detail { template < typename NodeTraits > struct default_header_holder : public NodeTraits::node { - typedef NodeTraits 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 NodeTraits 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; - default_header_holder() : node() {} + default_header_holder() : node() {} - const_node_ptr get_node() const - { return pointer_traits< const_node_ptr >::pointer_to(*static_cast< const node* >(this)); } + const_node_ptr get_node() const + { return pointer_traits< const_node_ptr >::pointer_to(*static_cast< const node* >(this)); } - node_ptr get_node() - { return pointer_traits< node_ptr >::pointer_to(*static_cast< node* >(this)); } + node_ptr get_node() + { return pointer_traits< node_ptr >::pointer_to(*static_cast< node* >(this)); } - // (unsafe) downcast used to implement container-from-iterator - static default_header_holder* get_holder(const node_ptr &p) - { return static_cast< default_header_holder* >(boost::intrusive::detail::to_raw_pointer(p)); } + // (unsafe) downcast used to implement container-from-iterator + static default_header_holder* get_holder(const node_ptr &p) + { return static_cast< default_header_holder* >(boost::intrusive::detail::to_raw_pointer(p)); } }; // type function producing the header node holder template < typename Value_Traits, typename HeaderHolder > struct get_header_holder_type { - typedef HeaderHolder type; + typedef HeaderHolder type; }; template < typename Value_Traits > struct get_header_holder_type< Value_Traits, void > { - typedef default_header_holder< typename Value_Traits::node_traits > type; + typedef default_header_holder< typename Value_Traits::node_traits > type; }; } //namespace detail diff --git a/boost/intrusive/detail/ebo_functor_holder.hpp b/boost/intrusive/detail/ebo_functor_holder.hpp index d2e8107b67..e8e73ff62a 100644 --- a/boost/intrusive/detail/ebo_functor_holder.hpp +++ b/boost/intrusive/detail/ebo_functor_holder.hpp @@ -14,11 +14,13 @@ #ifndef BOOST_INTRUSIVE_DETAIL_EBO_HOLDER_HPP #define BOOST_INTRUSIVE_DETAIL_EBO_HOLDER_HPP -#if defined(_MSC_VER) -# pragma once +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> #endif -#include <boost/config.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -181,7 +183,7 @@ class ebo_functor_holder_impl<T, false> public: ebo_functor_holder_impl() {} - ebo_functor_holder_impl(const T& t) + explicit ebo_functor_holder_impl(const T& t) : T(t) {} template<class Arg1, class Arg2> @@ -202,7 +204,7 @@ class ebo_functor_holder public: ebo_functor_holder(){} - ebo_functor_holder(const T& t) + explicit ebo_functor_holder(const T& t) : super(t) {} diff --git a/boost/intrusive/detail/empty_node_checker.hpp b/boost/intrusive/detail/empty_node_checker.hpp index 33d78a34ba..16aa5600e7 100644 --- a/boost/intrusive/detail/empty_node_checker.hpp +++ b/boost/intrusive/detail/empty_node_checker.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_EMPTY_NODE_CHECKER_HPP #define BOOST_INTRUSIVE_DETAIL_EMPTY_NODE_CHECKER_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/equal_to_value.hpp b/boost/intrusive/detail/equal_to_value.hpp index 3ffd1c26cf..c341f488e9 100644 --- a/boost/intrusive/detail/equal_to_value.hpp +++ b/boost/intrusive/detail/equal_to_value.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_EQUAL_TO_VALUE_HPP #define BOOST_INTRUSIVE_DETAIL_EQUAL_TO_VALUE_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/exception_disposer.hpp b/boost/intrusive/detail/exception_disposer.hpp index 1226f5e525..a10d63a75d 100644 --- a/boost/intrusive/detail/exception_disposer.hpp +++ b/boost/intrusive/detail/exception_disposer.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_EXCEPTION_DISPOSER_HPP #define BOOST_INTRUSIVE_DETAIL_EXCEPTION_DISPOSER_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/function_detector.hpp b/boost/intrusive/detail/function_detector.hpp index f72865df9b..5ecaeaf073 100644 --- a/boost/intrusive/detail/function_detector.hpp +++ b/boost/intrusive/detail/function_detector.hpp @@ -22,7 +22,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_FUNCTION_DETECTOR_HPP #define BOOST_INTRUSIVE_DETAIL_FUNCTION_DETECTOR_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/generic_hook.hpp b/boost/intrusive/detail/generic_hook.hpp index c5af081d65..b57a12b458 100644 --- a/boost/intrusive/detail/generic_hook.hpp +++ b/boost/intrusive/detail/generic_hook.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_GENERIC_HOOK_HPP #define BOOST_INTRUSIVE_GENERIC_HOOK_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -134,13 +138,13 @@ class generic_hook , typename NodeAlgorithms::node , node_holder<typename NodeAlgorithms::node, Tag, BaseHookType> >::type - //If this is the a default-tagged base hook derive from a class that + //If this is the a default-tagged base hook derive from a class that //will define an special internal typedef. Containers will be able to detect this //special typedef and obtain generic_hook's internal types in order to deduce //value_traits for this hook. , public hook_tags_definer < generic_hook<NodeAlgorithms, Tag, LinkMode, BaseHookType> - , detail::is_same<Tag, default_tag>::value*BaseHookType> + , detail::is_same<Tag, dft_tag>::value*BaseHookType> /// @endcond { /// @cond diff --git a/boost/intrusive/detail/get_value_traits.hpp b/boost/intrusive/detail/get_value_traits.hpp index 6f5a9e3f04..686e059583 100644 --- a/boost/intrusive/detail/get_value_traits.hpp +++ b/boost/intrusive/detail/get_value_traits.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_GET_VALUE_TRAITS_HPP #define BOOST_INTRUSIVE_DETAIL_GET_VALUE_TRAITS_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/has_member_function_callable_with.hpp b/boost/intrusive/detail/has_member_function_callable_with.hpp index ca96f15a19..30bef56c2b 100644 --- a/boost/intrusive/detail/has_member_function_callable_with.hpp +++ b/boost/intrusive/detail/has_member_function_callable_with.hpp @@ -1,372 +1,331 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2011-2014. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2014-2014. Distributed under the Boost // Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // -// See http://www.boost.org/libs/intrusive for documentation. +// See http://www.boost.org/libs/container for documentation. // ////////////////////////////////////////////////////////////////////////////// -// sample.h +#ifndef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_CALLABLE_WITH_HPP +#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_CALLABLE_WITH_HPP -#if !defined(BOOST_PP_IS_ITERATING) +//Mark that we don't support 0 arg calls due to compiler ICE in GCC 3.4/4.0/4.1 and +//wrong SFINAE for GCC 4.2/4.3 +#if defined(__GNUC__) && !defined(__clang__) && ((__GNUC__*100 + __GNUC_MINOR__*10) >= 340) && ((__GNUC__*100 + __GNUC_MINOR__*10) <= 430) + #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED +#elif defined(BOOST_INTEL) && (BOOST_INTEL < 1200 ) + #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED +#endif +#include <cstddef> +#include <boost/move/utility_core.hpp> +#include <boost/move/detail/fwd_macros.hpp> - #ifndef BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_DETAILS_INCLUDED - #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_DETAILS_INCLUDED +namespace boost_intrusive_hmfcw { - #include <boost/intrusive/detail/preprocessor.hpp> - #include <boost/intrusive/detail/mpl.hpp> - #include <boost/move/utility_core.hpp> +typedef char yes_type; +struct no_type{ char dummy[2]; }; +#if defined(BOOST_NO_CXX11_DECLTYPE) - //Mark that we don't support 0 arg calls due to compiler ICE in GCC 3.4/4.0/4.1 and - //wrong SFINAE for GCC 4.2/4.3 - #if defined(__GNUC__) && !defined(__clang__) && ((__GNUC__*100 + __GNUC_MINOR__*10) >= 340) && ((__GNUC__*100 + __GNUC_MINOR__*10) <= 430) - #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED - #elif defined(BOOST_INTEL) && (BOOST_INTEL < 1200 ) - #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED - #endif +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - namespace boost_intrusive_has_member_function_callable_with { +template<class T> +struct make_dontcare +{ + typedef dont_care type; +}; - struct dont_care - { - dont_care(...); - }; +#endif - template<class T> - struct make_dontcare - { - typedef boost_intrusive_has_member_function_callable_with::dont_care type; - }; +struct dont_care +{ + dont_care(...); +}; - struct private_type - { - static private_type p; - private_type const &operator,(int) const; - }; +struct private_type +{ + static private_type p; + private_type const &operator,(int) const; +}; - typedef char yes_type; // sizeof(yes_type) == 1 - struct no_type{ char dummy[2]; }; // sizeof(no_type) == 2 +template<typename T> +no_type is_private_type(T const &); +yes_type is_private_type(private_type const &); - template<typename T> - no_type is_private_type(T const &); - yes_type is_private_type(private_type const &); +#endif //#if defined(BOOST_NO_CXX11_DECLTYPE) - } //boost_intrusive_has_member_function_callable_with +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_SINGLE_ITERATION - #endif +template<typename T> struct remove_cv { typedef T type; }; +template<typename T> struct remove_cv<const T> { typedef T type; }; +template<typename T> struct remove_cv<const volatile T> { typedef T type; }; +template<typename T> struct remove_cv<volatile T> { typedef T type; }; + +#endif + +} //namespace boost_intrusive_hmfcw { + +#endif //BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_CALLABLE_WITH_HPP + +#ifndef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME + #error "You MUST define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME before including this header!" +#endif + +#ifndef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN + #error "You MUST define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN before including this header!" +#endif - #endif //BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_DETAILS_INCLUDED +#ifndef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX + #error "You MUST define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX before including this header!" +#endif -#else //!BOOST_PP_IS_ITERATING +#if BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX < BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN + #error "BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX value MUST be greater or equal than BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN!" +#endif - #ifndef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME - #error "BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME not defined!" - #endif +#if BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX == 0 + #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_COMMA_IF +#else + #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_COMMA_IF , +#endif - #ifndef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN - #error "BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN not defined!" - #endif +#ifndef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG + #error "BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG not defined!" +#endif - #ifndef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END +#ifndef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END #error "BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END not defined!" - #endif +#endif + +BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG + +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && !defined(BOOST_NO_CXX11_DECLTYPE) + //With decltype and variadic templaes, things are pretty easy + template<typename Fun, class ...Args> + struct BOOST_MOVE_CAT(has_member_function_callable_with_,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + { + template<class U> + static decltype(boost::move_detail::declval<U>(). + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(::boost::move_detail::declval<Args>()...) + , boost_intrusive_hmfcw::yes_type()) Test(U* f); + template<class U> + static boost_intrusive_hmfcw::no_type Test(...); + static const bool value = sizeof(Test<Fun>((Fun*)0)) == sizeof(boost_intrusive_hmfcw::yes_type); + }; + +#else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_NO_CXX11_DECLTYPE) + + ///////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////// + // + // has_member_function_callable_with_impl_XXX + // declaration, special case and 0 arg specializaton + // + ///////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////// - #if BOOST_PP_ITERATION_START() > BOOST_PP_ITERATION_FINISH() - #error "BOOST_PP_ITERATION_START() must be <= BOOST_PP_ITERATION_FINISH()" - #endif + #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + ///////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////// + // + // has_member_function_callable_with_impl_XXX for 1 to N arguments + // + ///////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////// + + //defined(BOOST_NO_CXX11_DECLTYPE) must be true + template<class Fun, class ...DontCares> + struct FunWrapTmpl : Fun + { + using Fun::BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME; + boost_intrusive_hmfcw::private_type BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(DontCares...) const; + }; - #if BOOST_PP_ITERATION() == BOOST_PP_ITERATION_START() + template<typename Fun, class ...Args> + struct BOOST_MOVE_CAT(has_member_function_callable_with_,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, Args...> + { + typedef FunWrapTmpl<typename boost_intrusive_hmfcw::make_dontcare<Args>::type...> FunWrap; + + static bool const value = (sizeof(boost_intrusive_hmfcw::no_type) == + sizeof(boost_intrusive_hmfcw::is_private_type + ( (::boost::move_detail::declval< FunWrap<Fun> >(). + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(::boost::move_detail::declval<Args>()...), 0) ) + ) + ); + }; + #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN + //Preprocessor must be used to generate specializations instead of variadic templates template <typename Type> - class BOOST_PP_CAT(has_member_function_named_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + class BOOST_MOVE_CAT(has_member_function_named_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) { struct BaseMixin { void BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(); }; - struct Base : public ::boost::intrusive::detail::remove_cv<Type>::type, public BaseMixin { Base(); }; + struct Base : public boost_intrusive_hmfcw::remove_cv<Type>::type, public BaseMixin {}; template <typename T, T t> class Helper{}; template <typename U> - static boost_intrusive_has_member_function_callable_with::no_type deduce + static boost_intrusive_hmfcw::no_type deduce (U*, Helper<void (BaseMixin::*)(), &U::BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME>* = 0); - static boost_intrusive_has_member_function_callable_with::yes_type deduce(...); + static boost_intrusive_hmfcw::yes_type deduce(...); public: - static const bool value = - sizeof(boost_intrusive_has_member_function_callable_with::yes_type) == sizeof(deduce((Base*)(0))); + static const bool value = sizeof(boost_intrusive_hmfcw::yes_type) == sizeof(deduce((Base*)0)); }; - #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - template<typename Fun, bool HasFunc - BOOST_PP_ENUM_TRAILING(BOOST_PP_ITERATION_FINISH(), BOOST_INTRUSIVE_PP_TEMPLATE_PARAM_VOID_DEFAULT, _)> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME), _impl); - //! - - template<typename Fun BOOST_PP_ENUM_TRAILING_PARAMS(BOOST_PP_ITERATION_FINISH(), class P)> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME), _impl) - <Fun, false BOOST_PP_ENUM_TRAILING_PARAMS(BOOST_PP_ITERATION_FINISH(), P)> - { - static const bool value = false; - }; - //! - - #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - template<typename Fun, bool HasFunc, class ...Args> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl); - - template<typename Fun, class ...Args> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, false, Args...> - { - static const bool value = false; - }; - - #ifdef BOOST_NO_CXX11_DECLTYPE - - //Special case for 0 args - template< class F - , std::size_t N = - sizeof((boost::move_detail::declval<F>(). - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME (), 0))> - struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) - { - boost_intrusive_has_member_function_callable_with::yes_type dummy; - BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); - }; - - //For buggy compilers like MSVC 7.1+ ((F*)0)->func() does not - //SFINAE-out the zeroarg_checker_ instantiation but sizeof yields to 0. - template<class F> - struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<F, 0> - { - boost_intrusive_has_member_function_callable_with::no_type dummy; - BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); - }; - - #endif //#ifdef BOOST_NO_CXX11_DECLTYPE - - template<typename Fun> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, true> - { - #ifndef BOOST_NO_CXX11_DECLTYPE - template<class U, class V = decltype(boost::move_detail::declval<U>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME()) > - static boost_intrusive_has_member_function_callable_with::yes_type Test(U*); - #else - template<class U> - static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) - <U> Test(BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*); - #endif - - template <class U> - static boost_intrusive_has_member_function_callable_with::no_type Test(...); - - static const bool value = sizeof(Test< Fun >(0)) - == sizeof(boost_intrusive_has_member_function_callable_with::yes_type); - }; - - template<typename Fun, class ...Args> - struct BOOST_PP_CAT( BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME), _impl) - <Fun, true , Args...> - { - - template<class ...DontCares> - struct FunWrapTmpl : Fun - { - FunWrapTmpl(); - using Fun::BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME; - - boost_intrusive_has_member_function_callable_with::private_type - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME - ( DontCares...) const; - }; - - typedef FunWrapTmpl<typename boost_intrusive_has_member_function_callable_with::make_dontcare<Args>::type...> FunWrap; - - static bool const value = (sizeof(boost_intrusive_has_member_function_callable_with::no_type) == - sizeof(boost_intrusive_has_member_function_callable_with::is_private_type - ( (::boost::move_detail::declval< FunWrap >(). - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME - ( ::boost::move_detail::declval<Args>()... ), 0) ) - ) - ); - }; + ///////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////// + // + // has_member_function_callable_with_impl_XXX specializations + // + ///////////////////////////////////////////////////////// - template<typename Fun, class ...Args> - struct BOOST_PP_CAT( has_member_function_callable_with_ - , BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) - : public BOOST_PP_CAT( BOOST_PP_CAT(has_member_function_callable_with_ - , BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - < Fun - , BOOST_PP_CAT( has_member_function_named_ - , BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME )<Fun>::value - , Args... > - {}; + template<typename Fun, bool HasFunc BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_COMMA_IF BOOST_MOVE_CAT(BOOST_MOVE_CLASSDFLT,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX)> + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME); - #endif //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END - - #endif //BOOST_PP_ITERATION() == BOOST_PP_ITERATION_START() - - #if BOOST_PP_ITERATION() == 0 - - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN - - #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - #if !defined(_MSC_VER) || (_MSC_VER < 1600) - - #if defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) - - template<typename Fun> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> - { - //Mark that we don't support 0 arg calls due to compiler ICE in GCC 3.4/4.0/4.1 and - //wrong SFINAE for GCC 4.2/4.3 - static const bool value = true; - }; - - #else //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) - - //Special case for 0 args - template< class F - , std::size_t N = - sizeof((boost::move_detail::declval<F>(). - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME (), 0))> - struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) - { - boost_intrusive_has_member_function_callable_with::yes_type dummy; - BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); - }; - - //For buggy compilers like MSVC 7.1+ ((F*)0)->func() does not - //SFINAE-out the zeroarg_checker_ instantiation but sizeof yields to 0. - template<class F> - struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<F, 0> - { - boost_intrusive_has_member_function_callable_with::no_type dummy; - BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); - }; - - template<typename Fun> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> - { - template<class U> - static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U> - Test(BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*); - - template <class U> - static boost_intrusive_has_member_function_callable_with::no_type Test(...); + //No BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME member specialization + template<typename Fun BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_COMMA_IF BOOST_MOVE_CAT(BOOST_MOVE_CLASS,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX)> + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + <Fun, false BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_COMMA_IF BOOST_MOVE_CAT(BOOST_MOVE_TARG,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX)> + { + static const bool value = false; + }; - static const bool value = sizeof(Test< Fun >(0)) - == sizeof(boost_intrusive_has_member_function_callable_with::yes_type); - }; - #endif //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) + #if BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN == 0 + //0 arg specialization when BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME is present + #if !defined(BOOST_NO_CXX11_DECLTYPE) - #else //#if !defined(_MSC_VER) || (_MSC_VER < 1600) template<typename Fun> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true> { template<class U> - static decltype( boost::move_detail::declval<U>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME() - , boost_intrusive_has_member_function_callable_with::yes_type()) - Test(U*); + static decltype(boost::move_detail::declval<U>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME() + , boost_intrusive_hmfcw::yes_type()) Test(U* f); template<class U> - static boost_intrusive_has_member_function_callable_with::no_type Test(...); - - static const bool value = sizeof(Test<Fun>(0)) - == sizeof(boost_intrusive_has_member_function_callable_with::yes_type); + static boost_intrusive_hmfcw::no_type Test(...); + static const bool value = sizeof(Test<Fun>((Fun*)0)) == sizeof(boost_intrusive_hmfcw::yes_type); }; - #endif //#if !defined(_MSC_VER) || (_MSC_VER < 1600) - - #else //#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - #endif //#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + #else //defined(BOOST_NO_CXX11_DECLTYPE) - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END + #if !defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) - #else //BOOST_PP_ITERATION() == 0 + template<class F, std::size_t N = sizeof(boost::move_detail::declval<F>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(), 0)> + struct BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + { boost_intrusive_hmfcw::yes_type dummy[N ? 1 : 2]; }; - #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN - - template<typename Fun BOOST_PP_ENUM_TRAILING_PARAMS(BOOST_PP_ITERATION(), class P)> - struct BOOST_PP_CAT( BOOST_PP_CAT(has_member_function_callable_with_ - , BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, true - BOOST_PP_ENUM_TRAILING_PARAMS(BOOST_PP_ITERATION(), P) - BOOST_PP_ENUM_TRAILING( BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()) - , BOOST_INTRUSIVE_PP_IDENTITY - , void)> - { - struct FunWrap : Fun + template<typename Fun> + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true> { - FunWrap(); - - using Fun::BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME; - boost_intrusive_has_member_function_callable_with::private_type - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME - ( BOOST_PP_ENUM(BOOST_PP_ITERATION() - , BOOST_INTRUSIVE_PP_IDENTITY - , boost_intrusive_has_member_function_callable_with::dont_care)) const; + template<class U> static BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U> + Test(BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*); + template<class U> static boost_intrusive_hmfcw::no_type Test(...); + static const bool value = sizeof(Test< Fun >(0)) == sizeof(boost_intrusive_hmfcw::yes_type); }; - static bool const value = - (sizeof(boost_intrusive_has_member_function_callable_with::no_type) == - sizeof(boost_intrusive_has_member_function_callable_with::is_private_type - ( (boost::move_detail::declval<FunWrap>(). - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME - ( BOOST_PP_ENUM( BOOST_PP_ITERATION(), BOOST_INTRUSIVE_PP_DECLVAL, _) ), 0 - ) - ) - ) - ); - }; - - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END - #endif //#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - #endif //BOOST_PP_ITERATION() == 0 - - #if BOOST_PP_ITERATION() == BOOST_PP_ITERATION_FINISH() - - #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN - - template<typename Fun - BOOST_PP_ENUM_TRAILING(BOOST_PP_ITERATION_FINISH(), BOOST_INTRUSIVE_PP_TEMPLATE_PARAM_VOID_DEFAULT, _)> - struct BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) - : public BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME), _impl) - <Fun, BOOST_PP_CAT(has_member_function_named_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun>::value - BOOST_PP_ENUM_TRAILING_PARAMS(BOOST_PP_ITERATION_FINISH(), P) > - {}; - - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END - - #endif //#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - #undef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME - #undef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN - #undef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END - - #endif //#if BOOST_PP_ITERATION() == BOOST_PP_ITERATION_FINISH() + #else //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) -#endif //!BOOST_PP_IS_ITERATING + template<typename Fun> + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true> + {//GCC [3.4-4.3) gives ICE when instantiating the 0 arg version so it is not supported. + static const bool value = true; + }; + + #endif//!defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) + #endif //!defined(BOOST_NO_CXX11_DECLTYPE) + #endif //#if BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN == 0 + + #if BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX > 0 + //1 to N arg specialization when BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME is present + #if defined(BOOST_NO_CXX11_DECLTYPE) + #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_ITERATION(N)\ + template<class Fun> struct BOOST_MOVE_CAT(FunWrap##N, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) : Fun\ + {\ + using Fun::BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME;\ + boost_intrusive_hmfcw::private_type BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME\ + (BOOST_MOVE_REPEAT##N(boost_intrusive_hmfcw::dont_care)) const;\ + };\ + \ + template<typename Fun, BOOST_MOVE_CLASS##N>\ + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true, BOOST_MOVE_TARG##N>\ + {\ + static bool const value = (sizeof(boost_intrusive_hmfcw::no_type) == sizeof(boost_intrusive_hmfcw::is_private_type\ + ( (::boost::move_detail::declval\ + < BOOST_MOVE_CAT(FunWrap##N, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun> >().\ + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(BOOST_MOVE_DECLVAL##N), 0) )\ + )\ + );\ + };\ + // + #else + #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_ITERATION(N)\ + template<typename Fun, BOOST_MOVE_CLASS##N>\ + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)\ + <Fun, true, BOOST_MOVE_TARG##N>\ + {\ + template<class U>\ + static decltype(boost::move_detail::declval<U>().\ + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(BOOST_MOVE_DECLVAL##N)\ + , boost_intrusive_hmfcw::yes_type()) Test(U* f);\ + template<class U>\ + static boost_intrusive_hmfcw::no_type Test(...);\ + static const bool value = sizeof(Test<Fun>((Fun*)0)) == sizeof(boost_intrusive_hmfcw::yes_type);\ + };\ + // + #endif + //////////////////////////////////// + // Build and invoke BOOST_MOVE_ITERATE_NTOM macrofunction, note that N has to be at least 1 + //////////////////////////////////// + #if BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN == 0 + #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_ITERATE_MIN 1 + #else + #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_ITERATE_MIN BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN + #endif + BOOST_MOVE_CAT + (BOOST_MOVE_CAT(BOOST_MOVE_CAT(BOOST_MOVE_ITERATE_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_ITERATE_MIN), TO) + ,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX) + (BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_ITERATION) + #undef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_ITERATION + #undef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_ITERATE_MIN + //////////////////////////////////// + // End of BOOST_MOVE_ITERATE_NTOM + //////////////////////////////////// + #endif //BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX > 0 + + ///////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////// + // + // has_member_function_callable_with_FUNC + // + ///////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////// + + //Otherwise use the preprocessor + template<typename Fun BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_COMMA_IF BOOST_MOVE_CAT(BOOST_MOVE_CLASSDFLT,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX)> + struct BOOST_MOVE_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + : public BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + <Fun + , BOOST_MOVE_CAT(has_member_function_named_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun>::value + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_COMMA_IF BOOST_MOVE_CAT(BOOST_MOVE_TARG,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX)> + {}; + #endif //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) +#endif + +BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END + +//Undef local macros +#undef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_COMMA_IF + +//Undef user defined macros +#undef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME +#undef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN +#undef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX +#undef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG +#undef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END diff --git a/boost/intrusive/detail/hashtable_node.hpp b/boost/intrusive/detail/hashtable_node.hpp index 6449fa0dd2..923a3e1d38 100644 --- a/boost/intrusive/detail/hashtable_node.hpp +++ b/boost/intrusive/detail/hashtable_node.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_HASHTABLE_NODE_HPP #define BOOST_INTRUSIVE_HASHTABLE_NODE_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/hook_traits.hpp b/boost/intrusive/detail/hook_traits.hpp index c9c115b1de..71f342af06 100644 --- a/boost/intrusive/detail/hook_traits.hpp +++ b/boost/intrusive/detail/hook_traits.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_HOOK_TRAITS_HPP #define BOOST_INTRUSIVE_DETAIL_HOOK_TRAITS_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/iiterator.hpp b/boost/intrusive/detail/iiterator.hpp index 8378ead6ad..5c6721bd0e 100644 --- a/boost/intrusive/detail/iiterator.hpp +++ b/boost/intrusive/detail/iiterator.hpp @@ -13,71 +13,32 @@ #ifndef BOOST_INTRUSIVE_DETAIL_IITERATOR_HPP #define BOOST_INTRUSIVE_DETAIL_IITERATOR_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif +#include <boost/intrusive/detail/iterator.hpp> #include <boost/intrusive/pointer_traits.hpp> #include <boost/intrusive/detail/mpl.hpp> #include <boost/intrusive/detail/is_stateful_value_traits.hpp> -#include <boost/intrusive/detail/std_fwd.hpp> - -#include <cstddef> - namespace boost { namespace intrusive { -template<class Category, class T, class Distance, class Pointer, class Reference> -struct iterator -{ - typedef Category iterator_category; - typedef T value_type; - typedef Distance difference_type; - typedef Pointer pointer; - typedef Reference reference; -}; - -template<class Iterator> -struct iterator_traits -{ - typedef typename Iterator::difference_type difference_type; - typedef typename Iterator::value_type value_type; - typedef typename Iterator::pointer pointer; - typedef typename Iterator::reference reference; - typedef typename Iterator::iterator_category iterator_category; -}; - -template<class T> -struct iterator_traits<T*> -{ - typedef std::ptrdiff_t difference_type; - typedef T value_type; - typedef T* pointer; - typedef T& reference; - typedef std::random_access_iterator_tag iterator_category; -}; - -template<class T> -struct iterator_traits<const T*> -{ - typedef std::ptrdiff_t difference_type; - typedef T value_type; - typedef const T* pointer; - typedef const T& reference; - typedef std::random_access_iterator_tag iterator_category; -}; - template<class ValueTraits> struct value_traits_pointers { typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT (boost::intrusive::detail:: , ValueTraits, value_traits_ptr - , typename pointer_traits<typename ValueTraits::node_traits::node_ptr>::template + , typename boost::intrusive::pointer_traits<typename ValueTraits::node_traits::node_ptr>::template rebind_pointer<ValueTraits>::type) value_traits_ptr; - typedef typename pointer_traits<value_traits_ptr>::template + typedef typename boost::intrusive::pointer_traits<value_traits_ptr>::template rebind_pointer<ValueTraits const>::type const_value_traits_ptr; }; @@ -154,73 +115,6 @@ struct iiterator_members<NodePtr, StoredPointer, false> NodePtr nodeptr_; }; -namespace detail { - -template<class InputIt, class Distance> inline -void advance_impl(InputIt& it, Distance n, const std::input_iterator_tag&) -{ - while(n--) - ++it; -} - -template<class InputIt, class Distance> inline -void advance_impl(InputIt& it, Distance n, std::forward_iterator_tag &) -{ - while(n--) - ++it; -} - -template<class InputIt, class Distance> inline -void advance_impl(InputIt& it, Distance n, std::bidirectional_iterator_tag &) -{ - for (; 0 < n; --n) - ++it; - for (; n < 0; ++n) - --it; -} - -template<class InputIt, class Distance> -inline void advance_impl(InputIt& it, Distance n, const std::random_access_iterator_tag &) -{ - it += n; -} - -} //namespace detail - -template<class InputIt, class Distance> -inline void iterator_advance(InputIt& it, Distance n) -{ // increment iterator by offset, arbitrary iterators - boost::intrusive::detail::advance_impl(it, n, boost::intrusive::iterator_traits<InputIt>::iterator_category()); -} - -namespace detail{ - -template<class InputIt, class Distance, class Category> -inline void distance_impl(InputIt first, InputIt last, Distance& off, const Category &) -{ - while(first != last){ - ++off; - ++first; - } -} - -template<class InputIt, class Distance> inline -void distance_impl(InputIt first, InputIt last, Distance& off, const std::random_access_iterator_tag&) -{ - off += last - first; -} - -} //namespace detail - -template<class InputIt> inline -typename iterator_traits<InputIt>::difference_type iterator_distance(InputIt first, InputIt last) -{ - typename iterator_traits<InputIt>::difference_type off = 0; - boost::intrusive::detail::distance_impl(first, last, off, boost::intrusive::iterator_traits<InputIt>::iterator_category()); - return off; -} - - } //namespace intrusive } //namespace boost diff --git a/boost/intrusive/detail/is_stateful_value_traits.hpp b/boost/intrusive/detail/is_stateful_value_traits.hpp index da2260edf6..680b043aa8 100644 --- a/boost/intrusive/detail/is_stateful_value_traits.hpp +++ b/boost/intrusive/detail/is_stateful_value_traits.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_IS_STATEFUL_VALUE_TRAITS_HPP #define BOOST_INTRUSIVE_DETAIL_IS_STATEFUL_VALUE_TRAITS_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/iterator.hpp b/boost/intrusive/detail/iterator.hpp new file mode 100644 index 0000000000..fb6fb81976 --- /dev/null +++ b/boost/intrusive/detail/iterator.hpp @@ -0,0 +1,147 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2014-2014 +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/libs/intrusive for documentation. +// +///////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP +#define BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include <cstddef> +#include <boost/intrusive/detail/std_fwd.hpp> +#include <boost/move/detail/iterator_traits.hpp> +#include <boost/move/detail/meta_utils_core.hpp> + +namespace boost { +namespace intrusive { + +using boost::movelib::iterator_traits; + +//////////////////// +// iterator +//////////////////// +template<class Category, class T, class Distance, class Pointer = T*, class Reference = T&> +struct iterator +{ + typedef Category iterator_category; + typedef T value_type; + typedef Distance difference_type; + typedef Pointer pointer; + typedef Reference reference; +}; + +//////////////////////////////////////// +// iterator_[dis|en]able_if_tag +//////////////////////////////////////// +template<class I, class Tag, class R = void> +struct iterator_enable_if_tag + : ::boost::move_detail::enable_if_c + < ::boost::move_detail::is_same + < typename boost::intrusive::iterator_traits<I>::iterator_category + , Tag + >::value + , R> +{}; + +template<class I, class Tag, class R = void> +struct iterator_disable_if_tag + : ::boost::move_detail::enable_if_c + < !::boost::move_detail::is_same + < typename boost::intrusive::iterator_traits<I>::iterator_category + , Tag + >::value + , R> +{}; + +//////////////////////////////////////// +// iterator_[dis|en]able_if_tag_difference_type +//////////////////////////////////////// +template<class I, class Tag> +struct iterator_enable_if_tag_difference_type + : iterator_enable_if_tag<I, Tag, typename boost::intrusive::iterator_traits<I>::difference_type> +{}; + +template<class I, class Tag> +struct iterator_disable_if_tag_difference_type + : iterator_disable_if_tag<I, Tag, typename boost::intrusive::iterator_traits<I>::difference_type> +{}; + +//////////////////// +// advance +//////////////////// +template<class InputIt, class Distance> inline +typename iterator_enable_if_tag<InputIt, std::input_iterator_tag>::type + iterator_advance(InputIt& it, Distance n) +{ + while(n--) + ++it; +} + +template<class InputIt, class Distance> inline +typename iterator_enable_if_tag<InputIt, std::forward_iterator_tag>::type + iterator_advance(InputIt& it, Distance n) +{ + while(n--) + ++it; +} + +template<class InputIt, class Distance> inline +typename iterator_enable_if_tag<InputIt, std::bidirectional_iterator_tag>::type + iterator_advance(InputIt& it, Distance n) +{ + for (; 0 < n; --n) + ++it; + for (; n < 0; ++n) + --it; +} + +template<class InputIt, class Distance> inline +typename iterator_enable_if_tag<InputIt, std::random_access_iterator_tag>::type + iterator_advance(InputIt& it, Distance n) +{ + it += n; +} + +//////////////////// +// distance +//////////////////// +template<class InputIt> inline +typename iterator_disable_if_tag_difference_type + <InputIt, std::random_access_iterator_tag>::type + iterator_distance(InputIt first, InputIt last) +{ + typename iterator_traits<InputIt>::difference_type off = 0; + while(first != last){ + ++off; + ++first; + } + return off; +} + +template<class InputIt> inline +typename iterator_enable_if_tag_difference_type + <InputIt, std::random_access_iterator_tag>::type + iterator_distance(InputIt first, InputIt last) +{ + typename iterator_traits<InputIt>::difference_type off = last - first; + return off; +} + +} //namespace intrusive +} //namespace boost + +#endif //BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP diff --git a/boost/intrusive/detail/key_nodeptr_comp.hpp b/boost/intrusive/detail/key_nodeptr_comp.hpp index dfee8b9bfc..8c456634e5 100644 --- a/boost/intrusive/detail/key_nodeptr_comp.hpp +++ b/boost/intrusive/detail/key_nodeptr_comp.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_KEY_NODEPTR_COMP_HPP #define BOOST_INTRUSIVE_DETAIL_KEY_NODEPTR_COMP_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -26,7 +30,8 @@ namespace detail { template<class KeyValueCompare, class ValueTraits> struct key_nodeptr_comp - : private ebo_functor_holder<KeyValueCompare> + //Use public inheritance to avoid MSVC bugs with closures + : public ebo_functor_holder<KeyValueCompare> { typedef ValueTraits value_traits; typedef typename value_traits::value_type value_type; @@ -44,6 +49,7 @@ struct key_nodeptr_comp static const bool value = is_same<T, const_node_ptr>::value || is_same<T, node_ptr>::value; }; + //key_forward template<class T> const value_type & key_forward (const T &node, typename enable_if_c<is_node_ptr<T>::value>::type * = 0) const @@ -53,14 +59,23 @@ struct key_nodeptr_comp const T & key_forward(const T &key, typename enable_if_c<!is_node_ptr<T>::value>::type* = 0) const { return key; } + //operator() 1 arg + template<class KeyType> + bool operator()(const KeyType &key1) const + { return base_t::get()(this->key_forward(key1)); } + template<class KeyType> + bool operator()(const KeyType &key1) + { return base_t::get()(this->key_forward(key1)); } + + //operator() 2 arg template<class KeyType, class KeyType2> bool operator()(const KeyType &key1, const KeyType2 &key2) const { return base_t::get()(this->key_forward(key1), this->key_forward(key2)); } - template<class KeyType> - bool operator()(const KeyType &key1) const - { return base_t::get()(this->key_forward(key1)); } + template<class KeyType, class KeyType2> + bool operator()(const KeyType &key1, const KeyType2 &key2) + { return base_t::get()(this->key_forward(key1), this->key_forward(key2)); } const ValueTraits *const traits_; }; diff --git a/boost/intrusive/detail/list_iterator.hpp b/boost/intrusive/detail/list_iterator.hpp index efddfba3f1..77c9fa6097 100644 --- a/boost/intrusive/detail/list_iterator.hpp +++ b/boost/intrusive/detail/list_iterator.hpp @@ -14,7 +14,11 @@ #ifndef BOOST_INTRUSIVE_LIST_ITERATOR_HPP #define BOOST_INTRUSIVE_LIST_ITERATOR_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/list_node.hpp b/boost/intrusive/detail/list_node.hpp index ba97ece956..f740e545e8 100644 --- a/boost/intrusive/detail/list_node.hpp +++ b/boost/intrusive/detail/list_node.hpp @@ -14,7 +14,11 @@ #ifndef BOOST_INTRUSIVE_LIST_NODE_HPP #define BOOST_INTRUSIVE_LIST_NODE_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/math.hpp b/boost/intrusive/detail/math.hpp index f212ae743f..03000fceeb 100644 --- a/boost/intrusive/detail/math.hpp +++ b/boost/intrusive/detail/math.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_MATH_HPP #define BOOST_INTRUSIVE_DETAIL_MATH_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -84,9 +88,9 @@ namespace detail { #if defined(BOOST_HAS_LONG_LONG) template<> - struct builtin_clz_dispatch<unsigned long long> + struct builtin_clz_dispatch< ::boost::ulong_long_type > { - static unsigned long long call(unsigned long long n) + static ::boost::ulong_long_type call(::boost::ulong_long_type n) { return __builtin_clzll(n); } }; #endif @@ -154,7 +158,7 @@ namespace detail { inline std::size_t floor_log2 (std::size_t v, integer<std::size_t, 32>) { - static const int MultiplyDeBruijnBitPosition[32] = + static const int MultiplyDeBruijnBitPosition[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 diff --git a/boost/intrusive/detail/memory_util.hpp b/boost/intrusive/detail/memory_util.hpp deleted file mode 100644 index 18a5d3e7e2..0000000000 --- a/boost/intrusive/detail/memory_util.hpp +++ /dev/null @@ -1,92 +0,0 @@ -////////////////////////////////////////////////////////////////////////////// -// -// (C) Copyright Pablo Halpern 2009. Distributed under the Boost -// Software License, Version 1.0. (See accompanying file -// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -// -////////////////////////////////////////////////////////////////////////////// -// -// (C) Copyright Ion Gaztanaga 2011-2014. Distributed under the Boost -// Software License, Version 1.0. (See accompanying file -// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -// -// See http://www.boost.org/libs/intrusive for documentation. -// -////////////////////////////////////////////////////////////////////////////// - -#ifndef BOOST_INTRUSIVE_ALLOCATOR_MEMORY_UTIL_HPP -#define BOOST_INTRUSIVE_ALLOCATOR_MEMORY_UTIL_HPP - -#if defined(_MSC_VER) -# pragma once -#endif - -#include <boost/intrusive/detail/workaround.hpp> -#include <boost/intrusive/detail/mpl.hpp> -#include <boost/intrusive/detail/preprocessor.hpp> -#include <boost/preprocessor/iteration/iterate.hpp> - -namespace boost { -namespace intrusive { -namespace detail { - -template <typename T> -inline T* addressof(T& obj) -{ - return static_cast<T*> - (static_cast<void*> - (const_cast<char*> - (&reinterpret_cast<const char&>(obj)) - ) - ); -} - -template <typename T> -struct LowPriorityConversion -{ - // Convertible from T with user-defined-conversion rank. - LowPriorityConversion(const T&) { } -}; - -}}} //namespace boost::intrusive::detail - -#include <boost/intrusive/detail/has_member_function_callable_with.hpp> - -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME pointer_to -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN namespace boost { namespace intrusive { namespace detail { -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}} -#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) -#include BOOST_PP_ITERATE() - -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME static_cast_from -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN namespace boost { namespace intrusive { namespace detail { -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}} -#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) -#include BOOST_PP_ITERATE() - -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME const_cast_from -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN namespace boost { namespace intrusive { namespace detail { -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}} -#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) -#include BOOST_PP_ITERATE() - -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME dynamic_cast_from -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN namespace boost { namespace intrusive { namespace detail { -#define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}} -#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) -#include BOOST_PP_ITERATE() - -namespace boost { -namespace intrusive { -namespace detail { - -BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(element_type) -BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(difference_type) -BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(reference) -BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(value_traits_ptr) - -} //namespace detail { -} //namespace intrusive { -} //namespace boost { - -#endif // ! defined(BOOST_INTRUSIVE_ALLOCATOR_MEMORY_UTIL_HPP) diff --git a/boost/intrusive/detail/minimal_less_equal_header.hpp b/boost/intrusive/detail/minimal_less_equal_header.hpp new file mode 100644 index 0000000000..5e8a19debf --- /dev/null +++ b/boost/intrusive/detail/minimal_less_equal_header.hpp @@ -0,0 +1,30 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2014-2015 +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/libs/intrusive for documentation. +// +///////////////////////////////////////////////////////////////////////////// +#ifndef BOOST_INTRUSIVE_DETAIL_MINIMAL_LESS_EQUAL_HEADER_HPP +#define BOOST_INTRUSIVE_DETAIL_MINIMAL_LESS_EQUAL_HEADER_HPP +# +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif +# +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif +# +#//Try to avoid including <functional>, as it's quite big in C++11 +#if defined(BOOST_GNU_STDLIB) +# include <bits/stl_function.h> +#else +# include <functional> //Fallback +#endif +# +#endif //BOOST_INTRUSIVE_DETAIL_MINIMAL_LESS_EQUAL_HEADER_HPP diff --git a/boost/intrusive/detail/minimal_pair_header.hpp b/boost/intrusive/detail/minimal_pair_header.hpp new file mode 100644 index 0000000000..1358a08588 --- /dev/null +++ b/boost/intrusive/detail/minimal_pair_header.hpp @@ -0,0 +1,30 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2014-2015 +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/libs/intrusive for documentation. +// +///////////////////////////////////////////////////////////////////////////// +#ifndef BOOST_INTRUSIVE_DETAIL_MINIMAL_PAIR_HEADER_HPP +#define BOOST_INTRUSIVE_DETAIL_MINIMAL_PAIR_HEADER_HPP +# +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif +# +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif +# +#//Try to avoid including <utility>, as it's quite big in C++11 +#if defined(BOOST_GNU_STDLIB) +# include <bits/stl_pair.h> +#else +# include <utility> //Fallback +#endif +# +#endif //BOOST_INTRUSIVE_DETAIL_MINIMAL_PAIR_HEADER_HPP diff --git a/boost/intrusive/detail/mpl.hpp b/boost/intrusive/detail/mpl.hpp index 9b2c9f114c..39d2c58bd3 100644 --- a/boost/intrusive/detail/mpl.hpp +++ b/boost/intrusive/detail/mpl.hpp @@ -14,7 +14,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_MPL_HPP #define BOOST_INTRUSIVE_DETAIL_MPL_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -315,7 +319,14 @@ template <> struct unvoid_ref<const void> { struct type_impl { }; typedef type_i ::boost::intrusive::detail::if_c \ <value, T, DefaultWrap>::type::TNAME type; \ }; \ - \ + // + +#define BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT(INSTANTIATION_NS_PREFIX, T, TNAME, TIMPL) \ + typename INSTANTIATION_NS_PREFIX \ + boost_intrusive_default_type_ ## TNAME< T, TIMPL >::type \ +// + +#define BOOST_INTRUSIVE_INSTANTIATE_EVAL_DEFAULT_TYPE_TMPLT(TNAME)\ template <typename T, typename DefaultType> \ struct boost_intrusive_eval_default_type_ ## TNAME \ { \ @@ -339,11 +350,6 @@ template <> struct unvoid_ref<const void> { struct type_impl { }; typedef type_i }; \ // -#define BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT(INSTANTIATION_NS_PREFIX, T, TNAME, TIMPL) \ - typename INSTANTIATION_NS_PREFIX \ - boost_intrusive_default_type_ ## TNAME< T, TIMPL >::type \ -// - #define BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_EVAL_DEFAULT(INSTANTIATION_NS_PREFIX, T, TNAME, TIMPL) \ typename INSTANTIATION_NS_PREFIX \ boost_intrusive_eval_default_type_ ## TNAME< T, TIMPL >::type \ @@ -367,6 +373,58 @@ struct TRAITS_PREFIX##_bool_is_true\ };\ // +#define BOOST_INTRUSIVE_HAS_STATIC_MEMBER_FUNC_SIGNATURE(TRAITS_NAME, FUNC_NAME) \ + template <typename U, typename Signature> \ + class TRAITS_NAME \ + { \ + private: \ + template<Signature> struct helper;\ + template<typename T> \ + static ::boost::intrusive::detail::yes_type check(helper<&T::FUNC_NAME>*); \ + template<typename T> static ::boost::intrusive::detail::no_type check(...); \ + public: \ + static const bool value = sizeof(check<U>(0)) == sizeof(::boost::intrusive::detail::yes_type); \ + }; \ +// + +#define BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(TRAITS_NAME, FUNC_NAME) \ +template <typename Type> \ +struct TRAITS_NAME \ +{ \ + struct BaseMixin \ + { \ + void FUNC_NAME(); \ + }; \ + struct Base : public Type, public BaseMixin { Base(); }; \ + template <typename T, T t> class Helper{}; \ + template <typename U> \ + static ::boost::intrusive::detail::no_type check(U*, Helper<void (BaseMixin::*)(), &U::FUNC_NAME>* = 0); \ + static ::boost::intrusive::detail::yes_type check(...); \ + static const bool value = sizeof(::boost::intrusive::detail::yes_type) == sizeof(check((Base*)(0))); \ +};\ +// + +#define BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED_IGNORE_SIGNATURE(TRAITS_NAME, FUNC_NAME) \ +BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(TRAITS_NAME##_ignore_signature, FUNC_NAME) \ +\ +template <typename Type, class> \ +struct TRAITS_NAME \ + : public TRAITS_NAME##_ignore_signature<Type> \ +{};\ +// + + +template <typename T> +inline T* addressof(T& obj) +{ + return static_cast<T*> + (static_cast<void*> + (const_cast<char*> + (&reinterpret_cast<const char&>(obj)) + ) + ); +} + } //namespace detail } //namespace intrusive } //namespace boost diff --git a/boost/intrusive/detail/node_cloner_disposer.hpp b/boost/intrusive/detail/node_cloner_disposer.hpp index 2a18100205..65af3e37b8 100644 --- a/boost/intrusive/detail/node_cloner_disposer.hpp +++ b/boost/intrusive/detail/node_cloner_disposer.hpp @@ -13,11 +13,16 @@ #ifndef BOOST_INTRUSIVE_DETAIL_NODE_CLONER_DISPOSER_HPP #define BOOST_INTRUSIVE_DETAIL_NODE_CLONER_DISPOSER_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif #include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/detail/mpl.hpp> #include <boost/intrusive/detail/ebo_functor_holder.hpp> #include <boost/intrusive/detail/algo_type.hpp> #include <boost/intrusive/detail/assert.hpp> @@ -26,9 +31,10 @@ namespace boost { namespace intrusive { namespace detail { -template<class F, class ValueTraits, algo_types AlgoType> +template<class F, class ValueTraits, algo_types AlgoType, bool IsConst = true> struct node_cloner - : private ebo_functor_holder<F> + //Use public inheritance to avoid MSVC bugs with closures + : public ebo_functor_holder<F> { typedef ValueTraits value_traits; typedef typename value_traits::node_traits node_traits; @@ -45,6 +51,8 @@ struct node_cloner typedef typename value_traits::reference reference; typedef typename value_traits::const_reference const_reference; + typedef typename if_c<IsConst, const_reference, reference>::type reference_type; + node_cloner(F f, const ValueTraits *traits) : base_t(f), traits_(traits) {} @@ -52,7 +60,7 @@ struct node_cloner // tree-based containers use this method, which is proxy-reference friendly node_ptr operator()(const node_ptr & p) { - const_reference v = *traits_->to_value_ptr(p); + reference_type v = *traits_->to_value_ptr(p); node_ptr n = traits_->to_node_ptr(*base_t::get()(v)); //Cloned node must be in default mode if the linking mode requires it if(safemode_or_autounlink) @@ -63,7 +71,7 @@ struct node_cloner // hashtables use this method, which is proxy-reference unfriendly node_ptr operator()(const node &to_clone) { - const value_type &v = + reference_type v = *traits_->to_value_ptr (pointer_traits<const_node_ptr>::pointer_to(to_clone)); node_ptr n = traits_->to_node_ptr(*base_t::get()(v)); @@ -78,7 +86,8 @@ struct node_cloner template<class F, class ValueTraits, algo_types AlgoType> struct node_disposer - : private ebo_functor_holder<F> + //Use public inheritance to avoid MSVC bugs with closures + : public ebo_functor_holder<F> { typedef ValueTraits value_traits; typedef typename value_traits::node_traits node_traits; diff --git a/boost/intrusive/detail/node_holder.hpp b/boost/intrusive/detail/node_holder.hpp index 12732a87a7..b8dabef2df 100644 --- a/boost/intrusive/detail/node_holder.hpp +++ b/boost/intrusive/detail/node_holder.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_NODE_HOLDER_HPP #define BOOST_INTRUSIVE_DETAIL_NODE_HOLDER_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/node_to_value.hpp b/boost/intrusive/detail/node_to_value.hpp index 6ec3971239..5af3347345 100644 --- a/boost/intrusive/detail/node_to_value.hpp +++ b/boost/intrusive/detail/node_to_value.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_NODE_TO_VALUE_HPP #define BOOST_INTRUSIVE_DETAIL_NODE_TO_VALUE_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/parent_from_member.hpp b/boost/intrusive/detail/parent_from_member.hpp index 3dfe8d6461..30eba13e16 100644 --- a/boost/intrusive/detail/parent_from_member.hpp +++ b/boost/intrusive/detail/parent_from_member.hpp @@ -12,7 +12,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_PARENT_FROM_MEMBER_HPP #define BOOST_INTRUSIVE_DETAIL_PARENT_FROM_MEMBER_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -48,7 +52,7 @@ inline std::ptrdiff_t offset_from_pointer_to_member(const Member Parent::* ptr_t caster.ptr_to_member = ptr_to_member; return std::ptrdiff_t(caster.offset); - //Additional info on MSVC behaviour for the future. For 2/3 int ptr-to-member + //Additional info on MSVC behaviour for the future. For 2/3 int ptr-to-member //types dereference seems to be: // // vboffset = [compile_time_offset if 2-int ptr2memb] / diff --git a/boost/intrusive/detail/pointer_element.hpp b/boost/intrusive/detail/pointer_element.hpp index 1c17f419ec..dd26e3cf0b 100644 --- a/boost/intrusive/detail/pointer_element.hpp +++ b/boost/intrusive/detail/pointer_element.hpp @@ -11,11 +11,17 @@ #ifndef BOOST_INTRUSIVE_DETAIL_POINTER_ELEMENT_HPP #define BOOST_INTRUSIVE_DETAIL_POINTER_ELEMENT_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif +#ifndef BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP #include <boost/intrusive/detail/workaround.hpp> +#endif //BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP namespace boost { namespace intrusive { @@ -118,14 +124,6 @@ template <typename T> struct first_param < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6, P7, P8> > { typedef T type; }; - template < template //10arg - <class,class,class,class,class,class,class,class,class,class,class - > class TemplateClass, class T - , class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7, class P8, class P9> - struct first_param - < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6, P7, P8, P9> > - { typedef T type; }; - #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <typename T> diff --git a/boost/intrusive/detail/preprocessor.hpp b/boost/intrusive/detail/preprocessor.hpp deleted file mode 100644 index cdbc8a1d39..0000000000 --- a/boost/intrusive/detail/preprocessor.hpp +++ /dev/null @@ -1,42 +0,0 @@ -////////////////////////////////////////////////////////////////////////////// -// -// (C) Copyright Ion Gaztanaga 2008-2014. Distributed under the Boost -// Software License, Version 1.0. (See accompanying file -// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -// -// See http://www.boost.org/libs/intrusive for documentation. -// -////////////////////////////////////////////////////////////////////////////// - -#ifndef BOOST_INTRUSIVE_DETAIL_PREPROCESSOR_HPP -#define BOOST_INTRUSIVE_DETAIL_PREPROCESSOR_HPP - -#if defined(_MSC_VER) -# pragma once -#endif - -#include <boost/intrusive/detail/config_begin.hpp> -#include <boost/intrusive/detail/workaround.hpp> - -#include <boost/preprocessor/cat.hpp> -#include <boost/preprocessor/repetition/enum.hpp> -#include <boost/preprocessor/repetition/enum_trailing_params.hpp> -#include <boost/preprocessor/repetition/enum_trailing.hpp> -#include <boost/preprocessor/arithmetic/sub.hpp> - - -#define BOOST_INTRUSIVE_MAX_CONSTRUCTOR_PARAMETERS 10 - -#define BOOST_INTRUSIVE_PP_IDENTITY(z, n, data) data - -#define BOOST_INTRUSIVE_PP_DECLVAL(z, n, data) \ -boost::move_detail::declval< BOOST_PP_CAT(P, n) >() \ -//! - -#define BOOST_INTRUSIVE_PP_TEMPLATE_PARAM_VOID_DEFAULT(z, n, data) \ - BOOST_PP_CAT(class P, n) = void \ -//! - -#include <boost/intrusive/detail/config_end.hpp> - -#endif //#ifndef BOOST_INTRUSIVE_DETAIL_PREPROCESSOR_HPP diff --git a/boost/intrusive/detail/rbtree_node.hpp b/boost/intrusive/detail/rbtree_node.hpp index ab50509c25..c4364399d8 100644 --- a/boost/intrusive/detail/rbtree_node.hpp +++ b/boost/intrusive/detail/rbtree_node.hpp @@ -14,7 +14,11 @@ #ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP #define BOOST_INTRUSIVE_RBTREE_NODE_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/reverse_iterator.hpp b/boost/intrusive/detail/reverse_iterator.hpp index 9f443ab4b2..6a6fee5ac2 100644 --- a/boost/intrusive/detail/reverse_iterator.hpp +++ b/boost/intrusive/detail/reverse_iterator.hpp @@ -10,19 +10,22 @@ // ///////////////////////////////////////////////////////////////////////////// -#ifndef BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP -#define BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP +#ifndef BOOST_INTRUSIVE_DETAIL_REVERSE_ITERATOR_HPP +#define BOOST_INTRUSIVE_DETAIL_REVERSE_ITERATOR_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif #include <boost/intrusive/detail/config_begin.hpp> -#include <boost/intrusive/detail/iiterator.hpp> +#include <boost/intrusive/detail/iterator.hpp> namespace boost { namespace intrusive { -namespace detail { template<class It> class reverse_iterator @@ -60,7 +63,7 @@ class reverse_iterator { It temp(m_current); --temp; return temp.operator->(); } reference operator[](difference_type off) const - { return this->m_current[-off]; } + { return this->m_current[-off-1]; } reverse_iterator& operator++() { --m_current; return *this; } @@ -130,10 +133,9 @@ class reverse_iterator It m_current; // the wrapped iterator }; -} //namespace detail -} //namespace intrusive -} //namespace boost +} //namespace intrusive { +} //namespace boost { #include <boost/intrusive/detail/config_end.hpp> -#endif //BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP +#endif //BOOST_INTRUSIVE_DETAIL_REVERSE_ITERATOR_HPP diff --git a/boost/intrusive/detail/simple_disposers.hpp b/boost/intrusive/detail/simple_disposers.hpp index af597722fa..1420b281b0 100644 --- a/boost/intrusive/detail/simple_disposers.hpp +++ b/boost/intrusive/detail/simple_disposers.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_SIMPLE_DISPOSERS_HPP #define BOOST_INTRUSIVE_DETAIL_SIMPLE_DISPOSERS_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/size_holder.hpp b/boost/intrusive/detail/size_holder.hpp index a733187733..de1933ed50 100644 --- a/boost/intrusive/detail/size_holder.hpp +++ b/boost/intrusive/detail/size_holder.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_SIZE_HOLDER_HPP #define BOOST_INTRUSIVE_DETAIL_SIZE_HOLDER_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/slist_iterator.hpp b/boost/intrusive/detail/slist_iterator.hpp index 579c660f57..80a6fef924 100644 --- a/boost/intrusive/detail/slist_iterator.hpp +++ b/boost/intrusive/detail/slist_iterator.hpp @@ -14,7 +14,11 @@ #ifndef BOOST_INTRUSIVE_SLIST_ITERATOR_HPP #define BOOST_INTRUSIVE_SLIST_ITERATOR_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/slist_node.hpp b/boost/intrusive/detail/slist_node.hpp index 437190e6c0..3d5fbfb6e5 100644 --- a/boost/intrusive/detail/slist_node.hpp +++ b/boost/intrusive/detail/slist_node.hpp @@ -14,7 +14,11 @@ #ifndef BOOST_INTRUSIVE_SLIST_NODE_HPP #define BOOST_INTRUSIVE_SLIST_NODE_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/std_fwd.hpp b/boost/intrusive/detail/std_fwd.hpp index b657c4acfe..0492c1dc3d 100644 --- a/boost/intrusive/detail/std_fwd.hpp +++ b/boost/intrusive/detail/std_fwd.hpp @@ -11,7 +11,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_STD_FWD_HPP #define BOOST_INTRUSIVE_DETAIL_STD_FWD_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -25,6 +29,12 @@ #pragma GCC diagnostic ignored "-Wc++11-extensions" #define BOOST_INTRUSIVE_STD_NS_BEG _LIBCPP_BEGIN_NAMESPACE_STD #define BOOST_INTRUSIVE_STD_NS_END _LIBCPP_END_NAMESPACE_STD +#elif defined(BOOST_GNU_STDLIB) && defined(_GLIBCXX_BEGIN_NAMESPACE_VERSION) //GCC >= 4.6 + #define BOOST_INTRUSIVE_STD_NS_BEG namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION + #define BOOST_INTRUSIVE_STD_NS_END _GLIBCXX_END_NAMESPACE_VERSION } // namespace +#elif defined(BOOST_GNU_STDLIB) && defined(_GLIBCXX_BEGIN_NAMESPACE) //GCC >= 4.2 + #define BOOST_INTRUSIVE_STD_NS_BEG _GLIBCXX_BEGIN_NAMESPACE(std) + #define BOOST_INTRUSIVE_STD_NS_END _GLIBCXX_END_NAMESPACE #else #define BOOST_INTRUSIVE_STD_NS_BEG namespace std{ #define BOOST_INTRUSIVE_STD_NS_END } @@ -51,4 +61,3 @@ BOOST_INTRUSIVE_STD_NS_END #endif //BOOST_INTRUSIVE_CLANG_INLINE_STD_NS #endif //#ifndef BOOST_INTRUSIVE_DETAIL_STD_FWD_HPP - diff --git a/boost/intrusive/detail/to_raw_pointer.hpp b/boost/intrusive/detail/to_raw_pointer.hpp index e7ebff9e5d..387f63f2a4 100644 --- a/boost/intrusive/detail/to_raw_pointer.hpp +++ b/boost/intrusive/detail/to_raw_pointer.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_TO_RAW_POINTER_HPP #define BOOST_INTRUSIVE_DETAIL_TO_RAW_POINTER_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/transform_iterator.hpp b/boost/intrusive/detail/transform_iterator.hpp index 698318be9b..89ec973967 100644 --- a/boost/intrusive/detail/transform_iterator.hpp +++ b/boost/intrusive/detail/transform_iterator.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_TRANSFORM_ITERATOR_HPP #define BOOST_INTRUSIVE_DETAIL_TRANSFORM_ITERATOR_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -90,16 +94,6 @@ class transform_iterator friend bool operator!= (const transform_iterator& i, const transform_iterator& i2) { return !(i == i2); } -/* - friend bool operator> (const transform_iterator& i, const transform_iterator& i2) - { return i2 < i; } - - friend bool operator<= (const transform_iterator& i, const transform_iterator& i2) - { return !(i > i2); } - - friend bool operator>= (const transform_iterator& i, const transform_iterator& i2) - { return !(i < i2); } -*/ friend typename Iterator::difference_type operator- (const transform_iterator& i, const transform_iterator& i2) { return i2.distance_to(i); } diff --git a/boost/intrusive/detail/tree_iterator.hpp b/boost/intrusive/detail/tree_iterator.hpp index c3b599d190..525761f3d6 100644 --- a/boost/intrusive/detail/tree_iterator.hpp +++ b/boost/intrusive/detail/tree_iterator.hpp @@ -13,14 +13,18 @@ #ifndef BOOST_INTRUSIVE_TREE_ITERATOR_HPP #define BOOST_INTRUSIVE_TREE_ITERATOR_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/detail/std_fwd.hpp> #include <boost/intrusive/detail/iiterator.hpp> -#include <boost/intrusive/bstree_algorithms.hpp> +#include <boost/intrusive/detail/bstree_algorithms_base.hpp> namespace boost { namespace intrusive { @@ -46,8 +50,12 @@ class tree_iterator typedef typename types_t::node node; typedef typename types_t::node_ptr node_ptr; typedef typename types_t::const_value_traits_ptr const_value_traits_ptr; + typedef bstree_algorithms_base<node_traits> node_algorithms; + static const bool stateful_value_traits = types_t::stateful_value_traits; - typedef bstree_algorithms<node_traits> node_algorithms; + + void unspecified_bool_type_func() const {} + typedef void (tree_iterator::*unspecified_bool_type)() const; public: typedef typename types_t::iterator_traits::difference_type difference_type; @@ -100,6 +108,21 @@ class tree_iterator return result; } + void go_left() + { members_.nodeptr_ = node_traits::get_left(members_.nodeptr_); } + + void go_right() + { members_.nodeptr_ = node_traits::get_right(members_.nodeptr_); } + + void go_parent() + { members_.nodeptr_ = node_traits::get_parent(members_.nodeptr_); } + + operator unspecified_bool_type() const + { return members_.nodeptr_ ? &tree_iterator::unspecified_bool_type_func : 0; } + + bool operator! () const + { return !members_.nodeptr_; } + friend bool operator== (const tree_iterator& l, const tree_iterator& r) { return l.pointed_node() == r.pointed_node(); } diff --git a/boost/intrusive/detail/tree_node.hpp b/boost/intrusive/detail/tree_node.hpp index 653d6fcf07..e36a82a6d6 100644 --- a/boost/intrusive/detail/tree_node.hpp +++ b/boost/intrusive/detail/tree_node.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_TREE_NODE_HPP #define BOOST_INTRUSIVE_TREE_NODE_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/uncast.hpp b/boost/intrusive/detail/uncast.hpp index 944b6cd617..7db97b7457 100644 --- a/boost/intrusive/detail/uncast.hpp +++ b/boost/intrusive/detail/uncast.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_UNCAST_HPP #define BOOST_INTRUSIVE_DETAIL_UNCAST_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif diff --git a/boost/intrusive/detail/workaround.hpp b/boost/intrusive/detail/workaround.hpp index ad00691f25..b73f4ef8bf 100644 --- a/boost/intrusive/detail/workaround.hpp +++ b/boost/intrusive/detail/workaround.hpp @@ -8,10 +8,14 @@ // ////////////////////////////////////////////////////////////////////////////// -#ifndef BOOST_INTRUSIVE_DETAIL_WRKRND_HPP -#define BOOST_INTRUSIVE_DETAIL_WRKRND_HPP +#ifndef BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP +#define BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -26,5 +30,9 @@ //Macros for documentation purposes. For code, expands to the argument #define BOOST_INTRUSIVE_IMPDEF(TYPE) TYPE #define BOOST_INTRUSIVE_SEEDOC(TYPE) TYPE +#define BOOST_INTRUSIVE_DOC1ST(TYPE1, TYPE2) TYPE2 +#define BOOST_INTRUSIVE_I , +#define BOOST_INTRUSIVE_DOCIGN(T1) T1 + -#endif //#ifndef BOOST_INTRUSIVE_DETAIL_WRKRND_HPP +#endif //#ifndef BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP diff --git a/boost/intrusive/hashtable.hpp b/boost/intrusive/hashtable.hpp index af73f70629..1d4f3d3f0c 100644 --- a/boost/intrusive/hashtable.hpp +++ b/boost/intrusive/hashtable.hpp @@ -12,21 +12,9 @@ #ifndef BOOST_INTRUSIVE_HASHTABLE_HPP #define BOOST_INTRUSIVE_HASHTABLE_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> -//std C++ -#include <functional> //std::equal_to -#include <utility> //std::pair -#include <algorithm> //std::swap, std::lower_bound, std::upper_bound -#include <cstddef> //std::size_t -//boost -#include <boost/intrusive/detail/assert.hpp> -#include <boost/static_assert.hpp> -#include <boost/functional/hash.hpp> + //General intrusive utilities #include <boost/intrusive/detail/hashtable_node.hpp> #include <boost/intrusive/detail/transform_iterator.hpp> @@ -44,7 +32,23 @@ #include <boost/intrusive/slist.hpp> #include <boost/intrusive/pointer_traits.hpp> #include <boost/intrusive/detail/mpl.hpp> + +//boost +#include <boost/functional/hash.hpp> +#include <boost/intrusive/detail/assert.hpp> +#include <boost/static_assert.hpp> #include <boost/move/utility_core.hpp> +#include <boost/move/adl_move_swap.hpp> + +//std C++ +#include <boost/intrusive/detail/minimal_less_equal_header.hpp> //std::equal_to +#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair +#include <algorithm> //std::lower_bound, std::upper_bound +#include <cstddef> //std::size_t + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -550,7 +554,8 @@ struct downcast_node_to_value_t template<class F, class SlistNodePtr, class NodePtr> struct node_cast_adaptor - : private detail::ebo_functor_holder<F> + //Use public inheritance to avoid MSVC bugs with closures + : public detail::ebo_functor_holder<F> { typedef detail::ebo_functor_holder<F> base_t; @@ -800,6 +805,7 @@ struct get_hash<void, T> //Stores bucket_plus_vtraits plust the hash function template<class VoidOrKeyHash, class ValueTraits, class BucketTraits> struct bucket_hash_t + //Use public inheritance to avoid MSVC bugs with closures : public detail::ebo_functor_holder <typename get_hash< VoidOrKeyHash , typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits::value_type @@ -852,6 +858,7 @@ struct get_equal_to<void, T> //non-empty bucket shall not be cached. template<class VoidOrKeyHash, class VoidOrKeyEqual, class ValueTraits, class BucketTraits, bool> struct bucket_hash_equal_t + //Use public inheritance to avoid MSVC bugs with closures : public detail::ebo_functor_holder //equal <typename get_equal_to< VoidOrKeyEqual , typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits::value_type @@ -929,6 +936,7 @@ struct bucket_hash_equal_t //non-empty bucket shall be cached. template<class VoidOrKeyHash, class VoidOrKeyEqual, class ValueTraits, class BucketTraits> //cache_begin == true version struct bucket_hash_equal_t<VoidOrKeyHash, VoidOrKeyEqual, ValueTraits, BucketTraits, true> + //Use public inheritance to avoid MSVC bugs with closures : public detail::ebo_functor_holder //equal <typename get_equal_to< VoidOrKeyEqual , typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits::value_type @@ -973,7 +981,7 @@ struct bucket_hash_equal_t<VoidOrKeyHash, VoidOrKeyEqual, ValueTraits, BucketTra void priv_swap_cache(bucket_hash_equal_t &other) { - std::swap(this->cached_begin_, other.cached_begin_); + ::boost::adl_move_swap(this->cached_begin_, other.cached_begin_); } siterator priv_begin() const @@ -1308,7 +1316,7 @@ class hashtable_impl typedef detail::transform_iterator < typename slist_impl::iterator - , downcast_node_to_value_t + , downcast_node_to_value_t < value_traits , true> > const_local_iterator; @@ -1510,13 +1518,12 @@ class hashtable_impl //! found using ADL throw. Basic guarantee. void swap(hashtable_impl& other) { - using std::swap; //These can throw - swap(this->priv_equal(), other.priv_equal()); - swap(this->priv_hasher(), other.priv_hasher()); + ::boost::adl_move_swap(this->priv_equal(), other.priv_equal()); + ::boost::adl_move_swap(this->priv_hasher(), other.priv_hasher()); //These can't throw - swap(this->priv_bucket_traits(), other.priv_bucket_traits()); - swap(this->priv_value_traits(), other.priv_value_traits()); + ::boost::adl_move_swap(this->priv_bucket_traits(), other.priv_bucket_traits()); + ::boost::adl_move_swap(this->priv_value_traits(), other.priv_value_traits()); this->priv_swap_cache(other); if(constant_time_size){ size_type backup = this->priv_size_traits().get_size(); @@ -1568,7 +1575,7 @@ class hashtable_impl const bucket_ptr src_buckets = src.priv_bucket_pointer(); const bucket_ptr dst_buckets = this->priv_bucket_pointer(); size_type constructed; - + typedef node_cast_adaptor< detail::node_disposer<Disposer, value_traits, CircularSListAlgorithms> , slist_node_ptr, node_ptr > NodeDisposer; typedef node_cast_adaptor< detail::node_cloner <Cloner, value_traits, CircularSListAlgorithms> @@ -1660,7 +1667,7 @@ class hashtable_impl //! //! <b>Effects</b>: Equivalent to this->insert_equal(t) for each element in [b, e). //! - //! <b>Complexity</b>: Average case O(N), where N is std::distance(b, e). + //! <b>Complexity</b>: Average case O(N), where N is distance(b, e). //! Worst case O(N*this->size()). //! //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee. @@ -1706,7 +1713,7 @@ class hashtable_impl //! //! <b>Effects</b>: Equivalent to this->insert_unique(t) for each element in [b, e). //! - //! <b>Complexity</b>: Average case O(N), where N is std::distance(b, e). + //! <b>Complexity</b>: Average case O(N), where N is distance(b, e). //! Worst case O(N*this->size()). //! //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee. @@ -1819,7 +1826,7 @@ class hashtable_impl //! <b>Effects</b>: Erases the range pointed to by b end e. //! - //! <b>Complexity</b>: Average case O(std::distance(b, e)), + //! <b>Complexity</b>: Average case O(distance(b, e)), //! worst case O(this->size()). //! //! <b>Throws</b>: Nothing. @@ -1896,7 +1903,7 @@ class hashtable_impl //! <b>Effects</b>: Erases the range pointed to by b end e. //! Disposer::operator()(pointer) is called for the removed elements. //! - //! <b>Complexity</b>: Average case O(std::distance(b, e)), + //! <b>Complexity</b>: Average case O(distance(b, e)), //! worst case O(this->size()). //! //! <b>Throws</b>: Nothing. @@ -2805,7 +2812,7 @@ class hashtable_impl siterator priv_invalid_local_it() const { return this->data_type::internal.internal.internal.internal.priv_invalid_local_it(); } - + split_traits &priv_split_traits() { return this->data_type::internal.priv_split_traits(); } @@ -3287,11 +3294,11 @@ class hashtable {} hashtable(BOOST_RV_REF(hashtable) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} hashtable& operator=(BOOST_RV_REF(hashtable) x) - { return static_cast<hashtable&>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<hashtable&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } }; #endif diff --git a/boost/intrusive/intrusive_fwd.hpp b/boost/intrusive/intrusive_fwd.hpp index a4498161a1..88cb537c6b 100644 --- a/boost/intrusive/intrusive_fwd.hpp +++ b/boost/intrusive/intrusive_fwd.hpp @@ -13,7 +13,11 @@ #ifndef BOOST_INTRUSIVE_FWD_HPP #define BOOST_INTRUSIVE_FWD_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -25,15 +29,15 @@ //! - boost::intrusive::list / boost::intrusive::list_base_hook / boost::intrusive::list_member_hook //! - boost::intrusive::bstree / boost::intrusive::bs_set / boost::intrusive::bs_multiset / //! boost::intrusive::bs_set_base_hook / boost::intrusive::bs_set_member_hook -//! - boost::intrusive::rbtree / boost::intrusive::set / boost::intrusive::multiset / +//! - boost::intrusive::rbtree / boost::intrusive::set / boost::intrusive::multiset / //! boost::intrusive::set_base_hook / boost::intrusive::set_member_hook //! - boost::intrusive::avltree / boost::intrusive::avl_set / boost::intrusive::avl_multiset / //! boost::intrusive::avl_set_base_hook / boost::intrusive::avl_set_member_hook -//! - boost::intrusive::splaytree / boost::intrusive::splay_set / boost::intrusive::splay_multiset -//! - boost::intrusive::sgtree / boost::intrusive::sg_set / boost::intrusive::sg_multiset +//! - boost::intrusive::splaytree / boost::intrusive::splay_set / boost::intrusive::splay_multiset +//! - boost::intrusive::sgtree / boost::intrusive::sg_set / boost::intrusive::sg_multiset //! - boost::intrusive::treap / boost::intrusive::treap_set / boost::intrusive::treap_multiset //! - boost::intrusive::hashtable / boost::intrusive::unordered_set / boost::intrusive::unordered_multiset / -//! boost::intrusive::unordered_set_base_hook / boost::intrusive::unordered_set_member_hook / +//! boost::intrusive::unordered_set_base_hook / boost::intrusive::unordered_set_member_hook / //! - boost::intrusive::any_base_hook / boost::intrusive::any_member_hook //! //! It forward declares the following container or hook options: @@ -50,7 +54,7 @@ //! boost::intrusive::trivial_value_traits //! //! Finally it forward declares the following general purpose utilities: -//! - boost::intrusive::pointer_plus_bits / boost::intrusive::priority_compare. +//! - boost::intrusive::pointer_plus_bits / boost::intrusive::priority_compare. #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) @@ -630,7 +634,7 @@ struct hash; template<typename ValueTraits> struct value_traits; template< typename Parent - , typename MemberHook + , typename MemberHook , MemberHook Parent::* PtrToMember> struct member_hook; @@ -703,16 +707,16 @@ struct trivial_value_traits; //Additional utilities -template<typename VoidPointer, std::size_t Alignment> +template<typename VoidPointer, std::size_t Alignment> struct max_pointer_plus_bits; -template<std::size_t Alignment> +template<std::size_t Alignment> struct max_pointer_plus_bits<void *, Alignment>; template<typename Pointer, std::size_t NumBits> struct pointer_plus_bits; -template<typename T, std::size_t NumBits> +template<typename T, std::size_t NumBits> struct pointer_plus_bits<T *, NumBits>; template<typename Ptr> diff --git a/boost/intrusive/linear_slist_algorithms.hpp b/boost/intrusive/linear_slist_algorithms.hpp index 31e5594384..4b1f06ff9f 100644 --- a/boost/intrusive/linear_slist_algorithms.hpp +++ b/boost/intrusive/linear_slist_algorithms.hpp @@ -14,16 +14,16 @@ #ifndef BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP #define BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/common_slist_algorithms.hpp> #include <boost/intrusive/detail/algo_type.hpp> #include <cstddef> -#include <utility> +#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { diff --git a/boost/intrusive/link_mode.hpp b/boost/intrusive/link_mode.hpp index c7245d9c1f..4ba4daff7d 100644 --- a/boost/intrusive/link_mode.hpp +++ b/boost/intrusive/link_mode.hpp @@ -13,7 +13,7 @@ #ifndef BOOST_INTRUSIVE_LINK_MODE_HPP #define BOOST_INTRUSIVE_LINK_MODE_HPP -#if defined(_MSC_VER) +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -50,7 +50,7 @@ enum link_mode_type{ template <link_mode_type link_mode> struct is_safe_autounlink { - static const bool value = + static const bool value = (int)link_mode == (int)auto_unlink || (int)link_mode == (int)safe_link; }; diff --git a/boost/intrusive/list.hpp b/boost/intrusive/list.hpp index 297267d34b..906b002907 100644 --- a/boost/intrusive/list.hpp +++ b/boost/intrusive/list.hpp @@ -14,10 +14,6 @@ #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/intrusive_fwd.hpp> #include <boost/intrusive/detail/assert.hpp> @@ -38,13 +34,17 @@ #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 <algorithm> -#include <functional> -#include <cstddef> +#include <boost/intrusive/detail/minimal_less_equal_header.hpp>//std::less +#include <cstddef> //std::size_t, etc. + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -97,14 +97,15 @@ class list_impl 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 boost::intrusive::reverse_iterator<iterator> reverse_iterator; + typedef boost::intrusive::reverse_iterator<const_iterator> const_reverse_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 circular_list_algorithms<node_traits> node_algorithms; - typedef HeaderHolder header_holder_type; + typedef typename detail::get_header_holder_type + < value_traits, HeaderHolder >::type header_holder_type; static const bool constant_time_size = ConstantTimeSize; static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; @@ -186,7 +187,7 @@ class list_impl //! //! <b>Effects</b>: Constructs a list equal to the range [first,last). //! - //! <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). @@ -352,7 +353,7 @@ class list_impl //! //! <b>Complexity</b>: Constant. const_reference front() const - { return *priv_value_traits().to_value_ptr(detail::uncast(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 reference to the last element of the list. //! @@ -603,7 +604,7 @@ class list_impl } //! <b>Requires</b>: b and e must be valid iterators to elements in *this. - //! n must be std::distance(b, e). + //! n must be distance(b, e). //! //! <b>Effects</b>: Erases the element range pointed by b and e //! No destructors are called. @@ -914,12 +915,12 @@ class list_impl if(constant_time_size) this->splice(p, x, f, e, node_algorithms::distance(f.pointed_node(), e.pointed_node())); else - this->splice(p, x, f, e, 1);//distance is a dummy value + this->splice(p, x, f, e, 1);//intrusive::iterator_distance is a dummy value } //! <b>Requires</b>: p must be a valid iterator of *this. //! f and e must point to elements contained in list x. - //! n == std::distance(f, e) + //! n == distance(f, e) //! //! <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. @@ -1247,7 +1248,7 @@ class list_impl static const_iterator s_iterator_to(const_reference value) { BOOST_STATIC_ASSERT((!stateful_value_traits)); - reference r =*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value)); + reference r =*detail::uncast(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()); } @@ -1278,7 +1279,7 @@ class list_impl //! <b>Note</b>: Iterators and references are not invalidated. const_iterator iterator_to(const_reference value) const { - reference r = *pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value)); + reference r = *detail::uncast(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()); } @@ -1348,7 +1349,7 @@ inline bool operator< #else (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()); } +{ 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> @@ -1363,30 +1364,11 @@ bool operator== #endif { 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()){ 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) @@ -1475,15 +1457,12 @@ struct make_list typedef typename detail::get_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 < value_traits, typename packed_options::size_type, packed_options::constant_time_size, - header_holder_type + typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -1533,11 +1512,11 @@ class list {} list(BOOST_RV_REF(list) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} list& operator=(BOOST_RV_REF(list) x) - { return static_cast<list &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<list &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static list &container_from_end_iterator(iterator end_iterator) { return static_cast<list &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/list_hook.hpp b/boost/intrusive/list_hook.hpp index 1a06a980b7..aef72537e7 100644 --- a/boost/intrusive/list_hook.hpp +++ b/boost/intrusive/list_hook.hpp @@ -14,10 +14,6 @@ #ifndef BOOST_INTRUSIVE_LIST_HOOK_HPP #define BOOST_INTRUSIVE_LIST_HOOK_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -26,6 +22,11 @@ #include <boost/intrusive/options.hpp> #include <boost/intrusive/detail/generic_hook.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + + namespace boost { namespace intrusive { diff --git a/boost/intrusive/member_value_traits.hpp b/boost/intrusive/member_value_traits.hpp index 96c50ee45c..b540178d5a 100644 --- a/boost/intrusive/member_value_traits.hpp +++ b/boost/intrusive/member_value_traits.hpp @@ -13,10 +13,6 @@ #ifndef BOOST_INTRUSIVE_MEMBER_VALUE_TRAITS_HPP #define BOOST_INTRUSIVE_MEMBER_VALUE_TRAITS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -24,6 +20,10 @@ #include <boost/intrusive/detail/parent_from_member.hpp> #include <boost/intrusive/pointer_traits.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { diff --git a/boost/intrusive/options.hpp b/boost/intrusive/options.hpp index 9a77750c7f..ec6e9674d9 100644 --- a/boost/intrusive/options.hpp +++ b/boost/intrusive/options.hpp @@ -13,16 +13,16 @@ #ifndef BOOST_INTRUSIVE_OPTIONS_HPP #define BOOST_INTRUSIVE_OPTIONS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/link_mode.hpp> #include <boost/intrusive/pack_options.hpp> #include <boost/intrusive/detail/mpl.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -37,8 +37,7 @@ struct fhtraits; template<class T, class Hook, Hook T::* P> struct mhtraits; -//typedef void default_tag; -struct default_tag; +struct dft_tag; struct member_tag; template<class SupposedValueTraits> @@ -127,7 +126,7 @@ struct member_hook // //always single inheritance, the offset of the node is exactly the offset of // //the hook. Since the node type is shared between all member hooks, this saves // //quite a lot of symbol stuff. -// , (Ptr2MemNode)PtrToMember +// , (Ptr2MemNode)PtrToMember // , MemberHook::hooktags::link_mode> member_value_traits; typedef mhtraits <Parent, MemberHook, PtrToMember> member_value_traits; template<class Base> @@ -231,7 +230,7 @@ struct hook_defaults { typedef void* void_pointer; static const link_mode_type link_mode = safe_link; - typedef default_tag tag; + typedef dft_tag tag; static const bool optimize_size = false; static const bool store_hash = false; static const bool linear = false; diff --git a/boost/intrusive/pack_options.hpp b/boost/intrusive/pack_options.hpp index 077b08b60c..944243f661 100644 --- a/boost/intrusive/pack_options.hpp +++ b/boost/intrusive/pack_options.hpp @@ -13,12 +13,12 @@ #ifndef BOOST_INTRUSIVE_PACK_OPTIONS_HPP #define BOOST_INTRUSIVE_PACK_OPTIONS_HPP -#if defined(_MSC_VER) +#include <boost/intrusive/detail/config_begin.hpp> + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif -#include <boost/intrusive/detail/config_begin.hpp> - namespace boost { namespace intrusive { @@ -257,7 +257,7 @@ struct OPTION_NAME \ //! - a default options class defining initial static constant //! and typedefs //! - several options defined with BOOST_INTRUSIVE_OPTION_CONSTANT and -//! BOOST_INTRUSIVE_OPTION_TYPE +//! BOOST_INTRUSIVE_OPTION_TYPE //! //! and packs them together in a new type that defines all options as //! member typedefs or static constant values. Given options of form: @@ -308,7 +308,7 @@ struct pack_options //! //! \code //! struct OPTION_NAME<class TYPE> -//! { /*unspecified_content*/ }; +//! { unspecified_content }; //! \endcode //! //! ...that after being combined with @@ -338,7 +338,7 @@ struct pack_options //! //! \code //! struct OPTION_NAME<TYPE VALUE> -//! { /*unspecified_content*/ }; +//! { unspecified_content }; //! \endcode //! //! ...that after being combined with diff --git a/boost/intrusive/parent_from_member.hpp b/boost/intrusive/parent_from_member.hpp index e6be5bce6b..af3aa1f808 100644 --- a/boost/intrusive/parent_from_member.hpp +++ b/boost/intrusive/parent_from_member.hpp @@ -12,15 +12,15 @@ #ifndef BOOST_INTRUSIVE_PARENT_FROM_MEMBER_HPP #define BOOST_INTRUSIVE_PARENT_FROM_MEMBER_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/parent_from_member.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { diff --git a/boost/intrusive/pointer_plus_bits.hpp b/boost/intrusive/pointer_plus_bits.hpp index 1fcf67aa55..117aff3c58 100644 --- a/boost/intrusive/pointer_plus_bits.hpp +++ b/boost/intrusive/pointer_plus_bits.hpp @@ -13,15 +13,15 @@ #ifndef BOOST_INTRUSIVE_POINTER_PLUS_BITS_HPP #define BOOST_INTRUSIVE_POINTER_PLUS_BITS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/mpl.hpp> //ls_zeros #include <boost/intrusive/detail/assert.hpp> //BOOST_INTRUSIVE_INVARIANT_ASSERT +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { diff --git a/boost/intrusive/pointer_rebind.hpp b/boost/intrusive/pointer_rebind.hpp index 852491355b..9592e06e1d 100644 --- a/boost/intrusive/pointer_rebind.hpp +++ b/boost/intrusive/pointer_rebind.hpp @@ -11,11 +11,17 @@ #ifndef BOOST_INTRUSIVE_POINTER_REBIND_HPP #define BOOST_INTRUSIVE_POINTER_REBIND_HPP -#if defined(_MSC_VER) -# pragma once +#ifndef BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP +#include <boost/intrusive/detail/workaround.hpp> +#endif //BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> #endif -#include <boost/intrusive/detail/workaround.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -165,12 +171,6 @@ template <template <class, class, class, class, class, class, class, class, clas struct pointer_rebinder<Ptr<A, P0, P1, P2, P3, P4, P5, P6, P7, P8>, U, 0u> { typedef Ptr<U, P0, P1, P2, P3, P4, P5, P6, P7, P8> type; }; -template <template <class, class, class, class, class, class, class, class, class, class, class> class Ptr //10arg - , typename A, class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7, class P8, class P9 - , class U> -struct pointer_rebinder<Ptr<A, P0, P1, P2, P3, P4, P5, P6, P7, P8, P9>, U, 0u> -{ typedef Ptr<U, P0, P1, P2, P3, P4, P5, P6, P7, P8, P9> type; }; - #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <typename Ptr, typename U> diff --git a/boost/intrusive/pointer_traits.hpp b/boost/intrusive/pointer_traits.hpp index d3c66df091..24843fddc5 100644 --- a/boost/intrusive/pointer_traits.hpp +++ b/boost/intrusive/pointer_traits.hpp @@ -6,7 +6,7 @@ // ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2011-2013. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2011-2014. Distributed under the Boost // Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // @@ -17,26 +17,53 @@ #ifndef BOOST_INTRUSIVE_POINTER_TRAITS_HPP #define BOOST_INTRUSIVE_POINTER_TRAITS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> -#include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/workaround.hpp> -#include <boost/intrusive/detail/memory_util.hpp> #include <boost/intrusive/pointer_rebind.hpp> #include <boost/intrusive/detail/pointer_element.hpp> #include <boost/intrusive/detail/mpl.hpp> #include <cstddef> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { +namespace detail { + +#if !defined(BOOST_MSVC) || (BOOST_MSVC > 1310) +BOOST_INTRUSIVE_HAS_STATIC_MEMBER_FUNC_SIGNATURE(has_member_function_callable_with_pointer_to, pointer_to) +BOOST_INTRUSIVE_HAS_STATIC_MEMBER_FUNC_SIGNATURE(has_member_function_callable_with_dynamic_cast_from, dynamic_cast_from) +BOOST_INTRUSIVE_HAS_STATIC_MEMBER_FUNC_SIGNATURE(has_member_function_callable_with_static_cast_from, static_cast_from) +BOOST_INTRUSIVE_HAS_STATIC_MEMBER_FUNC_SIGNATURE(has_member_function_callable_with_const_cast_from, const_cast_from) +#else +BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED_IGNORE_SIGNATURE(has_member_function_callable_with_pointer_to, pointer_to) +BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED_IGNORE_SIGNATURE(has_member_function_callable_with_dynamic_cast_from, dynamic_cast_from) +BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED_IGNORE_SIGNATURE(has_member_function_callable_with_static_cast_from, static_cast_from) +BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED_IGNORE_SIGNATURE(has_member_function_callable_with_const_cast_from, const_cast_from) +#endif + +BOOST_INTRUSIVE_INSTANTIATE_EVAL_DEFAULT_TYPE_TMPLT(element_type) +BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(difference_type) +BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(reference) +BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(value_traits_ptr) + +} //namespace detail { + //! pointer_traits is the implementation of C++11 std::pointer_traits class with some //! extensions like castings. //! //! pointer_traits supplies a uniform interface to certain attributes of pointer-like types. +//! +//! <b>Note</b>: When defining a custom family of pointers or references to be used with BI +//! library, make sure the public static conversion functions accessed through +//! the `pointer_traits` interface (`*_cast_from` and `pointer_to`) can +//! properly convert between const and nonconst referred member types +//! <b>without the use of implicit constructor calls</b>. It is suggested these +//! conversions be implemented as function templates, where the template +//! argument is the type of the object being converted from. template <typename Ptr> struct pointer_traits { @@ -91,59 +118,83 @@ struct pointer_traits //! <b>Remark</b>: If element_type is (possibly cv-qualified) void, r type is unspecified; otherwise, //! it is element_type &. //! - //! <b>Returns</b>: A dereferenceable pointer to r obtained by calling Ptr::pointer_to(r). + //! <b>Returns</b>: A dereferenceable pointer to r obtained by calling Ptr::pointer_to(reference). //! Non-standard extension: If such function does not exist, returns pointer(addressof(r)); + //! + //! <b>Note</b>: For non-conforming compilers only the existence of a member function called + //! <code>pointer_to</code> is checked. static pointer pointer_to(reference r) { //Non-standard extension, it does not require Ptr::pointer_to. If not present //tries to converts &r to pointer. const bool value = boost::intrusive::detail:: has_member_function_callable_with_pointer_to - <Ptr, reference>::value; + <Ptr, Ptr (*)(reference)>::value; boost::intrusive::detail::bool_<value> flag; return pointer_traits::priv_pointer_to(flag, r); } //! <b>Remark</b>: Non-standard extension. //! - //! <b>Returns</b>: A dereferenceable pointer to r obtained by calling Ptr::static_cast_from(r). + //! <b>Returns</b>: A dereferenceable pointer to r obtained by calling the static template function + //! Ptr::static_cast_from(UPpr/const UPpr &). //! If such function does not exist, returns pointer_to(static_cast<element_type&>(*uptr)) + //! + //! <b>Note</b>: For non-conforming compilers only the existence of a member function called + //! <code>static_cast_from</code> is checked. template<class UPtr> static pointer static_cast_from(const UPtr &uptr) { + typedef const UPtr &RefArg; const bool value = boost::intrusive::detail:: has_member_function_callable_with_static_cast_from - <Ptr, const UPtr>::value; - boost::intrusive::detail::bool_<value> flag; - return pointer_traits::priv_static_cast_from(flag, uptr); + <pointer, pointer(*)(RefArg)>::value + || boost::intrusive::detail:: + has_member_function_callable_with_static_cast_from + <pointer, pointer(*)(UPtr)>::value; + return pointer_traits::priv_static_cast_from(boost::intrusive::detail::bool_<value>(), uptr); } //! <b>Remark</b>: Non-standard extension. //! - //! <b>Returns</b>: A dereferenceable pointer to r obtained by calling Ptr::const_cast_from(r). + //! <b>Returns</b>: A dereferenceable pointer to r obtained by calling the static template function + //! Ptr::const_cast_from<UPtr>(UPpr/const UPpr &). //! If such function does not exist, returns pointer_to(const_cast<element_type&>(*uptr)) + //! + //! <b>Note</b>: For non-conforming compilers only the existence of a member function called + //! <code>const_cast_from</code> is checked. template<class UPtr> static pointer const_cast_from(const UPtr &uptr) { + typedef const UPtr &RefArg; const bool value = boost::intrusive::detail:: has_member_function_callable_with_const_cast_from - <Ptr, const UPtr>::value; - boost::intrusive::detail::bool_<value> flag; - return pointer_traits::priv_const_cast_from(flag, uptr); + <pointer, pointer(*)(RefArg)>::value + || boost::intrusive::detail:: + has_member_function_callable_with_const_cast_from + <pointer, pointer(*)(UPtr)>::value; + return pointer_traits::priv_const_cast_from(boost::intrusive::detail::bool_<value>(), uptr); } //! <b>Remark</b>: Non-standard extension. //! - //! <b>Returns</b>: A dereferenceable pointer to r obtained by calling Ptr::dynamic_cast_from(r). + //! <b>Returns</b>: A dereferenceable pointer to r obtained by calling the static template function + //! Ptr::dynamic_cast_from<UPtr>(UPpr/const UPpr &). //! If such function does not exist, returns pointer_to(*dynamic_cast<element_type*>(&*uptr)) + //! + //! <b>Note</b>: For non-conforming compilers only the existence of a member function called + //! <code>dynamic_cast_from</code> is checked. template<class UPtr> static pointer dynamic_cast_from(const UPtr &uptr) { + typedef const UPtr &RefArg; const bool value = boost::intrusive::detail:: has_member_function_callable_with_dynamic_cast_from - <Ptr, const UPtr>::value; - boost::intrusive::detail::bool_<value> flag; - return pointer_traits::priv_dynamic_cast_from(flag, uptr); + <pointer, pointer(*)(RefArg)>::value + || boost::intrusive::detail:: + has_member_function_callable_with_dynamic_cast_from + <pointer, pointer(*)(UPtr)>::value; + return pointer_traits::priv_dynamic_cast_from(boost::intrusive::detail::bool_<value>(), uptr); } ///@cond diff --git a/boost/intrusive/priority_compare.hpp b/boost/intrusive/priority_compare.hpp index 419a7d2293..2ff851f475 100644 --- a/boost/intrusive/priority_compare.hpp +++ b/boost/intrusive/priority_compare.hpp @@ -13,14 +13,14 @@ #ifndef BOOST_INTRUSIVE_PRIORITY_COMPARE_HPP #define BOOST_INTRUSIVE_PRIORITY_COMPARE_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> -#include <functional> +#include <boost/intrusive/detail/minimal_less_equal_header.hpp> + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -56,8 +56,8 @@ struct get_prio<void, T> /// @endcond -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/rbtree.hpp b/boost/intrusive/rbtree.hpp index d6e692ef95..4ef50b4c4f 100644 --- a/boost/intrusive/rbtree.hpp +++ b/boost/intrusive/rbtree.hpp @@ -12,15 +12,11 @@ #ifndef BOOST_INTRUSIVE_RBTREE_HPP #define BOOST_INTRUSIVE_RBTREE_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <cstddef> -#include <functional> -#include <utility> +#include <boost/intrusive/detail/minimal_less_equal_header.hpp> +#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair #include <boost/intrusive/set_hook.hpp> #include <boost/intrusive/detail/rbtree_node.hpp> @@ -35,6 +31,10 @@ #include <boost/move/utility_core.hpp> #include <boost/static_assert.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -86,7 +86,7 @@ class rbtree_impl /// @cond typedef bstree_impl< ValueTraits, VoidOrKeyComp, SizeType , ConstantTimeSize, RbTreeAlgorithms - , HeaderHolder> tree_type; + , HeaderHolder> tree_type; typedef tree_type implementation_defined; /// @endcond @@ -139,12 +139,12 @@ class rbtree_impl //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) rbtree_impl(BOOST_RV_REF(rbtree_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) rbtree_impl& operator=(BOOST_RV_REF(rbtree_impl) x) - { return static_cast<rbtree_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<rbtree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::bstree::~bstree() @@ -213,10 +213,14 @@ class rbtree_impl //! @copydoc ::boost::intrusive::bstree::swap void swap(rbtree_impl& other); - //! @copydoc ::boost::intrusive::bstree::clone_from + //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree &src, cloner, Disposer) template <class Cloner, class Disposer> void clone_from(const rbtree_impl &src, Cloner cloner, Disposer disposer); + //! @copydoc ::boost::intrusive::bstree::clone_from(bstree &src, cloner, Disposer) + template <class Cloner, class Disposer> + void clone_from(rbtree_impl &src, Cloner cloner, Disposer disposer); + //! @copydoc ::boost::intrusive::bstree::insert_equal(reference) iterator insert_equal(reference value); @@ -305,7 +309,7 @@ class rbtree_impl //! @copydoc ::boost::intrusive::bstree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -453,15 +457,13 @@ struct make_rbtree typedef typename detail::get_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 rbtree_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -518,11 +520,11 @@ class rbtree {} rbtree(BOOST_RV_REF(rbtree) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} rbtree& operator=(BOOST_RV_REF(rbtree) x) - { return static_cast<rbtree &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<rbtree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static rbtree &container_from_end_iterator(iterator end_iterator) { return static_cast<rbtree &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/rbtree_algorithms.hpp b/boost/intrusive/rbtree_algorithms.hpp index 376deaf312..ad9c7658e3 100644 --- a/boost/intrusive/rbtree_algorithms.hpp +++ b/boost/intrusive/rbtree_algorithms.hpp @@ -23,10 +23,6 @@ #ifndef BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP #define BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -37,6 +33,10 @@ #include <boost/intrusive/bstree_algorithms.hpp> #include <boost/intrusive/detail/ebo_functor_holder.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -44,12 +44,13 @@ namespace intrusive { template<class NodeTraits, class F> struct rbtree_node_cloner - : private detail::ebo_functor_holder<F> + //Use public inheritance to avoid MSVC bugs with closures + : public detail::ebo_functor_holder<F> { typedef typename NodeTraits::node_ptr node_ptr; typedef detail::ebo_functor_holder<F> base_t; - rbtree_node_cloner(F f) + explicit rbtree_node_cloner(F f) : base_t(f) {} @@ -71,8 +72,14 @@ struct rbtree_node_checker typedef ValueTraits value_traits; typedef typename value_traits::node_traits node_traits; typedef typename node_traits::const_node_ptr const_node_ptr; + typedef typename node_traits::node_ptr node_ptr; - typedef typename base_checker_t::return_type return_type; + struct return_type + : public base_checker_t::return_type + { + return_type() : black_count_(0) {} + std::size_t black_count_; + }; rbtree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker) : base_checker_t(comp, extra_checker) @@ -82,13 +89,21 @@ struct rbtree_node_checker const return_type& check_return_left, const return_type& check_return_right, return_type& check_return) { - if (node_traits::get_color(p) == node_traits::red()) - { - if (node_traits::get_left(p)) - BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_color(node_traits::get_left(p)) == node_traits::black()); - if (node_traits::get_right(p)) - BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_color(node_traits::get_right(p)) == node_traits::black()); + + if (node_traits::get_color(p) == node_traits::red()){ + //Red nodes have black children + const node_ptr p_left(node_traits::get_left(p)); + const node_ptr p_right(node_traits::get_right(p)); + BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_left || node_traits::get_color(p_left) == node_traits::black()); + BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_right || node_traits::get_color(p_right) == node_traits::black()); + //Red node can't be root + BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_parent(node_traits::get_parent(p)) != p); } + //Every path to p contains the same number of black nodes + const std::size_t l_black_count = check_return_left.black_count_; + BOOST_INTRUSIVE_INVARIANT_ASSERT(l_black_count == check_return_right.black_count_); + check_return.black_count_ = l_black_count + + static_cast<std::size_t>(node_traits::get_color(p) == node_traits::black()); base_checker_t::operator()(p, check_return_left, check_return_right, check_return); } }; @@ -186,7 +201,7 @@ class rbtree_algorithms //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree static void swap_tree(const node_ptr & header1, const node_ptr & header2); - + #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&) diff --git a/boost/intrusive/set.hpp b/boost/intrusive/set.hpp index b8366a2e80..1048429005 100644 --- a/boost/intrusive/set.hpp +++ b/boost/intrusive/set.hpp @@ -13,10 +13,6 @@ #ifndef BOOST_INTRUSIVE_SET_HPP #define BOOST_INTRUSIVE_SET_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -25,6 +21,10 @@ #include <boost/move/utility_core.hpp> #include <boost/static_assert.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -97,12 +97,12 @@ class set_impl //! @copydoc ::boost::intrusive::rbtree::rbtree(rbtree &&) set_impl(BOOST_RV_REF(set_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::rbtree::operator=(rbtree &&) set_impl& operator=(BOOST_RV_REF(set_impl) x) - { return static_cast<set_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::rbtree::~rbtree() @@ -174,7 +174,7 @@ class set_impl //! @copydoc ::boost::intrusive::rbtree::clone_from template <class Cloner, class Disposer> void clone_from(const set_impl &src, Cloner cloner, Disposer disposer); - + #endif //#ifdef BOOST_iNTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::rbtree::insert_unique(reference) @@ -268,7 +268,7 @@ class set_impl //! @copydoc ::boost::intrusive::rbtree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::rbtree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -418,15 +418,13 @@ struct make_set typedef typename detail::get_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 set_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -479,11 +477,11 @@ class set {} set(BOOST_RV_REF(set) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} set& operator=(BOOST_RV_REF(set) x) - { return static_cast<set &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<set &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static set &container_from_end_iterator(iterator end_iterator) { return static_cast<set &>(Base::container_from_end_iterator(end_iterator)); } @@ -569,12 +567,12 @@ class multiset_impl //! @copydoc ::boost::intrusive::rbtree::rbtree(rbtree &&) multiset_impl(BOOST_RV_REF(multiset_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::rbtree::operator=(rbtree &&) multiset_impl& operator=(BOOST_RV_REF(multiset_impl) x) - { return static_cast<multiset_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::rbtree::~rbtree() @@ -717,7 +715,7 @@ class multiset_impl //! @copydoc ::boost::intrusive::rbtree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::rbtree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -859,15 +857,13 @@ struct make_multiset typedef typename detail::get_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 multiset_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -921,11 +917,11 @@ class multiset {} multiset(BOOST_RV_REF(multiset) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} multiset& operator=(BOOST_RV_REF(multiset) x) - { return static_cast<multiset &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<multiset &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static multiset &container_from_end_iterator(iterator end_iterator) { return static_cast<multiset &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/set_hook.hpp b/boost/intrusive/set_hook.hpp index ce984a305e..b641280878 100644 --- a/boost/intrusive/set_hook.hpp +++ b/boost/intrusive/set_hook.hpp @@ -14,10 +14,6 @@ #ifndef BOOST_INTRUSIVE_SET_HOOK_HPP #define BOOST_INTRUSIVE_SET_HOOK_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -26,6 +22,10 @@ #include <boost/intrusive/options.hpp> #include <boost/intrusive/detail/generic_hook.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { diff --git a/boost/intrusive/sg_set.hpp b/boost/intrusive/sg_set.hpp index 6c1477ad3f..7e250cb6a0 100644 --- a/boost/intrusive/sg_set.hpp +++ b/boost/intrusive/sg_set.hpp @@ -12,10 +12,6 @@ #ifndef BOOST_INTRUSIVE_SG_SET_HPP #define BOOST_INTRUSIVE_SG_SET_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/mpl.hpp> @@ -23,6 +19,10 @@ #include <boost/static_assert.hpp> #include <boost/move/utility_core.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -95,12 +95,12 @@ class sg_set_impl //! @copydoc ::boost::intrusive::sgtree::sgtree(sgtree &&) sg_set_impl(BOOST_RV_REF(sg_set_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::sgtree::operator=(sgtree &&) sg_set_impl& operator=(BOOST_RV_REF(sg_set_impl) x) - { return static_cast<sg_set_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<sg_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::sgtree::~sgtree() @@ -172,7 +172,7 @@ class sg_set_impl //! @copydoc ::boost::intrusive::sgtree::clone_from template <class Cloner, class Disposer> void clone_from(const sg_set_impl &src, Cloner cloner, Disposer disposer); - + #endif //#ifdef BOOST_iNTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::sgtree::insert_unique(reference) @@ -266,7 +266,7 @@ class sg_set_impl //! @copydoc ::boost::intrusive::sgtree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::sgtree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -429,15 +429,13 @@ struct make_sg_set typedef typename detail::get_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 sg_set_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::floating_point - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -490,11 +488,11 @@ class sg_set {} sg_set(BOOST_RV_REF(sg_set) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} sg_set& operator=(BOOST_RV_REF(sg_set) x) - { return static_cast<sg_set &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<sg_set &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static sg_set &container_from_end_iterator(iterator end_iterator) { return static_cast<sg_set &>(Base::container_from_end_iterator(end_iterator)); } @@ -580,12 +578,12 @@ class sg_multiset_impl //! @copydoc ::boost::intrusive::sgtree::sgtree(sgtree &&) sg_multiset_impl(BOOST_RV_REF(sg_multiset_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::sgtree::operator=(sgtree &&) sg_multiset_impl& operator=(BOOST_RV_REF(sg_multiset_impl) x) - { return static_cast<sg_multiset_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<sg_multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::sgtree::~sgtree() @@ -725,10 +723,10 @@ class sg_multiset_impl //! @copydoc ::boost::intrusive::sgtree::count(const KeyType&,KeyValueCompare)const template<class KeyType, class KeyValueCompare> size_type count(const KeyType& key, KeyValueCompare comp) const; - + //! @copydoc ::boost::intrusive::sgtree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::sgtree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -883,15 +881,13 @@ struct make_sg_multiset typedef typename detail::get_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 sg_multiset_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::floating_point - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -945,11 +941,11 @@ class sg_multiset {} sg_multiset(BOOST_RV_REF(sg_multiset) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} sg_multiset& operator=(BOOST_RV_REF(sg_multiset) x) - { return static_cast<sg_multiset &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<sg_multiset &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static sg_multiset &container_from_end_iterator(iterator end_iterator) { return static_cast<sg_multiset &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/sgtree.hpp b/boost/intrusive/sgtree.hpp index 5df70f84b5..feeaf3bcbf 100644 --- a/boost/intrusive/sgtree.hpp +++ b/boost/intrusive/sgtree.hpp @@ -18,18 +18,8 @@ #ifndef BOOST_INTRUSIVE_SGTREE_HPP #define BOOST_INTRUSIVE_SGTREE_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> -#include <algorithm> -#include <cstddef> -#include <functional> -#include <utility> -#include <cmath> -#include <cstddef> #include <boost/intrusive/detail/assert.hpp> #include <boost/static_assert.hpp> #include <boost/intrusive/bs_set_hook.hpp> @@ -42,7 +32,19 @@ #include <boost/intrusive/sgtree_algorithms.hpp> #include <boost/intrusive/detail/key_nodeptr_comp.hpp> #include <boost/intrusive/link_mode.hpp> + #include <boost/move/utility_core.hpp> +#include <boost/move/adl_move_swap.hpp> + +#include <cstddef> +#include <boost/intrusive/detail/minimal_less_equal_header.hpp> +#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair +#include <cmath> +#include <cstddef> + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -105,7 +107,6 @@ struct h_alpha_t // floor(log2(n)/-log2(alpha)) // floor(log2(n)*(1/-log2(alpha))) //////////////////////////////////////////////////////////// - //return static_cast<std::size_t>(std::log(float(n))*inv_minus_logalpha_); return static_cast<std::size_t>(detail::fast_log2(float(n))*inv_minus_logalpha_); } @@ -150,7 +151,7 @@ struct alpha_holder } h_alpha_t get_h_alpha_t() const - { return h_alpha_t(/*alpha_, */inv_minus_logalpha_); } + { return h_alpha_t(inv_minus_logalpha_); } multiply_by_alpha_t get_multiply_by_alpha_t() const { return multiply_by_alpha_t(alpha_); } @@ -233,7 +234,7 @@ class sgtree_impl typedef ValueTraits value_traits; /// @cond typedef bstree_impl< ValueTraits, VoidOrKeyComp, SizeType - , true, SgTreeAlgorithms, HeaderHolder> tree_type; + , true, SgTreeAlgorithms, HeaderHolder> tree_type; typedef tree_type implementation_defined; /// @endcond @@ -304,14 +305,14 @@ class sgtree_impl //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) sgtree_impl(BOOST_RV_REF(sgtree_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))), alpha_traits(x.get_alpha_traits()) - { std::swap(this->get_alpha_traits(), x.get_alpha_traits()); } + : tree_type(BOOST_MOVE_BASE(tree_type, x)), alpha_traits(x.get_alpha_traits()) + { ::boost::adl_move_swap(this->get_alpha_traits(), x.get_alpha_traits()); } //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) sgtree_impl& operator=(BOOST_RV_REF(sgtree_impl) x) { this->get_alpha_traits() = x.get_alpha_traits(); - return static_cast<sgtree_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); + return static_cast<sgtree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } /// @cond @@ -403,9 +404,8 @@ class sgtree_impl void swap(sgtree_impl& other) { //This can throw - using std::swap; this->tree_type::swap(static_cast<tree_type&>(other)); - swap(this->get_alpha_traits(), other.get_alpha_traits()); + ::boost::adl_move_swap(this->get_alpha_traits(), other.get_alpha_traits()); } //! @copydoc ::boost::intrusive::bstree::clone_from @@ -692,7 +692,7 @@ class sgtree_impl //! @copydoc ::boost::intrusive::bstree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -898,15 +898,13 @@ struct make_sgtree typedef typename detail::get_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 sgtree_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::floating_point - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -963,11 +961,11 @@ class sgtree {} sgtree(BOOST_RV_REF(sgtree) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} sgtree& operator=(BOOST_RV_REF(sgtree) x) - { return static_cast<sgtree &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<sgtree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static sgtree &container_from_end_iterator(iterator end_iterator) { return static_cast<sgtree &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/sgtree_algorithms.hpp b/boost/intrusive/sgtree_algorithms.hpp index cb5f71cffd..2d741841e1 100644 --- a/boost/intrusive/sgtree_algorithms.hpp +++ b/boost/intrusive/sgtree_algorithms.hpp @@ -17,10 +17,6 @@ #ifndef BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP #define BOOST_INTRUSIVE_SGTREE_ALGORITHMS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -28,7 +24,9 @@ #include <boost/intrusive/detail/algo_type.hpp> #include <boost/intrusive/bstree_algorithms.hpp> - +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -320,12 +318,12 @@ class sgtree_algorithms if(tree_size > max_tree_size) max_tree_size = tree_size; - if(tree_size > 2 && //Nothing to do with only the root + if(tree_size > 2 && //Nothing to do with only the root //Check if the root node is unbalanced //Scapegoat paper depth counts root depth as zero and "depth" counts root as 1, //but since "depth" is the depth of the ancestor of x, i == depth depth > h_alpha(tree_size)){ - + //Find the first non height-balanced node //as described in the section 4.2 of the paper. //This method is the alternative method described diff --git a/boost/intrusive/slist.hpp b/boost/intrusive/slist.hpp index 4698730d8d..757508149b 100644 --- a/boost/intrusive/slist.hpp +++ b/boost/intrusive/slist.hpp @@ -14,10 +14,6 @@ #ifndef BOOST_INTRUSIVE_SLIST_HPP #define BOOST_INTRUSIVE_SLIST_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -32,6 +28,7 @@ #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> @@ -39,14 +36,18 @@ #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 <functional> -#include <algorithm> +#include <boost/intrusive/detail/minimal_less_equal_header.hpp>//std::less #include <cstddef> //std::size_t -#include <utility> //std::pair +#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -139,7 +140,8 @@ class slist_impl 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 HeaderHolder header_holder_type; + 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<value_traits>::value; @@ -313,7 +315,7 @@ class slist_impl //! //! <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). @@ -907,7 +909,7 @@ class slist_impl } //! <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, @@ -975,7 +977,7 @@ class slist_impl { 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, @@ -1265,7 +1267,7 @@ class slist_impl //! <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. @@ -1350,7 +1352,7 @@ class slist_impl //! <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. @@ -1712,7 +1714,7 @@ class slist_impl static const_iterator s_iterator_to(const_reference value) { BOOST_STATIC_ASSERT((!stateful_value_traits)); - reference r =*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value)); + reference r =*detail::uncast(pointer_traits<const_pointer>::pointer_to(value)); return const_iterator(value_traits::to_node_ptr(r), const_value_traits_ptr()); } @@ -1742,7 +1744,7 @@ class slist_impl //! <b>Note</b>: Iterators and references are not invalidated. const_iterator iterator_to(const_reference value) const { - reference r =*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value)); + 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()); } @@ -1828,7 +1830,7 @@ class slist_impl //! <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. @@ -1847,7 +1849,7 @@ class slist_impl if(n){ BOOST_INTRUSIVE_INVARIANT_ASSERT(n > 0); BOOST_INTRUSIVE_INVARIANT_ASSERT - (size_type(std::distance + (size_type(boost::intrusive::iterator_distance ( iterator(f, this->priv_value_traits_ptr()) , iterator(before_l, this->priv_value_traits_ptr()))) +1 == n); @@ -2054,7 +2056,7 @@ inline bool operator< ( 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> @@ -2070,30 +2072,11 @@ bool operator== #endif { typedef slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> slist_type; - typedef typename slist_type::const_iterator const_iterator; 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) @@ -2184,17 +2167,16 @@ struct make_slist Options... #endif >::type packed_options; + typedef typename detail::get_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 slist_impl < value_traits , typename packed_options::size_type , (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) - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -2253,11 +2235,11 @@ class slist {} 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)); } diff --git a/boost/intrusive/slist_hook.hpp b/boost/intrusive/slist_hook.hpp index 18b59ed792..eac27370ec 100644 --- a/boost/intrusive/slist_hook.hpp +++ b/boost/intrusive/slist_hook.hpp @@ -14,10 +14,6 @@ #ifndef BOOST_INTRUSIVE_SLIST_HOOK_HPP #define BOOST_INTRUSIVE_SLIST_HOOK_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -27,6 +23,10 @@ #include <boost/intrusive/options.hpp> #include <boost/intrusive/detail/generic_hook.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { diff --git a/boost/intrusive/splay_set.hpp b/boost/intrusive/splay_set.hpp index cefc7926a2..80887dffdc 100644 --- a/boost/intrusive/splay_set.hpp +++ b/boost/intrusive/splay_set.hpp @@ -12,10 +12,6 @@ #ifndef BOOST_INTRUSIVE_SPLAY_SET_HPP #define BOOST_INTRUSIVE_SPLAY_SET_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/splaytree.hpp> @@ -23,6 +19,10 @@ #include <boost/move/utility_core.hpp> #include <boost/static_assert.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -95,12 +95,12 @@ class splay_set_impl //! @copydoc ::boost::intrusive::splaytree::splaytree(splaytree &&) splay_set_impl(BOOST_RV_REF(splay_set_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::splaytree::operator=(splaytree &&) splay_set_impl& operator=(BOOST_RV_REF(splay_set_impl) x) - { return static_cast<splay_set_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<splay_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::splaytree::~splaytree() @@ -172,7 +172,7 @@ class splay_set_impl //! @copydoc ::boost::intrusive::splaytree::clone_from template <class Cloner, class Disposer> void clone_from(const splay_set_impl &src, Cloner cloner, Disposer disposer); - + #endif //#ifdef BOOST_iNTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::splaytree::insert_unique(reference) @@ -273,7 +273,7 @@ class splay_set_impl //! @copydoc ::boost::intrusive::splaytree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::splaytree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -388,7 +388,7 @@ class splay_set_impl //! @copydoc ::boost::intrusive::splaytree::splay_down(const_reference) iterator splay_down(const_reference value); - + //! @copydoc ::boost::intrusive::splaytree::rebalance void rebalance(); @@ -439,15 +439,13 @@ struct make_splay_set typedef typename detail::get_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 splay_set_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -738,7 +736,7 @@ class splay_multiset_impl //! @copydoc ::boost::intrusive::splaytree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::splaytree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -845,7 +843,7 @@ class splay_multiset_impl //! @copydoc ::boost::intrusive::splaytree::splay_down(const_reference) iterator splay_down(const_reference value); - + //! @copydoc ::boost::intrusive::splaytree::rebalance void rebalance(); @@ -896,15 +894,13 @@ struct make_splay_multiset typedef typename detail::get_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 splay_multiset_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; diff --git a/boost/intrusive/splaytree.hpp b/boost/intrusive/splaytree.hpp index 67046426c8..e3866aa912 100644 --- a/boost/intrusive/splaytree.hpp +++ b/boost/intrusive/splaytree.hpp @@ -12,15 +12,11 @@ #ifndef BOOST_INTRUSIVE_SPLAYTREE_HPP #define BOOST_INTRUSIVE_SPLAYTREE_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <cstddef> -#include <functional> -#include <utility> +#include <boost/intrusive/detail/minimal_less_equal_header.hpp> +#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair #include <boost/static_assert.hpp> #include <boost/intrusive/bstree.hpp> @@ -34,6 +30,10 @@ #include <boost/intrusive/detail/key_nodeptr_comp.hpp> #include <boost/move/utility_core.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -78,7 +78,7 @@ class splaytree_impl /// @cond typedef bstree_impl< ValueTraits, VoidOrKeyComp, SizeType , ConstantTimeSize, SplayTreeAlgorithms - , HeaderHolder> tree_type; + , HeaderHolder> tree_type; typedef tree_type implementation_defined; /// @endcond @@ -136,12 +136,12 @@ class splaytree_impl //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) splaytree_impl(BOOST_RV_REF(splaytree_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&) splaytree_impl& operator=(BOOST_RV_REF(splaytree_impl) x) - { return static_cast<splaytree_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<splaytree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::bstree::~bstree() @@ -533,15 +533,13 @@ struct make_splaytree typedef typename detail::get_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 splaytree_impl < value_traits , typename packed_options::compare , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -598,11 +596,11 @@ class splaytree {} splaytree(BOOST_RV_REF(splaytree) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} splaytree& operator=(BOOST_RV_REF(splaytree) x) - { return static_cast<splaytree &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<splaytree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static splaytree &container_from_end_iterator(iterator end_iterator) { return static_cast<splaytree &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/splaytree_algorithms.hpp b/boost/intrusive/splaytree_algorithms.hpp index c49714a1d7..1c6afdf63c 100644 --- a/boost/intrusive/splaytree_algorithms.hpp +++ b/boost/intrusive/splaytree_algorithms.hpp @@ -30,10 +30,6 @@ #ifndef BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP #define BOOST_INTRUSIVE_SPLAYTREE_ALGORITHMS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/assert.hpp> @@ -43,6 +39,10 @@ #include <cstddef> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -86,7 +86,7 @@ struct splaydown_assemble_and_fix_header // left(t), right(t) := right(null), left(null); //end assemble; { // left(r), right(l) := right(t), left(t); - + node_ptr const old_t_left = NodeTraits::get_left(t_); node_ptr const old_t_right = NodeTraits::get_right(t_); NodeTraits::set_right(l_, old_t_left); @@ -222,7 +222,7 @@ class splaytree_algorithms //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(const node_ptr&) static void init_header(const node_ptr & header); - + #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&) @@ -233,21 +233,21 @@ class splaytree_algorithms if(NodeTraits::get_left(z)){ splay_up(bstree_algo::prev_node(z), header); } - /* + //possibility 2 - if(NodeTraits::get_left(z)){ - node_ptr l = NodeTraits::get_left(z); - splay_up(l, header); - }*/ - /* - if(NodeTraits::get_left(z)){ - node_ptr l = bstree_algo::prev_node(z); - splay_up_impl(l, z); - }*/ - /* + //if(NodeTraits::get_left(z)){ + // node_ptr l = NodeTraits::get_left(z); + // splay_up(l, header); + //} + + //if(NodeTraits::get_left(z)){ + // node_ptr l = bstree_algo::prev_node(z); + // splay_up_impl(l, z); + //} + //possibility 4 - splay_up(z, header); - */ + //splay_up(z, header); + bstree_algo::erase(header, z); } diff --git a/boost/intrusive/treap.hpp b/boost/intrusive/treap.hpp index b3afb864be..bf374696fb 100644 --- a/boost/intrusive/treap.hpp +++ b/boost/intrusive/treap.hpp @@ -12,19 +12,10 @@ #ifndef BOOST_INTRUSIVE_TREAP_HPP #define BOOST_INTRUSIVE_TREAP_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> -#include <algorithm> -#include <cstddef> -#include <functional> -#include <utility> #include <boost/intrusive/detail/assert.hpp> -#include <boost/static_assert.hpp> #include <boost/intrusive/bs_set_hook.hpp> #include <boost/intrusive/bstree.hpp> #include <boost/intrusive/detail/tree_node.hpp> @@ -34,11 +25,22 @@ #include <boost/intrusive/detail/mpl.hpp> #include <boost/intrusive/treap_algorithms.hpp> #include <boost/intrusive/link_mode.hpp> -#include <boost/move/utility_core.hpp> #include <boost/intrusive/priority_compare.hpp> #include <boost/intrusive/detail/node_cloner_disposer.hpp> #include <boost/intrusive/detail/key_nodeptr_comp.hpp> +#include <boost/static_assert.hpp> +#include <boost/move/utility_core.hpp> +#include <boost/move/adl_move_swap.hpp> + +#include <cstddef> +#include <boost/intrusive/detail/minimal_less_equal_header.hpp> +#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -77,6 +79,7 @@ template<class ValueTraits, class VoidOrKeyComp, class VoidOrPrioComp, class Siz class treap_impl /// @cond : public bstree_impl<ValueTraits, VoidOrKeyComp, SizeType, ConstantTimeSize, BsTreeAlgorithms, HeaderHolder> + //Use public inheritance to avoid MSVC bugs with closures , public detail::ebo_functor_holder < typename get_prio < VoidOrPrioComp @@ -90,7 +93,7 @@ class treap_impl /// @cond typedef bstree_impl< ValueTraits, VoidOrKeyComp, SizeType , ConstantTimeSize, BsTreeAlgorithms - , HeaderHolder> tree_type; + , HeaderHolder> tree_type; typedef tree_type implementation_defined; typedef get_prio < VoidOrPrioComp @@ -100,7 +103,7 @@ class treap_impl <typename get_prio_type::type> prio_base; /// @endcond - + typedef typename implementation_defined::pointer pointer; typedef typename implementation_defined::const_pointer const_pointer; typedef typename implementation_defined::value_type value_type; @@ -184,7 +187,7 @@ class treap_impl //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&) treap_impl(BOOST_RV_REF(treap_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) , prio_base(::boost::move(x.priv_pcomp())) {} @@ -329,8 +332,7 @@ class treap_impl { tree_type::swap(other); //This can throw - using std::swap; - swap(this->priv_pcomp(), other.priv_pcomp()); + ::boost::adl_move_swap(this->priv_pcomp(), other.priv_pcomp()); } //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. @@ -710,7 +712,7 @@ class treap_impl this->tree_type::sz_traits().increment(); } - //! <b>Effects</b>: Erases the element pointed to by pos. + //! <b>Effects</b>: Erases the element pointed to by i. //! //! <b>Complexity</b>: Average complexity for erase element is constant time. //! @@ -786,7 +788,7 @@ class treap_impl //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. //! - //! <b>Effects</b>: Erases the element pointed to by pos. + //! <b>Effects</b>: Erases the element pointed to by i. //! Disposer::operator()(pointer) is called for the removed element. //! //! <b>Complexity</b>: Average complexity for erase element is constant time. @@ -930,7 +932,7 @@ class treap_impl //! @copydoc ::boost::intrusive::bstree::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -1096,8 +1098,6 @@ struct make_treap typedef typename detail::get_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 treap_impl < value_traits @@ -1105,7 +1105,7 @@ struct make_treap , typename packed_options::priority , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -1164,11 +1164,11 @@ class treap {} treap(BOOST_RV_REF(treap) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} treap& operator=(BOOST_RV_REF(treap) x) - { return static_cast<treap&>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<treap&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static treap &container_from_end_iterator(iterator end_iterator) { return static_cast<treap &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/treap_algorithms.hpp b/boost/intrusive/treap_algorithms.hpp index 787c3d0bac..006a880d15 100644 --- a/boost/intrusive/treap_algorithms.hpp +++ b/boost/intrusive/treap_algorithms.hpp @@ -13,10 +13,6 @@ #ifndef BOOST_INTRUSIVE_TREAP_ALGORITHMS_HPP #define BOOST_INTRUSIVE_TREAP_ALGORITHMS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -25,8 +21,10 @@ #include <boost/intrusive/detail/assert.hpp> #include <boost/intrusive/detail/algo_type.hpp> #include <boost/intrusive/bstree_algorithms.hpp> -#include <algorithm> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { diff --git a/boost/intrusive/treap_set.hpp b/boost/intrusive/treap_set.hpp index ef68b0595e..a88df58e44 100644 --- a/boost/intrusive/treap_set.hpp +++ b/boost/intrusive/treap_set.hpp @@ -12,10 +12,6 @@ #ifndef BOOST_INTRUSIVE_TREAP_SET_HPP #define BOOST_INTRUSIVE_TREAP_SET_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/treap.hpp> @@ -23,6 +19,10 @@ #include <boost/move/utility_core.hpp> #include <boost/static_assert.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -101,7 +101,7 @@ class treap_set_impl //! [b, e). //! //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using - //! comp and otherwise N * log N, where N is std::distance(last, first). + //! comp and otherwise N * log N, where N is distance(last, first). //! //! <b>Throws</b>: If value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) @@ -117,13 +117,13 @@ class treap_set_impl //! <b>Effects</b>: to-do //! treap_set_impl(BOOST_RV_REF(treap_set_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! <b>Effects</b>: to-do //! treap_set_impl& operator=(BOOST_RV_REF(treap_set_impl) x) - { return static_cast<treap_set_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<treap_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::treap::~treap() @@ -311,7 +311,7 @@ class treap_set_impl //! @copydoc ::boost::intrusive::treap::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -443,8 +443,6 @@ struct make_treap_set typedef typename detail::get_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 treap_set_impl < value_traits @@ -452,7 +450,7 @@ struct make_treap_set , typename packed_options::priority , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -509,11 +507,11 @@ class treap_set {} treap_set(BOOST_RV_REF(treap_set) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} treap_set& operator=(BOOST_RV_REF(treap_set) x) - { return static_cast<treap_set &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<treap_set &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static treap_set &container_from_end_iterator(iterator end_iterator) { return static_cast<treap_set &>(Base::container_from_end_iterator(end_iterator)); } @@ -604,7 +602,7 @@ class treap_multiset_impl //! [b, e). //! //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using - //! comp and otherwise N * log N, where N is std::distance(last, first). + //! comp and otherwise N * log N, where N is distance(last, first). //! //! <b>Throws</b>: If value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) @@ -620,13 +618,13 @@ class treap_multiset_impl //! <b>Effects</b>: to-do //! treap_multiset_impl(BOOST_RV_REF(treap_multiset_impl) x) - : tree_type(::boost::move(static_cast<tree_type&>(x))) + : tree_type(BOOST_MOVE_BASE(tree_type, x)) {} //! <b>Effects</b>: to-do //! treap_multiset_impl& operator=(BOOST_RV_REF(treap_multiset_impl) x) - { return static_cast<treap_multiset_impl&>(tree_type::operator=(::boost::move(static_cast<tree_type&>(x)))); } + { return static_cast<treap_multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! @copydoc ::boost::intrusive::treap::~treap() @@ -786,10 +784,10 @@ class treap_multiset_impl //! @copydoc ::boost::intrusive::treap::count(const KeyType&,KeyValueCompare)const template<class KeyType, class KeyValueCompare> size_type count(const KeyType& key, KeyValueCompare comp) const; - + //! @copydoc ::boost::intrusive::treap::lower_bound(const_reference) iterator lower_bound(const_reference value); - + //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyValueCompare) template<class KeyType, class KeyValueCompare> iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -913,8 +911,6 @@ struct make_treap_multiset typedef typename detail::get_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 treap_multiset_impl < value_traits @@ -922,7 +918,7 @@ struct make_treap_multiset , typename packed_options::priority , typename packed_options::size_type , packed_options::constant_time_size - , header_holder_type + , typename packed_options::header_holder_type > implementation_defined; /// @endcond typedef implementation_defined type; @@ -979,11 +975,11 @@ class treap_multiset {} treap_multiset(BOOST_RV_REF(treap_multiset) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} treap_multiset& operator=(BOOST_RV_REF(treap_multiset) x) - { return static_cast<treap_multiset &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<treap_multiset &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static treap_multiset &container_from_end_iterator(iterator end_iterator) { return static_cast<treap_multiset &>(Base::container_from_end_iterator(end_iterator)); } diff --git a/boost/intrusive/trivial_value_traits.hpp b/boost/intrusive/trivial_value_traits.hpp index 18d28be92c..03deb162d6 100644 --- a/boost/intrusive/trivial_value_traits.hpp +++ b/boost/intrusive/trivial_value_traits.hpp @@ -13,15 +13,15 @@ #ifndef BOOST_INTRUSIVE_TRIVIAL_VALUE_TRAITS_HPP #define BOOST_INTRUSIVE_TRIVIAL_VALUE_TRAITS_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/link_mode.hpp> #include <boost/intrusive/pointer_traits.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { diff --git a/boost/intrusive/unordered_set.hpp b/boost/intrusive/unordered_set.hpp index e47f3baaaf..4b0c91e741 100644 --- a/boost/intrusive/unordered_set.hpp +++ b/boost/intrusive/unordered_set.hpp @@ -13,16 +13,16 @@ #ifndef BOOST_INTRUSIVE_UNORDERED_SET_HPP #define BOOST_INTRUSIVE_UNORDERED_SET_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/hashtable.hpp> #include <boost/move/utility_core.hpp> #include <boost/static_assert.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -134,7 +134,7 @@ class unordered_set_impl //! <b>Effects</b>: Constructs an empty unordered_set and inserts elements from //! [b, e). //! - //! <b>Complexity</b>: If N is std::distance(b, e): Average case is O(N) + //! <b>Complexity</b>: If N is distance(b, e): Average case is O(N) //! (with a good hash function and with buckets_len >= N),worst case O(N2). //! //! <b>Throws</b>: If value_traits::node_traits::node @@ -156,13 +156,13 @@ class unordered_set_impl //! <b>Effects</b>: to-do //! unordered_set_impl(BOOST_RV_REF(unordered_set_impl) x) - : table_type(::boost::move(static_cast<table_type&>(x))) + : table_type(BOOST_MOVE_BASE(table_type, x)) {} //! <b>Effects</b>: to-do //! unordered_set_impl& operator=(BOOST_RV_REF(unordered_set_impl) x) - { return static_cast<unordered_set_impl&>(table_type::operator=(::boost::move(static_cast<table_type&>(x)))); } + { return static_cast<unordered_set_impl&>(table_type::operator=(BOOST_MOVE_BASE(table_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED //! <b>Effects</b>: Detaches all elements from this. The objects in the unordered_set @@ -325,7 +325,7 @@ class unordered_set_impl //! //! <b>Effects</b>: Equivalent to this->insert(t) for each element in [b, e). //! - //! <b>Complexity</b>: Average case O(N), where N is std::distance(b, e). + //! <b>Complexity</b>: Average case O(N), where N is distance(b, e). //! Worst case O(N*this->size()). //! //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee. @@ -413,7 +413,7 @@ class unordered_set_impl //! <b>Effects</b>: Erases the range pointed to by b end e. //! - //! <b>Complexity</b>: Average case O(std::distance(b, e)), + //! <b>Complexity</b>: Average case O(distance(b, e)), //! worst case O(this->size()). //! //! <b>Throws</b>: Nothing. @@ -485,7 +485,7 @@ class unordered_set_impl //! <b>Effects</b>: Erases the range pointed to by b end e. //! Disposer::operator()(pointer) is called for the removed elements. //! - //! <b>Complexity</b>: Average case O(std::distance(b, e)), + //! <b>Complexity</b>: Average case O(distance(b, e)), //! worst case O(this->size()). //! //! <b>Throws</b>: Nothing. @@ -1110,11 +1110,11 @@ class unordered_set {} unordered_set(BOOST_RV_REF(unordered_set) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} unordered_set& operator=(BOOST_RV_REF(unordered_set) x) - { return static_cast<unordered_set&>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<unordered_set&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } }; #endif @@ -1227,7 +1227,7 @@ class unordered_multiset_impl //! <b>Effects</b>: Constructs an empty unordered_multiset and inserts elements from //! [b, e). //! - //! <b>Complexity</b>: If N is std::distance(b, e): Average case is O(N) + //! <b>Complexity</b>: If N is distance(b, e): Average case is O(N) //! (with a good hash function and with buckets_len >= N),worst case O(N2). //! //! <b>Throws</b>: If value_traits::node_traits::node @@ -1249,13 +1249,13 @@ class unordered_multiset_impl //! <b>Effects</b>: to-do //! unordered_multiset_impl(BOOST_RV_REF(unordered_multiset_impl) x) - : table_type(::boost::move(static_cast<table_type&>(x))) + : table_type(BOOST_MOVE_BASE(table_type, x)) {} //! <b>Effects</b>: to-do //! unordered_multiset_impl& operator=(BOOST_RV_REF(unordered_multiset_impl) x) - { return static_cast<unordered_multiset_impl&>(table_type::operator=(::boost::move(static_cast<table_type&>(x)))); } + { return static_cast<unordered_multiset_impl&>(table_type::operator=(BOOST_MOVE_BASE(table_type, x))); } #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED @@ -1442,7 +1442,7 @@ class unordered_multiset_impl //! <b>Effects</b>: Erases the range pointed to by b end e. //! - //! <b>Complexity</b>: Average case O(std::distance(b, e)), + //! <b>Complexity</b>: Average case O(distance(b, e)), //! worst case O(this->size()). //! //! <b>Throws</b>: Nothing. @@ -1521,7 +1521,7 @@ class unordered_multiset_impl //! <b>Effects</b>: Erases the range pointed to by b end e. //! Disposer::operator()(pointer) is called for the removed elements. //! - //! <b>Complexity</b>: Average case O(std::distance(b, e)), + //! <b>Complexity</b>: Average case O(distance(b, e)), //! worst case O(this->size()). //! //! <b>Throws</b>: Nothing. @@ -2146,11 +2146,11 @@ class unordered_multiset {} unordered_multiset(BOOST_RV_REF(unordered_multiset) x) - : Base(::boost::move(static_cast<Base&>(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} unordered_multiset& operator=(BOOST_RV_REF(unordered_multiset) x) - { return static_cast<unordered_multiset&>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + { return static_cast<unordered_multiset&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } }; #endif diff --git a/boost/intrusive/unordered_set_hook.hpp b/boost/intrusive/unordered_set_hook.hpp index 7406c9428d..95a575a9fc 100644 --- a/boost/intrusive/unordered_set_hook.hpp +++ b/boost/intrusive/unordered_set_hook.hpp @@ -14,10 +14,6 @@ #ifndef BOOST_INTRUSIVE_UNORDERED_SET_HOOK_HPP #define BOOST_INTRUSIVE_UNORDERED_SET_HOOK_HPP -#if defined(_MSC_VER) -# pragma once -#endif - #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/intrusive_fwd.hpp> @@ -26,6 +22,10 @@ #include <boost/intrusive/options.hpp> #include <boost/intrusive/detail/generic_hook.hpp> +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { |