1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2007-2014 4 // 5 // Distributed under the Boost Software License, Version 1.0. 6 // (See accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 // 9 // See http://www.boost.org/libs/intrusive for documentation. 10 // 11 ///////////////////////////////////////////////////////////////////////////// 12 13 #ifndef BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP 14 #define BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP 15 16 #include <cstddef> 17 #include <boost/intrusive/detail/config_begin.hpp> 18 #include <boost/intrusive/intrusive_fwd.hpp> 19 #include <boost/intrusive/detail/bstree_algorithms_base.hpp> 20 #include <boost/intrusive/detail/assert.hpp> 21 #include <boost/intrusive/detail/uncast.hpp> 22 #include <boost/intrusive/detail/math.hpp> 23 #include <boost/intrusive/detail/algo_type.hpp> 24 25 #include <boost/intrusive/detail/minimal_pair_header.hpp> 26 27 #if defined(BOOST_HAS_PRAGMA_ONCE) 28 # pragma once 29 #endif 30 31 namespace boost { 32 namespace intrusive { 33 34 /// @cond 35 36 //! This type is the information that will be filled by insert_unique_check 37 template <class NodePtr> 38 struct insert_commit_data_t 39 { 40 bool link_left; 41 NodePtr node; 42 }; 43 44 template <class NodePtr> 45 struct data_for_rebalance_t 46 { 47 NodePtr x; 48 NodePtr x_parent; 49 NodePtr y; 50 }; 51 52 namespace detail { 53 54 template<class ValueTraits, class NodePtrCompare, class ExtraChecker> 55 struct bstree_node_checker 56 : public ExtraChecker 57 { 58 typedef ExtraChecker base_checker_t; 59 typedef ValueTraits value_traits; 60 typedef typename value_traits::node_traits node_traits; 61 typedef typename node_traits::const_node_ptr const_node_ptr; 62 63 struct return_type 64 : public base_checker_t::return_type 65 { return_typeboost::intrusive::detail::bstree_node_checker::return_type66 return_type() : min_key_node_ptr(const_node_ptr()), max_key_node_ptr(const_node_ptr()), node_count(0) {} 67 68 const_node_ptr min_key_node_ptr; 69 const_node_ptr max_key_node_ptr; 70 size_t node_count; 71 }; 72 bstree_node_checkerboost::intrusive::detail::bstree_node_checker73 bstree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker) 74 : base_checker_t(extra_checker), comp_(comp) 75 {} 76 operator ()boost::intrusive::detail::bstree_node_checker77 void operator () (const const_node_ptr& p, 78 const return_type& check_return_left, const return_type& check_return_right, 79 return_type& check_return) 80 { 81 if (check_return_left.max_key_node_ptr) 82 BOOST_INTRUSIVE_INVARIANT_ASSERT(!comp_(p, check_return_left.max_key_node_ptr)); 83 if (check_return_right.min_key_node_ptr) 84 BOOST_INTRUSIVE_INVARIANT_ASSERT(!comp_(check_return_right.min_key_node_ptr, p)); 85 check_return.min_key_node_ptr = node_traits::get_left(p)? check_return_left.min_key_node_ptr : p; 86 check_return.max_key_node_ptr = node_traits::get_right(p)? check_return_right.max_key_node_ptr : p; 87 check_return.node_count = check_return_left.node_count + check_return_right.node_count + 1; 88 base_checker_t::operator()(p, check_return_left, check_return_right, check_return); 89 } 90 91 const NodePtrCompare comp_; 92 }; 93 94 } // namespace detail 95 96 /// @endcond 97 98 99 100 //! This is an implementation of a binary search tree. 101 //! A node in the search tree has references to its children and its parent. This 102 //! is to allow traversal of the whole tree from a given node making the 103 //! implementation of iterator a pointer to a node. 104 //! At the top of the tree a node is used specially. This node's parent pointer 105 //! is pointing to the root of the tree. Its left pointer points to the 106 //! leftmost node in the tree and the right pointer to the rightmost one. 107 //! This node is used to represent the end-iterator. 108 //! 109 //! +---------+ 110 //! header------------------------------>| | 111 //! | | 112 //! +----------(left)--------| |--------(right)---------+ 113 //! | +---------+ | 114 //! | | | 115 //! | | (parent) | 116 //! | | | 117 //! | | | 118 //! | +---------+ | 119 //! root of tree ..|......................> | | | 120 //! | | D | | 121 //! | | | | 122 //! | +-------+---------+-------+ | 123 //! | | | | 124 //! | | | | 125 //! | | | | 126 //! | | | | 127 //! | | | | 128 //! | +---------+ +---------+ | 129 //! | | | | | | 130 //! | | B | | F | | 131 //! | | | | | | 132 //! | +--+---------+--+ +--+---------+--+ | 133 //! | | | | | | 134 //! | | | | | | 135 //! | | | | | | 136 //! | +---+-----+ +-----+---+ +---+-----+ +-----+---+ | 137 //! +-->| | | | | | | |<--+ 138 //! | A | | C | | E | | G | 139 //! | | | | | | | | 140 //! +---------+ +---------+ +---------+ +---------+ 141 //! 142 //! bstree_algorithms is configured with a NodeTraits class, which encapsulates the 143 //! information about the node to be manipulated. NodeTraits must support the 144 //! following interface: 145 //! 146 //! <b>Typedefs</b>: 147 //! 148 //! <tt>node</tt>: The type of the node that forms the binary search tree 149 //! 150 //! <tt>node_ptr</tt>: A pointer to a node 151 //! 152 //! <tt>const_node_ptr</tt>: A pointer to a const node 153 //! 154 //! <b>Static functions</b>: 155 //! 156 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt> 157 //! 158 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt> 159 //! 160 //! <tt>static node_ptr get_left(const_node_ptr n);</tt> 161 //! 162 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt> 163 //! 164 //! <tt>static node_ptr get_right(const_node_ptr n);</tt> 165 //! 166 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt> 167 template<class NodeTraits> 168 class bstree_algorithms : public bstree_algorithms_base<NodeTraits> 169 { 170 public: 171 typedef typename NodeTraits::node node; 172 typedef NodeTraits node_traits; 173 typedef typename NodeTraits::node_ptr node_ptr; 174 typedef typename NodeTraits::const_node_ptr const_node_ptr; 175 typedef insert_commit_data_t<node_ptr> insert_commit_data; 176 typedef data_for_rebalance_t<node_ptr> data_for_rebalance; 177 178 /// @cond 179 typedef bstree_algorithms<NodeTraits> this_type; 180 typedef bstree_algorithms_base<NodeTraits> base_type; 181 private: 182 template<class Disposer> 183 struct dispose_subtree_disposer 184 { dispose_subtree_disposerboost::intrusive::bstree_algorithms::dispose_subtree_disposer185 dispose_subtree_disposer(Disposer &disp, const node_ptr & subtree) 186 : disposer_(&disp), subtree_(subtree) 187 {} 188 releaseboost::intrusive::bstree_algorithms::dispose_subtree_disposer189 void release() 190 { disposer_ = 0; } 191 ~dispose_subtree_disposerboost::intrusive::bstree_algorithms::dispose_subtree_disposer192 ~dispose_subtree_disposer() 193 { 194 if(disposer_){ 195 dispose_subtree(subtree_, *disposer_); 196 } 197 } 198 Disposer *disposer_; 199 const node_ptr subtree_; 200 }; 201 202 /// @endcond 203 204 public: 205 //! <b>Requires</b>: 'header' is the header node of a tree. 206 //! 207 //! <b>Effects</b>: Returns the first node of the tree, the header if the tree is empty. 208 //! 209 //! <b>Complexity</b>: Constant time. 210 //! 211 //! <b>Throws</b>: Nothing. begin_node(const const_node_ptr & header)212 static node_ptr begin_node(const const_node_ptr & header) 213 { return node_traits::get_left(header); } 214 215 //! <b>Requires</b>: 'header' is the header node of a tree. 216 //! 217 //! <b>Effects</b>: Returns the header of the tree. 218 //! 219 //! <b>Complexity</b>: Constant time. 220 //! 221 //! <b>Throws</b>: Nothing. end_node(const const_node_ptr & header)222 static node_ptr end_node(const const_node_ptr & header) 223 { return detail::uncast(header); } 224 225 //! <b>Requires</b>: 'header' is the header node of a tree. 226 //! 227 //! <b>Effects</b>: Returns the root of the tree if any, header otherwise 228 //! 229 //! <b>Complexity</b>: Constant time. 230 //! 231 //! <b>Throws</b>: Nothing. root_node(const const_node_ptr & header)232 static node_ptr root_node(const const_node_ptr & header) 233 { 234 node_ptr p = node_traits::get_parent(header); 235 return p ? p : detail::uncast(header); 236 } 237 238 //! <b>Requires</b>: 'node' is a node of the tree or a node initialized 239 //! by init(...) or init_node. 240 //! 241 //! <b>Effects</b>: Returns true if the node is initialized by init() or init_node(). 242 //! 243 //! <b>Complexity</b>: Constant time. 244 //! 245 //! <b>Throws</b>: Nothing. unique(const const_node_ptr & node)246 static bool unique(const const_node_ptr & node) 247 { return !NodeTraits::get_parent(node); } 248 249 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 250 //! <b>Requires</b>: 'node' is a node of the tree or a header node. 251 //! 252 //! <b>Effects</b>: Returns the header of the tree. 253 //! 254 //! <b>Complexity</b>: Logarithmic. 255 //! 256 //! <b>Throws</b>: Nothing. 257 static node_ptr get_header(const const_node_ptr & node); 258 #endif 259 260 //! <b>Requires</b>: node1 and node2 can't be header nodes 261 //! of two trees. 262 //! 263 //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted 264 //! in the position node2 before the function. node2 will be inserted in the 265 //! position node1 had before the function. 266 //! 267 //! <b>Complexity</b>: Logarithmic. 268 //! 269 //! <b>Throws</b>: Nothing. 270 //! 271 //! <b>Note</b>: This function will break container ordering invariants if 272 //! node1 and node2 are not equivalent according to the ordering rules. 273 //! 274 //!Experimental function swap_nodes(const node_ptr & node1,const node_ptr & node2)275 static void swap_nodes(const node_ptr & node1, const node_ptr & node2) 276 { 277 if(node1 == node2) 278 return; 279 280 node_ptr header1(base_type::get_header(node1)), header2(base_type::get_header(node2)); 281 swap_nodes(node1, header1, node2, header2); 282 } 283 284 //! <b>Requires</b>: node1 and node2 can't be header nodes 285 //! of two trees with header header1 and header2. 286 //! 287 //! <b>Effects</b>: Swaps two nodes. After the function node1 will be inserted 288 //! in the position node2 before the function. node2 will be inserted in the 289 //! position node1 had before the function. 290 //! 291 //! <b>Complexity</b>: Constant. 292 //! 293 //! <b>Throws</b>: Nothing. 294 //! 295 //! <b>Note</b>: This function will break container ordering invariants if 296 //! node1 and node2 are not equivalent according to the ordering rules. 297 //! 298 //!Experimental function swap_nodes(const node_ptr & node1,const node_ptr & header1,const node_ptr & node2,const node_ptr & header2)299 static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2) 300 { 301 if(node1 == node2) 302 return; 303 304 //node1 and node2 must not be header nodes 305 //BOOST_INTRUSIVE_INVARIANT_ASSERT((header1 != node1 && header2 != node2)); 306 if(header1 != header2){ 307 //Update header1 if necessary 308 if(node1 == NodeTraits::get_left(header1)){ 309 NodeTraits::set_left(header1, node2); 310 } 311 312 if(node1 == NodeTraits::get_right(header1)){ 313 NodeTraits::set_right(header1, node2); 314 } 315 316 if(node1 == NodeTraits::get_parent(header1)){ 317 NodeTraits::set_parent(header1, node2); 318 } 319 320 //Update header2 if necessary 321 if(node2 == NodeTraits::get_left(header2)){ 322 NodeTraits::set_left(header2, node1); 323 } 324 325 if(node2 == NodeTraits::get_right(header2)){ 326 NodeTraits::set_right(header2, node1); 327 } 328 329 if(node2 == NodeTraits::get_parent(header2)){ 330 NodeTraits::set_parent(header2, node1); 331 } 332 } 333 else{ 334 //If both nodes are from the same tree 335 //Update header if necessary 336 if(node1 == NodeTraits::get_left(header1)){ 337 NodeTraits::set_left(header1, node2); 338 } 339 else if(node2 == NodeTraits::get_left(header2)){ 340 NodeTraits::set_left(header2, node1); 341 } 342 343 if(node1 == NodeTraits::get_right(header1)){ 344 NodeTraits::set_right(header1, node2); 345 } 346 else if(node2 == NodeTraits::get_right(header2)){ 347 NodeTraits::set_right(header2, node1); 348 } 349 350 if(node1 == NodeTraits::get_parent(header1)){ 351 NodeTraits::set_parent(header1, node2); 352 } 353 else if(node2 == NodeTraits::get_parent(header2)){ 354 NodeTraits::set_parent(header2, node1); 355 } 356 357 //Adjust data in nodes to be swapped 358 //so that final link swap works as expected 359 if(node1 == NodeTraits::get_parent(node2)){ 360 NodeTraits::set_parent(node2, node2); 361 362 if(node2 == NodeTraits::get_right(node1)){ 363 NodeTraits::set_right(node1, node1); 364 } 365 else{ 366 NodeTraits::set_left(node1, node1); 367 } 368 } 369 else if(node2 == NodeTraits::get_parent(node1)){ 370 NodeTraits::set_parent(node1, node1); 371 372 if(node1 == NodeTraits::get_right(node2)){ 373 NodeTraits::set_right(node2, node2); 374 } 375 else{ 376 NodeTraits::set_left(node2, node2); 377 } 378 } 379 } 380 381 //Now swap all the links 382 node_ptr temp; 383 //swap left link 384 temp = NodeTraits::get_left(node1); 385 NodeTraits::set_left(node1, NodeTraits::get_left(node2)); 386 NodeTraits::set_left(node2, temp); 387 //swap right link 388 temp = NodeTraits::get_right(node1); 389 NodeTraits::set_right(node1, NodeTraits::get_right(node2)); 390 NodeTraits::set_right(node2, temp); 391 //swap parent link 392 temp = NodeTraits::get_parent(node1); 393 NodeTraits::set_parent(node1, NodeTraits::get_parent(node2)); 394 NodeTraits::set_parent(node2, temp); 395 396 //Now adjust adjacent nodes for newly inserted node 1 397 if((temp = NodeTraits::get_left(node1))){ 398 NodeTraits::set_parent(temp, node1); 399 } 400 if((temp = NodeTraits::get_right(node1))){ 401 NodeTraits::set_parent(temp, node1); 402 } 403 if((temp = NodeTraits::get_parent(node1)) && 404 //The header has been already updated so avoid it 405 temp != header2){ 406 if(NodeTraits::get_left(temp) == node2){ 407 NodeTraits::set_left(temp, node1); 408 } 409 if(NodeTraits::get_right(temp) == node2){ 410 NodeTraits::set_right(temp, node1); 411 } 412 } 413 //Now adjust adjacent nodes for newly inserted node 2 414 if((temp = NodeTraits::get_left(node2))){ 415 NodeTraits::set_parent(temp, node2); 416 } 417 if((temp = NodeTraits::get_right(node2))){ 418 NodeTraits::set_parent(temp, node2); 419 } 420 if((temp = NodeTraits::get_parent(node2)) && 421 //The header has been already updated so avoid it 422 temp != header1){ 423 if(NodeTraits::get_left(temp) == node1){ 424 NodeTraits::set_left(temp, node2); 425 } 426 if(NodeTraits::get_right(temp) == node1){ 427 NodeTraits::set_right(temp, node2); 428 } 429 } 430 } 431 432 //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree 433 //! and new_node must not be inserted in a tree. 434 //! 435 //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the 436 //! tree with new_node. The tree does not need to be rebalanced 437 //! 438 //! <b>Complexity</b>: Logarithmic. 439 //! 440 //! <b>Throws</b>: Nothing. 441 //! 442 //! <b>Note</b>: This function will break container ordering invariants if 443 //! new_node is not equivalent to node_to_be_replaced according to the 444 //! ordering rules. This function is faster than erasing and inserting 445 //! the node, since no rebalancing and comparison is needed. Experimental function replace_node(const node_ptr & node_to_be_replaced,const node_ptr & new_node)446 static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node) 447 { 448 if(node_to_be_replaced == new_node) 449 return; 450 replace_node(node_to_be_replaced, base_type::get_header(node_to_be_replaced), new_node); 451 } 452 453 //! <b>Requires</b>: node_to_be_replaced must be inserted in a tree 454 //! with header "header" and new_node must not be inserted in a tree. 455 //! 456 //! <b>Effects</b>: Replaces node_to_be_replaced in its position in the 457 //! tree with new_node. The tree does not need to be rebalanced 458 //! 459 //! <b>Complexity</b>: Constant. 460 //! 461 //! <b>Throws</b>: Nothing. 462 //! 463 //! <b>Note</b>: This function will break container ordering invariants if 464 //! new_node is not equivalent to node_to_be_replaced according to the 465 //! ordering rules. This function is faster than erasing and inserting 466 //! the node, since no rebalancing or comparison is needed. Experimental function replace_node(const node_ptr & node_to_be_replaced,const node_ptr & header,const node_ptr & new_node)467 static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node) 468 { 469 if(node_to_be_replaced == new_node) 470 return; 471 472 //Update header if necessary 473 if(node_to_be_replaced == NodeTraits::get_left(header)){ 474 NodeTraits::set_left(header, new_node); 475 } 476 477 if(node_to_be_replaced == NodeTraits::get_right(header)){ 478 NodeTraits::set_right(header, new_node); 479 } 480 481 if(node_to_be_replaced == NodeTraits::get_parent(header)){ 482 NodeTraits::set_parent(header, new_node); 483 } 484 485 //Now set data from the original node 486 node_ptr temp; 487 NodeTraits::set_left(new_node, NodeTraits::get_left(node_to_be_replaced)); 488 NodeTraits::set_right(new_node, NodeTraits::get_right(node_to_be_replaced)); 489 NodeTraits::set_parent(new_node, NodeTraits::get_parent(node_to_be_replaced)); 490 491 //Now adjust adjacent nodes for newly inserted node 492 if((temp = NodeTraits::get_left(new_node))){ 493 NodeTraits::set_parent(temp, new_node); 494 } 495 if((temp = NodeTraits::get_right(new_node))){ 496 NodeTraits::set_parent(temp, new_node); 497 } 498 if((temp = NodeTraits::get_parent(new_node)) && 499 //The header has been already updated so avoid it 500 temp != header){ 501 if(NodeTraits::get_left(temp) == node_to_be_replaced){ 502 NodeTraits::set_left(temp, new_node); 503 } 504 if(NodeTraits::get_right(temp) == node_to_be_replaced){ 505 NodeTraits::set_right(temp, new_node); 506 } 507 } 508 } 509 510 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 511 //! <b>Requires</b>: 'node' is a node from the tree except the header. 512 //! 513 //! <b>Effects</b>: Returns the next node of the tree. 514 //! 515 //! <b>Complexity</b>: Average constant time. 516 //! 517 //! <b>Throws</b>: Nothing. 518 static node_ptr next_node(const node_ptr & node); 519 520 //! <b>Requires</b>: 'node' is a node from the tree except the leftmost node. 521 //! 522 //! <b>Effects</b>: Returns the previous node of the tree. 523 //! 524 //! <b>Complexity</b>: Average constant time. 525 //! 526 //! <b>Throws</b>: Nothing. 527 static node_ptr prev_node(const node_ptr & node); 528 529 //! <b>Requires</b>: 'node' is a node of a tree but not the header. 530 //! 531 //! <b>Effects</b>: Returns the minimum node of the subtree starting at p. 532 //! 533 //! <b>Complexity</b>: Logarithmic to the size of the subtree. 534 //! 535 //! <b>Throws</b>: Nothing. 536 static node_ptr minimum(node_ptr node); 537 538 //! <b>Requires</b>: 'node' is a node of a tree but not the header. 539 //! 540 //! <b>Effects</b>: Returns the maximum node of the subtree starting at p. 541 //! 542 //! <b>Complexity</b>: Logarithmic to the size of the subtree. 543 //! 544 //! <b>Throws</b>: Nothing. 545 static node_ptr maximum(node_ptr node); 546 #endif 547 548 //! <b>Requires</b>: 'node' must not be part of any tree. 549 //! 550 //! <b>Effects</b>: After the function unique(node) == true. 551 //! 552 //! <b>Complexity</b>: Constant. 553 //! 554 //! <b>Throws</b>: Nothing. 555 //! 556 //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree. init(const node_ptr & node)557 static void init(const node_ptr & node) 558 { 559 NodeTraits::set_parent(node, node_ptr()); 560 NodeTraits::set_left(node, node_ptr()); 561 NodeTraits::set_right(node, node_ptr()); 562 }; 563 564 //! <b>Effects</b>: Returns true if node is in the same state as if called init(node) 565 //! 566 //! <b>Complexity</b>: Constant. 567 //! 568 //! <b>Throws</b>: Nothing. inited(const const_node_ptr & node)569 static bool inited(const const_node_ptr & node) 570 { 571 return !NodeTraits::get_parent(node) && 572 !NodeTraits::get_left(node) && 573 !NodeTraits::get_right(node) ; 574 }; 575 576 //! <b>Requires</b>: node must not be part of any tree. 577 //! 578 //! <b>Effects</b>: Initializes the header to represent an empty tree. 579 //! unique(header) == true. 580 //! 581 //! <b>Complexity</b>: Constant. 582 //! 583 //! <b>Throws</b>: Nothing. 584 //! 585 //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree. init_header(const node_ptr & header)586 static void init_header(const node_ptr & header) 587 { 588 NodeTraits::set_parent(header, node_ptr()); 589 NodeTraits::set_left(header, header); 590 NodeTraits::set_right(header, header); 591 } 592 593 //! <b>Requires</b>: "disposer" must be an object function 594 //! taking a node_ptr parameter and shouldn't throw. 595 //! 596 //! <b>Effects</b>: Empties the target tree calling 597 //! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree 598 //! except the header. 599 //! 600 //! <b>Complexity</b>: Linear to the number of element of the source tree plus the. 601 //! number of elements of tree target tree when calling this function. 602 //! 603 //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed. 604 template<class Disposer> clear_and_dispose(const node_ptr & header,Disposer disposer)605 static void clear_and_dispose(const node_ptr & header, Disposer disposer) 606 { 607 node_ptr source_root = NodeTraits::get_parent(header); 608 if(!source_root) 609 return; 610 dispose_subtree(source_root, disposer); 611 init_header(header); 612 } 613 614 //! <b>Requires</b>: header is the header of a tree. 615 //! 616 //! <b>Effects</b>: Unlinks the leftmost node from the tree, and 617 //! updates the header link to the new leftmost node. 618 //! 619 //! <b>Complexity</b>: Average complexity is constant time. 620 //! 621 //! <b>Throws</b>: Nothing. 622 //! 623 //! <b>Notes</b>: This function breaks the tree and the tree can 624 //! only be used for more unlink_leftmost_without_rebalance calls. 625 //! This function is normally used to achieve a step by step 626 //! controlled destruction of the tree. unlink_leftmost_without_rebalance(const node_ptr & header)627 static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header) 628 { 629 node_ptr leftmost = NodeTraits::get_left(header); 630 if (leftmost == header) 631 return node_ptr(); 632 node_ptr leftmost_parent(NodeTraits::get_parent(leftmost)); 633 node_ptr leftmost_right (NodeTraits::get_right(leftmost)); 634 bool is_root = leftmost_parent == header; 635 636 if (leftmost_right){ 637 NodeTraits::set_parent(leftmost_right, leftmost_parent); 638 NodeTraits::set_left(header, base_type::minimum(leftmost_right)); 639 640 if (is_root) 641 NodeTraits::set_parent(header, leftmost_right); 642 else 643 NodeTraits::set_left(NodeTraits::get_parent(header), leftmost_right); 644 } 645 else if (is_root){ 646 NodeTraits::set_parent(header, node_ptr()); 647 NodeTraits::set_left(header, header); 648 NodeTraits::set_right(header, header); 649 } 650 else{ 651 NodeTraits::set_left(leftmost_parent, node_ptr()); 652 NodeTraits::set_left(header, leftmost_parent); 653 } 654 return leftmost; 655 } 656 657 //! <b>Requires</b>: node is a node of the tree but it's not the header. 658 //! 659 //! <b>Effects</b>: Returns the number of nodes of the subtree. 660 //! 661 //! <b>Complexity</b>: Linear time. 662 //! 663 //! <b>Throws</b>: Nothing. size(const const_node_ptr & header)664 static std::size_t size(const const_node_ptr & header) 665 { 666 node_ptr beg(begin_node(header)); 667 node_ptr end(end_node(header)); 668 std::size_t i = 0; 669 for(;beg != end; beg = base_type::next_node(beg)) ++i; 670 return i; 671 } 672 673 //! <b>Requires</b>: header1 and header2 must be the header nodes 674 //! of two trees. 675 //! 676 //! <b>Effects</b>: Swaps two trees. After the function header1 will contain 677 //! links to the second tree and header2 will have links to the first tree. 678 //! 679 //! <b>Complexity</b>: Constant. 680 //! 681 //! <b>Throws</b>: Nothing. swap_tree(const node_ptr & header1,const node_ptr & header2)682 static void swap_tree(const node_ptr & header1, const node_ptr & header2) 683 { 684 if(header1 == header2) 685 return; 686 687 node_ptr tmp; 688 689 //Parent swap 690 tmp = NodeTraits::get_parent(header1); 691 NodeTraits::set_parent(header1, NodeTraits::get_parent(header2)); 692 NodeTraits::set_parent(header2, tmp); 693 //Left swap 694 tmp = NodeTraits::get_left(header1); 695 NodeTraits::set_left(header1, NodeTraits::get_left(header2)); 696 NodeTraits::set_left(header2, tmp); 697 //Right swap 698 tmp = NodeTraits::get_right(header1); 699 NodeTraits::set_right(header1, NodeTraits::get_right(header2)); 700 NodeTraits::set_right(header2, tmp); 701 702 //Now test parent 703 node_ptr h1_parent(NodeTraits::get_parent(header1)); 704 if(h1_parent){ 705 NodeTraits::set_parent(h1_parent, header1); 706 } 707 else{ 708 NodeTraits::set_left(header1, header1); 709 NodeTraits::set_right(header1, header1); 710 } 711 712 node_ptr h2_parent(NodeTraits::get_parent(header2)); 713 if(h2_parent){ 714 NodeTraits::set_parent(h2_parent, header2); 715 } 716 else{ 717 NodeTraits::set_left(header2, header2); 718 NodeTraits::set_right(header2, header2); 719 } 720 } 721 722 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 723 //! <b>Requires</b>: p is a node of a tree. 724 //! 725 //! <b>Effects</b>: Returns true if p is the header of the tree. 726 //! 727 //! <b>Complexity</b>: Constant. 728 //! 729 //! <b>Throws</b>: Nothing. 730 static bool is_header(const const_node_ptr & p); 731 #endif 732 733 //! <b>Requires</b>: "header" must be the header node of a tree. 734 //! KeyNodePtrCompare is a function object that induces a strict weak 735 //! ordering compatible with the strict weak ordering used to create the 736 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. 737 //! 738 //! <b>Effects</b>: Returns a node_ptr to the first element that is equivalent to 739 //! "key" according to "comp" or "header" if that element does not exist. 740 //! 741 //! <b>Complexity</b>: Logarithmic. 742 //! 743 //! <b>Throws</b>: If "comp" throws. 744 template<class KeyType, class KeyNodePtrCompare> find(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)745 static node_ptr find 746 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 747 { 748 node_ptr end = detail::uncast(header); 749 node_ptr y = lower_bound(header, key, comp); 750 return (y == end || comp(key, y)) ? end : y; 751 } 752 753 //! <b>Requires</b>: "header" must be the header node of a tree. 754 //! KeyNodePtrCompare is a function object that induces a strict weak 755 //! ordering compatible with the strict weak ordering used to create the 756 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. 757 //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If 758 //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be true. 759 //! 760 //! <b>Effects</b>: Returns an a pair with the following criteria: 761 //! 762 //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise 763 //! 764 //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise 765 //! 766 //! <b>Complexity</b>: Logarithmic. 767 //! 768 //! <b>Throws</b>: If "comp" throws. 769 //! 770 //! <b>Note</b>: This function can be more efficient than calling upper_bound 771 //! and lower_bound for lower_key and upper_key. 772 //! 773 //! <b>Note</b>: Experimental function, the interface might change. 774 template< class KeyType, class KeyNodePtrCompare> bounded_range(const const_node_ptr & header,const KeyType & lower_key,const KeyType & upper_key,KeyNodePtrCompare comp,bool left_closed,bool right_closed)775 static std::pair<node_ptr, node_ptr> bounded_range 776 ( const const_node_ptr & header 777 , const KeyType &lower_key 778 , const KeyType &upper_key 779 , KeyNodePtrCompare comp 780 , bool left_closed 781 , bool right_closed) 782 { 783 node_ptr y = detail::uncast(header); 784 node_ptr x = NodeTraits::get_parent(header); 785 786 while(x){ 787 //If x is less than lower_key the target 788 //range is on the right part 789 if(comp(x, lower_key)){ 790 //Check for invalid input range 791 BOOST_INTRUSIVE_INVARIANT_ASSERT(comp(x, upper_key)); 792 x = NodeTraits::get_right(x); 793 } 794 //If the upper_key is less than x, the target 795 //range is on the left part 796 else if(comp(upper_key, x)){ 797 y = x; 798 x = NodeTraits::get_left(x); 799 } 800 else{ 801 //x is inside the bounded range(lower_key <= x <= upper_key), 802 //so we must split lower and upper searches 803 // 804 //Sanity check: if lower_key and upper_key are equal, then both left_closed and right_closed can't be false 805 BOOST_INTRUSIVE_INVARIANT_ASSERT(left_closed || right_closed || comp(lower_key, x) || comp(x, upper_key)); 806 return std::pair<node_ptr,node_ptr>( 807 left_closed 808 //If left_closed, then comp(x, lower_key) is already the lower_bound 809 //condition so we save one comparison and go to the next level 810 //following traditional lower_bound algo 811 ? lower_bound_loop(NodeTraits::get_left(x), x, lower_key, comp) 812 //If left-open, comp(x, lower_key) is not the upper_bound algo 813 //condition so we must recheck current 'x' node with upper_bound algo 814 : upper_bound_loop(x, y, lower_key, comp) 815 , 816 right_closed 817 //If right_closed, then comp(upper_key, x) is already the upper_bound 818 //condition so we can save one comparison and go to the next level 819 //following lower_bound algo 820 ? upper_bound_loop(NodeTraits::get_right(x), y, upper_key, comp) 821 //If right-open, comp(upper_key, x) is not the lower_bound algo 822 //condition so we must recheck current 'x' node with lower_bound algo 823 : lower_bound_loop(x, y, upper_key, comp) 824 ); 825 } 826 } 827 return std::pair<node_ptr,node_ptr> (y, y); 828 } 829 830 //! <b>Requires</b>: "header" must be the header node of a tree. 831 //! KeyNodePtrCompare is a function object that induces a strict weak 832 //! ordering compatible with the strict weak ordering used to create the 833 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. 834 //! 835 //! <b>Effects</b>: Returns the number of elements with a key equivalent to "key" 836 //! according to "comp". 837 //! 838 //! <b>Complexity</b>: Logarithmic. 839 //! 840 //! <b>Throws</b>: If "comp" throws. 841 template<class KeyType, class KeyNodePtrCompare> count(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)842 static std::size_t count 843 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 844 { 845 std::pair<node_ptr, node_ptr> ret = equal_range(header, key, comp); 846 std::size_t n = 0; 847 while(ret.first != ret.second){ 848 ++n; 849 ret.first = base_type::next_node(ret.first); 850 } 851 return n; 852 } 853 854 //! <b>Requires</b>: "header" must be the header node of a tree. 855 //! KeyNodePtrCompare is a function object that induces a strict weak 856 //! ordering compatible with the strict weak ordering used to create the 857 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. 858 //! 859 //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing 860 //! all elements that are equivalent to "key" according to "comp" or an 861 //! empty range that indicates the position where those elements would be 862 //! if there are no equivalent elements. 863 //! 864 //! <b>Complexity</b>: Logarithmic. 865 //! 866 //! <b>Throws</b>: If "comp" throws. 867 template<class KeyType, class KeyNodePtrCompare> equal_range(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)868 static std::pair<node_ptr, node_ptr> equal_range 869 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 870 { 871 return bounded_range(header, key, key, comp, true, true); 872 } 873 874 //! <b>Requires</b>: "header" must be the header node of a tree. 875 //! KeyNodePtrCompare is a function object that induces a strict weak 876 //! ordering compatible with the strict weak ordering used to create the 877 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. 878 //! 879 //! <b>Effects</b>: Returns an a pair of node_ptr delimiting a range containing 880 //! the first element that is equivalent to "key" according to "comp" or an 881 //! empty range that indicates the position where that element would be 882 //! if there are no equivalent elements. 883 //! 884 //! <b>Complexity</b>: Logarithmic. 885 //! 886 //! <b>Throws</b>: If "comp" throws. 887 template<class KeyType, class KeyNodePtrCompare> lower_bound_range(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)888 static std::pair<node_ptr, node_ptr> lower_bound_range 889 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 890 { 891 node_ptr const lb(lower_bound(header, key, comp)); 892 std::pair<node_ptr, node_ptr> ret_ii(lb, lb); 893 if(lb != header && !comp(key, lb)){ 894 ret_ii.second = base_type::next_node(ret_ii.second); 895 } 896 return ret_ii; 897 } 898 899 //! <b>Requires</b>: "header" must be the header node of a tree. 900 //! KeyNodePtrCompare is a function object that induces a strict weak 901 //! ordering compatible with the strict weak ordering used to create the 902 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. 903 //! 904 //! <b>Effects</b>: Returns a node_ptr to the first element that is 905 //! not less than "key" according to "comp" or "header" if that element does 906 //! not exist. 907 //! 908 //! <b>Complexity</b>: Logarithmic. 909 //! 910 //! <b>Throws</b>: If "comp" throws. 911 template<class KeyType, class KeyNodePtrCompare> lower_bound(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)912 static node_ptr lower_bound 913 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 914 { 915 return lower_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp); 916 } 917 918 //! <b>Requires</b>: "header" must be the header node of a tree. 919 //! KeyNodePtrCompare is a function object that induces a strict weak 920 //! ordering compatible with the strict weak ordering used to create the 921 //! the tree. KeyNodePtrCompare can compare KeyType with tree's node_ptrs. 922 //! 923 //! <b>Effects</b>: Returns a node_ptr to the first element that is greater 924 //! than "key" according to "comp" or "header" if that element does not exist. 925 //! 926 //! <b>Complexity</b>: Logarithmic. 927 //! 928 //! <b>Throws</b>: If "comp" throws. 929 template<class KeyType, class KeyNodePtrCompare> upper_bound(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp)930 static node_ptr upper_bound 931 (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp) 932 { 933 return upper_bound_loop(NodeTraits::get_parent(header), detail::uncast(header), key, comp); 934 } 935 936 //! <b>Requires</b>: "header" must be the header node of a tree. 937 //! "commit_data" must have been obtained from a previous call to 938 //! "insert_unique_check". No objects should have been inserted or erased 939 //! from the set between the "insert_unique_check" that filled "commit_data" 940 //! and the call to "insert_commit". 941 //! 942 //! 943 //! <b>Effects</b>: Inserts new_node in the set using the information obtained 944 //! from the "commit_data" that a previous "insert_check" filled. 945 //! 946 //! <b>Complexity</b>: Constant time. 947 //! 948 //! <b>Throws</b>: Nothing. 949 //! 950 //! <b>Notes</b>: This function has only sense if a "insert_unique_check" has been 951 //! previously executed to fill "commit_data". No value should be inserted or 952 //! erased between the "insert_check" and "insert_commit" calls. insert_unique_commit(const node_ptr & header,const node_ptr & new_value,const insert_commit_data & commit_data)953 static void insert_unique_commit 954 (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data) 955 { return insert_commit(header, new_value, commit_data); } 956 957 //! <b>Requires</b>: "header" must be the header node of a tree. 958 //! KeyNodePtrCompare is a function object that induces a strict weak 959 //! ordering compatible with the strict weak ordering used to create the 960 //! the tree. NodePtrCompare compares KeyType with a node_ptr. 961 //! 962 //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the 963 //! tree according to "comp" and obtains the needed information to realize 964 //! a constant-time node insertion if there is no equivalent node. 965 //! 966 //! <b>Returns</b>: If there is an equivalent value 967 //! returns a pair containing a node_ptr to the already present node 968 //! and false. If there is not equivalent key can be inserted returns true 969 //! in the returned pair's boolean and fills "commit_data" that is meant to 970 //! be used with the "insert_commit" function to achieve a constant-time 971 //! insertion function. 972 //! 973 //! <b>Complexity</b>: Average complexity is at most logarithmic. 974 //! 975 //! <b>Throws</b>: If "comp" throws. 976 //! 977 //! <b>Notes</b>: This function is used to improve performance when constructing 978 //! a node is expensive and the user does not want to have two equivalent nodes 979 //! in the tree: if there is an equivalent value 980 //! the constructed object must be discarded. Many times, the part of the 981 //! node that is used to impose the order is much cheaper to construct 982 //! than the node and this function offers the possibility to use that part 983 //! to check if the insertion will be successful. 984 //! 985 //! If the check is successful, the user can construct the node and use 986 //! "insert_commit" to insert the node in constant-time. This gives a total 987 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)). 988 //! 989 //! "commit_data" remains valid for a subsequent "insert_unique_commit" only 990 //! if no more objects are inserted or erased from the set. 991 template<class KeyType, class KeyNodePtrCompare> insert_unique_check(const const_node_ptr & header,const KeyType & key,KeyNodePtrCompare comp,insert_commit_data & commit_data,std::size_t * pdepth=0)992 static std::pair<node_ptr, bool> insert_unique_check 993 (const const_node_ptr & header, const KeyType &key 994 ,KeyNodePtrCompare comp, insert_commit_data &commit_data 995 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 996 , std::size_t *pdepth = 0 997 #endif 998 ) 999 { 1000 std::size_t depth = 0; 1001 node_ptr h(detail::uncast(header)); 1002 node_ptr y(h); 1003 node_ptr x(NodeTraits::get_parent(y)); 1004 node_ptr prev = node_ptr(); 1005 1006 //Find the upper bound, cache the previous value and if we should 1007 //store it in the left or right node 1008 bool left_child = true; 1009 while(x){ 1010 ++depth; 1011 y = x; 1012 x = (left_child = comp(key, x)) ? 1013 NodeTraits::get_left(x) : (prev = y, NodeTraits::get_right(x)); 1014 } 1015 1016 if(pdepth) *pdepth = depth; 1017 1018 //Since we've found the upper bound there is no other value with the same key if: 1019 // - There is no previous node 1020 // - The previous node is less than the key 1021 const bool not_present = !prev || comp(prev, key); 1022 if(not_present){ 1023 commit_data.link_left = left_child; 1024 commit_data.node = y; 1025 } 1026 return std::pair<node_ptr, bool>(prev, not_present); 1027 } 1028 1029 //! <b>Requires</b>: "header" must be the header node of a tree. 1030 //! KeyNodePtrCompare is a function object that induces a strict weak 1031 //! ordering compatible with the strict weak ordering used to create the 1032 //! the tree. NodePtrCompare compares KeyType with a node_ptr. 1033 //! "hint" is node from the "header"'s tree. 1034 //! 1035 //! <b>Effects</b>: Checks if there is an equivalent node to "key" in the 1036 //! tree according to "comp" using "hint" as a hint to where it should be 1037 //! inserted and obtains the needed information to realize 1038 //! a constant-time node insertion if there is no equivalent node. 1039 //! If "hint" is the upper_bound the function has constant time 1040 //! complexity (two comparisons in the worst case). 1041 //! 1042 //! <b>Returns</b>: If there is an equivalent value 1043 //! returns a pair containing a node_ptr to the already present node 1044 //! and false. If there is not equivalent key can be inserted returns true 1045 //! in the returned pair's boolean and fills "commit_data" that is meant to 1046 //! be used with the "insert_commit" function to achieve a constant-time 1047 //! insertion function. 1048 //! 1049 //! <b>Complexity</b>: Average complexity is at most logarithmic, but it is 1050 //! amortized constant time if new_node should be inserted immediately before "hint". 1051 //! 1052 //! <b>Throws</b>: If "comp" throws. 1053 //! 1054 //! <b>Notes</b>: This function is used to improve performance when constructing 1055 //! a node is expensive and the user does not want to have two equivalent nodes 1056 //! in the tree: if there is an equivalent value 1057 //! the constructed object must be discarded. Many times, the part of the 1058 //! node that is used to impose the order is much cheaper to construct 1059 //! than the node and this function offers the possibility to use that part 1060 //! to check if the insertion will be successful. 1061 //! 1062 //! If the check is successful, the user can construct the node and use 1063 //! "insert_commit" to insert the node in constant-time. This gives a total 1064 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)). 1065 //! 1066 //! "commit_data" remains valid for a subsequent "insert_unique_commit" only 1067 //! if no more objects are inserted or erased from the set. 1068 template<class KeyType, class KeyNodePtrCompare> insert_unique_check(const const_node_ptr & header,const node_ptr & hint,const KeyType & key,KeyNodePtrCompare comp,insert_commit_data & commit_data,std::size_t * pdepth=0)1069 static std::pair<node_ptr, bool> insert_unique_check 1070 (const const_node_ptr & header, const node_ptr &hint, const KeyType &key 1071 ,KeyNodePtrCompare comp, insert_commit_data &commit_data 1072 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1073 , std::size_t *pdepth = 0 1074 #endif 1075 ) 1076 { 1077 //hint must be bigger than the key 1078 if(hint == header || comp(key, hint)){ 1079 node_ptr prev(hint); 1080 //Previous value should be less than the key 1081 if(hint == begin_node(header) || comp((prev = base_type::prev_node(hint)), key)){ 1082 commit_data.link_left = unique(header) || !NodeTraits::get_left(hint); 1083 commit_data.node = commit_data.link_left ? hint : prev; 1084 if(pdepth){ 1085 *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1; 1086 } 1087 return std::pair<node_ptr, bool>(node_ptr(), true); 1088 } 1089 } 1090 //Hint was wrong, use hintless insertion 1091 return insert_unique_check(header, key, comp, commit_data, pdepth); 1092 } 1093 1094 //! <b>Requires</b>: "header" must be the header node of a tree. 1095 //! NodePtrCompare is a function object that induces a strict weak 1096 //! ordering compatible with the strict weak ordering used to create the 1097 //! the tree. NodePtrCompare compares two node_ptrs. "hint" is node from 1098 //! the "header"'s tree. 1099 //! 1100 //! <b>Effects</b>: Inserts new_node into the tree, using "hint" as a hint to 1101 //! where it will be inserted. If "hint" is the upper_bound 1102 //! the insertion takes constant time (two comparisons in the worst case). 1103 //! 1104 //! <b>Complexity</b>: Logarithmic in general, but it is amortized 1105 //! constant time if new_node is inserted immediately before "hint". 1106 //! 1107 //! <b>Throws</b>: If "comp" throws. 1108 template<class NodePtrCompare> insert_equal(const node_ptr & h,const node_ptr & hint,const node_ptr & new_node,NodePtrCompare comp,std::size_t * pdepth=0)1109 static node_ptr insert_equal 1110 (const node_ptr & h, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp 1111 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1112 , std::size_t *pdepth = 0 1113 #endif 1114 ) 1115 { 1116 insert_commit_data commit_data; 1117 insert_equal_check(h, hint, new_node, comp, commit_data, pdepth); 1118 insert_commit(h, new_node, commit_data); 1119 return new_node; 1120 } 1121 1122 //! <b>Requires</b>: "h" must be the header node of a tree. 1123 //! NodePtrCompare is a function object that induces a strict weak 1124 //! ordering compatible with the strict weak ordering used to create the 1125 //! the tree. NodePtrCompare compares two node_ptrs. 1126 //! 1127 //! <b>Effects</b>: Inserts new_node into the tree before the upper bound 1128 //! according to "comp". 1129 //! 1130 //! <b>Complexity</b>: Average complexity for insert element is at 1131 //! most logarithmic. 1132 //! 1133 //! <b>Throws</b>: If "comp" throws. 1134 template<class NodePtrCompare> insert_equal_upper_bound(const node_ptr & h,const node_ptr & new_node,NodePtrCompare comp,std::size_t * pdepth=0)1135 static node_ptr insert_equal_upper_bound 1136 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp 1137 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1138 , std::size_t *pdepth = 0 1139 #endif 1140 ) 1141 { 1142 insert_commit_data commit_data; 1143 insert_equal_upper_bound_check(h, new_node, comp, commit_data, pdepth); 1144 insert_commit(h, new_node, commit_data); 1145 return new_node; 1146 } 1147 1148 //! <b>Requires</b>: "h" must be the header node of a tree. 1149 //! NodePtrCompare is a function object that induces a strict weak 1150 //! ordering compatible with the strict weak ordering used to create the 1151 //! the tree. NodePtrCompare compares two node_ptrs. 1152 //! 1153 //! <b>Effects</b>: Inserts new_node into the tree before the lower bound 1154 //! according to "comp". 1155 //! 1156 //! <b>Complexity</b>: Average complexity for insert element is at 1157 //! most logarithmic. 1158 //! 1159 //! <b>Throws</b>: If "comp" throws. 1160 template<class NodePtrCompare> insert_equal_lower_bound(const node_ptr & h,const node_ptr & new_node,NodePtrCompare comp,std::size_t * pdepth=0)1161 static node_ptr insert_equal_lower_bound 1162 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp 1163 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1164 , std::size_t *pdepth = 0 1165 #endif 1166 ) 1167 { 1168 insert_commit_data commit_data; 1169 insert_equal_lower_bound_check(h, new_node, comp, commit_data, pdepth); 1170 insert_commit(h, new_node, commit_data); 1171 return new_node; 1172 } 1173 1174 //! <b>Requires</b>: "header" must be the header node of a tree. 1175 //! "pos" must be a valid iterator or header (end) node. 1176 //! "pos" must be an iterator pointing to the successor to "new_node" 1177 //! once inserted according to the order of already inserted nodes. This function does not 1178 //! check "pos" and this precondition must be guaranteed by the caller. 1179 //! 1180 //! <b>Effects</b>: Inserts new_node into the tree before "pos". 1181 //! 1182 //! <b>Complexity</b>: Constant-time. 1183 //! 1184 //! <b>Throws</b>: Nothing. 1185 //! 1186 //! <b>Note</b>: If "pos" is not the successor of the newly inserted "new_node" 1187 //! tree invariants might be broken. insert_before(const node_ptr & header,const node_ptr & pos,const node_ptr & new_node,std::size_t * pdepth=0)1188 static node_ptr insert_before 1189 (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node 1190 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1191 , std::size_t *pdepth = 0 1192 #endif 1193 ) 1194 { 1195 insert_commit_data commit_data; 1196 insert_before_check(header, pos, commit_data, pdepth); 1197 insert_commit(header, new_node, commit_data); 1198 return new_node; 1199 } 1200 1201 //! <b>Requires</b>: "header" must be the header node of a tree. 1202 //! "new_node" must be, according to the used ordering no less than the 1203 //! greatest inserted key. 1204 //! 1205 //! <b>Effects</b>: Inserts new_node into the tree before "pos". 1206 //! 1207 //! <b>Complexity</b>: Constant-time. 1208 //! 1209 //! <b>Throws</b>: Nothing. 1210 //! 1211 //! <b>Note</b>: If "new_node" is less than the greatest inserted key 1212 //! tree invariants are broken. This function is slightly faster than 1213 //! using "insert_before". push_back(const node_ptr & header,const node_ptr & new_node,std::size_t * pdepth=0)1214 static void push_back 1215 (const node_ptr & header, const node_ptr & new_node 1216 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1217 , std::size_t *pdepth = 0 1218 #endif 1219 ) 1220 { 1221 insert_commit_data commit_data; 1222 push_back_check(header, commit_data, pdepth); 1223 insert_commit(header, new_node, commit_data); 1224 } 1225 1226 //! <b>Requires</b>: "header" must be the header node of a tree. 1227 //! "new_node" must be, according to the used ordering, no greater than the 1228 //! lowest inserted key. 1229 //! 1230 //! <b>Effects</b>: Inserts new_node into the tree before "pos". 1231 //! 1232 //! <b>Complexity</b>: Constant-time. 1233 //! 1234 //! <b>Throws</b>: Nothing. 1235 //! 1236 //! <b>Note</b>: If "new_node" is greater than the lowest inserted key 1237 //! tree invariants are broken. This function is slightly faster than 1238 //! using "insert_before". push_front(const node_ptr & header,const node_ptr & new_node,std::size_t * pdepth=0)1239 static void push_front 1240 (const node_ptr & header, const node_ptr & new_node 1241 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1242 , std::size_t *pdepth = 0 1243 #endif 1244 ) 1245 { 1246 insert_commit_data commit_data; 1247 push_front_check(header, commit_data, pdepth); 1248 insert_commit(header, new_node, commit_data); 1249 } 1250 1251 //! <b>Requires</b>: 'node' can't be a header node. 1252 //! 1253 //! <b>Effects</b>: Calculates the depth of a node: the depth of a 1254 //! node is the length (number of edges) of the path from the root 1255 //! to that node. (The root node is at depth 0.) 1256 //! 1257 //! <b>Complexity</b>: Logarithmic to the number of nodes in the tree. 1258 //! 1259 //! <b>Throws</b>: Nothing. depth(const_node_ptr node)1260 static std::size_t depth(const_node_ptr node) 1261 { 1262 std::size_t depth = 0; 1263 node_ptr p_parent; 1264 while(node != NodeTraits::get_parent(p_parent = NodeTraits::get_parent(node))){ 1265 ++depth; 1266 node = p_parent; 1267 } 1268 return depth; 1269 } 1270 1271 //! <b>Requires</b>: "cloner" must be a function 1272 //! object taking a node_ptr and returning a new cloned node of it. "disposer" must 1273 //! take a node_ptr and shouldn't throw. 1274 //! 1275 //! <b>Effects</b>: First empties target tree calling 1276 //! <tt>void disposer::operator()(const node_ptr &)</tt> for every node of the tree 1277 //! except the header. 1278 //! 1279 //! Then, duplicates the entire tree pointed by "source_header" cloning each 1280 //! source node with <tt>node_ptr Cloner::operator()(const node_ptr &)</tt> to obtain 1281 //! the nodes of the target tree. If "cloner" throws, the cloned target nodes 1282 //! are disposed using <tt>void disposer(const node_ptr &)</tt>. 1283 //! 1284 //! <b>Complexity</b>: Linear to the number of element of the source tree plus the 1285 //! number of elements of tree target tree when calling this function. 1286 //! 1287 //! <b>Throws</b>: If cloner functor throws. If this happens target nodes are disposed. 1288 template <class Cloner, class Disposer> clone(const const_node_ptr & source_header,const node_ptr & target_header,Cloner cloner,Disposer disposer)1289 static void clone 1290 (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer) 1291 { 1292 if(!unique(target_header)){ 1293 clear_and_dispose(target_header, disposer); 1294 } 1295 1296 node_ptr leftmost, rightmost; 1297 node_ptr new_root = clone_subtree 1298 (source_header, target_header, cloner, disposer, leftmost, rightmost); 1299 1300 //Now update header node 1301 NodeTraits::set_parent(target_header, new_root); 1302 NodeTraits::set_left (target_header, leftmost); 1303 NodeTraits::set_right (target_header, rightmost); 1304 } 1305 1306 //! <b>Requires</b>: header must be the header of a tree, z a node 1307 //! of that tree and z != header. 1308 //! 1309 //! <b>Effects</b>: Erases node "z" from the tree with header "header". 1310 //! 1311 //! <b>Complexity</b>: Amortized constant time. 1312 //! 1313 //! <b>Throws</b>: Nothing. erase(const node_ptr & header,const node_ptr & z)1314 static void erase(const node_ptr & header, const node_ptr & z) 1315 { 1316 data_for_rebalance ignored; 1317 erase(header, z, ignored); 1318 } 1319 1320 //! <b>Requires</b>: node is a tree node but not the header. 1321 //! 1322 //! <b>Effects</b>: Unlinks the node and rebalances the tree. 1323 //! 1324 //! <b>Complexity</b>: Average complexity is constant time. 1325 //! 1326 //! <b>Throws</b>: Nothing. unlink(const node_ptr & node)1327 static void unlink(const node_ptr & node) 1328 { 1329 node_ptr x = NodeTraits::get_parent(node); 1330 if(x){ 1331 while(!base_type::is_header(x)) 1332 x = NodeTraits::get_parent(x); 1333 erase(x, node); 1334 } 1335 } 1336 1337 //! <b>Requires</b>: header must be the header of a tree. 1338 //! 1339 //! <b>Effects</b>: Rebalances the tree. 1340 //! 1341 //! <b>Throws</b>: Nothing. 1342 //! 1343 //! <b>Complexity</b>: Linear. rebalance(const node_ptr & header)1344 static void rebalance(const node_ptr & header) 1345 { 1346 node_ptr root = NodeTraits::get_parent(header); 1347 if(root){ 1348 rebalance_subtree(root); 1349 } 1350 } 1351 1352 //! <b>Requires</b>: old_root is a node of a tree. It shall not be null. 1353 //! 1354 //! <b>Effects</b>: Rebalances the subtree rooted at old_root. 1355 //! 1356 //! <b>Returns</b>: The new root of the subtree. 1357 //! 1358 //! <b>Throws</b>: Nothing. 1359 //! 1360 //! <b>Complexity</b>: Linear. rebalance_subtree(const node_ptr & old_root)1361 static node_ptr rebalance_subtree(const node_ptr & old_root) 1362 { 1363 //Taken from: 1364 //"Tree rebalancing in optimal time and space" 1365 //Quentin F. Stout and Bette L. Warren 1366 1367 //To avoid irregularities in the algorithm (old_root can be a 1368 //left or right child or even the root of the tree) just put the 1369 //root as the right child of its parent. Before doing this backup 1370 //information to restore the original relationship after 1371 //the algorithm is applied. 1372 node_ptr super_root = NodeTraits::get_parent(old_root); 1373 BOOST_INTRUSIVE_INVARIANT_ASSERT(super_root); 1374 1375 //Get root info 1376 node_ptr super_root_right_backup = NodeTraits::get_right(super_root); 1377 bool super_root_is_header = NodeTraits::get_parent(super_root) == old_root; 1378 bool old_root_is_right = is_right_child(old_root); 1379 NodeTraits::set_right(super_root, old_root); 1380 1381 std::size_t size; 1382 subtree_to_vine(super_root, size); 1383 vine_to_subtree(super_root, size); 1384 node_ptr new_root = NodeTraits::get_right(super_root); 1385 1386 //Recover root 1387 if(super_root_is_header){ 1388 NodeTraits::set_right(super_root, super_root_right_backup); 1389 NodeTraits::set_parent(super_root, new_root); 1390 } 1391 else if(old_root_is_right){ 1392 NodeTraits::set_right(super_root, new_root); 1393 } 1394 else{ 1395 NodeTraits::set_right(super_root, super_root_right_backup); 1396 NodeTraits::set_left(super_root, new_root); 1397 } 1398 return new_root; 1399 } 1400 1401 //! <b>Effects</b>: Asserts the integrity of the container with additional checks provided by the user. 1402 //! 1403 //! <b>Requires</b>: header must be the header of a tree. 1404 //! 1405 //! <b>Complexity</b>: Linear time. 1406 //! 1407 //! <b>Note</b>: The method might not have effect when asserts are turned off (e.g., with NDEBUG). 1408 //! Experimental function, interface might change in future versions. 1409 template<class Checker> check(const const_node_ptr & header,Checker checker,typename Checker::return_type & checker_return)1410 static void check(const const_node_ptr& header, Checker checker, typename Checker::return_type& checker_return) 1411 { 1412 const_node_ptr root_node_ptr = NodeTraits::get_parent(header); 1413 if (!root_node_ptr){ 1414 // check left&right header pointers 1415 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == header); 1416 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == header); 1417 } 1418 else{ 1419 // check parent pointer of root node 1420 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(root_node_ptr) == header); 1421 // check subtree from root 1422 check_subtree(root_node_ptr, checker, checker_return); 1423 // check left&right header pointers 1424 const_node_ptr p = root_node_ptr; 1425 while (NodeTraits::get_left(p)) { p = NodeTraits::get_left(p); } 1426 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(header) == p); 1427 p = root_node_ptr; 1428 while (NodeTraits::get_right(p)) { p = NodeTraits::get_right(p); } 1429 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(header) == p); 1430 } 1431 } 1432 1433 protected: erase(const node_ptr & header,const node_ptr & z,data_for_rebalance & info)1434 static void erase(const node_ptr & header, const node_ptr & z, data_for_rebalance &info) 1435 { 1436 node_ptr y(z); 1437 node_ptr x; 1438 const node_ptr z_left(NodeTraits::get_left(z)); 1439 const node_ptr z_right(NodeTraits::get_right(z)); 1440 1441 if(!z_left){ 1442 x = z_right; // x might be null. 1443 } 1444 else if(!z_right){ // z has exactly one non-null child. y == z. 1445 x = z_left; // x is not null. 1446 BOOST_ASSERT(x); 1447 } 1448 else{ //make y != z 1449 // y = find z's successor 1450 y = base_type::minimum(z_right); 1451 x = NodeTraits::get_right(y); // x might be null. 1452 } 1453 1454 node_ptr x_parent; 1455 const node_ptr z_parent(NodeTraits::get_parent(z)); 1456 const bool z_is_leftchild(NodeTraits::get_left(z_parent) == z); 1457 1458 if(y != z){ //has two children and y is the minimum of z 1459 //y is z's successor and it has a null left child. 1460 //x is the right child of y (it can be null) 1461 //Relink y in place of z and link x with y's old parent 1462 NodeTraits::set_parent(z_left, y); 1463 NodeTraits::set_left(y, z_left); 1464 if(y != z_right){ 1465 //Link y with the right tree of z 1466 NodeTraits::set_right(y, z_right); 1467 NodeTraits::set_parent(z_right, y); 1468 //Link x with y's old parent (y must be a left child) 1469 x_parent = NodeTraits::get_parent(y); 1470 BOOST_ASSERT(NodeTraits::get_left(x_parent) == y); 1471 if(x) 1472 NodeTraits::set_parent(x, x_parent); 1473 //Since y was the successor and not the right child of z, it must be a left child 1474 NodeTraits::set_left(x_parent, x); 1475 } 1476 else{ //y was the right child of y so no need to fix x's position 1477 x_parent = y; 1478 } 1479 NodeTraits::set_parent(y, z_parent); 1480 this_type::set_child(header, y, z_parent, z_is_leftchild); 1481 } 1482 else { // z has zero or one child, x is one child (it can be null) 1483 //Just link x to z's parent 1484 x_parent = z_parent; 1485 if(x) 1486 NodeTraits::set_parent(x, z_parent); 1487 this_type::set_child(header, x, z_parent, z_is_leftchild); 1488 1489 //Now update leftmost/rightmost in case z was one of them 1490 if(NodeTraits::get_left(header) == z){ 1491 //z_left must be null because z is the leftmost 1492 BOOST_ASSERT(!z_left); 1493 NodeTraits::set_left(header, !z_right ? 1494 z_parent : // makes leftmost == header if z == root 1495 base_type::minimum(z_right)); 1496 } 1497 if(NodeTraits::get_right(header) == z){ 1498 //z_right must be null because z is the rightmost 1499 BOOST_ASSERT(!z_right); 1500 NodeTraits::set_right(header, !z_left ? 1501 z_parent : // makes rightmost == header if z == root 1502 base_type::maximum(z_left)); 1503 } 1504 } 1505 1506 //If z had 0/1 child, y == z and one of its children (and maybe null) 1507 //If z had 2 children, y is the successor of z and x is the right child of y 1508 info.x = x; 1509 info.y = y; 1510 //If z had 0/1 child, x_parent is the new parent of the old right child of y (z's successor) 1511 //If z had 2 children, x_parent is the new parent of y (z_parent) 1512 BOOST_ASSERT(!x || NodeTraits::get_parent(x) == x_parent); 1513 info.x_parent = x_parent; 1514 } 1515 1516 //! <b>Requires</b>: node is a node of the tree but it's not the header. 1517 //! 1518 //! <b>Effects</b>: Returns the number of nodes of the subtree. 1519 //! 1520 //! <b>Complexity</b>: Linear time. 1521 //! 1522 //! <b>Throws</b>: Nothing. subtree_size(const const_node_ptr & subtree)1523 static std::size_t subtree_size(const const_node_ptr & subtree) 1524 { 1525 std::size_t count = 0; 1526 if (subtree){ 1527 node_ptr n = detail::uncast(subtree); 1528 node_ptr m = NodeTraits::get_left(n); 1529 while(m){ 1530 n = m; 1531 m = NodeTraits::get_left(n); 1532 } 1533 1534 while(1){ 1535 ++count; 1536 node_ptr n_right(NodeTraits::get_right(n)); 1537 if(n_right){ 1538 n = n_right; 1539 m = NodeTraits::get_left(n); 1540 while(m){ 1541 n = m; 1542 m = NodeTraits::get_left(n); 1543 } 1544 } 1545 else { 1546 do{ 1547 if (n == subtree){ 1548 return count; 1549 } 1550 m = n; 1551 n = NodeTraits::get_parent(n); 1552 }while(NodeTraits::get_left(n) != m); 1553 } 1554 } 1555 } 1556 return count; 1557 } 1558 1559 //! <b>Requires</b>: p is a node of a tree. 1560 //! 1561 //! <b>Effects</b>: Returns true if p is a left child. 1562 //! 1563 //! <b>Complexity</b>: Constant. 1564 //! 1565 //! <b>Throws</b>: Nothing. is_left_child(const node_ptr & p)1566 static bool is_left_child(const node_ptr & p) 1567 { return NodeTraits::get_left(NodeTraits::get_parent(p)) == p; } 1568 1569 //! <b>Requires</b>: p is a node of a tree. 1570 //! 1571 //! <b>Effects</b>: Returns true if p is a right child. 1572 //! 1573 //! <b>Complexity</b>: Constant. 1574 //! 1575 //! <b>Throws</b>: Nothing. is_right_child(const node_ptr & p)1576 static bool is_right_child(const node_ptr & p) 1577 { return NodeTraits::get_right(NodeTraits::get_parent(p)) == p; } 1578 insert_before_check(const node_ptr & header,const node_ptr & pos,insert_commit_data & commit_data,std::size_t * pdepth=0)1579 static void insert_before_check 1580 (const node_ptr &header, const node_ptr & pos 1581 , insert_commit_data &commit_data 1582 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1583 , std::size_t *pdepth = 0 1584 #endif 1585 ) 1586 { 1587 node_ptr prev(pos); 1588 if(pos != NodeTraits::get_left(header)) 1589 prev = base_type::prev_node(pos); 1590 bool link_left = unique(header) || !NodeTraits::get_left(pos); 1591 commit_data.link_left = link_left; 1592 commit_data.node = link_left ? pos : prev; 1593 if(pdepth){ 1594 *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1; 1595 } 1596 } 1597 push_back_check(const node_ptr & header,insert_commit_data & commit_data,std::size_t * pdepth=0)1598 static void push_back_check 1599 (const node_ptr & header, insert_commit_data &commit_data 1600 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1601 , std::size_t *pdepth = 0 1602 #endif 1603 ) 1604 { 1605 node_ptr prev(NodeTraits::get_right(header)); 1606 if(pdepth){ 1607 *pdepth = prev == header ? 0 : depth(prev) + 1; 1608 } 1609 commit_data.link_left = false; 1610 commit_data.node = prev; 1611 } 1612 push_front_check(const node_ptr & header,insert_commit_data & commit_data,std::size_t * pdepth=0)1613 static void push_front_check 1614 (const node_ptr & header, insert_commit_data &commit_data 1615 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1616 , std::size_t *pdepth = 0 1617 #endif 1618 ) 1619 { 1620 node_ptr pos(NodeTraits::get_left(header)); 1621 if(pdepth){ 1622 *pdepth = pos == header ? 0 : depth(pos) + 1; 1623 } 1624 commit_data.link_left = true; 1625 commit_data.node = pos; 1626 } 1627 1628 template<class NodePtrCompare> insert_equal_check(const node_ptr & header,const node_ptr & hint,const node_ptr & new_node,NodePtrCompare comp,insert_commit_data & commit_data,std::size_t * pdepth=0)1629 static void insert_equal_check 1630 (const node_ptr &header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp 1631 , insert_commit_data &commit_data 1632 /// @cond 1633 , std::size_t *pdepth = 0 1634 /// @endcond 1635 ) 1636 { 1637 if(hint == header || !comp(hint, new_node)){ 1638 node_ptr prev(hint); 1639 if(hint == NodeTraits::get_left(header) || 1640 !comp(new_node, (prev = base_type::prev_node(hint)))){ 1641 bool link_left = unique(header) || !NodeTraits::get_left(hint); 1642 commit_data.link_left = link_left; 1643 commit_data.node = link_left ? hint : prev; 1644 if(pdepth){ 1645 *pdepth = commit_data.node == header ? 0 : depth(commit_data.node) + 1; 1646 } 1647 } 1648 else{ 1649 insert_equal_upper_bound_check(header, new_node, comp, commit_data, pdepth); 1650 } 1651 } 1652 else{ 1653 insert_equal_lower_bound_check(header, new_node, comp, commit_data, pdepth); 1654 } 1655 } 1656 1657 template<class NodePtrCompare> insert_equal_upper_bound_check(const node_ptr & h,const node_ptr & new_node,NodePtrCompare comp,insert_commit_data & commit_data,std::size_t * pdepth=0)1658 static void insert_equal_upper_bound_check 1659 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0) 1660 { 1661 std::size_t depth = 0; 1662 node_ptr y(h); 1663 node_ptr x(NodeTraits::get_parent(y)); 1664 1665 while(x){ 1666 ++depth; 1667 y = x; 1668 x = comp(new_node, x) ? 1669 NodeTraits::get_left(x) : NodeTraits::get_right(x); 1670 } 1671 if(pdepth) *pdepth = depth; 1672 commit_data.link_left = (y == h) || comp(new_node, y); 1673 commit_data.node = y; 1674 } 1675 1676 template<class NodePtrCompare> insert_equal_lower_bound_check(const node_ptr & h,const node_ptr & new_node,NodePtrCompare comp,insert_commit_data & commit_data,std::size_t * pdepth=0)1677 static void insert_equal_lower_bound_check 1678 (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp, insert_commit_data & commit_data, std::size_t *pdepth = 0) 1679 { 1680 std::size_t depth = 0; 1681 node_ptr y(h); 1682 node_ptr x(NodeTraits::get_parent(y)); 1683 1684 while(x){ 1685 ++depth; 1686 y = x; 1687 x = !comp(x, new_node) ? 1688 NodeTraits::get_left(x) : NodeTraits::get_right(x); 1689 } 1690 if(pdepth) *pdepth = depth; 1691 commit_data.link_left = (y == h) || !comp(y, new_node); 1692 commit_data.node = y; 1693 } 1694 insert_commit(const node_ptr & header,const node_ptr & new_node,const insert_commit_data & commit_data)1695 static void insert_commit 1696 (const node_ptr & header, const node_ptr & new_node, const insert_commit_data &commit_data) 1697 { 1698 //Check if commit_data has not been initialized by a insert_unique_check call. 1699 BOOST_INTRUSIVE_INVARIANT_ASSERT(commit_data.node != node_ptr()); 1700 node_ptr parent_node(commit_data.node); 1701 if(parent_node == header){ 1702 NodeTraits::set_parent(header, new_node); 1703 NodeTraits::set_right(header, new_node); 1704 NodeTraits::set_left(header, new_node); 1705 } 1706 else if(commit_data.link_left){ 1707 NodeTraits::set_left(parent_node, new_node); 1708 if(parent_node == NodeTraits::get_left(header)) 1709 NodeTraits::set_left(header, new_node); 1710 } 1711 else{ 1712 NodeTraits::set_right(parent_node, new_node); 1713 if(parent_node == NodeTraits::get_right(header)) 1714 NodeTraits::set_right(header, new_node); 1715 } 1716 NodeTraits::set_parent(new_node, parent_node); 1717 NodeTraits::set_right(new_node, node_ptr()); 1718 NodeTraits::set_left(new_node, node_ptr()); 1719 } 1720 1721 //Fix header and own's parent data when replacing x with own, providing own's old data with parent set_child(const node_ptr & header,const node_ptr & new_child,const node_ptr & new_parent,const bool link_left)1722 static void set_child(const node_ptr & header, const node_ptr & new_child, const node_ptr & new_parent, const bool link_left) 1723 { 1724 if(new_parent == header) 1725 NodeTraits::set_parent(header, new_child); 1726 else if(link_left) 1727 NodeTraits::set_left(new_parent, new_child); 1728 else 1729 NodeTraits::set_right(new_parent, new_child); 1730 } 1731 1732 // rotate p to left (no header and p's parent fixup) rotate_left_no_parent_fix(const node_ptr & p,const node_ptr & p_right)1733 static void rotate_left_no_parent_fix(const node_ptr & p, const node_ptr &p_right) 1734 { 1735 node_ptr p_right_left(NodeTraits::get_left(p_right)); 1736 NodeTraits::set_right(p, p_right_left); 1737 if(p_right_left){ 1738 NodeTraits::set_parent(p_right_left, p); 1739 } 1740 NodeTraits::set_left(p_right, p); 1741 NodeTraits::set_parent(p, p_right); 1742 } 1743 1744 // rotate p to left (with header and p's parent fixup) rotate_left(const node_ptr & p,const node_ptr & p_right,const node_ptr & p_parent,const node_ptr & header)1745 static void rotate_left(const node_ptr & p, const node_ptr & p_right, const node_ptr & p_parent, const node_ptr & header) 1746 { 1747 const bool p_was_left(NodeTraits::get_left(p_parent) == p); 1748 rotate_left_no_parent_fix(p, p_right); 1749 NodeTraits::set_parent(p_right, p_parent); 1750 set_child(header, p_right, p_parent, p_was_left); 1751 } 1752 1753 // rotate p to right (no header and p's parent fixup) rotate_right_no_parent_fix(const node_ptr & p,const node_ptr & p_left)1754 static void rotate_right_no_parent_fix(const node_ptr & p, const node_ptr &p_left) 1755 { 1756 node_ptr p_left_right(NodeTraits::get_right(p_left)); 1757 NodeTraits::set_left(p, p_left_right); 1758 if(p_left_right){ 1759 NodeTraits::set_parent(p_left_right, p); 1760 } 1761 NodeTraits::set_right(p_left, p); 1762 NodeTraits::set_parent(p, p_left); 1763 } 1764 1765 // rotate p to right (with header and p's parent fixup) rotate_right(const node_ptr & p,const node_ptr & p_left,const node_ptr & p_parent,const node_ptr & header)1766 static void rotate_right(const node_ptr & p, const node_ptr & p_left, const node_ptr & p_parent, const node_ptr & header) 1767 { 1768 const bool p_was_left(NodeTraits::get_left(p_parent) == p); 1769 rotate_right_no_parent_fix(p, p_left); 1770 NodeTraits::set_parent(p_left, p_parent); 1771 set_child(header, p_left, p_parent, p_was_left); 1772 } 1773 1774 private: 1775 subtree_to_vine(node_ptr vine_tail,std::size_t & size)1776 static void subtree_to_vine(node_ptr vine_tail, std::size_t &size) 1777 { 1778 //Inspired by LibAVL: 1779 //It uses a clever optimization for trees with parent pointers. 1780 //No parent pointer is updated when transforming a tree to a vine as 1781 //most of them will be overriten during compression rotations. 1782 //A final pass must be made after the rebalancing to updated those 1783 //pointers not updated by tree_to_vine + compression calls 1784 std::size_t len = 0; 1785 node_ptr remainder = NodeTraits::get_right(vine_tail); 1786 while(remainder){ 1787 node_ptr tempptr = NodeTraits::get_left(remainder); 1788 if(!tempptr){ //move vine-tail down one 1789 vine_tail = remainder; 1790 remainder = NodeTraits::get_right(remainder); 1791 ++len; 1792 } 1793 else{ //rotate 1794 NodeTraits::set_left(remainder, NodeTraits::get_right(tempptr)); 1795 NodeTraits::set_right(tempptr, remainder); 1796 remainder = tempptr; 1797 NodeTraits::set_right(vine_tail, tempptr); 1798 } 1799 } 1800 size = len; 1801 } 1802 compress_subtree(node_ptr scanner,std::size_t count)1803 static void compress_subtree(node_ptr scanner, std::size_t count) 1804 { 1805 while(count--){ //compress "count" spine nodes in the tree with pseudo-root scanner 1806 node_ptr child = NodeTraits::get_right(scanner); 1807 node_ptr child_right = NodeTraits::get_right(child); 1808 NodeTraits::set_right(scanner, child_right); 1809 //Avoid setting the parent of child_right 1810 scanner = child_right; 1811 node_ptr scanner_left = NodeTraits::get_left(scanner); 1812 NodeTraits::set_right(child, scanner_left); 1813 if(scanner_left) 1814 NodeTraits::set_parent(scanner_left, child); 1815 NodeTraits::set_left(scanner, child); 1816 NodeTraits::set_parent(child, scanner); 1817 } 1818 } 1819 vine_to_subtree(const node_ptr & super_root,std::size_t count)1820 static void vine_to_subtree(const node_ptr & super_root, std::size_t count) 1821 { 1822 const std::size_t one_szt = 1u; 1823 std::size_t leaf_nodes = count + one_szt - std::size_t(one_szt << detail::floor_log2(count + one_szt)); 1824 compress_subtree(super_root, leaf_nodes); //create deepest leaves 1825 std::size_t vine_nodes = count - leaf_nodes; 1826 while(vine_nodes > 1){ 1827 vine_nodes /= 2; 1828 compress_subtree(super_root, vine_nodes); 1829 } 1830 1831 //Update parents of nodes still in the in the original vine line 1832 //as those have not been updated by subtree_to_vine or compress_subtree 1833 for ( node_ptr q = super_root, p = NodeTraits::get_right(super_root) 1834 ; p 1835 ; q = p, p = NodeTraits::get_right(p)){ 1836 NodeTraits::set_parent(p, q); 1837 } 1838 } 1839 1840 //! <b>Requires</b>: "n" must be a node inserted in a tree. 1841 //! 1842 //! <b>Effects</b>: Returns a pointer to the header node of the tree. 1843 //! 1844 //! <b>Complexity</b>: Logarithmic. 1845 //! 1846 //! <b>Throws</b>: Nothing. get_root(const node_ptr & node)1847 static node_ptr get_root(const node_ptr & node) 1848 { 1849 BOOST_INTRUSIVE_INVARIANT_ASSERT((!inited(node))); 1850 node_ptr x = NodeTraits::get_parent(node); 1851 if(x){ 1852 while(!base_type::is_header(x)){ 1853 x = NodeTraits::get_parent(x); 1854 } 1855 return x; 1856 } 1857 else{ 1858 return node; 1859 } 1860 } 1861 1862 template <class Cloner, class Disposer> clone_subtree(const const_node_ptr & source_parent,const node_ptr & target_parent,Cloner cloner,Disposer disposer,node_ptr & leftmost_out,node_ptr & rightmost_out)1863 static node_ptr clone_subtree 1864 (const const_node_ptr &source_parent, const node_ptr &target_parent 1865 , Cloner cloner, Disposer disposer 1866 , node_ptr &leftmost_out, node_ptr &rightmost_out 1867 ) 1868 { 1869 node_ptr target_sub_root = target_parent; 1870 node_ptr source_root = NodeTraits::get_parent(source_parent); 1871 if(!source_root){ 1872 leftmost_out = rightmost_out = source_root; 1873 } 1874 else{ 1875 //We'll calculate leftmost and rightmost nodes while iterating 1876 node_ptr current = source_root; 1877 node_ptr insertion_point = target_sub_root = cloner(current); 1878 1879 //We'll calculate leftmost and rightmost nodes while iterating 1880 node_ptr leftmost = target_sub_root; 1881 node_ptr rightmost = target_sub_root; 1882 1883 //First set the subroot 1884 NodeTraits::set_left(target_sub_root, node_ptr()); 1885 NodeTraits::set_right(target_sub_root, node_ptr()); 1886 NodeTraits::set_parent(target_sub_root, target_parent); 1887 1888 dispose_subtree_disposer<Disposer> rollback(disposer, target_sub_root); 1889 while(true) { 1890 //First clone left nodes 1891 if( NodeTraits::get_left(current) && 1892 !NodeTraits::get_left(insertion_point)) { 1893 current = NodeTraits::get_left(current); 1894 node_ptr temp = insertion_point; 1895 //Clone and mark as leaf 1896 insertion_point = cloner(current); 1897 NodeTraits::set_left (insertion_point, node_ptr()); 1898 NodeTraits::set_right (insertion_point, node_ptr()); 1899 //Insert left 1900 NodeTraits::set_parent(insertion_point, temp); 1901 NodeTraits::set_left (temp, insertion_point); 1902 //Update leftmost 1903 if(rightmost == target_sub_root) 1904 leftmost = insertion_point; 1905 } 1906 //Then clone right nodes 1907 else if( NodeTraits::get_right(current) && 1908 !NodeTraits::get_right(insertion_point)){ 1909 current = NodeTraits::get_right(current); 1910 node_ptr temp = insertion_point; 1911 //Clone and mark as leaf 1912 insertion_point = cloner(current); 1913 NodeTraits::set_left (insertion_point, node_ptr()); 1914 NodeTraits::set_right (insertion_point, node_ptr()); 1915 //Insert right 1916 NodeTraits::set_parent(insertion_point, temp); 1917 NodeTraits::set_right (temp, insertion_point); 1918 //Update rightmost 1919 rightmost = insertion_point; 1920 } 1921 //If not, go up 1922 else if(current == source_root){ 1923 break; 1924 } 1925 else{ 1926 //Branch completed, go up searching more nodes to clone 1927 current = NodeTraits::get_parent(current); 1928 insertion_point = NodeTraits::get_parent(insertion_point); 1929 } 1930 } 1931 rollback.release(); 1932 leftmost_out = leftmost; 1933 rightmost_out = rightmost; 1934 } 1935 return target_sub_root; 1936 } 1937 1938 template<class Disposer> dispose_subtree(node_ptr x,Disposer disposer)1939 static void dispose_subtree(node_ptr x, Disposer disposer) 1940 { 1941 while (x){ 1942 node_ptr save(NodeTraits::get_left(x)); 1943 if (save) { 1944 // Right rotation 1945 NodeTraits::set_left(x, NodeTraits::get_right(save)); 1946 NodeTraits::set_right(save, x); 1947 } 1948 else { 1949 save = NodeTraits::get_right(x); 1950 init(x); 1951 disposer(x); 1952 } 1953 x = save; 1954 } 1955 } 1956 1957 template<class KeyType, class KeyNodePtrCompare> lower_bound_loop(node_ptr x,node_ptr y,const KeyType & key,KeyNodePtrCompare comp)1958 static node_ptr lower_bound_loop 1959 (node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp) 1960 { 1961 while(x){ 1962 if(comp(x, key)){ 1963 x = NodeTraits::get_right(x); 1964 } 1965 else{ 1966 y = x; 1967 x = NodeTraits::get_left(x); 1968 } 1969 } 1970 return y; 1971 } 1972 1973 template<class KeyType, class KeyNodePtrCompare> upper_bound_loop(node_ptr x,node_ptr y,const KeyType & key,KeyNodePtrCompare comp)1974 static node_ptr upper_bound_loop 1975 (node_ptr x, node_ptr y, const KeyType &key, KeyNodePtrCompare comp) 1976 { 1977 while(x){ 1978 if(comp(key, x)){ 1979 y = x; 1980 x = NodeTraits::get_left(x); 1981 } 1982 else{ 1983 x = NodeTraits::get_right(x); 1984 } 1985 } 1986 return y; 1987 } 1988 1989 template<class Checker> check_subtree(const const_node_ptr & node,Checker checker,typename Checker::return_type & check_return)1990 static void check_subtree(const const_node_ptr& node, Checker checker, typename Checker::return_type& check_return) 1991 { 1992 const_node_ptr left = NodeTraits::get_left(node); 1993 const_node_ptr right = NodeTraits::get_right(node); 1994 typename Checker::return_type check_return_left; 1995 typename Checker::return_type check_return_right; 1996 if (left) 1997 { 1998 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(left) == node); 1999 check_subtree(left, checker, check_return_left); 2000 } 2001 if (right) 2002 { 2003 BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_parent(right) == node); 2004 check_subtree(right, checker, check_return_right); 2005 } 2006 checker(node, check_return_left, check_return_right, check_return); 2007 } 2008 }; 2009 2010 /// @cond 2011 2012 template<class NodeTraits> 2013 struct get_algo<BsTreeAlgorithms, NodeTraits> 2014 { 2015 typedef bstree_algorithms<NodeTraits> type; 2016 }; 2017 2018 template <class ValueTraits, class NodePtrCompare, class ExtraChecker> 2019 struct get_node_checker<BsTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker> 2020 { 2021 typedef detail::bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type; 2022 }; 2023 2024 /// @endcond 2025 2026 } //namespace intrusive 2027 } //namespace boost 2028 2029 #include <boost/intrusive/detail/config_end.hpp> 2030 2031 #endif //BOOST_INTRUSIVE_BSTREE_ALGORITHMS_HPP 2032