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 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 { 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(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&) swap_nodes(const node_ptr & node1,const node_ptr & node2)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&) swap_nodes(const node_ptr & node1,const node_ptr & header1,const node_ptr & node2,const node_ptr & header2)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&) replace_node(const node_ptr & node_to_be_replaced,const node_ptr & new_node)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&) replace_node(const node_ptr & node_to_be_replaced,const node_ptr & header,const node_ptr & new_node)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&) 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(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&) init_header(const node_ptr & header)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&) erase(const node_ptr & header,const node_ptr & z)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 288 color new_z_color; 289 if(info.y != z){ 290 new_z_color = NodeTraits::get_color(info.y); 291 NodeTraits::set_color(info.y, NodeTraits::get_color(z)); 292 } 293 else{ 294 new_z_color = NodeTraits::get_color(z); 295 } 296 //Rebalance rbtree if needed 297 if(new_z_color != NodeTraits::red()){ 298 rebalance_after_erasure(header, info.x, info.x_parent); 299 } 300 return z; 301 } 302 303 //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) 304 template <class Cloner, class Disposer> clone(const const_node_ptr & source_header,const node_ptr & target_header,Cloner cloner,Disposer disposer)305 static void clone 306 (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer) 307 { 308 rbtree_node_cloner<NodeTraits, Cloner> new_cloner(cloner); 309 bstree_algo::clone(source_header, target_header, new_cloner, disposer); 310 } 311 312 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 313 //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) 314 template<class Disposer> 315 static void clear_and_dispose(const node_ptr & header, Disposer disposer); 316 317 //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 318 template<class KeyType, class KeyNodePtrCompare> 319 static node_ptr lower_bound 320 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); 321 322 //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 323 template<class KeyType, class KeyNodePtrCompare> 324 static node_ptr upper_bound 325 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); 326 327 //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) 328 template<class KeyType, class KeyNodePtrCompare> 329 static node_ptr find 330 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); 331 332 //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 333 template<class KeyType, class KeyNodePtrCompare> 334 static std::pair<node_ptr, node_ptr> equal_range 335 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); 336 337 //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) 338 template<class KeyType, class KeyNodePtrCompare> 339 static std::pair<node_ptr, node_ptr> bounded_range 340 (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp 341 , bool left_closed, bool right_closed); 342 343 //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) 344 template<class KeyType, class KeyNodePtrCompare> 345 static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); 346 347 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 348 349 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) 350 template<class NodePtrCompare> insert_equal_upper_bound(const node_ptr & h,const node_ptr & new_node,NodePtrCompare comp)351 static node_ptr insert_equal_upper_bound 352 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) 353 { 354 bstree_algo::insert_equal_upper_bound(h, new_node, comp); 355 rebalance_after_insertion(h, new_node); 356 return new_node; 357 } 358 359 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) 360 template<class NodePtrCompare> insert_equal_lower_bound(const node_ptr & h,const node_ptr & new_node,NodePtrCompare comp)361 static node_ptr insert_equal_lower_bound 362 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) 363 { 364 bstree_algo::insert_equal_lower_bound(h, new_node, comp); 365 rebalance_after_insertion(h, new_node); 366 return new_node; 367 } 368 369 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) 370 template<class NodePtrCompare> insert_equal(const node_ptr & header,const node_ptr & hint,const node_ptr & new_node,NodePtrCompare comp)371 static node_ptr insert_equal 372 (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp) 373 { 374 bstree_algo::insert_equal(header, hint, new_node, comp); 375 rebalance_after_insertion(header, new_node); 376 return new_node; 377 } 378 379 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) insert_before(const node_ptr & header,const node_ptr & pos,const node_ptr & new_node)380 static node_ptr insert_before 381 (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node) 382 { 383 bstree_algo::insert_before(header, pos, new_node); 384 rebalance_after_insertion(header, new_node); 385 return new_node; 386 } 387 388 //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) push_back(const node_ptr & header,const node_ptr & new_node)389 static void push_back(const node_ptr & header, const node_ptr & new_node) 390 { 391 bstree_algo::push_back(header, new_node); 392 rebalance_after_insertion(header, new_node); 393 } 394 395 //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) push_front(const node_ptr & header,const node_ptr & new_node)396 static void push_front(const node_ptr & header, const node_ptr & new_node) 397 { 398 bstree_algo::push_front(header, new_node); 399 rebalance_after_insertion(header, new_node); 400 } 401 402 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 403 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) 404 template<class KeyType, class KeyNodePtrCompare> 405 static std::pair<node_ptr, bool> insert_unique_check 406 (const const_node_ptr & header, const KeyType &key 407 ,KeyNodePtrCompare comp, insert_commit_data &commit_data); 408 409 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) 410 template<class KeyType, class KeyNodePtrCompare> 411 static std::pair<node_ptr, bool> insert_unique_check 412 (const const_node_ptr & header, const node_ptr &hint, const KeyType &key 413 ,KeyNodePtrCompare comp, insert_commit_data &commit_data); 414 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 415 416 //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data&) insert_unique_commit(const node_ptr & header,const node_ptr & new_value,const insert_commit_data & commit_data)417 static void insert_unique_commit 418 (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data) 419 { 420 bstree_algo::insert_unique_commit(header, new_value, commit_data); 421 rebalance_after_insertion(header, new_value); 422 } 423 424 //! @copydoc ::boost::intrusive::bstree_algorithms::is_header is_header(const const_node_ptr & p)425 static bool is_header(const const_node_ptr & p) 426 { 427 return NodeTraits::get_color(p) == NodeTraits::red() && 428 bstree_algo::is_header(p); 429 } 430 431 /// @cond 432 private: 433 rebalance_after_erasure(const node_ptr & header,node_ptr x,node_ptr x_parent)434 static void rebalance_after_erasure(const node_ptr & header, node_ptr x, node_ptr x_parent) 435 { 436 while(1){ 437 if(x_parent == header || (x && NodeTraits::get_color(x) != NodeTraits::black())){ 438 break; 439 } 440 //Don't cache x_is_leftchild or similar because x can be null and 441 //equal to both x_parent_left and x_parent_right 442 const node_ptr x_parent_left(NodeTraits::get_left(x_parent)); 443 if(x == x_parent_left){ //x is left child 444 node_ptr w = NodeTraits::get_right(x_parent); 445 BOOST_INTRUSIVE_INVARIANT_ASSERT(w); 446 if(NodeTraits::get_color(w) == NodeTraits::red()){ 447 NodeTraits::set_color(w, NodeTraits::black()); 448 NodeTraits::set_color(x_parent, NodeTraits::red()); 449 bstree_algo::rotate_left(x_parent, w, NodeTraits::get_parent(x_parent), header); 450 w = NodeTraits::get_right(x_parent); 451 } 452 node_ptr const w_left (NodeTraits::get_left(w)); 453 node_ptr const w_right(NodeTraits::get_right(w)); 454 if((!w_left || NodeTraits::get_color(w_left) == NodeTraits::black()) && 455 (!w_right || NodeTraits::get_color(w_right) == NodeTraits::black())){ 456 NodeTraits::set_color(w, NodeTraits::red()); 457 x = x_parent; 458 x_parent = NodeTraits::get_parent(x_parent); 459 } 460 else { 461 if(!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()){ 462 NodeTraits::set_color(w_left, NodeTraits::black()); 463 NodeTraits::set_color(w, NodeTraits::red()); 464 bstree_algo::rotate_right(w, w_left, NodeTraits::get_parent(w), header); 465 w = NodeTraits::get_right(x_parent); 466 } 467 NodeTraits::set_color(w, NodeTraits::get_color(x_parent)); 468 NodeTraits::set_color(x_parent, NodeTraits::black()); 469 const node_ptr new_wright(NodeTraits::get_right(w)); 470 if(new_wright) 471 NodeTraits::set_color(new_wright, NodeTraits::black()); 472 bstree_algo::rotate_left(x_parent, NodeTraits::get_right(x_parent), NodeTraits::get_parent(x_parent), header); 473 break; 474 } 475 } 476 else { 477 // same as above, with right_ <-> left_. 478 node_ptr w = x_parent_left; 479 if(NodeTraits::get_color(w) == NodeTraits::red()){ 480 NodeTraits::set_color(w, NodeTraits::black()); 481 NodeTraits::set_color(x_parent, NodeTraits::red()); 482 bstree_algo::rotate_right(x_parent, w, NodeTraits::get_parent(x_parent), header); 483 w = NodeTraits::get_left(x_parent); 484 } 485 node_ptr const w_left (NodeTraits::get_left(w)); 486 node_ptr const w_right(NodeTraits::get_right(w)); 487 if((!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()) && 488 (!w_left || NodeTraits::get_color(w_left) == NodeTraits::black())){ 489 NodeTraits::set_color(w, NodeTraits::red()); 490 x = x_parent; 491 x_parent = NodeTraits::get_parent(x_parent); 492 } 493 else { 494 if(!w_left || NodeTraits::get_color(w_left) == NodeTraits::black()){ 495 NodeTraits::set_color(w_right, NodeTraits::black()); 496 NodeTraits::set_color(w, NodeTraits::red()); 497 bstree_algo::rotate_left(w, w_right, NodeTraits::get_parent(w), header); 498 w = NodeTraits::get_left(x_parent); 499 } 500 NodeTraits::set_color(w, NodeTraits::get_color(x_parent)); 501 NodeTraits::set_color(x_parent, NodeTraits::black()); 502 const node_ptr new_wleft(NodeTraits::get_left(w)); 503 if(new_wleft) 504 NodeTraits::set_color(new_wleft, NodeTraits::black()); 505 bstree_algo::rotate_right(x_parent, NodeTraits::get_left(x_parent), NodeTraits::get_parent(x_parent), header); 506 break; 507 } 508 } 509 } 510 if(x) 511 NodeTraits::set_color(x, NodeTraits::black()); 512 } 513 rebalance_after_insertion(const node_ptr & header,node_ptr p)514 static void rebalance_after_insertion(const node_ptr & header, node_ptr p) 515 { 516 NodeTraits::set_color(p, NodeTraits::red()); 517 while(1){ 518 node_ptr p_parent(NodeTraits::get_parent(p)); 519 const node_ptr p_grandparent(NodeTraits::get_parent(p_parent)); 520 if(p_parent == header || NodeTraits::get_color(p_parent) == NodeTraits::black() || p_grandparent == header){ 521 break; 522 } 523 524 NodeTraits::set_color(p_grandparent, NodeTraits::red()); 525 node_ptr const p_grandparent_left (NodeTraits::get_left (p_grandparent)); 526 bool const p_parent_is_left_child = p_parent == p_grandparent_left; 527 node_ptr const x(p_parent_is_left_child ? NodeTraits::get_right(p_grandparent) : p_grandparent_left); 528 529 if(x && NodeTraits::get_color(x) == NodeTraits::red()){ 530 NodeTraits::set_color(x, NodeTraits::black()); 531 NodeTraits::set_color(p_parent, NodeTraits::black()); 532 p = p_grandparent; 533 } 534 else{ //Final step 535 const bool p_is_left_child(NodeTraits::get_left(p_parent) == p); 536 if(p_parent_is_left_child){ //p_parent is left child 537 if(!p_is_left_child){ //p is right child 538 bstree_algo::rotate_left_no_parent_fix(p_parent, p); 539 //No need to link p and p_grandparent: 540 // [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_left(p_grandparent, p)] 541 //as p_grandparent is not the header, another rotation is coming and p_parent 542 //will be the left child of p_grandparent 543 p_parent = p; 544 } 545 bstree_algo::rotate_right(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header); 546 } 547 else{ //p_parent is right child 548 if(p_is_left_child){ //p is left child 549 bstree_algo::rotate_right_no_parent_fix(p_parent, p); 550 //No need to link p and p_grandparent: 551 // [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_right(p_grandparent, p)] 552 //as p_grandparent is not the header, another rotation is coming and p_parent 553 //will be the right child of p_grandparent 554 p_parent = p; 555 } 556 bstree_algo::rotate_left(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header); 557 } 558 NodeTraits::set_color(p_parent, NodeTraits::black()); 559 break; 560 } 561 } 562 NodeTraits::set_color(NodeTraits::get_parent(header), NodeTraits::black()); 563 } 564 /// @endcond 565 }; 566 567 /// @cond 568 569 template<class NodeTraits> 570 struct get_algo<RbTreeAlgorithms, NodeTraits> 571 { 572 typedef rbtree_algorithms<NodeTraits> type; 573 }; 574 575 template <class ValueTraits, class NodePtrCompare, class ExtraChecker> 576 struct get_node_checker<RbTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> 577 { 578 typedef detail::rbtree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; 579 }; 580 581 /// @endcond 582 583 } //namespace intrusive 584 } //namespace boost 585 586 #include <boost/intrusive/detail/config_end.hpp> 587 588 #endif //BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP 589