ceph/src/boost/boost/intrusive/detail/common_slist_algorithms.hpp

   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_COMMON_SLIST_ALGORITHMS_HPP
  14 #define BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP
  15
  16 #ifndef BOOST_CONFIG_HPP
  17 #  include <boost/config.hpp>
  18 #endif
  19
  20 #if defined(BOOST_HAS_PRAGMA_ONCE)
  21 #  pragma once
  22 #endif
  23
  24 #include <boost/intrusive/intrusive_fwd.hpp>
  25 #include <boost/intrusive/detail/assert.hpp>
  26 #include <boost/intrusive/detail/algo_type.hpp>
  27 #include <boost/core/no_exceptions_support.hpp>
  28 #include <cstddef>
  29
  30 namespace boost {
  31 namespace intrusive {
  32 namespace detail {
  33
  34 template<class NodeTraits>
  35 class common_slist_algorithms
  36 {
  37    public:
  38    typedef typename NodeTraits::node            node;
  39    typedef typename NodeTraits::node_ptr        node_ptr;
  40    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
  41    typedef NodeTraits                           node_traits;
  42
  43    static node_ptr get_previous_node(node_ptr p, const node_ptr & this_node)
  44    {
  45       for( node_ptr p_next
  46          ; this_node != (p_next = NodeTraits::get_next(p))
  47          ; p = p_next){
  48          //Logic error: possible use of linear lists with
  49          //operations only permitted with circular lists
  50          BOOST_INTRUSIVE_INVARIANT_ASSERT(p);
  51       }
  52       return p;
  53    }
  54
  55    BOOST_INTRUSIVE_FORCEINLINE static void init(node_ptr this_node)
  56    {  NodeTraits::set_next(this_node, node_ptr());  }
  57
  58    BOOST_INTRUSIVE_FORCEINLINE static bool unique(const const_node_ptr & this_node)
  59    {
  60       node_ptr next = NodeTraits::get_next(this_node);
  61       return !next || next == this_node;
  62    }
  63
  64    BOOST_INTRUSIVE_FORCEINLINE static bool inited(const const_node_ptr & this_node)
  65    {  return !NodeTraits::get_next(this_node); }
  66
  67    BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(node_ptr prev_node)
  68    {
  69       const_node_ptr this_node(NodeTraits::get_next(prev_node));
  70       NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node));
  71    }
  72
  73    BOOST_INTRUSIVE_FORCEINLINE static void unlink_after(node_ptr prev_node, node_ptr last_node)
  74    {  NodeTraits::set_next(prev_node, last_node);  }
  75
  76    BOOST_INTRUSIVE_FORCEINLINE static void link_after(node_ptr prev_node, node_ptr this_node)
  77    {
  78       NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node));
  79       NodeTraits::set_next(prev_node, this_node);
  80    }
  81
  82    BOOST_INTRUSIVE_FORCEINLINE static void incorporate_after(node_ptr bp, node_ptr b, node_ptr be)
  83    {
  84       node_ptr p(NodeTraits::get_next(bp));
  85       NodeTraits::set_next(bp, b);
  86       NodeTraits::set_next(be, p);
  87    }
  88
  89    static void transfer_after(node_ptr bp, node_ptr bb, node_ptr be)
  90    {
  91       if (bp != bb && bp != be && bb != be) {
  92          node_ptr next_b = NodeTraits::get_next(bb);
  93          node_ptr next_e = NodeTraits::get_next(be);
  94          node_ptr next_p = NodeTraits::get_next(bp);
  95          NodeTraits::set_next(bb, next_e);
  96          NodeTraits::set_next(be, next_p);
  97          NodeTraits::set_next(bp, next_b);
  98       }
  99    }
 100
 101    struct stable_partition_info
 102    {
 103       std::size_t num_1st_partition;
 104       std::size_t num_2nd_partition;
 105       node_ptr    beg_2st_partition;
 106       node_ptr    new_last_node;
 107    };
 108
 109    template<class Pred>
 110    static void stable_partition(node_ptr before_beg, node_ptr end, Pred pred, stable_partition_info &info)
 111    {
 112       node_ptr bcur = before_beg;
 113       node_ptr cur  = node_traits::get_next(bcur);
 114       node_ptr new_f = end;
 115
 116       std::size_t num1 = 0, num2 = 0;
 117       while(cur != end){
 118          if(pred(cur)){
 119             ++num1;
 120             bcur = cur;
 121             cur  = node_traits::get_next(cur);
 122          }
 123          else{
 124             ++num2;
 125             node_ptr last_to_remove = bcur;
 126             new_f = cur;
 127             bcur = cur;
 128             cur  = node_traits::get_next(cur);
 129             BOOST_TRY{
 130                //Main loop
 131                while(cur != end){
 132                   if(pred(cur)){ //Might throw
 133                      ++num1;
 134                      //Process current node
 135                      node_traits::set_next(last_to_remove, cur);
 136                      last_to_remove = cur;
 137                      node_ptr nxt = node_traits::get_next(cur);
 138                      node_traits::set_next(bcur, nxt);
 139                      cur = nxt;
 140                   }
 141                   else{
 142                      ++num2;
 143                      bcur = cur;
 144                      cur  = node_traits::get_next(cur);
 145                   }
 146                }
 147             }
 148             BOOST_CATCH(...){
 149                node_traits::set_next(last_to_remove, new_f);
 150                BOOST_RETHROW;
 151             }
 152             BOOST_CATCH_END
 153             node_traits::set_next(last_to_remove, new_f);
 154             break;
 155          }
 156       }
 157       info.num_1st_partition = num1;
 158       info.num_2nd_partition = num2;
 159       info.beg_2st_partition = new_f;
 160       info.new_last_node = bcur;
 161    }
 162
 163    //! <b>Requires</b>: f and l must be in a circular list.
 164    //!
 165    //! <b>Effects</b>: Returns the number of nodes in the range [f, l).
 166    //!
 167    //! <b>Complexity</b>: Linear
 168    //!
 169    //! <b>Throws</b>: Nothing.
 170    static std::size_t distance(const const_node_ptr &f, const const_node_ptr &l)
 171    {
 172       const_node_ptr i(f);
 173       std::size_t result = 0;
 174       while(i != l){
 175          i = NodeTraits::get_next(i);
 176          ++result;
 177       }
 178       return result;
 179    }
 180 };
 181
 182 /// @endcond
 183
 184 } //namespace detail
 185
 186 /// @cond
 187
 188 template<class NodeTraits>
 189 struct get_algo<CommonSListAlgorithms, NodeTraits>
 190 {
 191    typedef detail::common_slist_algorithms<NodeTraits> type;
 192 };
 193
 194
 195 } //namespace intrusive
 196 } //namespace boost
 197
 198 #endif //BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP