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/minimal_pair_header.hpp> //std::pair |
23 | |
24 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
25 | # pragma once |
26 | #endif |
27 | |
28 | namespace boost { |
29 | namespace 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> |
51 | template<class NodeTraits> |
52 | class 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 | |
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(const 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 if |
89 | //! 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(const 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 linear list. |
109 | //! |
110 | //! <b>Complexity</b>: Constant |
111 | //! |
112 | //! <b>Throws</b>: Nothing. |
113 | static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node); |
114 | |
115 | //! <b>Requires</b>: prev_node must be a node of a linear list. |
116 | //! |
117 | //! <b>Effects</b>: Links this_node after prev_node in the linear list. |
118 | //! |
119 | //! <b>Complexity</b>: Constant |
120 | //! |
121 | //! <b>Throws</b>: Nothing. |
122 | static void link_after(const node_ptr & prev_node, const node_ptr & this_node); |
123 | |
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. |
126 | //! |
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. |
129 | //! |
130 | //! <b>Complexity</b>: Constant |
131 | //! |
132 | //! <b>Throws</b>: Nothing. |
133 | static void transfer_after(const node_ptr & p, const node_ptr & b, const 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 (const node_ptr & this_node) |
145 | { NodeTraits::set_next(this_node, node_ptr ()); } |
146 | |
147 | //! <b>Requires</b>: this_node and prev_init_node must be in the same linear list. |
148 | //! |
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). |
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 linear list or be an empty linear list. |
160 | //! |
161 | //! <b>Effects</b>: Returns the number of nodes in a linear list. If the linear list |
162 | //! is empty, returns 1. |
163 | //! |
164 | //! <b>Complexity</b>: Linear |
165 | //! |
166 | //! <b>Throws</b>: Nothing. |
167 | static std::size_t count(const const_node_ptr & this_node) |
168 | { |
169 | std::size_t result = 0; |
170 | const_node_ptr p = this_node; |
171 | do{ |
172 | p = NodeTraits::get_next(p); |
173 | ++result; |
174 | } while (p); |
175 | return result; |
176 | } |
177 | |
178 | //! <b>Requires</b>: this_node and other_node must be nodes inserted |
179 | //! in linear lists or be empty linear lists. |
180 | //! |
181 | //! <b>Effects</b>: Moves all the nodes previously chained after this_node after other_node |
182 | //! and vice-versa. |
183 | //! |
184 | //! <b>Complexity</b>: Constant |
185 | //! |
186 | //! <b>Throws</b>: Nothing. |
187 | static void swap_trailing_nodes(const node_ptr & this_node, const node_ptr & other_node) |
188 | { |
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); |
193 | } |
194 | |
195 | //! <b>Effects</b>: Reverses the order of elements in the list. |
196 | //! |
197 | //! <b>Returns</b>: The new first node of the list. |
198 | //! |
199 | //! <b>Throws</b>: Nothing. |
200 | //! |
201 | //! <b>Complexity</b>: This function is linear to the contained elements. |
202 | static node_ptr reverse(const node_ptr & p) |
203 | { |
204 | if(!p) return node_ptr(); |
205 | node_ptr i = NodeTraits::get_next(p); |
206 | node_ptr first(p); |
207 | while(i){ |
208 | node_ptr nxti(NodeTraits::get_next(i)); |
209 | base_t::unlink_after(p); |
210 | NodeTraits::set_next(i, first); |
211 | first = i; |
212 | i = nxti; |
213 | } |
214 | return first; |
215 | } |
216 | |
217 | //! <b>Effects</b>: Moves the first n nodes starting at p to the end of the list. |
218 | //! |
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. |
221 | //! |
222 | //! <b>Throws</b>: Nothing. |
223 | //! |
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) |
226 | { |
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)){ |
230 | return ret; |
231 | } |
232 | |
233 | node_ptr first = p; |
234 | bool end_found = false; |
235 | node_ptr new_last = node_ptr(); |
236 | node_ptr old_last = node_ptr(); |
237 | |
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 |
241 | //and continue. |
242 | for(std::size_t i = 1; i <= n; ++i){ |
243 | new_last = first; |
244 | first = NodeTraits::get_next(first); |
245 | if(first == node_ptr()){ |
246 | //Shortcut the shift with the modulo of the size of the list |
247 | n %= i; |
248 | if(!n) return ret; |
249 | old_last = new_last; |
250 | i = 0; |
251 | //Unlink p and continue the new first node search |
252 | first = p; |
253 | //unlink_after(new_last); |
254 | end_found = true; |
255 | } |
256 | } |
257 | |
258 | //If the p has not been found in the previous loop, find it |
259 | //starting in the new first node and unlink it |
260 | if(!end_found){ |
261 | old_last = base_t::get_previous_node(first, node_ptr()); |
262 | } |
263 | |
264 | //Now link p after the new last node |
265 | NodeTraits::set_next(old_last, p); |
266 | NodeTraits::set_next(new_last, node_ptr()); |
267 | ret.first = first; |
268 | ret.second = new_last; |
269 | return ret; |
270 | } |
271 | |
272 | //! <b>Effects</b>: Moves the first n nodes starting at p to the beginning of the list. |
273 | //! |
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. |
276 | //! |
277 | //! <b>Throws</b>: Nothing. |
278 | //! |
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) |
281 | { |
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)) |
285 | return ret; |
286 | |
287 | node_ptr first = p; |
288 | |
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))){ |
295 | if(distance++ > n) |
296 | new_last = node_traits::get_next(new_last); |
297 | old_last = next_to_it; |
298 | } |
299 | //If the shift was bigger or equal than the size, obtain the equivalent |
300 | //forward shifts and find the new last node. |
301 | if(distance <= n){ |
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) |
307 | return ret; |
308 | |
309 | for( new_last = p |
310 | ; --new_before_last_pos |
311 | ; new_last = node_traits::get_next(new_last)){ |
312 | //empty |
313 | } |
314 | } |
315 | |
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; |
323 | return ret; |
324 | } |
325 | }; |
326 | |
327 | /// @cond |
328 | |
329 | template<class NodeTraits> |
330 | struct get_algo<LinearSListAlgorithms, NodeTraits> |
331 | { |
332 | typedef linear_slist_algorithms<NodeTraits> type; |
333 | }; |
334 | |
335 | /// @endcond |
336 | |
337 | } //namespace intrusive |
338 | } //namespace boost |
339 | |
340 | #include <boost/intrusive/detail/config_end.hpp> |
341 | |
342 | #endif //BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP |
343 | |