Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:38:43 

0001 /////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Olaf Krzikalla 2004-2006.
0004 // (C) Copyright Ion Gaztanaga  2006-2014.
0005 //
0006 // Distributed under the Boost Software License, Version 1.0.
0007 //    (See accompanying file LICENSE_1_0.txt or copy at
0008 //          http://www.boost.org/LICENSE_1_0.txt)
0009 //
0010 // See http://www.boost.org/libs/intrusive for documentation.
0011 //
0012 /////////////////////////////////////////////////////////////////////////////
0013 //
0014 // The tree destruction algorithm is based on Julienne Walker and The EC Team code:
0015 //
0016 // This code is in the public domain. Anyone may use it or change it in any way that
0017 // they see fit. The author assumes no responsibility for damages incurred through
0018 // use of the original code or any variations thereof.
0019 //
0020 // It is requested, but not required, that due credit is given to the original author
0021 // and anyone who has modified the code through a header comment, such as this one.
0022 
0023 #ifndef BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP
0024 #define BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP
0025 
0026 #include <boost/intrusive/detail/config_begin.hpp>
0027 #include <boost/intrusive/intrusive_fwd.hpp>
0028 
0029 #include <cstddef>
0030 
0031 #include <boost/intrusive/detail/assert.hpp>
0032 #include <boost/intrusive/detail/algo_type.hpp>
0033 #include <boost/intrusive/bstree_algorithms.hpp>
0034 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
0035 
0036 #if defined(BOOST_HAS_PRAGMA_ONCE)
0037 #  pragma once
0038 #endif
0039 
0040 namespace boost {
0041 namespace intrusive {
0042 
0043 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0044 
0045 template<class NodeTraits, class F>
0046 struct rbtree_node_cloner
0047    //Use public inheritance to avoid MSVC bugs with closures
0048    :  public detail::ebo_functor_holder<F>
0049 {
0050    typedef typename NodeTraits::node_ptr  node_ptr;
0051    typedef detail::ebo_functor_holder<F>  base_t;
0052 
0053    explicit rbtree_node_cloner(F f)
0054       :  base_t(f)
0055    {}
0056 
0057    node_ptr operator()(node_ptr p)
0058    {
0059       node_ptr n = base_t::get()(p);
0060       NodeTraits::set_color(n, NodeTraits::get_color(p));
0061       return n;
0062    }
0063 };
0064 
0065 namespace detail {
0066 
0067 template<class ValueTraits, class NodePtrCompare, class ExtraChecker>
0068 struct rbtree_node_checker
0069    : public bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker>
0070 {
0071    typedef bstree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> base_checker_t;
0072    typedef ValueTraits                             value_traits;
0073    typedef typename value_traits::node_traits      node_traits;
0074    typedef typename node_traits::const_node_ptr    const_node_ptr;
0075    typedef typename node_traits::node_ptr          node_ptr;
0076 
0077    struct return_type
0078          : public base_checker_t::return_type
0079    {
0080       return_type() : black_count_(0) {}
0081       std::size_t black_count_;
0082    };
0083 
0084    rbtree_node_checker(const NodePtrCompare& comp, ExtraChecker extra_checker)
0085       : base_checker_t(comp, extra_checker)
0086    {}
0087 
0088    void operator () (const_node_ptr p,
0089                      const return_type& check_return_left, const return_type& check_return_right,
0090                      return_type& check_return)
0091    {
0092 
0093       if (node_traits::get_color(p) == node_traits::red()){
0094          //Red nodes have black children
0095          const node_ptr p_left(node_traits::get_left(p));   (void)p_left;
0096          const node_ptr p_right(node_traits::get_right(p)); (void)p_right;
0097          BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_left  || node_traits::get_color(p_left)  == node_traits::black());
0098          BOOST_INTRUSIVE_INVARIANT_ASSERT(!p_right || node_traits::get_color(p_right) == node_traits::black());
0099          //Red node can't be root
0100          BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_parent(node_traits::get_parent(p)) != p);
0101       }
0102       //Every path to p contains the same number of black nodes
0103       const std::size_t l_black_count = check_return_left.black_count_;
0104       BOOST_INTRUSIVE_INVARIANT_ASSERT(l_black_count == check_return_right.black_count_);
0105       check_return.black_count_ = l_black_count +
0106          static_cast<std::size_t>(node_traits::get_color(p) == node_traits::black());
0107       base_checker_t::operator()(p, check_return_left, check_return_right, check_return);
0108    }
0109 };
0110 
0111 } // namespace detail
0112 
0113 #endif   //#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0114 
0115 //! rbtree_algorithms provides basic algorithms to manipulate
0116 //! nodes forming a red-black tree. The insertion and deletion algorithms are
0117 //! based on those in Cormen, Leiserson, and Rivest, Introduction to Algorithms
0118 //! (MIT Press, 1990), except that
0119 //!
0120 //! (1) the header node is maintained with links not only to the root
0121 //! but also to the leftmost node of the tree, to enable constant time
0122 //! begin(), and to the rightmost node of the tree, to enable linear time
0123 //! performance when used with the generic set algorithms (set_union,
0124 //! etc.);
0125 //!
0126 //! (2) when a node being deleted has two children its successor node is
0127 //! relinked into its place, rather than copied, so that the only
0128 //! pointers invalidated are those referring to the deleted node.
0129 //!
0130 //! rbtree_algorithms is configured with a NodeTraits class, which encapsulates the
0131 //! information about the node to be manipulated. NodeTraits must support the
0132 //! following interface:
0133 //!
0134 //! <b>Typedefs</b>:
0135 //!
0136 //! <tt>node</tt>: The type of the node that forms the binary search tree
0137 //!
0138 //! <tt>node_ptr</tt>: A pointer to a node
0139 //!
0140 //! <tt>const_node_ptr</tt>: A pointer to a const node
0141 //!
0142 //! <tt>color</tt>: The type that can store the color of a node
0143 //!
0144 //! <b>Static functions</b>:
0145 //!
0146 //! <tt>static node_ptr get_parent(const_node_ptr n);</tt>
0147 //!
0148 //! <tt>static void set_parent(node_ptr n, node_ptr parent);</tt>
0149 //!
0150 //! <tt>static node_ptr get_left(const_node_ptr n);</tt>
0151 //!
0152 //! <tt>static void set_left(node_ptr n, node_ptr left);</tt>
0153 //!
0154 //! <tt>static node_ptr get_right(const_node_ptr n);</tt>
0155 //!
0156 //! <tt>static void set_right(node_ptr n, node_ptr right);</tt>
0157 //!
0158 //! <tt>static color get_color(const_node_ptr n);</tt>
0159 //!
0160 //! <tt>static void set_color(node_ptr n, color c);</tt>
0161 //!
0162 //! <tt>static color black();</tt>
0163 //!
0164 //! <tt>static color red();</tt>
0165 template<class NodeTraits>
0166 class rbtree_algorithms
0167    #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0168    : public bstree_algorithms<NodeTraits>
0169    #endif
0170 {
0171    public:
0172    typedef NodeTraits                           node_traits;
0173    typedef typename NodeTraits::node            node;
0174    typedef typename NodeTraits::node_ptr        node_ptr;
0175    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
0176    typedef typename NodeTraits::color           color;
0177 
0178    /// @cond
0179    private:
0180 
0181    typedef bstree_algorithms<NodeTraits>  bstree_algo;
0182 
0183    /// @endcond
0184 
0185    public:
0186 
0187    //! This type is the information that will be
0188    //! filled by insert_unique_check
0189    typedef typename bstree_algo::insert_commit_data insert_commit_data;
0190 
0191    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0192 
0193    //! @copydoc ::boost::intrusive::bstree_algorithms::get_header(const_node_ptr)
0194    static node_ptr get_header(const_node_ptr n) BOOST_NOEXCEPT;
0195 
0196    //! @copydoc ::boost::intrusive::bstree_algorithms::begin_node
0197    static node_ptr begin_node(const_node_ptr header) BOOST_NOEXCEPT;
0198 
0199    //! @copydoc ::boost::intrusive::bstree_algorithms::end_node
0200    static node_ptr end_node(const_node_ptr header) BOOST_NOEXCEPT;
0201 
0202    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_tree
0203    static void swap_tree(node_ptr header1, node_ptr header2) BOOST_NOEXCEPT;
0204 
0205    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0206 
0207    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(node_ptr,node_ptr)
0208    static void swap_nodes(node_ptr node1, node_ptr node2) BOOST_NOEXCEPT
0209    {
0210       if(node1 == node2)
0211          return;
0212 
0213       node_ptr header1(bstree_algo::get_header(node1)), header2(bstree_algo::get_header(node2));
0214       swap_nodes(node1, header1, node2, header2);
0215    }
0216 
0217    //! @copydoc ::boost::intrusive::bstree_algorithms::swap_nodes(node_ptr,node_ptr,node_ptr,node_ptr)
0218    static void swap_nodes(node_ptr node1, node_ptr header1, node_ptr node2, node_ptr header2) BOOST_NOEXCEPT
0219    {
0220       if(node1 == node2)   return;
0221 
0222       bstree_algo::swap_nodes(node1, header1, node2, header2);
0223       //Swap color
0224       color c = NodeTraits::get_color(node1);
0225       NodeTraits::set_color(node1, NodeTraits::get_color(node2));
0226       NodeTraits::set_color(node2, c);
0227    }
0228 
0229    //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(node_ptr,node_ptr)
0230    static void replace_node(node_ptr node_to_be_replaced, node_ptr new_node) BOOST_NOEXCEPT
0231    {
0232       if(node_to_be_replaced == new_node)
0233          return;
0234       replace_node(node_to_be_replaced, bstree_algo::get_header(node_to_be_replaced), new_node);
0235    }
0236 
0237    //! @copydoc ::boost::intrusive::bstree_algorithms::replace_node(node_ptr,node_ptr,node_ptr)
0238    static void replace_node(node_ptr node_to_be_replaced, node_ptr header, node_ptr new_node) BOOST_NOEXCEPT
0239    {
0240       bstree_algo::replace_node(node_to_be_replaced, header, new_node);
0241       NodeTraits::set_color(new_node, NodeTraits::get_color(node_to_be_replaced));
0242    }
0243 
0244    //! @copydoc ::boost::intrusive::bstree_algorithms::unlink(node_ptr)
0245    static void unlink(node_ptr n) BOOST_NOEXCEPT
0246    {
0247       node_ptr x = NodeTraits::get_parent(n);
0248       if(x){
0249          while(!is_header(x))
0250             x = NodeTraits::get_parent(x);
0251          erase(x, n);
0252       }
0253    }
0254 
0255    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0256    //! @copydoc ::boost::intrusive::bstree_algorithms::unlink_leftmost_without_rebalance
0257    static node_ptr unlink_leftmost_without_rebalance(node_ptr header) BOOST_NOEXCEPT;
0258 
0259    //! @copydoc ::boost::intrusive::bstree_algorithms::unique(const_node_ptr)
0260    static bool unique(const_node_ptr n) BOOST_NOEXCEPT;
0261 
0262    //! @copydoc ::boost::intrusive::bstree_algorithms::size(const_node_ptr)
0263    static std::size_t size(const_node_ptr header) BOOST_NOEXCEPT;
0264 
0265    //! @copydoc ::boost::intrusive::bstree_algorithms::next_node(const_node_ptr)
0266    static node_ptr next_node(node_ptr n) BOOST_NOEXCEPT;
0267 
0268    //! @copydoc ::boost::intrusive::bstree_algorithms::prev_node(const_node_ptr)
0269    static node_ptr prev_node(node_ptr n) BOOST_NOEXCEPT;
0270 
0271    //! @copydoc ::boost::intrusive::bstree_algorithms::init(node_ptr)
0272    static void init(node_ptr n) BOOST_NOEXCEPT;
0273    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0274 
0275    //! @copydoc ::boost::intrusive::bstree_algorithms::init_header(node_ptr)
0276    static void init_header(node_ptr header) BOOST_NOEXCEPT
0277    {
0278       bstree_algo::init_header(header);
0279       NodeTraits::set_color(header, NodeTraits::red());
0280    }
0281 
0282    //! @copydoc ::boost::intrusive::bstree_algorithms::erase(node_ptr,node_ptr)
0283    static node_ptr erase(node_ptr header, node_ptr z) BOOST_NOEXCEPT
0284    {
0285       typename bstree_algo::data_for_rebalance info;
0286       bstree_algo::erase(header, z, info);
0287       rebalance_after_erasure(header, z, info);
0288       return z;
0289    }
0290 
0291    //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_unique
0292    template<class NodePtrCompare>
0293    static bool transfer_unique
0294       (node_ptr header1, NodePtrCompare comp, node_ptr header2, node_ptr z)
0295    {
0296       typename bstree_algo::data_for_rebalance info;
0297       bool const transferred = bstree_algo::transfer_unique(header1, comp, header2, z, info);
0298       if(transferred){
0299          rebalance_after_erasure(header2, z, info);
0300          rebalance_after_insertion(header1, z);
0301       }
0302       return transferred;
0303    }
0304 
0305    //! @copydoc ::boost::intrusive::bstree_algorithms::transfer_equal
0306    template<class NodePtrCompare>
0307    static void transfer_equal
0308       (node_ptr header1, NodePtrCompare comp, node_ptr header2, node_ptr z)
0309    {
0310       typename bstree_algo::data_for_rebalance info;
0311       bstree_algo::transfer_equal(header1, comp, header2, z, info);
0312       rebalance_after_erasure(header2, z, info);
0313       rebalance_after_insertion(header1, z);
0314    }
0315 
0316    //! @copydoc ::boost::intrusive::bstree_algorithms::clone(const_node_ptr,node_ptr,Cloner,Disposer)
0317    template <class Cloner, class Disposer>
0318    static void clone
0319       (const_node_ptr source_header, node_ptr target_header, Cloner cloner, Disposer disposer)
0320    {
0321       rbtree_node_cloner<NodeTraits, Cloner> new_cloner(cloner);
0322       bstree_algo::clone(source_header, target_header, new_cloner, disposer);
0323    }
0324 
0325    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0326    //! @copydoc ::boost::intrusive::bstree_algorithms::clear_and_dispose(const_node_ptr,Disposer)
0327    template<class Disposer>
0328    static void clear_and_dispose(node_ptr header, Disposer disposer) BOOST_NOEXCEPT;
0329 
0330    //! @copydoc ::boost::intrusive::bstree_algorithms::lower_bound(const_node_ptr,const KeyType&,KeyNodePtrCompare)
0331    template<class KeyType, class KeyNodePtrCompare>
0332    static node_ptr lower_bound
0333       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
0334 
0335    //! @copydoc ::boost::intrusive::bstree_algorithms::upper_bound(const_node_ptr,const KeyType&,KeyNodePtrCompare)
0336    template<class KeyType, class KeyNodePtrCompare>
0337    static node_ptr upper_bound
0338       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
0339 
0340    //! @copydoc ::boost::intrusive::bstree_algorithms::find(const_node_ptr, const KeyType&,KeyNodePtrCompare)
0341    template<class KeyType, class KeyNodePtrCompare>
0342    static node_ptr find
0343       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
0344 
0345    //! @copydoc ::boost::intrusive::bstree_algorithms::equal_range(const_node_ptr,const KeyType&,KeyNodePtrCompare)
0346    template<class KeyType, class KeyNodePtrCompare>
0347    static std::pair<node_ptr, node_ptr> equal_range
0348       (const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
0349 
0350    //! @copydoc ::boost::intrusive::bstree_algorithms::bounded_range(const_node_ptr,const KeyType&,const KeyType&,KeyNodePtrCompare,bool,bool)
0351    template<class KeyType, class KeyNodePtrCompare>
0352    static std::pair<node_ptr, node_ptr> bounded_range
0353       (const_node_ptr eader, const KeyType &lower_key, const KeyType &upper_key, KeyNodePtrCompare comp
0354       , bool left_closed, bool right_closed);
0355 
0356    //! @copydoc ::boost::intrusive::bstree_algorithms::count(const_node_ptr,const KeyType&,KeyNodePtrCompare)
0357    template<class KeyType, class KeyNodePtrCompare>
0358    static std::size_t count(const_node_ptr header, const KeyType &key, KeyNodePtrCompare comp);
0359 
0360    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0361 
0362    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_upper_bound(node_ptr,node_ptr,NodePtrCompare)
0363    template<class NodePtrCompare>
0364    static node_ptr insert_equal_upper_bound
0365       (node_ptr h, node_ptr new_node, NodePtrCompare comp)
0366    {
0367       bstree_algo::insert_equal_upper_bound(h, new_node, comp);
0368       rebalance_after_insertion(h, new_node);
0369       return new_node;
0370    }
0371 
0372    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal_lower_bound(node_ptr,node_ptr,NodePtrCompare)
0373    template<class NodePtrCompare>
0374    static node_ptr insert_equal_lower_bound
0375       (node_ptr h, node_ptr new_node, NodePtrCompare comp)
0376    {
0377       bstree_algo::insert_equal_lower_bound(h, new_node, comp);
0378       rebalance_after_insertion(h, new_node);
0379       return new_node;
0380    }
0381 
0382    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_equal(node_ptr,node_ptr,node_ptr,NodePtrCompare)
0383    template<class NodePtrCompare>
0384    static node_ptr insert_equal
0385       (node_ptr header, node_ptr hint, node_ptr new_node, NodePtrCompare comp)
0386    {
0387       bstree_algo::insert_equal(header, hint, new_node, comp);
0388       rebalance_after_insertion(header, new_node);
0389       return new_node;
0390    }
0391 
0392    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_before(node_ptr,node_ptr,node_ptr)
0393    static node_ptr insert_before
0394       (node_ptr header, node_ptr pos, node_ptr new_node) BOOST_NOEXCEPT
0395    {
0396       bstree_algo::insert_before(header, pos, new_node);
0397       rebalance_after_insertion(header, new_node);
0398       return new_node;
0399    }
0400 
0401    //! @copydoc ::boost::intrusive::bstree_algorithms::push_back(node_ptr,node_ptr)
0402    static void push_back(node_ptr header, node_ptr new_node) BOOST_NOEXCEPT
0403    {
0404       bstree_algo::push_back(header, new_node);
0405       rebalance_after_insertion(header, new_node);
0406    }
0407 
0408    //! @copydoc ::boost::intrusive::bstree_algorithms::push_front(node_ptr,node_ptr)
0409    static void push_front(node_ptr header, node_ptr new_node) BOOST_NOEXCEPT
0410    {
0411       bstree_algo::push_front(header, new_node);
0412       rebalance_after_insertion(header, new_node);
0413    }
0414 
0415    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0416    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const_node_ptr,const KeyType&,KeyNodePtrCompare,insert_commit_data&)
0417    template<class KeyType, class KeyNodePtrCompare>
0418    static std::pair<node_ptr, bool> insert_unique_check
0419       (const_node_ptr header,  const KeyType &key
0420       ,KeyNodePtrCompare comp, insert_commit_data &commit_data);
0421 
0422    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_check(const_node_ptr,const_node_ptr,const KeyType&,KeyNodePtrCompare,insert_commit_data&)
0423    template<class KeyType, class KeyNodePtrCompare>
0424    static std::pair<node_ptr, bool> insert_unique_check
0425       (const_node_ptr header, node_ptr hint, const KeyType &key
0426       ,KeyNodePtrCompare comp, insert_commit_data &commit_data);
0427    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
0428 
0429    //! @copydoc ::boost::intrusive::bstree_algorithms::insert_unique_commit(node_ptr,node_ptr,const insert_commit_data&)
0430    static void insert_unique_commit
0431       (node_ptr header, node_ptr new_value, const insert_commit_data &commit_data) BOOST_NOEXCEPT
0432    {
0433       bstree_algo::insert_unique_commit(header, new_value, commit_data);
0434       rebalance_after_insertion(header, new_value);
0435    }
0436 
0437    //! @copydoc ::boost::intrusive::bstree_algorithms::is_header
0438    static bool is_header(const_node_ptr p) BOOST_NOEXCEPT
0439    {
0440       return NodeTraits::get_color(p) == NodeTraits::red() &&
0441             bstree_algo::is_header(p);
0442    }
0443 
0444    /// @cond
0445    private:
0446 
0447    static void rebalance_after_erasure
0448       ( node_ptr header, node_ptr z, const typename bstree_algo::data_for_rebalance &info) BOOST_NOEXCEPT
0449    {
0450       color new_z_color;
0451       if(info.y != z){
0452          new_z_color = NodeTraits::get_color(info.y);
0453          NodeTraits::set_color(info.y, NodeTraits::get_color(z));
0454       }
0455       else{
0456          new_z_color = NodeTraits::get_color(z);
0457       }
0458       //Rebalance rbtree if needed
0459       if(new_z_color != NodeTraits::red()){
0460          rebalance_after_erasure_restore_invariants(header, info.x, info.x_parent);
0461       }
0462    }
0463 
0464    static void rebalance_after_erasure_restore_invariants(node_ptr header, node_ptr x, node_ptr x_parent) BOOST_NOEXCEPT
0465    {
0466       while(1){
0467          if(x_parent == header || (x && NodeTraits::get_color(x) != NodeTraits::black())){
0468             break;
0469          }
0470          //Don't cache x_is_leftchild or similar because x can be null and
0471          //equal to both x_parent_left and x_parent_right
0472          const node_ptr x_parent_left(NodeTraits::get_left(x_parent));
0473          if(x == x_parent_left){ //x is left child
0474             node_ptr w = NodeTraits::get_right(x_parent);
0475             BOOST_INTRUSIVE_INVARIANT_ASSERT(w);
0476             if(NodeTraits::get_color(w) == NodeTraits::red()){
0477                NodeTraits::set_color(w, NodeTraits::black());
0478                NodeTraits::set_color(x_parent, NodeTraits::red());
0479                bstree_algo::rotate_left(x_parent, w, NodeTraits::get_parent(x_parent), header);
0480                w = NodeTraits::get_right(x_parent);
0481                BOOST_INTRUSIVE_INVARIANT_ASSERT(w);
0482             }
0483             node_ptr const w_left (NodeTraits::get_left(w));
0484             node_ptr const w_right(NodeTraits::get_right(w));
0485             if((!w_left  || NodeTraits::get_color(w_left)  == NodeTraits::black()) &&
0486                (!w_right || NodeTraits::get_color(w_right) == NodeTraits::black())){
0487                NodeTraits::set_color(w, NodeTraits::red());
0488                x = x_parent;
0489                x_parent = NodeTraits::get_parent(x_parent);
0490             }
0491             else {
0492                if(!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()){
0493                   NodeTraits::set_color(w_left, NodeTraits::black());
0494                   NodeTraits::set_color(w, NodeTraits::red());
0495                   bstree_algo::rotate_right(w, w_left, NodeTraits::get_parent(w), header);
0496                   w = NodeTraits::get_right(x_parent);
0497                   BOOST_INTRUSIVE_INVARIANT_ASSERT(w);
0498                }
0499                NodeTraits::set_color(w, NodeTraits::get_color(x_parent));
0500                NodeTraits::set_color(x_parent, NodeTraits::black());
0501                const node_ptr new_wright(NodeTraits::get_right(w));
0502                if(new_wright)
0503                   NodeTraits::set_color(new_wright, NodeTraits::black());
0504                bstree_algo::rotate_left(x_parent, NodeTraits::get_right(x_parent), NodeTraits::get_parent(x_parent), header);
0505                break;
0506             }
0507          }
0508          else {
0509             // same as above, with right_ <-> left_.
0510             node_ptr w = x_parent_left;
0511             if(NodeTraits::get_color(w) == NodeTraits::red()){
0512                NodeTraits::set_color(w, NodeTraits::black());
0513                NodeTraits::set_color(x_parent, NodeTraits::red());
0514                bstree_algo::rotate_right(x_parent, w, NodeTraits::get_parent(x_parent), header);
0515                w = NodeTraits::get_left(x_parent);
0516                BOOST_INTRUSIVE_INVARIANT_ASSERT(w);
0517             }
0518             node_ptr const w_left (NodeTraits::get_left(w));
0519             node_ptr const w_right(NodeTraits::get_right(w));
0520             if((!w_right || NodeTraits::get_color(w_right) == NodeTraits::black()) &&
0521                (!w_left  || NodeTraits::get_color(w_left)  == NodeTraits::black())){
0522                NodeTraits::set_color(w, NodeTraits::red());
0523                x = x_parent;
0524                x_parent = NodeTraits::get_parent(x_parent);
0525             }
0526             else {
0527                if(!w_left || NodeTraits::get_color(w_left) == NodeTraits::black()){
0528                   NodeTraits::set_color(w_right, NodeTraits::black());
0529                   NodeTraits::set_color(w, NodeTraits::red());
0530                   bstree_algo::rotate_left(w, w_right, NodeTraits::get_parent(w), header);
0531                   w = NodeTraits::get_left(x_parent);
0532                   BOOST_INTRUSIVE_INVARIANT_ASSERT(w);
0533                }
0534                NodeTraits::set_color(w, NodeTraits::get_color(x_parent));
0535                NodeTraits::set_color(x_parent, NodeTraits::black());
0536                const node_ptr new_wleft(NodeTraits::get_left(w));
0537                if(new_wleft)
0538                   NodeTraits::set_color(new_wleft, NodeTraits::black());
0539                bstree_algo::rotate_right(x_parent, NodeTraits::get_left(x_parent), NodeTraits::get_parent(x_parent), header);
0540                break;
0541             }
0542          }
0543       }
0544       if(x)
0545          NodeTraits::set_color(x, NodeTraits::black());
0546    }
0547 
0548    static void rebalance_after_insertion(node_ptr header, node_ptr p) BOOST_NOEXCEPT
0549    {
0550       NodeTraits::set_color(p, NodeTraits::red());
0551       while(1){
0552          node_ptr p_parent(NodeTraits::get_parent(p));
0553          const node_ptr p_grandparent(NodeTraits::get_parent(p_parent));
0554          if(p_parent == header || NodeTraits::get_color(p_parent) == NodeTraits::black() || p_grandparent == header){
0555             break;
0556          }
0557 
0558          NodeTraits::set_color(p_grandparent, NodeTraits::red());
0559          node_ptr const p_grandparent_left (NodeTraits::get_left (p_grandparent));
0560          bool const p_parent_is_left_child = p_parent == p_grandparent_left;
0561          node_ptr const x(p_parent_is_left_child ? NodeTraits::get_right(p_grandparent) : p_grandparent_left);
0562 
0563          if(x && NodeTraits::get_color(x) == NodeTraits::red()){
0564             NodeTraits::set_color(x, NodeTraits::black());
0565             NodeTraits::set_color(p_parent, NodeTraits::black());
0566             p = p_grandparent;
0567          }
0568          else{ //Final step
0569             const bool p_is_left_child(NodeTraits::get_left(p_parent) == p);
0570             if(p_parent_is_left_child){ //p_parent is left child
0571                if(!p_is_left_child){ //p is right child
0572                   bstree_algo::rotate_left_no_parent_fix(p_parent, p);
0573                   //No need to link p and p_grandparent:
0574                   //    [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_left(p_grandparent, p)]
0575                   //as p_grandparent is not the header, another rotation is coming and p_parent
0576                   //will be the left child of p_grandparent
0577                   p_parent = p;
0578                }
0579                bstree_algo::rotate_right(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header);
0580             }
0581             else{  //p_parent is right child
0582                if(p_is_left_child){ //p is left child
0583                   bstree_algo::rotate_right_no_parent_fix(p_parent, p);
0584                   //No need to link p and p_grandparent:
0585                   //    [NodeTraits::set_parent(p, p_grandparent) + NodeTraits::set_right(p_grandparent, p)]
0586                   //as p_grandparent is not the header, another rotation is coming and p_parent
0587                   //will be the right child of p_grandparent
0588                   p_parent = p;
0589                }
0590                bstree_algo::rotate_left(p_grandparent, p_parent, NodeTraits::get_parent(p_grandparent), header);
0591             }
0592             NodeTraits::set_color(p_parent, NodeTraits::black());
0593             break;
0594          }
0595       }
0596       NodeTraits::set_color(NodeTraits::get_parent(header), NodeTraits::black());
0597    }
0598    /// @endcond
0599 };
0600 
0601 /// @cond
0602 
0603 template<class NodeTraits>
0604 struct get_algo<RbTreeAlgorithms, NodeTraits>
0605 {
0606    typedef rbtree_algorithms<NodeTraits> type;
0607 };
0608 
0609 template <class ValueTraits, class NodePtrCompare, class ExtraChecker>
0610 struct get_node_checker<RbTreeAlgorithms, ValueTraits, NodePtrCompare, ExtraChecker>
0611 {
0612     typedef detail::rbtree_node_checker<ValueTraits, NodePtrCompare, ExtraChecker> type;
0613 };
0614 
0615 /// @endcond
0616 
0617 } //namespace intrusive
0618 } //namespace boost
0619 
0620 #include <boost/intrusive/detail/config_end.hpp>
0621 
0622 #endif //BOOST_INTRUSIVE_RBTREE_ALGORITHMS_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!