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 rbtree_node_clonerboost::intrusive::rbtree_node_cloner53 explicit rbtree_node_cloner(F f) 54 : base_t(f) 55 {} 56 operator ()boost::intrusive::rbtree_node_cloner57 BOOST_INTRUSIVE_FORCEINLINE node_ptr operator()(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 { return_typeboost::intrusive::detail::rbtree_node_checker::return_type80 return_type() : black_count_(0) {} 81 std::size_t black_count_; 82 }; 83 rbtree_node_checkerboost::intrusive::detail::rbtree_node_checker84 rbtree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker) 85 : base_checker_t(comp, extra_checker) 86 {} 87 operator ()boost::intrusive::detail::rbtree_node_checker88 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(node_ptr header1, node_ptr header2); 204 205 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 206 207 //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(node_ptr,node_ptr) swap_nodes(node_ptr node1,node_ptr node2)208 static void swap_nodes(node_ptr node1, 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(node_ptr,node_ptr,node_ptr,node_ptr) swap_nodes(node_ptr node1,node_ptr header1,node_ptr node2,node_ptr header2)218 static void swap_nodes(node_ptr node1, node_ptr header1, node_ptr node2, 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(node_ptr,node_ptr) replace_node(node_ptr node_to_be_replaced,node_ptr new_node)230 static void replace_node(node_ptr node_to_be_replaced, 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(node_ptr,node_ptr,node_ptr) replace_node(node_ptr node_to_be_replaced,node_ptr header,node_ptr new_node)238 static void replace_node(node_ptr node_to_be_replaced, node_ptr header, 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(node_ptr) unlink(const node_ptr & node)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(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(node_ptr) init_header(node_ptr header)276 BOOST_INTRUSIVE_FORCEINLINE static void init_header(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(node_ptr,node_ptr) erase(node_ptr header,node_ptr z)283 static node_ptr erase(node_ptr header, 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> transfer_unique(node_ptr header1,NodePtrCompare comp,node_ptr header2,node_ptr z)293 static bool transfer_unique 294 (node_ptr header1, NodePtrCompare comp, node_ptr header2, 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> transfer_equal(node_ptr header1,NodePtrCompare comp,node_ptr header2,node_ptr z)307 static void transfer_equal 308 (node_ptr header1, NodePtrCompare comp, node_ptr header2, 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&,node_ptr,Cloner,Disposer) 317 template <class Cloner, class Disposer> clone(const_node_ptr source_header,node_ptr target_header,Cloner cloner,Disposer disposer)318 static void clone 319 (const_node_ptr source_header, 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(node_ptr,node_ptr,NodePtrCompare) 363 template<class NodePtrCompare> insert_equal_upper_bound(node_ptr h,node_ptr new_node,NodePtrCompare comp)364 static node_ptr insert_equal_upper_bound 365 (node_ptr h, 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(node_ptr,node_ptr,NodePtrCompare) 373 template<class NodePtrCompare> insert_equal_lower_bound(node_ptr h,node_ptr new_node,NodePtrCompare comp)374 static node_ptr insert_equal_lower_bound 375 (node_ptr h, 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(node_ptr,node_ptr,node_ptr,NodePtrCompare) 383 template<class NodePtrCompare> insert_equal(node_ptr header,node_ptr hint,node_ptr new_node,NodePtrCompare comp)384 static node_ptr insert_equal 385 (node_ptr header, node_ptr hint, 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(node_ptr,node_ptr,node_ptr) insert_before(node_ptr header,node_ptr pos,node_ptr new_node)393 static node_ptr insert_before 394 (node_ptr header, node_ptr pos, 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(node_ptr,node_ptr) push_back(node_ptr header,node_ptr new_node)402 static void push_back(node_ptr header, 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(node_ptr,node_ptr) push_front(node_ptr header,node_ptr new_node)409 static void push_front(node_ptr header, 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_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_node_ptr header, 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(node_ptr,node_ptr,const insert_commit_data&) insert_unique_commit(node_ptr header,node_ptr new_value,const insert_commit_data & commit_data)430 static void insert_unique_commit 431 (node_ptr header, 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 is_header(const const_node_ptr & p)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 rebalance_after_erasure(node_ptr header,node_ptr z,const typename bstree_algo::data_for_rebalance & info)447 static void rebalance_after_erasure 448 ( node_ptr header, 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 rebalance_after_erasure_restore_invariants(node_ptr header,node_ptr x,node_ptr x_parent)464 static void rebalance_after_erasure_restore_invariants(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 rebalance_after_insertion(node_ptr header,node_ptr p)548 static void rebalance_after_insertion(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 623