Chris@16: ///////////////////////////////////////////////////////////////////////////// Chris@16: // Chris@16: // (C) Copyright Olaf Krzikalla 2004-2006. Chris@101: // (C) Copyright Ion Gaztanaga 2006-2014. Chris@16: // Chris@16: // Distributed under the Boost Software License, Version 1.0. Chris@16: // (See accompanying file LICENSE_1_0.txt or copy at Chris@16: // http://www.boost.org/LICENSE_1_0.txt) Chris@16: // Chris@16: // See http://www.boost.org/libs/intrusive for documentation. Chris@16: // Chris@16: ///////////////////////////////////////////////////////////////////////////// Chris@16: // Chris@16: // The tree destruction algorithm is based on Julienne Walker and The EC Team code: Chris@16: // Chris@16: // This code is in the public domain. Anyone may use it or change it in any way that Chris@16: // they see fit. The author assumes no responsibility for damages incurred through Chris@16: // use of the original code or any variations thereof. Chris@16: // Chris@16: // It is requested, but not required, that due credit is given to the original author Chris@16: // and anyone who has modified the code through a header comment, such as this one. Chris@16: Chris@16: #ifndef BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP Chris@16: #define BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP Chris@16: Chris@16: #include Chris@101: #include Chris@16: Chris@16: #include Chris@16: Chris@16: #include Chris@101: #include Chris@16: #include Chris@101: #include Chris@101: Chris@101: #if defined(BOOST_HAS_PRAGMA_ONCE) Chris@101: # pragma once Chris@101: #endif Chris@16: Chris@16: namespace boost { Chris@16: namespace intrusive { Chris@16: Chris@16: #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: template Chris@16: struct rbtree_node_cloner Chris@101: //Use public inheritance to avoid MSVC bugs with closures Chris@101: : public detail::ebo_functor_holder Chris@16: { Chris@16: typedef typename NodeTraits::node_ptr node_ptr; Chris@16: typedef detail::ebo_functor_holder base_t; Chris@16: Chris@101: explicit rbtree_node_cloner(F f) Chris@16: : base_t(f) Chris@16: {} Chris@16: Chris@16: node_ptr operator()(const node_ptr & p) Chris@16: { Chris@16: node_ptr n = base_t::get()(p); Chris@16: NodeTraits::set_color(n, NodeTraits::get_color(p)); Chris@16: return n; Chris@16: } Chris@16: }; Chris@16: Chris@101: namespace detail { Chris@101: Chris@101: template Chris@101: struct rbtree_node_checker Chris@101: : public bstree_node_checker Chris@16: { Chris@101: typedef bstree_node_checker base_checker_t; Chris@101: typedef ValueTraits value_traits; Chris@101: typedef typename value_traits::node_traits node_traits; Chris@101: typedef typename node_traits::const_node_ptr const_node_ptr; Chris@101: typedef typename node_traits::node_ptr node_ptr; Chris@16: Chris@101: struct return_type Chris@101: : public base_checker_t::return_type Chris@16: { Chris@101: return_type() : black_count_(0) {} Chris@101: std::size_t black_count_; Chris@101: }; Chris@101: Chris@101: rbtree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker) Chris@101: : base_checker_t(comp, extra_checker) Chris@101: {} Chris@101: Chris@101: void operator () (const const_node_ptr& p, Chris@101: const return_type& check_return_left, const return_type& check_return_right, Chris@101: return_type& check_return) Chris@101: { Chris@101: Chris@101: if (node_traits::get_color(p) == node_traits::red()){ Chris@101: //Red nodes have black children Chris@101: const node_ptr p_left(node_traits::get_left(p)); Chris@101: const node_ptr p_right(node_traits::get_right(p)); Chris@101: BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_left || node_traits::get_color(p_left) == node_traits::black()); Chris@101: BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_right || node_traits::get_color(p_right) == node_traits::black()); Chris@101: //Red node can't be root Chris@101: BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_parent(node_traits::get_parent(p)) != p); Chris@101: } Chris@101: //Every path to p contains the same number of black nodes Chris@101: const std::size_t l_black_count = check_return_left.black_count_; Chris@101: BOOST_INTRUSIVE_INVARIANT_ASSERT(l_black_count == check_return_right.black_count_); Chris@101: check_return.black_count_ = l_black_count + Chris@101: static_cast(node_traits::get_color(p) == node_traits::black()); Chris@101: base_checker_t::operator()(p, check_return_left, check_return_right, check_return); Chris@16: } Chris@16: }; Chris@16: Chris@101: } // namespace detail Chris@101: Chris@16: #endif //#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: //! rbtree_algorithms provides basic algorithms to manipulate Chris@16: //! nodes forming a red-black tree. The insertion and deletion algorithms are Chris@16: //! based on those in Cormen, Leiserson, and Rivest, Introduction to Algorithms Chris@16: //! (MIT Press, 1990), except that Chris@16: //! Chris@16: //! (1) the header node is maintained with links not only to the root Chris@16: //! but also to the leftmost node of the tree, to enable constant time Chris@16: //! begin(), and to the rightmost node of the tree, to enable linear time Chris@16: //! performance when used with the generic set algorithms (set_union, Chris@16: //! etc.); Chris@16: //! Chris@16: //! (2) when a node being deleted has two children its successor node is Chris@16: //! relinked into its place, rather than copied, so that the only Chris@16: //! pointers invalidated are those referring to the deleted node. Chris@16: //! Chris@16: //! rbtree_algorithms is configured with a NodeTraits class, which encapsulates the Chris@16: //! information about the node to be manipulated. NodeTraits must support the Chris@16: //! following interface: Chris@16: //! Chris@16: //! Typedefs: Chris@16: //! Chris@16: //! node: The type of the node that forms the binary search tree Chris@16: //! Chris@16: //! node_ptr: A pointer to a node Chris@16: //! Chris@16: //! const_node_ptr: A pointer to a const node Chris@16: //! Chris@16: //! color: The type that can store the color of a node Chris@16: //! Chris@16: //! Static functions: Chris@16: //! Chris@16: //! static node_ptr get_parent(const_node_ptr n); Chris@16: //! Chris@16: //! static void set_parent(node_ptr n, node_ptr parent); Chris@16: //! Chris@16: //! static node_ptr get_left(const_node_ptr n); Chris@16: //! Chris@16: //! static void set_left(node_ptr n, node_ptr left); Chris@16: //! Chris@16: //! static node_ptr get_right(const_node_ptr n); Chris@16: //! Chris@16: //! static void set_right(node_ptr n, node_ptr right); Chris@16: //! Chris@16: //! static color get_color(const_node_ptr n); Chris@16: //! Chris@16: //! static void set_color(node_ptr n, color c); Chris@16: //! Chris@16: //! static color black(); Chris@16: //! Chris@16: //! static color red(); Chris@16: template Chris@16: class rbtree_algorithms Chris@16: #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: : public bstree_algorithms Chris@16: #endif Chris@16: { Chris@16: public: Chris@16: typedef NodeTraits node_traits; Chris@16: typedef typename NodeTraits::node node; Chris@16: typedef typename NodeTraits::node_ptr node_ptr; Chris@16: typedef typename NodeTraits::const_node_ptr const_node_ptr; Chris@16: typedef typename NodeTraits::color color; Chris@16: Chris@16: /// @cond Chris@16: private: Chris@16: Chris@16: typedef bstree_algorithms bstree_algo; Chris@16: Chris@16: /// @endcond Chris@16: Chris@16: public: Chris@16: Chris@16: //! This type is the information that will be Chris@16: //! filled by insert_unique_check Chris@16: typedef typename bstree_algo::insert_commit_data insert_commit_data; Chris@16: Chris@16: #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const const_node_ptr&) Chris@16: static node_ptr get_header(const const_node_ptr & n); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node Chris@16: static node_ptr begin_node(const const_node_ptr & header); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::end_node Chris@16: static node_ptr end_node(const const_node_ptr & header); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree Chris@16: static void swap_tree(const node_ptr & header1, const node_ptr & header2); Chris@101: Chris@16: #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&) Chris@16: static void swap_nodes(const node_ptr & node1, const node_ptr & node2) Chris@16: { Chris@16: if(node1 == node2) Chris@16: return; Chris@16: Chris@16: node_ptr header1(bstree_algo::get_header(node1)), header2(bstree_algo::get_header(node2)); Chris@16: swap_nodes(node1, header1, node2, header2); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(const node_ptr&,const node_ptr&,const node_ptr&,const node_ptr&) Chris@16: static void swap_nodes(const node_ptr & node1, const node_ptr & header1, const node_ptr & node2, const node_ptr & header2) Chris@16: { Chris@16: if(node1 == node2) return; Chris@16: Chris@16: bstree_algo::swap_nodes(node1, header1, node2, header2); Chris@16: //Swap color Chris@16: color c = NodeTraits::get_color(node1); Chris@16: NodeTraits::set_color(node1, NodeTraits::get_color(node2)); Chris@16: NodeTraits::set_color(node2, c); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&) Chris@16: static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & new_node) Chris@16: { Chris@16: if(node_to_be_replaced == new_node) Chris@16: return; Chris@16: replace_node(node_to_be_replaced, bstree_algo::get_header(node_to_be_replaced), new_node); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(const node_ptr&,const node_ptr&,const node_ptr&) Chris@16: static void replace_node(const node_ptr & node_to_be_replaced, const node_ptr & header, const node_ptr & new_node) Chris@16: { Chris@16: bstree_algo::replace_node(node_to_be_replaced, header, new_node); Chris@16: NodeTraits::set_color(new_node, NodeTraits::get_color(node_to_be_replaced)); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(const node_ptr&) Chris@16: static void unlink(const node_ptr& node) Chris@16: { Chris@16: node_ptr x = NodeTraits::get_parent(node); Chris@16: if(x){ Chris@16: while(!is_header(x)) Chris@16: x = NodeTraits::get_parent(x); Chris@16: erase(x, node); Chris@16: } Chris@16: } Chris@16: Chris@16: #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance Chris@16: static node_ptr unlink_leftmost_without_rebalance(const node_ptr & header); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const const_node_ptr&) Chris@16: static bool unique(const const_node_ptr & node); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::size(const const_node_ptr&) Chris@16: static std::size_t size(const const_node_ptr & header); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const node_ptr&) Chris@16: static node_ptr next_node(const node_ptr & node); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const node_ptr&) Chris@16: static node_ptr prev_node(const node_ptr & node); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::init(const node_ptr&) Chris@16: static void init(const node_ptr & node); Chris@16: #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(const node_ptr&) Chris@16: static void init_header(const node_ptr & header) Chris@16: { Chris@16: bstree_algo::init_header(header); Chris@16: NodeTraits::set_color(header, NodeTraits::red()); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::erase(const node_ptr&,const node_ptr&) Chris@16: static node_ptr erase(const node_ptr & header, const node_ptr & z) Chris@16: { Chris@16: typename bstree_algo::data_for_rebalance info; Chris@101: bstree_algo::erase(header, z, info); Chris@16: Chris@101: color new_z_color; Chris@101: if(info.y != z){ Chris@101: new_z_color = NodeTraits::get_color(info.y); Chris@101: NodeTraits::set_color(info.y, NodeTraits::get_color(z)); Chris@101: } Chris@101: else{ Chris@101: new_z_color = NodeTraits::get_color(z); Chris@101: } Chris@101: //Rebalance rbtree if needed Chris@101: if(new_z_color != NodeTraits::red()){ Chris@16: rebalance_after_erasure(header, info.x, info.x_parent); Chris@16: } Chris@16: return z; Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const const_node_ptr&,const node_ptr&,Cloner,Disposer) Chris@16: template Chris@16: static void clone Chris@16: (const const_node_ptr & source_header, const node_ptr & target_header, Cloner cloner, Disposer disposer) Chris@16: { Chris@16: rbtree_node_cloner new_cloner(cloner); Chris@16: bstree_algo::clone(source_header, target_header, new_cloner, disposer); Chris@16: } Chris@16: Chris@16: #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const node_ptr&,Disposer) Chris@16: template Chris@16: static void clear_and_dispose(const node_ptr & header, Disposer disposer); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) Chris@16: template Chris@16: static node_ptr lower_bound Chris@16: (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) Chris@16: template Chris@16: static node_ptr upper_bound Chris@16: (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::find(const const_node_ptr&, const KeyType&,KeyNodePtrCompare) Chris@16: template Chris@16: static node_ptr find Chris@16: (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) Chris@16: template Chris@16: static std::pair equal_range Chris@16: (const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const const_node_ptr&,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool) Chris@16: template Chris@16: static std::pair bounded_range Chris@16: (const const_node_ptr & header, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp Chris@16: , bool left_closed, bool right_closed); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::count(const const_node_ptr&,const KeyType&,KeyNodePtrCompare) Chris@16: template Chris@16: static std::size_t count(const const_node_ptr & header, const KeyType &key, KeyNodePtrCompare comp); Chris@101: Chris@16: #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(const node_ptr&,const node_ptr&,NodePtrCompare) Chris@16: template Chris@16: static node_ptr insert_equal_upper_bound Chris@16: (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) Chris@16: { Chris@16: bstree_algo::insert_equal_upper_bound(h, new_node, comp); Chris@16: rebalance_after_insertion(h, new_node); Chris@16: return new_node; Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(const node_ptr&,const node_ptr&,NodePtrCompare) Chris@16: template Chris@16: static node_ptr insert_equal_lower_bound Chris@16: (const node_ptr & h, const node_ptr & new_node, NodePtrCompare comp) Chris@16: { Chris@16: bstree_algo::insert_equal_lower_bound(h, new_node, comp); Chris@16: rebalance_after_insertion(h, new_node); Chris@16: return new_node; Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(const node_ptr&,const node_ptr&,const node_ptr&,NodePtrCompare) Chris@16: template Chris@16: static node_ptr insert_equal Chris@16: (const node_ptr & header, const node_ptr & hint, const node_ptr & new_node, NodePtrCompare comp) Chris@16: { Chris@16: bstree_algo::insert_equal(header, hint, new_node, comp); Chris@16: rebalance_after_insertion(header, new_node); Chris@16: return new_node; Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(const node_ptr&,const node_ptr&,const node_ptr&) Chris@16: static node_ptr insert_before Chris@16: (const node_ptr & header, const node_ptr & pos, const node_ptr & new_node) Chris@16: { Chris@16: bstree_algo::insert_before(header, pos, new_node); Chris@16: rebalance_after_insertion(header, new_node); Chris@16: return new_node; Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(const node_ptr&,const node_ptr&) Chris@16: static void push_back(const node_ptr & header, const node_ptr & new_node) Chris@16: { Chris@16: bstree_algo::push_back(header, new_node); Chris@16: rebalance_after_insertion(header, new_node); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(const node_ptr&,const node_ptr&) Chris@16: static void push_front(const node_ptr & header, const node_ptr & new_node) Chris@16: { Chris@16: bstree_algo::push_front(header, new_node); Chris@16: rebalance_after_insertion(header, new_node); Chris@16: } Chris@16: Chris@16: #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) Chris@16: template Chris@16: static std::pair insert_unique_check Chris@16: (const const_node_ptr & header, const KeyType &key Chris@16: ,KeyNodePtrCompare comp, insert_commit_data &commit_data); Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const const_node_ptr&,const node_ptr&,const KeyType&,KeyNodePtrCompare,insert_commit_data&) Chris@16: template Chris@16: static std::pair insert_unique_check Chris@16: (const const_node_ptr & header, const node_ptr &hint, const KeyType &key Chris@16: ,KeyNodePtrCompare comp, insert_commit_data &commit_data); Chris@16: #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(const node_ptr&,const node_ptr&,const insert_commit_data&) Chris@16: static void insert_unique_commit Chris@16: (const node_ptr & header, const node_ptr & new_value, const insert_commit_data &commit_data) Chris@16: { Chris@16: bstree_algo::insert_unique_commit(header, new_value, commit_data); Chris@16: rebalance_after_insertion(header, new_value); Chris@16: } Chris@16: Chris@16: //! @copydoc ::boost::intrusive::bstree_algorithms::is_header Chris@16: static bool is_header(const const_node_ptr & p) Chris@16: { Chris@16: return NodeTraits::get_color(p) == NodeTraits::red() && Chris@16: bstree_algo::is_header(p); Chris@16: } Chris@16: Chris@16: /// @cond Chris@16: private: Chris@16: Chris@16: static void rebalance_after_erasure(const node_ptr & header, node_ptr x, node_ptr x_parent) Chris@16: { Chris@101: while(1){ Chris@101: if(x_parent == header || (x && NodeTraits::get_color(x) != NodeTraits::black())){ Chris@101: break; Chris@101: } Chris@101: //Don't cache x_is_leftchild or similar because x can be null and Chris@101: //equal to both x_parent_left and x_parent_right Chris@101: const node_ptr x_parent_left(NodeTraits::get_left(x_parent)); Chris@101: if(x == x_parent_left){ //x is left child Chris@16: node_ptr w = NodeTraits::get_right(x_parent); Chris@101: BOOST_INTRUSIVE_INVARIANT_ASSERT(w); Chris@16: if(NodeTraits::get_color(w) == NodeTraits::red()){ Chris@16: NodeTraits::set_color(w, NodeTraits::black()); Chris@16: NodeTraits::set_color(x_parent, NodeTraits::red()); Chris@101: bstree_algo::rotate_left(x_parent, w, NodeTraits::get_parent(x_parent), header); Chris@16: w = NodeTraits::get_right(x_parent); Chris@16: } Chris@101: node_ptr const w_left (NodeTraits::get_left(w)); Chris@101: node_ptr const w_right(NodeTraits::get_right(w)); Chris@101: if((!w_left || NodeTraits::get_color(w_left) == NodeTraits::black()) && Chris@101: (!w_right || NodeTraits::get_color(w_right) == NodeTraits::black())){ Chris@16: NodeTraits::set_color(w, NodeTraits::red()); Chris@16: x = x_parent; Chris@16: x_parent = NodeTraits::get_parent(x_parent); Chris@16: } Chris@16: else { Chris@101: if(!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()){ Chris@101: NodeTraits::set_color(w_left, NodeTraits::black()); Chris@16: NodeTraits::set_color(w, NodeTraits::red()); Chris@101: bstree_algo::rotate_right(w, w_left, NodeTraits::get_parent(w), header); Chris@16: w = NodeTraits::get_right(x_parent); Chris@16: } Chris@16: NodeTraits::set_color(w, NodeTraits::get_color(x_parent)); Chris@16: NodeTraits::set_color(x_parent, NodeTraits::black()); Chris@101: const node_ptr new_wright(NodeTraits::get_right(w)); Chris@101: if(new_wright) Chris@101: NodeTraits::set_color(new_wright, NodeTraits::black()); Chris@101: bstree_algo::rotate_left(x_parent, NodeTraits::get_right(x_parent), NodeTraits::get_parent(x_parent), header); Chris@16: break; Chris@16: } Chris@16: } Chris@16: else { Chris@16: // same as above, with right_ <-> left_. Chris@101: node_ptr w = x_parent_left; Chris@16: if(NodeTraits::get_color(w) == NodeTraits::red()){ Chris@16: NodeTraits::set_color(w, NodeTraits::black()); Chris@16: NodeTraits::set_color(x_parent, NodeTraits::red()); Chris@101: bstree_algo::rotate_right(x_parent, w, NodeTraits::get_parent(x_parent), header); Chris@16: w = NodeTraits::get_left(x_parent); Chris@16: } Chris@101: node_ptr const w_left (NodeTraits::get_left(w)); Chris@101: node_ptr const w_right(NodeTraits::get_right(w)); Chris@101: if((!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()) && Chris@101: (!w_left || NodeTraits::get_color(w_left) == NodeTraits::black())){ Chris@16: NodeTraits::set_color(w, NodeTraits::red()); Chris@16: x = x_parent; Chris@16: x_parent = NodeTraits::get_parent(x_parent); Chris@16: } Chris@16: else { Chris@101: if(!w_left || NodeTraits::get_color(w_left) == NodeTraits::black()){ Chris@101: NodeTraits::set_color(w_right, NodeTraits::black()); Chris@16: NodeTraits::set_color(w, NodeTraits::red()); Chris@101: bstree_algo::rotate_left(w, w_right, NodeTraits::get_parent(w), header); Chris@16: w = NodeTraits::get_left(x_parent); Chris@16: } Chris@16: NodeTraits::set_color(w, NodeTraits::get_color(x_parent)); Chris@16: NodeTraits::set_color(x_parent, NodeTraits::black()); Chris@101: const node_ptr new_wleft(NodeTraits::get_left(w)); Chris@101: if(new_wleft) Chris@101: NodeTraits::set_color(new_wleft, NodeTraits::black()); Chris@101: bstree_algo::rotate_right(x_parent, NodeTraits::get_left(x_parent), NodeTraits::get_parent(x_parent), header); Chris@16: break; Chris@16: } Chris@16: } Chris@16: } Chris@16: if(x) Chris@16: NodeTraits::set_color(x, NodeTraits::black()); Chris@16: } Chris@16: Chris@16: static void rebalance_after_insertion(const node_ptr & header, node_ptr p) Chris@16: { Chris@16: NodeTraits::set_color(p, NodeTraits::red()); Chris@101: while(1){ Chris@16: node_ptr p_parent(NodeTraits::get_parent(p)); Chris@101: const node_ptr p_grandparent(NodeTraits::get_parent(p_parent)); Chris@101: if(p_parent == header || NodeTraits::get_color(p_parent) == NodeTraits::black() || p_grandparent == header){ Chris@101: break; Chris@101: } Chris@101: Chris@101: NodeTraits::set_color(p_grandparent, NodeTraits::red()); Chris@101: node_ptr const p_grandparent_left (NodeTraits::get_left (p_grandparent)); Chris@101: bool const p_parent_is_left_child = p_parent == p_grandparent_left; Chris@101: node_ptr const x(p_parent_is_left_child ? NodeTraits::get_right(p_grandparent) : p_grandparent_left); Chris@101: Chris@101: if(x && NodeTraits::get_color(x) == NodeTraits::red()){ Chris@101: NodeTraits::set_color(x, NodeTraits::black()); Chris@101: NodeTraits::set_color(p_parent, NodeTraits::black()); Chris@101: p = p_grandparent; Chris@101: } Chris@101: else{ //Final step Chris@101: const bool p_is_left_child(NodeTraits::get_left(p_parent) == p); Chris@101: if(p_parent_is_left_child){ //p_parent is left child Chris@101: if(!p_is_left_child){ //p is right child Chris@101: bstree_algo::rotate_left_no_parent_fix(p_parent, p); Chris@101: //No need to link p and p_grandparent: Chris@101: // [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_left(p_grandparent, p)] Chris@101: //as p_grandparent is not the header, another rotation is coming and p_parent Chris@101: //will be the left child of p_grandparent Chris@101: p_parent = p; Chris@101: } Chris@101: bstree_algo::rotate_right(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header); Chris@16: } Chris@101: else{ //p_parent is right child Chris@101: if(p_is_left_child){ //p is left child Chris@101: bstree_algo::rotate_right_no_parent_fix(p_parent, p); Chris@101: //No need to link p and p_grandparent: Chris@101: // [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_right(p_grandparent, p)] Chris@101: //as p_grandparent is not the header, another rotation is coming and p_parent Chris@101: //will be the right child of p_grandparent Chris@101: p_parent = p; Chris@16: } Chris@101: bstree_algo::rotate_left(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header); Chris@16: } Chris@101: NodeTraits::set_color(p_parent, NodeTraits::black()); Chris@101: break; Chris@16: } Chris@16: } Chris@16: NodeTraits::set_color(NodeTraits::get_parent(header), NodeTraits::black()); Chris@16: } Chris@16: /// @endcond Chris@16: }; Chris@16: Chris@16: /// @cond Chris@16: Chris@16: template Chris@16: struct get_algo Chris@16: { Chris@16: typedef rbtree_algorithms type; Chris@16: }; Chris@16: Chris@101: template Chris@101: struct get_node_checker Chris@101: { Chris@101: typedef detail::rbtree_node_checker type; Chris@101: }; Chris@101: Chris@16: /// @endcond Chris@16: Chris@16: } //namespace intrusive Chris@16: } //namespace boost Chris@16: Chris@16: #include Chris@16: Chris@16: #endif //BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP