1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Olaf Krzikalla 2004-2006.
4 // (C) Copyright Ion Gaztanaga 2006-2014
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)
10 // See http://www.boost.org/libs/intrusive for documentation.
12 /////////////////////////////////////////////////////////////////////////////
14 #ifndef BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP
15 #define BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP
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>
23 #if defined(BOOST_HAS_PRAGMA_ONCE)
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.
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:
40 //! <tt>node</tt>: The type of the node that forms the circular list
42 //! <tt>node_ptr</tt>: A pointer to a node
44 //! <tt>const_node_ptr</tt>: A pointer to a const node
46 //! <b>Static functions</b>:
48 //! <tt>static node_ptr get_next(const_node_ptr n);</tt>
50 //! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
51 template<class NodeTraits>
52 class circular_slist_algorithms
54 : public detail::common_slist_algorithms<NodeTraits>
58 typedef detail::common_slist_algorithms<NodeTraits> base_t;
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;
66 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
68 //! <b>Effects</b>: Constructs an non-used list element, putting the next
70 //! <tt>NodeTraits::get_next(this_node) == node_ptr()</tt>
72 //! <b>Complexity</b>: Constant
74 //! <b>Throws</b>: Nothing.
75 static void init(node_ptr this_node);
77 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
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>
83 //! <b>Complexity</b>: Constant
85 //! <b>Throws</b>: Nothing.
86 static bool unique(const_node_ptr this_node);
88 //! <b>Effects</b>: Returns true is "this_node" has the same state as
89 //! if it was inited using "init(node_ptr)"
91 //! <b>Complexity</b>: Constant
93 //! <b>Throws</b>: Nothing.
94 static bool inited(const_node_ptr this_node);
96 //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list.
98 //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list.
100 //! <b>Complexity</b>: Constant
102 //! <b>Throws</b>: Nothing.
103 static void unlink_after(node_ptr prev_node);
105 //! <b>Requires</b>: prev_node and last_node must be in a circular list
106 //! or be an empty circular list.
108 //! <b>Effects</b>: Unlinks the range (prev_node, last_node) from the circular list.
110 //! <b>Complexity</b>: Constant
112 //! <b>Throws</b>: Nothing.
113 static void unlink_after(node_ptr prev_node, node_ptr last_node);
115 //! <b>Requires</b>: prev_node must be a node of a circular list.
117 //! <b>Effects</b>: Links this_node after prev_node in the circular list.
119 //! <b>Complexity</b>: Constant
121 //! <b>Throws</b>: Nothing.
122 static void link_after(node_ptr prev_node, node_ptr this_node);
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.
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.
130 //! <b>Complexity</b>: Constant
132 //! <b>Throws</b>: Nothing.
133 static void transfer_after(node_ptr p, node_ptr b, node_ptr e);
135 #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
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>.
141 //! <b>Complexity</b>: Constant
143 //! <b>Throws</b>: Nothing.
144 BOOST_INTRUSIVE_FORCEINLINE static void init_header(const node_ptr &this_node)
145 { NodeTraits::set_next(this_node, this_node); }
147 //! <b>Requires</b>: this_node and prev_init_node must be in the same circular list.
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).
153 //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node.
155 //! <b>Throws</b>: Nothing.
156 BOOST_INTRUSIVE_FORCEINLINE 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); }
159 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
161 //! <b>Effects</b>: Returns the previous node of this_node in the circular list.
163 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
165 //! <b>Throws</b>: Nothing.
166 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous_node(const node_ptr & this_node)
167 { return base_t::get_previous_node(this_node, this_node); }
169 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
171 //! <b>Effects</b>: Returns the previous node of the previous node of this_node in the circular list.
173 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
175 //! <b>Throws</b>: Nothing.
176 BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_previous_previous_node(const node_ptr & this_node)
177 { return get_previous_previous_node(this_node, this_node); }
179 //! <b>Requires</b>: this_node and p must be in the same circular list.
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)).
185 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
187 //! <b>Throws</b>: Nothing.
188 static node_ptr get_previous_previous_node(node_ptr p, const node_ptr & this_node)
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){
194 p_next = p_next_next;
195 p_next_next = NodeTraits::get_next(p_next);
200 //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
202 //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list
203 //! is empty, returns 1.
205 //! <b>Complexity</b>: Linear
207 //! <b>Throws</b>: Nothing.
208 static std::size_t count(const const_node_ptr & this_node)
210 std::size_t result = 0;
211 const_node_ptr p = this_node;
213 p = NodeTraits::get_next(p);
215 } while (p != this_node);
219 //! <b>Requires</b>: this_node must be in a circular list, be an empty circular list or be inited.
221 //! <b>Effects</b>: Unlinks the node from the circular list.
223 //! <b>Complexity</b>: Linear to the number of elements in the circular list
225 //! <b>Throws</b>: Nothing.
226 BOOST_INTRUSIVE_FORCEINLINE static void unlink(const node_ptr & this_node)
228 if(NodeTraits::get_next(this_node))
229 base_t::unlink_after(get_previous_node(this_node));
232 //! <b>Requires</b>: nxt_node must be a node of a circular list.
234 //! <b>Effects</b>: Links this_node before nxt_node in the circular list.
236 //! <b>Complexity</b>: Linear to the number of elements in the circular list.
238 //! <b>Throws</b>: Nothing.
239 BOOST_INTRUSIVE_FORCEINLINE 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); }
242 //! <b>Requires</b>: this_node and other_node must be nodes inserted
243 //! in circular lists or be empty circular lists.
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.
249 //! <b>Complexity</b>: Linear to number of elements of both lists
251 //! <b>Throws</b>: Nothing.
252 static void swap_nodes(const node_ptr & this_node, const node_ptr & other_node)
254 if (other_node == this_node)
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;
263 if(!(other_null || other_empty)){
264 NodeTraits::set_next(this_next == other_node ? other_node : get_previous_node(other_node), this_node );
266 if(!(this_null | this_empty)){
267 NodeTraits::set_next(other_next == this_node ? this_node : get_previous_node(this_node), other_node );
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 ) );
273 //! <b>Effects</b>: Reverses the order of elements in the list.
275 //! <b>Throws</b>: Nothing.
277 //! <b>Complexity</b>: This function is linear to the contained elements.
278 static void reverse(const node_ptr & p)
280 node_ptr i = NodeTraits::get_next(p), e(p);
282 node_ptr nxt(NodeTraits::get_next(i));
285 base_t::transfer_after(e, i, nxt);
289 //! <b>Effects</b>: Moves the node p n positions towards the end of the list.
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.
294 //! <b>Throws</b>: Nothing.
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)
299 //Null shift, nothing to do
300 if(!n) return node_ptr();
301 node_ptr first = NodeTraits::get_next(p);
303 //count() == 1 or 2, nothing to do
304 if(NodeTraits::get_next(first) == p)
307 bool end_found = false;
308 node_ptr new_last = node_ptr();
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
314 for(std::size_t i = 1; i <= n; ++i){
316 first = NodeTraits::get_next(first);
318 //Shortcut the shift with the modulo of the size of the list
323 //Unlink p and continue the new first node search
324 first = NodeTraits::get_next(p);
325 base_t::unlink_after(new_last);
330 //If the p has not been found in the previous loop, find it
331 //starting in the new first node and unlink it
333 base_t::unlink_after(base_t::get_previous_node(first, p));
336 //Now link p after the new last node
337 base_t::link_after(new_last, p);
341 //! <b>Effects</b>: Moves the node p n positions towards the beginning of the list.
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.
346 //! <b>Throws</b>: Nothing.
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)
351 //Null shift, nothing to do
352 if(!n) return node_ptr();
353 node_ptr first = node_traits::get_next(p);
355 //count() == 1 or 2, nothing to do
356 if(node_traits::get_next(first) == p) return node_ptr();
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))){
365 new_last = node_traits::get_next(new_last);
366 old_last = next_to_it;
368 //If the shift was bigger or equal than the size, obtain the equivalent
369 //forward shifts and find the new last node.
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();
378 ; new_before_last_pos--
379 ; new_last = node_traits::get_next(new_last)){
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);
393 template<class NodeTraits>
394 struct get_algo<CircularSListAlgorithms, NodeTraits>
396 typedef circular_slist_algorithms<NodeTraits> type;
401 } //namespace intrusive
404 #include <boost/intrusive/detail/config_end.hpp>
406 #endif //BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP