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 avltree_node_clonerboost::intrusive::avltree_node_cloner45 BOOST_INTRUSIVE_FORCEINLINE avltree_node_cloner(F f) 46 : base_t(f) 47 {} 48 operator ()boost::intrusive::avltree_node_cloner49 BOOST_INTRUSIVE_FORCEINLINE 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 operator ()boost::intrusive::avltree_node_cloner56 BOOST_INTRUSIVE_FORCEINLINE 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 { return_typeboost::intrusive::detail::avltree_node_checker::return_type78 return_type() : height(0) {} 79 int height; 80 }; 81 avltree_node_checkerboost::intrusive::detail::avltree_node_checker82 avltree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker) 83 : base_checker_t(comp, extra_checker) 84 {} 85 operator ()boost::intrusive::detail::avltree_node_checker86 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(node_ptr header1, node_ptr header2); 180 181 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 182 183 //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(node_ptr,node_ptr) swap_nodes(node_ptr node1,node_ptr node2)184 static void swap_nodes(node_ptr node1, 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(node_ptr,node_ptr,node_ptr,node_ptr) swap_nodes(node_ptr node1,node_ptr header1,node_ptr node2,node_ptr header2)194 static void swap_nodes(node_ptr node1, node_ptr header1, node_ptr node2, 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(node_ptr,node_ptr) replace_node(node_ptr node_to_be_replaced,node_ptr new_node)206 static void replace_node(node_ptr node_to_be_replaced, 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(node_ptr,node_ptr,node_ptr) replace_node(node_ptr node_to_be_replaced,node_ptr header,node_ptr new_node)214 static void replace_node(node_ptr node_to_be_replaced, node_ptr header, 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(node_ptr) unlink(node_ptr node)221 static void unlink(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(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. init_header(node_ptr header)261 static void init_header(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(node_ptr,node_ptr) erase(node_ptr header,node_ptr z)268 static node_ptr erase(node_ptr header, 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> transfer_unique(node_ptr header1,NodePtrCompare comp,node_ptr header2,node_ptr z)278 static bool transfer_unique 279 (node_ptr header1, NodePtrCompare comp, node_ptr header2, 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> transfer_equal(node_ptr header1,NodePtrCompare comp,node_ptr header2,node_ptr z)292 static void transfer_equal 293 (node_ptr header1, NodePtrCompare comp, node_ptr header2, 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&,node_ptr,Cloner,Disposer) 302 template <class Cloner, class Disposer> clone(const const_node_ptr & source_header,node_ptr target_header,Cloner cloner,Disposer disposer)303 static void clone 304 (const const_node_ptr & source_header, 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(node_ptr,node_ptr,NodePtrCompare) 348 template<class NodePtrCompare> insert_equal_upper_bound(node_ptr h,node_ptr new_node,NodePtrCompare comp)349 static node_ptr insert_equal_upper_bound 350 (node_ptr h, 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(node_ptr,node_ptr,NodePtrCompare) 358 template<class NodePtrCompare> insert_equal_lower_bound(node_ptr h,node_ptr new_node,NodePtrCompare comp)359 static node_ptr insert_equal_lower_bound 360 (node_ptr h, 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(node_ptr,node_ptr,node_ptr,NodePtrCompare) 368 template<class NodePtrCompare> insert_equal(node_ptr header,node_ptr hint,node_ptr new_node,NodePtrCompare comp)369 static node_ptr insert_equal 370 (node_ptr header, node_ptr hint, 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(node_ptr,node_ptr,node_ptr) insert_before(node_ptr header,node_ptr pos,node_ptr new_node)378 static node_ptr insert_before 379 (node_ptr header, node_ptr pos, 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(node_ptr,node_ptr) push_back(node_ptr header,node_ptr new_node)387 static void push_back(node_ptr header, 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(node_ptr,node_ptr) push_front(node_ptr header,node_ptr new_node)394 static void push_front(node_ptr header, 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(node_ptr,node_ptr,const insert_commit_data &) insert_unique_commit(node_ptr header,node_ptr new_value,const insert_commit_data & commit_data)415 static void insert_unique_commit 416 (node_ptr header, 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 is_header(const const_node_ptr & p)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 verify(const node_ptr & header)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 verify_recursion(node_ptr n,std::size_t & count,std::size_t & height)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 rebalance_after_erasure(node_ptr header,node_ptr z,const typename bstree_algo::data_for_rebalance & info)485 static void rebalance_after_erasure 486 ( node_ptr header, 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 rebalance_after_erasure_restore_invariants(node_ptr header,node_ptr x,node_ptr x_parent)495 static void rebalance_after_erasure_restore_invariants(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 rebalance_after_insertion(node_ptr header,node_ptr x)563 static void rebalance_after_insertion(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 left_right_balancing(node_ptr a,node_ptr b,node_ptr c)608 static void left_right_balancing(node_ptr a, node_ptr b, 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 avl_rotate_left_right(const node_ptr a,const node_ptr a_oldleft,node_ptr hdr)633 static node_ptr avl_rotate_left_right(const node_ptr a, const node_ptr a_oldleft, 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 avl_rotate_right_left(const node_ptr a,const node_ptr a_oldright,node_ptr hdr)653 static node_ptr avl_rotate_right_left(const node_ptr a, const node_ptr a_oldright, 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 avl_rotate_left(node_ptr x,node_ptr x_oldright,node_ptr hdr)673 static void avl_rotate_left(node_ptr x, node_ptr x_oldright, 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 avl_rotate_right(node_ptr x,node_ptr x_oldleft,node_ptr hdr)688 static void avl_rotate_right(node_ptr x, node_ptr x_oldleft, 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 728