1/////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Olaf Krzikalla 2004-2006.
4// (C) Copyright Ion Gaztanaga 2006-2014
5//
6// Distributed under the Boost Software License, Version 1.0.
7// (See accompanying file LICENSE_1_0.txt or copy at
8// http://www.boost.org/LICENSE_1_0.txt)
9//
10// See http://www.boost.org/libs/intrusive for documentation.
11//
12/////////////////////////////////////////////////////////////////////////////
13
14#ifndef BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP
15#define BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP
16
17#include <boost/intrusive/detail/config_begin.hpp>
18#include <boost/intrusive/intrusive_fwd.hpp>
19#include <boost/intrusive/detail/common_slist_algorithms.hpp>
20#include <boost/intrusive/detail/algo_type.hpp>
21#include <cstddef>
22#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair
23
24#if defined(BOOST_HAS_PRAGMA_ONCE)
25# pragma once
26#endif
27
28namespace boost {
29namespace intrusive {
30
31//! linear_slist_algorithms provides basic algorithms to manipulate nodes
32//! forming a linear singly linked list.
33//!
34//! linear_slist_algorithms is configured with a NodeTraits class, which encapsulates the
35//! information about the node to be manipulated. NodeTraits must support the
36//! following interface:
37//!
38//! <b>Typedefs</b>:
39//!
40//! <tt>node</tt>: The type of the node that forms the linear list
41//!
42//! <tt>node_ptr</tt>: A pointer to a node
43//!
44//! <tt>const_node_ptr</tt>: A pointer to a const node
45//!
46//! <b>Static functions</b>:
47//!
48//! <tt>static node_ptr get_next(const_node_ptr n);</tt>
49//!
50//! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
51template<class NodeTraits>
52class linear_slist_algorithms
53 /// @cond
54 : public detail::common_slist_algorithms<NodeTraits>
55 /// @endcond
56{
57 /// @cond
58 typedef detail::common_slist_algorithms<NodeTraits> base_t;
59 /// @endcond
60 public:
61 typedef typename NodeTraits::node node;
62 typedef typename NodeTraits::node_ptr node_ptr;
63 typedef typename NodeTraits::const_node_ptr const_node_ptr;
64 typedef NodeTraits node_traits;
65
66 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
67
68 //! <b>Effects</b>: Constructs an non-used list element, putting the next
69 //! pointer to null:
70 //! <tt>NodeTraits::get_next(this_node) == node_ptr()</tt>
71 //!
72 //! <b>Complexity</b>: Constant
73 //!
74 //! <b>Throws</b>: Nothing.
75 static void init(const node_ptr & this_node);
76
77 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
78 //!
79 //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:
80 //! or it's a not inserted node:
81 //! <tt>return node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt>
82 //!
83 //! <b>Complexity</b>: Constant
84 //!
85 //! <b>Throws</b>: Nothing.
86 static bool unique(const_node_ptr this_node);
87
88 //! <b>Effects</b>: Returns true is "this_node" has the same state as if
89 //! it was inited using "init(node_ptr)"
90 //!
91 //! <b>Complexity</b>: Constant
92 //!
93 //! <b>Throws</b>: Nothing.
94 static bool inited(const_node_ptr this_node);
95
96 //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list.
97 //!
98 //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list.
99 //!
100 //! <b>Complexity</b>: Constant
101 //!
102 //! <b>Throws</b>: Nothing.
103 static void unlink_after(const node_ptr & prev_node);
104
105 //! <b>Requires</b>: prev_node and last_node must be in a circular list
106 //! or be an empty circular list.
107 //!
108 //! <b>Effects</b>: Unlinks the range (prev_node, last_node) from the linear list.
109 //!
110 //! <b>Complexity</b>: Constant
111 //!
112 //! <b>Throws</b>: Nothing.
113 static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node);
114
115 //! <b>Requires</b>: prev_node must be a node of a linear list.
116 //!
117 //! <b>Effects</b>: Links this_node after prev_node in the linear list.
118 //!
119 //! <b>Complexity</b>: Constant
120 //!
121 //! <b>Throws</b>: Nothing.
122 static void link_after(const node_ptr & prev_node, const node_ptr & this_node);
123
124 //! <b>Requires</b>: b and e must be nodes of the same linear list or an empty range.
125 //! and p must be a node of a different linear list.
126 //!
127 //! <b>Effects</b>: Removes the nodes from (b, e] range from their linear list and inserts
128 //! them after p in p's linear list.
129 //!
130 //! <b>Complexity</b>: Constant
131 //!
132 //! <b>Throws</b>: Nothing.
133 static void transfer_after(const node_ptr & p, const node_ptr & b, const node_ptr & e);
134
135 #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
136
137 //! <b>Effects</b>: Constructs an empty list, making this_node the only
138 //! node of the circular list:
139 //! <tt>NodeTraits::get_next(this_node) == this_node</tt>.
140 //!
141 //! <b>Complexity</b>: Constant
142 //!
143 //! <b>Throws</b>: Nothing.
144 static void init_header(const node_ptr & this_node)
145 { NodeTraits::set_next(this_node, node_ptr ()); }
146
147 //! <b>Requires</b>: this_node and prev_init_node must be in the same linear list.
148 //!
149 //! <b>Effects</b>: Returns the previous node of this_node in the linear list starting.
150 //! the search from prev_init_node. The first node checked for equality
151 //! is NodeTraits::get_next(prev_init_node).
152 //!
153 //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node.
154 //!
155 //! <b>Throws</b>: Nothing.
156 static node_ptr get_previous_node(const node_ptr & prev_init_node, const node_ptr & this_node)
157 { return base_t::get_previous_node(prev_init_node, this_node); }
158
159 //! <b>Requires</b>: this_node must be in a linear list or be an empty linear list.
160 //!
161 //! <b>Effects</b>: Returns the number of nodes in a linear list. If the linear list
162 //! is empty, returns 1.
163 //!
164 //! <b>Complexity</b>: Linear
165 //!
166 //! <b>Throws</b>: Nothing.
167 static std::size_t count(const const_node_ptr & this_node)
168 {
169 std::size_t result = 0;
170 const_node_ptr p = this_node;
171 do{
172 p = NodeTraits::get_next(p);
173 ++result;
174 } while (p);
175 return result;
176 }
177
178 //! <b>Requires</b>: this_node and other_node must be nodes inserted
179 //! in linear lists or be empty linear lists.
180 //!
181 //! <b>Effects</b>: Moves all the nodes previously chained after this_node after other_node
182 //! and vice-versa.
183 //!
184 //! <b>Complexity</b>: Constant
185 //!
186 //! <b>Throws</b>: Nothing.
187 static void swap_trailing_nodes(const node_ptr & this_node, const node_ptr & other_node)
188 {
189 node_ptr this_nxt = NodeTraits::get_next(this_node);
190 node_ptr other_nxt = NodeTraits::get_next(other_node);
191 NodeTraits::set_next(this_node, other_nxt);
192 NodeTraits::set_next(other_node, this_nxt);
193 }
194
195 //! <b>Effects</b>: Reverses the order of elements in the list.
196 //!
197 //! <b>Returns</b>: The new first node of the list.
198 //!
199 //! <b>Throws</b>: Nothing.
200 //!
201 //! <b>Complexity</b>: This function is linear to the contained elements.
202 static node_ptr reverse(const node_ptr & p)
203 {
204 if(!p) return node_ptr();
205 node_ptr i = NodeTraits::get_next(p);
206 node_ptr first(p);
207 while(i){
208 node_ptr nxti(NodeTraits::get_next(i));
209 base_t::unlink_after(p);
210 NodeTraits::set_next(i, first);
211 first = i;
212 i = nxti;
213 }
214 return first;
215 }
216
217 //! <b>Effects</b>: Moves the first n nodes starting at p to the end of the list.
218 //!
219 //! <b>Returns</b>: A pair containing the new first and last node of the list or
220 //! if there has been any movement, a null pair if n leads to no movement.
221 //!
222 //! <b>Throws</b>: Nothing.
223 //!
224 //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
225 static std::pair<node_ptr, node_ptr> move_first_n_backwards(const node_ptr & p, std::size_t n)
226 {
227 std::pair<node_ptr, node_ptr> ret;
228 //Null shift, or count() == 0 or 1, nothing to do
229 if(!n || !p || !NodeTraits::get_next(p)){
230 return ret;
231 }
232
233 node_ptr first = p;
234 bool end_found = false;
235 node_ptr new_last = node_ptr();
236 node_ptr old_last = node_ptr();
237
238 //Now find the new last node according to the shift count.
239 //If we find 0 before finding the new last node
240 //unlink p, shortcut the search now that we know the size of the list
241 //and continue.
242 for(std::size_t i = 1; i <= n; ++i){
243 new_last = first;
244 first = NodeTraits::get_next(first);
245 if(first == node_ptr()){
246 //Shortcut the shift with the modulo of the size of the list
247 n %= i;
248 if(!n) return ret;
249 old_last = new_last;
250 i = 0;
251 //Unlink p and continue the new first node search
252 first = p;
253 //unlink_after(new_last);
254 end_found = true;
255 }
256 }
257
258 //If the p has not been found in the previous loop, find it
259 //starting in the new first node and unlink it
260 if(!end_found){
261 old_last = base_t::get_previous_node(first, node_ptr());
262 }
263
264 //Now link p after the new last node
265 NodeTraits::set_next(old_last, p);
266 NodeTraits::set_next(new_last, node_ptr());
267 ret.first = first;
268 ret.second = new_last;
269 return ret;
270 }
271
272 //! <b>Effects</b>: Moves the first n nodes starting at p to the beginning of the list.
273 //!
274 //! <b>Returns</b>: A pair containing the new first and last node of the list or
275 //! if there has been any movement, a null pair if n leads to no movement.
276 //!
277 //! <b>Throws</b>: Nothing.
278 //!
279 //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
280 static std::pair<node_ptr, node_ptr> move_first_n_forward(const node_ptr & p, std::size_t n)
281 {
282 std::pair<node_ptr, node_ptr> ret;
283 //Null shift, or count() == 0 or 1, nothing to do
284 if(!n || !p || !NodeTraits::get_next(p))
285 return ret;
286
287 node_ptr first = p;
288
289 //Iterate until p is found to know where the current last node is.
290 //If the shift count is less than the size of the list, we can also obtain
291 //the position of the new last node after the shift.
292 node_ptr old_last(first), next_to_it, new_last(p);
293 std::size_t distance = 1;
294 while(!!(next_to_it = node_traits::get_next(old_last))){
295 if(distance++ > n)
296 new_last = node_traits::get_next(new_last);
297 old_last = next_to_it;
298 }
299 //If the shift was bigger or equal than the size, obtain the equivalent
300 //forward shifts and find the new last node.
301 if(distance <= n){
302 //Now find the equivalent forward shifts.
303 //Shortcut the shift with the modulo of the size of the list
304 std::size_t new_before_last_pos = (distance - (n % distance))% distance;
305 //If the shift is a multiple of the size there is nothing to do
306 if(!new_before_last_pos)
307 return ret;
308
309 for( new_last = p
310 ; --new_before_last_pos
311 ; new_last = node_traits::get_next(new_last)){
312 //empty
313 }
314 }
315
316 //Get the first new node
317 node_ptr new_first(node_traits::get_next(new_last));
318 //Now put the old beginning after the old end
319 NodeTraits::set_next(old_last, p);
320 NodeTraits::set_next(new_last, node_ptr());
321 ret.first = new_first;
322 ret.second = new_last;
323 return ret;
324 }
325};
326
327/// @cond
328
329template<class NodeTraits>
330struct get_algo<LinearSListAlgorithms, NodeTraits>
331{
332 typedef linear_slist_algorithms<NodeTraits> type;
333};
334
335/// @endcond
336
337} //namespace intrusive
338} //namespace boost
339
340#include <boost/intrusive/detail/config_end.hpp>
341
342#endif //BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP
343

source code of boost/boost/intrusive/linear_slist_algorithms.hpp