1 files changed, 29 insertions, 14 deletions

diff --git a/boost/intrusive/rbtree_algorithms.hpp b/boost/intrusive/rbtree_algorithms.hpp
index 376deaf312..ad9c7658e3 100644
--- a/boost/intrusive/rbtree_algorithms.hpp
+++ b/boost/intrusive/rbtree_algorithms.hpp
@@ -23,10 +23,6 @@
 #ifndef BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP
 #define BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP
 
-#if defined(_MSC_VER)
-#  pragma once
-#endif
-
 #include <boost/intrusive/detail/config_begin.hpp>
 #include <boost/intrusive/intrusive_fwd.hpp>
 
@@ -37,6 +33,10 @@
 #include <boost/intrusive/bstree_algorithms.hpp>
 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
 
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#  pragma once
+#endif
+
 namespace boost {
 namespace intrusive {
 
@@ -44,12 +44,13 @@ namespace intrusive {
 
 template<class NodeTraits, class F>
 struct rbtree_node_cloner
-   :  private detail::ebo_functor_holder<F>
+   //Use public inheritance to avoid MSVC bugs with closures
+   :  public detail::ebo_functor_holder<F>
 {
    typedef typename NodeTraits::node_ptr  node_ptr;
    typedef detail::ebo_functor_holder<F>  base_t;
 
-   rbtree_node_cloner(F f)
+   explicit rbtree_node_cloner(F f)
       :  base_t(f)
    {}
 
@@ -71,8 +72,14 @@ struct rbtree_node_checker
    typedef ValueTraits                             value_traits;
    typedef typename value_traits::node_traits      node_traits;
    typedef typename node_traits::const_node_ptr    const_node_ptr;
+   typedef typename node_traits::node_ptr          node_ptr;
 
-   typedef typename base_checker_t::return_type    return_type;
+   struct return_type
+         : public base_checker_t::return_type
+   {
+      return_type() : black_count_(0) {}
+      std::size_t black_count_;
+   };
 
    rbtree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker)
       : base_checker_t(comp, extra_checker)
@@ -82,13 +89,21 @@ struct rbtree_node_checker
                      const return_type& check_return_left, const return_type& check_return_right,
                      return_type& check_return)
    {
-      if (node_traits::get_color(p) == node_traits::red())
-      {
-         if (node_traits::get_left(p))
-            BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_color(node_traits::get_left(p)) == node_traits::black());
-         if (node_traits::get_right(p))
-            BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_color(node_traits::get_right(p)) == node_traits::black());
+
+      if (node_traits::get_color(p) == node_traits::red()){
+         //Red nodes have black children
+         const node_ptr p_left(node_traits::get_left(p));
+         const node_ptr p_right(node_traits::get_right(p));
+         BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_left  || node_traits::get_color(p_left)  == node_traits::black());
+         BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_right || node_traits::get_color(p_right) == node_traits::black());
+         //Red node can't be root
+         BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_parent(node_traits::get_parent(p)) != p);
       }
+      //Every path to p contains the same number of black nodes
+      const std::size_t l_black_count = check_return_left.black_count_;
+      BOOST_INTRUSIVE_INVARIANT_ASSERT(l_black_count == check_return_right.black_count_);
+      check_return.black_count_ = l_black_count +
+         static_cast<std::size_t>(node_traits::get_color(p) == node_traits::black());
       base_checker_t::operator()(p, check_return_left, check_return_right, check_return);
    }
 };
@@ -186,7 +201,7 @@ class rbtree_algorithms
 
    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree
    static void swap_tree(const node_ptr & header1, const node_ptr & header2);
-   
+
    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 
    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&)