intrusive/detail/common_slist_algorithms.hpp

0001 /////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga  2007-2014
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 //    (See accompanying file LICENSE_1_0.txt or copy at
0007 //          http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // See http://www.boost.org/libs/intrusive for documentation.
0010 //
0011 /////////////////////////////////////////////////////////////////////////////
0012
0013 #ifndef BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP
0014 #define BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP
0015
0016 #ifndef BOOST_CONFIG_HPP
0017 #  include <boost/config.hpp>
0018 #endif
0019
0020 #if defined(BOOST_HAS_PRAGMA_ONCE)
0021 #  pragma once
0022 #endif
0023
0024 #include <boost/intrusive/intrusive_fwd.hpp>
0025 #include <boost/intrusive/detail/workaround.hpp>
0026 #include <boost/intrusive/detail/assert.hpp>
0027 #include <boost/intrusive/detail/algo_type.hpp>
0028 #include <cstddef>
0029
0030 namespace boost {
0031 namespace intrusive {
0032 namespace detail {
0033
0034 template<class NodeTraits>
0035 class common_slist_algorithms
0036 {
0037    public:
0038    typedef typename NodeTraits::node            node;
0039    typedef typename NodeTraits::node_ptr        node_ptr;
0040    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
0041    typedef NodeTraits                           node_traits;
0042
0043    static node_ptr get_previous_node(node_ptr p, node_ptr this_node)
0044    {
0045       for( node_ptr p_next
0046          ; this_node != (p_next = NodeTraits::get_next(p))
0047          ; p = p_next){
0048          //Logic error: possible use of linear lists with
0049          //operations only permitted with circular lists
0050          BOOST_INTRUSIVE_INVARIANT_ASSERT(p);
0051       }
0052       return p;
0053    }
0054
0055    BOOST_INTRUSIVE_FORCEINLINE static void init(node_ptr this_node) BOOST_NOEXCEPT
0056    {  NodeTraits::set_next(this_node, node_ptr());  }
0057
0058    static bool unique(const_node_ptr this_node) BOOST_NOEXCEPT
0059    {
0060       node_ptr next = NodeTraits::get_next(this_node);
0061       return !next || next == this_node;
0062    }
0063
0064    BOOST_INTRUSIVE_FORCEINLINE static bool inited(const_node_ptr this_node) BOOST_NOEXCEPT
0065    {  return !NodeTraits::get_next(this_node); }
0066
0067    BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(node_ptr prev_node) BOOST_NOEXCEPT
0068    {
0069       const_node_ptr this_node(NodeTraits::get_next(prev_node));
0070       NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node));
0071    }
0072
0073    BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(node_ptr prev_node, node_ptr last_node) BOOST_NOEXCEPT
0074    {  NodeTraits::set_next(prev_node, last_node);  }
0075
0076    static void link_after(node_ptr prev_node, node_ptr this_node) BOOST_NOEXCEPT
0077    {
0078       NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node));
0079       NodeTraits::set_next(prev_node, this_node);
0080    }
0081
0082    static void incorporate_after(node_ptr bp, node_ptr b, node_ptr be) BOOST_NOEXCEPT
0083    {
0084       node_ptr p(NodeTraits::get_next(bp));
0085       NodeTraits::set_next(bp, b);
0086       NodeTraits::set_next(be, p);
0087    }
0088
0089    static void transfer_after(node_ptr bp, node_ptr bb, node_ptr be) BOOST_NOEXCEPT
0090    {
0091       if (bp != bb && bp != be && bb != be) {
0092          node_ptr next_b = NodeTraits::get_next(bb);
0093          node_ptr next_e = NodeTraits::get_next(be);
0094          node_ptr next_p = NodeTraits::get_next(bp);
0095          NodeTraits::set_next(bb, next_e);
0096          NodeTraits::set_next(be, next_p);
0097          NodeTraits::set_next(bp, next_b);
0098       }
0099    }
0100
0101    struct stable_partition_info
0102    {
0103       std::size_t num_1st_partition;
0104       std::size_t num_2nd_partition;
0105       node_ptr    beg_2st_partition;
0106       node_ptr    new_last_node;
0107    };
0108
0109    template<class Pred>
0110    static void stable_partition(node_ptr before_beg, node_ptr end, Pred pred, stable_partition_info &info)
0111    {
0112       node_ptr bcur = before_beg;
0113       node_ptr cur  = node_traits::get_next(bcur);
0114       node_ptr new_f = end;
0115
0116       std::size_t num1 = 0, num2 = 0;
0117       while(cur != end){
0118          if(pred(cur)){
0119             ++num1;
0120             bcur = cur;
0121             cur  = node_traits::get_next(cur);
0122          }
0123          else{
0124             ++num2;
0125             node_ptr last_to_remove = bcur;
0126             new_f = cur;
0127             bcur = cur;
0128             cur  = node_traits::get_next(cur);
0129             BOOST_INTRUSIVE_TRY{
0130                //Main loop
0131                while(cur != end){
0132                   if(pred(cur)){ //Might throw
0133                      ++num1;
0134                      //Process current node
0135                      node_traits::set_next(last_to_remove, cur);
0136                      last_to_remove = cur;
0137                      node_ptr nxt = node_traits::get_next(cur);
0138                      node_traits::set_next(bcur, nxt);
0139                      cur = nxt;
0140                   }
0141                   else{
0142                      ++num2;
0143                      bcur = cur;
0144                      cur  = node_traits::get_next(cur);
0145                   }
0146                }
0147             }
0148             BOOST_INTRUSIVE_CATCH(...){
0149                node_traits::set_next(last_to_remove, new_f);
0150                BOOST_INTRUSIVE_RETHROW;
0151             }
0152             BOOST_INTRUSIVE_CATCH_END
0153             node_traits::set_next(last_to_remove, new_f);
0154             break;
0155          }
0156       }
0157       info.num_1st_partition = num1;
0158       info.num_2nd_partition = num2;
0159       info.beg_2st_partition = new_f;
0160       info.new_last_node = bcur;
0161    }
0162
0163    //! <b>Requires</b>: f and l must be in a circular list.
0164    //!
0165    //! <b>Effects</b>: Returns the number of nodes in the range [f, l).
0166    //!
0167    //! <b>Complexity</b>: Linear
0168    //!
0169    //! <b>Throws</b>: Nothing.
0170    static std::size_t distance(const_node_ptr f, const_node_ptr l) BOOST_NOEXCEPT
0171    {
0172       const_node_ptr i(f);
0173       std::size_t result = 0;
0174       while(i != l){
0175          i = NodeTraits::get_next(i);
0176          ++result;
0177       }
0178       return result;
0179    }
0180
0181    //! <b>Requires</b>: "disposer" must be an object function
0182    //!   taking a node_ptr parameter and shouldn't throw.
0183    //!
0184    //! <b>Effects</b>: Calls
0185    //!   <tt>void disposer::operator()(node_ptr)</tt> for every node of the list
0186    //!    [p, e).
0187    //!
0188    //! <b>Returns</b>: The number of unlinked/disposed nodes
0189    //!
0190    //! <b>Complexity</b>: Linear to the number of element of the list.
0191    //!
0192    //! <b>Throws</b>: Nothing.
0193    template<class Disposer>
0194    static std::size_t unlink_after_and_dispose(node_ptr bb, node_ptr e, Disposer disposer) BOOST_NOEXCEPT
0195    {
0196       std::size_t n = 0u;
0197       node_ptr i = node_traits::get_next(bb);
0198       while (i != e) {
0199          node_ptr to_erase(i);
0200          i = node_traits::get_next(i);
0201          disposer(to_erase);
0202          ++n;
0203       }
0204       node_traits::set_next(bb, e);
0205       return n;
0206    }
0207
0208    //! <b>Requires</b>: "disposer" must be an object function
0209    //!   taking a node_ptr parameter and shouldn't throw.
0210    //!
0211    //! <b>Effects</b>: Calls
0212    //!   <tt>void disposer::operator()(node_ptr)</tt> for every node of the list
0213    //!    after p (but not for p). Works for circular or linear lists
0214    //!
0215    //! <b>Complexity</b>: Linear to the number of element of the list.
0216    //!
0217    //! <b>Throws</b>: Nothing.
0218    template<class Disposer>
0219    BOOST_INTRUSIVE_FORCEINLINE static void unlink_after_and_dispose(node_ptr bb, Disposer disposer) BOOST_NOEXCEPT
0220    {
0221       node_ptr i = node_traits::get_next(bb);
0222       node_traits::set_next(bb, node_traits::get_next(i));
0223       disposer(i);
0224    }
0225
0226    //! <b>Requires</b>: "disposer" must be an object function
0227    //!   taking a node_ptr parameter and shouldn't throw.
0228    //!
0229    //! <b>Effects</b>: Unlinks all nodes reachable from p (but not p) and calls
0230    //!   <tt>void disposer::operator()(node_ptr)</tt> for every node of the list
0231    //!    where p is linked.
0232    //!
0233    //! <b>Complexity</b>: Linear to the number of element of the list.
0234    //!
0235    //! <b>Throws</b>: Nothing.
0236    template<class Disposer>
0237    static std::size_t detach_and_dispose(node_ptr p, Disposer disposer) BOOST_NOEXCEPT
0238    {
0239       std::size_t n = 0;
0240       node_ptr i = node_traits::get_next(p);
0241       while ( i != p || i != node_ptr() ) {
0242          node_ptr to_erase(i);
0243          i = node_traits::get_next(i);
0244          disposer(to_erase);
0245       }
0246       node_traits::set_next(p, i);
0247       return n;
0248    }
0249 };
0250
0251 /// @endcond
0252
0253 } //namespace detail
0254
0255 /// @cond
0256
0257 template<class NodeTraits>
0258 struct get_algo<CommonSListAlgorithms, NodeTraits>
0259 {
0260    typedef detail::common_slist_algorithms<NodeTraits> type;
0261 };
0262
0263
0264 } //namespace intrusive
0265 } //namespace boost
0266
0267 #endif //BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP