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