From 733b5d5ae2c5d625211e2985ac25728ac3f54883 Mon Sep 17 00:00:00 2001 From: DongHun Kwak Date: Mon, 21 Mar 2016 15:45:20 +0900 Subject: Imported Upstream version 1.58.0 Change-Id: If0072143aa26874812e0db6872e1efb10a3e5e94 Signed-off-by: DongHun Kwak --- boost/intrusive/any_hook.hpp | 8 +- boost/intrusive/avl_set.hpp | 38 +- boost/intrusive/avl_set_hook.hpp | 8 +- boost/intrusive/avltree.hpp | 28 +- boost/intrusive/avltree_algorithms.hpp | 23 +- boost/intrusive/bs_set.hpp | 40 +- boost/intrusive/bs_set_hook.hpp | 8 +- boost/intrusive/bstree.hpp | 114 ++-- boost/intrusive/bstree_algorithms.hpp | 236 +++------ boost/intrusive/circular_list_algorithms.hpp | 79 +-- boost/intrusive/circular_slist_algorithms.hpp | 7 +- boost/intrusive/derivation_value_traits.hpp | 10 +- boost/intrusive/detail/algo_type.hpp | 6 +- boost/intrusive/detail/algorithm.hpp | 90 ++++ boost/intrusive/detail/any_node_and_algorithms.hpp | 32 +- boost/intrusive/detail/array_initializer.hpp | 9 +- boost/intrusive/detail/assert.hpp | 6 +- boost/intrusive/detail/avltree_node.hpp | 6 +- boost/intrusive/detail/bstree_algorithms_base.hpp | 184 +++++++ boost/intrusive/detail/common_slist_algorithms.hpp | 8 +- boost/intrusive/detail/default_header_holder.hpp | 34 +- boost/intrusive/detail/ebo_functor_holder.hpp | 12 +- boost/intrusive/detail/empty_node_checker.hpp | 6 +- boost/intrusive/detail/equal_to_value.hpp | 6 +- boost/intrusive/detail/exception_disposer.hpp | 6 +- boost/intrusive/detail/function_detector.hpp | 6 +- boost/intrusive/detail/generic_hook.hpp | 10 +- boost/intrusive/detail/get_value_traits.hpp | 6 +- .../detail/has_member_function_callable_with.hpp | 575 ++++++++++----------- boost/intrusive/detail/hashtable_node.hpp | 6 +- boost/intrusive/detail/hook_traits.hpp | 6 +- boost/intrusive/detail/iiterator.hpp | 122 +---- .../intrusive/detail/is_stateful_value_traits.hpp | 6 +- boost/intrusive/detail/iterator.hpp | 147 ++++++ boost/intrusive/detail/key_nodeptr_comp.hpp | 25 +- boost/intrusive/detail/list_iterator.hpp | 6 +- boost/intrusive/detail/list_node.hpp | 6 +- boost/intrusive/detail/math.hpp | 12 +- boost/intrusive/detail/memory_util.hpp | 92 ---- .../intrusive/detail/minimal_less_equal_header.hpp | 30 ++ boost/intrusive/detail/minimal_pair_header.hpp | 30 ++ boost/intrusive/detail/mpl.hpp | 72 ++- boost/intrusive/detail/node_cloner_disposer.hpp | 21 +- boost/intrusive/detail/node_holder.hpp | 6 +- boost/intrusive/detail/node_to_value.hpp | 6 +- boost/intrusive/detail/parent_from_member.hpp | 8 +- boost/intrusive/detail/pointer_element.hpp | 16 +- boost/intrusive/detail/preprocessor.hpp | 42 -- boost/intrusive/detail/rbtree_node.hpp | 6 +- boost/intrusive/detail/reverse_iterator.hpp | 22 +- boost/intrusive/detail/simple_disposers.hpp | 6 +- boost/intrusive/detail/size_holder.hpp | 6 +- boost/intrusive/detail/slist_iterator.hpp | 6 +- boost/intrusive/detail/slist_node.hpp | 6 +- boost/intrusive/detail/std_fwd.hpp | 13 +- boost/intrusive/detail/to_raw_pointer.hpp | 6 +- boost/intrusive/detail/transform_iterator.hpp | 16 +- boost/intrusive/detail/tree_iterator.hpp | 29 +- boost/intrusive/detail/tree_node.hpp | 6 +- boost/intrusive/detail/uncast.hpp | 6 +- boost/intrusive/detail/workaround.hpp | 16 +- boost/intrusive/hashtable.hpp | 65 +-- boost/intrusive/intrusive_fwd.hpp | 24 +- boost/intrusive/linear_slist_algorithms.hpp | 10 +- boost/intrusive/link_mode.hpp | 4 +- boost/intrusive/list.hpp | 67 +-- boost/intrusive/list_hook.hpp | 9 +- boost/intrusive/member_value_traits.hpp | 8 +- boost/intrusive/options.hpp | 15 +- boost/intrusive/pack_options.hpp | 12 +- boost/intrusive/parent_from_member.hpp | 8 +- boost/intrusive/pointer_plus_bits.hpp | 8 +- boost/intrusive/pointer_rebind.hpp | 18 +- boost/intrusive/pointer_traits.hpp | 93 +++- boost/intrusive/priority_compare.hpp | 14 +- boost/intrusive/rbtree.hpp | 34 +- boost/intrusive/rbtree_algorithms.hpp | 43 +- boost/intrusive/set.hpp | 38 +- boost/intrusive/set_hook.hpp | 8 +- boost/intrusive/sg_set.hpp | 40 +- boost/intrusive/sgtree.hpp | 46 +- boost/intrusive/sgtree_algorithms.hpp | 12 +- boost/intrusive/slist.hpp | 68 +-- boost/intrusive/slist_hook.hpp | 8 +- boost/intrusive/splay_set.hpp | 30 +- boost/intrusive/splaytree.hpp | 26 +- boost/intrusive/splaytree_algorithms.hpp | 38 +- boost/intrusive/treap.hpp | 46 +- boost/intrusive/treap_algorithms.hpp | 8 +- boost/intrusive/treap_set.hpp | 42 +- boost/intrusive/trivial_value_traits.hpp | 8 +- boost/intrusive/unordered_set.hpp | 38 +- boost/intrusive/unordered_set_hook.hpp | 8 +- 93 files changed, 1819 insertions(+), 1481 deletions(-) create mode 100644 boost/intrusive/detail/algorithm.hpp create mode 100644 boost/intrusive/detail/bstree_algorithms_base.hpp create mode 100644 boost/intrusive/detail/iterator.hpp delete mode 100644 boost/intrusive/detail/memory_util.hpp create mode 100644 boost/intrusive/detail/minimal_less_equal_header.hpp create mode 100644 boost/intrusive/detail/minimal_pair_header.hpp delete mode 100644 boost/intrusive/detail/preprocessor.hpp (limited to 'boost/intrusive') 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 #include #include @@ -25,6 +21,10 @@ #include #include +#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 #include #include @@ -23,6 +19,10 @@ #include #include +#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(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(tree_type::operator=(::boost::move(static_cast(x)))); } + { return static_cast(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 iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -418,15 +418,13 @@ struct make_avl_set typedef typename detail::get_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(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} avl_set& operator=(BOOST_RV_REF(avl_set) x) - { return static_cast(this->Base::operator=(::boost::move(static_cast(x)))); } + { return static_cast(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static avl_set &container_from_end_iterator(iterator end_iterator) { return static_cast(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(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(tree_type::operator=(::boost::move(static_cast(x)))); } + { return static_cast(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 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 iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -859,15 +857,13 @@ struct make_avl_multiset typedef typename detail::get_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(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} avl_multiset& operator=(BOOST_RV_REF(avl_multiset) x) - { return static_cast(this->Base::operator=(::boost::move(static_cast(x)))); } + { return static_cast(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static avl_multiset &container_from_end_iterator(iterator end_iterator) { return static_cast(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 #include @@ -25,6 +21,10 @@ #include #include +#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 #include #include -#include -#include +#include +#include #include #include @@ -35,6 +31,10 @@ #include #include +#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(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(tree_type::operator=(::boost::move(static_cast(x)))); } + { return static_cast(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 iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -455,15 +455,13 @@ struct make_avltree typedef typename detail::get_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(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} avltree& operator=(BOOST_RV_REF(avltree) x) - { return static_cast(this->Base::operator=(::boost::move(static_cast(x)))); } + { return static_cast(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static avltree &container_from_end_iterator(iterator end_iterator) { return static_cast(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 #include @@ -28,6 +24,11 @@ #include #include +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + + namespace boost { namespace intrusive { @@ -35,7 +36,8 @@ namespace intrusive { template struct avltree_node_cloner - : private detail::ebo_functor_holder + //Use public inheritance to avoid MSVC bugs with closures + : public detail::ebo_functor_holder { typedef typename NodeTraits::node_ptr node_ptr; typedef detail::ebo_functor_holder 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 #include #include @@ -23,6 +19,10 @@ #include #include +#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(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(tree_type::operator=(::boost::move(static_cast(x)))); } + { return static_cast(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 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 iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -416,15 +416,13 @@ struct make_bs_set typedef typename detail::get_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(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} bs_set& operator=(BOOST_RV_REF(bs_set) x) - { return static_cast(this->Base::operator=(::boost::move(static_cast(x)))); } + { return static_cast(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static bs_set &container_from_end_iterator(iterator end_iterator) { return static_cast(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(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(tree_type::operator=(::boost::move(static_cast(x)))); } + { return static_cast(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 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 iterator lower_bound(const KeyType& key, KeyValueCompare comp); @@ -857,15 +855,13 @@ struct make_bs_multiset typedef typename detail::get_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(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} bs_multiset& operator=(BOOST_RV_REF(bs_multiset) x) - { return static_cast(this->Base::operator=(::boost::move(static_cast(x)))); } + { return static_cast(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static bs_multiset &container_from_end_iterator(iterator end_iterator) { return static_cast(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 #include @@ -25,6 +21,10 @@ #include #include +#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 #include @@ -38,18 +34,22 @@ #include #include #include +#include #include #include #include #include #include +#include -#include //pair,lexicographical_compare -#include //swap +#include #include //size_t... -#include //less, equal_to +#include //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 iterator; typedef tree_iterator const_iterator; - typedef boost::intrusive::detail::reverse_iterator reverse_iterator; - typedef boost::intrusive::detail::reverse_iterator const_reverse_iterator; + typedef boost::intrusive::reverse_iterator reverse_iterator; + typedef boost::intrusive::reverse_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::element_type) value_type; @@ -94,7 +94,8 @@ struct bstbase3 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits::reference) reference; typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits::reference) const_reference; typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits::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; static const bool stateful_value_traits = detail::is_stateful_value_traits::value; @@ -227,13 +228,13 @@ struct bstbase3 }; template -struct get_less +struct get_compare { typedef Less type; }; template -struct get_less +struct get_compare { typedef ::std::less type; }; @@ -241,15 +242,16 @@ struct get_less template struct bstbase2 //Put the (possibly empty) functor in the first position to get EBO in MSVC - : public detail::ebo_functor_holder::type> , public bstbase3 { - typedef bstbase3 treeheader_t; + typedef bstbase3 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::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) reverse_iterator; - typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::detail::reverse_iterator) const_reverse_iterator; + typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::reverse_iterator) reverse_iterator; + typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::reverse_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 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, &this->get_value_traits()) ,detail::node_disposer(disposer, &this->get_value_traits())); this->sz_traits().set_size(src.sz_traits().get_size()); @@ -954,6 +955,41 @@ class bstree_impl } } + //! Requires: Disposer::operator()(pointer) shouldn't throw. + //! Cloner should yield to nodes equivalent to the original nodes. + //! + //! Effects: 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). + //! + //! Complexity: Linear to erased plus inserted elements. + //! + //! Throws: If cloner throws or predicate copy assignment throws. Basic guarantee. + //! + //! Note: This version can modify the source container, useful to implement + //! move semantics. + template + void clone_from(bstree_impl &src, Cloner cloner, Disposer disposer) + { + this->clear_and_dispose(disposer); + if(!src.empty()){ + detail::exception_disposer + rollback(*this, disposer); + node_algorithms::clone + (src.header_ptr() + ,this->header_ptr() + ,detail::node_cloner (cloner, &this->get_value_traits()) + ,detail::node_disposer(disposer, &this->get_value_traits())); + this->sz_traits().set_size(src.sz_traits().get_size()); + this->comp() = src.comp(); + rollback.release(); + } + } + //! Requires: value must be an lvalue //! //! Effects: 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); } - //! Effects: Erases the element pointed to by pos. + //! Effects: Erases the element pointed to by i. //! //! Complexity: Average complexity for erase element is constant time. //! @@ -1344,7 +1380,7 @@ class bstree_impl //! Requires: Disposer::operator()(pointer) shouldn't throw. //! - //! Effects: Erases the element pointed to by pos. + //! Effects: Erases the element pointed to by i. //! Disposer::operator()(pointer) is called for the removed element. //! //! Complexity: Average complexity for erase element is constant time. @@ -1951,7 +1987,7 @@ inline bool operator< ( const bstree_impl &x , const bstree_impl &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 @@ -1967,29 +2003,11 @@ bool operator== #endif { typedef bstree_impl 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 ::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(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} bstree& operator=(BOOST_RV_REF(bstree) x) - { return static_cast(this->Base::operator=(::boost::move(static_cast(x)))); } + { return static_cast(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static bstree &container_from_end_iterator(iterator end_iterator) { return static_cast(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 #include #include +#include #include #include #include #include -#include + +#include + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -167,7 +169,7 @@ struct bstree_node_checker //! //! static void set_right(node_ptr n, node_ptr right); template -class bstree_algorithms +class bstree_algorithms : public bstree_algorithms_base { public: typedef typename NodeTraits::node node; @@ -178,7 +180,8 @@ class bstree_algorithms typedef data_for_rebalance_t data_for_rebalance; /// @cond - + typedef bstree_algorithms this_type; + typedef bstree_algorithms_base base_type; private: template 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) //! Requires: 'node' is a node of the tree or a header node. //! //! Effects: Returns the header of the tree. @@ -254,42 +258,8 @@ class bstree_algorithms //! Complexity: Logarithmic. //! //! Throws: 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 //! Requires: 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); } //! Requires: node_to_be_replaced must be inserted in a tree @@ -541,6 +511,7 @@ class bstree_algorithms } } + #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) //! Requires: 'node' is a node from the tree except the header. //! //! Effects: Returns the next node of the tree. @@ -548,22 +519,7 @@ class bstree_algorithms //! Complexity: Average constant time. //! //! Throws: 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); //! Requires: 'node' is a node from the tree except the leftmost node. //! @@ -572,25 +528,7 @@ class bstree_algorithms //! Complexity: Average constant time. //! //! Throws: 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); //! Requires: 'node' is a node of a tree but not the header. //! @@ -599,15 +537,7 @@ class bstree_algorithms //! Complexity: Logarithmic to the size of the subtree. //! //! Throws: 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); //! Requires: 'node' is a node of a tree but not the header. //! @@ -616,15 +546,8 @@ class bstree_algorithms //! Complexity: Logarithmic to the size of the subtree. //! //! Throws: 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 //! Requires: '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) //! Requires: p is a node of a tree. //! //! Effects: Returns true if p is the header of the tree. @@ -807,22 +731,8 @@ class bstree_algorithms //! Complexity: Constant. //! //! Throws: 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 //! Requires: "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. //! //! Effects: 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 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 void disposer(const node_ptr &). //! - //! Complexity: Linear to the number of element of the source tree plus the. + //! Complexity: Linear to the number of element of the source tree plus the //! number of elements of tree target tree when calling this function. //! //! Throws: 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 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 #include #include #include #include +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -211,60 +211,6 @@ class circular_list_algorithms //! Complexity: Constant //! //! Throws: 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 #include #include #include #include +#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 #include #include #include +#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 +#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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +namespace boost { +namespace intrusive { + +struct algo_pred_equal +{ + template + bool operator()(const T &x, const T &y) const + { return x == y; } +}; + +struct algo_pred_less +{ + template + bool operator()(const T &x, const T &y) const + { return x < y; } +}; + +template +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 +bool algo_equal(InputIt1 first1, InputIt1 last1, InputIt2 first2) +{ return (algo_equal)(first1, last1, first2, algo_pred_equal()); } + +template +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 +bool algo_equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) +{ return (algo_equal)(first1, last1, first2, last2, algo_pred_equal()); } + +template + 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 + 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 +#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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif +#include #include 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 +#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 +#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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include + +namespace boost { +namespace intrusive { + +template +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; + + //! Requires: 'node' is a node from the tree except the header. + //! + //! Effects: Returns the next node of the tree. + //! + //! Complexity: Average constant time. + //! + //! Throws: 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; + } + } + + //! Requires: 'node' is a node from the tree except the leftmost node. + //! + //! Effects: Returns the previous node of the tree. + //! + //! Complexity: Average constant time. + //! + //! Throws: 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; + } + } + + //! Requires: 'node' is a node of a tree but not the header. + //! + //! Effects: Returns the minimum node of the subtree starting at p. + //! + //! Complexity: Logarithmic to the size of the subtree. + //! + //! Throws: 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; + } + + //! Requires: 'node' is a node of a tree but not the header. + //! + //! Effects: Returns the maximum node of the subtree starting at p. + //! + //! Complexity: Logarithmic to the size of the subtree. + //! + //! Throws: 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; + } + + //! Requires: p is a node of a tree. + //! + //! Effects: Returns true if p is the header of the tree. + //! + //! Complexity: Constant. + //! + //! Throws: 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; + } + + //! Requires: 'node' is a node of the tree or a header node. + //! + //! Effects: Returns the header of the tree. + //! + //! Complexity: Logarithmic. + //! + //! Throws: 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 +#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 +#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 #endif -#include +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -181,7 +183,7 @@ class ebo_functor_holder_impl public: ebo_functor_holder_impl() {} - ebo_functor_holder_impl(const T& t) + explicit ebo_functor_holder_impl(const T& t) : T(t) {} template @@ -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 +#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 +#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 +#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 +#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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -134,13 +138,13 @@ class generic_hook , typename NodeAlgorithms::node , node_holder >::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 - , detail::is_same::value*BaseHookType> + , detail::is_same::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 +#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 +#include +#include - #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 - #include - #include +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 +struct make_dontcare +{ + typedef dont_care type; +}; - struct dont_care - { - dont_care(...); - }; +#endif - template - 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 +no_type is_private_type(T const &); +yes_type is_private_type(private_type const &); - template - 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 struct remove_cv { typedef T type; }; +template struct remove_cv { typedef T type; }; +template struct remove_cv { typedef T type; }; +template struct remove_cv { 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 + struct BOOST_MOVE_CAT(has_member_function_callable_with_,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + { + template + static decltype(boost::move_detail::declval(). + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(::boost::move_detail::declval()...) + , boost_intrusive_hmfcw::yes_type()) Test(U* f); + template + static boost_intrusive_hmfcw::no_type Test(...); + static const bool value = sizeof(Test((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 + 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 + struct BOOST_MOVE_CAT(has_member_function_callable_with_,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + { + typedef FunWrapTmpl::type...> FunWrap; + + static bool const value = (sizeof(boost_intrusive_hmfcw::no_type) == + sizeof(boost_intrusive_hmfcw::is_private_type + ( (::boost::move_detail::declval< FunWrap >(). + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(::boost::move_detail::declval()...), 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 - 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, public BaseMixin { Base(); }; + struct Base : public boost_intrusive_hmfcw::remove_cv::type, public BaseMixin {}; template class Helper{}; template - static boost_intrusive_has_member_function_callable_with::no_type deduce + static boost_intrusive_hmfcw::no_type deduce (U*, Helper* = 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 - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME), _impl); - //! - - template - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME), _impl) - - { - static const bool value = false; - }; - //! - - #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - template - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl); - - template - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - - { - 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(). - 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 - struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) - { - 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 - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - - { - #ifndef BOOST_NO_CXX11_DECLTYPE - template().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME()) > - static boost_intrusive_has_member_function_callable_with::yes_type Test(U*); - #else - template - static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) - Test(BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)*); - #endif - - template - 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 - struct BOOST_PP_CAT( BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME), _impl) - - { - - template - 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::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()... ), 0) ) - ) - ); - }; + ///////////////////////////////////////////////////////// + ///////////////////////////////////////////////////////// + // + // has_member_function_callable_with_impl_XXX specializations + // + ///////////////////////////////////////////////////////// - template - 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 )::value - , Args... > - {}; + template + 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 - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - - { - //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(). - 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 - struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) - { - 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 - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - - { - template - static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) - Test(BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)*); - - template - static boost_intrusive_has_member_function_callable_with::no_type Test(...); + //No BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME member specialization + template + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + + { + 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 - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) { template - static decltype( boost::move_detail::declval().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().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME() + , boost_intrusive_hmfcw::yes_type()) Test(U* f); template - static boost_intrusive_has_member_function_callable_with::no_type Test(...); - - static const bool value = sizeof(Test(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*)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().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 - struct BOOST_PP_CAT( BOOST_PP_CAT(has_member_function_callable_with_ - , BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - - { - struct FunWrap : Fun + template + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) { - 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 static BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + Test(BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)*); + template 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(). - 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 - 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) - ::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 + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + {//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 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\ + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)\ + {\ + 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) >().\ + 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\ + struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)\ + \ + {\ + template\ + static decltype(boost::move_detail::declval().\ + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(BOOST_MOVE_DECLVAL##N)\ + , boost_intrusive_hmfcw::yes_type()) Test(U* f);\ + template\ + static boost_intrusive_hmfcw::no_type Test(...);\ + static const bool value = sizeof(Test((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 + 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) + ::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 +#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 +#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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif +#include #include #include #include -#include - -#include - namespace boost { namespace intrusive { -template -struct iterator -{ - typedef Category iterator_category; - typedef T value_type; - typedef Distance difference_type; - typedef Pointer pointer; - typedef Reference reference; -}; - -template -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 -struct iterator_traits -{ - 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 -struct iterator_traits -{ - 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 struct value_traits_pointers { typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT (boost::intrusive::detail:: , ValueTraits, value_traits_ptr - , typename pointer_traits::template + , typename boost::intrusive::pointer_traits::template rebind_pointer::type) value_traits_ptr; - typedef typename pointer_traits::template + typedef typename boost::intrusive::pointer_traits::template rebind_pointer::type const_value_traits_ptr; }; @@ -154,73 +115,6 @@ struct iiterator_members NodePtr nodeptr_; }; -namespace detail { - -template inline -void advance_impl(InputIt& it, Distance n, const std::input_iterator_tag&) -{ - while(n--) - ++it; -} - -template inline -void advance_impl(InputIt& it, Distance n, std::forward_iterator_tag &) -{ - while(n--) - ++it; -} - -template inline -void advance_impl(InputIt& it, Distance n, std::bidirectional_iterator_tag &) -{ - for (; 0 < n; --n) - ++it; - for (; n < 0; ++n) - --it; -} - -template -inline void advance_impl(InputIt& it, Distance n, const std::random_access_iterator_tag &) -{ - it += n; -} - -} //namespace detail - -template -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::iterator_category()); -} - -namespace detail{ - -template -inline void distance_impl(InputIt first, InputIt last, Distance& off, const Category &) -{ - while(first != last){ - ++off; - ++first; - } -} - -template inline -void distance_impl(InputIt first, InputIt last, Distance& off, const std::random_access_iterator_tag&) -{ - off += last - first; -} - -} //namespace detail - -template inline -typename iterator_traits::difference_type iterator_distance(InputIt first, InputIt last) -{ - typename iterator_traits::difference_type off = 0; - boost::intrusive::detail::distance_impl(first, last, off, boost::intrusive::iterator_traits::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 +#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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include +#include +#include +#include + +namespace boost { +namespace intrusive { + +using boost::movelib::iterator_traits; + +//////////////////// +// iterator +//////////////////// +template +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 +struct iterator_enable_if_tag + : ::boost::move_detail::enable_if_c + < ::boost::move_detail::is_same + < typename boost::intrusive::iterator_traits::iterator_category + , Tag + >::value + , R> +{}; + +template +struct iterator_disable_if_tag + : ::boost::move_detail::enable_if_c + < !::boost::move_detail::is_same + < typename boost::intrusive::iterator_traits::iterator_category + , Tag + >::value + , R> +{}; + +//////////////////////////////////////// +// iterator_[dis|en]able_if_tag_difference_type +//////////////////////////////////////// +template +struct iterator_enable_if_tag_difference_type + : iterator_enable_if_tag::difference_type> +{}; + +template +struct iterator_disable_if_tag_difference_type + : iterator_disable_if_tag::difference_type> +{}; + +//////////////////// +// advance +//////////////////// +template inline +typename iterator_enable_if_tag::type + iterator_advance(InputIt& it, Distance n) +{ + while(n--) + ++it; +} + +template inline +typename iterator_enable_if_tag::type + iterator_advance(InputIt& it, Distance n) +{ + while(n--) + ++it; +} + +template inline +typename iterator_enable_if_tag::type + iterator_advance(InputIt& it, Distance n) +{ + for (; 0 < n; --n) + ++it; + for (; n < 0; ++n) + --it; +} + +template inline +typename iterator_enable_if_tag::type + iterator_advance(InputIt& it, Distance n) +{ + it += n; +} + +//////////////////// +// distance +//////////////////// +template inline +typename iterator_disable_if_tag_difference_type + ::type + iterator_distance(InputIt first, InputIt last) +{ + typename iterator_traits::difference_type off = 0; + while(first != last){ + ++off; + ++first; + } + return off; +} + +template inline +typename iterator_enable_if_tag_difference_type + ::type + iterator_distance(InputIt first, InputIt last) +{ + typename iterator_traits::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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -26,7 +30,8 @@ namespace detail { template struct key_nodeptr_comp - : private ebo_functor_holder + //Use public inheritance to avoid MSVC bugs with closures + : public ebo_functor_holder { 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::value || is_same::value; }; + //key_forward template const value_type & key_forward (const T &node, typename enable_if_c::value>::type * = 0) const @@ -53,14 +59,23 @@ struct key_nodeptr_comp const T & key_forward(const T &key, typename enable_if_c::value>::type* = 0) const { return key; } + //operator() 1 arg + template + bool operator()(const KeyType &key1) const + { return base_t::get()(this->key_forward(key1)); } + template + bool operator()(const KeyType &key1) + { return base_t::get()(this->key_forward(key1)); } + + //operator() 2 arg template bool operator()(const KeyType &key1, const KeyType2 &key2) const { return base_t::get()(this->key_forward(key1), this->key_forward(key2)); } - template - bool operator()(const KeyType &key1) const - { return base_t::get()(this->key_forward(key1)); } + template + 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 +#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 +#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 +#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 + 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) { - 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 -#include -#include -#include - -namespace boost { -namespace intrusive { -namespace detail { - -template -inline T* addressof(T& obj) -{ - return static_cast - (static_cast - (const_cast - (&reinterpret_cast(obj)) - ) - ); -} - -template -struct LowPriorityConversion -{ - // Convertible from T with user-defined-conversion rank. - LowPriorityConversion(const T&) { } -}; - -}}} //namespace boost::intrusive::detail - -#include - -#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, )) -#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, )) -#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, )) -#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, )) -#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 +#endif +# +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif +# +#//Try to avoid including , as it's quite big in C++11 +#if defined(BOOST_GNU_STDLIB) +# include +#else +# include //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 +#endif +# +#//Try to avoid including , as it's quite big in C++11 +#if defined(BOOST_GNU_STDLIB) +# include +#else +# include //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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif @@ -315,7 +319,14 @@ template <> struct unvoid_ref { struct type_impl { }; typedef type_i ::boost::intrusive::detail::if_c \ ::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 \ struct boost_intrusive_eval_default_type_ ## TNAME \ { \ @@ -339,11 +350,6 @@ template <> struct unvoid_ref { 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 \ + class TRAITS_NAME \ + { \ + private: \ + template struct helper;\ + template \ + static ::boost::intrusive::detail::yes_type check(helper<&T::FUNC_NAME>*); \ + template static ::boost::intrusive::detail::no_type check(...); \ + public: \ + static const bool value = sizeof(check(0)) == sizeof(::boost::intrusive::detail::yes_type); \ + }; \ +// + +#define BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(TRAITS_NAME, FUNC_NAME) \ +template \ +struct TRAITS_NAME \ +{ \ + struct BaseMixin \ + { \ + void FUNC_NAME(); \ + }; \ + struct Base : public Type, public BaseMixin { Base(); }; \ + template class Helper{}; \ + template \ + static ::boost::intrusive::detail::no_type check(U*, Helper* = 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 \ +struct TRAITS_NAME \ + : public TRAITS_NAME##_ignore_signature \ +{};\ +// + + +template +inline T* addressof(T& obj) +{ + return static_cast + (static_cast + (const_cast + (&reinterpret_cast(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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif #include +#include #include #include #include @@ -26,9 +31,10 @@ namespace boost { namespace intrusive { namespace detail { -template +template struct node_cloner - : private ebo_functor_holder + //Use public inheritance to avoid MSVC bugs with closures + : public ebo_functor_holder { 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::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::pointer_to(to_clone)); node_ptr n = traits_->to_node_ptr(*base_t::get()(v)); @@ -78,7 +86,8 @@ struct node_cloner template struct node_disposer - : private ebo_functor_holder + //Use public inheritance to avoid MSVC bugs with closures + : public ebo_functor_holder { 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 +#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 +#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 +#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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif +#ifndef BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP #include +#endif //BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP namespace boost { namespace intrusive { @@ -118,14 +124,6 @@ template struct first_param < TemplateClass > { typedef T type; }; - template < template //10arg - 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 > - { typedef T type; }; - #endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template 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 -#include - -#include -#include -#include -#include -#include - - -#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 - -#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 +#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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif #include -#include +#include namespace boost { namespace intrusive { -namespace detail { template 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 -#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 +#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 +#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 +#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 +#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 +#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 +#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 +#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 +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif #include #include #include -#include +#include 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_algorithms; + static const bool stateful_value_traits = types_t::stateful_value_traits; - typedef bstree_algorithms 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 +#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 +#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 +#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 #include -//std C++ -#include //std::equal_to -#include //std::pair -#include //std::swap, std::lower_bound, std::upper_bound -#include //std::size_t -//boost -#include -#include -#include + //General intrusive utilities #include #include @@ -44,7 +32,23 @@ #include #include #include + +//boost +#include +#include +#include #include +#include + +//std C++ +#include //std::equal_to +#include //std::pair +#include //std::lower_bound, std::upper_bound +#include //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 struct node_cast_adaptor - : private detail::ebo_functor_holder + //Use public inheritance to avoid MSVC bugs with closures + : public detail::ebo_functor_holder { typedef detail::ebo_functor_holder base_t; @@ -800,6 +805,7 @@ struct get_hash //Stores bucket_plus_vtraits plust the hash function template struct bucket_hash_t + //Use public inheritance to avoid MSVC bugs with closures : public detail::ebo_functor_holder ::value_traits::value_type @@ -852,6 +858,7 @@ struct get_equal_to //non-empty bucket shall not be cached. template struct bucket_hash_equal_t + //Use public inheritance to avoid MSVC bugs with closures : public detail::ebo_functor_holder //equal ::value_traits::value_type @@ -929,6 +936,7 @@ struct bucket_hash_equal_t //non-empty bucket shall be cached. template //cache_begin == true version struct bucket_hash_equal_t + //Use public inheritance to avoid MSVC bugs with closures : public detail::ebo_functor_holder //equal ::value_traits::value_type @@ -973,7 +981,7 @@ struct bucket_hash_equal_tcached_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 , slist_node_ptr, node_ptr > NodeDisposer; typedef node_cast_adaptor< detail::node_cloner @@ -1660,7 +1667,7 @@ class hashtable_impl //! //! Effects: Equivalent to this->insert_equal(t) for each element in [b, e). //! - //! Complexity: Average case O(N), where N is std::distance(b, e). + //! Complexity: Average case O(N), where N is distance(b, e). //! Worst case O(N*this->size()). //! //! Throws: If the internal hasher or the equality functor throws. Basic guarantee. @@ -1706,7 +1713,7 @@ class hashtable_impl //! //! Effects: Equivalent to this->insert_unique(t) for each element in [b, e). //! - //! Complexity: Average case O(N), where N is std::distance(b, e). + //! Complexity: Average case O(N), where N is distance(b, e). //! Worst case O(N*this->size()). //! //! Throws: If the internal hasher or the equality functor throws. Basic guarantee. @@ -1819,7 +1826,7 @@ class hashtable_impl //! Effects: Erases the range pointed to by b end e. //! - //! Complexity: Average case O(std::distance(b, e)), + //! Complexity: Average case O(distance(b, e)), //! worst case O(this->size()). //! //! Throws: Nothing. @@ -1896,7 +1903,7 @@ class hashtable_impl //! Effects: Erases the range pointed to by b end e. //! Disposer::operator()(pointer) is called for the removed elements. //! - //! Complexity: Average case O(std::distance(b, e)), + //! Complexity: Average case O(distance(b, e)), //! worst case O(this->size()). //! //! Throws: 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(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} hashtable& operator=(BOOST_RV_REF(hashtable) x) - { return static_cast(this->Base::operator=(::boost::move(static_cast(x)))); } + { return static_cast(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 +#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 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 +template struct max_pointer_plus_bits; -template +template struct max_pointer_plus_bits; template struct pointer_plus_bits; -template +template struct pointer_plus_bits; template 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 #include #include #include #include -#include +#include //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 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 #include #include @@ -38,13 +34,17 @@ #include #include #include +#include #include #include -#include -#include -#include +#include //std::less +#include //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 iterator; typedef list_iterator const_iterator; - typedef boost::intrusive::detail::reverse_iterator reverse_iterator; - typedef boost::intrusive::detail::reverse_iteratorconst_reverse_iterator; + typedef boost::intrusive::reverse_iterator reverse_iterator; + typedef boost::intrusive::reverse_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_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; @@ -186,7 +187,7 @@ class list_impl //! //! Effects: Constructs a list equal to the range [first,last). //! - //! Complexity: Linear in std::distance(b, e). No copy constructors are called. + //! Complexity: Linear in distance(b, e). No copy constructors are called. //! //! Throws: If value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). @@ -352,7 +353,7 @@ class list_impl //! //! Complexity: 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())); } //! Effects: Returns a reference to the last element of the list. //! @@ -603,7 +604,7 @@ class list_impl } //! Requires: b and e must be valid iterators to elements in *this. - //! n must be std::distance(b, e). + //! n must be distance(b, e). //! //! Effects: 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 } //! Requires: 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) //! //! Effects: 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::const_cast_from(pointer_traits::pointer_to(value)); + reference r =*detail::uncast(pointer_traits::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 //! Note: Iterators and references are not invalidated. const_iterator iterator_to(const_reference value) const { - reference r = *pointer_traits::const_cast_from(pointer_traits::pointer_to(value)); + reference r = *detail::uncast(pointer_traits::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 &x, const list_impl &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 @@ -1363,30 +1364,11 @@ bool operator== #endif { typedef list_impl 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 ::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(x))) + : Base(BOOST_MOVE_BASE(Base, x)) {} list& operator=(BOOST_RV_REF(list) x) - { return static_cast(this->Base::operator=(::boost::move(static_cast(x)))); } + { return static_cast(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } static list &container_from_end_iterator(iterator end_iterator) { return static_cast(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 #include @@ -26,6 +22,11 @@ #include #include +#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 #include @@ -24,6 +20,10 @@ #include #include +#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 #include #include #include #include +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + namespace boost { namespace intrusive { @@ -37,8 +37,7 @@ struct fhtraits; template struct mhtraits; -//typedef void default_tag; -struct default_tag; +struct dft_tag; struct member_tag; template @@ -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 member_value_traits; template @@ -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 + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif -#include - 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 -//! { /*unspecified_content*/ }; +//! { unspecified_content }; //! \endcode //! //! ...that after being combined with @@ -338,7 +338,7 @@ struct pack_options //! //! \code //! struct OPTION_NAME -//! { /*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 #include #include +#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 #include #include //ls_zeros #include //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 +#endif //BOOST_INTRUSIVE_DETAIL_WORKAROUND_HPP + +#ifndef BOOST_CONFIG_HPP +# include #endif -#include +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif namespace boost { namespace intrusive { @@ -165,12 +171,6 @@ template