diff options
Diffstat (limited to 'boost/intrusive/detail')
25 files changed, 418 insertions, 323 deletions
diff --git a/boost/intrusive/detail/any_node_and_algorithms.hpp b/boost/intrusive/detail/any_node_and_algorithms.hpp index bda9ad3c45..b274135a90 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-2009 +// (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 @@ -18,7 +18,7 @@ #include <boost/intrusive/detail/assert.hpp> #include <boost/intrusive/pointer_traits.hpp> #include <cstddef> -#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/detail/mpl.hpp> #include <boost/pointer_cast.hpp> namespace boost { @@ -100,10 +100,10 @@ struct any_unordered_node_traits { n->node_ptr_2 = prev; } static std::size_t get_hash(const const_node_ptr & n) - { return n->size_t_1; } + { return n->size_t_1; } static void set_hash(const node_ptr & n, std::size_t h) - { n->size_t_1 = h; } + { n->size_t_1 = h; } }; @@ -255,9 +255,9 @@ class any_algorithms //! <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. @@ -265,9 +265,9 @@ class any_algorithms { node->node_ptr_1 = 0; }; //! <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 !node->node_ptr_1; }; @@ -289,8 +289,8 @@ class any_algorithms } }; -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/assert.hpp b/boost/intrusive/detail/assert.hpp index cfe392bfb0..33de97f701 100644 --- a/boost/intrusive/detail/assert.hpp +++ b/boost/intrusive/detail/assert.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2009 +// (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 @@ -11,7 +11,7 @@ ///////////////////////////////////////////////////////////////////////////// #ifndef BOOST_INTRUSIVE_DETAIL_ASSERT_HPP -#define BOOST_INTRUSIVE_DETAIL_ASSERT_HPP +#define BOOST_INTRUSIVE_DETAIL_ASSERT_HPP #if defined(_MSC_VER)&&(_MSC_VER>=1200) #pragma once diff --git a/boost/intrusive/detail/avltree_node.hpp b/boost/intrusive/detail/avltree_node.hpp index dc600e6695..aec0dabd4b 100644 --- a/boost/intrusive/detail/avltree_node.hpp +++ b/boost/intrusive/detail/avltree_node.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007. +// (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 @@ -172,13 +172,13 @@ struct avltree_node_traits , OptimizeSize && max_pointer_plus_bits < VoidPointer - , detail::alignment_of<compact_avltree_node<VoidPointer> >::value + , detail::alignment_of<compact_avltree_node<VoidPointer> >::value >::value >= 2u > {}; -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/clear_on_destructor_base.hpp b/boost/intrusive/detail/clear_on_destructor_base.hpp index 6765dfa05d..1b5c27fff4 100644 --- a/boost/intrusive/detail/clear_on_destructor_base.hpp +++ b/boost/intrusive/detail/clear_on_destructor_base.hpp @@ -1,6 +1,6 @@ //////} // /////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2008-2009. Distributed under the Boost +// (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) // diff --git a/boost/intrusive/detail/common_slist_algorithms.hpp b/boost/intrusive/detail/common_slist_algorithms.hpp index 15d6b3ff29..942b35a3f4 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-2009 +// (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 @@ -44,11 +44,11 @@ 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_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()); } + static void init(const node_ptr & this_node) + { NodeTraits::set_next(this_node, node_ptr()); } static bool unique(const const_node_ptr & this_node) { @@ -56,7 +56,7 @@ class common_slist_algorithms return !next || next == this_node; } - static bool inited(const const_node_ptr & this_node) + static bool inited(const const_node_ptr & this_node) { return !NodeTraits::get_next(this_node); } static void unlink_after(const node_ptr & prev_node) @@ -80,7 +80,7 @@ class common_slist_algorithms NodeTraits::set_next(bp, b); NodeTraits::set_next(be, p); } - + static void transfer_after(const node_ptr & bp, const node_ptr & bb, const node_ptr & be) { if (bp != bb && bp != be && bb != be) { @@ -95,8 +95,8 @@ class common_slist_algorithms }; } //namespace detail -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/config_begin.hpp b/boost/intrusive/detail/config_begin.hpp index bb126fcdf0..7d153368a5 100644 --- a/boost/intrusive/detail/config_begin.hpp +++ b/boost/intrusive/detail/config_begin.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2009 +// (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 @@ -20,10 +20,10 @@ #pragma warning (push) // //'function' : resolved overload was found by argument-dependent lookup - //A function found by argument-dependent lookup (Koenig lookup) was eventually + //A function found by argument-dependent lookup (Koenig lookup) was eventually //chosen by overload resolution. // - //In Visual C++ .NET and earlier compilers, a different function would have + //In Visual C++ .NET and earlier compilers, a different function would have //been called. To pick the original function, use an explicitly qualified name. // diff --git a/boost/intrusive/detail/config_end.hpp b/boost/intrusive/detail/config_end.hpp index 4277cb576f..d653030daa 100644 --- a/boost/intrusive/detail/config_end.hpp +++ b/boost/intrusive/detail/config_end.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2009 +// (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 diff --git a/boost/intrusive/detail/ebo_functor_holder.hpp b/boost/intrusive/detail/ebo_functor_holder.hpp index d4c2d1593b..850d074326 100644 --- a/boost/intrusive/detail/ebo_functor_holder.hpp +++ b/boost/intrusive/detail/ebo_functor_holder.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Joaquin M Lopez Munoz 2006-2009 +// (C) Copyright Joaquin M Lopez Munoz 2006-2012 // // 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/function_detector.hpp b/boost/intrusive/detail/function_detector.hpp index e00a7efcf2..08cee2d561 100644 --- a/boost/intrusive/detail/function_detector.hpp +++ b/boost/intrusive/detail/function_detector.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2009-2009. +// (C) Copyright Ion Gaztanaga 2009-2012. // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -15,7 +15,7 @@ /////////////////////////////////////////////////////////////////////////////// // Copyright 2007 Alexandre Courpron // -// Permission to use, copy, modify, redistribute and sell this software, +// Permission to use, copy, modify, redistribute and sell this software, // provided that this copyright notice appears on all copies of the software. /////////////////////////////////////////////////////////////////////////////// @@ -74,7 +74,7 @@ namespace function_detector { public : \ static const int check = NotFound + (sizeof(Test<T>(0, 0)) - sizeof(NotFoundType));\ };\ -}}} //namespace boost::intrusive::function_detector { +}}} //namespace boost::intrusive::function_detector { #define BOOST_INTRUSIVE_DETECT_FUNCTION(Class, InstantiationKey, ReturnType, Identifier, Params) \ ::boost::intrusive::function_detector::DetectMember_##InstantiationKey_##Identifier< Class,\ diff --git a/boost/intrusive/detail/generic_hook.hpp b/boost/intrusive/detail/generic_hook.hpp index fc35610b8d..5ddd52074e 100644 --- a/boost/intrusive/detail/generic_hook.hpp +++ b/boost/intrusive/detail/generic_hook.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007-2009 +// (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 @@ -143,7 +143,7 @@ class generic_hook 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 = + static const bool safemode_or_autounlink = (int)link_mode == (int)auto_unlink || (int)link_mode == (int)safe_link; }; @@ -163,14 +163,14 @@ class generic_hook } } - generic_hook(const generic_hook& ) + generic_hook(const generic_hook& ) { if(boost_intrusive_tags::safemode_or_autounlink){ node_algorithms::init(this->this_ptr()); } } - generic_hook& operator=(const generic_hook& ) + generic_hook& operator=(const generic_hook& ) { return *this; } ~generic_hook() @@ -179,13 +179,13 @@ class generic_hook (*this, detail::link_dispatch<boost_intrusive_tags::link_mode>()); } - void swap_nodes(generic_hook &other) + void swap_nodes(generic_hook &other) { node_algorithms::swap_nodes (this->this_ptr(), other.this_ptr()); } - bool is_linked() const + 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 )); @@ -201,8 +201,8 @@ class generic_hook }; } //namespace detail -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/has_member_function_callable_with.hpp b/boost/intrusive/detail/has_member_function_callable_with.hpp index 33811e3210..6516e28067 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-2011. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2011-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) // @@ -10,7 +10,7 @@ // sample.h -#if !BOOST_PP_IS_ITERATING +#if !defined(BOOST_PP_IS_ITERATING) #ifndef BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_DETAILS_INCLUDED #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_DETAILS_INCLUDED @@ -21,7 +21,7 @@ #include <boost/static_assert.hpp> #include <boost/move/move.hpp> - //Mark that we don't support 0 arg calls due to compiler ICE in GCC 3.4/4.0/4.1 and + //Mark that we don't support 0 arg calls due to compiler ICE in GCC 3.4/4.0/4.1 and //wrong SFINAE for GCC 4.2/4.3 #if defined(__GNUC__) && !defined(__clang__) && ((__GNUC__*100 + __GNUC_MINOR__*10) >= 340) && ((__GNUC__*100 + __GNUC_MINOR__*10) <= 430) #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED @@ -113,7 +113,7 @@ }; //! - #if !defined(_MSC_VER) || (_MSC_VER != 1600) + #if !defined(_MSC_VER) || (_MSC_VER < 1600) #if defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) @@ -121,16 +121,16 @@ 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 + //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 + #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 = + , 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) @@ -156,15 +156,15 @@ 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> + 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 + #endif //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) - #else //#if !defined(_MSC_VER) || (_MSC_VER != 1600) + #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)> @@ -180,7 +180,7 @@ 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) + #endif //#if !defined(_MSC_VER) || (_MSC_VER < 1600) #else //#if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) @@ -196,7 +196,7 @@ //Special case for 0 args template< class F - , std::size_t N = + , 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) @@ -222,9 +222,9 @@ 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> + 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); }; diff --git a/boost/intrusive/detail/hashtable_node.hpp b/boost/intrusive/detail/hashtable_node.hpp index ac6ab81948..86e607460c 100644 --- a/boost/intrusive/detail/hashtable_node.hpp +++ b/boost/intrusive/detail/hashtable_node.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007-2009 +// (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 @@ -40,7 +40,7 @@ struct prime_list_holder template<int Dummy> const std::size_t prime_list_holder<Dummy>::prime_list[] = { - 3ul, 7ul, 11ul, 17ul, 29ul, + 3ul, 7ul, 11ul, 17ul, 29ul, 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, @@ -180,9 +180,9 @@ class hashtable_iterator { return hashtable_iterator<Container, false>(this->slist_it(), this->get_container()); } public: - hashtable_iterator& operator++() + hashtable_iterator& operator++() { this->increment(); return *this; } - + hashtable_iterator operator++(int) { hashtable_iterator result (*this); @@ -219,7 +219,7 @@ class hashtable_iterator size_type buckets_len = cont->bucket_count(); ++slist_it_; - if(buckets[0].cend().pointed_node() <= slist_it_.pointed_node() && + 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 bucket_type &b = static_cast<const bucket_type&> diff --git a/boost/intrusive/detail/is_stateful_value_traits.hpp b/boost/intrusive/detail/is_stateful_value_traits.hpp index e38f4de459..8677c666d4 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-2009. +// (C) Copyright Ion Gaztanaga 2009-2012. // // 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/list_node.hpp b/boost/intrusive/detail/list_node.hpp index df99912dd2..d406af60e4 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-2009 +// (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 @@ -57,7 +57,7 @@ struct list_node_traits { n->next_ = next; } }; -// list_iterator provides some basic functions for a +// list_iterator provides some basic functions for a // node oriented bidirectional iterator: template<class Container, bool IsConst> class list_iterator @@ -76,7 +76,7 @@ class list_iterator 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 = + static const bool store_container_ptr = detail::store_cont_ptr_on_it<Container>::value; public: @@ -103,14 +103,14 @@ class list_iterator { members_.nodeptr_ = node; return static_cast<list_iterator&>(*this); } public: - list_iterator& operator++() + 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); + //members_.nodeptr_ = node_traits::get_next(members_.nodeptr_); + return static_cast<list_iterator&> (*this); } - + list_iterator operator++(int) { list_iterator result (*this); @@ -118,12 +118,12 @@ class list_iterator return result; } - list_iterator& operator--() - { - members_.nodeptr_ = node_traits::get_previous(members_.nodeptr_); - return static_cast<list_iterator&> (*this); + 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); @@ -182,8 +182,8 @@ class list_iterator } members_; }; -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/memory_util.hpp b/boost/intrusive/detail/memory_util.hpp index ad026c6d61..1a6431b078 100644 --- a/boost/intrusive/detail/memory_util.hpp +++ b/boost/intrusive/detail/memory_util.hpp @@ -6,7 +6,7 @@ // ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2011-2011. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2011-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) // @@ -182,7 +182,11 @@ 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*); @@ -194,7 +198,11 @@ 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*); @@ -205,12 +213,6 @@ struct type_has_rebind_other template <typename Ptr, typename T> struct type_rebind_mode { - template <typename X> - static char test(int, typename X::template rebind<T>::other*); - - template <typename X> - static int test(boost::intrusive::detail::LowPriorityConversion<int>, void*); - 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; @@ -251,6 +253,13 @@ 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) \ diff --git a/boost/intrusive/detail/mpl.hpp b/boost/intrusive/detail/mpl.hpp index 075381cae2..02b1361d2a 100644 --- a/boost/intrusive/detail/mpl.hpp +++ b/boost/intrusive/detail/mpl.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2009 +// (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 @@ -127,10 +127,10 @@ struct identity #if defined(BOOST_MSVC) || defined(__BORLANDC_) #define BOOST_INTRUSIVE_TT_DECL __cdecl #else -#define BOOST_INTRUSIVE_TT_DECL +#define BOOST_INTRUSIVE_TT_DECL #endif -#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) +#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) && !defined(UNDER_CE) #define BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS #endif @@ -156,10 +156,14 @@ 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; }; @@ -188,10 +192,14 @@ 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; }; @@ -220,10 +228,14 @@ 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; }; @@ -346,9 +358,9 @@ struct ls_zeros<1> static const std::size_t value = 0; }; -} //namespace detail -} //namespace intrusive -} //namespace boost +} //namespace detail +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/parent_from_member.hpp b/boost/intrusive/detail/parent_from_member.hpp index c06d932a70..2afffb47bc 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-2009 +// (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 @@ -31,29 +31,53 @@ inline std::ptrdiff_t offset_from_pointer_to_member(const Member Parent::* ptr_t //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) - return *(const boost::int32_t*)(void*)&ptr_to_member; + union caster_union + { + const Member Parent::* ptr_to_member; + boost::int32_t offset; + } caster; + caster.ptr_to_member = ptr_to_member; + return std::ptrdiff_t(caster.offset); //This works with gcc, msvc, ac++, ibmcpp #elif defined(__GNUC__) || defined(__HP_aCC) || defined(BOOST_INTEL) || \ defined(__IBMCPP__) || defined(__DECCXX) const Parent * const parent = 0; - const char *const member = reinterpret_cast<const char*>(&(parent->*ptr_to_member)); - return std::ptrdiff_t(member - reinterpret_cast<const char*>(parent)); + const char *const member = static_cast<const char*>(static_cast<const void*>(&(parent->*ptr_to_member))); + return std::ptrdiff_t(member - static_cast<const char*>(static_cast<const void*>(parent))); #else //This is the traditional C-front approach: __MWERKS__, __DMC__, __SUNPRO_CC - return (*(const std::ptrdiff_t*)(void*)&ptr_to_member) - 1; + union caster_union + { + const Member Parent::* ptr_to_member; + std::ptrdiff_t offset; + } caster; + caster.ptr_to_member = ptr_to_member; + return caster.offset - 1; #endif } template<class Parent, class Member> inline Parent *parent_from_member(Member *member, const Member Parent::* ptr_to_member) { - return (Parent*)((char*)member - offset_from_pointer_to_member(ptr_to_member)); + return static_cast<Parent*> + ( + static_cast<void*> + ( + static_cast<char*>(static_cast<void*>(member)) - offset_from_pointer_to_member(ptr_to_member) + ) + ); } template<class Parent, class Member> inline const Parent *parent_from_member(const Member *member, const Member Parent::* ptr_to_member) { - return (const Parent*)((const char*)member - offset_from_pointer_to_member(ptr_to_member)); + return static_cast<const Parent*> + ( + static_cast<const void*> + ( + static_cast<const char*>(static_cast<const void*>(member)) - offset_from_pointer_to_member(ptr_to_member) + ) + ); } } //namespace detail { diff --git a/boost/intrusive/detail/preprocessor.hpp b/boost/intrusive/detail/preprocessor.hpp index de662809e3..348b104bb0 100644 --- a/boost/intrusive/detail/preprocessor.hpp +++ b/boost/intrusive/detail/preprocessor.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2008-2011. Distributed under the Boost +// (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) // @@ -18,7 +18,7 @@ #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/detail/workaround.hpp> -#include <boost/preprocessor/iteration/local.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> diff --git a/boost/intrusive/detail/rbtree_node.hpp b/boost/intrusive/detail/rbtree_node.hpp index dbe0130024..b76582bb61 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-2009. +// (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 @@ -164,13 +164,13 @@ struct rbtree_node_traits , OptimizeSize && (max_pointer_plus_bits < VoidPointer - , detail::alignment_of<compact_rbtree_node<VoidPointer> >::value + , detail::alignment_of<compact_rbtree_node<VoidPointer> >::value >::value >= 1) > {}; -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/slist_node.hpp b/boost/intrusive/detail/slist_node.hpp index 5b96c09742..0eddbcd69a 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-2009 +// (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 @@ -43,13 +43,13 @@ struct slist_node_traits <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; static const node_ptr &get_next(const const_node_ptr & n) - { return n->next_; } + { return n->next_; } static void set_next(const node_ptr & n, const node_ptr & next) - { n->next_ = next; } + { n->next_ = next; } }; -// slist_iterator provides some basic functions for a +// slist_iterator provides some basic functions for a // node oriented bidirectional iterator: template<class Container, bool IsConst> class slist_iterator @@ -68,7 +68,7 @@ class slist_iterator 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 = + static const bool store_container_ptr = detail::store_cont_ptr_on_it<Container>::value; public: @@ -95,12 +95,12 @@ class slist_iterator { 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++() + { + members_.nodeptr_ = node_traits::get_next(members_.nodeptr_); + return static_cast<slist_iterator&> (*this); } - + slist_iterator operator++(int) { slist_iterator result (*this); @@ -155,8 +155,8 @@ class slist_iterator } members_; }; -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/transform_iterator.hpp b/boost/intrusive/detail/transform_iterator.hpp index 15ef3ab2c9..488db9ade8 100644 --- a/boost/intrusive/detail/transform_iterator.hpp +++ b/boost/intrusive/detail/transform_iterator.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007-2009 +// (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 @@ -71,7 +71,7 @@ class transform_iterator { return members_.m_it; } //Constructors - transform_iterator& operator++() + transform_iterator& operator++() { increment(); return *this; } transform_iterator operator++(int) diff --git a/boost/intrusive/detail/tree_algorithms.hpp b/boost/intrusive/detail/tree_algorithms.hpp index 8d31d9d710..c92d39b3b9 100644 --- a/boost/intrusive/detail/tree_algorithms.hpp +++ b/boost/intrusive/detail/tree_algorithms.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007. +// (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 @@ -25,20 +25,20 @@ 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 +//! 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 +//! 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)---------+ -//! | +---------+ | -//! | | | +//! +---------+ +//! header------------------------------>| | +//! | | +//! +----------(left)--------| |--------(right)---------+ +//! | +---------+ | +//! | | | //! | | (parent) | //! | | | //! | | | @@ -61,10 +61,10 @@ namespace detail { //! | | | | | | //! | | | | | | //! | +---+-----+ +-----+---+ +---+-----+ +-----+---+ | -//! +-->| | | | | | | |<--+ -//! | A | | C | | E | | G | -//! | | | | | | | | -//! +---------+ +---------+ +---------+ +---------+ +//! +-->| | | | | | | |<--+ +//! | A | | C | | E | | G | +//! | | | | | | | | +//! +---------+ +---------+ +---------+ +---------+ //! //! tree_algorithms is configured with a NodeTraits class, which encapsulates the @@ -82,15 +82,15 @@ namespace detail { //! <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 @@ -153,11 +153,11 @@ class tree_algorithms //! <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); } @@ -175,15 +175,15 @@ class tree_algorithms //! <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>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. //! @@ -192,22 +192,22 @@ class tree_algorithms { 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>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. //! @@ -216,8 +216,8 @@ class tree_algorithms { if(node1 == node2) return; - - //node1 and node2 must not be header nodes + + //node1 and node2 must not be header nodes //BOOST_INTRUSIVE_INVARIANT_ASSERT((header1 != node1 && header2 != node2)); if(header1 != header2){ //Update header1 if necessary @@ -347,14 +347,14 @@ class tree_algorithms //! <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>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 @@ -370,14 +370,14 @@ class tree_algorithms //! <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>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 @@ -388,7 +388,7 @@ class tree_algorithms { 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); @@ -428,11 +428,11 @@ class tree_algorithms } //! <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) { @@ -452,11 +452,11 @@ class tree_algorithms } //! <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) { @@ -479,11 +479,11 @@ class tree_algorithms } //! <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) { @@ -497,11 +497,11 @@ class tree_algorithms } //! <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) { @@ -517,9 +517,9 @@ class tree_algorithms //! <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. @@ -527,17 +527,17 @@ class tree_algorithms { NodeTraits::set_parent(node, node_ptr()); NodeTraits::set_left(node, node_ptr()); - NodeTraits::set_right(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) && + return !NodeTraits::get_parent(node) && !NodeTraits::get_left(node) && !NodeTraits::get_right(node) ; }; @@ -546,9 +546,9 @@ class tree_algorithms //! //! <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. @@ -556,19 +556,19 @@ class tree_algorithms { NodeTraits::set_parent(header, node_ptr()); NodeTraits::set_left(header, header); - NodeTraits::set_right(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 + //! <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) @@ -581,14 +581,14 @@ class tree_algorithms } //! <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 @@ -624,11 +624,11 @@ class tree_algorithms } //! <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) { @@ -660,11 +660,11 @@ class tree_algorithms } //! <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) { @@ -677,18 +677,18 @@ class tree_algorithms //! <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 + //! + //! <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>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 @@ -734,7 +734,7 @@ class tree_algorithms (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 + //and rightmost's parent )){ return true; } @@ -750,7 +750,7 @@ class tree_algorithms //! "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 @@ -765,55 +765,73 @@ class tree_algorithms //! 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 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 they there are no equivalent elements. + //! <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. - template<class KeyType, class KeyNodePtrCompare> - static std::pair<node_ptr, node_ptr> equal_range - (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) + //! + //! <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(comp(x, key)){ + //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); } - else if(comp(key, 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{ - node_ptr xu(x), yu(y); - y = x, x = NodeTraits::get_left(x); - xu = NodeTraits::get_right(xu); - - while(x){ - if(comp(x, key)){ - x = NodeTraits::get_right(x); - } - else { - y = x; - x = NodeTraits::get_left(x); - } - } - - while(xu){ - if(comp(key, xu)){ - yu = xu; - xu = NodeTraits::get_left(xu); - } - else { - xu = NodeTraits::get_right(xu); - } - } - return std::pair<node_ptr,node_ptr> (y, yu); + //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); @@ -824,29 +842,38 @@ class tree_algorithms //! 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) { - node_ptr y = uncast(header); - node_ptr x = NodeTraits::get_parent(header); - while(x){ - if(comp(x, key)){ - x = NodeTraits::get_right(x); - } - else { - y = x; - x = NodeTraits::get_left(x); - } - } - return y; + return lower_bound_loop(NodeTraits::get_parent(header), uncast(header), key, comp); } //! <b>Requires</b>: "header" must be the header node of a tree. @@ -858,40 +885,29 @@ class tree_algorithms //! 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) { - node_ptr y = uncast(header); - node_ptr x = NodeTraits::get_parent(header); - while(x){ - if(comp(key, x)){ - y = x; - x = NodeTraits::get_left(x); - } - else { - x = NodeTraits::get_right(x); - } - } - return y; + 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". - //! - //! + //! 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. @@ -929,7 +945,7 @@ class tree_algorithms //! 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. @@ -940,11 +956,11 @@ class tree_algorithms //! 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 @@ -976,7 +992,7 @@ class tree_algorithms while(x){ ++depth; y = x; - x = (left_child = comp(key, x)) ? + x = (left_child = comp(key, x)) ? NodeTraits::get_left(x) : (prev = y, NodeTraits::get_right(x)); } @@ -1026,7 +1042,7 @@ class tree_algorithms { if(hint == header || !comp(hint, new_node)){ node_ptr prev(hint); - if(hint == NodeTraits::get_left(header) || + 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; @@ -1147,13 +1163,13 @@ class tree_algorithms } //! <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>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) { @@ -1171,18 +1187,18 @@ class tree_algorithms //! 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 + //! <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 + //! 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 @@ -1247,7 +1263,7 @@ class tree_algorithms leftmost = insertion_point; } //Then clone right nodes - else if( NodeTraits::get_right(current) && + else if( NodeTraits::get_right(current) && !NodeTraits::get_right(insertion_point)){ current = NodeTraits::get_right(current); node_ptr temp = insertion_point; @@ -1300,21 +1316,21 @@ class tree_algorithms } //! <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; } @@ -1449,7 +1465,7 @@ class tree_algorithms 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 + //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. @@ -1521,7 +1537,7 @@ class tree_algorithms 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 + //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. @@ -1536,7 +1552,7 @@ class tree_algorithms //Put old_root as right child NodeTraits::set_right(super_root, old_root); - //Start the compression algorithm + //Start the compression algorithm node_ptr even_parent = super_root; node_ptr new_root = old_root; @@ -1578,7 +1594,7 @@ class tree_algorithms //! <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) { @@ -1596,6 +1612,40 @@ class tree_algorithms } 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) @@ -1609,7 +1659,7 @@ class tree_algorithms while(x){ ++depth; y = x; - x = comp(new_node, x) ? + x = comp(new_node, x) ? NodeTraits::get_left(x) : NodeTraits::get_right(x); } link_left = (y == h) || comp(new_node, y); @@ -1618,7 +1668,7 @@ class tree_algorithms while(x){ ++depth; y = x; - x = !comp(x, new_node) ? + x = !comp(x, new_node) ? NodeTraits::get_left(x) : NodeTraits::get_right(x); } link_left = (y == h) || !comp(y, new_node); @@ -1689,8 +1739,8 @@ class tree_algorithms }; } //namespace detail { -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/tree_node.hpp b/boost/intrusive/detail/tree_node.hpp index ccbe70caf1..09fa7a4562 100644 --- a/boost/intrusive/detail/tree_node.hpp +++ b/boost/intrusive/detail/tree_node.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2007. +// (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 @@ -66,7 +66,7 @@ struct tree_node_traits // // ///////////////////////////////////////////////////////////////////////////// -// tree_iterator provides some basic functions for a +// tree_iterator provides some basic functions for a // node oriented bidirectional iterator: template<class Container, bool IsConst> class tree_iterator @@ -86,7 +86,7 @@ class tree_iterator 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 = + static const bool store_container_ptr = detail::store_cont_ptr_on_it<Container>::value; public: @@ -114,12 +114,12 @@ class tree_iterator { 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++() + { + members_.nodeptr_ = node_algorithms::next_node(members_.nodeptr_); + return static_cast<tree_iterator&> (*this); } - + tree_iterator operator++(int) { tree_iterator result (*this); @@ -127,12 +127,12 @@ class tree_iterator return result; } - tree_iterator& operator--() - { - members_.nodeptr_ = node_algorithms::prev_node(members_.nodeptr_); - return static_cast<tree_iterator&> (*this); + 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); @@ -182,8 +182,8 @@ class tree_iterator } members_; }; -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/utilities.hpp b/boost/intrusive/detail/utilities.hpp index c0416203ff..c6bc798994 100644 --- a/boost/intrusive/detail/utilities.hpp +++ b/boost/intrusive/detail/utilities.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2009 +// (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 @@ -200,7 +200,7 @@ struct key_nodeptr_comp key_nodeptr_comp(KeyValueCompare kcomp, const Container *cont) : base_t(kcomp), cont_(cont) {} - + template<class T> struct is_node_ptr { @@ -236,7 +236,7 @@ struct node_cloner 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 = + enum { safemode_or_autounlink = (int)real_value_traits::link_mode == (int)auto_unlink || (int)real_value_traits::link_mode == (int)safe_link }; @@ -270,7 +270,7 @@ struct node_disposer 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 = + enum { safemode_or_autounlink = (int)real_value_traits::link_mode == (int)auto_unlink || (int)real_value_traits::link_mode == (int)safe_link }; @@ -378,7 +378,7 @@ struct base_hook_traits static const link_mode_type link_mode = LinkMode; - static pointer to_value_ptr(const node_ptr & n) + static pointer to_value_ptr(const node_ptr & n) { return pointer_traits<pointer>::pointer_to (static_cast<reference>(static_cast<node_holder_reference>(*n))); @@ -504,7 +504,7 @@ inline std::size_t floor_log2 (std::size_t x) 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) @@ -529,7 +529,7 @@ inline float fast_log2 (float val) x += 127 << 23; caster.x = x; val = caster.val; - val = ((-1.0f/3) * val + 2) * val - 2.0f/3; + val = ((-1.0f/3.f) * val + 2.f) * val - (2.0f/3.f); return (val + log_2); } @@ -655,7 +655,7 @@ struct node_to_value , detail::store_cont_ptr_on_it<Container>::value >::type { - static const bool store_container_ptr = + static const bool store_container_ptr = detail::store_cont_ptr_on_it<Container>::value; typedef typename Container::real_value_traits real_value_traits; @@ -871,8 +871,8 @@ class reverse_iterator }; } //namespace detail -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> diff --git a/boost/intrusive/detail/workaround.hpp b/boost/intrusive/detail/workaround.hpp index 5de529fb66..87cab4befc 100644 --- a/boost/intrusive/detail/workaround.hpp +++ b/boost/intrusive/detail/workaround.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2009. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-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) // |