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/twin.hpp> //for node_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 //A simple struct containing:
66 //
67 // typedef node_ptr type;
68 // node_ptr first;
69 // node_ptr second;
70 typedef twin<node_ptr> node_pair;
71
72 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
73
74 //! <b>Effects</b>: Constructs an non-used list element, putting the next
75 //! pointer to null:
76 //! <tt>NodeTraits::get_next(this_node) == node_ptr()</tt>
77 //!
78 //! <b>Complexity</b>: Constant
79 //!
80 //! <b>Throws</b>: Nothing.
81 static void init(node_ptr this_node) BOOST_NOEXCEPT;
82
83 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
84 //!
85 //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:
86 //! or it's a not inserted node:
87 //! <tt>return node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt>
88 //!
89 //! <b>Complexity</b>: Constant
90 //!
91 //! <b>Throws</b>: Nothing.
92 static bool unique(const_node_ptr this_node) BOOST_NOEXCEPT;
93
94 //! <b>Effects</b>: Returns true is "this_node" has the same state as if
95 //! it was inited using "init(node_ptr)"
96 //!
97 //! <b>Complexity</b>: Constant
98 //!
99 //! <b>Throws</b>: Nothing.
100 static bool inited(const_node_ptr this_node) BOOST_NOEXCEPT;
101
102 //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list.
103 //!
104 //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list.
105 //!
106 //! <b>Complexity</b>: Constant
107 //!
108 //! <b>Throws</b>: Nothing.
109 static void unlink_after(node_ptr prev_node) BOOST_NOEXCEPT;
110
111 //! <b>Requires</b>: prev_node and last_node must be in a circular list
112 //! or be an empty circular list.
113 //!
114 //! <b>Effects</b>: Unlinks the range (prev_node, last_node) from the linear list.
115 //!
116 //! <b>Complexity</b>: Constant
117 //!
118 //! <b>Throws</b>: Nothing.
119 static void unlink_after(node_ptr prev_node, node_ptr last_node) BOOST_NOEXCEPT;
120
121 //! <b>Requires</b>: prev_node must be a node of a linear list.
122 //!
123 //! <b>Effects</b>: Links this_node after prev_node in the linear list.
124 //!
125 //! <b>Complexity</b>: Constant
126 //!
127 //! <b>Throws</b>: Nothing.
128 static void link_after(node_ptr prev_node, node_ptr this_node) BOOST_NOEXCEPT;
129
130 //! <b>Requires</b>: b and e must be nodes of the same linear list or an empty range.
131 //! and p must be a node of a different linear list.
132 //!
133 //! <b>Effects</b>: Removes the nodes from (b, e] range from their linear list and inserts
134 //! them after p in p's linear list.
135 //!
136 //! <b>Complexity</b>: Constant
137 //!
138 //! <b>Throws</b>: Nothing.
139 static void transfer_after(node_ptr p, node_ptr b, node_ptr e) BOOST_NOEXCEPT;
140
141 #else
142
143 using base_t::transfer_after;
144
145 #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
146
147 //! <b>Effects</b>: Constructs an empty list, making this_node the only
148 //! node of the circular list:
149 //! <tt>NodeTraits::get_next(this_node) == this_node</tt>.
150 //!
151 //! <b>Complexity</b>: Constant
152 //!
153 //! <b>Throws</b>: Nothing.
154 inline static void init_header(node_ptr this_node) BOOST_NOEXCEPT
155 { NodeTraits::set_next(this_node, node_ptr()); }
156
157 //! <b>Requires</b>: 'p' is the first node of a list.
158 //!
159 //! <b>Effects</b>: Returns a pointer to a node that represents the "end" (one past end) node
160 //!
161 //! <b>Complexity</b>: Constant time.
162 //!
163 //! <b>Throws</b>: Nothing.
164 inline static node_ptr end_node(const_node_ptr) BOOST_NOEXCEPT
165 { return node_ptr(); }
166
167 //! <b>Effects</b>: Returns true if this_node_points to an empty list.
168 //!
169 //! <b>Complexity</b>: Constant
170 //!
171 //! <b>Throws</b>: Nothing.
172 inline static bool is_empty(const_node_ptr this_node) BOOST_NOEXCEPT
173 { return !NodeTraits::get_next(this_node); }
174
175 //! <b>Effects</b>: Returns true if this_node points to a sentinel node.
176 //!
177 //! <b>Complexity</b>: Constant
178 //!
179 //! <b>Throws</b>: Nothing.
180 inline static bool is_sentinel(const_node_ptr this_node) BOOST_NOEXCEPT
181 { return NodeTraits::get_next(this_node) == this_node; }
182
183 //! <b>Effects</b>: Marks this node as a "sentinel" node, a special state that is different from "empty",
184 //! that can be used to mark a special state of the list
185 //!
186 //! <b>Complexity</b>: Constant
187 //!
188 //! <b>Throws</b>: Nothing.
189 inline static void set_sentinel(node_ptr this_node) BOOST_NOEXCEPT
190 { NodeTraits::set_next(this_node, this_node); }
191
192 //! <b>Requires</b>: this_node and prev_init_node must be in the same linear list.
193 //!
194 //! <b>Effects</b>: Returns the previous node of this_node in the linear list starting.
195 //! the search from prev_init_node. The first node checked for equality
196 //! is NodeTraits::get_next(prev_init_node).
197 //!
198 //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node.
199 //!
200 //! <b>Throws</b>: Nothing.
201 inline static node_ptr
202 get_previous_node(node_ptr prev_init_node, node_ptr this_node) BOOST_NOEXCEPT
203 { return base_t::get_previous_node(prev_init_node, this_node); }
204
205 //! <b>Requires</b>: this_node must be in a linear list or be an empty linear list.
206 //!
207 //! <b>Effects</b>: Returns the number of nodes in a linear list. If the linear list
208 //! is empty, returns 1.
209 //!
210 //! <b>Complexity</b>: Linear
211 //!
212 //! <b>Throws</b>: Nothing.
213 static std::size_t count(const_node_ptr this_node) BOOST_NOEXCEPT
214 {
215 std::size_t result = 0;
216 const_node_ptr p = this_node;
217 do{
218 p = NodeTraits::get_next(p);
219 ++result;
220 } while (p);
221 return result;
222 }
223
224 //! <b>Requires</b>: this_node and other_node must be nodes inserted
225 //! in linear lists or be empty linear lists.
226 //!
227 //! <b>Effects</b>: Moves all the nodes previously chained after this_node after other_node
228 //! and vice-versa.
229 //!
230 //! <b>Complexity</b>: Constant
231 //!
232 //! <b>Throws</b>: Nothing.
233 inline static void swap_trailing_nodes(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT
234 {
235 node_ptr this_nxt = NodeTraits::get_next(this_node);
236 node_ptr other_nxt = NodeTraits::get_next(other_node);
237 NodeTraits::set_next(this_node, other_nxt);
238 NodeTraits::set_next(other_node, this_nxt);
239 }
240
241 //! <b>Effects</b>: Reverses the order of elements in the list.
242 //!
243 //! <b>Returns</b>: The new first node of the list.
244 //!
245 //! <b>Throws</b>: Nothing.
246 //!
247 //! <b>Complexity</b>: This function is linear to the contained elements.
248 static node_ptr reverse(node_ptr p) BOOST_NOEXCEPT
249 {
250 if(!p) return node_ptr();
251 node_ptr i = NodeTraits::get_next(p);
252 node_ptr first(p);
253 while(i){
254 node_ptr nxti(NodeTraits::get_next(i));
255 base_t::unlink_after(p);
256 NodeTraits::set_next(i, first);
257 first = i;
258 i = nxti;
259 }
260 return first;
261 }
262
263 //! <b>Effects</b>: Moves the first n nodes starting at p to the end of the list.
264 //!
265 //! <b>Returns</b>: A pair containing the new first and last node of the list or
266 //! if there has been any movement, a null pair if n leads to no movement.
267 //!
268 //! <b>Throws</b>: Nothing.
269 //!
270 //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
271 static node_pair move_first_n_backwards(node_ptr p, std::size_t n) BOOST_NOEXCEPT
272 {
273 node_pair ret;
274 //Null shift, or count() == 0 or 1, nothing to do
275 if(!n || !p || !NodeTraits::get_next(p)){
276 return ret;
277 }
278
279 node_ptr first = p;
280 bool end_found = false;
281 node_ptr new_last = node_ptr();
282 node_ptr old_last = node_ptr();
283
284 //Now find the new last node according to the shift count.
285 //If we find 0 before finding the new last node
286 //unlink p, shortcut the search now that we know the size of the list
287 //and continue.
288 for(std::size_t i = 1; i <= n; ++i){
289 new_last = first;
290 first = NodeTraits::get_next(first);
291 if(first == node_ptr()){
292 //Shortcut the shift with the modulo of the size of the list
293 n %= i;
294 if(!n) return ret;
295 old_last = new_last;
296 i = 0;
297 //Unlink p and continue the new first node search
298 first = p;
299 //unlink_after(new_last);
300 end_found = true;
301 }
302 }
303
304 //If the p has not been found in the previous loop, find it
305 //starting in the new first node and unlink it
306 if(!end_found){
307 old_last = base_t::get_previous_node(first, node_ptr());
308 }
309
310 //Now link p after the new last node
311 NodeTraits::set_next(old_last, p);
312 NodeTraits::set_next(new_last, node_ptr());
313 ret.first = first;
314 ret.second = new_last;
315 return ret;
316 }
317
318 //! <b>Effects</b>: Moves the first n nodes starting at p to the beginning of the list.
319 //!
320 //! <b>Returns</b>: A pair containing the new first and last node of the list or
321 //! if there has been any movement, a null pair if n leads to no movement.
322 //!
323 //! <b>Throws</b>: Nothing.
324 //!
325 //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
326 static node_pair move_first_n_forward(node_ptr p, std::size_t n) BOOST_NOEXCEPT
327 {
328 node_pair ret;
329 //Null shift, or count() == 0 or 1, nothing to do
330 if(!n || !p || !NodeTraits::get_next(p))
331 return ret;
332
333 node_ptr first = p;
334
335 //Iterate until p is found to know where the current last node is.
336 //If the shift count is less than the size of the list, we can also obtain
337 //the position of the new last node after the shift.
338 node_ptr old_last(first), next_to_it, new_last(p);
339 std::size_t distance = 1;
340 while(!!(next_to_it = node_traits::get_next(old_last))){
341 if(distance++ > n)
342 new_last = node_traits::get_next(new_last);
343 old_last = next_to_it;
344 }
345 //If the shift was bigger or equal than the size, obtain the equivalent
346 //forward shifts and find the new last node.
347 if(distance <= n){
348 //Now find the equivalent forward shifts.
349 //Shortcut the shift with the modulo of the size of the list
350 std::size_t new_before_last_pos = (distance - (n % distance))% distance;
351 //If the shift is a multiple of the size there is nothing to do
352 if(!new_before_last_pos)
353 return ret;
354
355 for( new_last = p
356 ; --new_before_last_pos
357 ; new_last = node_traits::get_next(new_last)){
358 //empty
359 }
360 }
361
362 //Get the first new node
363 node_ptr new_first(node_traits::get_next(new_last));
364 //Now put the old beginning after the old end
365 NodeTraits::set_next(old_last, p);
366 NodeTraits::set_next(new_last, node_ptr());
367 ret.first = new_first;
368 ret.second = new_last;
369 return ret;
370 }
371
372 //! <b>Requires</b>: other must be a list and p must be a node of a different linear list.
373 //!
374 //! <b>Effects</b>: Transfers all nodes from other after p in p's linear list.
375 //!
376 //! <b>Complexity</b>: Linear
377 //!
378 //! <b>Throws</b>: Nothing.
379 static void transfer_after(node_ptr p, node_ptr other) BOOST_NOEXCEPT
380 {
381 if ((is_empty)(this_node: p)) {
382 (swap_trailing_nodes)(this_node: p, other_node: other);
383 }
384 else {
385 node_ptr other_last((get_previous_node)(prev_init_node: other, this_node: node_ptr()));
386 base_t::transfer_after(p, other, other_last);
387 }
388 }
389
390 //! <b>Requires</b>: "disposer" must be an object function
391 //! taking a node_ptr parameter and shouldn't throw.
392 //!
393 //! <b>Effects</b>: Unlinks all nodes reachable from p (but not p) and calls
394 //! <tt>void disposer::operator()(node_ptr)</tt> for every node of the list
395 //! where p is linked.
396 //!
397 //! <b>Returns</b>: The number of disposed nodes
398 //!
399 //! <b>Complexity</b>: Linear to the number of element of the list.
400 //!
401 //! <b>Throws</b>: Nothing.
402 template<class Disposer>
403 inline static std::size_t detach_and_dispose(node_ptr p, Disposer disposer) BOOST_NOEXCEPT
404 { return base_t::unlink_after_and_dispose(p, node_ptr(), disposer); }
405};
406
407/// @cond
408
409template<class NodeTraits>
410struct get_algo<LinearSListAlgorithms, NodeTraits>
411{
412 typedef linear_slist_algorithms<NodeTraits> type;
413};
414
415/// @endcond
416
417} //namespace intrusive
418} //namespace boost
419
420#include <boost/intrusive/detail/config_end.hpp>
421
422#endif //BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP
423

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