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_LINEAR_SLIST_ALGORITHMS_HPP
15 #define BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP
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>
22 #include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair
24 #if defined(BOOST_HAS_PRAGMA_ONCE)
31 //! linear_slist_algorithms provides basic algorithms to manipulate nodes
32 //! forming a linear singly linked list.
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:
40 //! <tt>node</tt>: The type of the node that forms the linear 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 linear_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(const 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 if
89 //! 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(const 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 linear list.
110 //! <b>Complexity</b>: Constant
112 //! <b>Throws</b>: Nothing.
113 static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node);
115 //! <b>Requires</b>: prev_node must be a node of a linear list.
117 //! <b>Effects</b>: Links this_node after prev_node in the linear list.
119 //! <b>Complexity</b>: Constant
121 //! <b>Throws</b>: Nothing.
122 static void link_after(const node_ptr & prev_node, const node_ptr & this_node);
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.
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.
130 //! <b>Complexity</b>: Constant
132 //! <b>Throws</b>: Nothing.
133 static void transfer_after(const node_ptr & p, const node_ptr & b, const 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, node_ptr ()); }
147 //! <b>Requires</b>: this_node and prev_init_node must be in the same linear list.
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).
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 linear list or be an empty linear list.
161 //! <b>Effects</b>: Returns the number of nodes in a linear list. If the linear list
162 //! is empty, returns 1.
164 //! <b>Complexity</b>: Linear
166 //! <b>Throws</b>: Nothing.
167 static std::size_t count(const const_node_ptr & this_node)
169 std::size_t result = 0;
170 const_node_ptr p = this_node;
172 p = NodeTraits::get_next(p);
178 //! <b>Requires</b>: this_node and other_node must be nodes inserted
179 //! in linear lists or be empty linear lists.
181 //! <b>Effects</b>: Moves all the nodes previously chained after this_node after other_node
184 //! <b>Complexity</b>: Constant
186 //! <b>Throws</b>: Nothing.
187 static void swap_trailing_nodes(const node_ptr & this_node, const node_ptr & other_node)
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);
195 //! <b>Effects</b>: Reverses the order of elements in the list.
197 //! <b>Returns</b>: The new first node of the list.
199 //! <b>Throws</b>: Nothing.
201 //! <b>Complexity</b>: This function is linear to the contained elements.
202 static node_ptr reverse(const node_ptr & p)
204 if(!p) return node_ptr();
205 node_ptr i = NodeTraits::get_next(p);
208 node_ptr nxti(NodeTraits::get_next(i));
209 base_t::unlink_after(p);
210 NodeTraits::set_next(i, first);
217 //! <b>Effects</b>: Moves the first n nodes starting at p to the end of the list.
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.
222 //! <b>Throws</b>: Nothing.
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)
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)){
234 bool end_found = false;
235 node_ptr new_last = node_ptr();
236 node_ptr old_last = node_ptr();
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
242 for(std::size_t i = 1; i <= n; ++i){
244 first = NodeTraits::get_next(first);
245 if(first == node_ptr()){
246 //Shortcut the shift with the modulo of the size of the list
251 //Unlink p and continue the new first node search
253 //unlink_after(new_last);
258 //If the p has not been found in the previous loop, find it
259 //starting in the new first node and unlink it
261 old_last = base_t::get_previous_node(first, node_ptr());
264 //Now link p after the new last node
265 NodeTraits::set_next(old_last, p);
266 NodeTraits::set_next(new_last, node_ptr());
268 ret.second = new_last;
272 //! <b>Effects</b>: Moves the first n nodes starting at p to the beginning of the list.
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.
277 //! <b>Throws</b>: Nothing.
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)
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))
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))){
296 new_last = node_traits::get_next(new_last);
297 old_last = next_to_it;
299 //If the shift was bigger or equal than the size, obtain the equivalent
300 //forward shifts and find the new last node.
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)
310 ; --new_before_last_pos
311 ; new_last = node_traits::get_next(new_last)){
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;
329 template<class NodeTraits>
330 struct get_algo<LinearSListAlgorithms, NodeTraits>
332 typedef linear_slist_algorithms<NodeTraits> type;
337 } //namespace intrusive
340 #include <boost/intrusive/detail/config_end.hpp>
342 #endif //BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP