]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
1e59de90 | 22 | #include <boost/intrusive/detail/twin.hpp> //for node_pair |
7c673cae FG |
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; | |
1e59de90 TL |
65 | //A simple struct containing: |
66 | // | |
67 | // typedef node_ptr type; | |
68 | // node_ptr first; | |
69 | // node_ptr second; | |
70 | typedef twin<node_ptr> node_pair; | |
7c673cae FG |
71 | |
72 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
73 | ||
74 | //! <b>Effects</b>: Constructs an non-used list element, putting the next | |
75 | //! pointer to null: | |
76 | //! <tt>NodeTraits::get_next(this_node) == node_ptr()</tt> | |
77 | //! | |
78 | //! <b>Complexity</b>: Constant | |
79 | //! | |
80 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 81 | static void init(node_ptr this_node) BOOST_NOEXCEPT; |
7c673cae FG |
82 | |
83 | //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. | |
84 | //! | |
85 | //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list: | |
86 | //! or it's a not inserted node: | |
87 | //! <tt>return node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt> | |
88 | //! | |
89 | //! <b>Complexity</b>: Constant | |
90 | //! | |
91 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 92 | static bool unique(const_node_ptr this_node) BOOST_NOEXCEPT; |
7c673cae FG |
93 | |
94 | //! <b>Effects</b>: Returns true is "this_node" has the same state as if | |
95 | //! it was inited using "init(node_ptr)" | |
96 | //! | |
97 | //! <b>Complexity</b>: Constant | |
98 | //! | |
99 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 100 | static bool inited(const_node_ptr this_node) BOOST_NOEXCEPT; |
7c673cae FG |
101 | |
102 | //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list. | |
103 | //! | |
104 | //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list. | |
105 | //! | |
106 | //! <b>Complexity</b>: Constant | |
107 | //! | |
108 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 109 | static void unlink_after(node_ptr prev_node) BOOST_NOEXCEPT; |
7c673cae FG |
110 | |
111 | //! <b>Requires</b>: prev_node and last_node must be in a circular list | |
112 | //! or be an empty circular list. | |
113 | //! | |
114 | //! <b>Effects</b>: Unlinks the range (prev_node, last_node) from the linear list. | |
115 | //! | |
116 | //! <b>Complexity</b>: Constant | |
117 | //! | |
118 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 119 | static void unlink_after(node_ptr prev_node, node_ptr last_node) BOOST_NOEXCEPT; |
7c673cae FG |
120 | |
121 | //! <b>Requires</b>: prev_node must be a node of a linear list. | |
122 | //! | |
123 | //! <b>Effects</b>: Links this_node after prev_node in the linear list. | |
124 | //! | |
125 | //! <b>Complexity</b>: Constant | |
126 | //! | |
127 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 128 | static void link_after(node_ptr prev_node, node_ptr this_node) BOOST_NOEXCEPT; |
7c673cae FG |
129 | |
130 | //! <b>Requires</b>: b and e must be nodes of the same linear list or an empty range. | |
131 | //! and p must be a node of a different linear list. | |
132 | //! | |
133 | //! <b>Effects</b>: Removes the nodes from (b, e] range from their linear list and inserts | |
134 | //! them after p in p's linear list. | |
135 | //! | |
136 | //! <b>Complexity</b>: Constant | |
137 | //! | |
138 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 139 | static void transfer_after(node_ptr p, node_ptr b, node_ptr e) BOOST_NOEXCEPT; |
7c673cae FG |
140 | |
141 | #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
142 | ||
143 | //! <b>Effects</b>: Constructs an empty list, making this_node the only | |
144 | //! node of the circular list: | |
145 | //! <tt>NodeTraits::get_next(this_node) == this_node</tt>. | |
146 | //! | |
147 | //! <b>Complexity</b>: Constant | |
148 | //! | |
149 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 150 | BOOST_INTRUSIVE_FORCEINLINE static void init_header(node_ptr this_node) BOOST_NOEXCEPT |
7c673cae FG |
151 | { NodeTraits::set_next(this_node, node_ptr ()); } |
152 | ||
153 | //! <b>Requires</b>: this_node and prev_init_node must be in the same linear list. | |
154 | //! | |
155 | //! <b>Effects</b>: Returns the previous node of this_node in the linear list starting. | |
156 | //! the search from prev_init_node. The first node checked for equality | |
157 | //! is NodeTraits::get_next(prev_init_node). | |
158 | //! | |
159 | //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node. | |
160 | //! | |
161 | //! <b>Throws</b>: Nothing. | |
1e59de90 TL |
162 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr |
163 | get_previous_node(node_ptr prev_init_node, node_ptr this_node) BOOST_NOEXCEPT | |
7c673cae FG |
164 | { return base_t::get_previous_node(prev_init_node, this_node); } |
165 | ||
166 | //! <b>Requires</b>: this_node must be in a linear list or be an empty linear list. | |
167 | //! | |
168 | //! <b>Effects</b>: Returns the number of nodes in a linear list. If the linear list | |
169 | //! is empty, returns 1. | |
170 | //! | |
171 | //! <b>Complexity</b>: Linear | |
172 | //! | |
173 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 174 | static std::size_t count(const_node_ptr this_node) BOOST_NOEXCEPT |
7c673cae FG |
175 | { |
176 | std::size_t result = 0; | |
177 | const_node_ptr p = this_node; | |
178 | do{ | |
179 | p = NodeTraits::get_next(p); | |
180 | ++result; | |
181 | } while (p); | |
182 | return result; | |
183 | } | |
184 | ||
185 | //! <b>Requires</b>: this_node and other_node must be nodes inserted | |
186 | //! in linear lists or be empty linear lists. | |
187 | //! | |
188 | //! <b>Effects</b>: Moves all the nodes previously chained after this_node after other_node | |
189 | //! and vice-versa. | |
190 | //! | |
191 | //! <b>Complexity</b>: Constant | |
192 | //! | |
193 | //! <b>Throws</b>: Nothing. | |
1e59de90 | 194 | BOOST_INTRUSIVE_FORCEINLINE static void swap_trailing_nodes(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT |
7c673cae FG |
195 | { |
196 | node_ptr this_nxt = NodeTraits::get_next(this_node); | |
197 | node_ptr other_nxt = NodeTraits::get_next(other_node); | |
198 | NodeTraits::set_next(this_node, other_nxt); | |
199 | NodeTraits::set_next(other_node, this_nxt); | |
200 | } | |
201 | ||
202 | //! <b>Effects</b>: Reverses the order of elements in the list. | |
203 | //! | |
204 | //! <b>Returns</b>: The new first node of the list. | |
205 | //! | |
206 | //! <b>Throws</b>: Nothing. | |
207 | //! | |
208 | //! <b>Complexity</b>: This function is linear to the contained elements. | |
1e59de90 | 209 | static node_ptr reverse(node_ptr p) BOOST_NOEXCEPT |
7c673cae FG |
210 | { |
211 | if(!p) return node_ptr(); | |
212 | node_ptr i = NodeTraits::get_next(p); | |
213 | node_ptr first(p); | |
214 | while(i){ | |
215 | node_ptr nxti(NodeTraits::get_next(i)); | |
216 | base_t::unlink_after(p); | |
217 | NodeTraits::set_next(i, first); | |
218 | first = i; | |
219 | i = nxti; | |
220 | } | |
221 | return first; | |
222 | } | |
223 | ||
224 | //! <b>Effects</b>: Moves the first n nodes starting at p to the end of the list. | |
225 | //! | |
226 | //! <b>Returns</b>: A pair containing the new first and last node of the list or | |
227 | //! if there has been any movement, a null pair if n leads to no movement. | |
228 | //! | |
229 | //! <b>Throws</b>: Nothing. | |
230 | //! | |
231 | //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions. | |
1e59de90 | 232 | static node_pair move_first_n_backwards(node_ptr p, std::size_t n) BOOST_NOEXCEPT |
7c673cae | 233 | { |
1e59de90 | 234 | node_pair ret; |
7c673cae FG |
235 | //Null shift, or count() == 0 or 1, nothing to do |
236 | if(!n || !p || !NodeTraits::get_next(p)){ | |
237 | return ret; | |
238 | } | |
239 | ||
240 | node_ptr first = p; | |
241 | bool end_found = false; | |
242 | node_ptr new_last = node_ptr(); | |
243 | node_ptr old_last = node_ptr(); | |
244 | ||
245 | //Now find the new last node according to the shift count. | |
246 | //If we find 0 before finding the new last node | |
247 | //unlink p, shortcut the search now that we know the size of the list | |
248 | //and continue. | |
249 | for(std::size_t i = 1; i <= n; ++i){ | |
250 | new_last = first; | |
251 | first = NodeTraits::get_next(first); | |
252 | if(first == node_ptr()){ | |
253 | //Shortcut the shift with the modulo of the size of the list | |
254 | n %= i; | |
255 | if(!n) return ret; | |
256 | old_last = new_last; | |
257 | i = 0; | |
258 | //Unlink p and continue the new first node search | |
259 | first = p; | |
260 | //unlink_after(new_last); | |
261 | end_found = true; | |
262 | } | |
263 | } | |
264 | ||
265 | //If the p has not been found in the previous loop, find it | |
266 | //starting in the new first node and unlink it | |
267 | if(!end_found){ | |
268 | old_last = base_t::get_previous_node(first, node_ptr()); | |
269 | } | |
270 | ||
271 | //Now link p after the new last node | |
272 | NodeTraits::set_next(old_last, p); | |
273 | NodeTraits::set_next(new_last, node_ptr()); | |
274 | ret.first = first; | |
275 | ret.second = new_last; | |
276 | return ret; | |
277 | } | |
278 | ||
279 | //! <b>Effects</b>: Moves the first n nodes starting at p to the beginning of the list. | |
280 | //! | |
281 | //! <b>Returns</b>: A pair containing the new first and last node of the list or | |
282 | //! if there has been any movement, a null pair if n leads to no movement. | |
283 | //! | |
284 | //! <b>Throws</b>: Nothing. | |
285 | //! | |
286 | //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions. | |
1e59de90 | 287 | static node_pair move_first_n_forward(node_ptr p, std::size_t n) BOOST_NOEXCEPT |
7c673cae | 288 | { |
1e59de90 | 289 | node_pair ret; |
7c673cae FG |
290 | //Null shift, or count() == 0 or 1, nothing to do |
291 | if(!n || !p || !NodeTraits::get_next(p)) | |
292 | return ret; | |
293 | ||
294 | node_ptr first = p; | |
295 | ||
296 | //Iterate until p is found to know where the current last node is. | |
297 | //If the shift count is less than the size of the list, we can also obtain | |
298 | //the position of the new last node after the shift. | |
299 | node_ptr old_last(first), next_to_it, new_last(p); | |
300 | std::size_t distance = 1; | |
301 | while(!!(next_to_it = node_traits::get_next(old_last))){ | |
302 | if(distance++ > n) | |
303 | new_last = node_traits::get_next(new_last); | |
304 | old_last = next_to_it; | |
305 | } | |
306 | //If the shift was bigger or equal than the size, obtain the equivalent | |
307 | //forward shifts and find the new last node. | |
308 | if(distance <= n){ | |
309 | //Now find the equivalent forward shifts. | |
310 | //Shortcut the shift with the modulo of the size of the list | |
311 | std::size_t new_before_last_pos = (distance - (n % distance))% distance; | |
312 | //If the shift is a multiple of the size there is nothing to do | |
313 | if(!new_before_last_pos) | |
314 | return ret; | |
315 | ||
316 | for( new_last = p | |
317 | ; --new_before_last_pos | |
318 | ; new_last = node_traits::get_next(new_last)){ | |
319 | //empty | |
320 | } | |
321 | } | |
322 | ||
323 | //Get the first new node | |
324 | node_ptr new_first(node_traits::get_next(new_last)); | |
325 | //Now put the old beginning after the old end | |
326 | NodeTraits::set_next(old_last, p); | |
327 | NodeTraits::set_next(new_last, node_ptr()); | |
328 | ret.first = new_first; | |
329 | ret.second = new_last; | |
330 | return ret; | |
331 | } | |
332 | }; | |
333 | ||
334 | /// @cond | |
335 | ||
336 | template<class NodeTraits> | |
337 | struct get_algo<LinearSListAlgorithms, NodeTraits> | |
338 | { | |
339 | typedef linear_slist_algorithms<NodeTraits> type; | |
340 | }; | |
341 | ||
342 | /// @endcond | |
343 | ||
344 | } //namespace intrusive | |
345 | } //namespace boost | |
346 | ||
347 | #include <boost/intrusive/detail/config_end.hpp> | |
348 | ||
349 | #endif //BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP |