diff options
Diffstat (limited to 'boost/intrusive/detail')
49 files changed, 3601 insertions, 3895 deletions
diff --git a/boost/intrusive/detail/algo_type.hpp b/boost/intrusive/detail/algo_type.hpp new file mode 100644 index 0000000000..e40cb43b4e --- /dev/null +++ b/boost/intrusive/detail/algo_type.hpp @@ -0,0 +1,46 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_ALGO_TYPE_HPP +#define BOOST_INTRUSIVE_DETAIL_ALGO_TYPE_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +namespace boost { +namespace intrusive { + +enum algo_types +{ + CircularListAlgorithms, + CircularSListAlgorithms, + LinearSListAlgorithms, + CommonSListAlgorithms, + BsTreeAlgorithms, + RbTreeAlgorithms, + AvlTreeAlgorithms, + SgTreeAlgorithms, + SplayTreeAlgorithms, + TreapAlgorithms +}; + +template<algo_types AlgoType, class NodeTraits> +struct get_algo; + +template<algo_types AlgoType, class ValueTraits, class NodePtrCompare, class ExtraChecker> +struct get_node_checker; + +} //namespace intrusive +} //namespace boost + +#endif //BOOST_INTRUSIVE_DETAIL_ALGO_TYPE_HPP diff --git a/boost/intrusive/detail/any_node_and_algorithms.hpp b/boost/intrusive/detail/any_node_and_algorithms.hpp index b274135a90..5a0e8c27fe 100644 --- a/boost/intrusive/detail/any_node_and_algorithms.hpp +++ b/boost/intrusive/detail/any_node_and_algorithms.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2014 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -13,13 +13,13 @@ #ifndef BOOST_INTRUSIVE_ANY_NODE_HPP #define BOOST_INTRUSIVE_ANY_NODE_HPP -#include <boost/intrusive/detail/config_begin.hpp> -#include <iterator> -#include <boost/intrusive/detail/assert.hpp> -#include <boost/intrusive/pointer_traits.hpp> +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/pointer_rebind.hpp> #include <cstddef> #include <boost/intrusive/detail/mpl.hpp> -#include <boost/pointer_cast.hpp> namespace boost { namespace intrusive { @@ -27,8 +27,9 @@ namespace intrusive { template<class VoidPointer> struct any_node { - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<any_node>::type node_ptr; + typedef any_node node; + typedef typename pointer_rebind<VoidPointer, node>::type node_ptr; + typedef typename pointer_rebind<VoidPointer, const node>::type const_node_ptr; node_ptr node_ptr_1; node_ptr node_ptr_2; node_ptr node_ptr_3; @@ -38,11 +39,9 @@ struct any_node template<class VoidPointer> struct any_list_node_traits { - typedef any_node<VoidPointer> node; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; + typedef any_node<VoidPointer> node; + 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) { return n->node_ptr_1; } @@ -61,11 +60,9 @@ struct any_list_node_traits template<class VoidPointer> struct any_slist_node_traits { - typedef any_node<VoidPointer> node; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; + typedef any_node<VoidPointer> node; + 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) { return n->node_ptr_1; } @@ -110,12 +107,9 @@ struct any_unordered_node_traits template<class VoidPointer> struct any_rbtree_node_traits { - typedef any_node<VoidPointer> node; - - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; + typedef any_node<VoidPointer> node; + typedef typename node::node_ptr node_ptr; + typedef typename node::const_node_ptr const_node_ptr; typedef std::size_t color; @@ -154,12 +148,10 @@ struct any_rbtree_node_traits template<class VoidPointer> struct any_avltree_node_traits { - typedef any_node<VoidPointer> node; + typedef any_node<VoidPointer> node; + typedef typename node::node_ptr node_ptr; + typedef typename node::const_node_ptr const_node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; typedef std::size_t balance; static const node_ptr &get_parent(const const_node_ptr & n) @@ -200,12 +192,9 @@ struct any_avltree_node_traits template<class VoidPointer> struct any_tree_node_traits { - typedef any_node<VoidPointer> node; - - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; + typedef any_node<VoidPointer> node; + 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) { return n->node_ptr_1; } @@ -231,10 +220,8 @@ class any_node_traits { public: typedef any_node<VoidPointer> node; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; + typedef typename node::node_ptr node_ptr; + typedef typename node::const_node_ptr const_node_ptr; }; template<class VoidPointer> @@ -245,12 +232,10 @@ class any_algorithms {} public: - typedef any_node<VoidPointer> node; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; - typedef any_node_traits<VoidPointer> node_traits; + typedef any_node<VoidPointer> node; + typedef typename node::node_ptr node_ptr; + typedef typename node::const_node_ptr const_node_ptr; + typedef any_node_traits<VoidPointer> node_traits; //! <b>Requires</b>: node must not be part of any tree. //! @@ -281,7 +266,7 @@ class any_algorithms any_algorithms<VoidPointer>::template function_not_available_for_any_hooks<node_ptr>(); } - static void swap_nodes(const node_ptr & l, const node_ptr & r) + static void swap_nodes(const node_ptr &, const node_ptr &) { //Any nodes have no swap_nodes capability because they don't know //what algorithm they must use to unlink the node from the container @@ -292,6 +277,4 @@ class any_algorithms } //namespace intrusive } //namespace boost -#include <boost/intrusive/detail/config_end.hpp> - #endif //BOOST_INTRUSIVE_ANY_NODE_HPP diff --git a/boost/intrusive/detail/array_initializer.hpp b/boost/intrusive/detail/array_initializer.hpp new file mode 100644 index 0000000000..b2072a872d --- /dev/null +++ b/boost/intrusive/detail/array_initializer.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_ARRAY_INITIALIZER_HPP +#define BOOST_INTRUSIVE_DETAIL_ARRAY_INITIALIZER_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/core/no_exceptions_support.hpp> + +namespace boost { +namespace intrusive { +namespace detail { + +//This is not standard, but should work with all compilers +union max_align +{ + char char_; + short short_; + int int_; + long long_; + #ifdef BOOST_HAS_LONG_LONG + long long long_long_; + #endif + float float_; + double double_; + long double long_double_; + void * void_ptr_; +}; + +template<class T, std::size_t N> +class array_initializer +{ + public: + template<class CommonInitializer> + array_initializer(const CommonInitializer &init) + { + char *init_buf = (char*)rawbuf; + std::size_t i = 0; + BOOST_TRY{ + for(; i != N; ++i){ + new(init_buf)T(init); + init_buf += sizeof(T); + } + } + BOOST_CATCH(...){ + while(i--){ + init_buf -= sizeof(T); + ((T*)init_buf)->~T(); + } + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + operator T* () + { return (T*)(rawbuf); } + + operator const T*() const + { return (const T*)(rawbuf); } + + ~array_initializer() + { + char *init_buf = (char*)rawbuf + N*sizeof(T); + for(std::size_t i = 0; i != N; ++i){ + init_buf -= sizeof(T); + ((T*)init_buf)->~T(); + } + } + + private: + detail::max_align rawbuf[(N*sizeof(T)-1)/sizeof(detail::max_align)+1]; +}; + +} //namespace detail{ +} //namespace intrusive{ +} //namespace boost{ + +#endif //BOOST_INTRUSIVE_DETAIL_ARRAY_INITIALIZER_HPP diff --git a/boost/intrusive/detail/assert.hpp b/boost/intrusive/detail/assert.hpp index 33de97f701..d75d225ac4 100644 --- a/boost/intrusive/detail/assert.hpp +++ b/boost/intrusive/detail/assert.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -13,7 +13,7 @@ #ifndef BOOST_INTRUSIVE_DETAIL_ASSERT_HPP #define BOOST_INTRUSIVE_DETAIL_ASSERT_HPP -#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#if defined(_MSC_VER) #pragma once #endif diff --git a/boost/intrusive/detail/avltree_node.hpp b/boost/intrusive/detail/avltree_node.hpp index aec0dabd4b..522806a89e 100644 --- a/boost/intrusive/detail/avltree_node.hpp +++ b/boost/intrusive/detail/avltree_node.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007-2012 +// (C) Copyright Ion Gaztanaga 2007-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -13,9 +13,12 @@ #ifndef BOOST_INTRUSIVE_AVLTREE_NODE_HPP #define BOOST_INTRUSIVE_AVLTREE_NODE_HPP +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/detail/config_begin.hpp> -#include <iterator> -#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/pointer_rebind.hpp> #include <boost/intrusive/avltree_algorithms.hpp> #include <boost/intrusive/pointer_plus_bits.hpp> #include <boost/intrusive/detail/mpl.hpp> @@ -33,9 +36,8 @@ namespace intrusive { template<class VoidPointer> struct compact_avltree_node { - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer - <compact_avltree_node<VoidPointer> >::type node_ptr; + typedef typename pointer_rebind<VoidPointer, compact_avltree_node<VoidPointer> >::type node_ptr; + typedef typename pointer_rebind<VoidPointer, const compact_avltree_node<VoidPointer> >::type const_node_ptr; enum balance { negative_t, zero_t, positive_t }; node_ptr parent_, left_, right_; }; @@ -44,9 +46,8 @@ struct compact_avltree_node template<class VoidPointer> struct avltree_node { - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer - <avltree_node<VoidPointer> >::type node_ptr; + typedef typename pointer_rebind<VoidPointer, avltree_node<VoidPointer> >::type node_ptr; + typedef typename pointer_rebind<VoidPointer, const avltree_node<VoidPointer> >::type const_node_ptr; enum balance { negative_t, zero_t, positive_t }; node_ptr parent_, left_, right_; balance balance_; @@ -58,29 +59,33 @@ template<class VoidPointer> struct default_avltree_node_traits_impl { typedef avltree_node<VoidPointer> node; - - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer - <node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer - <const node>::type const_node_ptr; + typedef typename node::node_ptr node_ptr; + typedef typename node::const_node_ptr const_node_ptr; typedef typename node::balance balance; - static const node_ptr & get_parent(const const_node_ptr & n) + static node_ptr get_parent(const const_node_ptr & n) + { return n->parent_; } + + static node_ptr get_parent(const node_ptr & n) { return n->parent_; } static void set_parent(const node_ptr & n, const node_ptr & p) { n->parent_ = p; } - static const node_ptr & get_left(const const_node_ptr & n) + static node_ptr get_left(const const_node_ptr & n) + { return n->left_; } + + static node_ptr get_left(const node_ptr & n) { return n->left_; } static void set_left(const node_ptr & n, const node_ptr & l) { n->left_ = l; } - static const node_ptr & get_right(const const_node_ptr & n) + static node_ptr get_right(const const_node_ptr & n) + { return n->right_; } + + static node_ptr get_right(const node_ptr & n) { return n->right_; } static void set_right(const node_ptr & n, const node_ptr & r) @@ -89,6 +94,9 @@ struct default_avltree_node_traits_impl static balance get_balance(const const_node_ptr & n) { return n->balance_; } + static balance get_balance(const node_ptr & n) + { return n->balance_; } + static void set_balance(const node_ptr & n, balance b) { n->balance_ = b; } @@ -108,13 +116,8 @@ template<class VoidPointer> struct compact_avltree_node_traits_impl { typedef compact_avltree_node<VoidPointer> node; - - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer - <node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer - <const node>::type const_node_ptr; + typedef typename node::node_ptr node_ptr; + typedef typename node::const_node_ptr const_node_ptr; typedef typename node::balance balance; typedef pointer_plus_bits<node_ptr, 2> ptr_bit; @@ -125,13 +128,13 @@ struct compact_avltree_node_traits_impl static void set_parent(const node_ptr & n, const node_ptr & p) { ptr_bit::set_pointer(n->parent_, p); } - static const node_ptr & get_left(const const_node_ptr & n) + static node_ptr get_left(const const_node_ptr & n) { return n->left_; } static void set_left(const node_ptr & n, const node_ptr & l) { n->left_ = l; } - static const node_ptr & get_right(const const_node_ptr & n) + static node_ptr get_right(const const_node_ptr & n) { return n->right_; } static void set_right(const node_ptr & n, const node_ptr & r) @@ -164,7 +167,7 @@ struct avltree_node_traits_dispatch<VoidPointer, true> : public compact_avltree_node_traits_impl<VoidPointer> {}; -//Inherit from the detail::link_dispatch depending on the embedding capabilities +//Inherit from rbtree_node_traits_dispatch depending on the embedding capabilities template<class VoidPointer, bool OptimizeSize = false> struct avltree_node_traits : public avltree_node_traits_dispatch diff --git a/boost/intrusive/detail/clear_on_destructor_base.hpp b/boost/intrusive/detail/clear_on_destructor_base.hpp deleted file mode 100644 index 1b5c27fff4..0000000000 --- a/boost/intrusive/detail/clear_on_destructor_base.hpp +++ /dev/null @@ -1,36 +0,0 @@ -//////} // /////////////////////////////////////////////////////////////////////// -// -// (C) Copyright Ion Gaztanaga 2008-2012. 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_CLEAR_ON_DESTRUCTOR_HPP -#define BOOST_INTRUSIVE_DETAIL_CLEAR_ON_DESTRUCTOR_HPP - -#include <boost/intrusive/detail/config_begin.hpp> - -namespace boost { -namespace intrusive { -namespace detail { - -template<class Derived> -class clear_on_destructor_base -{ - protected: - ~clear_on_destructor_base() - { - static_cast<Derived*>(this)->clear(); - } -}; - -} // namespace detail { -} // namespace intrusive { -} // namespace boost { - -#include <boost/intrusive/detail/config_end.hpp> - -#endif //#ifndef BOOST_INTRUSIVE_DETAIL_CLEAR_ON_DESTRUCTOR_HPP diff --git a/boost/intrusive/detail/common_slist_algorithms.hpp b/boost/intrusive/detail/common_slist_algorithms.hpp index 942b35a3f4..4c7f1a11e0 100644 --- a/boost/intrusive/detail/common_slist_algorithms.hpp +++ b/boost/intrusive/detail/common_slist_algorithms.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007-2012 +// (C) Copyright Ion Gaztanaga 2007-2014 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -13,9 +13,14 @@ #ifndef BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP #define BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP -#include <boost/intrusive/detail/config_begin.hpp> +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/assert.hpp> +#include <boost/intrusive/detail/algo_type.hpp> +#include <boost/core/no_exceptions_support.hpp> #include <cstddef> namespace boost { @@ -31,9 +36,8 @@ class common_slist_algorithms typedef typename NodeTraits::const_node_ptr const_node_ptr; typedef NodeTraits node_traits; - static node_ptr get_previous_node(const node_ptr & prev_init_node, const node_ptr & this_node) + static node_ptr get_previous_node(node_ptr p, const node_ptr & this_node) { - node_ptr p = prev_init_node; for( node_ptr p_next ; this_node != (p_next = NodeTraits::get_next(p)) ; p = p_next){ @@ -44,9 +48,6 @@ class common_slist_algorithms return p; } - static void init_header(const node_ptr & this_node) - { NodeTraits::set_next(this_node, this_node); } - static void init(const node_ptr & this_node) { NodeTraits::set_next(this_node, node_ptr()); } @@ -92,12 +93,102 @@ class common_slist_algorithms NodeTraits::set_next(bp, next_b); } } + + struct stable_partition_info + { + std::size_t num_1st_partition; + std::size_t num_2nd_partition; + node_ptr beg_2st_partition; + node_ptr new_last_node; + }; + + template<class Pred> + static void stable_partition(node_ptr before_beg, const node_ptr &end, Pred pred, stable_partition_info &info) + { + node_ptr bcur = before_beg; + node_ptr cur = node_traits::get_next(bcur); + node_ptr new_f = end; + + std::size_t num1 = 0, num2 = 0; + while(cur != end){ + if(pred(cur)){ + ++num1; + bcur = cur; + cur = node_traits::get_next(cur); + } + else{ + ++num2; + node_ptr last_to_remove = bcur; + new_f = cur; + bcur = cur; + cur = node_traits::get_next(cur); + BOOST_TRY{ + //Main loop + while(cur != end){ + if(pred(cur)){ //Might throw + ++num1; + //Process current node + node_traits::set_next(last_to_remove, cur); + last_to_remove = cur; + node_ptr nxt = node_traits::get_next(cur); + node_traits::set_next(bcur, nxt); + cur = nxt; + } + else{ + ++num2; + bcur = cur; + cur = node_traits::get_next(cur); + } + } + } + BOOST_CATCH(...){ + node_traits::set_next(last_to_remove, new_f); + throw; + } + BOOST_CATCH_END + node_traits::set_next(last_to_remove, new_f); + break; + } + } + info.num_1st_partition = num1; + info.num_2nd_partition = num2; + info.beg_2st_partition = new_f; + info.new_last_node = bcur; + } + + //! <b>Requires</b>: f and l must be in a circular list. + //! + //! <b>Effects</b>: Returns the number of nodes in the range [f, l). + //! + //! <b>Complexity</b>: Linear + //! + //! <b>Throws</b>: Nothing. + static std::size_t distance(const const_node_ptr &f, const const_node_ptr &l) + { + const_node_ptr i(f); + std::size_t result = 0; + while(i != l){ + i = NodeTraits::get_next(i); + ++result; + } + return result; + } }; +/// @endcond + } //namespace detail + +/// @cond + +template<class NodeTraits> +struct get_algo<CommonSListAlgorithms, NodeTraits> +{ + typedef detail::common_slist_algorithms<NodeTraits> type; +}; + + } //namespace intrusive } //namespace boost -#include <boost/intrusive/detail/config_end.hpp> - #endif //BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP diff --git a/boost/intrusive/detail/config_begin.hpp b/boost/intrusive/detail/config_begin.hpp index 7d153368a5..36d605d072 100644 --- a/boost/intrusive/detail/config_begin.hpp +++ b/boost/intrusive/detail/config_begin.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -10,8 +10,7 @@ // ///////////////////////////////////////////////////////////////////////////// -#ifndef BOOST_INTRUSIVE_CONFIG_INCLUDED -#define BOOST_INTRUSIVE_CONFIG_INCLUDED +#ifndef BOOST_CONFIG_HPP #include <boost/config.hpp> #endif diff --git a/boost/intrusive/detail/config_end.hpp b/boost/intrusive/detail/config_end.hpp index d653030daa..a081443e69 100644 --- a/boost/intrusive/detail/config_end.hpp +++ b/boost/intrusive/detail/config_end.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at diff --git a/boost/intrusive/detail/default_header_holder.hpp b/boost/intrusive/detail/default_header_holder.hpp new file mode 100644 index 0000000000..c471691640 --- /dev/null +++ b/boost/intrusive/detail/default_header_holder.hpp @@ -0,0 +1,65 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_DEFAULT_HEADER_HOLDER_HPP +#define BOOST_INTRUSIVE_DETAIL_DEFAULT_HEADER_HOLDER_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/detail/to_raw_pointer.hpp> + +namespace boost { +namespace intrusive { +namespace detail { + +// trivial header node holder +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; + + default_header_holder() : node() {} + + 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)); } + + // (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; +}; +template < typename Value_Traits > +struct get_header_holder_type< Value_Traits, void > +{ + typedef default_header_holder< typename Value_Traits::node_traits > type; +}; + +} //namespace detail +} //namespace intrusive +} //namespace boost + +#endif //BOOST_INTRUSIVE_DETAIL_DEFAULT_HEADER_HOLDER_HPP diff --git a/boost/intrusive/detail/ebo_functor_holder.hpp b/boost/intrusive/detail/ebo_functor_holder.hpp index 850d074326..d2e8107b67 100644 --- a/boost/intrusive/detail/ebo_functor_holder.hpp +++ b/boost/intrusive/detail/ebo_functor_holder.hpp @@ -1,6 +1,7 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Joaquin M Lopez Munoz 2006-2012 +// (C) Copyright Joaquin M Lopez Munoz 2006-2013 +// (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 @@ -13,13 +14,145 @@ #ifndef BOOST_INTRUSIVE_DETAIL_EBO_HOLDER_HPP #define BOOST_INTRUSIVE_DETAIL_EBO_HOLDER_HPP -#include <boost/intrusive/detail/config_begin.hpp> -#include <boost/intrusive/detail/mpl.hpp> +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/config.hpp> namespace boost { namespace intrusive { namespace detail { +#if defined(BOOST_MSVC) || defined(__BORLANDC_) +#define BOOST_INTRUSIVE_TT_DECL __cdecl +#else +#define BOOST_INTRUSIVE_TT_DECL +#endif + +#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) && !defined(_M_ARM) && !defined(UNDER_CE) +#define BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS +#endif + +template <typename T> +struct is_unary_or_binary_function_impl +{ static const bool value = false; }; + +// see boost ticket #4094 +// avoid duplicate definitions of is_unary_or_binary_function_impl +#ifndef BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS + +template <typename R> +struct is_unary_or_binary_function_impl<R (*)()> +{ static const bool value = true; }; + +template <typename R> +struct is_unary_or_binary_function_impl<R (*)(...)> +{ static const bool value = true; }; + +#else // BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS + +template <typename R> +struct is_unary_or_binary_function_impl<R (__stdcall*)()> +{ static const bool value = true; }; + +#ifndef _MANAGED + +template <typename R> +struct is_unary_or_binary_function_impl<R (__fastcall*)()> +{ static const bool value = true; }; + +#endif + +template <typename R> +struct is_unary_or_binary_function_impl<R (__cdecl*)()> +{ static const bool value = true; }; + +template <typename R> +struct is_unary_or_binary_function_impl<R (__cdecl*)(...)> +{ static const bool value = true; }; + +#endif + +// see boost ticket #4094 +// avoid duplicate definitions of is_unary_or_binary_function_impl +#ifndef BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS + +template <typename R, class T0> +struct is_unary_or_binary_function_impl<R (*)(T0)> +{ static const bool value = true; }; + +template <typename R, class T0> +struct is_unary_or_binary_function_impl<R (*)(T0...)> +{ static const bool value = true; }; + +#else // BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS + +template <typename R, class T0> +struct is_unary_or_binary_function_impl<R (__stdcall*)(T0)> +{ static const bool value = true; }; + +#ifndef _MANAGED + +template <typename R, class T0> +struct is_unary_or_binary_function_impl<R (__fastcall*)(T0)> +{ static const bool value = true; }; + +#endif + +template <typename R, class T0> +struct is_unary_or_binary_function_impl<R (__cdecl*)(T0)> +{ static const bool value = true; }; + +template <typename R, class T0> +struct is_unary_or_binary_function_impl<R (__cdecl*)(T0...)> +{ static const bool value = true; }; + +#endif + +// see boost ticket #4094 +// avoid duplicate definitions of is_unary_or_binary_function_impl +#ifndef BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS + +template <typename R, class T0, class T1> +struct is_unary_or_binary_function_impl<R (*)(T0, T1)> +{ static const bool value = true; }; + +template <typename R, class T0, class T1> +struct is_unary_or_binary_function_impl<R (*)(T0, T1...)> +{ static const bool value = true; }; + +#else // BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS + +template <typename R, class T0, class T1> +struct is_unary_or_binary_function_impl<R (__stdcall*)(T0, T1)> +{ static const bool value = true; }; + +#ifndef _MANAGED + +template <typename R, class T0, class T1> +struct is_unary_or_binary_function_impl<R (__fastcall*)(T0, T1)> +{ static const bool value = true; }; + +#endif + +template <typename R, class T0, class T1> +struct is_unary_or_binary_function_impl<R (__cdecl*)(T0, T1)> +{ static const bool value = true; }; + +template <typename R, class T0, class T1> +struct is_unary_or_binary_function_impl<R (__cdecl*)(T0, T1...)> +{ static const bool value = true; }; +#endif + +template <typename T> +struct is_unary_or_binary_function_impl<T&> +{ static const bool value = false; }; + +template<typename T> +struct is_unary_or_binary_function : is_unary_or_binary_function_impl<T> +{}; + template<typename T, bool IsEmpty = true> class ebo_functor_holder_impl { @@ -90,6 +223,4 @@ class ebo_functor_holder } //namespace intrusive { } //namespace boost { -#include <boost/intrusive/detail/config_end.hpp> - #endif //#ifndef BOOST_INTRUSIVE_DETAIL_EBO_HOLDER_HPP diff --git a/boost/intrusive/detail/empty_node_checker.hpp b/boost/intrusive/detail/empty_node_checker.hpp new file mode 100644 index 0000000000..33d78a34ba --- /dev/null +++ b/boost/intrusive/detail/empty_node_checker.hpp @@ -0,0 +1,40 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_EMPTY_NODE_CHECKER_HPP +#define BOOST_INTRUSIVE_DETAIL_EMPTY_NODE_CHECKER_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +namespace boost { +namespace intrusive { +namespace detail { + +template<class ValueTraits> +struct empty_node_checker +{ + typedef ValueTraits value_traits; + typedef typename value_traits::node_traits node_traits; + typedef typename node_traits::const_node_ptr const_node_ptr; + + struct return_type {}; + + void operator () (const const_node_ptr&, const return_type&, const return_type&, return_type&) {} +}; + +} //namespace detail{ +} //namespace intrusive{ +} //namespace boost{ + +#endif //BOOST_INTRUSIVE_DETAIL_EMPTY_NODE_CHECKER_HPP diff --git a/boost/intrusive/detail/equal_to_value.hpp b/boost/intrusive/detail/equal_to_value.hpp new file mode 100644 index 0000000000..3ffd1c26cf --- /dev/null +++ b/boost/intrusive/detail/equal_to_value.hpp @@ -0,0 +1,44 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_EQUAL_TO_VALUE_HPP +#define BOOST_INTRUSIVE_DETAIL_EQUAL_TO_VALUE_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +namespace boost { +namespace intrusive { +namespace detail { + +//This functor compares a stored value +//and the one passed as an argument +template<class ConstReference> +class equal_to_value +{ + ConstReference t_; + + public: + equal_to_value(ConstReference t) + : t_(t) + {} + + bool operator()(ConstReference t)const + { return t_ == t; } +}; + +} //namespace detail{ +} //namespace intrusive{ +} //namespace boost{ + +#endif //BOOST_INTRUSIVE_DETAIL_EQUAL_TO_VALUE_HPP diff --git a/boost/intrusive/detail/exception_disposer.hpp b/boost/intrusive/detail/exception_disposer.hpp new file mode 100644 index 0000000000..1226f5e525 --- /dev/null +++ b/boost/intrusive/detail/exception_disposer.hpp @@ -0,0 +1,84 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_EXCEPTION_DISPOSER_HPP +#define BOOST_INTRUSIVE_DETAIL_EXCEPTION_DISPOSER_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +namespace boost { +namespace intrusive { +namespace detail { + +template<class Container, class Disposer> +class exception_disposer +{ + Container *cont_; + Disposer &disp_; + + exception_disposer(const exception_disposer&); + exception_disposer &operator=(const exception_disposer&); + + public: + exception_disposer(Container &cont, Disposer &disp) + : cont_(&cont), disp_(disp) + {} + + void release() + { cont_ = 0; } + + ~exception_disposer() + { + if(cont_){ + cont_->clear_and_dispose(disp_); + } + } +}; + +template<class Container, class Disposer, class SizeType> +class exception_array_disposer +{ + Container *cont_; + Disposer &disp_; + SizeType &constructed_; + + exception_array_disposer(const exception_array_disposer&); + exception_array_disposer &operator=(const exception_array_disposer&); + + public: + + exception_array_disposer + (Container &cont, Disposer &disp, SizeType &constructed) + : cont_(&cont), disp_(disp), constructed_(constructed) + {} + + void release() + { cont_ = 0; } + + ~exception_array_disposer() + { + SizeType n = constructed_; + if(cont_){ + while(n--){ + cont_[n].clear_and_dispose(disp_); + } + } + } +}; + +} //namespace detail{ +} //namespace intrusive{ +} //namespace boost{ + +#endif //BOOST_INTRUSIVE_DETAIL_EXCEPTION_DISPOSER_HPP diff --git a/boost/intrusive/detail/function_detector.hpp b/boost/intrusive/detail/function_detector.hpp index 08cee2d561..f72865df9b 100644 --- a/boost/intrusive/detail/function_detector.hpp +++ b/boost/intrusive/detail/function_detector.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2009-2012. +// (C) Copyright Ion Gaztanaga 2009-2013. // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -22,7 +22,9 @@ #ifndef BOOST_INTRUSIVE_DETAIL_FUNCTION_DETECTOR_HPP #define BOOST_INTRUSIVE_DETAIL_FUNCTION_DETECTOR_HPP -#include <boost/intrusive/detail/config_begin.hpp> +#if defined(_MSC_VER) +# pragma once +#endif namespace boost { namespace intrusive { @@ -83,6 +85,4 @@ namespace function_detector { ReturnType (*)Params \ >::check -#include <boost/intrusive/detail/config_end.hpp> - #endif //@ifndef BOOST_INTRUSIVE_DETAIL_FUNCTION_DETECTOR_HPP diff --git a/boost/intrusive/detail/generic_hook.hpp b/boost/intrusive/detail/generic_hook.hpp index 5ddd52074e..c5af081d65 100644 --- a/boost/intrusive/detail/generic_hook.hpp +++ b/boost/intrusive/detail/generic_hook.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007-2012 +// (C) Copyright Ion Gaztanaga 2007-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -13,139 +13,147 @@ #ifndef BOOST_INTRUSIVE_GENERIC_HOOK_HPP #define BOOST_INTRUSIVE_GENERIC_HOOK_HPP -#include <boost/intrusive/detail/config_begin.hpp> -#include <boost/intrusive/intrusive_fwd.hpp> +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/pointer_traits.hpp> #include <boost/intrusive/link_mode.hpp> -#include <boost/intrusive/detail/utilities.hpp> #include <boost/intrusive/detail/mpl.hpp> -#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/detail/assert.hpp> +#include <boost/intrusive/detail/node_holder.hpp> #include <boost/static_assert.hpp> namespace boost { namespace intrusive { -namespace detail { /// @cond -enum -{ NoBaseHook -, ListBaseHook -, SlistBaseHook -, SetBaseHook -, UsetBaseHook -, SplaySetBaseHook -, AvlSetBaseHook -, BsSetBaseHook -, AnyBaseHook -}; - -struct no_default_definer{}; +namespace detail { -template <class Hook, unsigned int> -struct default_definer; +template <link_mode_type LinkMode> +struct link_dispatch +{}; + +template<class Hook> +void destructor_impl(Hook &hook, detail::link_dispatch<safe_link>) +{ //If this assertion raises, you might have destroyed an object + //while it was still inserted in a container that is alive. + //If so, remove the object from the container before destroying it. + (void)hook; BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT(!hook.is_linked()); +} + +template<class Hook> +void destructor_impl(Hook &hook, detail::link_dispatch<auto_unlink>) +{ hook.unlink(); } + +template<class Hook> +void destructor_impl(Hook &, detail::link_dispatch<normal_link>) +{} + +} //namespace detail { + +enum base_hook_type +{ NoBaseHookId +, ListBaseHookId +, SlistBaseHookId +, RbTreeBaseHookId +, HashBaseHookId +, AvlTreeBaseHookId +, BsTreeBaseHookId +, TreapTreeBaseHookId +, AnyBaseHookId +}; -template <class Hook> -struct default_definer<Hook, ListBaseHook> -{ typedef Hook default_list_hook; }; -template <class Hook> -struct default_definer<Hook, SlistBaseHook> -{ typedef Hook default_slist_hook; }; +template <class HookTags, unsigned int> +struct hook_tags_definer{}; -template <class Hook> -struct default_definer<Hook, SetBaseHook> -{ typedef Hook default_set_hook; }; +template <class HookTags> +struct hook_tags_definer<HookTags, ListBaseHookId> +{ typedef HookTags default_list_hook; }; -template <class Hook> -struct default_definer<Hook, UsetBaseHook> -{ typedef Hook default_uset_hook; }; +template <class HookTags> +struct hook_tags_definer<HookTags, SlistBaseHookId> +{ typedef HookTags default_slist_hook; }; -template <class Hook> -struct default_definer<Hook, SplaySetBaseHook> -{ typedef Hook default_splay_set_hook; }; +template <class HookTags> +struct hook_tags_definer<HookTags, RbTreeBaseHookId> +{ typedef HookTags default_rbtree_hook; }; -template <class Hook> -struct default_definer<Hook, AvlSetBaseHook> -{ typedef Hook default_avl_set_hook; }; +template <class HookTags> +struct hook_tags_definer<HookTags, HashBaseHookId> +{ typedef HookTags default_hashtable_hook; }; -template <class Hook> -struct default_definer<Hook, BsSetBaseHook> -{ typedef Hook default_bs_set_hook; }; +template <class HookTags> +struct hook_tags_definer<HookTags, AvlTreeBaseHookId> +{ typedef HookTags default_avltree_hook; }; -template <class Hook> -struct default_definer<Hook, AnyBaseHook> -{ typedef Hook default_any_hook; }; +template <class HookTags> +struct hook_tags_definer<HookTags, BsTreeBaseHookId> +{ typedef HookTags default_bstree_hook; }; -template <class Hook, unsigned int BaseHookType> -struct make_default_definer -{ - typedef typename detail::if_c - < BaseHookType != 0 - , default_definer<Hook, BaseHookType> - , no_default_definer>::type type; -}; +template <class HookTags> +struct hook_tags_definer<HookTags, AnyBaseHookId> +{ typedef HookTags default_any_hook; }; template - < class GetNodeAlgorithms + < class NodeTraits , class Tag , link_mode_type LinkMode - , int HookType + , base_hook_type BaseHookType > -struct make_node_holder +struct hooktags_impl { - typedef typename detail::if_c - <!detail::is_same<Tag, member_tag>::value - , detail::node_holder - < typename GetNodeAlgorithms::type::node - , Tag - , LinkMode - , HookType> - , typename GetNodeAlgorithms::type::node - >::type type; + static const link_mode_type link_mode = LinkMode; + typedef Tag tag; + typedef NodeTraits node_traits; + static const bool is_base_hook = !detail::is_same<Tag, member_tag>::value; + static const bool safemode_or_autounlink = is_safe_autounlink<link_mode>::value; + static const unsigned int type = BaseHookType; }; /// @endcond template - < class GetNodeAlgorithms + < class NodeAlgorithms , class Tag , link_mode_type LinkMode - , int HookType + , base_hook_type BaseHookType > class generic_hook /// @cond - - //If the hook is a base hook, derive generic hook from detail::node_holder + //If the hook is a base hook, derive generic hook from node_holder //so that a unique base class is created to convert from the node - //to the type. This mechanism will be used by base_hook_traits. + //to the type. This mechanism will be used by bhtraits. // //If the hook is a member hook, generic hook will directly derive //from the hook. - : public make_default_definer - < generic_hook<GetNodeAlgorithms, Tag, LinkMode, HookType> - , detail::is_same<Tag, default_tag>::value*HookType + : public detail::if_c + < detail::is_same<Tag, member_tag>::value + , typename NodeAlgorithms::node + , node_holder<typename NodeAlgorithms::node, Tag, BaseHookType> >::type - , public make_node_holder<GetNodeAlgorithms, Tag, LinkMode, HookType>::type + //If this is the a default-tagged base hook derive from a class that + //will define an special internal typedef. Containers will be able to detect this + //special typedef and obtain generic_hook's internal types in order to deduce + //value_traits for this hook. + , public hook_tags_definer + < generic_hook<NodeAlgorithms, Tag, LinkMode, BaseHookType> + , detail::is_same<Tag, default_tag>::value*BaseHookType> /// @endcond { /// @cond - typedef typename GetNodeAlgorithms::type node_algorithms; + typedef NodeAlgorithms node_algorithms; typedef typename node_algorithms::node node; typedef typename node_algorithms::node_ptr node_ptr; typedef typename node_algorithms::const_node_ptr const_node_ptr; public: - struct boost_intrusive_tags - { - static const int hook_type = HookType; - static const link_mode_type link_mode = LinkMode; - typedef Tag tag; - typedef typename GetNodeAlgorithms::type::node_traits node_traits; - static const bool is_base_hook = !detail::is_same<Tag, member_tag>::value; - static const bool safemode_or_autounlink = - (int)link_mode == (int)auto_unlink || (int)link_mode == (int)safe_link; - }; + + typedef hooktags_impl + < typename NodeAlgorithms::node_traits + , Tag, LinkMode, BaseHookType> hooktags; node_ptr this_ptr() { return pointer_traits<node_ptr>::pointer_to(static_cast<node&>(*this)); } @@ -158,14 +166,14 @@ class generic_hook generic_hook() { - if(boost_intrusive_tags::safemode_or_autounlink){ + if(hooktags::safemode_or_autounlink){ node_algorithms::init(this->this_ptr()); } } generic_hook(const generic_hook& ) { - if(boost_intrusive_tags::safemode_or_autounlink){ + if(hooktags::safemode_or_autounlink){ node_algorithms::init(this->this_ptr()); } } @@ -176,7 +184,7 @@ class generic_hook ~generic_hook() { destructor_impl - (*this, detail::link_dispatch<boost_intrusive_tags::link_mode>()); + (*this, detail::link_dispatch<hooktags::link_mode>()); } void swap_nodes(generic_hook &other) @@ -188,22 +196,22 @@ class generic_hook bool is_linked() const { //is_linked() can be only used in safe-mode or auto-unlink - BOOST_STATIC_ASSERT(( boost_intrusive_tags::safemode_or_autounlink )); + BOOST_STATIC_ASSERT(( hooktags::safemode_or_autounlink )); return !node_algorithms::unique(this->this_ptr()); } void unlink() { - BOOST_STATIC_ASSERT(( (int)boost_intrusive_tags::link_mode == (int)auto_unlink )); - node_algorithms::unlink(this->this_ptr()); - node_algorithms::init(this->this_ptr()); + BOOST_STATIC_ASSERT(( (int)hooktags::link_mode == (int)auto_unlink )); + node_ptr n(this->this_ptr()); + if(!node_algorithms::inited(n)){ + node_algorithms::unlink(n); + node_algorithms::init(n); + } } }; -} //namespace detail } //namespace intrusive } //namespace boost -#include <boost/intrusive/detail/config_end.hpp> - #endif //BOOST_INTRUSIVE_GENERIC_HOOK_HPP diff --git a/boost/intrusive/detail/get_value_traits.hpp b/boost/intrusive/detail/get_value_traits.hpp new file mode 100644 index 0000000000..6f5a9e3f04 --- /dev/null +++ b/boost/intrusive/detail/get_value_traits.hpp @@ -0,0 +1,218 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_GET_VALUE_TRAITS_HPP +#define BOOST_INTRUSIVE_DETAIL_GET_VALUE_TRAITS_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/detail/hook_traits.hpp> + +namespace boost { +namespace intrusive { + +#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED + +template<class SupposedValueTraits> +struct is_default_hook_tag +{ static const bool value = false; }; + +namespace detail{ + +template <class T, class BaseHook> +struct concrete_hook_base_value_traits +{ + typedef typename BaseHook::hooktags tags; + typedef bhtraits + < T + , typename tags::node_traits + , tags::link_mode + , typename tags::tag + , tags::type> type; +}; + +template <class BaseHook> +struct concrete_hook_base_value_traits<void, BaseHook> +{ + typedef typename BaseHook::hooktags type; +}; + +template <class T, class AnyToSomeHook_ProtoValueTraits> +struct any_hook_base_value_traits +{ + //AnyToSomeHook value_traits derive from a generic_hook + //The generic_hook is configured with any_node_traits + //and AnyToSomeHook::value_traits with the correct + //node traits for the container, so use node_traits + //from AnyToSomeHook_ProtoValueTraits and the rest of + //elements from the hooktags member of the generic_hook + + typedef typename AnyToSomeHook_ProtoValueTraits::basic_hook_t basic_hook_t; + typedef typename pointer_rebind + < typename basic_hook_t::hooktags::node_traits::node_ptr + , void>::type void_pointer; + typedef typename AnyToSomeHook_ProtoValueTraits::template + node_traits_from_voidptr<void_pointer>::type node_traits; + + typedef bhtraits + < T + , node_traits + , basic_hook_t::hooktags::link_mode + , typename basic_hook_t::hooktags::tag + , basic_hook_t::hooktags::type + > type; +}; + +template <class AnyToSomeHook_ProtoValueTraits> +struct any_hook_base_value_traits<void, AnyToSomeHook_ProtoValueTraits> +{ + typedef typename AnyToSomeHook_ProtoValueTraits::basic_hook_t basic_hook_t; + typedef typename pointer_rebind + < typename basic_hook_t::hooktags::node_traits::node_ptr + , void>::type void_pointer; + + struct type + { + typedef typename AnyToSomeHook_ProtoValueTraits::template + node_traits_from_voidptr<void_pointer>::type node_traits; + }; +}; + +template<class MemberHook> +struct get_member_value_traits +{ + typedef typename MemberHook::member_value_traits type; +}; + +BOOST_INTRUSIVE_INTERNAL_STATIC_BOOL_IS_TRUE(internal_any_hook, is_any_hook) +BOOST_INTRUSIVE_INTERNAL_STATIC_BOOL_IS_TRUE(internal_base_hook, hooktags::is_base_hook) + +template <class T> +struct internal_member_value_traits +{ + template <class U> static one test(...); + template <class U> static two test(typename U::member_value_traits* = 0); + static const bool value = sizeof(test<T>(0)) == sizeof(two); +}; + +template<class SupposedValueTraits, class T, bool = is_default_hook_tag<SupposedValueTraits>::value> +struct supposed_value_traits; + +template<class T, class BaseHook, bool = internal_any_hook_bool_is_true<BaseHook>::value> +struct get_base_value_traits; + +template<class SupposedValueTraits, class T, bool = internal_base_hook_bool_is_true<SupposedValueTraits>::value> +struct supposed_base_value_traits; + +template<class SupposedValueTraits, bool = internal_member_value_traits<SupposedValueTraits>::value> +struct supposed_member_value_traits; + +template<class SupposedValueTraits, bool = internal_any_hook_bool_is_true<SupposedValueTraits>::value> +struct any_or_concrete_value_traits; + +//Base any hook +template<class T, class BaseHook> +struct get_base_value_traits<T, BaseHook, true> + : any_hook_base_value_traits<T, BaseHook> +{}; + +//Non-any base hook +template<class T, class BaseHook> +struct get_base_value_traits<T, BaseHook, false> + : concrete_hook_base_value_traits<T, BaseHook> +{}; + +//...It's a default hook +template<class SupposedValueTraits, class T> +struct supposed_value_traits<SupposedValueTraits, T, true> +{ typedef typename SupposedValueTraits::template apply<T>::type type; }; + +//...Not a default hook +template<class SupposedValueTraits, class T> +struct supposed_value_traits<SupposedValueTraits, T, false> +{ typedef SupposedValueTraits type; }; + +//...It's a base hook +template<class BaseHook, class T> +struct supposed_base_value_traits<BaseHook, T, true> + : get_base_value_traits<T, BaseHook> +{}; + +//...Not a base hook, try if it's a member or value_traits +template<class SupposedValueTraits, class T> +struct supposed_base_value_traits<SupposedValueTraits, T, false> + : supposed_member_value_traits<SupposedValueTraits> +{}; + +//...It's a member hook +template<class MemberHook> +struct supposed_member_value_traits<MemberHook, true> + : get_member_value_traits<MemberHook> +{}; + +//...Not a member hook +template<class SupposedValueTraits> +struct supposed_member_value_traits<SupposedValueTraits, false> + : any_or_concrete_value_traits<SupposedValueTraits> +{}; + +template<class AnyToSomeHook_ProtoValueTraits> +struct any_or_concrete_value_traits<AnyToSomeHook_ProtoValueTraits, true> +{ + //A hook node (non-base, e.g.: member or other value traits + typedef typename AnyToSomeHook_ProtoValueTraits::basic_hook_t basic_hook_t; + typedef typename pointer_rebind + <typename basic_hook_t::node_ptr, void>::type void_pointer; + typedef typename AnyToSomeHook_ProtoValueTraits::template + node_traits_from_voidptr<void_pointer>::type any_node_traits; + + struct type : basic_hook_t + { + typedef any_node_traits node_traits; + }; +}; + +template<class SupposedValueTraits> +struct any_or_concrete_value_traits<SupposedValueTraits, false> +{ + typedef SupposedValueTraits type; +}; + +//////////////////////////////////////// +// get_value_traits / get_node_traits +//////////////////////////////////////// + +template<class T, class SupposedValueTraits> +struct get_value_traits + : supposed_base_value_traits<typename supposed_value_traits<SupposedValueTraits, T>::type, T> +{}; + +template<class SupposedValueTraits> +struct get_node_traits +{ + typedef typename get_value_traits<void, SupposedValueTraits>::type::node_traits type; +}; + +} //namespace detail{ + +#endif //BOOST_INTRUSIVE_DOXYGEN_INVOKED + +} //namespace intrusive { +} //namespace boost { + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //#ifndef BOOST_INTRUSIVE_DETAIL_GET_VALUE_TRAITS_HPP diff --git a/boost/intrusive/detail/has_member_function_callable_with.hpp b/boost/intrusive/detail/has_member_function_callable_with.hpp index 6516e28067..ca96f15a19 100644 --- a/boost/intrusive/detail/has_member_function_callable_with.hpp +++ b/boost/intrusive/detail/has_member_function_callable_with.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2011-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2011-2014. Distributed under the Boost // Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // @@ -15,11 +15,10 @@ #ifndef BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_DETAILS_INCLUDED #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_DETAILS_INCLUDED - #include <boost/intrusive/detail/config_begin.hpp> - #include <boost/intrusive/detail/workaround.hpp> #include <boost/intrusive/detail/preprocessor.hpp> - #include <boost/static_assert.hpp> - #include <boost/move/move.hpp> + #include <boost/intrusive/detail/mpl.hpp> + #include <boost/move/utility_core.hpp> + //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 @@ -36,6 +35,12 @@ dont_care(...); }; + template<class T> + struct make_dontcare + { + typedef boost_intrusive_has_member_function_callable_with::dont_care type; + }; + struct private_type { static private_type p; @@ -51,7 +56,9 @@ } //boost_intrusive_has_member_function_callable_with - #include <boost/intrusive/detail/config_end.hpp> + #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_SINGLE_ITERATION + #endif #endif //BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_DETAILS_INCLUDED @@ -69,11 +76,11 @@ #error "BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END not defined!" #endif - #if BOOST_PP_ITERATION_START() != 0 - #error "BOOST_PP_ITERATION_START() must be zero (0)" + #if BOOST_PP_ITERATION_START() > BOOST_PP_ITERATION_FINISH() + #error "BOOST_PP_ITERATION_START() must be <= BOOST_PP_ITERATION_FINISH()" #endif - #if BOOST_PP_ITERATION() == 0 + #if BOOST_PP_ITERATION() == BOOST_PP_ITERATION_START() BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN @@ -85,7 +92,7 @@ void BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(); }; - struct Base : public Type, public BaseMixin { Base(); }; + struct Base : public ::boost::intrusive::detail::remove_cv<Type>::type, public BaseMixin { Base(); }; template <typename T, T t> class Helper{}; template <typename U> @@ -98,7 +105,7 @@ sizeof(boost_intrusive_has_member_function_callable_with::yes_type) == sizeof(deduce((Base*)(0))); }; - #if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) + #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template<typename Fun, bool HasFunc BOOST_PP_ENUM_TRAILING(BOOST_PP_ITERATION_FINISH(), BOOST_INTRUSIVE_PP_TEMPLATE_PARAM_VOID_DEFAULT, _)> @@ -113,76 +120,7 @@ }; //! - #if !defined(_MSC_VER) || (_MSC_VER < 1600) - - #if defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) - - template<typename Fun> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> - { - //Mark that we don't support 0 arg calls due to compiler ICE in GCC 3.4/4.0/4.1 and - //wrong SFINAE for GCC 4.2/4.3 - static const bool value = true; - }; - - #else //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) - - //Special case for 0 args - template< class F - , std::size_t N = - sizeof((boost::move_detail::declval<F>(). - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME (), 0))> - struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) - { - boost_intrusive_has_member_function_callable_with::yes_type dummy; - BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); - }; - - //For buggy compilers like MSVC 7.1+ ((F*)0)->func() does not - //SFINAE-out the zeroarg_checker_ instantiation but sizeof yields to 0. - template<class F> - struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<F, 0> - { - boost_intrusive_has_member_function_callable_with::no_type dummy; - BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); - }; - - template<typename Fun> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> - { - template<class U> - static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U> - Test(BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*); - - template <class U> - static boost_intrusive_has_member_function_callable_with::no_type Test(...); - - 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) - - #else //#if !defined(_MSC_VER) || (_MSC_VER < 1600) - template<typename Fun> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> - { - template<class U> - static decltype( boost::move_detail::declval<Fun>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME() - , boost_intrusive_has_member_function_callable_with::yes_type()) - Test(Fun*); - - template<class U> - static boost_intrusive_has_member_function_callable_with::no_type Test(...); - - static const bool value = sizeof(Test<Fun>(0)) - == sizeof(boost_intrusive_has_member_function_callable_with::yes_type); - }; - #endif //#if !defined(_MSC_VER) || (_MSC_VER < 1600) - - #else //#if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) + #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template<typename Fun, bool HasFunc, class ...Args> struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl); @@ -194,6 +132,8 @@ static const bool value = false; }; + #ifdef BOOST_NO_CXX11_DECLTYPE + //Special case for 0 args template< class F , std::size_t N = @@ -214,14 +154,21 @@ BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); }; + #endif //#ifdef BOOST_NO_CXX11_DECLTYPE + template<typename Fun> struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) <Fun, true> { + #ifndef BOOST_NO_CXX11_DECLTYPE + template<class U, class V = decltype(boost::move_detail::declval<U>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME()) > + static boost_intrusive_has_member_function_callable_with::yes_type Test(U*); + #else template<class U> - static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) <U> Test(BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*); - + #endif + template <class U> static boost_intrusive_has_member_function_callable_with::no_type Test(...); @@ -229,30 +176,23 @@ == sizeof(boost_intrusive_has_member_function_callable_with::yes_type); }; - template<typename Fun, class ...DontCares> - struct BOOST_PP_CAT( funwrap_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME ) - : Fun - { - BOOST_PP_CAT( funwrap_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME )(); - 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; - }; - template<typename Fun, class ...Args> struct BOOST_PP_CAT( BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME), _impl) <Fun, true , Args...> { - template<class T> - struct make_dontcare + + template<class ...DontCares> + struct FunWrapTmpl : Fun { - typedef boost_intrusive_has_member_function_callable_with::dont_care type; + 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 BOOST_PP_CAT( funwrap_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME ) - <Fun, typename make_dontcare<Args>::type...> FunWrap; + typedef FunWrapTmpl<typename boost_intrusive_has_member_function_callable_with::make_dontcare<Args>::type...> FunWrap; static bool const value = (sizeof(boost_intrusive_has_member_function_callable_with::no_type) == sizeof(boost_intrusive_has_member_function_callable_with::is_private_type @@ -274,32 +214,99 @@ , Args... > {}; - #endif //#if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) + #endif //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END + + #endif //BOOST_PP_ITERATION() == BOOST_PP_ITERATION_START() + + #if BOOST_PP_ITERATION() == 0 + + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN + + #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + #if !defined(_MSC_VER) || (_MSC_VER < 1600) + + #if defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) + + template<typename Fun> + struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) + <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> + { + //Mark that we don't support 0 arg calls due to compiler ICE in GCC 3.4/4.0/4.1 and + //wrong SFINAE for GCC 4.2/4.3 + static const bool value = true; + }; + + #else //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) + + //Special case for 0 args + template< class F + , std::size_t N = + sizeof((boost::move_detail::declval<F>(). + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME (), 0))> + struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + { + boost_intrusive_has_member_function_callable_with::yes_type dummy; + BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); + }; + + //For buggy compilers like MSVC 7.1+ ((F*)0)->func() does not + //SFINAE-out the zeroarg_checker_ instantiation but sizeof yields to 0. + template<class F> + struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<F, 0> + { + boost_intrusive_has_member_function_callable_with::no_type dummy; + BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); + }; + + template<typename Fun> + struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) + <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> + { + template<class U> + static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U> + Test(BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*); + + template <class U> + static boost_intrusive_has_member_function_callable_with::no_type Test(...); + + 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) + + #else //#if !defined(_MSC_VER) || (_MSC_VER < 1600) + template<typename Fun> + struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) + <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> + { + template<class U> + static decltype( boost::move_detail::declval<U>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME() + , boost_intrusive_has_member_function_callable_with::yes_type()) + Test(U*); + + template<class U> + static boost_intrusive_has_member_function_callable_with::no_type Test(...); + + static const bool value = sizeof(Test<Fun>(0)) + == sizeof(boost_intrusive_has_member_function_callable_with::yes_type); + }; + #endif //#if !defined(_MSC_VER) || (_MSC_VER < 1600) + + #else //#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + #endif //#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END #else //BOOST_PP_ITERATION() == 0 - #if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) + #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN - template<typename Fun> - struct BOOST_PP_CAT( BOOST_PP_CAT(funwrap, BOOST_PP_ITERATION()) - , BOOST_PP_CAT(_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)) - : Fun - { - BOOST_PP_CAT( BOOST_PP_CAT(funwrap, BOOST_PP_ITERATION()) - , BOOST_PP_CAT(_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME))(); - - 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<typename Fun BOOST_PP_ENUM_TRAILING_PARAMS(BOOST_PP_ITERATION(), class P)> struct BOOST_PP_CAT( BOOST_PP_CAT(has_member_function_callable_with_ , BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) @@ -309,9 +316,18 @@ , BOOST_INTRUSIVE_PP_IDENTITY , void)> { - typedef BOOST_PP_CAT( BOOST_PP_CAT(funwrap, BOOST_PP_ITERATION()) - , BOOST_PP_CAT(_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME))<Fun> - FunWrap; + struct FunWrap : Fun + { + 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; + }; + 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 @@ -325,13 +341,13 @@ }; BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END - #endif //#if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) + #endif //#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) #endif //BOOST_PP_ITERATION() == 0 #if BOOST_PP_ITERATION() == BOOST_PP_ITERATION_FINISH() - #if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) + #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN @@ -345,7 +361,7 @@ BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END - #endif //#if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) + #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 diff --git a/boost/intrusive/detail/hashtable_node.hpp b/boost/intrusive/detail/hashtable_node.hpp index 86e607460c..6449fa0dd2 100644 --- a/boost/intrusive/detail/hashtable_node.hpp +++ b/boost/intrusive/detail/hashtable_node.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007-2012 +// (C) Copyright Ion Gaztanaga 2007-2014 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -13,45 +13,24 @@ #ifndef BOOST_INTRUSIVE_HASHTABLE_NODE_HPP #define BOOST_INTRUSIVE_HASHTABLE_NODE_HPP -#include <boost/intrusive/detail/config_begin.hpp> -#include <iterator> +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/detail/assert.hpp> #include <boost/intrusive/pointer_traits.hpp> -#include <boost/intrusive/circular_list_algorithms.hpp> #include <boost/intrusive/detail/mpl.hpp> -#include <boost/intrusive/detail/utilities.hpp> -//#include <boost/intrusive/detail/slist_node.hpp> //remove-me -#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/trivial_value_traits.hpp> +#include <boost/intrusive/slist.hpp> //make_slist #include <cstddef> -#include <boost/pointer_cast.hpp> -#include <boost/move/move.hpp> +#include <climits> +#include <boost/move/core.hpp> namespace boost { namespace intrusive { namespace detail { -template<int Dummy = 0> -struct prime_list_holder -{ - static const std::size_t prime_list[]; - static const std::size_t prime_list_size; -}; - -template<int Dummy> -const std::size_t prime_list_holder<Dummy>::prime_list[] = { - 3ul, 7ul, 11ul, 17ul, 29ul, - 53ul, 97ul, 193ul, 389ul, 769ul, - 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, - 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, - 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, - 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, - 1610612741ul, 3221225473ul, 4294967291ul }; - -template<int Dummy> -const std::size_t prime_list_holder<Dummy>::prime_list_size - = sizeof(prime_list)/sizeof(std::size_t); - template <class Slist> struct bucket_impl : public Slist { @@ -89,6 +68,7 @@ struct bucket_traits_impl typedef typename pointer_traits <typename Slist::pointer>::template rebind_pointer < bucket_impl<Slist> >::type bucket_ptr; + typedef Slist slist; typedef typename Slist::size_type size_type; /// @endcond @@ -100,7 +80,6 @@ struct bucket_traits_impl : buckets_(x.buckets_), buckets_len_(x.buckets_len_) {} - bucket_traits_impl(BOOST_RV_REF(bucket_traits_impl) x) : buckets_(x.buckets_), buckets_len_(x.buckets_len_) { x.buckets_ = bucket_ptr(); x.buckets_len_ = 0; } @@ -127,57 +106,107 @@ struct bucket_traits_impl size_type buckets_len_; }; -template<class Container, bool IsConst> +template <class NodeTraits> +struct hash_reduced_slist_node_traits +{ + template <class U> static detail::one test(...); + template <class U> static detail::two test(typename U::reduced_slist_node_traits* = 0); + static const bool value = sizeof(test<NodeTraits>(0)) == sizeof(detail::two); +}; + +template <class NodeTraits> +struct apply_reduced_slist_node_traits +{ + typedef typename NodeTraits::reduced_slist_node_traits type; +}; + +template <class NodeTraits> +struct reduced_slist_node_traits +{ + typedef typename detail::eval_if_c + < hash_reduced_slist_node_traits<NodeTraits>::value + , apply_reduced_slist_node_traits<NodeTraits> + , detail::identity<NodeTraits> + >::type type; +}; + +template<class NodeTraits> +struct get_slist_impl +{ + typedef trivial_value_traits<NodeTraits, normal_link> trivial_traits; + + //Reducing symbol length + struct type : make_slist + < typename NodeTraits::node + , boost::intrusive::value_traits<trivial_traits> + , boost::intrusive::constant_time_size<false> + , boost::intrusive::size_type<std::size_t> + >::type + {}; +}; + +} //namespace detail { + +template<class BucketValueTraits, bool IsConst> class hashtable_iterator - : public std::iterator +{ + typedef boost::intrusive::iterator < std::forward_iterator_tag - , typename Container::value_type - , typename pointer_traits<typename Container::value_type*>::difference_type + , typename BucketValueTraits::value_traits::value_type + , typename pointer_traits<typename BucketValueTraits::value_traits::value_type*>::difference_type , typename detail::add_const_if_c - <typename Container::value_type, IsConst>::type * + <typename BucketValueTraits::value_traits::value_type, IsConst>::type * , typename detail::add_const_if_c - <typename Container::value_type, IsConst>::type & - > -{ - typedef typename Container::real_value_traits real_value_traits; - typedef typename Container::siterator siterator; - typedef typename Container::const_siterator const_siterator; - typedef typename Container::bucket_type bucket_type; + <typename BucketValueTraits::value_traits::value_type, IsConst>::type & + > iterator_traits; + + typedef typename BucketValueTraits::value_traits value_traits; + typedef typename BucketValueTraits::bucket_traits bucket_traits; + typedef typename value_traits::node_traits node_traits; + typedef typename detail::get_slist_impl + <typename detail::reduced_slist_node_traits + <typename value_traits::node_traits>::type + >::type slist_impl; + typedef typename slist_impl::iterator siterator; + typedef typename slist_impl::const_iterator const_siterator; + typedef detail::bucket_impl<slist_impl> bucket_type; typedef typename pointer_traits - <typename Container::pointer>::template rebind_pointer - < const Container >::type const_cont_ptr; - typedef typename Container::size_type size_type; + <typename value_traits::pointer>::template rebind_pointer + < const BucketValueTraits >::type const_bucketvaltraits_ptr; + typedef typename slist_impl::size_type size_type; - static typename Container::node_ptr downcast_bucket(typename bucket_type::node_ptr p) + + static typename node_traits::node_ptr downcast_bucket(typename bucket_type::node_ptr p) { - return pointer_traits<typename Container::node_ptr>:: - pointer_to(static_cast<typename Container::node&>(*p)); + return pointer_traits<typename node_traits::node_ptr>:: + pointer_to(static_cast<typename node_traits::node&>(*p)); } public: - typedef typename Container::value_type value_type; - typedef typename detail::add_const_if_c - <typename Container::value_type, IsConst>::type *pointer; - typedef typename detail::add_const_if_c - <typename Container::value_type, IsConst>::type &reference; + typedef typename iterator_traits::difference_type difference_type; + typedef typename iterator_traits::value_type value_type; + typedef typename iterator_traits::pointer pointer; + typedef typename iterator_traits::reference reference; + typedef typename iterator_traits::iterator_category iterator_category; hashtable_iterator () + : slist_it_() //Value initialization to achieve "null iterators" (N3644) {} - explicit hashtable_iterator(siterator ptr, const Container *cont) - : slist_it_ (ptr), cont_ (cont ? pointer_traits<const_cont_ptr>::pointer_to(*cont) : const_cont_ptr() ) + explicit hashtable_iterator(siterator ptr, const BucketValueTraits *cont) + : slist_it_ (ptr), traitsptr_ (cont ? pointer_traits<const_bucketvaltraits_ptr>::pointer_to(*cont) : const_bucketvaltraits_ptr() ) {} - hashtable_iterator(const hashtable_iterator<Container, false> &other) - : slist_it_(other.slist_it()), cont_(other.get_container()) + hashtable_iterator(const hashtable_iterator<BucketValueTraits, false> &other) + : slist_it_(other.slist_it()), traitsptr_(other.get_bucket_value_traits()) {} const siterator &slist_it() const { return slist_it_; } - hashtable_iterator<Container, false> unconst() const - { return hashtable_iterator<Container, false>(this->slist_it(), this->get_container()); } + hashtable_iterator<BucketValueTraits, false> unconst() const + { return hashtable_iterator<BucketValueTraits, false>(this->slist_it(), this->get_bucket_value_traits()); } public: hashtable_iterator& operator++() @@ -201,48 +230,57 @@ class hashtable_iterator pointer operator->() const { - return boost::intrusive::detail::to_raw_pointer(this->get_real_value_traits()->to_value_ptr + return boost::intrusive::detail::to_raw_pointer(this->priv_value_traits().to_value_ptr (downcast_bucket(slist_it_.pointed_node()))); } - const const_cont_ptr &get_container() const - { return cont_; } + const const_bucketvaltraits_ptr &get_bucket_value_traits() const + { return traitsptr_; } + + const value_traits &priv_value_traits() const + { return traitsptr_->priv_value_traits(); } - const real_value_traits *get_real_value_traits() const - { return &this->get_container()->get_real_value_traits(); } + const bucket_traits &priv_bucket_traits() const + { return traitsptr_->priv_bucket_traits(); } private: void increment() { - const Container *cont = boost::intrusive::detail::to_raw_pointer(cont_); - bucket_type* buckets = boost::intrusive::detail::to_raw_pointer(cont->bucket_pointer()); - size_type buckets_len = cont->bucket_count(); + const bucket_traits &rbuck_traits = this->priv_bucket_traits(); + bucket_type* const buckets = boost::intrusive::detail::to_raw_pointer(rbuck_traits.bucket_begin()); + const size_type buckets_len = rbuck_traits.bucket_count(); ++slist_it_; - if(buckets[0].cend().pointed_node() <= slist_it_.pointed_node() && - slist_it_.pointed_node()<= buckets[buckets_len].cend().pointed_node() ){ - //Now get the bucket_impl from the iterator + const typename slist_impl::node_ptr n = slist_it_.pointed_node(); + const siterator first_bucket_bbegin = buckets->end(); + if(first_bucket_bbegin.pointed_node() <= n && n <= buckets[buckets_len-1].cend().pointed_node()){ + //If one-past the node is inside the bucket then look for the next non-empty bucket + //1. get the bucket_impl from the iterator const bucket_type &b = static_cast<const bucket_type&> (bucket_type::slist_type::container_from_end_iterator(slist_it_)); - //Now just calculate the index b has in the bucket array - size_type n_bucket = static_cast<size_type>(&b - &buckets[0]); + //2. Now just calculate the index b has in the bucket array + size_type n_bucket = static_cast<size_type>(&b - buckets); + + //3. Iterate until a non-empty bucket is found do{ - if (++n_bucket == buckets_len){ - slist_it_ = (&buckets[0] + buckets_len)->end(); - break; + if (++n_bucket >= buckets_len){ //bucket overflow, return end() iterator + slist_it_ = buckets->before_begin(); + return; } - slist_it_ = buckets[n_bucket].begin(); } - while (slist_it_ == buckets[n_bucket].end()); + while (buckets[n_bucket].empty()); + slist_it_ = buckets[n_bucket].begin(); + } + else{ + //++slist_it_ yield to a valid object } } - siterator slist_it_; - const_cont_ptr cont_; + siterator slist_it_; + const_bucketvaltraits_ptr traitsptr_; }; -} //namespace detail { } //namespace intrusive { } //namespace boost { diff --git a/boost/intrusive/detail/hook_traits.hpp b/boost/intrusive/detail/hook_traits.hpp new file mode 100644 index 0000000000..c9c115b1de --- /dev/null +++ b/boost/intrusive/detail/hook_traits.hpp @@ -0,0 +1,182 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2014 +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/libs/intrusive for documentation. +// +///////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_INTRUSIVE_DETAIL_HOOK_TRAITS_HPP +#define BOOST_INTRUSIVE_DETAIL_HOOK_TRAITS_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/detail/parent_from_member.hpp> +#include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/detail/to_raw_pointer.hpp> +#include <boost/intrusive/detail/node_holder.hpp> + +namespace boost { +namespace intrusive { + +template<class T, class NodePtr, class Tag, unsigned int Type> +struct bhtraits_base +{ + public: + typedef NodePtr node_ptr; + typedef typename pointer_traits<node_ptr>::element_type node; + typedef node_holder<node, Tag, Type> node_holder_type; + typedef T value_type; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<const node>::type const_node_ptr; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<T>::type pointer; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<const T>::type const_pointer; + //typedef typename pointer_traits<pointer>::reference reference; + //typedef typename pointer_traits<const_pointer>::reference const_reference; + typedef T & reference; + typedef const T & const_reference; + typedef node_holder_type & node_holder_reference; + typedef const node_holder_type & const_node_holder_reference; + typedef node& node_reference; + typedef const node & const_node_reference; + + static pointer to_value_ptr(const node_ptr & n) + { + return pointer_traits<pointer>::pointer_to + (static_cast<reference>(static_cast<node_holder_reference>(*n))); + } + + static const_pointer to_value_ptr(const const_node_ptr & n) + { + return pointer_traits<const_pointer>::pointer_to + (static_cast<const_reference>(static_cast<const_node_holder_reference>(*n))); + } + + static node_ptr to_node_ptr(reference value) + { + return pointer_traits<node_ptr>::pointer_to + (static_cast<node_reference>(static_cast<node_holder_reference>(value))); + } + + static const_node_ptr to_node_ptr(const_reference value) + { + return pointer_traits<const_node_ptr>::pointer_to + (static_cast<const_node_reference>(static_cast<const_node_holder_reference>(value))); + } +}; + +template<class T, class NodeTraits, link_mode_type LinkMode, class Tag, unsigned int Type> +struct bhtraits + : public bhtraits_base<T, typename NodeTraits::node_ptr, Tag, Type> +{ + static const link_mode_type link_mode = LinkMode; + typedef NodeTraits node_traits; +}; + + +template<class T, class Hook, Hook T::* P> +struct mhtraits +{ + public: + typedef Hook hook_type; + typedef typename hook_type::hooktags::node_traits node_traits; + typedef typename node_traits::node node; + typedef T value_type; + typedef typename node_traits::node_ptr node_ptr; + typedef typename node_traits::const_node_ptr const_node_ptr; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<T>::type pointer; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<const T>::type const_pointer; + typedef T & reference; + typedef const T & const_reference; + typedef node& node_reference; + typedef const node & const_node_reference; + typedef hook_type& hook_reference; + typedef const hook_type & const_hook_reference; + + static const link_mode_type link_mode = Hook::hooktags::link_mode; + + static node_ptr to_node_ptr(reference value) + { + return pointer_traits<node_ptr>::pointer_to + (static_cast<node_reference>(static_cast<hook_reference>(value.*P))); + } + + static const_node_ptr to_node_ptr(const_reference value) + { + return pointer_traits<const_node_ptr>::pointer_to + (static_cast<const_node_reference>(static_cast<const_hook_reference>(value.*P))); + } + + static pointer to_value_ptr(const node_ptr & n) + { + return pointer_traits<pointer>::pointer_to + (*detail::parent_from_member<T, Hook> + (static_cast<Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P)); + } + + static const_pointer to_value_ptr(const const_node_ptr & n) + { + return pointer_traits<const_pointer>::pointer_to + (*detail::parent_from_member<T, Hook> + (static_cast<const Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P)); + } +}; + + +template<class Functor> +struct fhtraits +{ + public: + typedef typename Functor::hook_type hook_type; + typedef typename Functor::hook_ptr hook_ptr; + typedef typename Functor::const_hook_ptr const_hook_ptr; + typedef typename hook_type::hooktags::node_traits node_traits; + typedef typename node_traits::node node; + typedef typename Functor::value_type value_type; + typedef typename node_traits::node_ptr node_ptr; + typedef typename node_traits::const_node_ptr const_node_ptr; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<value_type>::type pointer; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<const value_type>::type const_pointer; + typedef value_type & reference; + typedef const value_type & const_reference; + static const link_mode_type link_mode = hook_type::hooktags::link_mode; + + static node_ptr to_node_ptr(reference value) + { return static_cast<node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value))); } + + static const_node_ptr to_node_ptr(const_reference value) + { return static_cast<const node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value))); } + + static pointer to_value_ptr(const node_ptr & n) + { return Functor::to_value_ptr(to_hook_ptr(n)); } + + static const_pointer to_value_ptr(const const_node_ptr & n) + { return Functor::to_value_ptr(to_hook_ptr(n)); } + + private: + static hook_ptr to_hook_ptr(const node_ptr & n) + { return hook_ptr(&*static_cast<hook_type*>(&*n)); } + + static const_hook_ptr to_hook_ptr(const const_node_ptr & n) + { return const_hook_ptr(&*static_cast<const hook_type*>(&*n)); } +}; + + +} //namespace intrusive +} //namespace boost + +#endif //BOOST_INTRUSIVE_DETAIL_HOOK_TRAITS_HPP diff --git a/boost/intrusive/detail/iiterator.hpp b/boost/intrusive/detail/iiterator.hpp new file mode 100644 index 0000000000..8378ead6ad --- /dev/null +++ b/boost/intrusive/detail/iiterator.hpp @@ -0,0 +1,227 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2014 +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/libs/intrusive for documentation. +// +///////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_INTRUSIVE_DETAIL_IITERATOR_HPP +#define BOOST_INTRUSIVE_DETAIL_IITERATOR_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/detail/is_stateful_value_traits.hpp> +#include <boost/intrusive/detail/std_fwd.hpp> + +#include <cstddef> + + +namespace boost { +namespace intrusive { + +template<class Category, class T, class Distance, class Pointer, class Reference> +struct iterator +{ + typedef Category iterator_category; + typedef T value_type; + typedef Distance difference_type; + typedef Pointer pointer; + typedef Reference reference; +}; + +template<class Iterator> +struct iterator_traits +{ + typedef typename Iterator::difference_type difference_type; + typedef typename Iterator::value_type value_type; + typedef typename Iterator::pointer pointer; + typedef typename Iterator::reference reference; + typedef typename Iterator::iterator_category iterator_category; +}; + +template<class T> +struct iterator_traits<T*> +{ + typedef std::ptrdiff_t difference_type; + typedef T value_type; + typedef T* pointer; + typedef T& reference; + typedef std::random_access_iterator_tag iterator_category; +}; + +template<class T> +struct iterator_traits<const T*> +{ + typedef std::ptrdiff_t difference_type; + typedef T value_type; + typedef const T* pointer; + typedef const T& reference; + typedef std::random_access_iterator_tag iterator_category; +}; + +template<class ValueTraits> +struct value_traits_pointers +{ + typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT + (boost::intrusive::detail:: + , ValueTraits, value_traits_ptr + , typename pointer_traits<typename ValueTraits::node_traits::node_ptr>::template + rebind_pointer<ValueTraits>::type) value_traits_ptr; + + typedef typename pointer_traits<value_traits_ptr>::template + rebind_pointer<ValueTraits const>::type const_value_traits_ptr; +}; + +template<class ValueTraits, bool IsConst, class Category> +struct iiterator +{ + typedef ValueTraits value_traits; + typedef typename value_traits::node_traits node_traits; + typedef typename node_traits::node node; + typedef typename node_traits::node_ptr node_ptr; + typedef ::boost::intrusive::pointer_traits<node_ptr> nodepointer_traits_t; + typedef typename nodepointer_traits_t::template + rebind_pointer<void>::type void_pointer; + typedef typename ValueTraits::value_type value_type; + typedef typename ValueTraits::pointer nonconst_pointer; + typedef typename ValueTraits::const_pointer yesconst_pointer; + typedef typename ::boost::intrusive::pointer_traits + <nonconst_pointer>::reference nonconst_reference; + typedef typename ::boost::intrusive::pointer_traits + <yesconst_pointer>::reference yesconst_reference; + typedef typename nodepointer_traits_t::difference_type difference_type; + typedef typename detail::if_c + <IsConst, yesconst_pointer, nonconst_pointer>::type pointer; + typedef typename detail::if_c + <IsConst, yesconst_reference, nonconst_reference>::type reference; + typedef iterator + < Category + , value_type + , difference_type + , pointer + , reference + > iterator_traits; + typedef typename value_traits_pointers + <ValueTraits>::value_traits_ptr value_traits_ptr; + typedef typename value_traits_pointers + <ValueTraits>::const_value_traits_ptr const_value_traits_ptr; + static const bool stateful_value_traits = + detail::is_stateful_value_traits<value_traits>::value; +}; + +template<class NodePtr, class StoredPointer, bool StatefulValueTraits = true> +struct iiterator_members +{ + + iiterator_members() + : nodeptr_()//Value initialization to achieve "null iterators" (N3644) + {} + + iiterator_members(const NodePtr &n_ptr, const StoredPointer &data) + : nodeptr_(n_ptr), ptr_(data) + {} + + StoredPointer get_ptr() const + { return ptr_; } + + NodePtr nodeptr_; + StoredPointer ptr_; +}; + +template<class NodePtr, class StoredPointer> +struct iiterator_members<NodePtr, StoredPointer, false> +{ + iiterator_members() + : nodeptr_()//Value initialization to achieve "null iterators" (N3644) + {} + + iiterator_members(const NodePtr &n_ptr, const StoredPointer &) + : nodeptr_(n_ptr) + {} + + StoredPointer get_ptr() const + { return StoredPointer(); } + + NodePtr nodeptr_; +}; + +namespace detail { + +template<class InputIt, class Distance> inline +void advance_impl(InputIt& it, Distance n, const std::input_iterator_tag&) +{ + while(n--) + ++it; +} + +template<class InputIt, class Distance> inline +void advance_impl(InputIt& it, Distance n, std::forward_iterator_tag &) +{ + while(n--) + ++it; +} + +template<class InputIt, class Distance> inline +void advance_impl(InputIt& it, Distance n, std::bidirectional_iterator_tag &) +{ + for (; 0 < n; --n) + ++it; + for (; n < 0; ++n) + --it; +} + +template<class InputIt, class Distance> +inline void advance_impl(InputIt& it, Distance n, const std::random_access_iterator_tag &) +{ + it += n; +} + +} //namespace detail + +template<class InputIt, class Distance> +inline void iterator_advance(InputIt& it, Distance n) +{ // increment iterator by offset, arbitrary iterators + boost::intrusive::detail::advance_impl(it, n, boost::intrusive::iterator_traits<InputIt>::iterator_category()); +} + +namespace detail{ + +template<class InputIt, class Distance, class Category> +inline void distance_impl(InputIt first, InputIt last, Distance& off, const Category &) +{ + while(first != last){ + ++off; + ++first; + } +} + +template<class InputIt, class Distance> inline +void distance_impl(InputIt first, InputIt last, Distance& off, const std::random_access_iterator_tag&) +{ + off += last - first; +} + +} //namespace detail + +template<class InputIt> inline +typename iterator_traits<InputIt>::difference_type iterator_distance(InputIt first, InputIt last) +{ + typename iterator_traits<InputIt>::difference_type off = 0; + boost::intrusive::detail::distance_impl(first, last, off, boost::intrusive::iterator_traits<InputIt>::iterator_category()); + return off; +} + + +} //namespace intrusive +} //namespace boost + +#endif //BOOST_INTRUSIVE_DETAIL_IITERATOR_HPP diff --git a/boost/intrusive/detail/is_stateful_value_traits.hpp b/boost/intrusive/detail/is_stateful_value_traits.hpp index 8677c666d4..da2260edf6 100644 --- a/boost/intrusive/detail/is_stateful_value_traits.hpp +++ b/boost/intrusive/detail/is_stateful_value_traits.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2009-2012. +// (C) Copyright Ion Gaztanaga 2009-2013. // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -13,7 +13,9 @@ #ifndef BOOST_INTRUSIVE_DETAIL_IS_STATEFUL_VALUE_TRAITS_HPP #define BOOST_INTRUSIVE_DETAIL_IS_STATEFUL_VALUE_TRAITS_HPP -#include <boost/intrusive/detail/config_begin.hpp> +#if defined(_MSC_VER) +# pragma once +#endif #if defined(_MSC_VER) && (_MSC_VER <= 1310) @@ -72,6 +74,4 @@ struct is_stateful_value_traits #endif -#include <boost/intrusive/detail/config_end.hpp> - #endif //@ifndef BOOST_INTRUSIVE_DETAIL_IS_STATEFUL_VALUE_TRAITS_HPP diff --git a/boost/intrusive/detail/key_nodeptr_comp.hpp b/boost/intrusive/detail/key_nodeptr_comp.hpp new file mode 100644 index 0000000000..dfee8b9bfc --- /dev/null +++ b/boost/intrusive/detail/key_nodeptr_comp.hpp @@ -0,0 +1,72 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_KEY_NODEPTR_COMP_HPP +#define BOOST_INTRUSIVE_DETAIL_KEY_NODEPTR_COMP_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/detail/ebo_functor_holder.hpp> + +namespace boost { +namespace intrusive { +namespace detail { + +template<class KeyValueCompare, class ValueTraits> +struct key_nodeptr_comp + : private ebo_functor_holder<KeyValueCompare> +{ + typedef ValueTraits value_traits; + typedef typename value_traits::value_type value_type; + typedef typename value_traits::node_ptr node_ptr; + typedef typename value_traits::const_node_ptr const_node_ptr; + typedef ebo_functor_holder<KeyValueCompare> base_t; + + key_nodeptr_comp(KeyValueCompare kcomp, const ValueTraits *traits) + : base_t(kcomp), traits_(traits) + {} + + template<class T> + struct is_node_ptr + { + static const bool value = is_same<T, const_node_ptr>::value || is_same<T, node_ptr>::value; + }; + + template<class T> + const value_type & key_forward + (const T &node, typename enable_if_c<is_node_ptr<T>::value>::type * = 0) const + { return *traits_->to_value_ptr(node); } + + template<class T> + const T & key_forward(const T &key, typename enable_if_c<!is_node_ptr<T>::value>::type* = 0) const + { return key; } + + + template<class KeyType, class KeyType2> + bool operator()(const KeyType &key1, const KeyType2 &key2) const + { return base_t::get()(this->key_forward(key1), this->key_forward(key2)); } + + template<class KeyType> + bool operator()(const KeyType &key1) const + { return base_t::get()(this->key_forward(key1)); } + + const ValueTraits *const traits_; +}; + +} //namespace detail{ +} //namespace intrusive{ +} //namespace boost{ + +#endif //BOOST_INTRUSIVE_DETAIL_KEY_NODEPTR_COMP_HPP diff --git a/boost/intrusive/detail/list_iterator.hpp b/boost/intrusive/detail/list_iterator.hpp new file mode 100644 index 0000000000..efddfba3f1 --- /dev/null +++ b/boost/intrusive/detail/list_iterator.hpp @@ -0,0 +1,129 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Olaf Krzikalla 2004-2006. +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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_LIST_ITERATOR_HPP +#define BOOST_INTRUSIVE_LIST_ITERATOR_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/detail/std_fwd.hpp> +#include <boost/intrusive/detail/iiterator.hpp> +#include <boost/intrusive/detail/mpl.hpp> + +namespace boost { +namespace intrusive { + +// list_iterator provides some basic functions for a +// node oriented bidirectional iterator: +template<class ValueTraits, bool IsConst> +class list_iterator +{ + protected: + typedef iiterator + <ValueTraits, IsConst, std::bidirectional_iterator_tag> types_t; + + static const bool stateful_value_traits = types_t::stateful_value_traits; + + typedef ValueTraits value_traits; + typedef typename types_t::node_traits node_traits; + + 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; + + public: + typedef typename types_t::iterator_traits::difference_type difference_type; + typedef typename types_t::iterator_traits::value_type value_type; + typedef typename types_t::iterator_traits::pointer pointer; + typedef typename types_t::iterator_traits::reference reference; + typedef typename types_t::iterator_traits::iterator_category iterator_category; + + list_iterator() + {} + + explicit list_iterator(const node_ptr & nodeptr, const const_value_traits_ptr &traits_ptr) + : members_(nodeptr, traits_ptr) + {} + + list_iterator(list_iterator<ValueTraits, false> const& other) + : members_(other.pointed_node(), other.get_value_traits()) + {} + + const node_ptr &pointed_node() const + { return members_.nodeptr_; } + + list_iterator &operator=(const node_ptr &node) + { members_.nodeptr_ = node; return static_cast<list_iterator&>(*this); } + + const_value_traits_ptr get_value_traits() const + { return members_.get_ptr(); } + + public: + list_iterator& operator++() + { + node_ptr p = node_traits::get_next(members_.nodeptr_); + members_.nodeptr_ = p; + return static_cast<list_iterator&> (*this); + } + + list_iterator operator++(int) + { + list_iterator result (*this); + members_.nodeptr_ = node_traits::get_next(members_.nodeptr_); + return result; + } + + list_iterator& operator--() + { + members_.nodeptr_ = node_traits::get_previous(members_.nodeptr_); + return static_cast<list_iterator&> (*this); + } + + list_iterator operator--(int) + { + list_iterator result (*this); + members_.nodeptr_ = node_traits::get_previous(members_.nodeptr_); + return result; + } + + friend bool operator== (const list_iterator& l, const list_iterator& r) + { return l.pointed_node() == r.pointed_node(); } + + friend bool operator!= (const list_iterator& l, const list_iterator& r) + { return !(l == r); } + + reference operator*() const + { return *operator->(); } + + pointer operator->() const + { return this->operator_arrow(detail::bool_<stateful_value_traits>()); } + + list_iterator<ValueTraits, false> unconst() const + { return list_iterator<ValueTraits, false>(this->pointed_node(), this->get_value_traits()); } + + private: + pointer operator_arrow(detail::false_) const + { return ValueTraits::to_value_ptr(members_.nodeptr_); } + + pointer operator_arrow(detail::true_) const + { return this->get_value_traits()->to_value_ptr(members_.nodeptr_); } + + iiterator_members<node_ptr, const_value_traits_ptr, stateful_value_traits> members_; +}; + +} //namespace intrusive +} //namespace boost + +#endif //BOOST_INTRUSIVE_LIST_ITERATOR_HPP diff --git a/boost/intrusive/detail/list_node.hpp b/boost/intrusive/detail/list_node.hpp index d406af60e4..ba97ece956 100644 --- a/boost/intrusive/detail/list_node.hpp +++ b/boost/intrusive/detail/list_node.hpp @@ -1,7 +1,7 @@ ///////////////////////////////////////////////////////////////////////////// // // (C) Copyright Olaf Krzikalla 2004-2006. -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -14,10 +14,11 @@ #ifndef BOOST_INTRUSIVE_LIST_NODE_HPP #define BOOST_INTRUSIVE_LIST_NODE_HPP -#include <boost/intrusive/detail/config_begin.hpp> -#include <iterator> -#include <boost/intrusive/detail/assert.hpp> -#include <boost/intrusive/pointer_traits.hpp> +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/pointer_rebind.hpp> namespace boost { namespace intrusive { @@ -29,8 +30,7 @@ namespace intrusive { template<class VoidPointer> struct list_node { - typedef typename pointer_traits - <VoidPointer>:: template rebind_pointer<list_node>::type node_ptr; + typedef typename pointer_rebind<VoidPointer, list_node>::type node_ptr; node_ptr next_; node_ptr prev_; }; @@ -38,153 +38,30 @@ struct list_node template<class VoidPointer> struct list_node_traits { - typedef list_node<VoidPointer> node; - typedef typename pointer_traits - <VoidPointer>:: template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>:: template rebind_pointer<const node>::type const_node_ptr; + typedef list_node<VoidPointer> node; + typedef typename node::node_ptr node_ptr; + typedef typename pointer_rebind<VoidPointer, const node>::type const_node_ptr; + + static node_ptr get_previous(const const_node_ptr & n) + { return n->prev_; } - static const node_ptr &get_previous(const const_node_ptr & n) + static node_ptr get_previous(const node_ptr & n) { return n->prev_; } static void set_previous(const node_ptr & n, const node_ptr & prev) { n->prev_ = prev; } - static const node_ptr &get_next(const const_node_ptr & n) + static node_ptr get_next(const const_node_ptr & n) + { return n->next_; } + + static node_ptr get_next(const node_ptr & n) { return n->next_; } static void set_next(const node_ptr & n, const node_ptr & next) { n->next_ = next; } }; -// list_iterator provides some basic functions for a -// node oriented bidirectional iterator: -template<class Container, bool IsConst> -class list_iterator - : public std::iterator - < std::bidirectional_iterator_tag - , typename Container::value_type - , typename Container::difference_type - , typename detail::if_c<IsConst,typename Container::const_pointer,typename Container::pointer>::type - , typename detail::if_c<IsConst,typename Container::const_reference,typename Container::reference>::type - > -{ - protected: - typedef typename Container::real_value_traits real_value_traits; - typedef typename real_value_traits::node_traits node_traits; - typedef typename node_traits::node node; - typedef typename node_traits::node_ptr node_ptr; - typedef typename pointer_traits<node_ptr>:: - template rebind_pointer<void>::type void_pointer; - static const bool store_container_ptr = - detail::store_cont_ptr_on_it<Container>::value; - - public: - typedef typename Container::value_type value_type; - typedef typename detail::if_c<IsConst,typename Container::const_pointer,typename Container::pointer>::type pointer; - typedef typename detail::if_c<IsConst,typename Container::const_reference,typename Container::reference>::type reference; - - list_iterator() - : members_ (node_ptr(), 0) - {} - - explicit list_iterator(const node_ptr & node, const Container *cont_ptr) - : members_ (node, cont_ptr) - {} - - list_iterator(list_iterator<Container, false> const& other) - : members_(other.pointed_node(), other.get_container()) - {} - - const node_ptr &pointed_node() const - { return members_.nodeptr_; } - - list_iterator &operator=(const node_ptr &node) - { members_.nodeptr_ = node; return static_cast<list_iterator&>(*this); } - - public: - list_iterator& operator++() - { - node_ptr p = node_traits::get_next(members_.nodeptr_); - members_.nodeptr_ = p; - //members_.nodeptr_ = node_traits::get_next(members_.nodeptr_); - return static_cast<list_iterator&> (*this); - } - - list_iterator operator++(int) - { - list_iterator result (*this); - members_.nodeptr_ = node_traits::get_next(members_.nodeptr_); - return result; - } - - list_iterator& operator--() - { - members_.nodeptr_ = node_traits::get_previous(members_.nodeptr_); - return static_cast<list_iterator&> (*this); - } - - list_iterator operator--(int) - { - list_iterator result (*this); - members_.nodeptr_ = node_traits::get_previous(members_.nodeptr_); - return result; - } - - friend bool operator== (const list_iterator& l, const list_iterator& r) - { return l.pointed_node() == r.pointed_node(); } - - friend bool operator!= (const list_iterator& l, const list_iterator& r) - { return !(l == r); } - - reference operator*() const - { return *operator->(); } - - pointer operator->() const - { return this->get_real_value_traits()->to_value_ptr(members_.nodeptr_); } - - const Container *get_container() const - { - if(store_container_ptr){ - const Container* c = static_cast<const Container*>(members_.get_ptr()); - BOOST_INTRUSIVE_INVARIANT_ASSERT(c != 0); - return c; - } - else{ - return 0; - } - } - - const real_value_traits *get_real_value_traits() const - { - if(store_container_ptr) - return &this->get_container()->get_real_value_traits(); - else - return 0; - } - - list_iterator<Container, false> unconst() const - { return list_iterator<Container, false>(this->pointed_node(), this->get_container()); } - - private: - struct members - : public detail::select_constptr - <void_pointer, store_container_ptr>::type - { - typedef typename detail::select_constptr - <void_pointer, store_container_ptr>::type Base; - - members(const node_ptr &n_ptr, const void *cont) - : Base(cont), nodeptr_(n_ptr) - {} - - node_ptr nodeptr_; - } members_; -}; - } //namespace intrusive } //namespace boost -#include <boost/intrusive/detail/config_end.hpp> - #endif //BOOST_INTRUSIVE_LIST_NODE_HPP diff --git a/boost/intrusive/detail/math.hpp b/boost/intrusive/detail/math.hpp new file mode 100644 index 0000000000..f212ae743f --- /dev/null +++ b/boost/intrusive/detail/math.hpp @@ -0,0 +1,271 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_MATH_HPP +#define BOOST_INTRUSIVE_DETAIL_MATH_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <cstddef> +#include <climits> + +namespace boost { +namespace intrusive { +namespace detail { + +/////////////////////////// +// floor_log2 Dispatcher +//////////////////////////// + +#if defined(_MSC_VER) && (_MSC_VER >= 1300) + + }}} //namespace boost::intrusive::detail + + //Use _BitScanReverseXX intrinsics + + #if defined(_M_X64) || defined(_M_AMD64) || defined(_M_IA64) //64 bit target + #define BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT + #endif + + #ifndef __INTRIN_H_ // Avoid including any windows system header + #ifdef __cplusplus + extern "C" { + #endif // __cplusplus + + #if defined(BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT) //64 bit target + unsigned char _BitScanReverse64(unsigned long *index, unsigned __int64 mask); + #pragma intrinsic(_BitScanReverse64) + #else //32 bit target + unsigned char _BitScanReverse(unsigned long *index, unsigned long mask); + #pragma intrinsic(_BitScanReverse) + #endif + + #ifdef __cplusplus + } + #endif // __cplusplus + #endif // __INTRIN_H_ + + #ifdef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT + #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse64 + #undef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT + #else + #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse + #endif + + namespace boost { + namespace intrusive { + namespace detail { + + inline std::size_t floor_log2 (std::size_t x) + { + unsigned long log2; + BOOST_INTRUSIVE_BSR_INTRINSIC( &log2, (unsigned long)x ); + return log2; + } + + #undef BOOST_INTRUSIVE_BSR_INTRINSIC + +#elif defined(__GNUC__) && ((__GNUC__ >= 4) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) //GCC >=3.4 + + //Compile-time error in case of missing specialization + template<class Uint> + struct builtin_clz_dispatch; + + #if defined(BOOST_HAS_LONG_LONG) + template<> + struct builtin_clz_dispatch<unsigned long long> + { + static unsigned long long call(unsigned long long n) + { return __builtin_clzll(n); } + }; + #endif + + template<> + struct builtin_clz_dispatch<unsigned long> + { + static unsigned long call(unsigned long n) + { return __builtin_clzl(n); } + }; + + template<> + struct builtin_clz_dispatch<unsigned int> + { + static unsigned int call(unsigned int n) + { return __builtin_clz(n); } + }; + + inline std::size_t floor_log2(std::size_t n) + { + return sizeof(std::size_t)*CHAR_BIT - std::size_t(1) - builtin_clz_dispatch<std::size_t>::call(n); + } + +#else //Portable methods + +//////////////////////////// +// Generic method +//////////////////////////// + + inline std::size_t floor_log2_get_shift(std::size_t n, true_ )//power of two size_t + { return n >> 1; } + + inline std::size_t floor_log2_get_shift(std::size_t n, false_ )//non-power of two size_t + { return (n >> 1) + ((n & 1u) & (n != 1)); } + + template<std::size_t N> + inline std::size_t floor_log2 (std::size_t x, integer<std::size_t, N>) + { + const std::size_t Bits = N; + const bool Size_t_Bits_Power_2= !(Bits & (Bits-1)); + + std::size_t n = x; + std::size_t log2 = 0; + + std::size_t remaining_bits = Bits; + std::size_t shift = floor_log2_get_shift(remaining_bits, bool_<Size_t_Bits_Power_2>()); + while(shift){ + std::size_t tmp = n >> shift; + if (tmp){ + log2 += shift, n = tmp; + } + shift = floor_log2_get_shift(shift, bool_<Size_t_Bits_Power_2>()); + } + + return log2; + } + + //////////////////////////// + // DeBruijn method + //////////////////////////// + + //Taken from: + //http://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers + //Thanks to Desmond Hume + + inline std::size_t floor_log2 (std::size_t v, integer<std::size_t, 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 + }; + + v |= v >> 1; + v |= v >> 2; + v |= v >> 4; + v |= v >> 8; + v |= v >> 16; + + return MultiplyDeBruijnBitPosition[(std::size_t)(v * 0x07C4ACDDU) >> 27]; + } + + inline std::size_t floor_log2 (std::size_t v, integer<std::size_t, 64>) + { + static const std::size_t MultiplyDeBruijnBitPosition[64] = { + 63, 0, 58, 1, 59, 47, 53, 2, + 60, 39, 48, 27, 54, 33, 42, 3, + 61, 51, 37, 40, 49, 18, 28, 20, + 55, 30, 34, 11, 43, 14, 22, 4, + 62, 57, 46, 52, 38, 26, 32, 41, + 50, 36, 17, 19, 29, 10, 13, 21, + 56, 45, 25, 31, 35, 16, 9, 12, + 44, 24, 15, 8, 23, 7, 6, 5}; + + v |= v >> 1; + v |= v >> 2; + v |= v >> 4; + v |= v >> 8; + v |= v >> 16; + v |= v >> 32; + return MultiplyDeBruijnBitPosition[((std::size_t)((v - (v >> 1))*0x07EDD5E59A4E28C2ULL)) >> 58]; + } + + + inline std::size_t floor_log2 (std::size_t x) + { + const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT; + return floor_log2(x, integer<std::size_t, Bits>()); + } + +#endif + +//Thanks to Laurent de Soras in +//http://www.flipcode.com/archives/Fast_log_Function.shtml +inline float fast_log2 (float val) +{ + union caster_t + { + unsigned x; + float val; + } caster; + + caster.val = val; + unsigned x = caster.x; + const int log_2 = int((x >> 23) & 255) - 128; + x &= ~(unsigned(255u) << 23u); + x += unsigned(127) << 23u; + caster.x = x; + val = caster.val; + //1+log2(m), m ranging from 1 to 2 + //3rd degree polynomial keeping first derivate continuity. + //For less precision the line can be commented out + val = ((-1.f/3.f) * val + 2.f) * val - (2.f/3.f); + return val + static_cast<float>(log_2); +} + +inline std::size_t ceil_log2 (std::size_t x) +{ + return static_cast<std::size_t>((x & (x-1)) != 0) + floor_log2(x); +} + +template<class SizeType, std::size_t N> +struct numbits_eq +{ + static const bool value = sizeof(SizeType)*CHAR_BIT == N; +}; + +template<class SizeType, class Enabler = void > +struct sqrt2_pow_max; + +template <class SizeType> +struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 32> >::type> +{ + static const SizeType value = 0xb504f334; + static const std::size_t pow = 31; +}; + +#ifndef BOOST_NO_INT64_T + +template <class SizeType> +struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 64> >::type> +{ + static const SizeType value = 0xb504f333f9de6484ull; + static const std::size_t pow = 63; +}; + +#endif //BOOST_NO_INT64_T + +// Returns floor(pow(sqrt(2), x * 2 + 1)). +// Defined for X from 0 up to the number of bits in size_t minus 1. +inline std::size_t sqrt2_pow_2xplus1 (std::size_t x) +{ + const std::size_t value = (std::size_t)sqrt2_pow_max<std::size_t>::value; + const std::size_t pow = (std::size_t)sqrt2_pow_max<std::size_t>::pow; + return (value >> (pow - x)) + 1; +} + +} //namespace detail +} //namespace intrusive +} //namespace boost + +#endif //BOOST_INTRUSIVE_DETAIL_MATH_HPP diff --git a/boost/intrusive/detail/memory_util.hpp b/boost/intrusive/detail/memory_util.hpp index 1a6431b078..18a5d3e7e2 100644 --- a/boost/intrusive/detail/memory_util.hpp +++ b/boost/intrusive/detail/memory_util.hpp @@ -6,7 +6,7 @@ // ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2011-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2011-2014. Distributed under the Boost // Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // @@ -17,14 +17,14 @@ #ifndef BOOST_INTRUSIVE_ALLOCATOR_MEMORY_UTIL_HPP #define BOOST_INTRUSIVE_ALLOCATOR_MEMORY_UTIL_HPP -#if (defined _MSC_VER) && (_MSC_VER >= 1200) +#if defined(_MSC_VER) # pragma once #endif -#include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/detail/workaround.hpp> #include <boost/intrusive/detail/mpl.hpp> #include <boost/intrusive/detail/preprocessor.hpp> +#include <boost/preprocessor/iteration/iterate.hpp> namespace boost { namespace intrusive { @@ -41,10 +41,6 @@ inline T* addressof(T& obj) ); } -template <typename T> struct unvoid { typedef T type; }; -template <> struct unvoid<void> { struct type { }; }; -template <> struct unvoid<const void> { struct type { }; }; - template <typename T> struct LowPriorityConversion { @@ -52,61 +48,6 @@ struct LowPriorityConversion LowPriorityConversion(const T&) { } }; -// Infrastructure for providing a default type for T::TNAME if absent. -#define BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(TNAME) \ - template <typename T, typename DefaultType> \ - struct boost_intrusive_default_type_ ## TNAME \ - { \ - template <typename X> \ - static char test(int, typename X::TNAME*); \ - \ - template <typename X> \ - static int test(boost::intrusive::detail:: \ - LowPriorityConversion<int>, void*); \ - \ - struct DefaultWrap { typedef DefaultType TNAME; }; \ - \ - static const bool value = (1 == sizeof(test<T>(0, 0))); \ - \ - typedef typename \ - ::boost::intrusive::detail::if_c \ - <value, T, DefaultWrap>::type::TNAME type; \ - }; \ - \ - template <typename T, typename DefaultType> \ - struct boost_intrusive_eval_default_type_ ## TNAME \ - { \ - template <typename X> \ - static char test(int, typename X::TNAME*); \ - \ - template <typename X> \ - static int test(boost::intrusive::detail:: \ - LowPriorityConversion<int>, void*); \ - \ - struct DefaultWrap \ - { typedef typename DefaultType::type TNAME; }; \ - \ - static const bool value = (1 == sizeof(test<T>(0, 0))); \ - \ - typedef typename \ - ::boost::intrusive::detail::eval_if_c \ - < value \ - , ::boost::intrusive::detail::identity<T> \ - , ::boost::intrusive::detail::identity<DefaultWrap> \ - >::type::TNAME type; \ - }; \ -// - -#define BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT(INSTANTIATION_NS_PREFIX, T, TNAME, TIMPL) \ - typename INSTANTIATION_NS_PREFIX \ - boost_intrusive_default_type_ ## TNAME< T, TIMPL >::type \ -// - -#define BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_EVAL_DEFAULT(INSTANTIATION_NS_PREFIX, T, TNAME, TIMPL) \ - typename INSTANTIATION_NS_PREFIX \ - boost_intrusive_eval_default_type_ ## TNAME< T, TIMPL >::type \ -// - }}} //namespace boost::intrusive::detail #include <boost/intrusive/detail/has_member_function_callable_with.hpp> @@ -114,25 +55,25 @@ struct LowPriorityConversion #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, (0, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) +#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) #include BOOST_PP_ITERATE() #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME static_cast_from #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN namespace boost { namespace intrusive { namespace detail { #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}} -#define BOOST_PP_ITERATION_PARAMS_1 (3, (0, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) +#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) #include BOOST_PP_ITERATE() #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME const_cast_from #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN namespace boost { namespace intrusive { namespace detail { #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}} -#define BOOST_PP_ITERATION_PARAMS_1 (3, (0, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) +#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) #include BOOST_PP_ITERATE() #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME dynamic_cast_from #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN namespace boost { namespace intrusive { namespace detail { #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}} -#define BOOST_PP_ITERATION_PARAMS_1 (3, (0, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) +#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) #include BOOST_PP_ITERATE() namespace boost { @@ -141,148 +82,11 @@ namespace detail { BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(element_type) BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(difference_type) - -////////////////////// -//struct first_param -////////////////////// - -template <typename T> struct first_param -{ typedef void type; }; - -#if !defined(BOOST_NO_VARIADIC_TEMPLATES) - - template <template <typename, typename...> class TemplateClass, typename T, typename... Args> - struct first_param< TemplateClass<T, Args...> > - { - typedef T type; - }; - -#else //C++03 compilers - - #define BOOST_PP_LOCAL_MACRO(n) \ - template < template <typename \ - BOOST_PP_ENUM_TRAILING(n, BOOST_INTRUSIVE_PP_IDENTITY, typename) > \ - class TemplateClass \ - , typename T BOOST_PP_ENUM_TRAILING_PARAMS(n, class P)> \ - struct first_param \ - < TemplateClass<T BOOST_PP_ENUM_TRAILING_PARAMS(n, P)> > \ - { \ - typedef T type; \ - }; \ - // - #define BOOST_PP_LOCAL_LIMITS (0, BOOST_INTRUSIVE_MAX_CONSTRUCTOR_PARAMETERS) - #include BOOST_PP_LOCAL_ITERATE() - -#endif //!defined(BOOST_NO_VARIADIC_TEMPLATES) - -/////////////////////////// -//struct type_rebind_mode -/////////////////////////// -template <typename Ptr, typename T> -struct type_has_rebind -{ - template <typename X> - #if !defined (__SUNPRO_CC) - static char test(int, typename X::template rebind<T>*); - #else - static char test(int, typename X::rebind<T>*); - #endif - - template <typename X> - static int test(boost::intrusive::detail::LowPriorityConversion<int>, void*); - - static const bool value = (1 == sizeof(test<Ptr>(0, 0))); -}; - -template <typename Ptr, typename T> -struct type_has_rebind_other -{ - template <typename X> - #if !defined (__SUNPRO_CC) - static char test(int, typename X::template rebind<T>::other*); - #else - static char test(int, typename X::rebind<T>::other*); - #endif - - template <typename X> - static int test(boost::intrusive::detail::LowPriorityConversion<int>, void*); - - static const bool value = (1 == sizeof(test<Ptr>(0, 0))); -}; - -template <typename Ptr, typename T> -struct type_rebind_mode -{ - static const unsigned int rebind = (unsigned int)type_has_rebind<Ptr, T>::value; - static const unsigned int rebind_other = (unsigned int)type_has_rebind_other<Ptr, T>::value; - static const unsigned int mode = rebind + rebind*rebind_other; -}; - -//////////////////////// -//struct type_rebinder -//////////////////////// -template <typename Ptr, typename U, unsigned int RebindMode = type_rebind_mode<Ptr, U>::mode> -struct type_rebinder; - -// Implementation of pointer_traits<Ptr>::rebind if Ptr has -// its own rebind::other type (C++03) -template <typename Ptr, typename U> -struct type_rebinder< Ptr, U, 2u > -{ - typedef typename Ptr::template rebind<U>::other type; -}; - -// Implementation of pointer_traits<Ptr>::rebind if Ptr has -// its own rebind template. -template <typename Ptr, typename U> -struct type_rebinder< Ptr, U, 1u > -{ - typedef typename Ptr::template rebind<U> type; -}; - -// Specialization of pointer_traits<Ptr>::rebind if Ptr does not -// have its own rebind template but has a the form Ptr<class T, -// OtherArgs>, where OtherArgs comprises zero or more type parameters. -// Many pointers fit this form, hence many pointers will get a -// reasonable default for rebind. -#if !defined(BOOST_NO_VARIADIC_TEMPLATES) - -template <template <class, class...> class Ptr, typename T, class... Tn, class U> -struct type_rebinder<Ptr<T, Tn...>, U, 0u > -{ - typedef Ptr<U, Tn...> type; -}; - -//Needed for non-conforming compilers like GCC 4.3 -template <template <class> class Ptr, typename T, class U> -struct type_rebinder<Ptr<T>, U, 0u > -{ - typedef Ptr<U> type; -}; - -#else //C++03 compilers - -#define BOOST_PP_LOCAL_MACRO(n) \ -template < template <typename \ - BOOST_PP_ENUM_TRAILING(n, BOOST_INTRUSIVE_PP_IDENTITY, typename) > \ - class Ptr \ - , typename T BOOST_PP_ENUM_TRAILING_PARAMS(n, class P) \ - , class U> \ -struct type_rebinder \ - < Ptr<T BOOST_PP_ENUM_TRAILING_PARAMS(n, P)>, U, 0u > \ -{ \ - typedef Ptr<U BOOST_PP_ENUM_TRAILING_PARAMS(n, P)> type; \ -}; \ -// -#define BOOST_PP_LOCAL_LIMITS (0, BOOST_INTRUSIVE_MAX_CONSTRUCTOR_PARAMETERS) -#include BOOST_PP_LOCAL_ITERATE() - -#endif //!defined(BOOST_NO_VARIADIC_TEMPLATES) +BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(reference) +BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(value_traits_ptr) } //namespace detail { } //namespace intrusive { } //namespace boost { -#include <boost/intrusive/detail/config_end.hpp> - #endif // ! defined(BOOST_INTRUSIVE_ALLOCATOR_MEMORY_UTIL_HPP) diff --git a/boost/intrusive/detail/mpl.hpp b/boost/intrusive/detail/mpl.hpp index 02b1361d2a..9b2c9f114c 100644 --- a/boost/intrusive/detail/mpl.hpp +++ b/boost/intrusive/detail/mpl.hpp @@ -1,6 +1,7 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2014 +// (C) Copyright Microsoft Corporation 2014 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -13,6 +14,10 @@ #ifndef BOOST_INTRUSIVE_DETAIL_MPL_HPP #define BOOST_INTRUSIVE_DETAIL_MPL_HPP +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/detail/config_begin.hpp> #include <cstddef> @@ -20,6 +25,76 @@ namespace boost { namespace intrusive { namespace detail { +template <typename T, typename U> +struct is_same +{ + static const bool value = false; +}; + +template <typename T> +struct is_same<T, T> +{ + static const bool value = true; +}; + +template<typename T> +struct add_const +{ typedef const T type; }; + +template<typename T> +struct remove_const +{ typedef T type; }; + +template<typename T> +struct remove_const<const T> +{ typedef T type; }; + +template<typename T> +struct remove_cv +{ typedef T type; }; + +template<typename T> +struct remove_cv<const T> +{ typedef T type; }; + +template<typename T> +struct remove_cv<const volatile T> +{ typedef T type; }; + +template<typename T> +struct remove_cv<volatile T> +{ typedef T type; }; + +template<class T> +struct remove_reference +{ + typedef T type; +}; + +template<class T> +struct remove_reference<T&> +{ + typedef T type; +}; + +template<class T> +struct remove_pointer +{ + typedef T type; +}; + +template<class T> +struct remove_pointer<T*> +{ + typedef T type; +}; + +template<class T> +struct add_pointer +{ + typedef T *type; +}; + typedef char one; struct two {one _[2];}; @@ -29,6 +104,12 @@ struct bool_ static const bool value = C_; }; +template< class Integer, Integer Value > +struct integer +{ + static const Integer value = Value; +}; + typedef bool_<true> true_; typedef bool_<false> false_; @@ -58,18 +139,32 @@ struct apply typedef typename F::template apply<Param>::type type; }; +#if defined(_MSC_VER) && (_MSC_VER >= 1400) + +template <class T, class U> +struct is_convertible +{ + static const bool value = __is_convertible_to(T, U); +}; + +#else + template <class T, class U> class is_convertible { typedef char true_t; class false_t { char dummy[2]; }; - static true_t dispatch(U); + //use any_conversion as first parameter since in MSVC + //overaligned types can't go through ellipsis static false_t dispatch(...); - static const T &trigger(); + static true_t dispatch(U); + static typename remove_reference<T>::type &trigger(); public: static const bool value = sizeof(dispatch(trigger())) == sizeof(true_t); }; +#endif + template< bool C , typename T1 @@ -124,134 +219,16 @@ struct identity typedef T type; }; -#if defined(BOOST_MSVC) || defined(__BORLANDC_) -#define BOOST_INTRUSIVE_TT_DECL __cdecl -#else -#define BOOST_INTRUSIVE_TT_DECL -#endif - -#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) && !defined(UNDER_CE) -#define BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS -#endif - -template <typename T> -struct is_unary_or_binary_function_impl -{ static const bool value = false; }; - -// see boost ticket #4094 -// avoid duplicate definitions of is_unary_or_binary_function_impl -#ifndef BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS - -template <typename R> -struct is_unary_or_binary_function_impl<R (*)()> -{ static const bool value = true; }; - -template <typename R> -struct is_unary_or_binary_function_impl<R (*)(...)> -{ static const bool value = true; }; - -#else // BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS - -template <typename R> -struct is_unary_or_binary_function_impl<R (__stdcall*)()> -{ static const bool value = true; }; - -#ifndef _MANAGED - -template <typename R> -struct is_unary_or_binary_function_impl<R (__fastcall*)()> -{ static const bool value = true; }; - -#endif - -template <typename R> -struct is_unary_or_binary_function_impl<R (__cdecl*)()> -{ static const bool value = true; }; - -template <typename R> -struct is_unary_or_binary_function_impl<R (__cdecl*)(...)> -{ static const bool value = true; }; - -#endif - -// see boost ticket #4094 -// avoid duplicate definitions of is_unary_or_binary_function_impl -#ifndef BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS - -template <typename R, class T0> -struct is_unary_or_binary_function_impl<R (*)(T0)> -{ static const bool value = true; }; - -template <typename R, class T0> -struct is_unary_or_binary_function_impl<R (*)(T0...)> -{ static const bool value = true; }; - -#else // BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS - -template <typename R, class T0> -struct is_unary_or_binary_function_impl<R (__stdcall*)(T0)> -{ static const bool value = true; }; - -#ifndef _MANAGED - -template <typename R, class T0> -struct is_unary_or_binary_function_impl<R (__fastcall*)(T0)> -{ static const bool value = true; }; - -#endif - -template <typename R, class T0> -struct is_unary_or_binary_function_impl<R (__cdecl*)(T0)> -{ static const bool value = true; }; - -template <typename R, class T0> -struct is_unary_or_binary_function_impl<R (__cdecl*)(T0...)> -{ static const bool value = true; }; - -#endif - -// see boost ticket #4094 -// avoid duplicate definitions of is_unary_or_binary_function_impl -#ifndef BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS - -template <typename R, class T0, class T1> -struct is_unary_or_binary_function_impl<R (*)(T0, T1)> -{ static const bool value = true; }; - -template <typename R, class T0, class T1> -struct is_unary_or_binary_function_impl<R (*)(T0, T1...)> -{ static const bool value = true; }; - -#else // BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS - -template <typename R, class T0, class T1> -struct is_unary_or_binary_function_impl<R (__stdcall*)(T0, T1)> -{ static const bool value = true; }; - -#ifndef _MANAGED - -template <typename R, class T0, class T1> -struct is_unary_or_binary_function_impl<R (__fastcall*)(T0, T1)> -{ static const bool value = true; }; - -#endif - -template <typename R, class T0, class T1> -struct is_unary_or_binary_function_impl<R (__cdecl*)(T0, T1)> -{ static const bool value = true; }; - -template <typename R, class T0, class T1> -struct is_unary_or_binary_function_impl<R (__cdecl*)(T0, T1...)> -{ static const bool value = true; }; -#endif - -template <typename T> -struct is_unary_or_binary_function_impl<T&> -{ static const bool value = false; }; +template<class T, bool Add> +struct add_const_if_c +{ + typedef typename if_c + < Add + , typename add_const<T>::type + , T + >::type type; +}; -template<typename T> -struct is_unary_or_binary_function -{ static const bool value = is_unary_or_binary_function_impl<T>::value; }; //boost::alignment_of yields to 10K lines of preprocessed code, so we //need an alternative @@ -280,49 +257,6 @@ struct alignment_of >::value; }; -template <typename T, typename U> -struct is_same -{ - typedef char yes_type; - struct no_type - { - char padding[8]; - }; - - template <typename V> - static yes_type is_same_tester(V*, V*); - static no_type is_same_tester(...); - - static T *t; - static U *u; - - static const bool value = sizeof(yes_type) == sizeof(is_same_tester(t,u)); -}; - -template<typename T> -struct add_const -{ typedef const T type; }; - -template<typename T> -struct remove_const -{ typedef T type; }; - -template<typename T> -struct remove_const<const T> -{ typedef T type; }; - -template<class T> -struct remove_reference -{ - typedef T type; -}; - -template<class T> -struct remove_reference<T&> -{ - typedef T type; -}; - template<class Class> class is_empty_class { @@ -358,6 +292,81 @@ struct ls_zeros<1> static const std::size_t value = 0; }; +template <typename T> struct unvoid_ref { typedef T &type; }; +template <> struct unvoid_ref<void> { struct type_impl { }; typedef type_impl & type; }; +template <> struct unvoid_ref<const void> { struct type_impl { }; typedef type_impl & type; }; + +// Infrastructure for providing a default type for T::TNAME if absent. +#define BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(TNAME) \ + template <typename T, typename DefaultType> \ + struct boost_intrusive_default_type_ ## TNAME \ + { \ + template <typename X> \ + static char test(int, typename X::TNAME*); \ + \ + template <typename X> \ + static int test(...); \ + \ + struct DefaultWrap { typedef DefaultType TNAME; }; \ + \ + static const bool value = (1 == sizeof(test<T>(0, 0))); \ + \ + typedef typename \ + ::boost::intrusive::detail::if_c \ + <value, T, DefaultWrap>::type::TNAME type; \ + }; \ + \ + template <typename T, typename DefaultType> \ + struct boost_intrusive_eval_default_type_ ## TNAME \ + { \ + template <typename X> \ + static char test(int, typename X::TNAME*); \ + \ + template <typename X> \ + static int test(...); \ + \ + struct DefaultWrap \ + { typedef typename DefaultType::type TNAME; }; \ + \ + static const bool value = (1 == sizeof(test<T>(0, 0))); \ + \ + typedef typename \ + ::boost::intrusive::detail::eval_if_c \ + < value \ + , ::boost::intrusive::detail::identity<T> \ + , ::boost::intrusive::detail::identity<DefaultWrap> \ + >::type::TNAME type; \ + }; \ +// + +#define BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT(INSTANTIATION_NS_PREFIX, T, TNAME, TIMPL) \ + typename INSTANTIATION_NS_PREFIX \ + boost_intrusive_default_type_ ## TNAME< T, TIMPL >::type \ +// + +#define BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_EVAL_DEFAULT(INSTANTIATION_NS_PREFIX, T, TNAME, TIMPL) \ + typename INSTANTIATION_NS_PREFIX \ + boost_intrusive_eval_default_type_ ## TNAME< T, TIMPL >::type \ +// + +#define BOOST_INTRUSIVE_INTERNAL_STATIC_BOOL_IS_TRUE(TRAITS_PREFIX, TYPEDEF_TO_FIND) \ +template <class T>\ +struct TRAITS_PREFIX##_bool\ +{\ + template<bool Add>\ + struct two_or_three {one _[2 + Add];};\ + template <class U> static one test(...);\ + template <class U> static two_or_three<U::TYPEDEF_TO_FIND> test (int);\ + static const std::size_t value = sizeof(test<T>(0));\ +};\ +\ +template <class T>\ +struct TRAITS_PREFIX##_bool_is_true\ +{\ + static const bool value = TRAITS_PREFIX##_bool<T>::value > sizeof(one)*2;\ +};\ +// + } //namespace detail } //namespace intrusive } //namespace boost diff --git a/boost/intrusive/detail/node_cloner_disposer.hpp b/boost/intrusive/detail/node_cloner_disposer.hpp new file mode 100644 index 0000000000..2a18100205 --- /dev/null +++ b/boost/intrusive/detail/node_cloner_disposer.hpp @@ -0,0 +1,109 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_NODE_CLONER_DISPOSER_HPP +#define BOOST_INTRUSIVE_DETAIL_NODE_CLONER_DISPOSER_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/detail/ebo_functor_holder.hpp> +#include <boost/intrusive/detail/algo_type.hpp> +#include <boost/intrusive/detail/assert.hpp> + +namespace boost { +namespace intrusive { +namespace detail { + +template<class F, class ValueTraits, algo_types AlgoType> +struct node_cloner + : private ebo_functor_holder<F> +{ + typedef ValueTraits value_traits; + typedef typename value_traits::node_traits node_traits; + typedef typename node_traits::node_ptr node_ptr; + typedef ebo_functor_holder<F> base_t; + typedef typename get_algo< AlgoType + , node_traits>::type node_algorithms; + static const bool safemode_or_autounlink = + is_safe_autounlink<value_traits::link_mode>::value; + typedef typename value_traits::value_type value_type; + typedef typename value_traits::pointer pointer; + typedef typename node_traits::node node; + typedef typename value_traits::const_node_ptr const_node_ptr; + typedef typename value_traits::reference reference; + typedef typename value_traits::const_reference const_reference; + + node_cloner(F f, const ValueTraits *traits) + : base_t(f), traits_(traits) + {} + + // 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); + 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) + BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n)); + return n; + } + + // hashtables use this method, which is proxy-reference unfriendly + node_ptr operator()(const node &to_clone) + { + const value_type &v = + *traits_->to_value_ptr + (pointer_traits<const_node_ptr>::pointer_to(to_clone)); + node_ptr n = traits_->to_node_ptr(*base_t::get()(v)); + //Cloned node must be in default mode if the linking mode requires it + if(safemode_or_autounlink) + BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n)); + return n; + } + + const ValueTraits * const traits_; +}; + +template<class F, class ValueTraits, algo_types AlgoType> +struct node_disposer + : private ebo_functor_holder<F> +{ + typedef ValueTraits value_traits; + typedef typename value_traits::node_traits node_traits; + typedef typename node_traits::node_ptr node_ptr; + typedef ebo_functor_holder<F> base_t; + typedef typename get_algo< AlgoType + , node_traits>::type node_algorithms; + static const bool safemode_or_autounlink = + is_safe_autounlink<value_traits::link_mode>::value; + + node_disposer(F f, const ValueTraits *cont) + : base_t(f), traits_(cont) + {} + + void operator()(const node_ptr & p) + { + if(safemode_or_autounlink) + node_algorithms::init(p); + base_t::get()(traits_->to_value_ptr(p)); + } + const ValueTraits * const traits_; +}; + +} //namespace detail{ +} //namespace intrusive{ +} //namespace boost{ + +#endif //BOOST_INTRUSIVE_DETAIL_NODE_CLONER_DISPOSER_HPP diff --git a/boost/intrusive/detail/node_holder.hpp b/boost/intrusive/detail/node_holder.hpp new file mode 100644 index 0000000000..12732a87a7 --- /dev/null +++ b/boost/intrusive/detail/node_holder.hpp @@ -0,0 +1,31 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_NODE_HOLDER_HPP +#define BOOST_INTRUSIVE_DETAIL_NODE_HOLDER_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +namespace boost { +namespace intrusive { + +template<class Node, class Tag, unsigned int> +struct node_holder + : public Node +{}; + +} //namespace intrusive{ +} //namespace boost{ + +#endif //BOOST_INTRUSIVE_DETAIL_NODE_HOLDER_HPP diff --git a/boost/intrusive/detail/node_to_value.hpp b/boost/intrusive/detail/node_to_value.hpp new file mode 100644 index 0000000000..6ec3971239 --- /dev/null +++ b/boost/intrusive/detail/node_to_value.hpp @@ -0,0 +1,126 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_NODE_TO_VALUE_HPP +#define BOOST_INTRUSIVE_DETAIL_NODE_TO_VALUE_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/detail/is_stateful_value_traits.hpp> + +namespace boost { +namespace intrusive { +namespace detail { + +template<class VoidPointer> +struct dummy_constptr +{ + typedef typename boost::intrusive::pointer_traits<VoidPointer>:: + template rebind_pointer<const void>::type ConstVoidPtr; + + explicit dummy_constptr(ConstVoidPtr) + {} + + dummy_constptr() + {} + + ConstVoidPtr get_ptr() const + { return ConstVoidPtr(); } +}; + +template<class VoidPointer> +struct constptr +{ + typedef typename boost::intrusive::pointer_traits<VoidPointer>:: + template rebind_pointer<const void>::type ConstVoidPtr; + + constptr() + {} + + explicit constptr(const ConstVoidPtr &ptr) + : const_void_ptr_(ptr) + {} + + const void *get_ptr() const + { return boost::intrusive::detail::to_raw_pointer(const_void_ptr_); } + + ConstVoidPtr const_void_ptr_; +}; + +template <class VoidPointer, bool store_ptr> +struct select_constptr +{ + typedef typename if_c + < store_ptr + , constptr<VoidPointer> + , dummy_constptr<VoidPointer> + >::type type; +}; + + +template<class ValueTraits, bool IsConst> +struct node_to_value + : public select_constptr + < typename pointer_traits + <typename ValueTraits::pointer>::template rebind_pointer<void>::type + , is_stateful_value_traits<ValueTraits>::value + >::type +{ + static const bool stateful_value_traits = is_stateful_value_traits<ValueTraits>::value; + typedef typename select_constptr + < typename pointer_traits + <typename ValueTraits::pointer>:: + template rebind_pointer<void>::type + , stateful_value_traits >::type Base; + + typedef ValueTraits value_traits; + typedef typename value_traits::value_type value_type; + typedef typename value_traits::node_traits::node node; + typedef typename add_const_if_c + <value_type, IsConst>::type vtype; + typedef typename add_const_if_c + <node, IsConst>::type ntype; + typedef typename pointer_traits + <typename ValueTraits::pointer>:: + template rebind_pointer<ntype>::type npointer; + typedef typename pointer_traits<npointer>:: + template rebind_pointer<const ValueTraits>::type const_value_traits_ptr; + + node_to_value(const const_value_traits_ptr &ptr) + : Base(ptr) + {} + + typedef vtype & result_type; + typedef ntype & first_argument_type; + + const_value_traits_ptr get_value_traits() const + { return pointer_traits<const_value_traits_ptr>::static_cast_from(Base::get_ptr()); } + + result_type to_value(first_argument_type arg, false_) const + { return *(value_traits::to_value_ptr(pointer_traits<npointer>::pointer_to(arg))); } + + result_type to_value(first_argument_type arg, true_) const + { return *(this->get_value_traits()->to_value_ptr(pointer_traits<npointer>::pointer_to(arg))); } + + result_type operator()(first_argument_type arg) const + { return this->to_value(arg, bool_<stateful_value_traits>()); } +}; + +} //namespace detail{ +} //namespace intrusive{ +} //namespace boost{ + +#endif //BOOST_INTRUSIVE_DETAIL_NODE_TO_VALUE_HPP diff --git a/boost/intrusive/detail/parent_from_member.hpp b/boost/intrusive/detail/parent_from_member.hpp index 2afffb47bc..3dfe8d6461 100644 --- a/boost/intrusive/detail/parent_from_member.hpp +++ b/boost/intrusive/detail/parent_from_member.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007-2012 +// (C) Copyright Ion Gaztanaga 2007-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -12,13 +12,16 @@ #ifndef BOOST_INTRUSIVE_DETAIL_PARENT_FROM_MEMBER_HPP #define BOOST_INTRUSIVE_DETAIL_PARENT_FROM_MEMBER_HPP +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/detail/config_begin.hpp> #include <cstddef> #if defined(BOOST_MSVC) || ((defined(_WIN32) || defined(__WIN32__) || defined(WIN32)) && defined(BOOST_INTEL)) - -#define BOOST_INTRUSIVE_MSVC_COMPLIANT_PTR_TO_MEMBER -#include <boost/cstdint.hpp> + #define BOOST_INTRUSIVE_MSVC_ABI_PTR_TO_MEMBER + #include <boost/static_assert.hpp> #endif namespace boost { @@ -29,15 +32,39 @@ template<class Parent, class Member> inline std::ptrdiff_t offset_from_pointer_to_member(const Member Parent::* ptr_to_member) { //The implementation of a pointer to member is compiler dependent. - #if defined(BOOST_INTRUSIVE_MSVC_COMPLIANT_PTR_TO_MEMBER) - //msvc compliant compilers use their the first 32 bits as offset (even in 64 bit mode) + #if defined(BOOST_INTRUSIVE_MSVC_ABI_PTR_TO_MEMBER) + + //MSVC compliant compilers use their the first 32 bits as offset (even in 64 bit mode) union caster_union { const Member Parent::* ptr_to_member; - boost::int32_t offset; + int offset; } caster; + + //MSVC ABI can use up to 3 int32 to represent pointer to member data + //with virtual base classes, in those cases there is no simple to + //obtain the address of the parent. So static assert to avoid runtime errors + BOOST_STATIC_ASSERT( sizeof(caster) == sizeof(int) ); + 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 + //types dereference seems to be: + // + // vboffset = [compile_time_offset if 2-int ptr2memb] / + // [ptr2memb.i32[2] if 3-int ptr2memb]. + // vbtable = *(this + vboffset); + // adj = vbtable[ptr2memb.i32[1]]; + // var = adj + (this + vboffset) + ptr2memb.i32[0]; + // + //To reverse the operation we need to + // - obtain vboffset (in 2-int ptr2memb implementation only) + // - Go to Parent's vbtable and obtain adjustment at index ptr2memb.i32[1] + // - parent = member - adj - vboffset - ptr2memb.i32[0] + // + //Even accessing to RTTI we might not be able to obtain this information + //so anyone who thinks it's possible, please send a patch. + //This works with gcc, msvc, ac++, ibmcpp #elif defined(__GNUC__) || defined(__HP_aCC) || defined(BOOST_INTEL) || \ defined(__IBMCPP__) || defined(__DECCXX) @@ -84,8 +111,8 @@ inline const Parent *parent_from_member(const Member *member, const Member Paren } //namespace intrusive { } //namespace boost { -#ifdef BOOST_INTRUSIVE_MSVC_COMPLIANT_PTR_TO_MEMBER -#undef BOOST_INTRUSIVE_MSVC_COMPLIANT_PTR_TO_MEMBER +#ifdef BOOST_INTRUSIVE_MSVC_ABI_PTR_TO_MEMBER +#undef BOOST_INTRUSIVE_MSVC_ABI_PTR_TO_MEMBER #endif #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/pointer_element.hpp b/boost/intrusive/detail/pointer_element.hpp new file mode 100644 index 0000000000..1c17f419ec --- /dev/null +++ b/boost/intrusive/detail/pointer_element.hpp @@ -0,0 +1,170 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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_POINTER_ELEMENT_HPP +#define BOOST_INTRUSIVE_DETAIL_POINTER_ELEMENT_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/detail/workaround.hpp> + +namespace boost { +namespace intrusive { +namespace detail{ + +////////////////////// +//struct first_param +////////////////////// + +template <typename T> struct first_param +{ typedef void type; }; + +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + template <template <typename, typename...> class TemplateClass, typename T, typename... Args> + struct first_param< TemplateClass<T, Args...> > + { + typedef T type; + }; + +#else //C++03 compilers + + template < template //0arg + <class + > class TemplateClass, class T + > + struct first_param + < TemplateClass<T> > + { typedef T type; }; + + template < template //1arg + <class,class + > class TemplateClass, class T + , class P0> + struct first_param + < TemplateClass<T, P0> > + { typedef T type; }; + + template < template //2arg + <class,class,class + > class TemplateClass, class T + , class P0, class P1> + struct first_param + < TemplateClass<T, P0, P1> > + { typedef T type; }; + + template < template //3arg + <class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2> + struct first_param + < TemplateClass<T, P0, P1, P2> > + { typedef T type; }; + + template < template //4arg + <class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3> + struct first_param + < TemplateClass<T, P0, P1, P2, P3> > + { typedef T type; }; + + template < template //5arg + <class,class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3, class P4> + struct first_param + < TemplateClass<T, P0, P1, P2, P3, P4> > + { typedef T type; }; + + template < template //6arg + <class,class,class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3, class P4, class P5> + struct first_param + < TemplateClass<T, P0, P1, P2, P3, P4, P5> > + { typedef T type; }; + + template < template //7arg + <class,class,class,class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3, class P4, class P5, class P6> + struct first_param + < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6> > + { typedef T type; }; + + template < template //8arg + <class,class,class,class,class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7> + struct first_param + < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6, P7> > + { typedef T type; }; + + template < template //9arg + <class,class,class,class,class,class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7, class P8> + struct first_param + < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6, P7, P8> > + { typedef T type; }; + + template < template //10arg + <class,class,class,class,class,class,class,class,class,class,class + > class TemplateClass, class T + , class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7, class P8, class P9> + struct first_param + < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6, P7, P8, P9> > + { typedef T type; }; + +#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + +template <typename T> +struct has_internal_pointer_element +{ + template <typename X> + static char test(int, typename X::element_type*); + + template <typename X> + static int test(...); + + static const bool value = (1 == sizeof(test<T>(0, 0))); +}; + +template<class Ptr, bool = has_internal_pointer_element<Ptr>::value> +struct pointer_element_impl +{ + typedef typename Ptr::element_type type; +}; + +template<class Ptr> +struct pointer_element_impl<Ptr, false> +{ + typedef typename boost::intrusive::detail::first_param<Ptr>::type type; +}; + +} //namespace detail{ + +template <typename Ptr> +struct pointer_element +{ + typedef typename ::boost::intrusive::detail::pointer_element_impl<Ptr>::type type; +}; + +template <typename T> +struct pointer_element<T*> +{ typedef T type; }; + +} //namespace container { +} //namespace boost { + +#endif // defined(BOOST_INTRUSIVE_DETAIL_POINTER_ELEMENT_HPP) diff --git a/boost/intrusive/detail/preprocessor.hpp b/boost/intrusive/detail/preprocessor.hpp index 348b104bb0..cdbc8a1d39 100644 --- a/boost/intrusive/detail/preprocessor.hpp +++ b/boost/intrusive/detail/preprocessor.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2008-2012. Distributed under the Boost +// (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) // @@ -11,29 +11,19 @@ #ifndef BOOST_INTRUSIVE_DETAIL_PREPROCESSOR_HPP #define BOOST_INTRUSIVE_DETAIL_PREPROCESSOR_HPP -#if (defined _MSC_VER) && (_MSC_VER >= 1200) +#if defined(_MSC_VER) # pragma once #endif #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/detail/workaround.hpp> -#include <boost/preprocessor/iteration/local.hpp> -#include <boost/preprocessor/punctuation/paren_if.hpp> -#include <boost/preprocessor/punctuation/comma_if.hpp> -#include <boost/preprocessor/control/expr_if.hpp> #include <boost/preprocessor/cat.hpp> #include <boost/preprocessor/repetition/enum.hpp> -#include <boost/preprocessor/repetition/enum_params.hpp> #include <boost/preprocessor/repetition/enum_trailing_params.hpp> #include <boost/preprocessor/repetition/enum_trailing.hpp> -#include <boost/preprocessor/repetition/enum_shifted_params.hpp> -#include <boost/preprocessor/repetition/enum_shifted.hpp> -#include <boost/preprocessor/repetition/repeat.hpp> -#include <boost/preprocessor/logical/not.hpp> #include <boost/preprocessor/arithmetic/sub.hpp> -#include <boost/preprocessor/arithmetic/add.hpp> -#include <boost/preprocessor/iteration/iterate.hpp> + #define BOOST_INTRUSIVE_MAX_CONSTRUCTOR_PARAMETERS 10 diff --git a/boost/intrusive/detail/rbtree_node.hpp b/boost/intrusive/detail/rbtree_node.hpp index b76582bb61..ab50509c25 100644 --- a/boost/intrusive/detail/rbtree_node.hpp +++ b/boost/intrusive/detail/rbtree_node.hpp @@ -1,7 +1,7 @@ ///////////////////////////////////////////////////////////////////////////// // // (C) Copyright Olaf Krzikalla 2004-2006. -// (C) Copyright Ion Gaztanaga 2006-2012. +// (C) Copyright Ion Gaztanaga 2006-2013. // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -14,12 +14,16 @@ #ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP #define BOOST_INTRUSIVE_RBTREE_NODE_HPP +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/detail/config_begin.hpp> -#include <iterator> -#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/pointer_rebind.hpp> #include <boost/intrusive/rbtree_algorithms.hpp> #include <boost/intrusive/pointer_plus_bits.hpp> #include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/detail/tree_node.hpp> namespace boost { namespace intrusive { @@ -34,9 +38,9 @@ namespace intrusive { template<class VoidPointer> struct compact_rbtree_node { - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer - <compact_rbtree_node<VoidPointer> >::type node_ptr; + typedef compact_rbtree_node<VoidPointer> node; + typedef typename pointer_rebind<VoidPointer, node >::type node_ptr; + typedef typename pointer_rebind<VoidPointer, const node >::type const_node_ptr; enum color { red_t, black_t }; node_ptr parent_, left_, right_; }; @@ -45,9 +49,9 @@ struct compact_rbtree_node template<class VoidPointer> struct rbtree_node { - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer - <rbtree_node<VoidPointer> >::type node_ptr; + typedef rbtree_node<VoidPointer> node; + typedef typename pointer_rebind<VoidPointer, node >::type node_ptr; + typedef typename pointer_rebind<VoidPointer, const node >::type const_node_ptr; enum color { red_t, black_t }; node_ptr parent_, left_, right_; @@ -60,27 +64,33 @@ template<class VoidPointer> struct default_rbtree_node_traits_impl { typedef rbtree_node<VoidPointer> node; - - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; + typedef typename node::node_ptr node_ptr; + typedef typename node::const_node_ptr const_node_ptr; typedef typename node::color color; - static const node_ptr & get_parent(const const_node_ptr & n) + static node_ptr get_parent(const const_node_ptr & n) + { return n->parent_; } + + static node_ptr get_parent(const node_ptr & n) { return n->parent_; } static void set_parent(const node_ptr & n, const node_ptr & p) { n->parent_ = p; } - static const node_ptr & get_left(const const_node_ptr & n) + static node_ptr get_left(const const_node_ptr & n) + { return n->left_; } + + static node_ptr get_left(const node_ptr & n) { return n->left_; } static void set_left(const node_ptr & n, const node_ptr & l) { n->left_ = l; } - static const node_ptr & get_right(const const_node_ptr & n) + static node_ptr get_right(const const_node_ptr & n) + { return n->right_; } + + static node_ptr get_right(const node_ptr & n) { return n->right_; } static void set_right(const node_ptr & n, const node_ptr & r) @@ -89,6 +99,9 @@ struct default_rbtree_node_traits_impl static color get_color(const const_node_ptr & n) { return n->color_; } + static color get_color(const node_ptr & n) + { return n->color_; } + static void set_color(const node_ptr & n, color c) { n->color_ = c; } @@ -105,10 +118,8 @@ template<class VoidPointer> struct compact_rbtree_node_traits_impl { typedef compact_rbtree_node<VoidPointer> node; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; + typedef typename node::node_ptr node_ptr; + typedef typename node::const_node_ptr const_node_ptr; typedef pointer_plus_bits<node_ptr, 1> ptr_bit; @@ -117,16 +128,25 @@ struct compact_rbtree_node_traits_impl static node_ptr get_parent(const const_node_ptr & n) { return ptr_bit::get_pointer(n->parent_); } + static node_ptr get_parent(const node_ptr & n) + { return ptr_bit::get_pointer(n->parent_); } + static void set_parent(const node_ptr & n, const node_ptr & p) { ptr_bit::set_pointer(n->parent_, p); } - static const node_ptr & get_left(const const_node_ptr & n) + static node_ptr get_left(const const_node_ptr & n) + { return n->left_; } + + static node_ptr get_left(const node_ptr & n) { return n->left_; } static void set_left(const node_ptr & n, const node_ptr & l) { n->left_ = l; } - static const node_ptr & get_right(const const_node_ptr & n) + static node_ptr get_right(const const_node_ptr & n) + { return n->right_; } + + static node_ptr get_right(const node_ptr & n) { return n->right_; } static void set_right(const node_ptr & n, const node_ptr & r) @@ -135,6 +155,9 @@ struct compact_rbtree_node_traits_impl static color get_color(const const_node_ptr & n) { return (color)ptr_bit::get_bits(n->parent_); } + static color get_color(const node_ptr & n) + { return (color)ptr_bit::get_bits(n->parent_); } + static void set_color(const node_ptr & n, color c) { ptr_bit::set_bits(n->parent_, c != 0); } @@ -156,7 +179,7 @@ struct rbtree_node_traits_dispatch<VoidPointer, true> : public compact_rbtree_node_traits_impl<VoidPointer> {}; -//Inherit from the detail::link_dispatch depending on the embedding capabilities +//Inherit from rbtree_node_traits_dispatch depending on the embedding capabilities template<class VoidPointer, bool OptimizeSize = false> struct rbtree_node_traits : public rbtree_node_traits_dispatch diff --git a/boost/intrusive/detail/reverse_iterator.hpp b/boost/intrusive/detail/reverse_iterator.hpp new file mode 100644 index 0000000000..9f443ab4b2 --- /dev/null +++ b/boost/intrusive/detail/reverse_iterator.hpp @@ -0,0 +1,139 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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 + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/detail/iiterator.hpp> + +namespace boost { +namespace intrusive { +namespace detail { + +template<class It> +class reverse_iterator +{ + public: + typedef typename boost::intrusive::iterator_traits<It>::pointer pointer; + typedef typename boost::intrusive::iterator_traits<It>::reference reference; + typedef typename boost::intrusive::iterator_traits<It>::difference_type difference_type; + typedef typename boost::intrusive::iterator_traits<It>::iterator_category iterator_category; + typedef typename boost::intrusive::iterator_traits<It>::value_type value_type; + + + typedef It iterator_type; + + reverse_iterator() + : m_current() //Value initialization to achieve "null iterators" (N3644) + {} + + explicit reverse_iterator(It r) + : m_current(r) + {} + + template<class OtherIt> + reverse_iterator(const reverse_iterator<OtherIt>& r) + : m_current(r.base()) + {} + + It base() const + { return m_current; } + + reference operator*() const + { It temp(m_current); --temp; return *temp; } + + pointer operator->() const + { It temp(m_current); --temp; return temp.operator->(); } + + reference operator[](difference_type off) const + { return this->m_current[-off]; } + + reverse_iterator& operator++() + { --m_current; return *this; } + + reverse_iterator operator++(int) + { + reverse_iterator temp = *this; + --m_current; + return temp; + } + + reverse_iterator& operator--() + { + ++m_current; + return *this; + } + + reverse_iterator operator--(int) + { + reverse_iterator temp(*this); + ++m_current; + return temp; + } + + friend bool operator==(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current == r.m_current; } + + friend bool operator!=(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current != r.m_current; } + + friend bool operator<(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current > r.m_current; } + + friend bool operator<=(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current >= r.m_current; } + + friend bool operator>(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current < r.m_current; } + + friend bool operator>=(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current <= r.m_current; } + + reverse_iterator& operator+=(difference_type off) + { m_current -= off; return *this; } + + friend reverse_iterator operator+(const reverse_iterator & l, difference_type off) + { + reverse_iterator tmp(l.m_current); + tmp.m_current -= off; + return tmp; + } + + reverse_iterator& operator-=(difference_type off) + { m_current += off; return *this; } + + friend reverse_iterator operator-(const reverse_iterator & l, difference_type off) + { + reverse_iterator tmp(l.m_current); + tmp.m_current += off; + return tmp; + } + + friend difference_type operator-(const reverse_iterator& l, const reverse_iterator& r) + { return r.m_current - l.m_current; } + + private: + It m_current; // the wrapped iterator +}; + +} //namespace detail +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_DETAIL_ITERATOR_HPP diff --git a/boost/intrusive/detail/simple_disposers.hpp b/boost/intrusive/detail/simple_disposers.hpp new file mode 100644 index 0000000000..af597722fa --- /dev/null +++ b/boost/intrusive/detail/simple_disposers.hpp @@ -0,0 +1,46 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_SIMPLE_DISPOSERS_HPP +#define BOOST_INTRUSIVE_DETAIL_SIMPLE_DISPOSERS_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +namespace boost { +namespace intrusive { +namespace detail { + +class null_disposer +{ + public: + template <class Pointer> + void operator()(Pointer) + {} +}; + +template<class NodeAlgorithms> +class init_disposer +{ + typedef typename NodeAlgorithms::node_ptr node_ptr; + + public: + void operator()(const node_ptr & p) + { NodeAlgorithms::init(p); } +}; + +} //namespace detail{ +} //namespace intrusive{ +} //namespace boost{ + +#endif //BOOST_INTRUSIVE_DETAIL_SIMPLE_DISPOSERS_HPP diff --git a/boost/intrusive/detail/size_holder.hpp b/boost/intrusive/detail/size_holder.hpp new file mode 100644 index 0000000000..a733187733 --- /dev/null +++ b/boost/intrusive/detail/size_holder.hpp @@ -0,0 +1,80 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_SIZE_HOLDER_HPP +#define BOOST_INTRUSIVE_DETAIL_SIZE_HOLDER_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +namespace boost { +namespace intrusive { +namespace detail { + +template<bool ConstantSize, class SizeType, class Tag = void> +struct size_holder +{ + static const bool constant_time_size = ConstantSize; + typedef SizeType size_type; + + SizeType get_size() const + { return size_; } + + void set_size(SizeType size) + { size_ = size; } + + void decrement() + { --size_; } + + void increment() + { ++size_; } + + void increase(SizeType n) + { size_ += n; } + + void decrease(SizeType n) + { size_ -= n; } + + SizeType size_; +}; + +template<class SizeType, class Tag> +struct size_holder<false, SizeType, Tag> +{ + static const bool constant_time_size = false; + typedef SizeType size_type; + + size_type get_size() const + { return 0; } + + void set_size(size_type) + {} + + void decrement() + {} + + void increment() + {} + + void increase(SizeType) + {} + + void decrease(SizeType) + {} +}; + +} //namespace detail{ +} //namespace intrusive{ +} //namespace boost{ + +#endif //BOOST_INTRUSIVE_DETAIL_SIZE_HOLDER_HPP diff --git a/boost/intrusive/detail/slist_iterator.hpp b/boost/intrusive/detail/slist_iterator.hpp new file mode 100644 index 0000000000..579c660f57 --- /dev/null +++ b/boost/intrusive/detail/slist_iterator.hpp @@ -0,0 +1,120 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Olaf Krzikalla 2004-2006. +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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_SLIST_ITERATOR_HPP +#define BOOST_INTRUSIVE_SLIST_ITERATOR_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/detail/std_fwd.hpp> +#include <boost/intrusive/detail/iiterator.hpp> +#include <boost/intrusive/detail/mpl.hpp> + +namespace boost { +namespace intrusive { + + +// slist_iterator provides some basic functions for a +// node oriented bidirectional iterator: +template<class ValueTraits, bool IsConst> +class slist_iterator +{ + protected: + typedef iiterator + <ValueTraits, IsConst, std::forward_iterator_tag> types_t; + + static const bool stateful_value_traits = types_t::stateful_value_traits; + + typedef ValueTraits value_traits; + typedef typename types_t::node_traits node_traits; + + 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; + + public: + typedef typename types_t::iterator_traits::difference_type difference_type; + typedef typename types_t::iterator_traits::value_type value_type; + typedef typename types_t::iterator_traits::pointer pointer; + typedef typename types_t::iterator_traits::reference reference; + typedef typename types_t::iterator_traits::iterator_category iterator_category; + + slist_iterator() + {} + + explicit slist_iterator(const node_ptr & nodeptr, const const_value_traits_ptr &traits_ptr) + : members_(nodeptr, traits_ptr) + {} + + slist_iterator(slist_iterator<ValueTraits, false> const& other) + : members_(other.pointed_node(), other.get_value_traits()) + {} + + const node_ptr &pointed_node() const + { return members_.nodeptr_; } + + slist_iterator &operator=(const node_ptr &node) + { members_.nodeptr_ = node; return static_cast<slist_iterator&>(*this); } + + const_value_traits_ptr get_value_traits() const + { return members_.get_ptr(); } + + public: + slist_iterator& operator++() + { + members_.nodeptr_ = node_traits::get_next(members_.nodeptr_); + return static_cast<slist_iterator&> (*this); + } + + slist_iterator operator++(int) + { + slist_iterator result (*this); + members_.nodeptr_ = node_traits::get_next(members_.nodeptr_); + return result; + } + + friend bool operator== (const slist_iterator& l, const slist_iterator& r) + { return l.pointed_node() == r.pointed_node(); } + + friend bool operator!= (const slist_iterator& l, const slist_iterator& r) + { return !(l == r); } + + reference operator*() const + { return *operator->(); } + + pointer operator->() const + { return this->operator_arrow(detail::bool_<stateful_value_traits>()); } + + slist_iterator<ValueTraits, false> unconst() const + { return slist_iterator<ValueTraits, false>(this->pointed_node(), this->get_value_traits()); } + + private: + + pointer operator_arrow(detail::false_) const + { return ValueTraits::to_value_ptr(members_.nodeptr_); } + + pointer operator_arrow(detail::true_) const + { return this->get_value_traits()->to_value_ptr(members_.nodeptr_); } + + iiterator_members<node_ptr, const_value_traits_ptr, stateful_value_traits> members_; +}; + +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_SLIST_ITERATOR_HPP diff --git a/boost/intrusive/detail/slist_node.hpp b/boost/intrusive/detail/slist_node.hpp index 0eddbcd69a..437190e6c0 100644 --- a/boost/intrusive/detail/slist_node.hpp +++ b/boost/intrusive/detail/slist_node.hpp @@ -1,7 +1,7 @@ ///////////////////////////////////////////////////////////////////////////// // // (C) Copyright Olaf Krzikalla 2004-2006. -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -14,10 +14,12 @@ #ifndef BOOST_INTRUSIVE_SLIST_NODE_HPP #define BOOST_INTRUSIVE_SLIST_NODE_HPP +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/detail/config_begin.hpp> -#include <iterator> -#include <boost/intrusive/detail/assert.hpp> -#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/pointer_rebind.hpp> namespace boost { namespace intrusive { @@ -25,8 +27,7 @@ namespace intrusive { template<class VoidPointer> struct slist_node { - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<slist_node>::type node_ptr; + typedef typename pointer_rebind<VoidPointer, slist_node>::type node_ptr; node_ptr next_; }; @@ -36,125 +37,20 @@ struct slist_node template<class VoidPointer> struct slist_node_traits { - typedef slist_node<VoidPointer> node; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; + typedef slist_node<VoidPointer> node; + typedef typename node::node_ptr node_ptr; + typedef typename pointer_rebind<VoidPointer, const node>::type const_node_ptr; + + static node_ptr get_next(const const_node_ptr & n) + { return n->next_; } - static const node_ptr &get_next(const const_node_ptr & n) + static node_ptr get_next(const node_ptr & n) { return n->next_; } static void set_next(const node_ptr & n, const node_ptr & next) { n->next_ = next; } }; -// slist_iterator provides some basic functions for a -// node oriented bidirectional iterator: -template<class Container, bool IsConst> -class slist_iterator - : public std::iterator - < std::forward_iterator_tag - , typename Container::value_type - , typename Container::difference_type - , typename detail::if_c<IsConst,typename Container::const_pointer,typename Container::pointer>::type - , typename detail::if_c<IsConst,typename Container::const_reference,typename Container::reference>::type - > -{ - protected: - typedef typename Container::real_value_traits real_value_traits; - typedef typename real_value_traits::node_traits node_traits; - typedef typename node_traits::node node; - typedef typename node_traits::node_ptr node_ptr; - typedef typename pointer_traits - <node_ptr>::template rebind_pointer <void>::type void_pointer; - static const bool store_container_ptr = - detail::store_cont_ptr_on_it<Container>::value; - - public: - typedef typename Container::value_type value_type; - typedef typename detail::if_c<IsConst,typename Container::const_pointer,typename Container::pointer>::type pointer; - typedef typename detail::if_c<IsConst,typename Container::const_reference,typename Container::reference>::type reference; - - slist_iterator() - : members_ (node_ptr(), 0) - {} - - explicit slist_iterator(const node_ptr & node, const Container *cont_ptr) - : members_ (node, cont_ptr) - {} - - slist_iterator(slist_iterator<Container, false> const& other) - : members_(other.pointed_node(), other.get_container()) - {} - - const node_ptr &pointed_node() const - { return members_.nodeptr_; } - - slist_iterator &operator=(const node_ptr &node) - { members_.nodeptr_ = node; return static_cast<slist_iterator&>(*this); } - - public: - slist_iterator& operator++() - { - members_.nodeptr_ = node_traits::get_next(members_.nodeptr_); - return static_cast<slist_iterator&> (*this); - } - - slist_iterator operator++(int) - { - slist_iterator result (*this); - members_.nodeptr_ = node_traits::get_next(members_.nodeptr_); - return result; - } - - friend bool operator== (const slist_iterator& l, const slist_iterator& r) - { return l.pointed_node() == r.pointed_node(); } - - friend bool operator!= (const slist_iterator& l, const slist_iterator& r) - { return !(l == r); } - - reference operator*() const - { return *operator->(); } - - pointer operator->() const - { return this->get_real_value_traits()->to_value_ptr(members_.nodeptr_); } - - const Container *get_container() const - { - if(store_container_ptr) - return static_cast<const Container*>(members_.get_ptr()); - else - return 0; - } - - slist_iterator<Container, false> unconst() const - { return slist_iterator<Container, false>(this->pointed_node(), this->get_container()); } - - const real_value_traits *get_real_value_traits() const - { - if(store_container_ptr) - return &this->get_container()->get_real_value_traits(); - else - return 0; - } - - private: - struct members - : public detail::select_constptr - <void_pointer, store_container_ptr>::type - { - typedef typename detail::select_constptr - <void_pointer, store_container_ptr>::type Base; - - members(const node_ptr &n_ptr, const void *cont) - : Base(cont), nodeptr_(n_ptr) - {} - - node_ptr nodeptr_; - } members_; -}; - } //namespace intrusive } //namespace boost diff --git a/boost/intrusive/detail/std_fwd.hpp b/boost/intrusive/detail/std_fwd.hpp new file mode 100644 index 0000000000..b657c4acfe --- /dev/null +++ b/boost/intrusive/detail/std_fwd.hpp @@ -0,0 +1,54 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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/container for documentation. +// +////////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_INTRUSIVE_DETAIL_STD_FWD_HPP +#define BOOST_INTRUSIVE_DETAIL_STD_FWD_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +////////////////////////////////////////////////////////////////////////////// +// Standard predeclarations +////////////////////////////////////////////////////////////////////////////// + +#if defined(__clang__) && defined(_LIBCPP_VERSION) + #define BOOST_INTRUSIVE_CLANG_INLINE_STD_NS + #pragma GCC diagnostic push + #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 +#else + #define BOOST_INTRUSIVE_STD_NS_BEG namespace std{ + #define BOOST_INTRUSIVE_STD_NS_END } +#endif + +BOOST_INTRUSIVE_STD_NS_BEG + +template<class T> +struct less; + +template<class T> +struct equal_to; + +struct input_iterator_tag; +struct forward_iterator_tag; +struct bidirectional_iterator_tag; +struct random_access_iterator_tag; + +BOOST_INTRUSIVE_STD_NS_END + +#ifdef BOOST_INTRUSIVE_CLANG_INLINE_STD_NS + #pragma GCC diagnostic pop + #undef BOOST_INTRUSIVE_CLANG_INLINE_STD_NS +#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 new file mode 100644 index 0000000000..e7ebff9e5d --- /dev/null +++ b/boost/intrusive/detail/to_raw_pointer.hpp @@ -0,0 +1,42 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_TO_RAW_POINTER_HPP +#define BOOST_INTRUSIVE_DETAIL_TO_RAW_POINTER_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/detail/pointer_element.hpp> + +namespace boost { +namespace intrusive { +namespace detail { + +template <class T> +inline T* to_raw_pointer(T* p) +{ return p; } + +template <class Pointer> +inline typename boost::intrusive::pointer_element<Pointer>::type* +to_raw_pointer(const Pointer &p) +{ return boost::intrusive::detail::to_raw_pointer(p.operator->()); } + +} //namespace detail +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP diff --git a/boost/intrusive/detail/transform_iterator.hpp b/boost/intrusive/detail/transform_iterator.hpp index 488db9ade8..698318be9b 100644 --- a/boost/intrusive/detail/transform_iterator.hpp +++ b/boost/intrusive/detail/transform_iterator.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007-2012 +// (C) Copyright Ion Gaztanaga 2007-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -13,8 +13,11 @@ #ifndef BOOST_INTRUSIVE_DETAIL_TRANSFORM_ITERATOR_HPP #define BOOST_INTRUSIVE_DETAIL_TRANSFORM_ITERATOR_HPP +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/detail/config_begin.hpp> -#include <iterator> #include <boost/intrusive/detail/mpl.hpp> namespace boost { @@ -51,7 +54,7 @@ struct operator_arrow_proxy<T&> template <class Iterator, class UnaryFunction> class transform_iterator - : public std::iterator + : public boost::intrusive::iterator < typename Iterator::iterator_category , typename detail::remove_reference<typename UnaryFunction::result_type>::type , typename Iterator::difference_type @@ -158,10 +161,10 @@ class transform_iterator { return members_(*members_.m_it); } void advance(typename Iterator::difference_type n) - { std::advance(members_.m_it, n); } + { boost::intrusive::iterator_advance(members_.m_it, n); } typename Iterator::difference_type distance_to(const transform_iterator &other)const - { return std::distance(other.members_.m_it, members_.m_it); } + { return boost::intrusive::iterator_distance(other.members_.m_it, members_.m_it); } }; } //namespace detail diff --git a/boost/intrusive/detail/tree_algorithms.hpp b/boost/intrusive/detail/tree_algorithms.hpp deleted file mode 100644 index c92d39b3b9..0000000000 --- a/boost/intrusive/detail/tree_algorithms.hpp +++ /dev/null @@ -1,1747 +0,0 @@ -///////////////////////////////////////////////////////////////////////////// -// -// (C) Copyright Ion Gaztanaga 2007-2012 -// -// 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_TREE_ALGORITHMS_HPP -#define BOOST_INTRUSIVE_TREE_ALGORITHMS_HPP - -#include <boost/intrusive/detail/config_begin.hpp> -#include <boost/intrusive/detail/assert.hpp> -#include <boost/intrusive/intrusive_fwd.hpp> -#include <cstddef> -#include <boost/intrusive/detail/utilities.hpp> -#include <boost/intrusive/pointer_traits.hpp> - -namespace boost { -namespace intrusive { -namespace detail { - -//! This is an implementation of a binary search tree. -//! A node in the search tree has references to its children and its parent. This -//! is to allow traversal of the whole tree from a given node making the -//! implementation of iterator a pointer to a node. -//! At the top of the tree a node is used specially. This node's parent pointer -//! is pointing to the root of the tree. Its left pointer points to the -//! leftmost node in the tree and the right pointer to the rightmost one. -//! This node is used to represent the end-iterator. -//! -//! +---------+ -//! header------------------------------>| | -//! | | -//! +----------(left)--------| |--------(right)---------+ -//! | +---------+ | -//! | | | -//! | | (parent) | -//! | | | -//! | | | -//! | +---------+ | -//! root of tree ..|......................> | | | -//! | | D | | -//! | | | | -//! | +-------+---------+-------+ | -//! | | | | -//! | | | | -//! | | | | -//! | | | | -//! | | | | -//! | +---------+ +---------+ | -//! | | | | | | -//! | | B | | F | | -//! | | | | | | -//! | +--+---------+--+ +--+---------+--+ | -//! | | | | | | -//! | | | | | | -//! | | | | | | -//! | +---+-----+ +-----+---+ +---+-----+ +-----+---+ | -//! +-->| | | | | | | |<--+ -//! | A | | C | | E | | G | -//! | | | | | | | | -//! +---------+ +---------+ +---------+ +---------+ -//! - -//! tree_algorithms is configured with a NodeTraits class, which encapsulates the -//! information about the node to be manipulated. NodeTraits must support the -//! following interface: -//! -//! <b>Typedefs</b>: -//! -//! <tt>node</tt>: The type of the node that forms the circular list -//! -//! <tt>node_ptr</tt>: A pointer to a node -//! -//! <tt>const_node_ptr</tt>: A pointer to a const node -//! -//! <b>Static functions</b>: -//! -//! <tt>static node_ptr get_parent(const_node_ptr n);</tt> -//! -//! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt> -//! -//! <tt>static node_ptr get_left(const_node_ptr n);</tt> -//! -//! <tt>static void set_left(node_ptr n, node_ptr left);</tt> -//! -//! <tt>static node_ptr get_right(const_node_ptr n);</tt> -//! -//! <tt>static void set_right(node_ptr n, node_ptr right);</tt> -template<class NodeTraits> -class tree_algorithms -{ - 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; - - //! This type is the information that will be filled by insert_unique_check - struct insert_commit_data - { - insert_commit_data() - : link_left(false) - , node() - {} - bool link_left; - node_ptr node; - }; - - struct nop_erase_fixup - { - void operator()(const node_ptr&, const node_ptr&){} - }; - - /// @cond - private: - template<class Disposer> - struct dispose_subtree_disposer - { - dispose_subtree_disposer(Disposer &disp, const node_ptr & subtree) - : disposer_(&disp), subtree_(subtree) - {} - - void release() - { disposer_ = 0; } - - ~dispose_subtree_disposer() - { - if(disposer_){ - dispose_subtree(subtree_, *disposer_); - } - } - Disposer *disposer_; - node_ptr subtree_; - }; - - static node_ptr uncast(const const_node_ptr & ptr) - { return pointer_traits<node_ptr>::const_cast_from(ptr); } - - /// @endcond - - public: - static node_ptr begin_node(const const_node_ptr & header) - { return node_traits::get_left(header); } - - static node_ptr end_node(const const_node_ptr & header) - { return uncast(header); } - - //! <b>Requires</b>: 'node' is a node of the tree or an node initialized - //! by init(...) or init_node. - //! - //! <b>Effects</b>: Returns true if the node is initialized by init() or init_node(). - //! - //! <b>Complexity</b>: Constant time. - //! - //! <b>Throws</b>: Nothing. - static bool unique(const const_node_ptr & node) - { return !NodeTraits::get_parent(node); } - - static node_ptr get_header(const const_node_ptr & node) - { - node_ptr h = uncast(node); - if(NodeTraits::get_parent(node)){ - h = NodeTraits::get_parent(node); - while(!is_header(h)) - h = NodeTraits::get_parent(h); - } - return h; - } - - //! <b>Requires</b>: node1 and node2 can't be header nodes - //! of two trees. - //! - //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted - //! in the position node2 before the function. node2 will be inserted in the - //! position node1 had before the function. - //! - //! <b>Complexity</b>: Logarithmic. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Note</b>: This function will break container ordering invariants if - //! node1 and node2 are not equivalent according to the ordering rules. - //! - //!Experimental function - static void swap_nodes(const node_ptr & node1, const node_ptr & node2) - { - if(node1 == node2) - return; - - node_ptr header1(get_header(node1)), header2(get_header(node2)); - swap_nodes(node1, header1, node2, header2); - } - - //! <b>Requires</b>: node1 and node2 can't be header nodes - //! of two trees with header header1 and header2. - //! - //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted - //! in the position node2 before the function. node2 will be inserted in the - //! position node1 had before the function. - //! - //! <b>Complexity</b>: Constant. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Note</b>: This function will break container ordering invariants if - //! node1 and node2 are not equivalent according to the ordering rules. - //! - //!Experimental function - static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2) - { - if(node1 == node2) - return; - - //node1 and node2 must not be header nodes - //BOOST_INTRUSIVE_INVARIANT_ASSERT((header1 != node1 && header2 != node2)); - if(header1 != header2){ - //Update header1 if necessary - if(node1 == NodeTraits::get_left(header1)){ - NodeTraits::set_left(header1, node2); - } - - if(node1 == NodeTraits::get_right(header1)){ - NodeTraits::set_right(header1, node2); - } - - if(node1 == NodeTraits::get_parent(header1)){ - NodeTraits::set_parent(header1, node2); - } - - //Update header2 if necessary - if(node2 == NodeTraits::get_left(header2)){ - NodeTraits::set_left(header2, node1); - } - - if(node2 == NodeTraits::get_right(header2)){ - NodeTraits::set_right(header2, node1); - } - - if(node2 == NodeTraits::get_parent(header2)){ - NodeTraits::set_parent(header2, node1); - } - } - else{ - //If both nodes are from the same tree - //Update header if necessary - if(node1 == NodeTraits::get_left(header1)){ - NodeTraits::set_left(header1, node2); - } - else if(node2 == NodeTraits::get_left(header2)){ - NodeTraits::set_left(header2, node1); - } - - if(node1 == NodeTraits::get_right(header1)){ - NodeTraits::set_right(header1, node2); - } - else if(node2 == NodeTraits::get_right(header2)){ - NodeTraits::set_right(header2, node1); - } - - if(node1 == NodeTraits::get_parent(header1)){ - NodeTraits::set_parent(header1, node2); - } - else if(node2 == NodeTraits::get_parent(header2)){ - NodeTraits::set_parent(header2, node1); - } - - //Adjust data in nodes to be swapped - //so that final link swap works as expected - if(node1 == NodeTraits::get_parent(node2)){ - NodeTraits::set_parent(node2, node2); - - if(node2 == NodeTraits::get_right(node1)){ - NodeTraits::set_right(node1, node1); - } - else{ - NodeTraits::set_left(node1, node1); - } - } - else if(node2 == NodeTraits::get_parent(node1)){ - NodeTraits::set_parent(node1, node1); - - if(node1 == NodeTraits::get_right(node2)){ - NodeTraits::set_right(node2, node2); - } - else{ - NodeTraits::set_left(node2, node2); - } - } - } - - //Now swap all the links - node_ptr temp; - //swap left link - temp = NodeTraits::get_left(node1); - NodeTraits::set_left(node1, NodeTraits::get_left(node2)); - NodeTraits::set_left(node2, temp); - //swap right link - temp = NodeTraits::get_right(node1); - NodeTraits::set_right(node1, NodeTraits::get_right(node2)); - NodeTraits::set_right(node2, temp); - //swap parent link - temp = NodeTraits::get_parent(node1); - NodeTraits::set_parent(node1, NodeTraits::get_parent(node2)); - NodeTraits::set_parent(node2, temp); - - //Now adjust adjacent nodes for newly inserted node 1 - if((temp = NodeTraits::get_left(node1))){ - NodeTraits::set_parent(temp, node1); - } - if((temp = NodeTraits::get_right(node1))){ - NodeTraits::set_parent(temp, node1); - } - if((temp = NodeTraits::get_parent(node1)) && - //The header has been already updated so avoid it - temp != header2){ - if(NodeTraits::get_left(temp) == node2){ - NodeTraits::set_left(temp, node1); - } - if(NodeTraits::get_right(temp) == node2){ - NodeTraits::set_right(temp, node1); - } - } - //Now adjust adjacent nodes for newly inserted node 2 - if((temp = NodeTraits::get_left(node2))){ - NodeTraits::set_parent(temp, node2); - } - if((temp = NodeTraits::get_right(node2))){ - NodeTraits::set_parent(temp, node2); - } - if((temp = NodeTraits::get_parent(node2)) && - //The header has been already updated so avoid it - temp != header1){ - if(NodeTraits::get_left(temp) == node1){ - NodeTraits::set_left(temp, node2); - } - if(NodeTraits::get_right(temp) == node1){ - NodeTraits::set_right(temp, node2); - } - } - } - - //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree - //! and new_node must not be inserted in a tree. - //! - //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the - //! tree with new_node. The tree does not need to be rebalanced - //! - //! <b>Complexity</b>: Logarithmic. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Note</b>: This function will break container ordering invariants if - //! new_node is not equivalent to node_to_be_replaced according to the - //! ordering rules. This function is faster than erasing and inserting - //! the node, since no rebalancing and comparison is needed. - //! - //!Experimental function - static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node) - { - if(node_to_be_replaced == new_node) - return; - replace_node(node_to_be_replaced, get_header(node_to_be_replaced), new_node); - } - - //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree - //! with header "header" and new_node must not be inserted in a tree. - //! - //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the - //! tree with new_node. The tree does not need to be rebalanced - //! - //! <b>Complexity</b>: Constant. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Note</b>: This function will break container ordering invariants if - //! new_node is not equivalent to node_to_be_replaced according to the - //! ordering rules. This function is faster than erasing and inserting - //! the node, since no rebalancing or comparison is needed. - //! - //!Experimental function - static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node) - { - if(node_to_be_replaced == new_node) - return; - - //Update header if necessary - if(node_to_be_replaced == NodeTraits::get_left(header)){ - NodeTraits::set_left(header, new_node); - } - - if(node_to_be_replaced == NodeTraits::get_right(header)){ - NodeTraits::set_right(header, new_node); - } - - if(node_to_be_replaced == NodeTraits::get_parent(header)){ - NodeTraits::set_parent(header, new_node); - } - - //Now set data from the original node - node_ptr temp; - NodeTraits::set_left(new_node, NodeTraits::get_left(node_to_be_replaced)); - NodeTraits::set_right(new_node, NodeTraits::get_right(node_to_be_replaced)); - NodeTraits::set_parent(new_node, NodeTraits::get_parent(node_to_be_replaced)); - - //Now adjust adjacent nodes for newly inserted node - if((temp = NodeTraits::get_left(new_node))){ - NodeTraits::set_parent(temp, new_node); - } - if((temp = NodeTraits::get_right(new_node))){ - NodeTraits::set_parent(temp, new_node); - } - if((temp = NodeTraits::get_parent(new_node)) && - //The header has been already updated so avoid it - temp != header){ - if(NodeTraits::get_left(temp) == node_to_be_replaced){ - NodeTraits::set_left(temp, new_node); - } - if(NodeTraits::get_right(temp) == node_to_be_replaced){ - NodeTraits::set_right(temp, new_node); - } - } - } - - //! <b>Requires</b>: 'node' is a node from the tree except the header. - //! - //! <b>Effects</b>: Returns the next node of the tree. - //! - //! <b>Complexity</b>: Average constant time. - //! - //! <b>Throws</b>: Nothing. - static node_ptr next_node(const node_ptr & node) - { - node_ptr p_right(NodeTraits::get_right(node)); - if(p_right){ - return minimum(p_right); - } - else { - node_ptr p(node); - node_ptr x = NodeTraits::get_parent(p); - while(p == NodeTraits::get_right(x)){ - p = x; - x = NodeTraits::get_parent(x); - } - return NodeTraits::get_right(p) != x ? x : uncast(p); - } - } - - //! <b>Requires</b>: 'node' is a node from the tree except the leftmost node. - //! - //! <b>Effects</b>: Returns the previous node of the tree. - //! - //! <b>Complexity</b>: Average constant time. - //! - //! <b>Throws</b>: Nothing. - static node_ptr prev_node(const node_ptr & node) - { - if(is_header(node)){ - return NodeTraits::get_right(node); - //return maximum(NodeTraits::get_parent(node)); - } - else if(NodeTraits::get_left(node)){ - return maximum(NodeTraits::get_left(node)); - } - else { - node_ptr p(node); - node_ptr x = NodeTraits::get_parent(p); - while(p == NodeTraits::get_left(x)){ - p = x; - x = NodeTraits::get_parent(x); - } - return x; - } - } - - //! <b>Requires</b>: 'node' is a node of a tree but not the header. - //! - //! <b>Effects</b>: Returns the minimum node of the subtree starting at p. - //! - //! <b>Complexity</b>: Logarithmic to the size of the subtree. - //! - //! <b>Throws</b>: Nothing. - static node_ptr minimum (const node_ptr & node) - { - node_ptr p(node); - for(node_ptr p_left = NodeTraits::get_left(p) - ;p_left - ;p_left = NodeTraits::get_left(p)){ - p = p_left; - } - return p; - } - - //! <b>Requires</b>: 'node' is a node of a tree but not the header. - //! - //! <b>Effects</b>: Returns the maximum node of the subtree starting at p. - //! - //! <b>Complexity</b>: Logarithmic to the size of the subtree. - //! - //! <b>Throws</b>: Nothing. - static node_ptr maximum(const node_ptr & node) - { - node_ptr p(node); - for(node_ptr p_right = NodeTraits::get_right(p) - ;p_right - ;p_right = NodeTraits::get_right(p)){ - p = p_right; - } - return p; - } - - //! <b>Requires</b>: 'node' must not be part of any tree. - //! - //! <b>Effects</b>: After the function unique(node) == true. - //! - //! <b>Complexity</b>: Constant. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree. - static void init(const node_ptr & node) - { - NodeTraits::set_parent(node, node_ptr()); - NodeTraits::set_left(node, node_ptr()); - NodeTraits::set_right(node, node_ptr()); - }; - - //! <b>Effects</b>: Returns true if node is in the same state as if called init(node) - //! - //! <b>Complexity</b>: Constant. - //! - //! <b>Throws</b>: Nothing. - static bool inited(const const_node_ptr & node) - { - return !NodeTraits::get_parent(node) && - !NodeTraits::get_left(node) && - !NodeTraits::get_right(node) ; - }; - - //! <b>Requires</b>: node must not be part of any tree. - //! - //! <b>Effects</b>: Initializes the header to represent an empty tree. - //! unique(header) == true. - //! - //! <b>Complexity</b>: Constant. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree. - static void init_header(const node_ptr & header) - { - NodeTraits::set_parent(header, node_ptr()); - NodeTraits::set_left(header, header); - NodeTraits::set_right(header, header); - } - - //! <b>Requires</b>: "disposer" must be an object function - //! taking a node_ptr parameter and shouldn't throw. - //! - //! <b>Effects</b>: Empties the target tree calling - //! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree - //! except the header. - //! - //! <b>Complexity</b>: Linear to the number of element of the source tree plus the. - //! number of elements of tree target tree when calling this function. - //! - //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed. - template<class Disposer> - static void clear_and_dispose(const node_ptr & header, Disposer disposer) - { - node_ptr source_root = NodeTraits::get_parent(header); - if(!source_root) - return; - dispose_subtree(source_root, disposer); - init_header(header); - } - - //! <b>Requires</b>: header is the header of a tree. - //! - //! <b>Effects</b>: Unlinks the leftmost node from the tree, and - //! updates the header link to the new leftmost node. - //! - //! <b>Complexity</b>: Average complexity is constant time. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Notes</b>: This function breaks the tree and the tree can - //! only be used for more unlink_leftmost_without_rebalance calls. - //! This function is normally used to achieve a step by step - //! controlled destruction of the tree. - static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header) - { - node_ptr leftmost = NodeTraits::get_left(header); - if (leftmost == header) - return node_ptr(); - node_ptr leftmost_parent(NodeTraits::get_parent(leftmost)); - node_ptr leftmost_right (NodeTraits::get_right(leftmost)); - bool is_root = leftmost_parent == header; - - if (leftmost_right){ - NodeTraits::set_parent(leftmost_right, leftmost_parent); - NodeTraits::set_left(header, tree_algorithms::minimum(leftmost_right)); - - if (is_root) - NodeTraits::set_parent(header, leftmost_right); - else - NodeTraits::set_left(NodeTraits::get_parent(header), leftmost_right); - } - else if (is_root){ - NodeTraits::set_parent(header, node_ptr()); - NodeTraits::set_left(header, header); - NodeTraits::set_right(header, header); - } - else{ - NodeTraits::set_left(leftmost_parent, node_ptr()); - NodeTraits::set_left(header, leftmost_parent); - } - return leftmost; - } - - //! <b>Requires</b>: node is a node of the tree but it's not the header. - //! - //! <b>Effects</b>: Returns the number of nodes of the subtree. - //! - //! <b>Complexity</b>: Linear time. - //! - //! <b>Throws</b>: Nothing. - static std::size_t count(const const_node_ptr & subtree) - { - if(!subtree) return 0; - std::size_t count = 0; - node_ptr p = minimum(uncast(subtree)); - bool continue_looping = true; - while(continue_looping){ - ++count; - node_ptr p_right(NodeTraits::get_right(p)); - if(p_right){ - p = minimum(p_right); - } - else { - for(;;){ - node_ptr q; - if (p == subtree){ - continue_looping = false; - break; - } - q = p; - p = NodeTraits::get_parent(p); - if (NodeTraits::get_left(p) == q) - break; - } - } - } - return count; - } - - //! <b>Requires</b>: node is a node of the tree but it's not the header. - //! - //! <b>Effects</b>: Returns the number of nodes of the subtree. - //! - //! <b>Complexity</b>: Linear time. - //! - //! <b>Throws</b>: Nothing. - static std::size_t size(const const_node_ptr & header) - { - 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; - return i; - } - - //! <b>Requires</b>: header1 and header2 must be the header nodes - //! of two trees. - //! - //! <b>Effects</b>: Swaps two trees. After the function header1 will contain - //! links to the second tree and header2 will have links to the first tree. - //! - //! <b>Complexity</b>: Constant. - //! - //! <b>Throws</b>: Nothing. - static void swap_tree(const node_ptr & header1, const node_ptr & header2) - { - if(header1 == header2) - return; - - node_ptr tmp; - - //Parent swap - tmp = NodeTraits::get_parent(header1); - NodeTraits::set_parent(header1, NodeTraits::get_parent(header2)); - NodeTraits::set_parent(header2, tmp); - //Left swap - tmp = NodeTraits::get_left(header1); - NodeTraits::set_left(header1, NodeTraits::get_left(header2)); - NodeTraits::set_left(header2, tmp); - //Right swap - tmp = NodeTraits::get_right(header1); - NodeTraits::set_right(header1, NodeTraits::get_right(header2)); - NodeTraits::set_right(header2, tmp); - - //Now test parent - node_ptr h1_parent(NodeTraits::get_parent(header1)); - if(h1_parent){ - NodeTraits::set_parent(h1_parent, header1); - } - else{ - NodeTraits::set_left(header1, header1); - NodeTraits::set_right(header1, header1); - } - - node_ptr h2_parent(NodeTraits::get_parent(header2)); - if(h2_parent){ - NodeTraits::set_parent(h2_parent, header2); - } - else{ - NodeTraits::set_left(header2, header2); - NodeTraits::set_right(header2, header2); - } - } - - static bool is_header(const const_node_ptr & p) - { - node_ptr p_left (NodeTraits::get_left(p)); - node_ptr p_right(NodeTraits::get_right(p)); - if(!NodeTraits::get_parent(p) || //Header condition when empty tree - (p_left && p_right && //Header always has leftmost and rightmost - (p_left == p_right || //Header condition when only node - (NodeTraits::get_parent(p_left) != p || - NodeTraits::get_parent(p_right) != p )) - //When tree size > 1 headers can't be leftmost's - //and rightmost's parent - )){ - return true; - } - return false; - } - - //! <b>Requires</b>: "header" must be the header node of a tree. - //! KeyNodePtrCompare is a function object that induces a strict weak - //! ordering compatible with the strict weak ordering used to create the - //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. - //! - //! <b>Effects</b>: Returns an node_ptr to the element that is equivalent to - //! "key" according to "comp" or "header" if that element does not exist. - //! - //! <b>Complexity</b>: Logarithmic. - //! - //! <b>Throws</b>: If "comp" throws. - template<class KeyType, class KeyNodePtrCompare> - static node_ptr find - (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) - { - node_ptr end = uncast(header); - node_ptr y = lower_bound(header, key, comp); - return (y == end || comp(key, y)) ? end : y; - } - - //! <b>Requires</b>: "header" must be the header node of a tree. - //! KeyNodePtrCompare is a function object that induces a strict weak - //! 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. - //! - //! <b>Effects</b>: Returns an a pair with the following criteria: - //! - //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise - //! - //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise - //! - //! <b>Complexity</b>: Logarithmic. - //! - //! <b>Throws</b>: If "comp" throws. - //! - //! <b>Note</b>: This function can be more efficient than calling upper_bound - //! and lower_bound for lower_key and upper_key. - template< class KeyType, class KeyNodePtrCompare> - static std::pair<node_ptr, node_ptr> bounded_range - ( const const_node_ptr & header - , const KeyType &lower_key - , const KeyType &upper_key - , KeyNodePtrCompare comp - , bool left_closed - , bool right_closed) - { - node_ptr y = uncast(header); - node_ptr x = NodeTraits::get_parent(header); - - while(x){ - //If x is less than lower_key the target - //range is on the right part - if(comp(x, lower_key)){ - //Check for invalid input range - BOOST_INTRUSIVE_INVARIANT_ASSERT(comp(x, upper_key)); - x = NodeTraits::get_right(x); - } - //If the upper_key is less than x, the target - //range is on the left part - else if(comp(upper_key, x)){ - //y > upper_key - y = x; - x = NodeTraits::get_left(x); - } - else{ - //x is inside the bounded range( x >= 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 - BOOST_INTRUSIVE_INVARIANT_ASSERT(left_closed || right_closed || comp(lower_key, x) || comp(x, upper_key)); - return std::pair<node_ptr,node_ptr>( - left_closed - //If left_closed, then comp(x, lower_key) is already the lower_bound - //condition so we save one comparison and go to the next level - //following traditional lower_bound algo - ? lower_bound_loop(NodeTraits::get_left(x), x, lower_key, comp) - //If left-open, comp(x, lower_key) is not the upper_bound algo - //condition so we must recheck current 'x' node with upper_bound algo - : upper_bound_loop(x, y, lower_key, comp) - , - right_closed - //If right_closed, then comp(upper_key, x) is already the upper_bound - //condition so we can save one comparison and go to the next level - //following lower_bound algo - ? upper_bound_loop(NodeTraits::get_right(x), y, upper_key, comp) - //If right-open, comp(upper_key, x) is not the lower_bound algo - //condition so we must recheck current 'x' node with lower_bound algo - : lower_bound_loop(x, y, upper_key, comp) - ); - } - } - return std::pair<node_ptr,node_ptr> (y, y); - } - - //! <b>Requires</b>: "header" must be the header node of a tree. - //! KeyNodePtrCompare is a function object that induces a strict weak - //! ordering compatible with the strict weak ordering used to create the - //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. - //! - //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing - //! all elements that are equivalent to "key" according to "comp" or an - //! empty range that indicates the position where those elements would be - //! if there are no equivalent elements. - //! - //! <b>Complexity</b>: Logarithmic. - //! - //! <b>Throws</b>: If "comp" throws. - template<class KeyType, class KeyNodePtrCompare> - static std::pair<node_ptr, node_ptr> equal_range - (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) - { - return bounded_range(header, key, key, comp, true, true); - } - - //! <b>Requires</b>: "header" must be the header node of a tree. - //! KeyNodePtrCompare is a function object that induces a strict weak - //! ordering compatible with the strict weak ordering used to create the - //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. - //! - //! <b>Effects</b>: Returns an node_ptr to the first element that is - //! not less than "key" according to "comp" or "header" if that element does - //! not exist. - //! - //! <b>Complexity</b>: Logarithmic. - //! - //! <b>Throws</b>: If "comp" throws. - template<class KeyType, class KeyNodePtrCompare> - static node_ptr lower_bound - (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) - { - return lower_bound_loop(NodeTraits::get_parent(header), uncast(header), key, comp); - } - - //! <b>Requires</b>: "header" must be the header node of a tree. - //! KeyNodePtrCompare is a function object that induces a strict weak - //! ordering compatible with the strict weak ordering used to create the - //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. - //! - //! <b>Effects</b>: Returns an node_ptr to the first element that is greater - //! than "key" according to "comp" or "header" if that element does not exist. - //! - //! <b>Complexity</b>: Logarithmic. - //! - //! <b>Throws</b>: If "comp" throws. - template<class KeyType, class KeyNodePtrCompare> - static node_ptr upper_bound - (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) - { - return upper_bound_loop(NodeTraits::get_parent(header), uncast(header), key, comp); - } - - //! <b>Requires</b>: "header" must be the header node of a tree. - //! "commit_data" must have been obtained from a previous call to - //! "insert_unique_check". No objects should have been inserted or erased - //! from the set between the "insert_unique_check" that filled "commit_data" - //! and the call to "insert_commit". - //! - //! - //! <b>Effects</b>: Inserts new_node in the set using the information obtained - //! from the "commit_data" that a previous "insert_check" filled. - //! - //! <b>Complexity</b>: Constant time. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been - //! previously executed to fill "commit_data". No value should be inserted or - //! erased between the "insert_check" and "insert_commit" calls. - static void insert_unique_commit - (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data) - { return insert_commit(header, new_value, commit_data); } - - static void insert_commit - (const node_ptr & header, const node_ptr & new_node, const insert_commit_data &commit_data) - { - //Check if commit_data has not been initialized by a insert_unique_check call. - BOOST_INTRUSIVE_INVARIANT_ASSERT(commit_data.node != node_ptr()); - node_ptr parent_node(commit_data.node); - if(parent_node == header){ - NodeTraits::set_parent(header, new_node); - NodeTraits::set_right(header, new_node); - NodeTraits::set_left(header, new_node); - } - else if(commit_data.link_left){ - NodeTraits::set_left(parent_node, new_node); - if(parent_node == NodeTraits::get_left(header)) - NodeTraits::set_left(header, new_node); - } - else{ - NodeTraits::set_right(parent_node, new_node); - if(parent_node == NodeTraits::get_right(header)) - NodeTraits::set_right(header, new_node); - } - NodeTraits::set_parent(new_node, parent_node); - NodeTraits::set_right(new_node, node_ptr()); - NodeTraits::set_left(new_node, node_ptr()); - } - - //! <b>Requires</b>: "header" must be the header node of a tree. - //! KeyNodePtrCompare is a function object that induces a strict weak - //! ordering compatible with the strict weak ordering used to create the - //! the tree. NodePtrCompare compares KeyType with a node_ptr. - //! - //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the - //! tree according to "comp" and obtains the needed information to realize - //! a constant-time node insertion if there is no equivalent node. - //! - //! <b>Returns</b>: If there is an equivalent value - //! returns a pair containing a node_ptr to the already present node - //! and false. If there is not equivalent key can be inserted returns true - //! in the returned pair's boolean and fills "commit_data" that is meant to - //! be used with the "insert_commit" function to achieve a constant-time - //! insertion function. - //! - //! <b>Complexity</b>: Average complexity is at most logarithmic. - //! - //! <b>Throws</b>: If "comp" throws. - //! - //! <b>Notes</b>: This function is used to improve performance when constructing - //! a node is expensive and the user does not want to have two equivalent nodes - //! in the tree: if there is an equivalent value - //! the constructed object must be discarded. Many times, the part of the - //! node that is used to impose the order is much cheaper to construct - //! than the node and this function offers the possibility to use that part - //! to check if the insertion will be successful. - //! - //! If the check is successful, the user can construct the node and use - //! "insert_commit" to insert the node in constant-time. This gives a total - //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)). - //! - //! "commit_data" remains valid for a subsequent "insert_unique_commit" only - //! if no more objects are inserted or erased from the set. - template<class KeyType, class KeyNodePtrCompare> - static std::pair<node_ptr, bool> insert_unique_check - (const const_node_ptr & header, const KeyType &key - ,KeyNodePtrCompare comp, insert_commit_data &commit_data, std::size_t *pdepth = 0) - { - std::size_t depth = 0; - node_ptr h(uncast(header)); - node_ptr y(h); - node_ptr x(NodeTraits::get_parent(y)); - node_ptr prev = node_ptr(); - - //Find the upper bound, cache the previous value and if we should - //store it in the left or right node - bool left_child = true; - while(x){ - ++depth; - y = x; - x = (left_child = comp(key, x)) ? - NodeTraits::get_left(x) : (prev = y, NodeTraits::get_right(x)); - } - - if(pdepth) *pdepth = depth; - - //Since we've found the upper bound there is no other value with the same key if: - // - There is no previous node - // - The previous node is less than the key - if(!prev || comp(prev, key)){ - commit_data.link_left = left_child; - commit_data.node = y; - return std::pair<node_ptr, bool>(node_ptr(), true); - } - //If the previous value was not less than key, it means that it's equal - //(because we've checked the upper bound) - else{ - return std::pair<node_ptr, bool>(prev, false); - } - } - - template<class KeyType, class KeyNodePtrCompare> - static std::pair<node_ptr, bool> insert_unique_check - (const const_node_ptr & header, const node_ptr &hint, const KeyType &key - ,KeyNodePtrCompare comp, insert_commit_data &commit_data, std::size_t *pdepth = 0) - { - //hint must be bigger than the key - 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)){ - commit_data.link_left = unique(header) || !NodeTraits::get_left(hint); - commit_data.node = commit_data.link_left ? hint : prev; - if(pdepth){ - *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1; - } - return std::pair<node_ptr, bool>(node_ptr(), true); - } - } - //Hint was wrong, use hintless insertion - return insert_unique_check(header, key, comp, commit_data, pdepth); - } - - template<class NodePtrCompare> - static void insert_equal_check - (const node_ptr &header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp - , insert_commit_data &commit_data, std::size_t *pdepth = 0) - { - if(hint == header || !comp(hint, new_node)){ - node_ptr prev(hint); - if(hint == NodeTraits::get_left(header) || - !comp(new_node, (prev = 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; - if(pdepth){ - *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1; - } - } - else{ - insert_equal_upper_bound_check(header, new_node, comp, commit_data, pdepth); - } - } - else{ - insert_equal_lower_bound_check(header, new_node, comp, commit_data, pdepth); - } - } - - template<class NodePtrCompare> - static void insert_equal_upper_bound_check - (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0) - { insert_equal_check_impl(true, h, new_node, comp, commit_data, pdepth); } - - template<class NodePtrCompare> - static void insert_equal_lower_bound_check - (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0) - { insert_equal_check_impl(false, h, new_node, comp, commit_data, pdepth); } - - template<class NodePtrCompare> - static node_ptr insert_equal - (const node_ptr & h, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp, std::size_t *pdepth = 0) - { - insert_commit_data commit_data; - insert_equal_check(h, hint, new_node, comp, commit_data, pdepth); - insert_commit(h, new_node, commit_data); - return new_node; - } - - template<class NodePtrCompare> - static node_ptr insert_equal_upper_bound - (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, std::size_t *pdepth = 0) - { - insert_commit_data commit_data; - insert_equal_upper_bound_check(h, new_node, comp, commit_data, pdepth); - insert_commit(h, new_node, commit_data); - return new_node; - } - - template<class NodePtrCompare> - static node_ptr insert_equal_lower_bound - (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, std::size_t *pdepth = 0) - { - insert_commit_data commit_data; - insert_equal_lower_bound_check(h, new_node, comp, commit_data, pdepth); - insert_commit(h, new_node, commit_data); - return new_node; - } - - static node_ptr insert_before - (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node, std::size_t *pdepth = 0) - { - insert_commit_data commit_data; - insert_before_check(header, pos, commit_data, pdepth); - insert_commit(header, new_node, commit_data); - return new_node; - } - - static void insert_before_check - (const node_ptr &header, const node_ptr & pos - , insert_commit_data &commit_data, std::size_t *pdepth = 0) - { - node_ptr prev(pos); - if(pos != NodeTraits::get_left(header)) - prev = 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; - if(pdepth){ - *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1; - } - } - - static void push_back - (const node_ptr & header, const node_ptr & new_node, std::size_t *pdepth = 0) - { - insert_commit_data commit_data; - push_back_check(header, commit_data, pdepth); - insert_commit(header, new_node, commit_data); - } - - static void push_back_check - (const node_ptr & header, insert_commit_data &commit_data, std::size_t *pdepth = 0) - { - node_ptr prev(NodeTraits::get_right(header)); - if(pdepth){ - *pdepth = prev == header ? 0 : depth(prev) + 1; - } - commit_data.link_left = false; - commit_data.node = prev; - } - - static void push_front - (const node_ptr & header, const node_ptr & new_node, std::size_t *pdepth = 0) - { - insert_commit_data commit_data; - push_front_check(header, commit_data, pdepth); - insert_commit(header, new_node, commit_data); - } - - static void push_front_check - (const node_ptr & header, insert_commit_data &commit_data, std::size_t *pdepth = 0) - { - node_ptr pos(NodeTraits::get_left(header)); - if(pdepth){ - *pdepth = pos == header ? 0 : depth(pos) + 1; - } - commit_data.link_left = true; - commit_data.node = pos; - } - - //! <b>Requires</b>: 'node' can't be a header node. - //! - //! <b>Effects</b>: Calculates the depth of a node: the depth of a - //! node is the length (number of edges) of the path from the root - //! to that node. (The root node is at depth 0.) - //! - //! <b>Complexity</b>: Logarithmic to the number of nodes in the tree. - //! - //! <b>Throws</b>: Nothing. - static std::size_t depth(const const_node_ptr & node) - { - const_node_ptr p(node); - std::size_t depth = 0; - node_ptr p_parent; - while(p != NodeTraits::get_parent(p_parent = NodeTraits::get_parent(p))){ - ++depth; - p = p_parent; - } - return depth; - } - - //! <b>Requires</b>: "cloner" must be a function - //! object taking a node_ptr and returning a new cloned node of it. "disposer" must - //! take a node_ptr and shouldn't throw. - //! - //! <b>Effects</b>: First empties target tree calling - //! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree - //! except the header. - //! - //! Then, duplicates the entire tree pointed by "source_header" cloning each - //! source node with <tt>node_ptr Cloner::operator()(const node_ptr &)</tt> to obtain - //! the nodes of the target tree. If "cloner" throws, the cloned target nodes - //! are disposed using <tt>void disposer(const node_ptr &)</tt>. - //! - //! <b>Complexity</b>: Linear to the number of element of the source tree plus the. - //! number of elements of tree target tree when calling this function. - //! - //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed. - template <class Cloner, class Disposer> - static void clone - (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer) - { - if(!unique(target_header)){ - clear_and_dispose(target_header, disposer); - } - - node_ptr leftmost, rightmost; - node_ptr new_root = clone_subtree - (source_header, target_header, cloner, disposer, leftmost, rightmost); - - //Now update header node - NodeTraits::set_parent(target_header, new_root); - NodeTraits::set_left (target_header, leftmost); - NodeTraits::set_right (target_header, rightmost); - } - - template <class Cloner, class Disposer> - static node_ptr clone_subtree - (const const_node_ptr &source_parent, const node_ptr &target_parent - , Cloner cloner, Disposer disposer - , node_ptr &leftmost_out, node_ptr &rightmost_out - ) - { - node_ptr target_sub_root = target_parent; - node_ptr source_root = NodeTraits::get_parent(source_parent); - if(!source_root){ - leftmost_out = rightmost_out = source_root; - } - else{ - //We'll calculate leftmost and rightmost nodes while iterating - node_ptr current = source_root; - node_ptr insertion_point = target_sub_root = cloner(current); - - //We'll calculate leftmost and rightmost nodes while iterating - node_ptr leftmost = target_sub_root; - node_ptr rightmost = target_sub_root; - - //First set the subroot - NodeTraits::set_left(target_sub_root, node_ptr()); - NodeTraits::set_right(target_sub_root, node_ptr()); - NodeTraits::set_parent(target_sub_root, target_parent); - - dispose_subtree_disposer<Disposer> rollback(disposer, target_sub_root); - while(true) { - //First clone left nodes - if( NodeTraits::get_left(current) && - !NodeTraits::get_left(insertion_point)) { - current = NodeTraits::get_left(current); - node_ptr temp = insertion_point; - //Clone and mark as leaf - insertion_point = cloner(current); - NodeTraits::set_left (insertion_point, node_ptr()); - NodeTraits::set_right (insertion_point, node_ptr()); - //Insert left - NodeTraits::set_parent(insertion_point, temp); - NodeTraits::set_left (temp, insertion_point); - //Update leftmost - if(rightmost == target_sub_root) - leftmost = insertion_point; - } - //Then clone right nodes - else if( NodeTraits::get_right(current) && - !NodeTraits::get_right(insertion_point)){ - current = NodeTraits::get_right(current); - node_ptr temp = insertion_point; - //Clone and mark as leaf - insertion_point = cloner(current); - NodeTraits::set_left (insertion_point, node_ptr()); - NodeTraits::set_right (insertion_point, node_ptr()); - //Insert right - NodeTraits::set_parent(insertion_point, temp); - NodeTraits::set_right (temp, insertion_point); - //Update rightmost - rightmost = insertion_point; - } - //If not, go up - else if(current == source_root){ - break; - } - else{ - //Branch completed, go up searching more nodes to clone - current = NodeTraits::get_parent(current); - insertion_point = NodeTraits::get_parent(insertion_point); - } - } - rollback.release(); - leftmost_out = leftmost; - rightmost_out = rightmost; - } - return target_sub_root; - } - - template<class Disposer> - static void dispose_subtree(const node_ptr & node, Disposer disposer) - { - node_ptr save; - node_ptr x(node); - while (x){ - save = NodeTraits::get_left(x); - if (save) { - // Right rotation - NodeTraits::set_left(x, NodeTraits::get_right(save)); - NodeTraits::set_right(save, x); - } - else { - save = NodeTraits::get_right(x); - init(x); - disposer(x); - } - x = save; - } - } - - //! <b>Requires</b>: p is a node of a tree. - //! - //! <b>Effects</b>: Returns true if p is a left child. - //! - //! <b>Complexity</b>: Constant. - //! - //! <b>Throws</b>: Nothing. - static bool is_left_child(const node_ptr & p) - { return NodeTraits::get_left(NodeTraits::get_parent(p)) == p; } - - //! <b>Requires</b>: p is a node of a tree. - //! - //! <b>Effects</b>: Returns true if p is a right child. - //! - //! <b>Complexity</b>: Constant. - //! - //! <b>Throws</b>: Nothing. - static bool is_right_child(const node_ptr & p) - { return NodeTraits::get_right(NodeTraits::get_parent(p)) == p; } - - //Fix header and own's parent data when replacing x with own, providing own's old data with parent - static void replace_own_impl(const node_ptr & own, const node_ptr & x, const node_ptr & header, const node_ptr & own_parent, bool own_was_left) - { - if(NodeTraits::get_parent(header) == own) - NodeTraits::set_parent(header, x); - else if(own_was_left) - NodeTraits::set_left(own_parent, x); - else - NodeTraits::set_right(own_parent, x); - } - - //Fix header and own's parent data when replacing x with own, supposing own - //links with its parent are still ok - static void replace_own(const node_ptr & own, const node_ptr & x, const node_ptr & header) - { - node_ptr own_parent(NodeTraits::get_parent(own)); - bool own_is_left(NodeTraits::get_left(own_parent) == own); - replace_own_impl(own, x, header, own_parent, own_is_left); - } - - // rotate parent p to left (no header and p's parent fixup) - static node_ptr rotate_left(const node_ptr & p) - { - node_ptr x(NodeTraits::get_right(p)); - node_ptr x_left(NodeTraits::get_left(x)); - NodeTraits::set_right(p, x_left); - if(x_left){ - NodeTraits::set_parent(x_left, p); - } - NodeTraits::set_left(x, p); - NodeTraits::set_parent(p, x); - return x; - } - - // rotate parent p to left (with header and p's parent fixup) - static void rotate_left(const node_ptr & p, const node_ptr & header) - { - bool p_was_left(is_left_child(p)); - node_ptr p_old_parent(NodeTraits::get_parent(p)); - node_ptr x(rotate_left(p)); - NodeTraits::set_parent(x, p_old_parent); - replace_own_impl(p, x, header, p_old_parent, p_was_left); - } - - // rotate parent p to right (no header and p's parent fixup) - static node_ptr rotate_right(const node_ptr & p) - { - node_ptr x(NodeTraits::get_left(p)); - node_ptr x_right(NodeTraits::get_right(x)); - NodeTraits::set_left(p, x_right); - if(x_right){ - NodeTraits::set_parent(x_right, p); - } - NodeTraits::set_right(x, p); - NodeTraits::set_parent(p, x); - return x; - } - - // rotate parent p to right (with header and p's parent fixup) - static void rotate_right(const node_ptr & p, const node_ptr & header) - { - bool p_was_left(is_left_child(p)); - node_ptr p_old_parent(NodeTraits::get_parent(p)); - node_ptr x(rotate_right(p)); - NodeTraits::set_parent(x, p_old_parent); - replace_own_impl(p, x, header, p_old_parent, p_was_left); - } - - static void erase(const node_ptr & header, const node_ptr & z) - { - data_for_rebalance ignored; - erase_impl(header, z, ignored); - } - - struct data_for_rebalance - { - node_ptr x; - node_ptr x_parent; - node_ptr y; - }; - - template<class F> - static void erase(const node_ptr & header, const node_ptr & z, F z_and_successor_fixup, data_for_rebalance &info) - { - erase_impl(header, z, info); - if(info.y != z){ - z_and_successor_fixup(z, info.y); - } - } - - static void unlink(const node_ptr & node) - { - node_ptr x = NodeTraits::get_parent(node); - if(x){ - while(!is_header(x)) - x = NodeTraits::get_parent(x); - erase(x, node); - } - } - - static void tree_to_vine(const node_ptr & header) - { subtree_to_vine(NodeTraits::get_parent(header)); } - - static void vine_to_tree(const node_ptr & header, std::size_t count) - { vine_to_subtree(NodeTraits::get_parent(header), count); } - - static void rebalance(const node_ptr & header) - { - //Taken from: - //"Tree rebalancing in optimal time and space" - //Quentin F. Stout and Bette L. Warren - std::size_t len = 0; - subtree_to_vine(NodeTraits::get_parent(header), &len); - vine_to_subtree(NodeTraits::get_parent(header), len); - } - - static node_ptr rebalance_subtree(const node_ptr & old_root) - { - std::size_t len = 0; - node_ptr new_root = subtree_to_vine(old_root, &len); - return vine_to_subtree(new_root, len); - } - - static node_ptr subtree_to_vine(const node_ptr & old_root, std::size_t *plen = 0) - { - std::size_t len; - len = 0; - if(!old_root) return node_ptr(); - - //To avoid irregularities in the algorithm (old_root can be a - //left or right child or even the root of the tree) just put the - //root as the right child of its parent. Before doing this backup - //information to restore the original relationship after - //the algorithm is applied. - node_ptr super_root = NodeTraits::get_parent(old_root); - BOOST_INTRUSIVE_INVARIANT_ASSERT(super_root); - - //Get info - node_ptr super_root_right_backup = NodeTraits::get_right(super_root); - bool super_root_is_header = is_header(super_root); - bool old_root_is_right = is_right_child(old_root); - - node_ptr x(old_root); - node_ptr new_root(x); - node_ptr save; - bool moved_to_right = false; - for( ; x; x = save){ - save = NodeTraits::get_left(x); - if(save){ - // Right rotation - node_ptr save_right = NodeTraits::get_right(save); - node_ptr x_parent = NodeTraits::get_parent(x); - NodeTraits::set_parent(save, x_parent); - NodeTraits::set_right (x_parent, save); - NodeTraits::set_parent(x, save); - NodeTraits::set_right (save, x); - NodeTraits::set_left(x, save_right); - if(save_right) - NodeTraits::set_parent(save_right, x); - if(!moved_to_right) - new_root = save; - } - else{ - moved_to_right = true; - save = NodeTraits::get_right(x); - ++len; - } - } - - if(super_root_is_header){ - NodeTraits::set_right(super_root, super_root_right_backup); - NodeTraits::set_parent(super_root, new_root); - } - else if(old_root_is_right){ - NodeTraits::set_right(super_root, new_root); - } - else{ - NodeTraits::set_right(super_root, super_root_right_backup); - NodeTraits::set_left(super_root, new_root); - } - if(plen) *plen = len; - return new_root; - } - - static node_ptr vine_to_subtree(const node_ptr & old_root, std::size_t count) - { - std::size_t leaf_nodes = count + 1 - ((std::size_t) 1 << floor_log2 (count + 1)); - std::size_t vine_nodes = count - leaf_nodes; - - node_ptr new_root = compress_subtree(old_root, leaf_nodes); - while(vine_nodes > 1){ - vine_nodes /= 2; - new_root = compress_subtree(new_root, vine_nodes); - } - return new_root; - } - - static node_ptr compress_subtree(const node_ptr & old_root, std::size_t count) - { - if(!old_root) return old_root; - - //To avoid irregularities in the algorithm (old_root can be - //left or right child or even the root of the tree) just put the - //root as the right child of its parent. First obtain - //information to restore the original relationship after - //the algorithm is applied. - node_ptr super_root = NodeTraits::get_parent(old_root); - BOOST_INTRUSIVE_INVARIANT_ASSERT(super_root); - - //Get info - node_ptr super_root_right_backup = NodeTraits::get_right(super_root); - bool super_root_is_header = is_header(super_root); - bool old_root_is_right = is_right_child(old_root); - - //Put old_root as right child - NodeTraits::set_right(super_root, old_root); - - //Start the compression algorithm - node_ptr even_parent = super_root; - node_ptr new_root = old_root; - - while(count--){ - node_ptr even = NodeTraits::get_right(even_parent); - node_ptr odd = NodeTraits::get_right(even); - - if(new_root == old_root) - new_root = odd; - - node_ptr even_right = NodeTraits::get_left(odd); - NodeTraits::set_right(even, even_right); - if (even_right) - NodeTraits::set_parent(even_right, even); - - NodeTraits::set_right(even_parent, odd); - NodeTraits::set_parent(odd, even_parent); - NodeTraits::set_left(odd, even); - NodeTraits::set_parent(even, odd); - even_parent = odd; - } - - if(super_root_is_header){ - NodeTraits::set_parent(super_root, new_root); - NodeTraits::set_right(super_root, super_root_right_backup); - } - else if(old_root_is_right){ - NodeTraits::set_right(super_root, new_root); - } - else{ - NodeTraits::set_left(super_root, new_root); - NodeTraits::set_right(super_root, super_root_right_backup); - } - return new_root; - } - - //! <b>Requires</b>: "n" must be a node inserted in a tree. - //! - //! <b>Effects</b>: Returns a pointer to the header node of the tree. - //! - //! <b>Complexity</b>: Logarithmic. - //! - //! <b>Throws</b>: Nothing. - static node_ptr get_root(const node_ptr & node) - { - BOOST_INTRUSIVE_INVARIANT_ASSERT((!inited(node))); - node_ptr x = NodeTraits::get_parent(node); - if(x){ - while(!is_header(x)){ - x = NodeTraits::get_parent(x); - } - return x; - } - else{ - return node; - } - } - - private: - - template<class KeyType, class KeyNodePtrCompare> - static node_ptr lower_bound_loop - (node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp) - { - while(x){ - if(comp(x, key)){ - x = NodeTraits::get_right(x); - } - else{ - y = x; - x = NodeTraits::get_left(x); - } - } - return y; - } - - template<class KeyType, class KeyNodePtrCompare> - static node_ptr upper_bound_loop - (node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp) - { - while(x){ - if(comp(key, x)){ - y = x; - x = NodeTraits::get_left(x); - } - else{ - x = NodeTraits::get_right(x); - } - } - return y; - } - - - template<class NodePtrCompare> - static void insert_equal_check_impl - (bool upper, const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0) - { - std::size_t depth = 0; - node_ptr y(h); - node_ptr x(NodeTraits::get_parent(y)); - bool link_left; - - if(upper){ - while(x){ - ++depth; - y = x; - x = comp(new_node, x) ? - NodeTraits::get_left(x) : NodeTraits::get_right(x); - } - link_left = (y == h) || comp(new_node, y); - } - else{ - while(x){ - ++depth; - y = x; - x = !comp(x, new_node) ? - NodeTraits::get_left(x) : NodeTraits::get_right(x); - } - link_left = (y == h) || !comp(y, new_node); - } - - commit_data.link_left = link_left; - commit_data.node = y; - if(pdepth) *pdepth = depth; - } - - static void erase_impl(const node_ptr & header, const node_ptr & z, data_for_rebalance &info) - { - node_ptr y(z); - node_ptr x; - node_ptr x_parent = node_ptr(); - node_ptr z_left(NodeTraits::get_left(z)); - node_ptr z_right(NodeTraits::get_right(z)); - if(!z_left){ - x = z_right; // x might be null. - } - else if(!z_right){ // z has exactly one non-null child. y == z. - x = z_left; // x is not null. - } - else{ - // find z's successor - y = tree_algorithms::minimum (z_right); - x = NodeTraits::get_right(y); // x might be null. - } - - if(y != z){ - // relink y in place of z. y is z's successor - NodeTraits::set_parent(NodeTraits::get_left(z), y); - NodeTraits::set_left(y, NodeTraits::get_left(z)); - if(y != NodeTraits::get_right(z)){ - x_parent = NodeTraits::get_parent(y); - if(x) - NodeTraits::set_parent(x, x_parent); - NodeTraits::set_left(x_parent, x); // y must be a child of left_ - NodeTraits::set_right(y, NodeTraits::get_right(z)); - NodeTraits::set_parent(NodeTraits::get_right(z), y); - } - else - x_parent = y; - tree_algorithms::replace_own (z, y, header); - NodeTraits::set_parent(y, NodeTraits::get_parent(z)); - } - else { // y == z --> z has only one child, or none - x_parent = NodeTraits::get_parent(z); - if(x) - NodeTraits::set_parent(x, x_parent); - tree_algorithms::replace_own (z, x, header); - if(NodeTraits::get_left(header) == z){ - NodeTraits::set_left(header, !NodeTraits::get_right(z) ? // z->get_left() must be null also - NodeTraits::get_parent(z) : // makes leftmost == header if z == root - tree_algorithms::minimum (x)); - } - if(NodeTraits::get_right(header) == z){ - NodeTraits::set_right(header, !NodeTraits::get_left(z) ? // z->get_right() must be null also - NodeTraits::get_parent(z) : // makes rightmost == header if z == root - tree_algorithms::maximum(x)); - } - } - - info.x = x; - info.x_parent = x_parent; - info.y = y; - } -}; - -} //namespace detail { -} //namespace intrusive -} //namespace boost - -#include <boost/intrusive/detail/config_end.hpp> - -#endif //BOOST_INTRUSIVE_TREE_ALGORITHMS_HPP diff --git a/boost/intrusive/detail/tree_iterator.hpp b/boost/intrusive/detail/tree_iterator.hpp new file mode 100644 index 0000000000..c3b599d190 --- /dev/null +++ b/boost/intrusive/detail/tree_iterator.hpp @@ -0,0 +1,141 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2007-2013 +// +// 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_TREE_ITERATOR_HPP +#define BOOST_INTRUSIVE_TREE_ITERATOR_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/detail/std_fwd.hpp> +#include <boost/intrusive/detail/iiterator.hpp> +#include <boost/intrusive/bstree_algorithms.hpp> + +namespace boost { +namespace intrusive { + +///////////////////////////////////////////////////////////////////////////// +// // +// Implementation of the tree iterator // +// // +///////////////////////////////////////////////////////////////////////////// + +// tree_iterator provides some basic functions for a +// node oriented bidirectional iterator: +template<class ValueTraits, bool IsConst> +class tree_iterator +{ + protected: + typedef iiterator< ValueTraits, IsConst + , std::bidirectional_iterator_tag> types_t; + + typedef ValueTraits value_traits; + typedef typename types_t::node_traits node_traits; + + 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; + static const bool stateful_value_traits = types_t::stateful_value_traits; + typedef bstree_algorithms<node_traits> node_algorithms; + + public: + typedef typename types_t::iterator_traits::difference_type difference_type; + typedef typename types_t::iterator_traits::value_type value_type; + typedef typename types_t::iterator_traits::pointer pointer; + typedef typename types_t::iterator_traits::reference reference; + typedef typename types_t::iterator_traits::iterator_category iterator_category; + + tree_iterator() + {} + + explicit tree_iterator(const node_ptr & nodeptr, const const_value_traits_ptr &traits_ptr) + : members_(nodeptr, traits_ptr) + {} + + tree_iterator(tree_iterator<value_traits, false> const& other) + : members_(other.pointed_node(), other.get_value_traits()) + {} + + const node_ptr &pointed_node() const + { return members_.nodeptr_; } + + tree_iterator &operator=(const node_ptr &nodeptr) + { members_.nodeptr_ = nodeptr; return static_cast<tree_iterator&>(*this); } + + public: + tree_iterator& operator++() + { + members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_); + return static_cast<tree_iterator&> (*this); + } + + tree_iterator operator++(int) + { + tree_iterator result (*this); + members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_); + return result; + } + + tree_iterator& operator--() + { + members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_); + return static_cast<tree_iterator&> (*this); + } + + tree_iterator operator--(int) + { + tree_iterator result (*this); + members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_); + return result; + } + + friend bool operator== (const tree_iterator& l, const tree_iterator& r) + { return l.pointed_node() == r.pointed_node(); } + + friend bool operator!= (const tree_iterator& l, const tree_iterator& r) + { return !(l == r); } + + reference operator*() const + { return *operator->(); } + + pointer operator->() const + { return this->operator_arrow(detail::bool_<stateful_value_traits>()); } + + const_value_traits_ptr get_value_traits() const + { return members_.get_ptr(); } + + tree_iterator end_iterator_from_it() const + { + return tree_iterator(node_algorithms::get_header(this->pointed_node()), this->get_value_traits()); + } + + tree_iterator<value_traits, false> unconst() const + { return tree_iterator<value_traits, false>(this->pointed_node(), this->get_value_traits()); } + + private: + pointer operator_arrow(detail::false_) const + { return ValueTraits::to_value_ptr(members_.nodeptr_); } + + pointer operator_arrow(detail::true_) const + { return this->get_value_traits()->to_value_ptr(members_.nodeptr_); } + + iiterator_members<node_ptr, const_value_traits_ptr, stateful_value_traits> members_; +}; + +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_TREE_ITERATOR_HPP diff --git a/boost/intrusive/detail/tree_node.hpp b/boost/intrusive/detail/tree_node.hpp index 09fa7a4562..653d6fcf07 100644 --- a/boost/intrusive/detail/tree_node.hpp +++ b/boost/intrusive/detail/tree_node.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007-2012 +// (C) Copyright Ion Gaztanaga 2007-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -13,10 +13,12 @@ #ifndef BOOST_INTRUSIVE_TREE_NODE_HPP #define BOOST_INTRUSIVE_TREE_NODE_HPP +#if defined(_MSC_VER) +# pragma once +#endif + #include <boost/intrusive/detail/config_begin.hpp> -#include <iterator> -#include <boost/intrusive/pointer_traits.hpp> -#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/pointer_rebind.hpp> namespace boost { namespace intrusive { @@ -24,9 +26,7 @@ namespace intrusive { template<class VoidPointer> struct tree_node { - typedef typename pointer_traits - <VoidPointer>::template rebind_pointer - <tree_node<VoidPointer> >::type node_ptr; + typedef typename pointer_rebind<VoidPointer, tree_node>::type node_ptr; node_ptr parent_, left_, right_; }; @@ -36,152 +36,37 @@ struct tree_node_traits { typedef tree_node<VoidPointer> node; - typedef typename pointer_traits<VoidPointer>::template - rebind_pointer<node>::type node_ptr; - typedef typename pointer_traits<VoidPointer>::template - rebind_pointer<const node>::type const_node_ptr; + typedef typename node::node_ptr node_ptr; + typedef typename pointer_rebind<VoidPointer, const node>::type const_node_ptr; + + static node_ptr get_parent(const const_node_ptr & n) + { return n->parent_; } - static const node_ptr & get_parent(const const_node_ptr & n) + static node_ptr get_parent(const node_ptr & n) { return n->parent_; } static void set_parent(const node_ptr & n, const node_ptr & p) { n->parent_ = p; } - static const node_ptr & get_left(const const_node_ptr & n) + static node_ptr get_left(const const_node_ptr & n) + { return n->left_; } + + static node_ptr get_left(const node_ptr & n) { return n->left_; } static void set_left(const node_ptr & n, const node_ptr & l) { n->left_ = l; } - static const node_ptr & get_right(const const_node_ptr & n) + static node_ptr get_right(const const_node_ptr & n) + { return n->right_; } + + static node_ptr get_right(const node_ptr & n) { return n->right_; } static void set_right(const node_ptr & n, const node_ptr & r) { n->right_ = r; } }; -///////////////////////////////////////////////////////////////////////////// -// // -// Implementation of the tree iterator // -// // -///////////////////////////////////////////////////////////////////////////// - -// tree_iterator provides some basic functions for a -// node oriented bidirectional iterator: -template<class Container, bool IsConst> -class tree_iterator - : public std::iterator - < std::bidirectional_iterator_tag - , typename Container::value_type - , typename Container::difference_type - , typename detail::if_c<IsConst,typename Container::const_pointer,typename Container::pointer>::type - , typename detail::if_c<IsConst,typename Container::const_reference,typename Container::reference>::type - > -{ - protected: - typedef typename Container::real_value_traits real_value_traits; - typedef typename Container::node_algorithms node_algorithms; - typedef typename real_value_traits::node_traits node_traits; - typedef typename node_traits::node node; - typedef typename node_traits::node_ptr node_ptr; - typedef typename pointer_traits<node_ptr>::template - rebind_pointer<void>::type void_pointer; - static const bool store_container_ptr = - detail::store_cont_ptr_on_it<Container>::value; - - public: - typedef typename Container::value_type value_type; - typedef typename detail::if_c<IsConst,typename Container::const_pointer,typename Container::pointer>::type pointer; - typedef typename detail::if_c<IsConst,typename Container::const_reference,typename Container::reference>::type reference; - - - tree_iterator() - : members_ (node_ptr(), (const void *)0) - {} - - explicit tree_iterator(const node_ptr & nodeptr, const Container *cont_ptr) - : members_ (nodeptr, cont_ptr) - {} - - tree_iterator(tree_iterator<Container, false> const& other) - : members_(other.pointed_node(), other.get_container()) - {} - - const node_ptr &pointed_node() const - { return members_.nodeptr_; } - - tree_iterator &operator=(const node_ptr &nodeptr) - { members_.nodeptr_ = nodeptr; return static_cast<tree_iterator&>(*this); } - - public: - tree_iterator& operator++() - { - members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_); - return static_cast<tree_iterator&> (*this); - } - - tree_iterator operator++(int) - { - tree_iterator result (*this); - members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_); - return result; - } - - tree_iterator& operator--() - { - members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_); - return static_cast<tree_iterator&> (*this); - } - - tree_iterator operator--(int) - { - tree_iterator result (*this); - members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_); - return result; - } - - friend bool operator== (const tree_iterator& l, const tree_iterator& r) - { return l.pointed_node() == r.pointed_node(); } - - friend bool operator!= (const tree_iterator& l, const tree_iterator& r) - { return !(l == r); } - - reference operator*() const - { return *operator->(); } - - pointer operator->() const - { return this->get_real_value_traits()->to_value_ptr(members_.nodeptr_); } - - const Container *get_container() const - { return static_cast<const Container*>(members_.get_ptr()); } - - const real_value_traits *get_real_value_traits() const - { return &this->get_container()->get_real_value_traits(); } - - tree_iterator end_iterator_from_it() const - { - return tree_iterator(node_algorithms::get_header(this->pointed_node()), this->get_container()); - } - - tree_iterator<Container, false> unconst() const - { return tree_iterator<Container, false>(this->pointed_node(), this->get_container()); } - - private: - struct members - : public detail::select_constptr - <void_pointer, store_container_ptr>::type - { - typedef typename detail::select_constptr - <void_pointer, store_container_ptr>::type Base; - - members(const node_ptr &n_ptr, const void *cont) - : Base(cont), nodeptr_(n_ptr) - {} - - node_ptr nodeptr_; - } members_; -}; - } //namespace intrusive } //namespace boost diff --git a/boost/intrusive/detail/uncast.hpp b/boost/intrusive/detail/uncast.hpp new file mode 100644 index 0000000000..944b6cd617 --- /dev/null +++ b/boost/intrusive/detail/uncast.hpp @@ -0,0 +1,51 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2014 +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/libs/intrusive for documentation. +// +///////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_INTRUSIVE_DETAIL_UNCAST_HPP +#define BOOST_INTRUSIVE_DETAIL_UNCAST_HPP + +#if defined(_MSC_VER) +# pragma once +#endif + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/detail/mpl.hpp> + +namespace boost { +namespace intrusive { +namespace detail { + +template<class ConstNodePtr> +struct uncast_types +{ + typedef typename pointer_traits<ConstNodePtr>::element_type element_type; + typedef typename remove_const<element_type>::type non_const_type; + typedef typename pointer_traits<ConstNodePtr>:: + template rebind_pointer<non_const_type>::type non_const_pointer; + typedef pointer_traits<non_const_pointer> non_const_traits; +}; + +template<class ConstNodePtr> +static typename uncast_types<ConstNodePtr>::non_const_pointer + uncast(const ConstNodePtr & ptr) +{ + return uncast_types<ConstNodePtr>::non_const_traits::const_cast_from(ptr); +} + +} //namespace detail { +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP diff --git a/boost/intrusive/detail/utilities.hpp b/boost/intrusive/detail/utilities.hpp deleted file mode 100644 index c6bc798994..0000000000 --- a/boost/intrusive/detail/utilities.hpp +++ /dev/null @@ -1,879 +0,0 @@ -///////////////////////////////////////////////////////////////////////////// -// -// (C) Copyright Ion Gaztanaga 2006-2012 -// -// 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_UTILITIES_HPP -#define BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP - -#include <boost/intrusive/detail/config_begin.hpp> -#include <boost/intrusive/pointer_traits.hpp> -#include <boost/intrusive/detail/parent_from_member.hpp> -#include <boost/intrusive/detail/ebo_functor_holder.hpp> -#include <boost/intrusive/link_mode.hpp> -#include <boost/intrusive/detail/mpl.hpp> -#include <boost/intrusive/detail/assert.hpp> -#include <boost/intrusive/detail/is_stateful_value_traits.hpp> -#include <boost/intrusive/pointer_traits.hpp> -#include <boost/cstdint.hpp> -#include <cstddef> -#include <climits> -#include <iterator> -#include <boost/cstdint.hpp> -#include <boost/static_assert.hpp> - -namespace boost { -namespace intrusive { -namespace detail { - -template <class T> -struct internal_member_value_traits -{ - template <class U> static detail::one test(...); - template <class U> static detail::two test(typename U::member_value_traits* = 0); - static const bool value = sizeof(test<T>(0)) == sizeof(detail::two); -}; - -template <class T> -struct internal_base_hook_bool -{ - template<bool Add> - struct two_or_three {one _[2 + Add];}; - template <class U> static one test(...); - template <class U> static two_or_three<U::boost_intrusive_tags::is_base_hook> test (int); - static const std::size_t value = sizeof(test<T>(0)); -}; - -template <class T> -struct internal_base_hook_bool_is_true -{ - static const bool value = internal_base_hook_bool<T>::value > sizeof(one)*2; -}; - -template <class T> -struct internal_any_hook_bool -{ - template<bool Add> - struct two_or_three {one _[2 + Add];}; - template <class U> static one test(...); - template <class U> static two_or_three<U::is_any_hook> test (int); - static const std::size_t value = sizeof(test<T>(0)); -}; - -template <class T> -struct internal_any_hook_bool_is_true -{ - static const bool value = internal_any_hook_bool<T>::value > sizeof(one)*2; -}; - - -template <class T> -struct external_value_traits_bool -{ - template<bool Add> - struct two_or_three {one _[2 + Add];}; - template <class U> static one test(...); - template <class U> static two_or_three<U::external_value_traits> test (int); - static const std::size_t value = sizeof(test<T>(0)); -}; - -template <class T> -struct external_bucket_traits_bool -{ - template<bool Add> - struct two_or_three {one _[2 + Add];}; - template <class U> static one test(...); - template <class U> static two_or_three<U::external_bucket_traits> test (int); - static const std::size_t value = sizeof(test<T>(0)); -}; - -template <class T> -struct external_value_traits_is_true -{ - static const bool value = external_value_traits_bool<T>::value > sizeof(one)*2; -}; - -template<class Node, class Tag, link_mode_type LinkMode, int> -struct node_holder - : public Node -{}; - -template <class T> -inline T* to_raw_pointer(T* p) -{ return p; } - -template <class Pointer> -inline typename boost::intrusive::pointer_traits<Pointer>::element_type* -to_raw_pointer(const Pointer &p) -{ return boost::intrusive::detail::to_raw_pointer(p.operator->()); } - -//This functor compares a stored value -//and the one passed as an argument -template<class ConstReference> -class equal_to_value -{ - ConstReference t_; - - public: - equal_to_value(ConstReference t) - : t_(t) - {} - - bool operator()(ConstReference t)const - { return t_ == t; } -}; - -class null_disposer -{ - public: - template <class Pointer> - void operator()(Pointer) - {} -}; - -template<class NodeAlgorithms> -class init_disposer -{ - typedef typename NodeAlgorithms::node_ptr node_ptr; - - public: - void operator()(const node_ptr & p) - { NodeAlgorithms::init(p); } -}; - -template<bool ConstantSize, class SizeType> -struct size_holder -{ - static const bool constant_time_size = ConstantSize; - typedef SizeType size_type; - - SizeType get_size() const - { return size_; } - - void set_size(SizeType size) - { size_ = size; } - - void decrement() - { --size_; } - - void increment() - { ++size_; } - - SizeType size_; -}; - -template<class SizeType> -struct size_holder<false, SizeType> -{ - static const bool constant_time_size = false; - typedef SizeType size_type; - - size_type get_size() const - { return 0; } - - void set_size(size_type) - {} - - void decrement() - {} - - void increment() - {} -}; - -template<class KeyValueCompare, class Container> -struct key_nodeptr_comp - : private detail::ebo_functor_holder<KeyValueCompare> -{ - typedef typename Container::real_value_traits real_value_traits; - typedef typename Container::value_type value_type; - typedef typename real_value_traits::node_ptr node_ptr; - typedef typename real_value_traits::const_node_ptr const_node_ptr; - typedef detail::ebo_functor_holder<KeyValueCompare> base_t; - key_nodeptr_comp(KeyValueCompare kcomp, const Container *cont) - : base_t(kcomp), cont_(cont) - {} - - template<class T> - struct is_node_ptr - { - static const bool value = is_same<T, const_node_ptr>::value || is_same<T, node_ptr>::value; - }; - - template<class T> - const value_type & key_forward - (const T &node, typename enable_if_c<is_node_ptr<T>::value>::type * = 0) const - { return *cont_->get_real_value_traits().to_value_ptr(node); } - - template<class T> - const T & key_forward(const T &key, typename enable_if_c<!is_node_ptr<T>::value>::type* = 0) const - { return key; } - - - template<class KeyType, class KeyType2> - bool operator()(const KeyType &key1, const KeyType2 &key2) const - { return base_t::get()(this->key_forward(key1), this->key_forward(key2)); } - - const Container *cont_; -}; - -template<class F, class Container> -struct node_cloner - : private detail::ebo_functor_holder<F> -{ - typedef typename Container::real_value_traits real_value_traits; - typedef typename Container::node_algorithms node_algorithms; - typedef typename real_value_traits::value_type value_type; - typedef typename real_value_traits::pointer pointer; - typedef typename real_value_traits::node_traits::node node; - typedef typename real_value_traits::node_ptr node_ptr; - typedef typename real_value_traits::const_node_ptr const_node_ptr; - typedef detail::ebo_functor_holder<F> base_t; - enum { safemode_or_autounlink = - (int)real_value_traits::link_mode == (int)auto_unlink || - (int)real_value_traits::link_mode == (int)safe_link }; - - node_cloner(F f, const Container *cont) - : base_t(f), cont_(cont) - {} - - node_ptr operator()(const node_ptr & p) - { return this->operator()(*p); } - - node_ptr operator()(const node &to_clone) - { - const value_type &v = - *cont_->get_real_value_traits().to_value_ptr - (pointer_traits<const_node_ptr>::pointer_to(to_clone)); - node_ptr n = cont_->get_real_value_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) - BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n)); - return n; - } - - const Container *cont_; -}; - -template<class F, class Container> -struct node_disposer - : private detail::ebo_functor_holder<F> -{ - typedef typename Container::real_value_traits real_value_traits; - typedef typename real_value_traits::node_ptr node_ptr; - typedef detail::ebo_functor_holder<F> base_t; - typedef typename Container::node_algorithms node_algorithms; - enum { safemode_or_autounlink = - (int)real_value_traits::link_mode == (int)auto_unlink || - (int)real_value_traits::link_mode == (int)safe_link }; - - node_disposer(F f, const Container *cont) - : base_t(f), cont_(cont) - {} - - void operator()(const node_ptr & p) - { - if(safemode_or_autounlink) - node_algorithms::init(p); - base_t::get()(cont_->get_real_value_traits().to_value_ptr(p)); - } - const Container *cont_; -}; - -struct dummy_constptr -{ - dummy_constptr(const void *) - {} - - const void *get_ptr() const - { return 0; } -}; - -template<class VoidPointer> -struct constptr -{ - typedef typename boost::intrusive::pointer_traits<VoidPointer>:: - template rebind_pointer<const void>::type ConstVoidPtr; - - constptr(const void *ptr) - : const_void_ptr_(ptr) - {} - - const void *get_ptr() const - { return boost::intrusive::detail::to_raw_pointer(const_void_ptr_); } - - ConstVoidPtr const_void_ptr_; -}; - -template <class VoidPointer, bool store_ptr> -struct select_constptr -{ - typedef typename detail::if_c - < store_ptr - , constptr<VoidPointer> - , dummy_constptr - >::type type; -}; - -template<class T, bool Add> -struct add_const_if_c -{ - typedef typename detail::if_c - < Add - , typename detail::add_const<T>::type - , T - >::type type; -}; - -template <link_mode_type LinkMode> -struct link_dispatch -{}; - -template<class Hook> -void destructor_impl(Hook &hook, detail::link_dispatch<safe_link>) -{ //If this assertion raises, you might have destroyed an object - //while it was still inserted in a container that is alive. - //If so, remove the object from the container before destroying it. - (void)hook; BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT(!hook.is_linked()); -} - -template<class Hook> -void destructor_impl(Hook &hook, detail::link_dispatch<auto_unlink>) -{ hook.unlink(); } - -template<class Hook> -void destructor_impl(Hook &, detail::link_dispatch<normal_link>) -{} - -template<class T, class NodeTraits, link_mode_type LinkMode, class Tag, int HookType> -struct base_hook_traits -{ - public: - typedef detail::node_holder - <typename NodeTraits::node, Tag, LinkMode, HookType> node_holder; - typedef typename NodeTraits::node node; - typedef NodeTraits node_traits; - typedef T value_type; - typedef typename node_traits::node_ptr node_ptr; - typedef typename node_traits::const_node_ptr const_node_ptr; - typedef typename pointer_traits<node_ptr>:: - template rebind_pointer<T>::type pointer; - typedef typename pointer_traits<node_ptr>:: - template rebind_pointer<const T>::type const_pointer; - //typedef typename pointer_traits<pointer>::reference reference; - //typedef typename pointer_traits<const_pointer>::reference const_reference; - typedef T & reference; - typedef const T & const_reference; - typedef node_holder & node_holder_reference; - typedef const node_holder & const_node_holder_reference; - typedef node& node_reference; - typedef const node & const_node_reference; - - static const link_mode_type link_mode = LinkMode; - - static pointer to_value_ptr(const node_ptr & n) - { - return pointer_traits<pointer>::pointer_to - (static_cast<reference>(static_cast<node_holder_reference>(*n))); - } - - static const_pointer to_value_ptr(const const_node_ptr & n) - { - return pointer_traits<const_pointer>::pointer_to - (static_cast<const_reference>(static_cast<const_node_holder_reference>(*n))); - } - - static node_ptr to_node_ptr(reference value) - { - return pointer_traits<node_ptr>::pointer_to - (static_cast<node_reference>(static_cast<node_holder_reference>(value))); - } - - static const_node_ptr to_node_ptr(const_reference value) - { - return pointer_traits<const_node_ptr>::pointer_to - (static_cast<const_node_reference>(static_cast<const_node_holder_reference>(value))); - } -}; - -template<class T, class Hook, Hook T::* P> -struct member_hook_traits -{ - public: - typedef Hook hook_type; - typedef typename hook_type::boost_intrusive_tags::node_traits node_traits; - typedef typename node_traits::node node; - typedef T value_type; - typedef typename node_traits::node_ptr node_ptr; - typedef typename node_traits::const_node_ptr const_node_ptr; - typedef typename pointer_traits<node_ptr>:: - template rebind_pointer<T>::type pointer; - typedef typename pointer_traits<node_ptr>:: - template rebind_pointer<const T>::type const_pointer; - typedef T & reference; - typedef const T & const_reference; - typedef node& node_reference; - typedef const node & const_node_reference; - typedef hook_type& hook_reference; - typedef const hook_type & const_hook_reference; - - static const link_mode_type link_mode = Hook::boost_intrusive_tags::link_mode; - - static node_ptr to_node_ptr(reference value) - { - return pointer_traits<node_ptr>::pointer_to - (static_cast<node_reference>(static_cast<hook_reference>(value.*P))); - } - - static const_node_ptr to_node_ptr(const_reference value) - { - return pointer_traits<const_node_ptr>::pointer_to - (static_cast<const_node_reference>(static_cast<const_hook_reference>(value.*P))); - } - - static pointer to_value_ptr(const node_ptr & n) - { - return pointer_traits<pointer>::pointer_to - (*detail::parent_from_member<T, Hook> - (static_cast<Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P)); - } - - static const_pointer to_value_ptr(const const_node_ptr & n) - { - return pointer_traits<const_pointer>::pointer_to - (*detail::parent_from_member<T, Hook> - (static_cast<const Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P)); - } -}; - -template<class Functor> -struct function_hook_traits -{ - public: - typedef typename Functor::hook_type hook_type; - typedef typename Functor::hook_ptr hook_ptr; - typedef typename Functor::const_hook_ptr const_hook_ptr; - typedef typename hook_type::boost_intrusive_tags::node_traits node_traits; - typedef typename node_traits::node node; - typedef typename Functor::value_type value_type; - typedef typename node_traits::node_ptr node_ptr; - typedef typename node_traits::const_node_ptr const_node_ptr; - typedef typename pointer_traits<node_ptr>:: - template rebind_pointer<value_type>::type pointer; - typedef typename pointer_traits<node_ptr>:: - template rebind_pointer<const value_type>::type const_pointer; - typedef value_type & reference; - typedef const value_type & const_reference; - static const link_mode_type link_mode = hook_type::boost_intrusive_tags::link_mode; - - static node_ptr to_node_ptr(reference value) - { return static_cast<node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value))); } - - static const_node_ptr to_node_ptr(const_reference value) - { return static_cast<const node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value))); } - - static pointer to_value_ptr(const node_ptr & n) - { return Functor::to_value_ptr(to_hook_ptr(n)); } - - static const_pointer to_value_ptr(const const_node_ptr & n) - { return Functor::to_value_ptr(to_hook_ptr(n)); } - - private: - static hook_ptr to_hook_ptr(const node_ptr & n) - { return hook_ptr(&*static_cast<hook_type*>(&*n)); } - - static const_hook_ptr to_hook_ptr(const const_node_ptr & n) - { return const_hook_ptr(&*static_cast<const hook_type*>(&*n)); } -}; - - -//This function uses binary search to discover the -//highest set bit of the integer -inline std::size_t floor_log2 (std::size_t x) -{ - const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT; - const bool Size_t_Bits_Power_2= !(Bits & (Bits-1)); - BOOST_STATIC_ASSERT(Size_t_Bits_Power_2); - - std::size_t n = x; - std::size_t log2 = 0; - - for(std::size_t shift = Bits >> 1; shift; shift >>= 1){ - std::size_t tmp = n >> shift; - if (tmp) - log2 += shift, n = tmp; - } - - return log2; -} - -inline float fast_log2 (float val) -{ - union caster_t - { - boost::uint32_t x; - float val; - } caster; - - caster.val = val; - boost::uint32_t x = caster.x; - const int log_2 = (int)(((x >> 23) & 255) - 128); - x &= ~(255 << 23); - x += 127 << 23; - caster.x = x; - val = caster.val; - val = ((-1.0f/3.f) * val + 2.f) * val - (2.0f/3.f); - - return (val + log_2); -} - -inline std::size_t ceil_log2 (std::size_t x) -{ - return ((x & (x-1))!= 0) + floor_log2(x); -} - -template<class SizeType, std::size_t N> -struct numbits_eq -{ - static const bool value = sizeof(SizeType)*CHAR_BIT == N; -}; - -template<class SizeType, class Enabler = void > -struct sqrt2_pow_max; - -template <class SizeType> -struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 32> >::type> -{ - static const boost::uint32_t value = 0xb504f334; - static const std::size_t pow = 31; -}; - -template <class SizeType> -struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 64> >::type> -{ - static const boost::uint64_t value = 0xb504f333f9de6484ull; - static const std::size_t pow = 63; -}; - -// Returns floor(pow(sqrt(2), x * 2 + 1)). -// Defined for X from 0 up to the number of bits in size_t minus 1. -inline std::size_t sqrt2_pow_2xplus1 (std::size_t x) -{ - const std::size_t value = (std::size_t)sqrt2_pow_max<std::size_t>::value; - const std::size_t pow = (std::size_t)sqrt2_pow_max<std::size_t>::pow; - return (value >> (pow - x)) + 1; -} - -template<class Container, class Disposer> -class exception_disposer -{ - Container *cont_; - Disposer &disp_; - - exception_disposer(const exception_disposer&); - exception_disposer &operator=(const exception_disposer&); - - public: - exception_disposer(Container &cont, Disposer &disp) - : cont_(&cont), disp_(disp) - {} - - void release() - { cont_ = 0; } - - ~exception_disposer() - { - if(cont_){ - cont_->clear_and_dispose(disp_); - } - } -}; - -template<class Container, class Disposer, class SizeType> -class exception_array_disposer -{ - Container *cont_; - Disposer &disp_; - SizeType &constructed_; - - exception_array_disposer(const exception_array_disposer&); - exception_array_disposer &operator=(const exception_array_disposer&); - - public: - - exception_array_disposer - (Container &cont, Disposer &disp, SizeType &constructed) - : cont_(&cont), disp_(disp), constructed_(constructed) - {} - - void release() - { cont_ = 0; } - - ~exception_array_disposer() - { - SizeType n = constructed_; - if(cont_){ - while(n--){ - cont_[n].clear_and_dispose(disp_); - } - } - } -}; - -template<class ValueTraits, bool ExternalValueTraits> -struct store_cont_ptr_on_it_impl -{ - static const bool value = is_stateful_value_traits<ValueTraits>::value; -}; - -template<class ValueTraits> -struct store_cont_ptr_on_it_impl<ValueTraits, true> -{ - static const bool value = true; -}; - -template <class Container> -struct store_cont_ptr_on_it -{ - typedef typename Container::value_traits value_traits; - static const bool value = store_cont_ptr_on_it_impl - <value_traits, external_value_traits_is_true<value_traits>::value>::value; -}; - -template<class Container, bool IsConst> -struct node_to_value - : public detail::select_constptr - < typename pointer_traits - <typename Container::pointer>::template rebind_pointer<void>::type - , detail::store_cont_ptr_on_it<Container>::value - >::type -{ - static const bool store_container_ptr = - detail::store_cont_ptr_on_it<Container>::value; - - typedef typename Container::real_value_traits real_value_traits; - typedef typename real_value_traits::value_type value_type; - typedef typename detail::select_constptr - < typename pointer_traits - <typename Container::pointer>::template rebind_pointer<void>::type - , store_container_ptr >::type Base; - typedef typename real_value_traits::node_traits::node node; - typedef typename detail::add_const_if_c - <value_type, IsConst>::type vtype; - typedef typename detail::add_const_if_c - <node, IsConst>::type ntype; - typedef typename pointer_traits - <typename Container::pointer>::template rebind_pointer<ntype>::type npointer; - - node_to_value(const Container *cont) - : Base(cont) - {} - - typedef vtype & result_type; - typedef ntype & first_argument_type; - - const Container *get_container() const - { - if(store_container_ptr) - return static_cast<const Container*>(Base::get_ptr()); - else - return 0; - } - - const real_value_traits *get_real_value_traits() const - { - if(store_container_ptr) - return &this->get_container()->get_real_value_traits(); - else - return 0; - } - - result_type operator()(first_argument_type arg) const - { - return *(this->get_real_value_traits()->to_value_ptr - (pointer_traits<npointer>::pointer_to(arg))); - } -}; - -//This is not standard, but should work with all compilers -union max_align -{ - char char_; - short short_; - int int_; - long long_; - #ifdef BOOST_HAS_LONG_LONG - long long long_long_; - #endif - float float_; - double double_; - long double long_double_; - void * void_ptr_; -}; - -template<class T, std::size_t N> -class array_initializer -{ - public: - template<class CommonInitializer> - array_initializer(const CommonInitializer &init) - { - char *init_buf = (char*)rawbuf; - std::size_t i = 0; - try{ - for(; i != N; ++i){ - new(init_buf)T(init); - init_buf += sizeof(T); - } - } - catch(...){ - while(i--){ - init_buf -= sizeof(T); - ((T*)init_buf)->~T(); - } - throw; - } - } - - operator T* () - { return (T*)(rawbuf); } - - operator const T*() const - { return (const T*)(rawbuf); } - - ~array_initializer() - { - char *init_buf = (char*)rawbuf + N*sizeof(T); - for(std::size_t i = 0; i != N; ++i){ - init_buf -= sizeof(T); - ((T*)init_buf)->~T(); - } - } - - private: - detail::max_align rawbuf[(N*sizeof(T)-1)/sizeof(detail::max_align)+1]; -}; - - - - -template<class It> -class reverse_iterator - : public std::iterator< - typename std::iterator_traits<It>::iterator_category, - typename std::iterator_traits<It>::value_type, - typename std::iterator_traits<It>::difference_type, - typename std::iterator_traits<It>::pointer, - typename std::iterator_traits<It>::reference> -{ - public: - typedef typename std::iterator_traits<It>::pointer pointer; - typedef typename std::iterator_traits<It>::reference reference; - typedef typename std::iterator_traits<It>::difference_type difference_type; - typedef It iterator_type; - - reverse_iterator(){} - - explicit reverse_iterator(It r) - : m_current(r) - {} - - template<class OtherIt> - reverse_iterator(const reverse_iterator<OtherIt>& r) - : m_current(r.base()) - {} - - It base() const - { return m_current; } - - reference operator*() const - { It temp(m_current); --temp; return *temp; } - - pointer operator->() const - { It temp(m_current); --temp; return temp.operator->(); } - - reference operator[](difference_type off) const - { return this->m_current[-off]; } - - reverse_iterator& operator++() - { --m_current; return *this; } - - reverse_iterator operator++(int) - { - reverse_iterator temp = *this; - --m_current; - return temp; - } - - reverse_iterator& operator--() - { - ++m_current; - return *this; - } - - reverse_iterator operator--(int) - { - reverse_iterator temp(*this); - ++m_current; - return temp; - } - - friend bool operator==(const reverse_iterator& l, const reverse_iterator& r) - { return l.m_current == r.m_current; } - - friend bool operator!=(const reverse_iterator& l, const reverse_iterator& r) - { return l.m_current != r.m_current; } - - friend bool operator<(const reverse_iterator& l, const reverse_iterator& r) - { return l.m_current < r.m_current; } - - friend bool operator<=(const reverse_iterator& l, const reverse_iterator& r) - { return l.m_current <= r.m_current; } - - friend bool operator>(const reverse_iterator& l, const reverse_iterator& r) - { return l.m_current > r.m_current; } - - friend bool operator>=(const reverse_iterator& l, const reverse_iterator& r) - { return l.m_current >= r.m_current; } - - reverse_iterator& operator+=(difference_type off) - { m_current -= off; return *this; } - - friend reverse_iterator operator+(const reverse_iterator & l, difference_type off) - { - reverse_iterator tmp(l.m_current); - tmp.m_current -= off; - return tmp; - } - - reverse_iterator& operator-=(difference_type off) - { m_current += off; return *this; } - - friend reverse_iterator operator-(const reverse_iterator & l, difference_type off) - { - reverse_iterator tmp(l.m_current); - tmp.m_current += off; - return tmp; - } - - friend difference_type operator-(const reverse_iterator& l, const reverse_iterator& r) - { return r.m_current - l.m_current; } - - private: - It m_current; // the wrapped iterator -}; - -} //namespace detail -} //namespace intrusive -} //namespace boost - -#include <boost/intrusive/detail/config_end.hpp> - -#endif //BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP diff --git a/boost/intrusive/detail/workaround.hpp b/boost/intrusive/detail/workaround.hpp index 87cab4befc..ad00691f25 100644 --- a/boost/intrusive/detail/workaround.hpp +++ b/boost/intrusive/detail/workaround.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2013. 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) // @@ -11,12 +11,20 @@ #ifndef BOOST_INTRUSIVE_DETAIL_WRKRND_HPP #define BOOST_INTRUSIVE_DETAIL_WRKRND_HPP -#include <boost/intrusive/detail/config_begin.hpp> +#if defined(_MSC_VER) +# pragma once +#endif + +#ifndef BOOST_CONFIG_HPP +#include <boost/config.hpp> +#endif -#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES) +#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) #define BOOST_INTRUSIVE_PERFECT_FORWARDING #endif -#include <boost/intrusive/detail/config_end.hpp> +//Macros for documentation purposes. For code, expands to the argument +#define BOOST_INTRUSIVE_IMPDEF(TYPE) TYPE +#define BOOST_INTRUSIVE_SEEDOC(TYPE) TYPE #endif //#ifndef BOOST_INTRUSIVE_DETAIL_WRKRND_HPP |