]>
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_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 | ||
27 | namespace boost { | |
28 | namespace 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> | |
51 | template<class NodeTraits> | |
52 | class 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 | BOOST_INTRUSIVE_FORCEINLINE 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 | 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); } | |
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 | 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); } | |
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 | 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); } | |
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 | BOOST_INTRUSIVE_FORCEINLINE 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 | 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); } | |
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 | ||
393 | template<class NodeTraits> | |
394 | struct 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 |