ceph/src/boost/libs/intrusive/include/boost/intrusive/rbtree_algorithms.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Olaf Krzikalla 2004-2006.
   4 // (C) Copyright Ion Gaztanaga  2006-2014.
   5 //
   6 // Distributed under the Boost Software License, Version 1.0.
   7 //    (See accompanying file LICENSE_1_0.txt or copy at
   8 //          http://www.boost.org/LICENSE_1_0.txt)
   9 //
  10 // See http://www.boost.org/libs/intrusive for documentation.
  11 //
  12 /////////////////////////////////////////////////////////////////////////////
  13 //
  14 // The tree destruction algorithm is based on Julienne Walker and The EC Team code:
  15 //
  16 // This code is in the public domain. Anyone may use it or change it in any way that
  17 // they see fit. The author assumes no responsibility for damages incurred through
  18 // use of the original code or any variations thereof.
  19 //
  20 // It is requested, but not required, that due credit is given to the original author
  21 // and anyone who has modified the code through a header comment, such as this one.
  22
  23 #ifndef BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP
  24 #define BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP
  25
  26 #include <boost/intrusive/detail/config_begin.hpp>
  27 #include <boost/intrusive/intrusive_fwd.hpp>
  28
  29 #include <cstddef>
  30
  31 #include <boost/intrusive/detail/assert.hpp>
  32 #include <boost/intrusive/detail/algo_type.hpp>
  33 #include <boost/intrusive/bstree_algorithms.hpp>
  34 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
  35
  36 #if defined(BOOST_HAS_PRAGMA_ONCE)
  37 #  pragma once
  38 #endif
  39
  40 namespace boost {
  41 namespace intrusive {
  42
  43 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
  44
  45 template<class NodeTraits, class F>
  46 struct rbtree_node_cloner
  47    //Use public inheritance to avoid MSVC bugs with closures
  48    :  public detail::ebo_functor_holder<F>
  49 {
  50    typedef typename NodeTraits::node_ptr  node_ptr;
  51    typedef detail::ebo_functor_holder<F>  base_t;
  52
  53    explicit rbtree_node_cloner(F f)
  54       :  base_t(f)
  55    {}
  56
  57    node_ptr operator()(const node_ptr & p)
  58    {
  59       node_ptr n = base_t::get()(p);
  60       NodeTraits::set_color(n, NodeTraits::get_color(p));
  61       return n;
  62    }
  63 };
  64
  65 namespace detail {
  66
  67 template<class ValueTraits, class NodePtrCompare, class ExtraChecker>
  68 struct rbtree_node_checker
  69    : public bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker>
  70 {
  71    typedef bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> base_checker_t;
  72    typedef ValueTraits                             value_traits;
  73    typedef typename value_traits::node_traits      node_traits;
  74    typedef typename node_traits::const_node_ptr    const_node_ptr;
  75    typedef typename node_traits::node_ptr          node_ptr;
  76
  77    struct return_type
  78          : public base_checker_t::return_type
  79    {
  80       return_type() : black_count_(0) {}
  81       std::size_t black_count_;
  82    };
  83
  84    rbtree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker)
  85       : base_checker_t(comp, extra_checker)
  86    {}
  87
  88    void operator () (const const_node_ptr& p,
  89                      const return_type& check_return_left, const return_type& check_return_right,
  90                      return_type& check_return)
  91    {
  92
  93       if (node_traits::get_color(p) == node_traits::red()){
  94          //Red nodes have black children
  95          const node_ptr p_left(node_traits::get_left(p));   (void)p_left;
  96          const node_ptr p_right(node_traits::get_right(p)); (void)p_right;
  97          BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_left  || node_traits::get_color(p_left)  == node_traits::black());
  98          BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_right || node_traits::get_color(p_right) == node_traits::black());
  99          //Red node can't be root
 100          BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_parent(node_traits::get_parent(p)) != p);
 101       }
 102       //Every path to p contains the same number of black nodes
 103       const std::size_t l_black_count = check_return_left.black_count_;
 104       BOOST_INTRUSIVE_INVARIANT_ASSERT(l_black_count == check_return_right.black_count_);
 105       check_return.black_count_ = l_black_count +
 106          static_cast<std::size_t>(node_traits::get_color(p) == node_traits::black());
 107       base_checker_t::operator()(p, check_return_left, check_return_right, check_return);
 108    }
 109 };
 110
 111 } // namespace detail
 112
 113 #endif   //#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 114
 115 //! rbtree_algorithms provides basic algorithms to manipulate
 116 //! nodes forming a red-black tree. The insertion and deletion algorithms are
 117 //! based on those in Cormen, Leiserson, and Rivest, Introduction to Algorithms
 118 //! (MIT Press, 1990), except that
 119 //!
 120 //! (1) the header node is maintained with links not only to the root
 121 //! but also to the leftmost node of the tree, to enable constant time
 122 //! begin(), and to the rightmost node of the tree, to enable linear time
 123 //! performance when used with the generic set algorithms (set_union,
 124 //! etc.);
 125 //!
 126 //! (2) when a node being deleted has two children its successor node is
 127 //! relinked into its place, rather than copied, so that the only
 128 //! pointers invalidated are those referring to the deleted node.
 129 //!
 130 //! rbtree_algorithms is configured with a NodeTraits class, which encapsulates the
 131 //! information about the node to be manipulated. NodeTraits must support the
 132 //! following interface:
 133 //!
 134 //! <b>Typedefs</b>:
 135 //!
 136 //! <tt>node</tt>: The type of the node that forms the binary search tree
 137 //!
 138 //! <tt>node_ptr</tt>: A pointer to a node
 139 //!
 140 //! <tt>const_node_ptr</tt>: A pointer to a const node
 141 //!
 142 //! <tt>color</tt>: The type that can store the color of a node
 143 //!
 144 //! <b>Static functions</b>:
 145 //!
 146 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt>
 147 //!
 148 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>
 149 //!
 150 //! <tt>static node_ptr get_left(const_node_ptr n);</tt>
 151 //!
 152 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt>
 153 //!
 154 //! <tt>static node_ptr get_right(const_node_ptr n);</tt>
 155 //!
 156 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt>
 157 //!
 158 //! <tt>static color get_color(const_node_ptr n);</tt>
 159 //!
 160 //! <tt>static void set_color(node_ptr n, color c);</tt>
 161 //!
 162 //! <tt>static color black();</tt>
 163 //!
 164 //! <tt>static color red();</tt>
 165 template<class NodeTraits>
 166 class rbtree_algorithms
 167    #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 168    : public bstree_algorithms<NodeTraits>
 169    #endif
 170 {
 171    public:
 172    typedef NodeTraits                           node_traits;
 173    typedef typename NodeTraits::node            node;
 174    typedef typename NodeTraits::node_ptr        node_ptr;
 175    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
 176    typedef typename NodeTraits::color           color;
 177
 178    /// @cond
 179    private:
 180
 181    typedef bstree_algorithms<NodeTraits>  bstree_algo;
 182
 183    /// @endcond
 184
 185    public:
 186
 187    //! This type is the information that will be
 188    //! filled by insert_unique_check
 189    typedef typename bstree_algo::insert_commit_data insert_commit_data;
 190
 191    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 192
 193    //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&)
 194    static node_ptr get_header(const const_node_ptr & n);
 195
 196    //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node
 197    static node_ptr begin_node(const const_node_ptr & header);
 198
 199    //! @copydoc ::boost::intrusive::bstree_algorithms::end_node
 200    static node_ptr end_node(const const_node_ptr & header);
 201
 202    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree
 203    static void swap_tree(const node_ptr & header1, const node_ptr & header2);
 204
 205    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 206
 207    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&)
 208    static void swap_nodes(const node_ptr & node1, const node_ptr & node2)
 209    {
 210       if(node1 == node2)
 211          return;
 212
 213       node_ptr header1(bstree_algo::get_header(node1)), header2(bstree_algo::get_header(node2));
 214       swap_nodes(node1, header1, node2, header2);
 215    }
 216
 217    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&,const node_ptr&,const node_ptr&)
 218    static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2)
 219    {
 220       if(node1 == node2)   return;
 221
 222       bstree_algo::swap_nodes(node1, header1, node2, header2);
 223       //Swap color
 224       color c = NodeTraits::get_color(node1);
 225       NodeTraits::set_color(node1, NodeTraits::get_color(node2));
 226       NodeTraits::set_color(node2, c);
 227    }
 228
 229    //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&)
 230    static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node)
 231    {
 232       if(node_to_be_replaced == new_node)
 233          return;
 234       replace_node(node_to_be_replaced, bstree_algo::get_header(node_to_be_replaced), new_node);
 235    }
 236
 237    //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&)
 238    static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node)
 239    {
 240       bstree_algo::replace_node(node_to_be_replaced, header, new_node);
 241       NodeTraits::set_color(new_node, NodeTraits::get_color(node_to_be_replaced));
 242    }
 243
 244    //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(const node_ptr&)
 245    static void unlink(const node_ptr& node)
 246    {
 247       node_ptr x = NodeTraits::get_parent(node);
 248       if(x){
 249          while(!is_header(x))
 250             x = NodeTraits::get_parent(x);
 251          erase(x, node);
 252       }
 253    }
 254
 255    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 256    //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance
 257    static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header);
 258
 259    //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&)
 260    static bool unique(const const_node_ptr & node);
 261
 262    //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&)
 263    static std::size_t size(const const_node_ptr & header);
 264
 265    //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&)
 266    static node_ptr next_node(const node_ptr & node);
 267
 268    //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&)
 269    static node_ptr prev_node(const node_ptr & node);
 270
 271    //! @copydoc ::boost::intrusive::bstree_algorithms::init(const node_ptr&)
 272    static void init(const node_ptr & node);
 273    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 274
 275    //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(const node_ptr&)
 276    static void init_header(const node_ptr & header)
 277    {
 278       bstree_algo::init_header(header);
 279       NodeTraits::set_color(header, NodeTraits::red());
 280    }
 281
 282    //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&)
 283    static node_ptr erase(const node_ptr & header, const node_ptr & z)
 284    {
 285       typename bstree_algo::data_for_rebalance info;
 286       bstree_algo::erase(header, z, info);
 287       rebalance_after_erasure(header, z, info);
 288       return z;
 289    }
 290
 291    //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique
 292    template<class NodePtrCompare>
 293    static bool transfer_unique
 294       (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
 295    {
 296       typename bstree_algo::data_for_rebalance info;
 297       bool const transferred = bstree_algo::transfer_unique(header1, comp, header2, z, info);
 298       if(transferred){
 299          rebalance_after_erasure(header2, z, info);
 300          rebalance_after_insertion(header1, z);
 301       }
 302       return transferred;
 303    }
 304
 305    //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal
 306    template<class NodePtrCompare>
 307    static void transfer_equal
 308       (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
 309    {
 310       typename bstree_algo::data_for_rebalance info;
 311       bstree_algo::transfer_equal(header1, comp, header2, z, info);
 312       rebalance_after_erasure(header2, z, info);
 313       rebalance_after_insertion(header1, z);
 314    }
 315
 316    //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer)
 317    template <class Cloner, class Disposer>
 318    static void clone
 319       (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer)
 320    {
 321       rbtree_node_cloner<NodeTraits, Cloner> new_cloner(cloner);
 322       bstree_algo::clone(source_header, target_header, new_cloner, disposer);
 323    }
 324
 325    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 326    //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer)
 327    template<class Disposer>
 328    static void clear_and_dispose(const node_ptr & header, Disposer disposer);
 329
 330    //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
 331    template<class KeyType, class KeyNodePtrCompare>
 332    static node_ptr lower_bound
 333       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp);
 334
 335    //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
 336    template<class KeyType, class KeyNodePtrCompare>
 337    static node_ptr upper_bound
 338       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp);
 339
 340    //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare)
 341    template<class KeyType, class KeyNodePtrCompare>
 342    static node_ptr find
 343       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp);
 344
 345    //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
 346    template<class KeyType, class KeyNodePtrCompare>
 347    static std::pair<node_ptr, node_ptr> equal_range
 348       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp);
 349
 350    //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool)
 351    template<class KeyType, class KeyNodePtrCompare>
 352    static std::pair<node_ptr, node_ptr> bounded_range
 353       (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
 354       , bool left_closed, bool right_closed);
 355
 356    //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
 357    template<class KeyType, class KeyNodePtrCompare>
 358    static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp);
 359
 360    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 361
 362    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare)
 363    template<class NodePtrCompare>
 364    static node_ptr insert_equal_upper_bound
 365       (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp)
 366    {
 367       bstree_algo::insert_equal_upper_bound(h, new_node, comp);
 368       rebalance_after_insertion(h, new_node);
 369       return new_node;
 370    }
 371
 372    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare)
 373    template<class NodePtrCompare>
 374    static node_ptr insert_equal_lower_bound
 375       (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp)
 376    {
 377       bstree_algo::insert_equal_lower_bound(h, new_node, comp);
 378       rebalance_after_insertion(h, new_node);
 379       return new_node;
 380    }
 381
 382    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare)
 383    template<class NodePtrCompare>
 384    static node_ptr insert_equal
 385       (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp)
 386    {
 387       bstree_algo::insert_equal(header, hint, new_node, comp);
 388       rebalance_after_insertion(header, new_node);
 389       return new_node;
 390    }
 391
 392    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&)
 393    static node_ptr insert_before
 394       (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node)
 395    {
 396       bstree_algo::insert_before(header, pos, new_node);
 397       rebalance_after_insertion(header, new_node);
 398       return new_node;
 399    }
 400
 401    //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&)
 402    static void push_back(const node_ptr & header, const node_ptr & new_node)
 403    {
 404       bstree_algo::push_back(header, new_node);
 405       rebalance_after_insertion(header, new_node);
 406    }
 407
 408    //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&)
 409    static void push_front(const node_ptr & header, const node_ptr & new_node)
 410    {
 411       bstree_algo::push_front(header, new_node);
 412       rebalance_after_insertion(header, new_node);
 413    }
 414
 415    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 416    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&)
 417    template<class KeyType, class KeyNodePtrCompare>
 418    static std::pair<node_ptr, bool> insert_unique_check
 419       (const const_node_ptr & header,  const KeyType &key
 420       ,KeyNodePtrCompare comp, insert_commit_data &commit_data);
 421
 422    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&)
 423    template<class KeyType, class KeyNodePtrCompare>
 424    static std::pair<node_ptr, bool> insert_unique_check
 425       (const const_node_ptr & header, const node_ptr &hint, const KeyType &key
 426       ,KeyNodePtrCompare comp, insert_commit_data &commit_data);
 427    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 428
 429    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data&)
 430    static void insert_unique_commit
 431       (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data)
 432    {
 433       bstree_algo::insert_unique_commit(header, new_value, commit_data);
 434       rebalance_after_insertion(header, new_value);
 435    }
 436
 437    //! @copydoc ::boost::intrusive::bstree_algorithms::is_header
 438    static bool is_header(const const_node_ptr & p)
 439    {
 440       return NodeTraits::get_color(p) == NodeTraits::red() &&
 441             bstree_algo::is_header(p);
 442    }
 443
 444    /// @cond
 445    private:
 446
 447    static void rebalance_after_erasure
 448       ( const node_ptr & header, const node_ptr &z, const typename bstree_algo::data_for_rebalance &info)
 449    {
 450       color new_z_color;
 451       if(info.y != z){
 452          new_z_color = NodeTraits::get_color(info.y);
 453          NodeTraits::set_color(info.y, NodeTraits::get_color(z));
 454       }
 455       else{
 456          new_z_color = NodeTraits::get_color(z);
 457       }
 458       //Rebalance rbtree if needed
 459       if(new_z_color != NodeTraits::red()){
 460          rebalance_after_erasure_restore_invariants(header, info.x, info.x_parent);
 461       }
 462    }
 463
 464    static void rebalance_after_erasure_restore_invariants(const node_ptr & header, node_ptr x, node_ptr x_parent)
 465    {
 466       while(1){
 467          if(x_parent == header || (x && NodeTraits::get_color(x) != NodeTraits::black())){
 468             break;
 469          }
 470          //Don't cache x_is_leftchild or similar because x can be null and
 471          //equal to both x_parent_left and x_parent_right
 472          const node_ptr x_parent_left(NodeTraits::get_left(x_parent));
 473          if(x == x_parent_left){ //x is left child
 474             node_ptr w = NodeTraits::get_right(x_parent);
 475             BOOST_INTRUSIVE_INVARIANT_ASSERT(w);
 476             if(NodeTraits::get_color(w) == NodeTraits::red()){
 477                NodeTraits::set_color(w, NodeTraits::black());
 478                NodeTraits::set_color(x_parent, NodeTraits::red());
 479                bstree_algo::rotate_left(x_parent, w, NodeTraits::get_parent(x_parent), header);
 480                w = NodeTraits::get_right(x_parent);
 481                BOOST_INTRUSIVE_INVARIANT_ASSERT(w);
 482             }
 483             node_ptr const w_left (NodeTraits::get_left(w));
 484             node_ptr const w_right(NodeTraits::get_right(w));
 485             if((!w_left  || NodeTraits::get_color(w_left)  == NodeTraits::black()) &&
 486                (!w_right || NodeTraits::get_color(w_right) == NodeTraits::black())){
 487                NodeTraits::set_color(w, NodeTraits::red());
 488                x = x_parent;
 489                x_parent = NodeTraits::get_parent(x_parent);
 490             }
 491             else {
 492                if(!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()){
 493                   NodeTraits::set_color(w_left, NodeTraits::black());
 494                   NodeTraits::set_color(w, NodeTraits::red());
 495                   bstree_algo::rotate_right(w, w_left, NodeTraits::get_parent(w), header);
 496                   w = NodeTraits::get_right(x_parent);
 497                   BOOST_INTRUSIVE_INVARIANT_ASSERT(w);
 498                }
 499                NodeTraits::set_color(w, NodeTraits::get_color(x_parent));
 500                NodeTraits::set_color(x_parent, NodeTraits::black());
 501                const node_ptr new_wright(NodeTraits::get_right(w));
 502                if(new_wright)
 503                   NodeTraits::set_color(new_wright, NodeTraits::black());
 504                bstree_algo::rotate_left(x_parent, NodeTraits::get_right(x_parent), NodeTraits::get_parent(x_parent), header);
 505                break;
 506             }
 507          }
 508          else {
 509             // same as above, with right_ <-> left_.
 510             node_ptr w = x_parent_left;
 511             if(NodeTraits::get_color(w) == NodeTraits::red()){
 512                NodeTraits::set_color(w, NodeTraits::black());
 513                NodeTraits::set_color(x_parent, NodeTraits::red());
 514                bstree_algo::rotate_right(x_parent, w, NodeTraits::get_parent(x_parent), header);
 515                w = NodeTraits::get_left(x_parent);
 516                BOOST_INTRUSIVE_INVARIANT_ASSERT(w);
 517             }
 518             node_ptr const w_left (NodeTraits::get_left(w));
 519             node_ptr const w_right(NodeTraits::get_right(w));
 520             if((!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()) &&
 521                (!w_left  || NodeTraits::get_color(w_left)  == NodeTraits::black())){
 522                NodeTraits::set_color(w, NodeTraits::red());
 523                x = x_parent;
 524                x_parent = NodeTraits::get_parent(x_parent);
 525             }
 526             else {
 527                if(!w_left || NodeTraits::get_color(w_left) == NodeTraits::black()){
 528                   NodeTraits::set_color(w_right, NodeTraits::black());
 529                   NodeTraits::set_color(w, NodeTraits::red());
 530                   bstree_algo::rotate_left(w, w_right, NodeTraits::get_parent(w), header);
 531                   w = NodeTraits::get_left(x_parent);
 532                   BOOST_INTRUSIVE_INVARIANT_ASSERT(w);
 533                }
 534                NodeTraits::set_color(w, NodeTraits::get_color(x_parent));
 535                NodeTraits::set_color(x_parent, NodeTraits::black());
 536                const node_ptr new_wleft(NodeTraits::get_left(w));
 537                if(new_wleft)
 538                   NodeTraits::set_color(new_wleft, NodeTraits::black());
 539                bstree_algo::rotate_right(x_parent, NodeTraits::get_left(x_parent), NodeTraits::get_parent(x_parent), header);
 540                break;
 541             }
 542          }
 543       }
 544       if(x)
 545          NodeTraits::set_color(x, NodeTraits::black());
 546    }
 547
 548    static void rebalance_after_insertion(const node_ptr & header, node_ptr p)
 549    {
 550       NodeTraits::set_color(p, NodeTraits::red());
 551       while(1){
 552          node_ptr p_parent(NodeTraits::get_parent(p));
 553          const node_ptr p_grandparent(NodeTraits::get_parent(p_parent));
 554          if(p_parent == header || NodeTraits::get_color(p_parent) == NodeTraits::black() || p_grandparent == header){
 555             break;
 556          }
 557
 558          NodeTraits::set_color(p_grandparent, NodeTraits::red());
 559          node_ptr const p_grandparent_left (NodeTraits::get_left (p_grandparent));
 560          bool const p_parent_is_left_child = p_parent == p_grandparent_left;
 561          node_ptr const x(p_parent_is_left_child ? NodeTraits::get_right(p_grandparent) : p_grandparent_left);
 562
 563          if(x && NodeTraits::get_color(x) == NodeTraits::red()){
 564             NodeTraits::set_color(x, NodeTraits::black());
 565             NodeTraits::set_color(p_parent, NodeTraits::black());
 566             p = p_grandparent;
 567          }
 568          else{ //Final step
 569             const bool p_is_left_child(NodeTraits::get_left(p_parent) == p);
 570             if(p_parent_is_left_child){ //p_parent is left child
 571                if(!p_is_left_child){ //p is right child
 572                   bstree_algo::rotate_left_no_parent_fix(p_parent, p);
 573                   //No need to link p and p_grandparent:
 574                   //    [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_left(p_grandparent, p)]
 575                   //as p_grandparent is not the header, another rotation is coming and p_parent
 576                   //will be the left child of p_grandparent
 577                   p_parent = p;
 578                }
 579                bstree_algo::rotate_right(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header);
 580             }
 581             else{  //p_parent is right child
 582                if(p_is_left_child){ //p is left child
 583                   bstree_algo::rotate_right_no_parent_fix(p_parent, p);
 584                   //No need to link p and p_grandparent:
 585                   //    [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_right(p_grandparent, p)]
 586                   //as p_grandparent is not the header, another rotation is coming and p_parent
 587                   //will be the right child of p_grandparent
 588                   p_parent = p;
 589                }
 590                bstree_algo::rotate_left(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header);
 591             }
 592             NodeTraits::set_color(p_parent, NodeTraits::black());
 593             break;
 594          }
 595       }
 596       NodeTraits::set_color(NodeTraits::get_parent(header), NodeTraits::black());
 597    }
 598    /// @endcond
 599 };
 600
 601 /// @cond
 602
 603 template<class NodeTraits>
 604 struct get_algo<RbTreeAlgorithms, NodeTraits>
 605 {
 606    typedef rbtree_algorithms<NodeTraits> type;
 607 };
 608
 609 template <class ValueTraits, class NodePtrCompare, class ExtraChecker>
 610 struct get_node_checker<RbTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker>
 611 {
 612     typedef detail::rbtree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type;
 613 };
 614
 615 /// @endcond
 616
 617 } //namespace intrusive
 618 } //namespace boost
 619
 620 #include <boost/intrusive/detail/config_end.hpp>
 621
 622 #endif //BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP