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 
get_previous_node(node_ptr p,const node_ptr & this_node)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 
init(const node_ptr & this_node)55    static void init(const node_ptr & this_node)
56    {  NodeTraits::set_next(this_node, node_ptr());  }
57 
unique(const const_node_ptr & this_node)58    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 
inited(const const_node_ptr & this_node)64    static bool inited(const const_node_ptr & this_node)
65    {  return !NodeTraits::get_next(this_node); }
66 
unlink_after(const node_ptr & prev_node)67    static void unlink_after(const 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 
unlink_after(const node_ptr & prev_node,const node_ptr & last_node)73    static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node)
74    {  NodeTraits::set_next(prev_node, last_node);  }
75 
link_after(const node_ptr & prev_node,const node_ptr & this_node)76    static void link_after(const node_ptr & prev_node, const 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 
incorporate_after(const node_ptr & bp,const node_ptr & b,const node_ptr & be)82    static void incorporate_after(const node_ptr & bp, const node_ptr & b, const 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 
transfer_after(const node_ptr & bp,const node_ptr & bb,const node_ptr & be)89    static void transfer_after(const node_ptr & bp, const node_ptr & bb, const 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>
stable_partition(node_ptr before_beg,const node_ptr & end,Pred pred,stable_partition_info & info)110    static void stable_partition(node_ptr before_beg, const 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.
distance(const const_node_ptr & f,const const_node_ptr & l)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
199