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/workaround.hpp>
26#include <boost/intrusive/detail/assert.hpp>
27#include <boost/intrusive/detail/algo_type.hpp>
28#include <cstddef>
29
30namespace boost {
31namespace intrusive {
32namespace detail {
33
34template<class NodeTraits>
35class 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, 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 inline static void init(node_ptr this_node) BOOST_NOEXCEPT
56 { NodeTraits::set_next(this_node, node_ptr()); }
57
58 static bool unique(const_node_ptr this_node) BOOST_NOEXCEPT
59 {
60 node_ptr next = NodeTraits::get_next(this_node);
61 return !next || next == this_node;
62 }
63
64 inline static bool inited(const_node_ptr this_node) BOOST_NOEXCEPT
65 { return !NodeTraits::get_next(this_node); }
66
67 inline static void unlink_after(node_ptr prev_node) BOOST_NOEXCEPT
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 inline static void unlink_after(node_ptr prev_node, node_ptr last_node) BOOST_NOEXCEPT
74 { NodeTraits::set_next(prev_node, last_node); }
75
76 static void link_after(node_ptr prev_node, node_ptr this_node) BOOST_NOEXCEPT
77 {
78 NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node));
79 NodeTraits::set_next(prev_node, this_node);
80 }
81
82 static void incorporate_after(node_ptr bp, node_ptr b, node_ptr be) BOOST_NOEXCEPT
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) BOOST_NOEXCEPT
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_INTRUSIVE_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_INTRUSIVE_CATCH(...){
149 node_traits::set_next(last_to_remove, new_f);
150 BOOST_INTRUSIVE_RETHROW;
151 }
152 BOOST_INTRUSIVE_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_node_ptr f, const_node_ptr l) BOOST_NOEXCEPT
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 //! <b>Requires</b>: "disposer" must be an object function
182 //! taking a node_ptr parameter and shouldn't throw.
183 //!
184 //! <b>Effects</b>: Calls
185 //! <tt>void disposer::operator()(node_ptr)</tt> for every node of the list
186 //! [p, e).
187 //!
188 //! <b>Returns</b>: The number of unlinked/disposed nodes
189 //!
190 //! <b>Complexity</b>: Linear to the number of element of the list.
191 //!
192 //! <b>Throws</b>: Nothing.
193 template<class Disposer>
194 static std::size_t unlink_after_and_dispose(node_ptr bb, node_ptr e, Disposer disposer) BOOST_NOEXCEPT
195 {
196 std::size_t n = 0u;
197 node_ptr i = node_traits::get_next(bb);
198 while (i != e) {
199 node_ptr to_erase(i);
200 i = node_traits::get_next(i);
201 disposer(to_erase);
202 ++n;
203 }
204 node_traits::set_next(bb, e);
205 return n;
206 }
207
208 //! <b>Requires</b>: "disposer" must be an object function
209 //! taking a node_ptr parameter and shouldn't throw.
210 //!
211 //! <b>Effects</b>: Calls
212 //! <tt>void disposer::operator()(node_ptr)</tt> for every node of the list
213 //! after p (but not for p). Works for circular or linear lists
214 //!
215 //! <b>Complexity</b>: Linear to the number of element of the list.
216 //!
217 //! <b>Throws</b>: Nothing.
218 template<class Disposer>
219 inline static void unlink_after_and_dispose(node_ptr bb, Disposer disposer) BOOST_NOEXCEPT
220 {
221 node_ptr i = node_traits::get_next(bb);
222 node_traits::set_next(bb, node_traits::get_next(i));
223 disposer(i);
224 }
225
226 //! <b>Requires</b>: "disposer" must be an object function
227 //! taking a node_ptr parameter and shouldn't throw.
228 //!
229 //! <b>Effects</b>: Unlinks all nodes reachable from p (but not p) and calls
230 //! <tt>void disposer::operator()(node_ptr)</tt> for every node of the list
231 //! where p is linked.
232 //!
233 //! <b>Complexity</b>: Linear to the number of element of the list.
234 //!
235 //! <b>Throws</b>: Nothing.
236 template<class Disposer>
237 static std::size_t detach_and_dispose(node_ptr p, Disposer disposer) BOOST_NOEXCEPT
238 {
239 std::size_t n = 0;
240 node_ptr i = node_traits::get_next(p);
241 while ( i != p || i != node_ptr() ) {
242 node_ptr to_erase(i);
243 i = node_traits::get_next(i);
244 disposer(to_erase);
245 }
246 node_traits::set_next(p, i);
247 return n;
248 }
249};
250
251/// @endcond
252
253} //namespace detail
254
255/// @cond
256
257template<class NodeTraits>
258struct get_algo<CommonSListAlgorithms, NodeTraits>
259{
260 typedef detail::common_slist_algorithms<NodeTraits> type;
261};
262
263
264} //namespace intrusive
265} //namespace boost
266
267#endif //BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP
268

source code of boost/libs/intrusive/include/boost/intrusive/detail/common_slist_algorithms.hpp