ceph/src/boost/boost/intrusive/avltree_algorithms.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Daniel K. O. 2005.
   4 // (C) Copyright Ion Gaztanaga 2007-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 #ifndef BOOST_INTRUSIVE_AVLTREE_ALGORITHMS_HPP
  15 #define BOOST_INTRUSIVE_AVLTREE_ALGORITHMS_HPP
  16
  17 #include <boost/intrusive/detail/config_begin.hpp>
  18 #include <boost/intrusive/intrusive_fwd.hpp>
  19
  20 #include <cstddef>
  21
  22 #include <boost/intrusive/detail/assert.hpp>
  23 #include <boost/intrusive/detail/algo_type.hpp>
  24 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
  25 #include <boost/intrusive/bstree_algorithms.hpp>
  26
  27 #if defined(BOOST_HAS_PRAGMA_ONCE)
  28 #  pragma once
  29 #endif
  30
  31
  32 namespace boost {
  33 namespace intrusive {
  34
  35 /// @cond
  36
  37 template<class NodeTraits, class F>
  38 struct avltree_node_cloner
  39    //Use public inheritance to avoid MSVC bugs with closures
  40    :  public detail::ebo_functor_holder<F>
  41 {
  42    typedef typename NodeTraits::node_ptr  node_ptr;
  43    typedef detail::ebo_functor_holder<F>  base_t;
  44
  45    avltree_node_cloner(F f)
  46       :  base_t(f)
  47    {}
  48
  49    node_ptr operator()(const node_ptr & p)
  50    {
  51       node_ptr n = base_t::get()(p);
  52       NodeTraits::set_balance(n, NodeTraits::get_balance(p));
  53       return n;
  54    }
  55
  56    node_ptr operator()(const node_ptr & p) const
  57    {
  58       node_ptr n = base_t::get()(p);
  59       NodeTraits::set_balance(n, NodeTraits::get_balance(p));
  60       return n;
  61    }
  62 };
  63
  64 namespace detail {
  65
  66 template<class ValueTraits, class NodePtrCompare, class ExtraChecker>
  67 struct avltree_node_checker
  68       : public bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker>
  69 {
  70    typedef bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> base_checker_t;
  71    typedef ValueTraits                             value_traits;
  72    typedef typename value_traits::node_traits      node_traits;
  73    typedef typename node_traits::const_node_ptr    const_node_ptr;
  74
  75    struct return_type
  76          : public base_checker_t::return_type
  77    {
  78       return_type() : height(0) {}
  79       int height;
  80    };
  81
  82    avltree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker)
  83       : base_checker_t(comp, extra_checker)
  84    {}
  85
  86    void operator () (const const_node_ptr& p,
  87                      const return_type& check_return_left, const return_type& check_return_right,
  88                      return_type& check_return)
  89    {
  90       const int height_diff = check_return_right.height - check_return_left.height; (void)height_diff;
  91       BOOST_INTRUSIVE_INVARIANT_ASSERT(
  92          (height_diff == -1 && node_traits::get_balance(p) == node_traits::negative()) ||
  93          (height_diff ==  0 && node_traits::get_balance(p) == node_traits::zero()) ||
  94          (height_diff ==  1 && node_traits::get_balance(p) == node_traits::positive())
  95       );
  96       check_return.height = 1 +
  97          (check_return_left.height > check_return_right.height ? check_return_left.height : check_return_right.height);
  98       base_checker_t::operator()(p, check_return_left, check_return_right, check_return);
  99    }
 100 };
 101
 102 } // namespace detail
 103
 104 /// @endcond
 105
 106 //! avltree_algorithms is configured with a NodeTraits class, which encapsulates the
 107 //! information about the node to be manipulated. NodeTraits must support the
 108 //! following interface:
 109 //!
 110 //! <b>Typedefs</b>:
 111 //!
 112 //! <tt>node</tt>: The type of the node that forms the binary search tree
 113 //!
 114 //! <tt>node_ptr</tt>: A pointer to a node
 115 //!
 116 //! <tt>const_node_ptr</tt>: A pointer to a const node
 117 //!
 118 //! <tt>balance</tt>: The type of the balance factor
 119 //!
 120 //! <b>Static functions</b>:
 121 //!
 122 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt>
 123 //!
 124 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>
 125 //!
 126 //! <tt>static node_ptr get_left(const_node_ptr n);</tt>
 127 //!
 128 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt>
 129 //!
 130 //! <tt>static node_ptr get_right(const_node_ptr n);</tt>
 131 //!
 132 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt>
 133 //!
 134 //! <tt>static balance get_balance(const_node_ptr n);</tt>
 135 //!
 136 //! <tt>static void set_balance(node_ptr n, balance b);</tt>
 137 //!
 138 //! <tt>static balance negative();</tt>
 139 //!
 140 //! <tt>static balance zero();</tt>
 141 //!
 142 //! <tt>static balance positive();</tt>
 143 template<class NodeTraits>
 144 class avltree_algorithms
 145    #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 146    : public bstree_algorithms<NodeTraits>
 147    #endif
 148 {
 149    public:
 150    typedef typename NodeTraits::node            node;
 151    typedef NodeTraits                           node_traits;
 152    typedef typename NodeTraits::node_ptr        node_ptr;
 153    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
 154    typedef typename NodeTraits::balance         balance;
 155
 156    /// @cond
 157    private:
 158    typedef bstree_algorithms<NodeTraits>  bstree_algo;
 159
 160    /// @endcond
 161
 162    public:
 163    //! This type is the information that will be
 164    //! filled by insert_unique_check
 165    typedef typename bstree_algo::insert_commit_data insert_commit_data;
 166
 167    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 168
 169    //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&)
 170    static node_ptr get_header(const const_node_ptr & n);
 171
 172    //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node
 173    static node_ptr begin_node(const const_node_ptr & header);
 174
 175    //! @copydoc ::boost::intrusive::bstree_algorithms::end_node
 176    static node_ptr end_node(const const_node_ptr & header);
 177
 178    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree
 179    static void swap_tree(const node_ptr & header1, const node_ptr & header2);
 180
 181    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 182
 183    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&)
 184    static void swap_nodes(const node_ptr & node1, const node_ptr & node2)
 185    {
 186       if(node1 == node2)
 187          return;
 188
 189       node_ptr header1(bstree_algo::get_header(node1)), header2(bstree_algo::get_header(node2));
 190       swap_nodes(node1, header1, node2, header2);
 191    }
 192
 193    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&,const node_ptr&,const node_ptr&)
 194    static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2)
 195    {
 196       if(node1 == node2)   return;
 197
 198       bstree_algo::swap_nodes(node1, header1, node2, header2);
 199       //Swap balance
 200       balance c = NodeTraits::get_balance(node1);
 201       NodeTraits::set_balance(node1, NodeTraits::get_balance(node2));
 202       NodeTraits::set_balance(node2, c);
 203    }
 204
 205    //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&)
 206    static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node)
 207    {
 208       if(node_to_be_replaced == new_node)
 209          return;
 210       replace_node(node_to_be_replaced, bstree_algo::get_header(node_to_be_replaced), new_node);
 211    }
 212
 213    //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&)
 214    static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node)
 215    {
 216       bstree_algo::replace_node(node_to_be_replaced, header, new_node);
 217       NodeTraits::set_balance(new_node, NodeTraits::get_balance(node_to_be_replaced));
 218    }
 219
 220    //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(const node_ptr&)
 221    static void unlink(const node_ptr & node)
 222    {
 223       node_ptr x = NodeTraits::get_parent(node);
 224       if(x){
 225          while(!is_header(x))
 226             x = NodeTraits::get_parent(x);
 227          erase(x, node);
 228       }
 229    }
 230
 231    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 232    //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance
 233    static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header);
 234
 235    //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&)
 236    static bool unique(const const_node_ptr & node);
 237
 238    //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&)
 239    static std::size_t size(const const_node_ptr & header);
 240
 241    //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&)
 242    static node_ptr next_node(const node_ptr & node);
 243
 244    //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&)
 245    static node_ptr prev_node(const node_ptr & node);
 246
 247    //! @copydoc ::boost::intrusive::bstree_algorithms::init(const node_ptr&)
 248    static void init(const node_ptr & node);
 249    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 250
 251    //! <b>Requires</b>: node must not be part of any tree.
 252    //!
 253    //! <b>Effects</b>: Initializes the header to represent an empty tree.
 254    //!   unique(header) == true.
 255    //!
 256    //! <b>Complexity</b>: Constant.
 257    //!
 258    //! <b>Throws</b>: Nothing.
 259    //!
 260    //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
 261    static void init_header(const node_ptr & header)
 262    {
 263       bstree_algo::init_header(header);
 264       NodeTraits::set_balance(header, NodeTraits::zero());
 265    }
 266
 267    //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&)
 268    static node_ptr erase(const node_ptr & header, const node_ptr & z)
 269    {
 270       typename bstree_algo::data_for_rebalance info;
 271       bstree_algo::erase(header, z, info);
 272       rebalance_after_erasure(header, z, info);
 273       return z;
 274    }
 275
 276    //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique
 277    template<class NodePtrCompare>
 278    static bool transfer_unique
 279       (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
 280    {
 281       typename bstree_algo::data_for_rebalance info;
 282       bool const transferred = bstree_algo::transfer_unique(header1, comp, header2, z, info);
 283       if(transferred){
 284          rebalance_after_erasure(header2, z, info);
 285          rebalance_after_insertion(header1, z);
 286       }
 287       return transferred;
 288    }
 289
 290    //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal
 291    template<class NodePtrCompare>
 292    static void transfer_equal
 293       (const node_ptr & header1, NodePtrCompare comp, const node_ptr &header2, const node_ptr & z)
 294    {
 295       typename bstree_algo::data_for_rebalance info;
 296       bstree_algo::transfer_equal(header1, comp, header2, z, info);
 297       rebalance_after_erasure(header2, z, info);
 298       rebalance_after_insertion(header1, z);
 299    }
 300
 301    //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer)
 302    template <class Cloner, class Disposer>
 303    static void clone
 304       (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer)
 305    {
 306       avltree_node_cloner<NodeTraits, Cloner> new_cloner(cloner);
 307       bstree_algo::clone(source_header, target_header, new_cloner, disposer);
 308    }
 309
 310    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 311    //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer)
 312    template<class Disposer>
 313    static void clear_and_dispose(const node_ptr & header, Disposer disposer);
 314
 315    //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
 316    template<class KeyType, class KeyNodePtrCompare>
 317    static node_ptr lower_bound
 318       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp);
 319
 320    //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
 321    template<class KeyType, class KeyNodePtrCompare>
 322    static node_ptr upper_bound
 323       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp);
 324
 325    //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
 326    template<class KeyType, class KeyNodePtrCompare>
 327    static node_ptr find
 328       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp);
 329
 330    //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
 331    template<class KeyType, class KeyNodePtrCompare>
 332    static std::pair<node_ptr, node_ptr> equal_range
 333       (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp);
 334
 335    //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool)
 336    template<class KeyType, class KeyNodePtrCompare>
 337    static std::pair<node_ptr, node_ptr> bounded_range
 338       (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
 339       , bool left_closed, bool right_closed);
 340
 341    //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare)
 342    template<class KeyType, class KeyNodePtrCompare>
 343    static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp);
 344
 345    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 346
 347    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare)
 348    template<class NodePtrCompare>
 349    static node_ptr insert_equal_upper_bound
 350       (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp)
 351    {
 352       bstree_algo::insert_equal_upper_bound(h, new_node, comp);
 353       rebalance_after_insertion(h, new_node);
 354       return new_node;
 355    }
 356
 357    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare)
 358    template<class NodePtrCompare>
 359    static node_ptr insert_equal_lower_bound
 360       (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp)
 361    {
 362       bstree_algo::insert_equal_lower_bound(h, new_node, comp);
 363       rebalance_after_insertion(h, new_node);
 364       return new_node;
 365    }
 366
 367    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare)
 368    template<class NodePtrCompare>
 369    static node_ptr insert_equal
 370       (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp)
 371    {
 372       bstree_algo::insert_equal(header, hint, new_node, comp);
 373       rebalance_after_insertion(header, new_node);
 374       return new_node;
 375    }
 376
 377    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&)
 378    static node_ptr insert_before
 379       (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node)
 380    {
 381       bstree_algo::insert_before(header, pos, new_node);
 382       rebalance_after_insertion(header, new_node);
 383       return new_node;
 384    }
 385
 386    //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&)
 387    static void push_back(const node_ptr & header, const node_ptr & new_node)
 388    {
 389       bstree_algo::push_back(header, new_node);
 390       rebalance_after_insertion(header, new_node);
 391    }
 392
 393    //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&)
 394    static void push_front(const node_ptr & header, const node_ptr & new_node)
 395    {
 396       bstree_algo::push_front(header, new_node);
 397       rebalance_after_insertion(header, new_node);
 398    }
 399
 400    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 401    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&)
 402    template<class KeyType, class KeyNodePtrCompare>
 403    static std::pair<node_ptr, bool> insert_unique_check
 404       (const const_node_ptr & header,  const KeyType &key
 405       ,KeyNodePtrCompare comp, insert_commit_data &commit_data);
 406
 407    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&)
 408    template<class KeyType, class KeyNodePtrCompare>
 409    static std::pair<node_ptr, bool> insert_unique_check
 410       (const const_node_ptr & header, const node_ptr &hint, const KeyType &key
 411       ,KeyNodePtrCompare comp, insert_commit_data &commit_data);
 412    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 413
 414    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data &)
 415    static void insert_unique_commit
 416       (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data)
 417    {
 418       bstree_algo::insert_unique_commit(header, new_value, commit_data);
 419       rebalance_after_insertion(header, new_value);
 420    }
 421
 422    //! @copydoc ::boost::intrusive::bstree_algorithms::is_header
 423    static bool is_header(const const_node_ptr & p)
 424    {  return NodeTraits::get_balance(p) == NodeTraits::zero() && bstree_algo::is_header(p);  }
 425
 426
 427    /// @cond
 428    static bool verify(const node_ptr &header)
 429    {
 430       std::size_t height;
 431       std::size_t count;
 432       return verify_recursion(NodeTraits::get_parent(header), count, height);
 433    }
 434
 435    private:
 436
 437    static bool verify_recursion(node_ptr n, std::size_t &count, std::size_t &height)
 438    {
 439       if (!n){
 440          count = 0;
 441          height = 0;
 442          return true;
 443       }
 444       std::size_t leftcount, rightcount;
 445       std::size_t leftheight, rightheight;
 446       if(!verify_recursion(NodeTraits::get_left (n), leftcount,  leftheight) ||
 447          !verify_recursion(NodeTraits::get_right(n), rightcount, rightheight) ){
 448          return false;
 449       }
 450       count = 1u + leftcount + rightcount;
 451       height = 1u + (leftheight > rightheight ? leftheight : rightheight);
 452
 453       //If equal height, balance must be zero
 454       if(rightheight == leftheight){
 455          if(NodeTraits::get_balance(n) != NodeTraits::zero()){
 456             BOOST_ASSERT(0);
 457             return false;
 458          }
 459       }
 460       //If right is taller than left, then the difference must be at least 1 and the balance positive
 461       else if(rightheight > leftheight){
 462          if(rightheight - leftheight > 1 ){
 463             BOOST_ASSERT(0);
 464             return false;
 465          }
 466          else if(NodeTraits::get_balance(n) != NodeTraits::positive()){
 467             BOOST_ASSERT(0);
 468             return false;
 469          }
 470       }
 471       //If left is taller than right, then the difference must be at least 1 and the balance negative
 472       else{
 473          if(leftheight - rightheight > 1 ){
 474             BOOST_ASSERT(0);
 475             return false;
 476          }
 477          else if(NodeTraits::get_balance(n) != NodeTraits::negative()){
 478             BOOST_ASSERT(0);
 479             return false;
 480          }
 481       }
 482       return true;
 483    }
 484
 485    static void rebalance_after_erasure
 486       ( const node_ptr & header, const node_ptr &z, const typename bstree_algo::data_for_rebalance &info)
 487    {
 488       if(info.y != z){
 489          NodeTraits::set_balance(info.y, NodeTraits::get_balance(z));
 490       }
 491       //Rebalance avltree
 492       rebalance_after_erasure_restore_invariants(header, info.x, info.x_parent);
 493    }
 494
 495    static void rebalance_after_erasure_restore_invariants(const node_ptr & header, node_ptr x, node_ptr x_parent)
 496    {
 497       for ( node_ptr root = NodeTraits::get_parent(header)
 498           ; x != root
 499           ; root = NodeTraits::get_parent(header), x_parent = NodeTraits::get_parent(x)) {
 500          const balance x_parent_balance = NodeTraits::get_balance(x_parent);
 501          //Don't cache x_is_leftchild or similar because x can be null and
 502          //equal to both x_parent_left and x_parent_right
 503          const node_ptr x_parent_left (NodeTraits::get_left(x_parent));
 504          const node_ptr x_parent_right(NodeTraits::get_right(x_parent));
 505
 506          if(x_parent_balance == NodeTraits::zero()){
 507             NodeTraits::set_balance( x_parent, x == x_parent_right ? NodeTraits::negative() : NodeTraits::positive() );
 508             break;       // the height didn't change, let's stop here
 509          }
 510          else if(x_parent_balance == NodeTraits::negative()){
 511             if (x == x_parent_left) {  ////x is left child or x and sibling are null
 512                NodeTraits::set_balance(x_parent, NodeTraits::zero()); // balanced
 513                x = x_parent;
 514             }
 515             else {
 516                // x is right child (x_parent_left is the left child)
 517                BOOST_INTRUSIVE_INVARIANT_ASSERT(x_parent_left);
 518                if (NodeTraits::get_balance(x_parent_left) == NodeTraits::positive()) {
 519                   // x_parent_left MUST have a right child
 520                   BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(x_parent_left));
 521                   x = avl_rotate_left_right(x_parent, x_parent_left, header);
 522                }
 523                else {
 524                   avl_rotate_right(x_parent, x_parent_left, header);
 525                   x = x_parent_left;
 526                }
 527
 528                // if changed from negative to NodeTraits::positive(), no need to check above
 529                if (NodeTraits::get_balance(x) == NodeTraits::positive()){
 530                   break;
 531                }
 532             }
 533          }
 534          else if(x_parent_balance == NodeTraits::positive()){
 535             if (x == x_parent_right) { //x is right child or x and sibling are null
 536                NodeTraits::set_balance(x_parent, NodeTraits::zero()); // balanced
 537                x = x_parent;
 538             }
 539             else {
 540                // x is left child (x_parent_right is the right child)
 541                BOOST_INTRUSIVE_INVARIANT_ASSERT(x_parent_right);
 542                if (NodeTraits::get_balance(x_parent_right) == NodeTraits::negative()) {
 543                   // x_parent_right MUST have then a left child
 544                   BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(x_parent_right));
 545                   x = avl_rotate_right_left(x_parent, x_parent_right, header);
 546                }
 547                else {
 548                   avl_rotate_left(x_parent, x_parent_right, header);
 549                   x = x_parent_right;
 550                }
 551                // if changed from NodeTraits::positive() to negative, no need to check above
 552                if (NodeTraits::get_balance(x) == NodeTraits::negative()){
 553                   break;
 554                }
 555             }
 556          }
 557          else{
 558             BOOST_INTRUSIVE_INVARIANT_ASSERT(false);  // never reached
 559          }
 560       }
 561    }
 562
 563    static void rebalance_after_insertion(const node_ptr & header, node_ptr x)
 564    {
 565       NodeTraits::set_balance(x, NodeTraits::zero());
 566       // Rebalance.
 567       for(node_ptr root = NodeTraits::get_parent(header); x != root; root = NodeTraits::get_parent(header)){
 568          node_ptr const x_parent(NodeTraits::get_parent(x));
 569          node_ptr const x_parent_left(NodeTraits::get_left(x_parent));
 570          const balance x_parent_balance = NodeTraits::get_balance(x_parent);
 571          const bool x_is_leftchild(x == x_parent_left);
 572          if(x_parent_balance == NodeTraits::zero()){
 573             // if x is left, parent will have parent->bal_factor = negative
 574             // else, parent->bal_factor = NodeTraits::positive()
 575             NodeTraits::set_balance( x_parent, x_is_leftchild ? NodeTraits::negative() : NodeTraits::positive()  );
 576             x = x_parent;
 577          }
 578          else if(x_parent_balance == NodeTraits::positive()){
 579             // if x is a left child, parent->bal_factor = zero
 580             if (x_is_leftchild)
 581                NodeTraits::set_balance(x_parent, NodeTraits::zero());
 582             else{        // x is a right child, needs rebalancing
 583                if (NodeTraits::get_balance(x) == NodeTraits::negative())
 584                   avl_rotate_right_left(x_parent, x, header);
 585                else
 586                   avl_rotate_left(x_parent, x, header);
 587             }
 588             break;
 589          }
 590          else if(x_parent_balance == NodeTraits::negative()){
 591             // if x is a left child, needs rebalancing
 592             if (x_is_leftchild) {
 593                if (NodeTraits::get_balance(x) == NodeTraits::positive())
 594                   avl_rotate_left_right(x_parent, x, header);
 595                else
 596                   avl_rotate_right(x_parent, x, header);
 597             }
 598             else
 599                NodeTraits::set_balance(x_parent, NodeTraits::zero());
 600             break;
 601          }
 602          else{
 603             BOOST_INTRUSIVE_INVARIANT_ASSERT(false);  // never reached
 604          }
 605       }
 606    }
 607
 608    static void left_right_balancing(const node_ptr & a, const node_ptr & b, const node_ptr & c)
 609    {
 610       // balancing...
 611       const balance c_balance = NodeTraits::get_balance(c);
 612       const balance zero_balance = NodeTraits::zero();
 613       const balance posi_balance = NodeTraits::positive();
 614       const balance nega_balance = NodeTraits::negative();
 615       NodeTraits::set_balance(c, zero_balance);
 616       if(c_balance == nega_balance){
 617          NodeTraits::set_balance(a, posi_balance);
 618          NodeTraits::set_balance(b, zero_balance);
 619       }
 620       else if(c_balance == zero_balance){
 621          NodeTraits::set_balance(a, zero_balance);
 622          NodeTraits::set_balance(b, zero_balance);
 623       }
 624       else if(c_balance == posi_balance){
 625          NodeTraits::set_balance(a, zero_balance);
 626          NodeTraits::set_balance(b, nega_balance);
 627       }
 628       else{
 629          BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached
 630       }
 631    }
 632
 633    static node_ptr avl_rotate_left_right(const node_ptr a, const node_ptr a_oldleft, const node_ptr & hdr)
 634    {  // [note: 'a_oldleft' is 'b']
 635       //             |                               |         //
 636       //             a(-2)                           c         //
 637       //            / \                             / \        //
 638       //           /   \        ==>                /   \       //
 639       //      (pos)b    [g]                       b     a      //
 640       //          / \                            / \   / \     //
 641       //        [d]  c                         [d]  e f  [g]   //
 642       //            / \                                        //
 643       //           e   f                                       //
 644       const node_ptr c = NodeTraits::get_right(a_oldleft);
 645       bstree_algo::rotate_left_no_parent_fix(a_oldleft, c);
 646       //No need to link c with a [NodeTraits::set_parent(c, a) + NodeTraits::set_left(a, c)]
 647       //as c is not root and another rotation is coming
 648       bstree_algo::rotate_right(a, c, NodeTraits::get_parent(a), hdr);
 649       left_right_balancing(a, a_oldleft, c);
 650       return c;
 651    }
 652
 653    static node_ptr avl_rotate_right_left(const node_ptr a, const node_ptr a_oldright, const node_ptr & hdr)
 654    {  // [note: 'a_oldright' is 'b']
 655       //              |                               |           //
 656       //              a(pos)                          c           //
 657       //             / \                             / \          //
 658       //            /   \                           /   \         //
 659       //          [d]   b(neg)         ==>         a     b        //
 660       //               / \                        / \   / \       //
 661       //              c  [g]                    [d] e  f  [g]     //
 662       //             / \                                          //
 663       //            e   f                                         //
 664       const node_ptr c (NodeTraits::get_left(a_oldright));
 665       bstree_algo::rotate_right_no_parent_fix(a_oldright, c);
 666       //No need to link c with a [NodeTraits::set_parent(c, a) + NodeTraits::set_right(a, c)]
 667       //as c is not root and another rotation is coming.
 668       bstree_algo::rotate_left(a, c, NodeTraits::get_parent(a), hdr);
 669       left_right_balancing(a_oldright, a, c);
 670       return c;
 671    }
 672
 673    static void avl_rotate_left(const node_ptr &x, const node_ptr &x_oldright, const node_ptr & hdr)
 674    {
 675       bstree_algo::rotate_left(x, x_oldright, NodeTraits::get_parent(x), hdr);
 676
 677       // reset the balancing factor
 678       if (NodeTraits::get_balance(x_oldright) == NodeTraits::positive()) {
 679          NodeTraits::set_balance(x, NodeTraits::zero());
 680          NodeTraits::set_balance(x_oldright, NodeTraits::zero());
 681       }
 682       else {        // this doesn't happen during insertions
 683          NodeTraits::set_balance(x, NodeTraits::positive());
 684          NodeTraits::set_balance(x_oldright, NodeTraits::negative());
 685       }
 686    }
 687
 688    static void avl_rotate_right(const node_ptr &x, const node_ptr &x_oldleft, const node_ptr & hdr)
 689    {
 690       bstree_algo::rotate_right(x, x_oldleft, NodeTraits::get_parent(x), hdr);
 691
 692       // reset the balancing factor
 693       if (NodeTraits::get_balance(x_oldleft) == NodeTraits::negative()) {
 694          NodeTraits::set_balance(x, NodeTraits::zero());
 695          NodeTraits::set_balance(x_oldleft, NodeTraits::zero());
 696       }
 697       else {        // this doesn't happen during insertions
 698          NodeTraits::set_balance(x, NodeTraits::negative());
 699          NodeTraits::set_balance(x_oldleft, NodeTraits::positive());
 700       }
 701    }
 702
 703    /// @endcond
 704 };
 705
 706 /// @cond
 707
 708 template<class NodeTraits>
 709 struct get_algo<AvlTreeAlgorithms, NodeTraits>
 710 {
 711    typedef avltree_algorithms<NodeTraits> type;
 712 };
 713
 714 template <class ValueTraits, class NodePtrCompare, class ExtraChecker>
 715 struct get_node_checker<AvlTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker>
 716 {
 717    typedef detail::avltree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type;
 718 };
 719
 720 /// @endcond
 721
 722 } //namespace intrusive
 723 } //namespace boost
 724
 725 #include <boost/intrusive/detail/config_end.hpp>
 726
 727 #endif //BOOST_INTRUSIVE_AVLTREE_ALGORITHMS_HPP