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/algo_type.hpp>
22
23#if defined(BOOST_HAS_PRAGMA_ONCE)
24# pragma once
25#endif
26
27namespace boost {
28namespace intrusive {
29
30//! circular_slist_algorithms provides basic algorithms to manipulate nodes
31//! forming a circular singly linked list. An empty circular list is formed by a node
32//! whose pointer to the next node points to itself.
33//!
34//! circular_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 circular 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 circular_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(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
89 //! if 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(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 circular list.
109 //!
110 //! <b>Complexity</b>: Constant
111 //!
112 //! <b>Throws</b>: Nothing.
113 static void unlink_after(node_ptr prev_node, node_ptr last_node);
114
115 //! <b>Requires</b>: prev_node must be a node of a circular list.
116 //!
117 //! <b>Effects</b>: Links this_node after prev_node in the circular list.
118 //!
119 //! <b>Complexity</b>: Constant
120 //!
121 //! <b>Throws</b>: Nothing.
122 static void link_after(node_ptr prev_node, node_ptr this_node);
123
124 //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
125 //! and p must be a node of a different circular list.
126 //!
127 //! <b>Effects</b>: Removes the nodes from (b, e] range from their circular list and inserts
128 //! them after p in p's circular list.
129 //!
130 //! <b>Complexity</b>: Constant
131 //!
132 //! <b>Throws</b>: Nothing.
133 static void transfer_after(node_ptr p, node_ptr b, 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, this_node); }
146
147 //! <b>Requires</b>: this_node and prev_init_node must be in the same circular list.
148 //!
149 //! <b>Effects</b>: Returns the previous node of this_node in the circular 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 circular list or be an empty circular list.
160 //!
161 //! <b>Effects</b>: Returns the previous node of this_node in the circular list.
162 //!
163 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
164 //!
165 //! <b>Throws</b>: Nothing.
166 static node_ptr get_previous_node(const node_ptr & this_node)
167 { return base_t::get_previous_node(this_node, this_node); }
168
169 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
170 //!
171 //! <b>Effects</b>: Returns the previous node of the previous node of this_node in the circular list.
172 //!
173 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
174 //!
175 //! <b>Throws</b>: Nothing.
176 static node_ptr get_previous_previous_node(const node_ptr & this_node)
177 { return get_previous_previous_node(this_node, this_node); }
178
179 //! <b>Requires</b>: this_node and p must be in the same circular list.
180 //!
181 //! <b>Effects</b>: Returns the previous node of the previous node of this_node in the
182 //! circular list starting. the search from p. The first node checked
183 //! for equality is NodeTraits::get_next((NodeTraits::get_next(p)).
184 //!
185 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
186 //!
187 //! <b>Throws</b>: Nothing.
188 static node_ptr get_previous_previous_node(node_ptr p, const node_ptr & this_node)
189 {
190 node_ptr p_next = NodeTraits::get_next(p);
191 node_ptr p_next_next = NodeTraits::get_next(p_next);
192 while (this_node != p_next_next){
193 p = p_next;
194 p_next = p_next_next;
195 p_next_next = NodeTraits::get_next(p_next);
196 }
197 return p;
198 }
199
200 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
201 //!
202 //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list
203 //! is empty, returns 1.
204 //!
205 //! <b>Complexity</b>: Linear
206 //!
207 //! <b>Throws</b>: Nothing.
208 static std::size_t count(const const_node_ptr & this_node)
209 {
210 std::size_t result = 0;
211 const_node_ptr p = this_node;
212 do{
213 p = NodeTraits::get_next(p);
214 ++result;
215 } while (p != this_node);
216 return result;
217 }
218
219 //! <b>Requires</b>: this_node must be in a circular list, be an empty circular list or be inited.
220 //!
221 //! <b>Effects</b>: Unlinks the node from the circular list.
222 //!
223 //! <b>Complexity</b>: Linear to the number of elements in the circular list
224 //!
225 //! <b>Throws</b>: Nothing.
226 static void unlink(const node_ptr & this_node)
227 {
228 if(NodeTraits::get_next(this_node))
229 base_t::unlink_after(get_previous_node(this_node));
230 }
231
232 //! <b>Requires</b>: nxt_node must be a node of a circular list.
233 //!
234 //! <b>Effects</b>: Links this_node before nxt_node in the circular list.
235 //!
236 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
237 //!
238 //! <b>Throws</b>: Nothing.
239 static void link_before (const node_ptr & nxt_node, const node_ptr & this_node)
240 { base_t::link_after(get_previous_node(nxt_node), this_node); }
241
242 //! <b>Requires</b>: this_node and other_node must be nodes inserted
243 //! in circular lists or be empty circular lists.
244 //!
245 //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in
246 //! other_nodes position in the second circular list and the other_node is inserted
247 //! in this_node's position in the first circular list.
248 //!
249 //! <b>Complexity</b>: Linear to number of elements of both lists
250 //!
251 //! <b>Throws</b>: Nothing.
252 static void swap_nodes(const node_ptr & this_node, const node_ptr & other_node)
253 {
254 if (other_node == this_node)
255 return;
256 const node_ptr this_next = NodeTraits::get_next(this_node);
257 const node_ptr other_next = NodeTraits::get_next(other_node);
258 const bool this_null = !this_next;
259 const bool other_null = !other_next;
260 const bool this_empty = this_next == this_node;
261 const bool other_empty = other_next == other_node;
262
263 if(!(other_null || other_empty)){
264 NodeTraits::set_next(this_next == other_node ? other_node : get_previous_node(other_node), this_node );
265 }
266 if(!(this_null | this_empty)){
267 NodeTraits::set_next(other_next == this_node ? this_node : get_previous_node(this_node), other_node );
268 }
269 NodeTraits::set_next(this_node, other_empty ? this_node : (other_next == this_node ? other_node : other_next) );
270 NodeTraits::set_next(other_node, this_empty ? other_node : (this_next == other_node ? this_node : this_next ) );
271 }
272
273 //! <b>Effects</b>: Reverses the order of elements in the list.
274 //!
275 //! <b>Throws</b>: Nothing.
276 //!
277 //! <b>Complexity</b>: This function is linear to the contained elements.
278 static void reverse(const node_ptr & p)
279 {
280 node_ptr i = NodeTraits::get_next(p), e(p);
281 for (;;) {
282 node_ptr nxt(NodeTraits::get_next(i));
283 if (nxt == e)
284 break;
285 base_t::transfer_after(e, i, nxt);
286 }
287 }
288
289 //! <b>Effects</b>: Moves the node p n positions towards the end of the list.
290 //!
291 //! <b>Returns</b>: The previous node of p after the function if there has been any movement,
292 //! Null if n leads to no movement.
293 //!
294 //! <b>Throws</b>: Nothing.
295 //!
296 //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
297 static node_ptr move_backwards(const node_ptr & p, std::size_t n)
298 {
299 //Null shift, nothing to do
300 if(!n) return node_ptr();
301 node_ptr first = NodeTraits::get_next(p);
302
303 //count() == 1 or 2, nothing to do
304 if(NodeTraits::get_next(first) == p)
305 return node_ptr();
306
307 bool end_found = false;
308 node_ptr new_last = node_ptr();
309
310 //Now find the new last node according to the shift count.
311 //If we find p before finding the new last node
312 //unlink p, shortcut the search now that we know the size of the list
313 //and continue.
314 for(std::size_t i = 1; i <= n; ++i){
315 new_last = first;
316 first = NodeTraits::get_next(first);
317 if(first == p){
318 //Shortcut the shift with the modulo of the size of the list
319 n %= i;
320 if(!n)
321 return node_ptr();
322 i = 0;
323 //Unlink p and continue the new first node search
324 first = NodeTraits::get_next(p);
325 base_t::unlink_after(new_last);
326 end_found = true;
327 }
328 }
329
330 //If the p has not been found in the previous loop, find it
331 //starting in the new first node and unlink it
332 if(!end_found){
333 base_t::unlink_after(base_t::get_previous_node(first, p));
334 }
335
336 //Now link p after the new last node
337 base_t::link_after(new_last, p);
338 return new_last;
339 }
340
341 //! <b>Effects</b>: Moves the node p n positions towards the beginning of the list.
342 //!
343 //! <b>Returns</b>: The previous node of p after the function if there has been any movement,
344 //! Null if n leads equals to no movement.
345 //!
346 //! <b>Throws</b>: Nothing.
347 //!
348 //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions.
349 static node_ptr move_forward(const node_ptr & p, std::size_t n)
350 {
351 //Null shift, nothing to do
352 if(!n) return node_ptr();
353 node_ptr first = node_traits::get_next(p);
354
355 //count() == 1 or 2, nothing to do
356 if(node_traits::get_next(first) == p) return node_ptr();
357
358 //Iterate until p is found to know where the current last node is.
359 //If the shift count is less than the size of the list, we can also obtain
360 //the position of the new last node after the shift.
361 node_ptr old_last(first), next_to_it, new_last(p);
362 std::size_t distance = 1;
363 while(p != (next_to_it = node_traits::get_next(old_last))){
364 if(++distance > n)
365 new_last = node_traits::get_next(new_last);
366 old_last = next_to_it;
367 }
368 //If the shift was bigger or equal than the size, obtain the equivalent
369 //forward shifts and find the new last node.
370 if(distance <= n){
371 //Now find the equivalent forward shifts.
372 //Shortcut the shift with the modulo of the size of the list
373 std::size_t new_before_last_pos = (distance - (n % distance))% distance;
374 //If the shift is a multiple of the size there is nothing to do
375 if(!new_before_last_pos) return node_ptr();
376
377 for( new_last = p
378 ; new_before_last_pos--
379 ; new_last = node_traits::get_next(new_last)){
380 //empty
381 }
382 }
383
384 //Now unlink p and link it after the new last node
385 base_t::unlink_after(old_last);
386 base_t::link_after(new_last, p);
387 return new_last;
388 }
389};
390
391/// @cond
392
393template<class NodeTraits>
394struct get_algo<CircularSListAlgorithms, NodeTraits>
395{
396 typedef circular_slist_algorithms<NodeTraits> type;
397};
398
399/// @endcond
400
401} //namespace intrusive
402} //namespace boost
403
404#include <boost/intrusive/detail/config_end.hpp>
405
406#endif //BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP
407

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