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_CIRCULAR_SLIST_ALGORITHMS_HPP
15#define BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP
16
17#include <cstddef>
18#include <boost/intrusive/detail/config_begin.hpp>
19#include <boost/intrusive/intrusive_fwd.hpp>
20#include <boost/intrusive/detail/common_slist_algorithms.hpp>
21#include <boost/intrusive/detail/uncast.hpp>
22#include <boost/intrusive/detail/algo_type.hpp>
23
24#if defined(BOOST_HAS_PRAGMA_ONCE)
25# pragma once
26#endif
27
28namespace boost {
29namespace intrusive {
30
31//! circular_slist_algorithms provides basic algorithms to manipulate nodes
32//! forming a circular singly linked list. An empty circular list is formed by a node
33//! whose pointer to the next node points to itself.
34//!
35//! circular_slist_algorithms is configured with a NodeTraits class, which encapsulates the
36//! information about the node to be manipulated. NodeTraits must support the
37//! following interface:
38//!
39//! <b>Typedefs</b>:
40//!
41//! <tt>node</tt>: The type of the node that forms the circular list
42//!
43//! <tt>node_ptr</tt>: A pointer to a node
44//!
45//! <tt>const_node_ptr</tt>: A pointer to a const node
46//!
47//! <b>Static functions</b>:
48//!
49//! <tt>static node_ptr get_next(const_node_ptr n);</tt>
50//!
51//! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
52template<class NodeTraits>
53class circular_slist_algorithms
54 /// @cond
55 : public detail::common_slist_algorithms<NodeTraits>
56 /// @endcond
57{
58 /// @cond
59 typedef detail::common_slist_algorithms<NodeTraits> base_t;
60 /// @endcond
61 public:
62 typedef typename NodeTraits::node node;
63 typedef typename NodeTraits::node_ptr node_ptr;
64 typedef typename NodeTraits::const_node_ptr const_node_ptr;
65 typedef NodeTraits node_traits;
66
67 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
68
69 //! <b>Effects</b>: Constructs an non-used list element, putting the next
70 //! pointer to null:
71 //! <tt>NodeTraits::get_next(this_node) == node_ptr()</tt>
72 //!
73 //! <b>Complexity</b>: Constant
74 //!
75 //! <b>Throws</b>: Nothing.
76 static void init(node_ptr this_node) BOOST_NOEXCEPT;
77
78 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
79 //!
80 //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:
81 //! or it's a not inserted node:
82 //! <tt>return node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt>
83 //!
84 //! <b>Complexity</b>: Constant
85 //!
86 //! <b>Throws</b>: Nothing.
87 static bool unique(const_node_ptr this_node) BOOST_NOEXCEPT;
88
89 //! <b>Effects</b>: Returns true is "this_node" has the same state as
90 //! if it was inited using "init(node_ptr)"
91 //!
92 //! <b>Complexity</b>: Constant
93 //!
94 //! <b>Throws</b>: Nothing.
95 static bool inited(const_node_ptr this_node) BOOST_NOEXCEPT;
96
97 //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list.
98 //!
99 //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list.
100 //!
101 //! <b>Complexity</b>: Constant
102 //!
103 //! <b>Throws</b>: Nothing.
104 static void unlink_after(node_ptr prev_node) BOOST_NOEXCEPT;
105
106 //! <b>Requires</b>: prev_node and last_node must be in a circular list
107 //! or be an empty circular list.
108 //!
109 //! <b>Effects</b>: Unlinks the range (prev_node, last_node) from the circular list.
110 //!
111 //! <b>Complexity</b>: Constant
112 //!
113 //! <b>Throws</b>: Nothing.
114 static void unlink_after(node_ptr prev_node, node_ptr last_node) BOOST_NOEXCEPT;
115
116 //! <b>Requires</b>: prev_node must be a node of a circular list.
117 //!
118 //! <b>Effects</b>: Links this_node after prev_node in the circular list.
119 //!
120 //! <b>Complexity</b>: Constant
121 //!
122 //! <b>Throws</b>: Nothing.
123 static void link_after(node_ptr prev_node, node_ptr this_node) BOOST_NOEXCEPT;
124
125 //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
126 //! and p must be a node of a different circular list.
127 //!
128 //! <b>Effects</b>: Removes the nodes from (b, e] range from their circular list and inserts
129 //! them after p in p's circular list.
130 //!
131 //! <b>Complexity</b>: Constant
132 //!
133 //! <b>Throws</b>: Nothing.
134 static void transfer_after(node_ptr p, node_ptr b, node_ptr e) BOOST_NOEXCEPT;
135
136 #else
137
138 using base_t::transfer_after;
139
140 #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
141
142 //! <b>Effects</b>: Constructs an empty list, making this_node the only
143 //! node of the circular list:
144 //! <tt>NodeTraits::get_next(this_node) == this_node</tt>.
145 //!
146 //! <b>Complexity</b>: Constant
147 //!
148 //! <b>Throws</b>: Nothing.
149 inline static void init_header(node_ptr this_node) BOOST_NOEXCEPT
150 { NodeTraits::set_next(this_node, this_node); }
151
152 //! <b>Requires</b>: 'p' is the first node of a list.
153 //!
154 //! <b>Effects</b>: Returns a pointer to a node that represents the "end" (one past end) node
155 //!
156 //! <b>Complexity</b>: Constant time.
157 //!
158 //! <b>Throws</b>: Nothing.
159 inline static node_ptr end_node(const_node_ptr p) BOOST_NOEXCEPT
160 { return detail::uncast(p); }
161
162 //! <b>Effects</b>: Returns true if this_node_points to an empty list.
163 //!
164 //! <b>Complexity</b>: Constant
165 //!
166 //! <b>Throws</b>: Nothing.
167 inline static bool is_empty(const_node_ptr this_node) BOOST_NOEXCEPT
168 { return NodeTraits::get_next(this_node) == this_node; }
169
170 //! <b>Effects</b>: Returns true if this_node points to a sentinel node.
171 //!
172 //! <b>Complexity</b>: Constant
173 //!
174 //! <b>Throws</b>: Nothing.
175 inline static bool is_sentinel(const_node_ptr this_node) BOOST_NOEXCEPT
176 { return NodeTraits::get_next(this_node) == node_ptr(); }
177
178 //! <b>Effects</b>: Marks this node as a "sentinel" node, a special state that is different from "empty",
179 //! that can be used to mark a special state of the list
180 //!
181 //! <b>Complexity</b>: Constant
182 //!
183 //! <b>Throws</b>: Nothing.
184 inline static void set_sentinel(node_ptr this_node) BOOST_NOEXCEPT
185 { NodeTraits::set_next(this_node, node_ptr()); }
186
187 //! <b>Requires</b>: this_node and prev_init_node must be in the same circular list.
188 //!
189 //! <b>Effects</b>: Returns the previous node of this_node in the circular list starting.
190 //! the search from prev_init_node. The first node checked for equality
191 //! is NodeTraits::get_next(prev_init_node).
192 //!
193 //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node.
194 //!
195 //! <b>Throws</b>: Nothing.
196 inline static node_ptr get_previous_node(node_ptr prev_init_node, node_ptr this_node) BOOST_NOEXCEPT
197 { return base_t::get_previous_node(prev_init_node, this_node); }
198
199 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
200 //!
201 //! <b>Effects</b>: Returns the previous node of this_node in the circular list.
202 //!
203 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
204 //!
205 //! <b>Throws</b>: Nothing.
206 inline static node_ptr get_previous_node(node_ptr this_node) BOOST_NOEXCEPT
207 { return base_t::get_previous_node(this_node, this_node); }
208
209 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
210 //!
211 //! <b>Effects</b>: Returns the previous node of the previous node of this_node in the circular list.
212 //!
213 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
214 //!
215 //! <b>Throws</b>: Nothing.
216 inline static node_ptr get_previous_previous_node(node_ptr this_node) BOOST_NOEXCEPT
217 { return get_previous_previous_node(this_node, this_node); }
218
219 //! <b>Requires</b>: this_node and p must be in the same circular list.
220 //!
221 //! <b>Effects</b>: Returns the previous node of the previous node of this_node in the
222 //! circular list starting. the search from p. The first node checked
223 //! for equality is NodeTraits::get_next((NodeTraits::get_next(p)).
224 //!
225 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
226 //!
227 //! <b>Throws</b>: Nothing.
228 static node_ptr get_previous_previous_node(node_ptr p, node_ptr this_node) BOOST_NOEXCEPT
229 {
230 node_ptr p_next = NodeTraits::get_next(p);
231 node_ptr p_next_next = NodeTraits::get_next(p_next);
232 while (this_node != p_next_next){
233 p = p_next;
234 p_next = p_next_next;
235 p_next_next = NodeTraits::get_next(p_next);
236 }
237 return p;
238 }
239
240 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
241 //!
242 //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list
243 //! is empty, returns 1.
244 //!
245 //! <b>Complexity</b>: Linear
246 //!
247 //! <b>Throws</b>: Nothing.
248 static std::size_t count(const_node_ptr this_node) BOOST_NOEXCEPT
249 {
250 std::size_t result = 0;
251 const_node_ptr p = this_node;
252 do{
253 p = NodeTraits::get_next(p);
254 ++result;
255 } while (p != this_node);
256 return result;
257 }
258
259 //! <b>Requires</b>: this_node must be in a circular list, be an empty circular list or be inited.
260 //!
261 //! <b>Effects</b>: Unlinks the node from the circular list.
262 //!
263 //! <b>Complexity</b>: Linear to the number of elements in the circular list
264 //!
265 //! <b>Throws</b>: Nothing.
266 static void unlink(node_ptr this_node) BOOST_NOEXCEPT
267 {
268 if(NodeTraits::get_next(this_node))
269 base_t::unlink_after(get_previous_node(this_node));
270 }
271
272 //! <b>Requires</b>: nxt_node must be a node of a circular list.
273 //!
274 //! <b>Effects</b>: Links this_node before nxt_node in the circular list.
275 //!
276 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
277 //!
278 //! <b>Throws</b>: Nothing.
279 inline static void link_before (node_ptr nxt_node, node_ptr this_node) BOOST_NOEXCEPT
280 { base_t::link_after(get_previous_node(nxt_node), this_node); }
281
282 //! <b>Requires</b>: this_node and other_node must be nodes inserted
283 //! in circular lists or be empty circular lists.
284 //!
285 //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in
286 //! other_nodes position in the second circular list and the other_node is inserted
287 //! in this_node's position in the first circular list.
288 //!
289 //! <b>Complexity</b>: Linear to number of elements of both lists
290 //!
291 //! <b>Throws</b>: Nothing.
292 static void swap_nodes(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT
293 {
294 if (other_node == this_node)
295 return;
296 const node_ptr this_next = NodeTraits::get_next(this_node);
297 const node_ptr other_next = NodeTraits::get_next(other_node);
298 const bool this_null = !this_next;
299 const bool other_null = !other_next;
300 const bool this_empty = this_next == this_node;
301 const bool other_empty = other_next == other_node;
302
303 if(!(other_null || other_empty)){
304 NodeTraits::set_next(this_next == other_node ? other_node : get_previous_node(other_node), this_node );
305 }
306 if(!(this_null | this_empty)){
307 NodeTraits::set_next(other_next == this_node ? this_node : get_previous_node(this_node), other_node );
308 }
309 NodeTraits::set_next(this_node, other_empty ? this_node : (other_next == this_node ? other_node : other_next) );
310 NodeTraits::set_next(other_node, this_empty ? other_node : (this_next == other_node ? this_node : this_next ) );
311 }
312
313 //! <b>Effects</b>: Reverses the order of elements in the list.
314 //!
315 //! <b>Throws</b>: Nothing.
316 //!
317 //! <b>Complexity</b>: This function is linear to the contained elements.
318 static void reverse(node_ptr p) BOOST_NOEXCEPT
319 {
320 node_ptr i = NodeTraits::get_next(p), e(p);
321 for (;;) {
322 node_ptr nxt(NodeTraits::get_next(i));
323 if (nxt == e)
324 break;
325 base_t::transfer_after(e, i, nxt);
326 }
327 }
328
329 //! <b>Effects</b>: Moves the node p n positions towards the end of the list.
330 //!
331 //! <b>Returns</b>: The previous node of p after the function if there has been any movement,
332 //! Null if n leads to no movement.
333 //!
334 //! <b>Throws</b>: Nothing.
335 //!
336 //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
337 static node_ptr move_backwards(node_ptr p, std::size_t n) BOOST_NOEXCEPT
338 {
339 //Null shift, nothing to do
340 if(!n) return node_ptr();
341 node_ptr first = NodeTraits::get_next(p);
342
343 //count() == 1 or 2, nothing to do
344 if(NodeTraits::get_next(first) == p)
345 return node_ptr();
346
347 bool end_found = false;
348 node_ptr new_last = node_ptr();
349
350 //Now find the new last node according to the shift count.
351 //If we find p before finding the new last node
352 //unlink p, shortcut the search now that we know the size of the list
353 //and continue.
354 for(std::size_t i = 1; i <= n; ++i){
355 new_last = first;
356 first = NodeTraits::get_next(first);
357 if(first == p){
358 //Shortcut the shift with the modulo of the size of the list
359 n %= i;
360 if(!n)
361 return node_ptr();
362 i = 0;
363 //Unlink p and continue the new first node search
364 first = NodeTraits::get_next(p);
365 base_t::unlink_after(new_last);
366 end_found = true;
367 }
368 }
369
370 //If the p has not been found in the previous loop, find it
371 //starting in the new first node and unlink it
372 if(!end_found){
373 base_t::unlink_after(base_t::get_previous_node(first, p));
374 }
375
376 //Now link p after the new last node
377 base_t::link_after(new_last, p);
378 return new_last;
379 }
380
381 //! <b>Effects</b>: Moves the node p n positions towards the beginning of the list.
382 //!
383 //! <b>Returns</b>: The previous node of p after the function if there has been any movement,
384 //! Null if n leads equals to no movement.
385 //!
386 //! <b>Throws</b>: Nothing.
387 //!
388 //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
389 static node_ptr move_forward(node_ptr p, std::size_t n) BOOST_NOEXCEPT
390 {
391 //Null shift, nothing to do
392 if(!n) return node_ptr();
393 node_ptr first = node_traits::get_next(p);
394
395 //count() == 1 or 2, nothing to do
396 if(node_traits::get_next(first) == p) return node_ptr();
397
398 //Iterate until p is found to know where the current last node is.
399 //If the shift count is less than the size of the list, we can also obtain
400 //the position of the new last node after the shift.
401 node_ptr old_last(first), next_to_it, new_last(p);
402 std::size_t distance = 1;
403 while(p != (next_to_it = node_traits::get_next(old_last))){
404 if(++distance > n)
405 new_last = node_traits::get_next(new_last);
406 old_last = next_to_it;
407 }
408 //If the shift was bigger or equal than the size, obtain the equivalent
409 //forward shifts and find the new last node.
410 if(distance <= n){
411 //Now find the equivalent forward shifts.
412 //Shortcut the shift with the modulo of the size of the list
413 std::size_t new_before_last_pos = (distance - (n % distance))% distance;
414 //If the shift is a multiple of the size there is nothing to do
415 if(!new_before_last_pos) return node_ptr();
416
417 for( new_last = p
418 ; new_before_last_pos--
419 ; new_last = node_traits::get_next(new_last)){
420 //empty
421 }
422 }
423
424 //Now unlink p and link it after the new last node
425 base_t::unlink_after(old_last);
426 base_t::link_after(new_last, p);
427 return new_last;
428 }
429
430 //! <b>Requires</b>: other must be a list and p must be a node of a different list.
431 //!
432 //! <b>Effects</b>: Transfers all nodes from other after p in p's list.
433 //!
434 //! <b>Complexity</b>: Linear
435 //!
436 //! <b>Throws</b>: Nothing.
437 static void transfer_after(node_ptr p, node_ptr other) BOOST_NOEXCEPT
438 {
439 node_ptr other_last((get_previous_node)(other));
440 base_t::transfer_after(p, other, other_last);
441 }
442
443 //! <b>Requires</b>: "disposer" must be an object function
444 //! taking a node_ptr parameter and shouldn't throw.
445 //!
446 //! <b>Effects</b>: Unlinks all nodes reachable from p (but not p) and calls
447 //! <tt>void disposer::operator()(node_ptr)</tt> for every node of the list
448 //! where p is linked.
449 //!
450 //! <b>Returns</b>: The number of disposed nodes
451 //!
452 //! <b>Complexity</b>: Linear to the number of element of the list.
453 //!
454 //! <b>Throws</b>: Nothing.
455 template<class Disposer>
456 inline static std::size_t detach_and_dispose(node_ptr p, Disposer disposer) BOOST_NOEXCEPT
457 { return base_t::unlink_after_and_dispose(p, p, disposer); }
458};
459
460/// @cond
461
462template<class NodeTraits>
463struct get_algo<CircularSListAlgorithms, NodeTraits>
464{
465 typedef circular_slist_algorithms<NodeTraits> type;
466};
467
468/// @endcond
469
470} //namespace intrusive
471} //namespace boost
472
473#include <boost/intrusive/detail/config_end.hpp>
474
475#endif //BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP
476

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