Imported Upstream version 1.62.0upstream/1.62.0

Change-Id: I9d4c1ddb7b7d8f0069217ecc582700f9fda6dd4c
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>

9 files changed, 289 insertions, 147 deletions

diff --git a/boost/intrusive/detail/algo_type.hpp b/boost/intrusive/detail/algo_type.hpp
index 6da48e9e79..70ec63f574 100644
--- a/boost/intrusive/detail/algo_type.hpp
+++ b/boost/intrusive/detail/algo_type.hpp
@@ -35,7 +35,10 @@ enum algo_types
    AvlTreeAlgorithms,
    SgTreeAlgorithms,
    SplayTreeAlgorithms,
-   TreapAlgorithms
+   TreapAlgorithms,
+   UnorderedAlgorithms,
+   UnorderedCircularSlistAlgorithms,
+   AnyAlgorithm
 };
 
 template<algo_types AlgoType, class NodeTraits>
diff --git a/boost/intrusive/detail/any_node_and_algorithms.hpp b/boost/intrusive/detail/any_node_and_algorithms.hpp
index 4b087b582b..26a1edcd3e 100644
--- a/boost/intrusive/detail/any_node_and_algorithms.hpp
+++ b/boost/intrusive/detail/any_node_and_algorithms.hpp
@@ -23,8 +23,9 @@
 
 #include <boost/intrusive/detail/workaround.hpp>
 #include <boost/intrusive/pointer_rebind.hpp>
-#include <cstddef>
 #include <boost/intrusive/detail/mpl.hpp>
+#include <boost/intrusive/detail/algo_type.hpp>
+#include <cstddef>
 
 namespace boost {
 namespace intrusive {
@@ -279,6 +280,17 @@ class any_algorithms
    }
 };
 
+///@cond
+
+template<class NodeTraits>
+struct get_algo<AnyAlgorithm, NodeTraits>
+{
+   typedef typename pointer_rebind<typename NodeTraits::node_ptr, void>::type void_pointer;
+   typedef any_algorithms<void_pointer> type;
+};
+
+///@endcond
+
 } //namespace intrusive
 } //namespace boost
 
diff --git a/boost/intrusive/detail/common_slist_algorithms.hpp b/boost/intrusive/detail/common_slist_algorithms.hpp
index c6fa289a23..5e6ff4d1aa 100644
--- a/boost/intrusive/detail/common_slist_algorithms.hpp
+++ b/boost/intrusive/detail/common_slist_algorithms.hpp
@@ -52,34 +52,34 @@ class common_slist_algorithms
       return p;
    }
 
-   static void init(const node_ptr & this_node)
+   BOOST_INTRUSIVE_FORCEINLINE static void init(const node_ptr & this_node)
    {  NodeTraits::set_next(this_node, node_ptr());  }
 
-   static bool unique(const const_node_ptr & this_node)
+   BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & this_node)
    {
       node_ptr next = NodeTraits::get_next(this_node);
       return !next || next == this_node;
    }
 
-   static bool inited(const const_node_ptr & this_node)
+   BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & this_node)
    {  return !NodeTraits::get_next(this_node); }
 
-   static void unlink_after(const node_ptr & prev_node)
+   BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(const node_ptr & prev_node)
    {
       const_node_ptr this_node(NodeTraits::get_next(prev_node));
       NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node));
    }
 
-   static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node)
+   BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node)
    {  NodeTraits::set_next(prev_node, last_node);  }
 
-   static void link_after(const node_ptr & prev_node, const node_ptr & this_node)
+   BOOST_INTRUSIVE_FORCEINLINE static void link_after(const node_ptr & prev_node, const node_ptr & this_node)
    {
       NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node));
       NodeTraits::set_next(prev_node, this_node);
    }
 
-   static void incorporate_after(const node_ptr & bp, const node_ptr & b, const node_ptr & be)
+   BOOST_INTRUSIVE_FORCEINLINE static void incorporate_after(const node_ptr & bp, const node_ptr & b, const node_ptr & be)
    {
       node_ptr p(NodeTraits::get_next(bp));
       NodeTraits::set_next(bp, b);
diff --git a/boost/intrusive/detail/ebo_functor_holder.hpp b/boost/intrusive/detail/ebo_functor_holder.hpp
index ef278ed805..31b2f81398 100644
--- a/boost/intrusive/detail/ebo_functor_holder.hpp
+++ b/boost/intrusive/detail/ebo_functor_holder.hpp
@@ -259,7 +259,7 @@ class ebo_functor_holder<T, false>
    BOOST_INTRUSIVE_FORCEINLINE ebo_functor_holder& operator=(BOOST_COPY_ASSIGN_REF(ebo_functor_holder) x)
    {
       const ebo_functor_holder&r = x;
-      this->get() = x.get();
+      this->get() = r;
       return *this;
    }
 
diff --git a/boost/intrusive/detail/generic_hook.hpp b/boost/intrusive/detail/generic_hook.hpp
index b57a12b458..13421b8805 100644
--- a/boost/intrusive/detail/generic_hook.hpp
+++ b/boost/intrusive/detail/generic_hook.hpp
@@ -26,6 +26,7 @@
 #include <boost/intrusive/detail/mpl.hpp>
 #include <boost/intrusive/detail/assert.hpp>
 #include <boost/intrusive/detail/node_holder.hpp>
+#include <boost/intrusive/detail/algo_type.hpp>
 #include <boost/static_assert.hpp>
 
 namespace boost {
@@ -120,7 +121,8 @@ struct hooktags_impl
 /// @endcond
 
 template
-   < class NodeAlgorithms
+   < boost::intrusive::algo_types Algo
+   , class NodeTraits
    , class Tag
    , link_mode_type LinkMode
    , base_hook_type BaseHookType
@@ -135,20 +137,20 @@ class generic_hook
    //from the hook.
    : public detail::if_c
       < detail::is_same<Tag, member_tag>::value
-      , typename NodeAlgorithms::node
-      , node_holder<typename NodeAlgorithms::node, Tag, BaseHookType>
+      , typename NodeTraits::node
+      , node_holder<typename NodeTraits::node, Tag, BaseHookType>
       >::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, dft_tag>::value*BaseHookType>
+      < generic_hook<Algo, NodeTraits, Tag, LinkMode, BaseHookType>
+      , detail::is_same<Tag, dft_tag>::value ? BaseHookType : NoBaseHookId>
    /// @endcond
 {
    /// @cond
-   typedef          NodeAlgorithms                    node_algorithms;
+   typedef typename get_algo<Algo, NodeTraits>::type  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;
@@ -156,7 +158,7 @@ class generic_hook
    public:
 
    typedef hooktags_impl
-      < typename NodeAlgorithms::node_traits
+      < NodeTraits
       , Tag, LinkMode, BaseHookType>                  hooktags;
 
    node_ptr this_ptr()
diff --git a/boost/intrusive/detail/has_member_function_callable_with.hpp b/boost/intrusive/detail/has_member_function_callable_with.hpp
index 2e73305d17..92ef60ee6d 100644
--- a/boost/intrusive/detail/has_member_function_callable_with.hpp
+++ b/boost/intrusive/detail/has_member_function_callable_with.hpp
@@ -11,13 +11,22 @@
 #ifndef BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_CALLABLE_WITH_HPP
 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_CALLABLE_WITH_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
-#if defined(__GNUC__) && !defined(__clang__) && ((__GNUC__*100 + __GNUC_MINOR__*10) >= 340) && ((__GNUC__*100 + __GNUC_MINOR__*10) <= 430)
-   #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED
-#elif defined(BOOST_INTEL) && (BOOST_INTEL < 1200 )
-   #define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED
+#ifndef BOOST_CONFIG_HPP
+#  include <boost/config.hpp>
 #endif
+
+//In case no decltype and no variadics, 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/MSVC10/MSVC11
+#if defined(BOOST_NO_CXX11_DECLTYPE) && defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+#  if defined(BOOST_GCC) && (BOOST_GCC < 40400)
+#     define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED
+#  elif defined(BOOST_INTEL) && (BOOST_INTEL < 1200)
+#     define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED
+#  elif defined(BOOST_MSVC) && (BOOST_MSVC < 1800)
+#     define BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED
+#  endif
+#endif   //#if defined(BOOST_NO_CXX11_DECLTYPE) && defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
 #include <cstddef>
 #include <boost/move/utility_core.hpp>
 #include <boost/move/detail/fwd_macros.hpp>
@@ -27,6 +36,11 @@ namespace boost_intrusive_hmfcw {
 typedef char yes_type;
 struct no_type{ char dummy[2]; };
 
+struct dont_care
+{
+   dont_care(...);
+};
+
 #if defined(BOOST_NO_CXX11_DECLTYPE)
 
 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
@@ -39,11 +53,6 @@ struct make_dontcare
 
 #endif
 
-struct dont_care
-{
-   dont_care(...);
-};
-
 struct private_type
 {
    static private_type p;
@@ -56,7 +65,7 @@ yes_type is_private_type(private_type const &);
 
 #endif   //#if defined(BOOST_NO_CXX11_DECLTYPE)
 
-#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_NO_CXX11_DECLTYPE)
 
 template<typename T> struct remove_cv                    {  typedef T type;   };
 template<typename T> struct remove_cv<const T>           {  typedef T type;   };
@@ -124,7 +133,31 @@ BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG
    //    declaration, special case and 0 arg specializaton
    //
    /////////////////////////////////////////////////////////
-   /////////////////////////////////////////////////////////
+
+   template <typename Type>
+   class BOOST_MOVE_CAT(has_member_function_named_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
+   {
+      struct BaseMixin
+      {
+         void BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME()
+         {} //Some compilers require the definition or linker errors happen
+      };
+
+      struct Base
+         : public boost_intrusive_hmfcw::remove_cv<Type>::type, public BaseMixin
+      {  //Declare the unneeded default constructor as some old compilers wrongly require it with is_convertible
+         Base(){}
+      };
+      template <typename T, T t> class Helper{};
+
+      template <typename U>
+      static boost_intrusive_hmfcw::no_type  deduce
+         (U*, Helper<void (BaseMixin::*)(), &U::BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME>* = 0);
+      static boost_intrusive_hmfcw::yes_type deduce(...);
+
+      public:
+      static const bool value = sizeof(boost_intrusive_hmfcw::yes_type) == sizeof(deduce((Base*)0));
+   };
 
    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
       /////////////////////////////////////////////////////////
@@ -136,53 +169,45 @@ BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG
       /////////////////////////////////////////////////////////
 
       //defined(BOOST_NO_CXX11_DECLTYPE) must be true
-      template<class Fun, class ...DontCares>
+      template<class Fun>
       struct FunWrapTmpl : Fun
       {
          using Fun::BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME;
+         FunWrapTmpl();
+         template<class ...DontCares>
          boost_intrusive_hmfcw::private_type BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(DontCares...) const;
       };
 
+      template<typename Fun, bool HasFunc, class ...Args>
+      struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME);
+
+      //No BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME member specialization
       template<typename Fun, class ...Args>
-      struct BOOST_MOVE_CAT(has_member_function_callable_with_,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, Args...>
+      struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
+         <Fun, false, Args...>
       {
-         typedef FunWrapTmpl<typename boost_intrusive_hmfcw::make_dontcare<Args>::type...> FunWrap;
+         static const bool value = false;
+      };
 
-         static bool const value = (sizeof(boost_intrusive_hmfcw::no_type) ==
-                                    sizeof(boost_intrusive_hmfcw::is_private_type
-                                             ( (::boost::move_detail::declval< FunWrap<Fun> >().
+      template<typename Fun, class ...Args>
+      struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_,BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true, Args...>
+      {
+         static bool const value = (sizeof(boost_intrusive_hmfcw::no_type) == sizeof(boost_intrusive_hmfcw::is_private_type
+                                             ( (::boost::move_detail::declval
+                                                   < FunWrapTmpl<Fun> >().
                                                    BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(::boost::move_detail::declval<Args>()...), 0) )
                                           )
                                     );
       };
-   #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
-
-      //Preprocessor must be used to generate specializations instead of variadic templates
 
-      template <typename Type>
-      class BOOST_MOVE_CAT(has_member_function_named_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
-      {
-         struct BaseMixin
-         {
-            void BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME()
-            {} //Some compilers require the definition or linker errors happen
-         };
-
-         struct Base
-            : public boost_intrusive_hmfcw::remove_cv<Type>::type, public BaseMixin
-         {  //Declare the unneeded default constructor as some old compilers wrongly require it with is_convertible
-            Base(){}
-         };
-         template <typename T, T t> class Helper{};
-
-         template <typename U>
-         static boost_intrusive_hmfcw::no_type  deduce
-            (U*, Helper<void (BaseMixin::*)(), &U::BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME>* = 0);
-         static boost_intrusive_hmfcw::yes_type deduce(...);
-
-         public:
-         static const bool value = sizeof(boost_intrusive_hmfcw::yes_type) == sizeof(deduce((Base*)0));
-      };
+      template<typename Fun, class ...Args>
+      struct BOOST_MOVE_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
+         : public BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
+            <Fun
+            , BOOST_MOVE_CAT(has_member_function_named_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun>::value
+            , Args...>
+      {};
+   #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 
       /////////////////////////////////////////////////////////
       /////////////////////////////////////////////////////////
@@ -222,24 +247,24 @@ BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG
 
             #if !defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED)
 
-            template<class F, std::size_t N = sizeof(boost::move_detail::declval<F>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(), 0)>
-            struct BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
-            {  boost_intrusive_hmfcw::yes_type dummy[N ? 1 : 2];   };
+               template<class F, std::size_t N = sizeof(boost::move_detail::declval<F>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(), 0)>
+               struct BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)
+               {  boost_intrusive_hmfcw::yes_type dummy[N ? 1 : 2];   };
 
-            template<typename Fun>
-            struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true>
-            {
-               template<class U> static BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>
-                  Test(BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*);
-               template<class U> static boost_intrusive_hmfcw::no_type Test(...);
-               static const bool value = sizeof(Test< Fun >(0)) == sizeof(boost_intrusive_hmfcw::yes_type);
-            };
+               template<typename Fun>
+               struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true>
+               {
+                  template<class U> static BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>
+                     Test(BOOST_MOVE_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*);
+                  template<class U> static boost_intrusive_hmfcw::no_type Test(...);
+                  static const bool value = sizeof(Test< Fun >(0)) == sizeof(boost_intrusive_hmfcw::yes_type);
+               };
 
             #else //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED)
 
                template<typename Fun>
                struct BOOST_MOVE_CAT(has_member_function_callable_with_impl_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<Fun, true>
-               {//GCC [3.4-4.3) gives ICE when instantiating the 0 arg version so it is not supported.
+               {  //Some compilers gives ICE when instantiating the 0 arg version so it is not supported.
                   static const bool value = true;
                };
 
diff --git a/boost/intrusive/detail/key_nodeptr_comp.hpp b/boost/intrusive/detail/key_nodeptr_comp.hpp
index 1a5ec32acc..9d64f09bcd 100644
--- a/boost/intrusive/detail/key_nodeptr_comp.hpp
+++ b/boost/intrusive/detail/key_nodeptr_comp.hpp
@@ -23,6 +23,8 @@
 
 #include <boost/intrusive/detail/mpl.hpp>
 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
+#include <boost/intrusive/detail/tree_value_compare.hpp>
+
 
 namespace boost {
 namespace intrusive {
@@ -30,64 +32,84 @@ namespace detail {
 
 template < class KeyTypeKeyCompare
          , class ValueTraits
-         , class KeyOfValue = void
+         , class KeyOfValue
          >
-struct key_nodeptr_comp
-   //Use public inheritance to avoid MSVC bugs with closures
-   :  public ebo_functor_holder<KeyTypeKeyCompare>
+struct key_nodeptr_comp_types
 {
-   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<KeyTypeKeyCompare>   base_t;
+   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 typename detail::if_c
             < detail::is_same<KeyOfValue, void>::value
             , detail::identity<value_type>
             , KeyOfValue
-            >::type                                key_of_value;
-   typedef typename key_of_value::type         key_type;
-
-   key_nodeptr_comp(KeyTypeKeyCompare kcomp, const ValueTraits *traits)
-      :  base_t(kcomp), traits_(traits)
-   {}
+            >::type                                      key_of_value;
+   typedef tree_value_compare
+      <typename ValueTraits::pointer, KeyTypeKeyCompare, key_of_value>      base_t;
+};
 
-   template<class T>
-   struct is_node_ptr
+//This function object transforms a key comparison type to
+//a function that can compare nodes or nodes with nodes or keys.
+template < class KeyTypeKeyCompare
+         , class ValueTraits
+         , class KeyOfValue = void
+         >
+struct key_nodeptr_comp
+   //Use public inheritance to avoid MSVC bugs with closures
+   :  public key_nodeptr_comp_types<KeyTypeKeyCompare, ValueTraits, KeyOfValue>::base_t
+{
+   typedef key_nodeptr_comp_types<KeyTypeKeyCompare, ValueTraits, KeyOfValue> types_t;
+   typedef typename types_t::value_traits          value_traits;
+   typedef typename types_t::value_type            value_type;
+   typedef typename types_t::node_ptr              node_ptr;
+   typedef typename types_t::const_node_ptr        const_node_ptr;
+   typedef typename types_t::base_t                base_t;
+   typedef typename types_t::key_of_value          key_of_value;
+
+   template <class P1>
+   struct is_same_or_nodeptr_convertible
    {
-      static const bool value = is_same<T, const_node_ptr>::value || is_same<T, node_ptr>::value;
+      static const bool same_type = is_same<P1,const_node_ptr>::value || is_same<P1,node_ptr>::value;
+      static const bool value = same_type || is_convertible<P1, const_node_ptr>::value;
    };
 
-   //key_forward
-   template<class T>
-   typename enable_if<is_node_ptr<T>, const key_type &>::type key_forward(const T &node) const
-   {  return key_of_value()(*traits_->to_value_ptr(node));  }
+   base_t base() const
+   {  return static_cast<const base_t&>(*this); }
 
-   template<class T>
-   #if defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN)
-   const T &key_forward (const T &key, typename disable_if<is_node_ptr<T> >::type* =0) const
-   #else
-   typename disable_if<is_node_ptr<T>, const T &>::type key_forward(const T &key) const
-   #endif
-   {  return key;  }
-
-   //operator() 1 arg
-   template<class KeyType>
-   bool operator()(const KeyType &key1) const
-   {  return base_t::get()(this->key_forward(key1));  }
+   BOOST_INTRUSIVE_FORCEINLINE key_nodeptr_comp(KeyTypeKeyCompare kcomp, const ValueTraits *traits)
+      :  base_t(kcomp), traits_(traits)
+   {}
 
-   template<class KeyType>
-   bool operator()(const KeyType &key1)
-   {  return base_t::get()(this->key_forward(key1));  }
+   //pred(pnode)
+   template<class T1>
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()(const T1 &t1, typename enable_if_c< is_same_or_nodeptr_convertible<T1>::value >::type* =0) const
+   {  return base().get()(key_of_value()(*traits_->to_value_ptr(t1)));  }
 
    //operator() 2 arg
-   template<class KeyType, class KeyType2>
-   bool operator()(const KeyType &key1, const KeyType2 &key2) const
-   {  return base_t::get()(this->key_forward(key1), this->key_forward(key2));  }
-
-   template<class KeyType, class KeyType2>
-   bool operator()(const KeyType &key1, const KeyType2 &key2)
-   {  return base_t::get()(this->key_forward(key1), this->key_forward(key2));  }
+   //pred(pnode, pnode)
+   template<class T1, class T2>
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()
+      (const T1 &t1, const T2 &t2, typename enable_if_c< is_same_or_nodeptr_convertible<T1>::value && is_same_or_nodeptr_convertible<T2>::value >::type* =0) const
+   {  return base()(*traits_->to_value_ptr(t1), *traits_->to_value_ptr(t2));  }
+
+   //pred(pnode, key)
+   template<class T1, class T2>
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()
+      (const T1 &t1, const T2 &t2, typename enable_if_c< is_same_or_nodeptr_convertible<T1>::value && !is_same_or_nodeptr_convertible<T2>::value >::type* =0) const
+   {  return base()(*traits_->to_value_ptr(t1), t2);  }
+
+   //pred(key, pnode)
+   template<class T1, class T2>
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()
+      (const T1 &t1, const T2 &t2, typename enable_if_c< !is_same_or_nodeptr_convertible<T1>::value && is_same_or_nodeptr_convertible<T2>::value >::type* =0) const
+   {  return base()(t1, *traits_->to_value_ptr(t2));  }
+
+   //pred(key, key)
+   template<class T1, class T2>
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()
+      (const T1 &t1, const T2 &t2, typename enable_if_c< !is_same_or_nodeptr_convertible<T1>::value && !is_same_or_nodeptr_convertible<T2>::value >::type* =0) const
+   {  return base()(t1, t2);  }
 
    const ValueTraits *const traits_;
 };
diff --git a/boost/intrusive/detail/size_holder.hpp b/boost/intrusive/detail/size_holder.hpp
index 9802ac32f1..bd14dc5049 100644
--- a/boost/intrusive/detail/size_holder.hpp
+++ b/boost/intrusive/detail/size_holder.hpp
@@ -51,6 +51,9 @@ struct size_holder
    BOOST_INTRUSIVE_FORCEINLINE void decrease(SizeType n)
    {  size_ -= n; }
 
+   BOOST_INTRUSIVE_FORCEINLINE void swap(size_holder &other)
+   {  SizeType tmp(size_); size_ = other.size_; other.size_ = tmp; }
+
    SizeType size_;
 };
 
@@ -77,6 +80,8 @@ struct size_holder<false, SizeType, Tag>
 
    BOOST_INTRUSIVE_FORCEINLINE void decrease(SizeType)
    {}
+
+   BOOST_INTRUSIVE_FORCEINLINE void swap(size_holder){}
 };
 
 }  //namespace detail{
diff --git a/boost/intrusive/detail/tree_value_compare.hpp b/boost/intrusive/detail/tree_value_compare.hpp
index 810d894066..c8f596fc96 100644
--- a/boost/intrusive/detail/tree_value_compare.hpp
+++ b/boost/intrusive/detail/tree_value_compare.hpp
@@ -21,67 +21,140 @@
 #include <boost/intrusive/detail/workaround.hpp>
 #include <boost/intrusive/detail/mpl.hpp>
 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
+#include <boost/intrusive/pointer_traits.hpp>
 
 namespace boost{
 namespace intrusive{
 
-template<class Key, class T, class KeyCompare, class KeyOfValue>
+//Needed to support smart references to value types
+template <class From, class ValuePtr>
+struct disable_if_smartref_to
+   : detail::disable_if_c 
+      <  detail::is_same
+            <From, typename pointer_traits
+               <ValuePtr>
+                  ::reference>::value
+      || detail::is_same
+            <From, typename pointer_traits
+                     < typename pointer_rebind
+                           <ValuePtr, const typename pointer_element<ValuePtr>::type>::type>
+                  ::reference>::value
+      >
+{};
+
+//This function object takes a KeyCompare function object
+//and compares values that contains keys using KeyOfValue
+template< class ValuePtr, class KeyCompare, class KeyOfValue
+        , bool = boost::intrusive::detail::is_same<typename pointer_element<ValuePtr>::type, typename KeyOfValue::type>::value >
 struct tree_value_compare
    :  public boost::intrusive::detail::ebo_functor_holder<KeyCompare>
 {
-   typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t;
-   typedef T            value_type;
-   typedef KeyCompare   key_compare;
-   typedef KeyOfValue   key_of_value;
-   typedef Key          key_type;
+   typedef typename pointer_element<ValuePtr>::type   value_type;
+   typedef KeyCompare                                 key_compare;
+   typedef KeyOfValue                                 key_of_value;
+   typedef typename KeyOfValue::type                  key_type;
 
+   typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t;
 
-   tree_value_compare()
+   BOOST_INTRUSIVE_FORCEINLINE tree_value_compare()
       :  base_t()
    {}
 
-   explicit tree_value_compare(const key_compare &kcomp)
+   BOOST_INTRUSIVE_FORCEINLINE explicit tree_value_compare(const key_compare &kcomp)
       :  base_t(kcomp)
    {}
 
-   tree_value_compare (const tree_value_compare &x)
+   BOOST_INTRUSIVE_FORCEINLINE tree_value_compare (const tree_value_compare &x)
       :  base_t(x.base_t::get())
    {}
 
-   tree_value_compare &operator=(const tree_value_compare &x)
+   BOOST_INTRUSIVE_FORCEINLINE tree_value_compare &operator=(const tree_value_compare &x)
    {  this->base_t::get() = x.base_t::get();   return *this;  }
 
-   tree_value_compare &operator=(const key_compare &x)
+   BOOST_INTRUSIVE_FORCEINLINE tree_value_compare &operator=(const key_compare &x)
    {  this->base_t::get() = x;   return *this;  }
 
    BOOST_INTRUSIVE_FORCEINLINE const key_compare &key_comp() const
    {  return static_cast<const key_compare &>(*this);  }
 
-   BOOST_INTRUSIVE_FORCEINLINE key_compare &key_comp()
-   {  return static_cast<key_compare &>(*this);  }
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const
+   {  return this->key_comp()(key1, key2);  }
+
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()(const value_type &value1, const value_type &value2) const
+   {  return this->key_comp()(KeyOfValue()(value1), KeyOfValue()(value2));  }
+
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()(const key_type &key1, const value_type &value2) const
+   {  return this->key_comp()(key1, KeyOfValue()(value2));  }
+
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()(const value_type &value1, const key_type &key2) const
+   {  return this->key_comp()(KeyOfValue()(value1), key2);  }
 
    template<class U>
-   struct is_key
-      : boost::intrusive::detail::is_same<const U, const key_type>
-   {};
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()( const key_type &key1, const U &nonkey2
+                                              , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+   {  return this->key_comp()(key1, nonkey2);  }
 
    template<class U>
-   const key_type & key_forward
-      (const U &key, typename boost::intrusive::detail::enable_if<is_key<U> >::type* = 0) const
-   {  return key; }
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()( const U &nonkey1, const key_type &key2
+                                              , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+   {  return this->key_comp()(nonkey1, key2);  }
 
    template<class U>
-   BOOST_INTRUSIVE_FORCEINLINE const key_type & key_forward
-      (const U &key, typename boost::intrusive::detail::disable_if<is_key<U> >::type* = 0) const
-   {  return KeyOfValue()(key);  }
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()( const value_type &value1, const U &nonvalue2
+                                              , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+   {  return this->key_comp()(KeyOfValue()(value1), nonvalue2);  }
 
-   template<class KeyType, class KeyType2>
-   BOOST_INTRUSIVE_FORCEINLINE bool operator()(const KeyType &key1, const KeyType2 &key2) const
-   {  return key_compare::operator()(this->key_forward(key1), this->key_forward(key2));  }
+   template<class U>
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()( const U &nonvalue1, const value_type &value2
+                                              , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+   {  return this->key_comp()(nonvalue1, KeyOfValue()(value2));  }
+};
 
-   template<class KeyType, class KeyType2>
-   BOOST_INTRUSIVE_FORCEINLINE bool operator()(const KeyType &key1, const KeyType2 &key2)
-   {  return key_compare::operator()(this->key_forward(key1), this->key_forward(key2));  }
+template<class ValuePtr, class KeyCompare, class KeyOfValue>
+struct tree_value_compare<ValuePtr, KeyCompare, KeyOfValue, true>
+   :  public boost::intrusive::detail::ebo_functor_holder<KeyCompare>
+{
+   typedef typename pointer_element<ValuePtr>::type   value_type;
+   typedef KeyCompare                                 key_compare;
+   typedef KeyOfValue                                 key_of_value;
+   typedef typename KeyOfValue::type                  key_type;
+
+   typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t;
+
+
+   BOOST_INTRUSIVE_FORCEINLINE tree_value_compare()
+      :  base_t()
+   {}
+
+   BOOST_INTRUSIVE_FORCEINLINE explicit tree_value_compare(const key_compare &kcomp)
+      :  base_t(kcomp)
+   {}
+
+   BOOST_INTRUSIVE_FORCEINLINE tree_value_compare (const tree_value_compare &x)
+      :  base_t(x.base_t::get())
+   {}
+
+   BOOST_INTRUSIVE_FORCEINLINE tree_value_compare &operator=(const tree_value_compare &x)
+   {  this->base_t::get() = x.base_t::get();   return *this;  }
+
+   BOOST_INTRUSIVE_FORCEINLINE tree_value_compare &operator=(const key_compare &x)
+   {  this->base_t::get() = x;   return *this;  }
+
+   BOOST_INTRUSIVE_FORCEINLINE const key_compare &key_comp() const
+   {  return static_cast<const key_compare &>(*this);  }
+
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const
+   {  return this->key_comp()(key1, key2);  }
+
+   template<class U>
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()( const key_type &key1, const U &nonkey2
+                                              , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+   {  return this->key_comp()(key1, nonkey2);  }
+
+   template<class U>
+   BOOST_INTRUSIVE_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2
+                                              , typename disable_if_smartref_to<U, ValuePtr>::type* = 0) const
+   {  return this->key_comp()(nonkey1, key2);  }
 };
 
 }  //namespace intrusive{